An interactive algorithm to find the most preferred solution of multi-objective integer programs

In this paper, we develop an interactive algorithm that finds the most preferred solution of a decision maker (DM) for multi-objective integer programming problems. We assume that the DM’s preferences are consistent with a quasiconcave value function unknown to us. Based on the properties of quasiconcave value functions and pairwise preference information obtained from the DM, we generate constraints to restrict the implied inferior regions. The algorithm continues iteratively and guarantees to find the most preferred solution for integer programs. We test the performance of the algorithm on multi-objective assignment, knapsack, and shortest path problems and show that it works well.     

A multi-objective optimization evolutionary algorithm incorporating preference information based on fuzzy logic

A multi-objective optimization evolutionary algorithm incorporating preference information interactively is proposed. A new nine grade evaluation method is used to quantify the linguistic preferences expressed by the decision maker (DM) so as to reduce his/her cognitive overload. When comparing individuals, the classical Pareto dominance relation is commonly used, but it has difficulty in dealing with problems involving large numbers of objectives in which it gives an unmanageable and large set of Pareto optimal solutions. In order to overcome this limitation, a new outranking relation called “strength superior” which is based on the preference information is constructed via a fuzzy inference system to help the algorithm find a few solutions located in the preferred regions, and the graphical user interface is used to realize the interaction between the DM and the algorithm. The computational complexity of the proposed algorithm is analyzed theoretically, and its ability to handle preference information is validated through simulation. The influence of parameters on the performance of the algorithm is discussed and comparisons to another preference guided multi-objective evolutionary algorithm indicate that the proposed algorithm is effective in solving high dimensional optimization problems.     

An interactive evolutionary multi-objective optimization algorithm with a limited number of decision maker calls

This paper presents a preference-based method to handle optimization problems with multiple objectives. With an increase in the number of objectives the computational cost in solving a multi-objective optimization problem rises exponentially, and it becomes increasingly difficult for evolutionary multi-objective techniques to produce the entire Pareto-optimal front. In this paper, an evolutionary multi-objective procedure is combined with preference information from the decision maker during the intermediate stages of the algorithm leading to the most preferred point. The proposed approach is different from the existing approaches, as it tries to find the most preferred point with a limited budget of decision maker calls. In this paper, we incorporate the idea into a progressively interactive technique based on polyhedral cones. The idea is also tested on another progressively interactive approach based on value functions. Results are provided on two to five-objective unconstrained as well as constrained test problems.     

Genetic local search for multi-objective combinatorial optimization

The paper presents a new genetic local search (GLS) algorithm for multi-objective combinatorial optimization (MOCO). The goal of the algorithm is to generate in a short time a set of approximately efficient solutions that will allow the decision maker to choose a good compromise solution. In each iteration, the algorithm draws at random a utility function and constructs a temporary population composed of a number of best solutions among the prior generated solutions. Then, a pair of solutions selected at random from the temporary population is recombined. Local search procedure is applied to each offspring. Results of the presented experiment indicate that the algorithm outperforms other multi-objective methods based on GLS and a Pareto ranking-based multi-objective genetic algorithm (GA) on travelling salesperson problem (TSP).     

多目标0-1规划问题的蜂群算法

针对多目标0-1规划问题,本文给出一种新型的智能优化算法——蜂群算法进行求解,并通过实例验证,与遗传算法、蚁群算法和元胞蚁群算法作了相应比较。就多目标0-1规划问题而言,蜂群算法能得到更多的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.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these algorithms.     

解非线性规划问题的非参数罚函数多目标正交遗传算法

对非线性规划问题的处理通常采用罚函数法,使用罚函数法的困难在于参数的选取.本文提出了一种解非线性规划问题非参数罚函数多目标正交遗传算法,对违反约束的个体进行动态的惩罚以保持群体中不可行解的一定比例,从而不但有效增加种群的多样性,而且避免了传统的过度惩罚缺陷,使群体更好地向最优解逼近.数据实验表明该算法对带约束的非线性规划问题求解是非常有效的.     

A new mechanism to maintain diversity in multi-objective metaheuristics

