A continuation approach to mode-finding of multivariate Gaussian mixtures and kernel density estimates

This paper presents a novel method of multi-objective optimization by learning automata (MOLA) to solve complex multi-objective optimization problems. MOLA consists of multiple automata which perform sequential search in the solution domain. Each automaton undertakes dimensional search in the selected dimension of the solution domain, and each dimension is divided into a certain number of cells. Each automaton performs a continuous search action, instead of discrete actions, within cells. The merits of MOLA have been demonstrated, in comparison with a multi-objective evolutionary algorithm based on decomposition (MOEA/D) and non-dominated sorting genetic algorithm II (NSGA-II), on eleven multi-objective benchmark functions and an optimal problem in the midwestern American electric power system which is integrated with wind power, respectively. The simulation results have shown that MOLA can obtain more accurate and evenly distributed Pareto fronts, in comparison with MOEA/D and NSGA-II.     

A hybrid multi-objective evolutionary algorithm based on NSGA-II for practical scheduling with release times in steel plants

The hot metal is produced from the blast furnaces in the iron plant and should be processed as soon as possible in the subsequent steel plant for energy saving. Therefore, the release times of hot metal have an influence on the scheduling of a steel plant. In this paper, the scheduling problem with release times for steel plants is studied. The production objectives and constraints related to the release times are clarified, and a new multi-objective scheduling model is built. For the solving of the multi-objective optimization, a hybrid multi-objective evolutionary algorithm based on non-dominated sorting genetic algorithm-II (NSGA-II) is proposed. In the hybrid multi-objective algorithm, an efficient decoding heuristic (DH) and a non-dominated solution construction method (NSCM) are proposed based on the problem-specific characteristics. During the evolutionary process, individuals with different solutions may have a same chromosome because the NSCM constructs non-dominated solutions just based on the solution found by DH. Therefore, three operations in the original NSGA-II process are modified to avoid identical chromosomes in the evolutionary operations. Computational tests show that the proposed hybrid algorithm based on NSGA-II is feasible and effective for the multi-objective scheduling with release times.     

Robustness analysis in Multi-Objective Mathematical Programming using Monte Carlo simulation

In most multi-objective optimization problems we aim at selecting the most preferred among the generated Pareto optimal solutions (a subjective selection among objectively determined solutions). In this paper we consider the robustness of the selected Pareto optimal solution in relation to perturbations within weights of the objective functions. For this task we design an integrated approach that can be used in multi-objective discrete and continuous problems using a combination of Monte Carlo simulation and optimization. In the proposed method we introduce measures of robustness for Pareto optimal solutions. In this way we can compare them according to their robustness, introducing one more characteristic for the Pareto optimal solution quality. In addition, especially in multi-objective discrete problems, we can detect the most robust Pareto optimal solution among neighboring ones. A computational experiment is designed in order to illustrate the method and its advantages. It is noteworthy that the Augmented Weighted Tchebycheff proved to be much more reliable than the conventional weighted sum method in discrete problems, due to the existence of unsupported Pareto optimal solutions.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

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.     

Synchronous and asynchronous Pareto-based multi-objective Artificial Bee Colony algorithms

Pareto-based multi-objective optimization algorithms prefer non-dominated solutions over dominated solutions and maintain as much as possible diversity in the Pareto optimal set to represent the whole Pareto-front. This paper proposes three multi-objective Artificial Bee Colony (ABC) algorithms based on synchronous and asynchronous models using Pareto-dominance and non-dominated sorting: asynchronous multi-objective ABC using only Pareto-dominance rule (A-MOABC/PD), asynchronous multi-objective ABC using non-dominated sorting procedure (A-MOABC/NS) and synchronous multi-objective ABC using non-dominated sorting procedure (S-MOABC/NS). These algorithms were investigated in terms of the inverted generational distance, hypervolume and spread performance metrics, running time, approximation to whole Pareto-front and Pareto-solutions spaces. It was shown that S-MOABC/NS is more scalable and efficient compared to its asynchronous counterpart and more efficient and robust than A-MOABC/PD. An investigation on parameter sensitivity of S-MOABC/NS was presented to relate the behavior of the algorithm to the values of the control parameters. The results of S-MOABC/NS were compared to some state-of-the art algorithms. Results show that S-MOABC/NS can provide good approximations to well distributed and high quality non-dominated fronts and can be used as a promising alternative tool to solve multi-objective problems with the advantage of being simple and employing a few control parameters.     

Goal programming using multiple objective hybrid metaheuristic algorithm

In this paper, a Goal Programming (GP) model is converted into a multi-objective optimization problem (MOO) of minimizing deviations from fixed goals. To solve the resulting MOO problem, a hybrid metaheuristic with two steps is proposed to find the Pareto set's solutions. First, a Record-to-Record Travel with an adaptive memory is used to find first non-dominated Pareto frontier solutions preemptively. Second, a Variable Neighbour Search technique with three transformation types is used to intensify every non dominated solution found in the first Pareto frontier to produce the final Pareto frontier solutions. The efficiency of the proposed approach is demonstrated by solving two nonlinear GP test problems and three engineering design problems. In all problems, multiple solutions to the GP problem are found in one single simulation run. The results prove that the proposed algorithm is robust, fast and simply structured, and manages to find high-quality solutions in short computational times by efficiently alternating search diversification and intensification using very few user-defined parameters.     

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

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

