PAVED: Pareto Front Visualization for Engineering Design

Design problems in engineering typically involve a large solution space and several potentially conflicting criteria. Selecting a compromise solution is often supported by optimization algorithms that compute hundreds of Pareto-optimal solutions, thus informing a decision by the engineer. However, the complexity of evaluating and comparing alternatives increases with the number of criteria that need to be considered at the same time. We present a design study on Pareto front visualization to support engineers in applying their expertise and subjective preferences for selection of the most-preferred solution. We provide a characterization of data and tasks from the parametric design of electric motors. The requirements identified were the basis for our development of PAVED, an interactive parallel coordinates visualization for exploration of multi-criteria alternatives. We reflect on our user-centered design process that included iterative refinement with real data in close collaboration with a domain expert as well as a summative evaluation in the field. The results suggest a high usability of our visualization as part of a real-world engineering design workflow. Our lessons learned can serve as guidance to future visualization developers targeting multi-criteria optimization problems in engineering design or alternative domains.     

The Pareto-optimal Solution Set of the Equilibrium Network Design Problem with Multiple Commensurate Objectives

The focus of this paper is to develop a solution framework to study equilibrium transportation network design problems with multiple objectives that are mutually commensurate. Objective parameterization, or scalarization, forms the core idea of this solution approach, by which a multi-objective problem can be equivalently addressed by tackling a series of single-objective problems. In particular, we develop a parameterization-based heuristic that resembles an iterative divide-and-conquer strategy to locate a Pareto-optimal solution in each divided range of commensurate parameters. Unlike its previous counterparts, the heuristic is capable of asymptotically exhausting the complete Pareto-optimal solution set and identifying parameter ranges that exclude any Pareto-optimal solution. Its algorithmic effectiveness and solution characteristics are justified by a set of numerical examples, from which we also gain additional insights about its solution generation behavior and the tradeoff between the computation cost and solution quality.     

Obtaining accurate classifiers with Pareto-optimal and near Pareto-optimal rules

In the field of data mining, confidence and support are often used to measure the quality of a rule. Pareto-optimal rules, which are Pareto-optimal in terms of confidence and support maximization, have an interesting characteristic that Pareto-optimal rules maximize other various rule evaluation criteria. In this paper, we examine the effectiveness of designing classifiers from Pareto-optimal rules. We consider not only Pareto-optimal rules but also near Pareto-optimal rules. To show the effectiveness, we compare classifiers obtained from Pareto-optimal and near Pareto-optimal rules with classifiers obtained from the rules that have large value in terms of other different rule evaluation criteria. Eight criteria are examined in this paper: CF, confidence, cover, Laplace, lift, random, slave, support. Through computational experiments, we show that classifiers obtained from Pareto-optimal rules have higher accuracy than those from rules extracted according to the other criteria. This work was presented in part and awarded as Young Author Award at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Two-machine flow-shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow-shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is NP-hard and for its solution we provide two different approximation algorithms, a pseudo-polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto-optimal points (this problem is NP-hard due to the NP-hardness of the same problem variation on a single machine [20]). We show that this problem can be solved in pseudo-polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most (1+?)R and a makespan value of at most (1+?)K. This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.     

The regularization ofNB-scheme in differential games

The optimality principles in non-zero sum differential games and multicriterial control problems taken from the corresponding static (simultaneous) game theory are usually dynamic unstable (time inconsistent), thus their use becomes questionable if special regularization attempts are not made. This important aspect was first considered in [1], but also in the earlier paper of Strotz [7] this was shown for a special control problem with discount payoff. We have shown in [2] that many of the known procedures (excluding those based on scalarization of the payoff vector), of selecting of a special Pareto-optimal solution from the set of all Pareto-optimal solutions are dynamic unstable (time-inconsistent) and therefore the regularization procedures leading to the dynamic stable optimality principles are purposed [3]. It turns out that also in the Nash [4] bargaining process the regularization attempt can be made by constructng a special equation for the conflict point. The idea of the method is closely connected with the paper [5]. The special attention to the time-consistency problem is given also in the recent publications [6,8].This paper is financially supported by Russian Fundamental Research Foundation (project N 93-011-1714).     

