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.     

Swarm approach based on gravity for optimizing energy savings in grid systems

Execution time optimization is one of the most important objectives to accomplish for experiments launched on grid environments. However, the computing community is becoming more conscious about energy savings, seeking their optimization. In this work, both execution time and energy consumption are optimized through two swarm and multi-objective algorithms based on both physics and biology fields. On the one hand, multi-objective gravitational search algorithm (MOGSA) is inspired by the gravity forces between the planet masses. On the other hand, Multi-Objective Firefly Algorithm is based on the light attraction between the fireflies. These swarm algorithms are compared with the standard multi-objective algorithm non-dominated sorting genetic algorithm II to study their efficiency as multi-objective algorithms. Moreover, the best algorithm proposed, MOGSA, is compared with MOHEFT (a multi-objective version of one of the most-used algorithms in workflow scheduling, HEFT), and also with two real grid schedulers: Workload Management System and deadline budget constraint. Results show the superior performance of MOGSA regarding the others.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

New simulation-based frameworks for multi-objective reliability-based design optimization of structures

In the present study, two new simulation-based frameworks are proposed for multi-objective reliability-based design optimization (MORBDO). The first is based on hybrid non-dominated sorting weighted simulation method (NSWSM) in conjunction with iterative local searches that is efficient for continuous MORBDO problems. According to NSWSM, uniform samples are generated within the design space and, then, the set of feasible samples are separated. Thereafter, the non-dominated sorting operator is employed to extract the approximated Pareto front. The iterative local sample generation is then performed in order to enhance the accuracy, diversity, and increase the extent of non-dominated solutions. In the second framework, a pseudo-double loop algorithm is presented based on hybrid weighted simulation method (WSM) and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) that is efficient for problems including both discrete and continuous variables. According to hybrid WSM-NSGA-II, proper non-dominated solutions are produced in each generation of NSGA-II and, subsequently, WSM evaluates the reliability level of each candidate solution until the algorithm converges to the true Pareto solutions. The valuable characteristic of presented approaches is that only one simulation run is required for WSM during entire optimization process, even if solutions for different levels of reliability be desired. Illustrative examples indicate that NSWSM with the proposed local search strategy is more efficient for small dimension continuous problems. However, WSM-NSGA-II outperforms NSWSM in terms of solutions quality and computational efficiency, specifically for discrete MORBDOs. Employing global optimizer in WSM-NSGA-II provided more accurate results with lower samples than NSWSM.     

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.     

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.     

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.     

ParEGO extensions for multi-objective optimization of expensive evaluation functions

This paper deals with multi-objective optimization in the case of expensive objective functions. Such a problem arises frequently in engineering applications where the main purpose is to find a set of optimal solutions in a limited global processing time. Several algorithms use linearly combined criteria to use directly mono-objective algorithms. Nevertheless, other algorithms, such as multi-objective evolutionary algorithm (MOEA) and model-based algorithms, propose a strategy based on Pareto dominance to optimize efficiently all criteria. A widely used model-based algorithm for multi-objective optimization is Pareto efficient global optimization (ParEGO). It combines linearly the objective functions with several random weights and maximizes the expected improvement (EI) criterion. However, this algorithm tends to favor parameter values suitable for the reduction of the surrogate model error, rather than finding non-dominated solutions. The contribution of this article is to propose an extension of the ParEGO algorithm for finding the Pareto Front by introducing a double Kriging strategy. Such an innovation allows to calculate a modified EI criterion that jointly accounts for the objective function approximation error and the probability to find Pareto Set solutions. The main feature of the resulting algorithm is to enhance the convergence speed and thus to reduce the total number of function evaluations. This new algorithm is compared against ParEGO and several MOEA algorithms on a standard benchmark problems. Finally, an automotive engineering problem allowing to illustrate the applicability of the proposed approach is given as an example of a real application: the parameter setting of an indirect tire pressure monitoring system.     

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.     

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.     

