A Post-Optimality Analysis Algorithm for Multi-Objective Optimization

Algorithms for multi-objective optimization problems are designed to generate a single Pareto optimum (non-dominated solution) or a set of Pareto optima that reflect the preferences of the decision-maker. If a set of Pareto optima are generated, then it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optima using an unbiased technique of filtering solutions. This suggests the need for an efficient selection procedure to identify such a preferred subset that reflects the preferences of the decision-maker with respect to the objective functions. Selection procedures typically use a value function or a scalarizing function to express preferences among objective functions. This paper introduces and analyzes the Greedy Reduction (GR) algorithm for obtaining subsets of Pareto optima from large solution sets in multi-objective optimization. Selection of these subsets is based on maximizing a scalarizing function of the vector of percentile ordinal rankings of the Pareto optima within the larger set. A proof of optimality of the GR algorithm that relies on the non-dominated property of the vector of percentile ordinal rankings is provided. The GR algorithm executes in linear time in the worst case. The GR algorithm is illustrated on sets of Pareto optima obtained from five interactive methods for multi-objective optimization and three non-linear multi-objective test problems. These results suggest that the GR algorithm provides an efficient way to identify subsets of preferred Pareto optima from larger sets.     

Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation

This paper investigates the use of multi-objective methods to guide the search when solving single-objective optimisation problems with genetic algorithms. Using the job shop scheduling and travelling salesman problems as examples, experiments demonstrate that the use of helper-objectives (additional objectives guiding the search) significantly improves the average performance of a standard GA. The helper-objectives guide the search towards solutions containing good building blocks and help the algorithm escape local optima. The experiments reveal that the approach works if the number of simultaneously used helper-objectives is low. However, a high number of helper-objectives can be used in the same run by changing the helper-objectives dynamically. The experiments reveal that for the majority of problem instances studied, the proposed approach significantly outperforms a traditional GA.The experiments also demonstrate that controlling the proportion of non-dominated solutions in the population is very important when using helper-objectives, since the presence of too many non-dominated solutions removes the selection pressure in the algorithm.     

Exact hybrid algorithms for solving a bi-objective vehicle routing problem

The paper investigates a capacitated vehicle routing problem with two objectives: (1) minimization of total travel cost and (2) minimization of the length of the longest route. We present algorithmic variants for the exact determination of the Pareto-optimal solutions of this bi-objective problem. Our approach is based on the adaptive ε-constraint method. For solving the resulting single-objective subproblems, we apply a branch-and-cut technique, using (among others) a novel implementation of Held-Karp-type bounds. Incumbent solutions are generated by means of a single-objective genetic algorithm and, alternatively, by the multi-objective NSGA-II algorithm. Experimental results for a benchmark of 54 test instances from the TSPLIB are reported.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

Parallelization of population-based multi-objective meta-heuristics: An empirical study

In single-objective optimization it is possible to find a global optimum, while in the multi-objective case no optimal solution is clearly defined, but several that simultaneously optimize all the objectives. However, the majority of this kind of problems cannot be solved exactly as they have very large and highly complex search spaces. Recently, meta-heuristic approaches have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. Most of these meta-heuristics use a population of solutions, and hence the runtime increases when the population size grows. An interesting way to overcome this problem is to apply parallel processing. This paper analyzes the performance of several parallel paradigms in the context of population-based multi-objective meta-heuristics. In particular, we evaluate four alternative parallelizations of the Pareto simulated annealing algorithm, in terms of quality of the solutions, and speedup.     

Heuristic approaches to determine base-stock levels in a serial supply chain with a single objective and with multiple objectives

This paper deals with the problem of determination of installation base-stock levels in a serial supply chain. The problem is treated first as a single-objective inventory-cost optimization problem, and subsequently as a multi-objective optimization problem by considering two cost components, namely, holding costs and shortage costs. Variants of genetic algorithms are proposed to determine the best base-stock levels in the single-objective case. All variants, especially random-key gene-wise genetic algorithm (RKGGA), show an excellent performance, in terms of convergence to the best base-stock levels across a variety of supply chain settings, with minimum computational effort. Heuristics to obtain base-stock levels are proposed, and heuristic solutions are introduced in the initial population of the RKGGA to expedite the convergence of the genetic search process. To deal with the multi-objective supply-chain inventory optimization problem, a simple multi-objective genetic algorithm is proposed to obtain a set of non-dominated solutions.     

Approximate Pareto sets of minimal size for multi-objective optimization problems

