PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimum Manhattan Distance Approach to Multiple Criteria Decision Making in Multiobjective Optimization Problems

Wei-Yu Chiu, Gary G. Yen, Teng-Kuei Juan

arXiv:1705.01705v1math.OC

TL;DR

Selecting a final solution from Pareto-optimal alternatives is difficult when preference models require subjective inputs or lack geometric interpretation. The paper proposes minimum Manhattan distance selection from a normalized ideal vector and establishes its equivalence to weighted-sum and divide-and-conquer approaches. The resulting framework supports geometric knee selection, systematic weighting, efficient evaluation, and scalable knee definitions.

  • Problem

    Existing MCDM approaches may require subjective decision-maker weighting, careful normalization, and lack geometric interpretations valued in evolutionary computation.

  • Method

    The MMD approach selects the vector minimizing Manhattan distance from a normalized ideal vector and connects this procedure theoretically with weighted-sum and divide-and-conquer knee selection.

  • Results

    MMD, weighted-sum, and divide-and-conquer approaches yielded the same final solutions in 2-D, 3-D, and 5-D MCDM problems.

  • Takeaways & Limitations

    The approach provides geometric interpretations, systematic weighting, efficient matrix-based evaluation, and scalable definitions of knees and knee solutions.

Abstract

from arXiv · show

A minimum Manhattan distance (MMD) approach to multiple criteria decision making in multiobjective optimization problems (MOPs) is proposed. The approach selects the final solution corresponding with a vector that has the MMD from a normalized ideal vector. This procedure is equivalent to the knee selection described by a divide and conquer approach that involves iterations of pairwise comparisons. Being able to systematically assign weighting coefficients to multiple criteria, the MMD approach is equivalent to a weighted-sum (WS) approach. Because of the equivalence, the MMD approach possesses rich geometric interpretations that are considered essential in the field of evolutionary computation. The MMD approach is elegant because all evaluations can be performed by efficient matrix calculations without iterations of comparisons. While the WS approach may encounter an indeterminate situation in which a few solutions yield almost the same WS, the MMD approach is able to determine the final solution discriminately. Since existing multiobjective evolutionary algorithms aim for a posteriori decision making, i.e., determining the final solution after a set of Pareto optimal solutions is available, the proposed MMD approach can be combined with them to form a powerful solution method of solving MOPs. Furthermore, the approach enables scalable definitions of the knee and knee solutions.

I. INTRODUCTION

The paper addresses final-solution selection in multiobjective optimization, where preference inputs can be burdensome and geometric interpretations are valued. It proposes an a posteriori MMD approach connected theoretically to knee selection, weighted sums, and divide-and-conquer comparisons.

  • Motivation: MCDM selects one solution from Pareto-optimal alternatives according to multiple criteria after solving a multiobjective optimization problem.MOEAs produce approximate Pareto sets and fronts, from which a final solution must be selected.
  • Motivation: Weighting-based preference models may require normalization, depend on APF shape, and rely heavily on subjective decision-maker inputs.Quantifying preferences can also be difficult, particularly when many objectives are involved.
  • Knee selection: Knee solutions seek strong overall performance by allowing substantial improvement in some objectives with only insignificant degradation in others.Their geometric interpretation motivates their use as a preference model in evolutionary computation.
  • Proposed approach: The proposed MMD approach performs a posteriori MCDM and can be combined with most MOEAs because decision making is separated from optimization.If different MOEAs produce the same APF, the MCDM result is unchanged.
  • Contributions: MMD, weighted-sum, and divide-and-conquer approaches are theoretically connected, enabling geometric interpretations, systematic weighting, and scalable knee definitions.The framework does not require differentiable objective functions or prior preference information.

II. PROBLEM FORMULATIONS AND KNEE SELECTION