Design for Six Sigma through collaborative multiobjective optimization

This paper presents a global methodology for designing product for Six Sigma. First, we combine a feasibility-modeling technique with an interactive multiobjective algorithm taking into account the decision maker’s preferences (IMOP) to generate several Pareto-optimal solutions that maintain a probability of constraint satisfaction. These solutions are called reliable Pareto-optimal solutions.The solutions found by the algorithm fulfill as much as possible the decision makers’ requirements. Second, we develop a procedure for choosing a solution for implementation from among the reliable Pareto-optimal solutions generated by the algorithm. This procedure is based on the robust design and philosophy of Six Sigma. Finally, the critical characteristics are identified to help the managers develop the manufacturing system and its related control plans in order to achieve quality products. The proposed methodology is applied to vehicle crash-worthiness design optimization for side impact with structural weight and front door velocity under side impact as objectives.     

Mining Pareto-optimal rules with respect to support and confirmation or support and anti-support

In knowledge discovery and data mining many measures of interestingness have been proposed in order to measure the relevance and utility of the discovered patterns. Among these measures, an important role is played by Bayesian confirmation measures, which express in what degree a premise confirms a conclusion. In this paper, we are considering knowledge patterns in a form of “if…, then…” rules with a fixed conclusion. We investigate a monotone link between Bayesian confirmation measures, and classic dimensions being rule support and confidence. In particular, we formulate and prove conditions for monotone dependence of two confirmation measures enjoying some desirable properties on rule support and confidence. As the confidence measure is unable to identify and eliminate non-interesting rules, for which a premise does not confirm a conclusion, we propose to substitute the confidence for one of the considered confirmation measures in mining the Pareto-optimal rules. We also provide general conclusions for the monotone link between any confirmation measure enjoying the desirable properties and rule support and confidence. Finally, we propose to mine rules maximizing rule support and minimizing rule anti-support, which is the number of examples, which satisfy the premise of the rule but not its conclusion (called counter-examples of the considered rule). We prove that in this way we are able to mine all the rules maximizing any confirmation measure enjoying the desirable properties. We also prove that this Pareto-optimal set includes all the rules from the previously considered Pareto-optimal borders.     

Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs

We consider the scheduling problem in which two agents (agents A and B), each having its own job set (containing the A-jobs and B-jobs, respectively), compete to process their own jobs in a two-machine flowshop. Each agent wants to maximize a certain criterion depending on the completion times of its jobs only. Specifically, agent A desires to maximize either the weighted number of just-in-time (JIT) A-jobs that are completed exactly on their due dates or the maximum weight of the JIT A-jobs, while agent B wishes to maximize the weighted number of JIT B-jobs. Evidently four optimization problems can be formulated by treating the two agents’ criteria as objectives and constraints of the corresponding optimization problems. We focus on the problem of finding the Pareto-optimal schedules and present a bicriterion analysis of the problem. Solving this problem also solves the other three problems of bicriterion scheduling as a by-product. We show that the problems under consideration are either polynomially or pseudo-polynomially solvable. In addition, for each pseudo-polynomial-time solution algorithm, we show how to convert it into a two-dimensional fully polynomial-time approximation scheme for determining an approximate Pareto-optimal schedule. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.     

A random search heuristic for a multi-objective production planning

Real world production planning is involved in optimizing different objectives while considering a spectrum of parameters, decision variables, and constraints of the corresponding cases. This comes from the fact that production managers desire to utilize from an ideal production plan by considering a number of objectives over a set of technological constraints. This paper presents a new multi-objective production planning model which is proved to be NP-Complete. So a random search heuristic is proposed to explore the feasible solution space with the hope of finding the best solution in a reasonable time while extracting a set of Pareto-optimal solutions. Then each Pareto-optimal solution is considered as an alternative production plan in the hand of production manager. Both the modeling and the solution processes are carried out for a real world problem and the results are reported briefly. Also, performance of the proposed problem-specific heuristic is verified by comparing it with a multi-objective genetic algorithm on a set randomly generated test data.     

一类新型动态多目标鲁棒进化优化方法