随机混流U型拆卸线平衡排序问题多目标进化算法优化

针对混流U型拆卸线平衡排序问题,考虑拆卸时间不确定,建立了该问题最小拆卸线平均闲置率、尽早拆卸危害和高需求零部件、最小化平均方向改变次数的多目标优化模型,并提出一种基于分解和动态邻域搜索的混合多目标进化算法(Hybrid Multi-objective Evolutionary Algorithm Based on Decomposition, HMOEA/D)。该算法通过采用弹性任务分配策略、动态邻域结构和动态调整权重以保证解的可行性并搜索得到分布较好的非劣解集。最后,仿真求解实验设计技术(DOE)生成的测试算例,结果表明HMOEA/D较其它算法能得到更接近Pareto最优、分布更好的近似解集。     

Multi-objective open shop scheduling by considering human error and preventive maintenance

This study presents an open shop scheduling model by considering human error and preventive maintenance. The proposed mathematical model takes into account conflicting objective functions including makespan, human error and machine availability. In order to find the optimum scheduling, human error, maintenance and production factors are considered, simultaneously. Human error is measured by Human Error Assessment and Reduction Technique (HEART). Three metaheuristic methods including non-dominated sorting genetic algorithm-II (NSGA-II), multi-objective particle swarm optimization (MOPSO) and strength Pareto evolutionary algorithm II (SPEA-II) are developed to find near-optimal solution. The Taguchi method is applied by adjusting parameters of metaheuristic algorithms. Several illustrative examples and a real case study (auto spare parts manufacturer) are applied to show the applicability of the multi-objective mixed integer nonlinear programming model. The proposed approach of this study may be used for similar open shop problems with minor modifications.     

Convex hull-based multi-objective evolutionary computation for maximizing receiver operating characteristics performance

The receiver operating characteristics (ROC) analysis has gained increasing popularity for analyzing the performance of classifiers. In particular, maximizing the convex hull of a set of classifiers in the ROC space, namely ROCCH maximization, is becoming an increasingly important problem. In this work, a new convex hull-based evolutionary multi-objective algorithm named ETriCM is proposed for evolving neural networks with respect to ROCCH maximization. Specially, convex hull-based sorting with convex hull of individual minima (CH-CHIM-sorting) and extreme area extraction selection (EAE-selection) are proposed as a novel selection operator. Empirical studies on 7 high-dimensional and imbalanced datasets show that ETriCM outperforms various state-of-the-art algorithms including convex hull-based evolutionary multi-objective algorithm (CH-EMOA) and non-dominated sorting genetic algorithm II (NSGA-II).     

Subset simulation for multi-objective optimization

Subset simulation is an efficient Monte Carlo technique originally developed for structural reliability problems, and further modified to solve single-objective optimization problems based on the idea that an extreme event (optimization problem) can be considered as a rare event (reliability problem). In this paper subset simulation is extended to solve multi-objective optimization problems by taking advantages of Markov Chain Monte Carlo and a simple evolutionary strategy. In the optimization process, a non-dominated sorting algorithm is introduced to judge the priority of each sample and handle the constraints. To improve the diversification of samples, a reordering strategy is proposed. A Pareto set can be generated after limited iterations by combining the two sorting algorithms together. Eight numerical multi-objective optimization benchmark problems are solved to demonstrate the efficiency and robustness of the proposed algorithm. A parametric study on the sample size in a simulation level and the proportion of seed samples is performed to investigate the performance of the proposed algorithm. Comparisons are made with three existing algorithms. Finally, the proposed algorithm is applied to the conceptual design optimization of a civil jet.     

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

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

Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighbourhoods

This paper presents the investigation of an evolutionary multi-objective simulated annealing (EMOSA) algorithm with variable neighbourhoods to solve the multi-objective multicast routing problems in telecommunications. The hybrid algorithm aims to carry out a more flexible and adaptive exploration in the complex search space by using features of the variable neighbourhood search to find more non-dominated solutions in the Pareto front. Different neighbourhood strictures have been designed with regard to the set of objectives, aiming to drive the search towards optimising all objectives simultaneously. A large number of simulations have been carried out on benchmark instances and random networks with real world features including cost, delay and link utilisations. Experimental results demonstrate that the proposed EMOSA algorithm with variable neighbourhoods is able to find high-quality non-dominated solutions for the problems tested. In particular, the neighbourhood structures that are specifically designed for each objective significantly improved the performance of the proposed algorithm compared with variants of the algorithm with a single neighbourhood.     

Pruned Pareto-optimal sets for the system redundancy allocation problem based on multiple prioritized objectives

In this paper, a new methodology is presented to solve different versions of multi-objective system redundancy allocation problems with prioritized objectives. Multi-objective problems are often solved by modifying them into equivalent single objective problems using pre-defined weights or utility functions. Then, a multi-objective problem is solved similar to a single objective problem returning a single solution. These methods can be problematic because assigning appropriate numerical values (i.e., weights) to an objective function can be challenging for many practitioners. On the other hand, methods such as genetic algorithms and tabu search often yield numerous non-dominated Pareto optimal solutions, which makes the selection of one single best solution very difficult. In this research, a tabu search meta-heuristic approach is used to initially find the entire Pareto-optimal front, and then, Monte-Carlo simulation provides a decision maker with a pruned and prioritized set of Pareto-optimal solutions based on user-defined objective function preferences. The purpose of this study is to create a bridge between Pareto optimality and single solution approaches.     

DMEA: a direction-based multiobjective evolutionary algorithm

A novel direction-based multi-objective evolutionary algorithm (DMEA) is proposed, in which a population evolves over time along some directions of improvement. We distinguish two types of direction: (1) the convergence direction between a non-dominated solution (stored in an archive) and a dominated solution from the current population; and, (2) the spread direction between two non-dominated solutions in the archive. At each generation, these directions are used to perturb the current parental population from which offspring are produced. The combined population of offspring and archived solutions forms the basis for the creation of both the next-generation archive and parental pools. The rule governing the formation of the next-generation parental pool is as follows: the first half is populated by non-dominated solutions whose spread is aided by a niching criterion applied in the decision space. The second half is filled with both non-dominated and dominated solutions from the sorted remainder of the combined population. The selection of non-dominated solutions for the next-generation archive is also assisted by a mechanism, in which neighborhoods of rays in objective space serve as niches. These rays originate from the current estimate of the Pareto optimal front??s (POF??s) ideal point and emit randomly into the hyperquadrant that contains the current POF estimate. Experiments on two well-known benchmark sets, namely ZDT and DTLZ have been carried out to investigate the performance and the behavior of the DMEA. We validated its performance by comparing it with four well-known existing algorithms. With respect to convergence and spread performance, DMEA turns out to be very competitive.     

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.     

A novel multi-objective memetic algorithm based on opposition-based self-adaptive differential evolution

Under the framework of evolutionary paradigms, many evolutionary algorithms have been designed for handling multi-objective optimization problems. Each of the different algorithms may display exceptionally good performance in certain optimization problems, but none of them can be completely superior over one another. As such, different evolutionary algorithms are being synthesized to complement each other in view of their strengths and the limitations inherent in them. In this study, the novel memetic algorithm known as the Opposition-based Self-adaptive Hybridized Differential Evolution algorithm (OSADE) is being comprehensively investigated through a comparative study with some state-of-the-art algorithms, such as NSGA-II, non-dominated sorting Differential Evolution (NSDE), MOEA/D-SBX, MOEA/D-DE and the Multi-objective Evolutionary Gradient Search (MO-EGS) by using a suite of different benchmark problems. Through the experimental results that are presented by employing the Inverted Generational Distance (IGD) and the Hausdorff Distance performance indicators, it is seen that OSADE is able to achieve competitive, if not better, performance when compared to the other algorithms in this study.