The paper formulates MCDM over approximate Pareto fronts and develops knee selection through pairwise comparisons. The divide-and-conquer procedure favors transitions with positive net improvement and can reduce candidates iteratively until one solution remains.

  • Problem formulation: Pareto dominance requires no worse objective values in every dimension and a strict improvement in at least one dimension.Nondominated points form the Pareto-optimal set, whose objective-image is the Pareto front.
  • Problem formulation: An MCDM problem selects one solution from an approximate Pareto set using information represented by the corresponding approximate Pareto front.The task can be challenging when the number of objectives or candidate solutions is large.
  • Knee selection: Knee selection prefers transitions whose improvement percentage in one objective outweighs degradation in another.For three or more objectives, the criterion generalizes to a positive net improvement percentage.
  • Divide and conquer: Pairwise comparisons halve the number of candidate solutions after each iteration and ideally require log2 M iterations for M solutions.For M = 8, the figure illustrates log2 8 comparison iterations.
  • Knee selection: For three objectives, a transition of (−20%, 15%, 15%) is preferred because its net improvement is 10%.The calculation is −20% + 15% + 15% = 10%.

III. DIVIDE AND CONQUER APPROACH

The divide-and-conquer approach formalizes knee selection through pairwise net-improvement comparisons, grouping incomparable solutions into equivalence classes. A unique preferred class enables consistent knee definitions, while matrix calculations provide an efficient implementation.

  • The approach defines a net-improvement preference model for comparing solutions pairwise.
  • Transition direction does not affect preference because a positive comparison in one direction corresponds to a negative comparison in the reverse direction.
  • Solutions with zero net improvement are treated as equivalent and grouped into equivalence classes to avoid incomparability.
  • The induced equivalence relation partitions the solution set, and the divide-and-conquer procedure identifies a unique most-preferred class.
  • The unique class defines the knee and knee solution, while pairwise iterations halve the candidate set and can be replaced by matrix calculations.

IV. MINIMUM MANHATTAN DISTANCE APPROACH

The MMD approach selects the solution closest to a normalized ideal vector and is theoretically equivalent to both weighted-sum and divide-and-conquer knee selection. Its Manhattan-distance formulation supports geometric interpretation, systematic weighting, efficient matrix evaluation, and handling of several front shapes.

  • The D&C approach is transformed into a weighted-sum formulation, which is then transformed into MMD by adding entries of an ideal vector.This establishes the equivalence among D&C, weighted-sum, and MMD formulations.
  • The MMD approach selects the point in the normalized Pareto front with minimum Manhattan distance from the normalized ideal vector.The Manhattan norm is the 1-norm, or taxicab norm.
  • The MMD approach systematically assigns objective weights from maximum objective spreads and can be evaluated through efficient matrix calculations.Unlike D&C, it does not require iterations of pairwise comparisons.
  • Geometrically, MMD enlarges a rhombus centered at the normalized ideal vector until it first intersects the normalized Pareto front.The minimum radius indicates closeness to the ideal vector; a smaller minimum radius implies a more bent normalized front.
  • For concave fronts, MMD can select extreme vectors, including both endpoints when all other nondominated vectors have greater Manhattan distance.If the front is a line segment, all vectors on the line can be selected as extreme vectors.
  • For discontinuous fronts, MMD selects vectors on the left side of the segment connecting the two extreme vectors, selecting extremes when all nonextreme vectors lie on the right.

V. NUMERICAL RESULTS

The numerical-results section examines the proposed methodology across multiple settings, including equivalent formulations, practical concerns, benchmark MOPs, and a real-world MCDM problem.

  • The experiments examine equivalence using 2-D, 3-D, and 5-D approximate Pareto fronts.
  • The study investigates practical concerns and evaluates the MMD approach on benchmark MOPs and a real-world MCDM problem.

A. Equivalence Analysis