传统动态多目标优化问题（Dynamic multi-objective optimization problems,DMOPs）的求解方法,通常需要在新环境下,通过重新激发寻优过程,获得适应该环境的Pareto最优解.这可能导致较高的计算代价和资源成本,甚至无法在有限时间内执行该优化解.由此,提出一类寻找动态鲁棒Pareto最优解集的进化优化方法.动态鲁棒Pareto解集是指某一时刻下的Pareto较优解可以以一定稳定性阈值,逼近未来多个连续动态环境下的真实前沿,从而直接作为这些环境下的Pareto解集,以减小计算代价.为合理度量Pareto解的环境适应性,给出了时间鲁棒性和性能鲁棒性定义,并将其转化为两类鲁棒优化模型.引入基于分解的多目标进化优化方法和无惩罚约束处理方法,构建了动态多目标分解鲁棒进化优化方法.特别是基于移动平均预测模型实现了未来动态环境下适应值的多维时间序列预测.基于提出的两类新型性能评价测度,针对8个典型动态测试函数的仿真实验,结果表明该方法得到满足决策者精度要求,且具有较长平均生存时间的动态鲁棒Pareto最优解.     

Algorithms for path medi-centers of a tree

We consider the problem of finding an optimal location of a path on a tree, using combinations of minisum and minimax criteria (which are respectively maximal distance and average distance from the path to customers situated at the vertices). The case of linear combination of the two criteria and the case where one criterion is optimized subject to a restriction on the value of the other are considered and linear-time algorithms for these problems are presented. It is proved that the representation of the set of Pareto-optimal paths in the space of criteria has cardinality not greater than n−1, where n is the number of vertices of the tree, and can be obtained in O(n log n) time, although the number of Pareto-optimal paths can be O(n²)     

On the Complexity of Pareto-Optimal Nash and Strong Equilibria

We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.     

A simulated annealing approach to a bi-criteria sequencing problem in a two-stage supply chain

In this paper, a multi-objective simulated annealing (MOSA) solution approach is proposed to a bi-criteria sequencing problem to coordinate required set-ups between two successive stages of a supply chain in a flow shop pattern. Each production batch has two distinct attributes and a set-up occurs in each stage when the corresponding attribute of the two successive batches are different. There are two objectives including: minimizing total set-ups and minimizing the maximum number of set-ups between the two stages that are both NP-hard problems. The MOSA approach starts with an initial set of locally non-dominated solutions generated by an initializing heuristic. The set is then iteratively updated through the annealing process in search for true Pareto-optimal frontier until a stopping criterion is met. Performance of the proposed MOSA was evaluated using true Pareto-optimal solutions of small problems found via total enumeration. It was also compared against a lower bound in large problems. Comparative experiments show that the MOSA is robust in finding true Pareto-optimal solutions in small problems. It was also shown that MOSA is very well-performing in large problems and that it outperforms an existing multi-objective genetic algorithm (MOGA) in terms of quality of solutions.     

DOPGA: a new fitness assignment scheme for multi-objective evolutionary algorithms

In this article, a new fitness assignment scheme to evaluate the Pareto-optimal solutions for multi-objective evolutionary algorithms is proposed. The proposed DOmination Power of an individual Genetic Algorithm (DOPGA) method can order the individuals in a form in which each individual (the so-called solution) could have a unique rank. With this new method, a multi-objective problem can be treated as if it were a single-objective problem without drastically deviating from the Pareto definition. In DOPGA, relative position of a solution is embedded into the fitness assignment procedures. We compare the performance of the algorithm with two benchmark evolutionary algorithms (Strength Pareto Evolutionary Algorithm (SPEA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2)) on 12 unconstrained bi-objective and one tri-objective test problems. DOPGA significantly outperforms SPEA on all test problems. DOPGA performs better than SPEA2 in terms of convergence metric on all test problems. Also, Pareto-optimal solutions found by DOPGA spread better than SPEA2 on eight of 13 test problems.     

A genetic algorithm approach for multi-objective optimization of supply chain networks