A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA), for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. FastPGA utilizes a new ranking strategy that utilizes more information about Pareto dominance among solutions and niching relations. New genetic operators are employed to enhance the proposed algorithm’s performance in terms of convergence behavior and computational effort as rapid convergence is of utmost concern and highly desired when solving expensive multiobjective optimization problems (MOPs). Computational results for a number of test problems indicate that FastPGA is a promising approach. FastPGA yields similar performance to that of the improved nondominated sorting genetic algorithm (NSGA-II), a widely-accepted benchmark in the MOEA research community. However, FastPGA outperforms NSGA-II when only a small number of solution evaluations are permitted, as would be the case when solving expensive MOPs.     

Non-dominated sorting procedure for Pareto dominance ranking on multicore CPU and/or GPU

Evolutionary multi-objective optimization algorithms aim at finding an approximation of the Pareto set. For hard to solve problems with many conflicting objectives, the number of functions evaluations to represent the Pareto front can be large and time consuming. Parallel computing can reduce the wall-clock time of such algorithms. Previous studies tackled the parallelization of a particular evolutionary algorithm. In this research, we focus on improving one of the most time consuming procedures—the non-dominated sorting—, which is used in the state-of-the-art multi-objective genetic algorithms. Here, three parallel versions of the non-dominated sorting procedure are developed: (1) a multicore (based on Pthreads); (2) a Graphic Processing Unit (GPU) (based on CUDA interface); and (3) a hybrid (based on Pthreads and CUDA). The user can select the most suitable option to efficiently compute the non-dominated sorting procedure depending on the available hardware. Results show that the use of GPU computing provides a substantial improvement in terms of performance. The hybrid approach has the best performance when a good load balance is established among cores and GPU.     

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.     

基于混沌集群智能优化算法的多目标粗糙集属性约减

针对管理实践及大数据处理过程中具有多决策属性的粗糙集属性约减问题,将条件属性依赖度与知识分辨度进行结合构建属性权重,分别建立针对不同决策属性的约减目标函数,引入帕累托最优思想,将基于多决策属性的粗糙集属性约减问题转化为离散多目标优化问题。针对该问题的结构设计了具有集群智能优化思想的元胞自动机求解算法,在算法中引入基于个体的非支配解集平衡局部最优与全局最优的关系,引入混沌遗传算子增加种群多样性。以某铁路局设备安全风险处理数据为案例构建多决策属性粗糙集决策表进行优化计算并进行管理决策分析。研究发现:(1)相对于传统的NSGA-II与MO-cell算法,本文提出的算法具有更强的多目标属性挖掘性能;(2)帕累托最优思想可以较好地解释多决策属性粗糙集在管理实践中的意义。     

A mapping technique for better solution exploration: NSGA-II adaptation

A mapping method (MaM) for a better solution space exploration adapted to NSGA-II method is presented. The Mapping technique divides the solution space into several zones using a Hamming distance to a reference solution. We present a bijective mapping function from the search space to the binary representation space of solutions. For each zone, a mapping metric is used to evaluate the solution space exploration. According to this evaluation, a local search is performed. The mapping is adapted to the well known non-dominated sorting genetic algorithm-II (NSGA-II) method applied to solve the flexible job shop problem (FJSP) case. We present the comparison between the hybridization using the local search for the non-dominated solutions and the hybridization using the mapping metrics. The multi-objective metrics show the efficiency of mapping adaptation in terms of convergence and diversity.     

Transfer weight functions for injecting problem information in the multi-objective CMA-ES

The covariance matrix adaptation evolution strategy (CMA-ES) is one of the state-of-the-art evolutionary algorithms for optimization problems with continuous representation. It has been extensively applied to single-objective optimization problems, and different variants of CMA-ES have also been proposed for multi-objective optimization problems (MOPs). When applied to MOPs, the traditional steps of CMA-ES have to be modified to accommodate for multiple objectives. This fact is particularly evident when the number of objectives is higher than 3 and, with a high probability, all the solutions produced become non-dominated. An open question is to what extent information about the objective values of the non-dominated solutions can be injected in the CMA-ES model for a more effective search. In this paper, we investigate this general question using several metrics that describe the quality of the solutions already evaluated, different transfer weight functions, and a set of difficult benchmark instances including many-objective problems. We introduce a number of new strategies that modify how the probabilistic model is learned in CMA-ES. By conducting an exhaustive empirical analysis on two difficult benchmarks of many-objective functions we show that the proposed strategies to infuse information about the quality indicators into the learned models can achieve consistent improvements in the quality of the Pareto fronts obtained and enhance the convergence rate of the algorithm. Moreover, we conducted a comparison with a state-of-the-art algorithm from the literature, and achieved competitive results in problems with irregular Pareto fronts.     

Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies

Pareto local search (PLS) methods are local search algorithms for multi-objective combinatorial optimization problems based on the Pareto dominance criterion. PLS explores the Pareto neighbourhood of a set of non-dominated solutions until it reaches a local optimal Pareto front. In this paper, we discuss and analyse three different Pareto neighbourhood exploration strategies: best, first, and neutral improvement. Furthermore, we introduce a deactivation mechanism that restarts PLS from an archive of solutions rather than from a single solution in order to avoid the exploration of already explored regions. To escape from a local optimal solution set we apply stochastic perturbation strategies, leading to stochastic Pareto local search algorithms (SPLS). We consider two perturbation strategies: mutation and path-guided mutation. While the former is unbiased, the latter is biased towards preserving common substructures between 2 solutions. We apply SPLS on a set of large, correlated bi-objective quadratic assignment problems (bQAPs) and observe that SPLS significantly outperforms multi-start PLS. We investigate the reason of this performance gain by studying the fitness landscape structure of the bQAPs using random walks. The best performing method uses the stochastic perturbation algorithms, the first improvement Pareto neigborhood exploration and the deactivation technique.     

Focused ultrasonic therapy planning: Metamodeling,optimization, visualization

We present a generic approach for focused ultrasonic therapy planning on the basis of numerical simulation, multi-objective optimization, stochastic analysis and visualization in virtual environments. A realistic test case is used to demonstrate the approach. RBF metamodeling of simulation results is performed for continuous representation of two optimization objectives. The non-convex Pareto front of the objectives is determined by means of non-dominated set and local improvement algorithms. Uncertainties of metamodeling are estimated by means of a cross-validation procedure. The 3D visualization in virtual environment framework Avango allows detailed inspection of MRT images, the corresponding material model and spatial distribution of the resulting thermal dose.     

考虑客户满意度的计划外来船靠泊调度模型及算法

为解决船舶临时请求靠港而调整调度的特殊需求,建立了以客户满意度最大和额外作业成本最小为目标的双目标优化模型,利用改进模拟植物生长算法予以求解,求解中采取确定-随机策略确定初始生长点,以固定步长和变步长混合方式构建邻域,并融入分层非支配排序方法。确定兼顾船公司和港口方利益的调度方案时,利用Pareto前沿分布特点,对船公司和港口方的偏向度进行量化,选择偏向度差值最小的方案。最后,以我国某集装箱码头为例,验证了本文模型和算法的可行性。计算结果与NSGA-II算法进行对比,证明了文中改进模拟植物生长算法的有效性。本文成果可以为提高港口管理效率提供技术支持。     

A new multi-objective discrete robust optimization algorithm for engineering design

This paper proposes a novel multi-objective discrete robust optimization (MODRO) algorithm for design of engineering structures involving uncertainties. In the present MODRO procedure, grey relational analysis (GRA), coupled with principal component analysis (PCA), was used as a multicriteria decision making model for converting multiple conflicting objectives into one unified cost function. The optimization process was iterated using the successive Taguchi approach to avoid the limitation that the conventional Taguchi method fails to deal with a large number of design variables and design levels. The proposed method was first verified by a mathematical benchmark example and a ten-bar truss design problem; and then it was applied to a more sophisticated design case of full scale vehicle structure for crashworthiness criteria. The results showed that the algorithm is able to achieve an optimal design in a fairly efficient manner attributable to its integration with the multicriteria decision making model. Note that the optimal design can be directly used in practical applications without further design selection. In addition, it was found that the optimum is close to the corresponding Pareto frontier generated from the other approaches, such as the non-dominated sorting genetic algorithm II (NSGA-II), but can be more robust as a result of introduction of the Taguchi method. Due to its independence on metamodeling techniques, the proposed algorithm could be fairly promising for engineering design problems of high dimensionality.     

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 hybrid quantum-inspired immune algorithm for multiobjective optimization

This study suggests a novel quantum immune algorithm for finding Pareto-optimal solutions to multiobjective optimization problems based on quantum computing and immune system. In the proposed algorithm, there are distinct characteristics as follows. First, the encoding method is based on Q-bit representation, and thus a chaos-based approach is suggested to initialize the population. Second, a new chaos-based rotation gate and Q-gates are presented to perform mutation and improve the quality of the population, respectively. Finally, especially, a new truncation algorithm with similar individuals (TASI) is utilized to preserve the diversity of the population. Also, a new selection operator is proposed to create the new population based on TASI. Simulation results on six standard problems (ZDT6, CP, SP, VNT, OSY and KIT) show the proposed algorithm is able to find a much better spread of solutions and has better convergence near the true Pareto-optimal front compared to the vector immune algorithm (VIS) and the elitist non-dominated sorting genetic system (NSGA-II).