Across 2-D, 3-D, and 5-D cases, the MMD, WS, and D&C approaches select the same solution. Their geometric interpretations differ by dimensionality, while D&C uses pairwise comparisons.

  • A. Equivalence Analysis: In 2-D MOP1, MMD uses a rhombus, WS a line, and D&C pairwise comparisons to represent equivalent selection procedures.The MMD rhombus expands from the ideal vector until it intersects the nondominated approximate Pareto front.
  • A. Equivalence Analysis: In 3-D MOP5, MMD becomes a regular octahedron, WS a plane, and D&C a sequence of pairwise comparisons yielding the same solution.The octahedron is enlarged around the ideal vector until it intersects the nondominated approximate Pareto front.
  • A. Equivalence Analysis: In 5-D scalable DTLZ1, MMD and WS yield the same solution, while four random D&C comparison orders demonstrate order independence.The higher-dimensional case is evaluated algebraically because geometric visualization is unavailable.

B. Practical Concerns

The approaches produced identical final solutions across tested dimensions, but their practical behavior differs. WS can struggle when weighted sums are nearly indistinguishable, whereas D&C can require more computation.

  • B. Practical Concerns: The MMD, WS, and D&C approaches yielded the same final solutions in 2-D, 3-D, and 5-D MCDM problems.This establishes agreement across the dimensional cases examined in the study.
  • B. Practical Concerns: D&C can consume relatively more computational time than the equivalent MMD and WS approaches.The additional cost is associated with its iterative pairwise-comparison procedure.
  • B. Practical Concerns: When weighted sums are almost identical, WS has difficulty finding the final solution, whereas MMD and D&C can distinguish among alternatives.The imbalance between objective magnitudes and their maximum spreads causes one normalized term to dominate the weighted sum.
  • B. Practical Concerns: Four random D&C comparison orders in DTLZ1 led to the same solution, indicating independence from comparing order in that experiment.The trials are presented as a practical check of the pairwise procedure.

C. Further Exploration

The MMD approach is applied to convex and discontinuous Pareto fronts using normalized samples closest to the ideal vector in Manhattan distance. Discontinuous-front geometry changes which samples are selected.

  • C. Further Exploration: For convex Pareto fronts in ZDT1 and related test problems, MMD selects normalized samples closest to the ideal vector by Manhattan distance.The approach is evaluated on population samples drawn from the true Pareto fronts.
  • C. Further Exploration: For discontinuous fronts, ZDT3 selects a sample most distant from the connecting extreme-vector line in Manhattan norm, unlike MOP4 and MOP6.MOP4 and MOP6 select samples on the opposite side of the line but close to it.

D. Real-World Application

The real-world application evaluates plant-layout alternatives with six criteria and compares MMD with established MCDM methods. MMD agrees with the consensus choice while avoiding some method-specific decision complications.

  • D. Real-World Application: The plant-layout problem evaluates 18 alternatives using flow distance, adjacency score, shape ratio, flexibility, accessibility, and maintenance.Negative signs on adjacency score, flexibility, and accessibility indicate larger-the-better quantities.
  • D. Real-World Application: Most compared MCDM approaches rank x11, x15, and x17 among the top three, with x15 selected as the consensus choice.The comparison includes GRA, DEA, TOPSIS, and SAW.
  • D. Real-World Application: The proposed MMD approach is consistent with selecting x15 and is described as relatively simple and elegant.The paper contrasts this with parameter selection, multiple candidates, or inconsistent rankings in some alternative methods.
  • D. Real-World Application: GRA requires a prescribed distinguishing coefficient, DEA leaves three alternatives for further decision, and TOPSIS selects x11 instead of the consensus.SAW is effective in this example but is reported to have limited literature use because it can produce illogical results.

VI. CONCLUSION

The paper proposes an MMD approach for selecting a final solution from Pareto-optimal solutions in MOPs, combining systematic weighting with geometric interpretations and knee-selection equivalence.

  • The MMD approach selects a final solution while avoiding subjective preference inputs from the decision maker.
  • MMD systematically generates weighting coefficients and is equivalent to both a weighted-sum approach and knee selection via divide and conquer.
  • The approach offers rich geometric interpretations and evaluates alternatives through efficient matrix calculations.
  • Simulations were performed to illustrate the effectiveness of the proposed methodology.
Loading 1705.01705v1…