Supply chain network (SCN) design is to provide an optimal platform for efficient and effective supply chain management. It is an important and strategic operations management problem in supply chain management, and usually involves multiple and conflicting objectives such as cost, service level, resource utilization, etc. This paper proposes a new solution procedure based on genetic algorithms to find the set of Pareto-optimal solutions for multi-objective SCN design problem. To deal with multi-objective and enable the decision maker for evaluating a greater number of alternative solutions, two different weight approaches are implemented in the proposed solution procedure. An experimental study using actual data from a company, which is a producer of plastic products in Turkey, is carried out into two stages. While the effects of weight approaches on the performance of proposed solution procedure are investigated in the first stage, the proposed solution procedure and simulated annealing are compared according to quality of Pareto-optimal solutions in the second stage.     

基于环境经济调度问题的空间自适应划分多目标优化

提出一种基于空间自适应划分的多目标优化算法. 为了增强种群的收敛性和多样性, 多维搜索空间被划分成多个网格, 网格内的粒子通过共享“引导”粒子的经验信息调整自身的速度和位置, 并引入年龄观测器实时记录引导粒子对Pareto 解集所做的贡献, 及时更新引导粒子, 以增强算法的全局搜索能力. 对多目标测试函数以及环境经济调度问题进行了仿真实验, 实验结果表明, 所提出算法能对解空间进行更加全面、充分的探索, 快速找到一组分布具有较好的逼近性、宽广性和均匀性的最优解集合.

     

Solving a reverse supply chain design problem by improved Benders decomposition schemes

In this paper we propose improved Benders decomposition schemes for solving a remanufacturing supply chain design problem (RSCP). We introduce a set of valid inequalities in order to improve the quality of the lower bound and also to accelerate the convergence of the classical Benders algorithm. We also derive quasi Pareto-optimal cuts for improving convergence and propose a Benders decomposition scheme to solve our RSCP problem. Computational experiments for randomly generated networks of up to 700 sourcing sites, 100 candidate sites for locating reprocessing facilities, and 50 reclamation facilities are presented. In general, according to our computational results, the Benders decomposition scheme based on the quasi Pareto-optimal cuts outperforms the classical algorithm with valid inequalities.     

An agenda-based framework for multi-issue negotiation

This paper presents a new model for multi-issue negotiation under time constraints in an incomplete information setting. The issues to be bargained over can be associated with a single good/service or multiple goods/services. In our agenda-based model, the order in which issues are bargained over and agreements are reached is determined endogenously, as part of the bargaining equilibrium. In this context we determine the conditions under which agents have similar preferences over the implementation scheme and the conditions under which they have conflicting preferences. Our analysis shows the existence of equilibrium even when both players have uncertain information about each other, and each agent's information is its private knowledge. We also study the properties of the equilibrium solution and determine conditions under which it is unique, symmetric, and Pareto-optimal.     

多目标遗传算法求解认知无线电性能优化问题

认知无线电的性能优化是一个动态多目标优化问题。现有的Bio-CR模型基于遗传算法优化认知无线电的性能,它使用线性加权方法将此多目标优化问题简化为了一个单目标优化问题。针对Bio-CR很难确定每个适应度函数的权值和容易漏掉一些最优解的问题,提出了基于多目标遗传算法的认知无线电性能优化算法CREA。CREA能够根据信道条件和用户服务需求的变化动态地调整传输参数以优化性能,不仅克服了Bio-CR的两个缺点,而且通过保存计算结果进一步减少了遗传算法的运行次数。CREA首先根据信道条件的变化动态确定一组适应度函数,然后运行多目标遗传算法获得一个Pareto-optimal set,最后根据用户服务需求从中选出一个最满意解,并通知认知无线电更新自己的传输参数。Matlab仿真实验证明了CREA的正确性和有效性。     

一种损失规避供应链协调模型

研究了损失规避供应链的协调建模问题。在介绍了供应链成员的损失规避效用后,我们提出了一种帕累托最优框架下的协调定义。随后,我们分析了这样一类两阶段供应链系统：损失规避供应商和零售商的效用函数具有非递减灵敏特性,得出了系统最优解决方案。结果表明,帕累托最优分配规则依赖于供应链的总利润水平,而最优决策行为一般不同于风险中立下的最优决策,所以常用协调合同不能协调该供应链,必须设计新的合同形式。