We are interested in a problem introduced by Vassilvitskii and Yannakakis (2005), the computation of a minimum set of solutions that approximates within an accuracy ε$\epsilon$ the Pareto set of a multi-objective optimization problem. We mainly establish a new 3-approximation algorithm for the bi-objective case. We also propose a study of the greedy algorithm performance for the tri-objective case when the points are given explicitly, answering an open question raised by Koltun and Papadimitriou in (2007).     

基于存档策略的多目标优化的遗传算法及其收敛性分析

设计了一种用遗传算法求解多目标优化问题的有效方法——基于存档策略的多目标优化的遗传算法,并讨论了此算法的收敛性.首先给出档案的定义,设计出基于支配关系下的带有存档策略遗传算法,并通过算例检验了算法的有效性;然后引入了两档案间的距离的概念,在此距离定义的基础上证明了算法在概率意义下是收敛的.     

A numerical method for nonconvex multi-objective optimal control problems

A numerical method is proposed for constructing an approximation of the Pareto front of nonconvex multi-objective optimal control problems. First, a suitable scalarization technique is employed for the multi-objective optimal control problem. Then by using a grid of scalarization parameter values, i.e., a grid of weights, a sequence of single-objective optimal control problems are solved to obtain points which are spread over the Pareto front. The technique is illustrated on problems involving tumor anti-angiogenesis and a fed-batch bioreactor, which exhibit bang–bang, singular and boundary types of optimal control. We illustrate that the Bolza form, the traditional scalarization in optimal control, fails to represent all the compromise, i.e., Pareto optimal, solutions.     

Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits

We introduce and test a new approach for the bi-objective routing problem known as the traveling salesman problem with profits. This problem deals with the optimization of two conflicting objectives: the minimization of the tour length and the maximization of the collected profits. This problem has been studied in the form of a single objective problem, where either the two objectives have been combined or one of the objectives has been treated as a constraint. The purpose of our study is to find solutions to this problem using the notion of Pareto optimality, i.e. by searching for efficient solutions and constructing an efficient frontier. We have developed an ejection chain local search and combined it with a multi-objective evolutionary algorithm which is used to generate diversified starting solutions in the objective space. We apply our hybrid meta-heuristic to synthetic data sets and demonstrate its effectiveness by comparing our results with a procedure that employs one of the best single-objective approaches.      

多目标规划的一种混合遗传算法

本文利用遗传算法的全局搜索内能力及直接搜索算法的局部优化能力，提出了一种用于多目标规划的混合遗传算法．与Pareto遗传算法相比．本文提出的算法能提高多目标遗传算法优化搜索效率，并保证了能得到适舍决策者要求的Pareto最优解．最后，理论与实践证明其有有效性．     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.     

Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core

This paper deals with the bi-objective multi-dimensional knapsack problem. We propose the adaptation of the core concept that is effectively used in single-objective multi-dimensional knapsack problems. The main idea of the core concept is based on the “divide and conquer” principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). The quality of the obtained solution can be adjusted according to the size of the core and there is always a trade off between the solution time and the quality of solution. In the specific study we define the core problem for the multi-objective multi-dimensional knapsack problem. After defining the core we solve the bi-objective integer programming that comprises only the core variables using the Multicriteria Branch and Bound algorithm that can generate the complete Pareto set in small and medium size multi-objective integer programming problems. A small example is used to illustrate the method while computational and economy issues are also discussed. Computational experiments are also presented using available or appropriately modified benchmarks in order to examine the quality of Pareto set approximation with respect to the solution time. Extensions to the general multi-objective case as well as to the computation of the exact solution are also mentioned.     

A GRASP algorithm for the multi-criteria minimum spanning tree problem

This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions, we use different weight vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions. This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource of CNPq.     

Annealing-tabu PAES: a multi-objective hybrid meta-heuristic

Most real-life optimization problems require taking into account not one, but multiple objectives simultaneously. In most cases these objectives are in conflict, i.e. the improvement of some objectives implies the deterioration of others. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined, but rather a set of solutions. In the last decade most papers dealing with multi-objective optimization use the concept of Pareto-optimality. The goal of Pareto-based multi-objective strategies is to generate a front (set) of non-dominated solutions as an approximation to the true Pareto-optimal front. However, this front is unknown for problems with large and highly complex search spaces, which is why meta-heuristic methods have become important tools for solving this kind of problem. Hybridization in the multi-objective context is nowadays an open research area. This article presents a novel extension of the well-known Pareto archived evolution strategy (PAES) which combines simulated annealing and tabu search. Experiments on several mathematical problems show that this hybridization allows an improvement in the quality of the non-dominated solutions in comparison with PAES, and also with its extension M-PAES.     