In this article, a new mechanism to spread the solutions generated by a multi-objective evolutionary algorithm is proposed. This approach is based on the use of stripes that are applied in objective function space and is independent of the search engine adopted. Additionally, it overcomes some of the drawbacks of other previous proposals such as the ?-dominance method. In order to validate the proposed approach, it is coupled to a multi-objective particle swarm optimizer and its performance is assessed with respect to that of state-of-the-art algorithms, using standard test problems and performance measures taken from the specialized literature. The results indicate that the proposed approach is a viable diversity maintenance mechanism that can be incorporated to any multi-objective metaheuristic used for multi-objective optimization.     

基于遗传算法的多目标柔性工作车间调度问题求解

本文针对柔性工作车间调度问题给出了一个有意义的综合目标尽可能缩短制造周期的同时尽可能的减少机器负荷。由于传统遗传算法在多目标柔性工作车间调度问题上的局限性，我们提出了一种改进遗传算法：首先，我们给出了针对综合目标的工序调度算法获得初始集合；接着，针对柔性工作车间调度问题的特点，我们在常用的基于工序顺序的编码方法上融入了基于机器分配的编码方法，并据此设计了相应的交叉变异操作；最后借鉴了物种进化现象中的环境迁移思想设计了解决多目标优化问题的迁移操作。实验结果表明，改进的遗传算法在多目标柔性工作车间调度问题的解决上要优于传统遗传算法。     

An efficient multi-objective PSO algorithm assisted by Kriging metamodel for expensive black-box problems

The huge computational overhead is the main challenge in the application of community based optimization methods, such as multi-objective particle swarm optimization and multi-objective genetic algorithm, to deal with the multi-objective optimization involving costly simulations. This paper proposes a Kriging metamodel assisted multi-objective particle swarm optimization method to solve this kind of expensively black-box multi-objective optimization problems. On the basis of crowding distance based multi-objective particle swarm optimization algorithm, the new proposed method constructs Kriging metamodel for each expensive objective function adaptively, and then the non-dominated solutions of the metamodels are utilized to guide the update of particle population. To reduce the computational cost, the generalized expected improvements of each particle predicted by metamodels are presented to determine which particles need to perform actual function evaluations. The suggested method is tested on 12 benchmark functions and compared with the original crowding distance based multi-objective particle swarm optimization algorithm and non-dominated sorting genetic algorithm-II algorithm. The test results show that the application of Kriging metamodel improves the search ability and reduces the number of evaluations. Additionally, the new proposed method is applied to the optimal design of a cycloid gear pump and achieves desirable results.     

Theory of convex cones in multicriteria decision making

We develop the theory of convex polyhedral cones in the objective-function space of a multicriteria decision problem. The convex cones are obtained from the decision-maker's pairwise judgments of decision alternatives and are applicable to any quasiconcave utility function. Therefore, the cones can be used in any progressively articulated solution procedure that employs pairwise comparisons. The cones represent convex sets of solutions that are inferior to known solutions to a multicriteria problem. Therefore, these convex sets can be eliminated from consideration while solving the problem. We develop the underlying theory and a framework for representing knowledge about the decision-maker's preference structure using convex cones. This framework can be adopted in the interactive solution of any multicriteria problem after taking into account the characteristics of the problem and the solution procedure. Our computational experience with different multicriteria problems shows that this approach is both viable and efficient in solving practical problems of moderate size.     

Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm

In this paper, we develop a novel stochastic multi-objective multi-mode transportation model for hub covering location problem under uncertainty. The transportation time between each pair of nodes is an uncertain parameter and also is influenced by a risk factor in the network. We extend the traditional comprehensive hub location problem by considering two new objective functions. So, our multi-objective model includes (i) minimization of total current investment costs and (ii) minimization of maximum transportation time between each origin–destination pair in the network. Besides, a novel multi-objective imperialist competitive algorithm (MOICA) is proposed to obtain the Pareto-optimal solutions of the problem. The performance of the proposed solution algorithm is compared with two well-known meta-heuristics, namely, non-dominated sorting genetic algorithm (NSGA-II) and Pareto archive evolution strategy (PAES). Computational results show that MOICA outperforms the other meta-heuristics.     

A posterior preference articulation approach to multiresponse surface optimization