多品种柔性生产企业的订单调度模型及其遗传算法

以订单总完工时间最小和订单平均流程时间最小为目标函数,利用改进的多目标遗传算法生成了多品种订单调度模型.为解决组合模型的指数爆炸问题,提出了一种按规则分配订单以及订单中各作业排序相结合的集成调度思想;以一种整数和字母组合的编码方法用于可行解的表达,并在每个分目标的进化过程中,对选择、交叉、变异算子以及精英解保留策略重新进行设计,保证了解的分布性和均匀性;同时还提出了一种新的终止条件,将精英种群与分目标的子种群进行合并,从而加快收敛的速度.以典型的订单生产企业为例进行仿真实验,实验结果表明,应用该算法可以获得满意的Pareto解集.     

公交网络时刻表再协同设计的多目标优化模型

为了改善公交服务质量,公交运营者试图调整现有时刻表的发车时间,使不同线路的车次协同到达换乘站点以方便乘客换乘。针对此场景,研究了公交时刻表重新协同设计问题,提出了求解该问题的多目标模型。模型考虑了对发车间隔灵敏的乘客需求、灵活的车次协同到站方式和发车时间的规则性,分析了该多目标模型的特征和计算复杂性,表明本文研究的问题是NP-hard问题,且它的帕累托最优前沿是非凸的,设计了基于非支配排序的遗传算法求解模型。算例表明,与枚举算法相比,提出的求解算法在较短的时间内可获得高质量的帕累托解。     

New multi-objective method to solve reentrant hybrid flow shop scheduling problem

This paper focuses on the multi-objective resolution of a reentrant hybrid flow shop scheduling problem (RHFS). In our case the two objectives are: the maximization of the utilization rate of the bottleneck and the minimization of the maximum completion time. This problem is solved with a new multi-objective genetic algorithm called L-NSGA which uses the Lorenz dominance relationship. The results of L-NSGA are compared with NSGA2, SPEA2 and an exact method. A stochastic model of the system is proposed and used with a discrete event simulation module. A test protocol is applied to compare the four methods on various configurations of the problem. The comparison is established using two standard multi-objective metrics. The Lorenz dominance relationship provides a stronger selection than the Pareto dominance and gives better results than the latter. The computational tests show that L-NSGA provides better solutions than NSGA2 and SPEA2; moreover, its solutions are closer to the optimal front. The efficiency of our method is verified in an industrial field-experiment.     

A fast steady-state <Emphasis Type="Italic">ε</Emphasis>-dominance multi-objective evolutionary algorithm

Multi-objective evolutionary algorithms (MOEAs) have become an increasingly popular tool for design and optimization tasks in real-world applications. Most of the popular baseline algorithms are pivoted on the use of Pareto-ranking (that is empirically inefficient) to improve the convergence to the Pareto front of a multi-objective optimization problem. This paper proposes a new ε-dominance MOEA (EDMOEA) which adopts pair-comparison selection and steady-state replacement instead of the Pareto-ranking. The proposed algorithm is an elitist algorithm with a new preservation technique of population diversity based on the ε-dominance relation. It is demonstrated that superior results could be obtained by the EDMOEA compared with other algorithms: NSGA-II, SPEA2, IBEA, ε-MOEA, PESA and PESA-II on test problems. The EDMOEA is able to converge to the Pareto optimal set much faster especially on the ZDT test functions with a large number of decision variables.     

Multi-objective optimization of pin fin to determine the optimal fin geometry using genetic algorithm

In this study, one dimensional heat transfer in a pin fin is modeled and optimized. We used Bezier curves to determine the best geometry of the fin. The model equations are solved to analyze the heat transfer. Total heat transfer rate and fin efficiency factor are considered as two objective functions and multi-objective optimization carried out to maximize heat transfer rate and fin efficiency simultaneously. Fast and elitist non-dominated sorting genetic algorithm (NSGA-II) is used to determine a set of multiple optimum solutions, called ‘Pareto optimal solutions. The optimized results are presented with Pareto front which demonstrate conflict between two objective functions in the optimized point, both energy conservation and thermal analysis are carried out to verify the solution method and the results shows good precision.