In multiresponse surface optimization (MRSO), responses are often in conflict. To obtain a satisfactory compromise, the preference information of a decision maker (DM) on the tradeoffs among the responses should be incorporated into the problem. In most existing work, the DM expresses a subjective judgment on the responses through a preference parameter before the problem-solving process, after which a single solution is obtained. In this study, we propose a posterior preference articulation approach to MRSO. The approach initially finds a set of nondominated solutions without the DM’s preference information, and then allows the DM to select the best solution from among the nondominated solutions. An interactive selection method based on pairwise comparisons made by the DM is adopted in our method to facilitate the DM’s selection process. The proposed method does not require that the preference information be specified in advance. It is easy and effective in that a satisfactory compromise can be obtained through a series of pairwise comparisons, regardless of the type of the DM’s utility function.     

A visual interactive approach for scenario-based stochastic multi-objective problems and an application

In many practical applications of stochastic programming, discretization of continuous random variables in the form of a scenario tree is required. In this paper, we deal with the randomness in scenario generation and present a visual interactive method for scenario-based stochastic multi-objective problems. The method relies on multi-variate statistical analysis of solutions obtained from a multi-objective stochastic problem to construct joint confidence regions for the objective function values. The decision maker (DM) explores desirable parts of the efficient frontier using a visual representation that depicts the trajectories of the objective function values within confidence bands. In this way, we communicate the effects of randomness inherent in the problem to the DM to help her understand the trade-offs and the levels of risk associated with each objective.     

主通道位置不固定的设施布局问题多目标优化模型及算法

以物流中心设施布局问题为对象,提出了考虑出入口及主通道位置不固定情况下的设施布局问题的多目标优化模型并设计了其改进的遗传算法。首先,以物料搬运成本最小、活动关系密切度最大和面积利用率最大为目标,构建了考虑出入口位置不固定条件下的具有I型主通道的设施布局多目标优化数学模型。然后,设计了一种改进的遗传算法,包括:改进的编码、解码方法,追加了解码修正操作,基于惩罚函数策略的适应度函数等。实例测试表明,本算法的执行效率高而且结果稳定,优化效果好,布局结果紧凑适用。     

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

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

An interior multiobjective primal-dual linear programming algorithm using approximated gradients and sequential generation of anchor points

An algorithm for addressing multiple objective linear programming (MOLP) problems is presented. The algorithm modifies the path-following primal-dual algorithm to MOLP problems by using the single objective algorithm to generate interior search directions and later combine them to derive a single direction along which to step to the next iterate. Combining the different interior search directions is done by interacting with a Decision Maker (DM) to obtain locally-relevant preference information for the value vectors along these directions. This preference information is then used to derive an approximation to the gradient of an implicity-known utility function, and using a projection of this gradient provides a direction gradient of an implicitly-known utility function, and using a projection of this gradient provides a direction vector along which we step to the next iterate. At each iteration the algorithm also generates boundary points that aid in deriving the combined search direction. We refer to these boundary points, generated sequentially during the process, as anchor points that serve as candidate solutions at which to terminate the iterative process.     

多目标应急物流中心选址的鲁棒优化模型

针对重大突发事件的应急物资救援,研究了应急物流中心的选址及应急物资的调运问题。利用离散的情景集合描述受灾点应急物资需求的不确定性以及应急物资运输成本和运输时间的不确定性,同时考虑应急救援成本和应急救援时间两个目标,建立了多目标应急物流中心选址的确定型模型和鲁棒优化模型。为将多目标问题转化为单目标问题,利用成本单目标和时间单目标的最优结果将多目标转化为相对值再加权处理,该方法既可消除多个目标之间的单位及数量级差异,还可以根据问题的数据变化进行动态调整。以提供应急物资救援服务的设施作为编码,设计了一种通用的混合蛙跳算法。为检验模型和算法的有效性,设计了一个多情景的算例,结果表明两个模型和算法具备良好的可行性和有效性,且鲁棒优化模型能较好地保持对各种不确定性的抗干扰能力;最后,讨论分析了成本偏好权重和鲁棒约束系数的影响,结果表明可根据成本偏好权重的取值范围来区分各种应急救援阶段,体现不同救援阶段的救援要求及特征,并给出了成本偏好权重和鲁棒约束系数的取值建议。     

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.