A preference-based multi-objective evolutionary algorithm R-NSGA-II with stochastic local search

Incorporation of a decision maker’s preferences into multi-objective evolutionary algorithms has become a relevant trend during the last decade, and several preference-based evolutionary algorithms have been proposed in the literature. Our research is focused on improvement of a well-known preference-based evolutionary algorithm R-NSGA-II by incorporating a local search strategy based on a single agent stochastic approach. The proposed memetic algorithm has been experimentally evaluated by solving a set of well-known multi-objective optimization benchmark problems. It has been experimentally shown that incorporation of the local search strategy has a positive impact to the quality of the algorithm in the sense of the precision and distribution evenness of approximation.     

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.     

A multi-objective memetic algorithm based on decomposition for big optimization problems

When solving multi-objective optimization problems (MOPs) with big data, traditional multi-objective evolutionary algorithms (MOEAs) meet challenges because they demand high computational costs that cannot satisfy the demands of online data processing involving optimization. The gradient heuristic optimization methods show great potential in solving large scale numerical optimization problems with acceptable computational costs. However, some intrinsic limitations make them unsuitable for searching for the Pareto fronts. It is believed that the combination of these two types of methods can deal with big MOPs with less computational cost. The main contribution of this paper is that a multi-objective memetic algorithm based on decomposition for big optimization problems (MOMA/D-BigOpt) is proposed and a gradient-based local search operator is embedded in MOMA/D-BigOpt. In the experiments, MOMA/D-BigOpt is tested on the multi-objective big optimization problems with thousands of variables. We also combine the local search operator with other widely used MOEAs to verify its effectiveness. The experimental results show that the proposed algorithm outperforms MOEAs without the gradient heuristic local search operator.     

A parallel competitive colonial algorithm for JIT flowshop scheduling

This paper proposes two parallel algorithms which are improved by heuristics for a bi-objective flowshop scheduling problem with sequence-dependent setup times in a just-in-time environment. In the proposed algorithms, the population will be decomposed into the several sub-populations in parallel. Multiple objectives are combined with min–max method then each sub-population evolves separately in order to obtain a good approximation of the Pareto-front. After unifying the obtained results, we propose a variable neighborhood algorithm and a hybrid variable neighborhood search/tabu search algorithm to improve the Pareto-front. The non-dominated sets obtained from our proposed algorithms, a genetic local search and restarted iterated Pareto greedy algorithm are compared. It is found that most of the solutions in the net non-dominated front are yielded by our proposed algorithms.     

An evolutionary artificial immune system for multi-objective optimization

In this paper, an evolutionary artificial immune system for multi-objective optimization which combines the global search ability of evolutionary algorithms and immune learning of artificial immune systems is proposed. A new selection strategy is developed based upon the concept of clonal selection principle to maintain the balance between exploration and exploitation. In order to maintain a diverse repertoire of antibodies, an information-theoretic based density preservation mechanism is also presented. In addition, the performances of various multi-objective evolutionary algorithms as well as the effectiveness of the proposed features are examined based upon seven benchmark problems characterized by different difficulties in local optimality, non-uniformity, discontinuity, non-convexity, high-dimensionality and constraints. The comparative study shows the effectiveness of the proposed algorithm, which produces solution sets that are highly competitive in terms of convergence, diversity and distribution. Investigations also demonstrate the contribution and robustness of the proposed features.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. 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 optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

A new orthogonal evolutionary algorithm based on decomposition for multi-objective optimization

The diversity of solutions is very important for multi-objective evolutionary algorithms to deal with multi-objective optimization problems (MOPs). In order to achieve the goal, a new orthogonal evolutionary algorithm based on objective space decomposition (OEA/D) is proposed in this paper. To be specific, the objective space of an MOP is firstly decomposed into a set of sub-regions via a set of direction vectors, and OEA/D maintains the diversity of solutions by making each sub-region have a solution to the maximum extent. Also, the quantization orthogonal crossover (QOX) is used to enhance the search ability of OEA/D. Experimental studies have been conducted to compare this proposed algorithm with classic MOEA/D, NSGAII, NICA and D2MOPSO. Simulation results on six multi-objective benchmark functions show that the proposed algorithm is able to obtain better diversity and more evenly distributed Pareto fronts than other four algorithms.     

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.     

Scale factor local search in differential evolution

This paper proposes the scale factor local search differential evolution (SFLSDE). The SFLSDE is a differential evolution (DE) based memetic algorithm which employs, within a self-adaptive scheme, two local search algorithms. These local search algorithms aim at detecting a value of the scale factor corresponding to an offspring with a high performance, while the generation is executed. The local search algorithms thus assist in the global search and generate offspring with high performance which are subsequently supposed to promote the generation of enhanced solutions within the evolutionary framework. Despite its simplicity, the proposed algorithm seems to have very good performance on various test problems. Numerical results are shown in order to justify the use of a double local search instead of a single search. In addition, the SFLSDE has been compared with a standard DE and three other modern DE based metaheuristic for a large and varied set of test problems. Numerical results are given for relatively low and high dimensional cases. A statistical analysis of the optimization results has been included in order to compare the results in terms of final solution detected and convergence speed. The efficiency of the proposed algorithm seems to be very high especially for large scale problems and complex fitness landscapes.     

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

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

Particle swarm with equilibrium strategy of selection for multi-objective optimization

A new ranking scheme based on equilibrium strategy of selection is proposed for multi-objective particle swarm optimization (MOPSO), and the preference ordering is used to identify the “best compromise” in the ranking stage. This scheme increases the selective pressure, especially when the number of objectives is very large. The proposed algorithm has been compared with other multi-objective evolutionary algorithms (MOEAs). The experimental results indicate that our algorithm produces better convergence performance.     

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.     

Hybridizing local search algorithms for global optimization

In this paper, we combine two types of local search algorithms for global optimization of continuous functions. In the literature, most of the hybrid algorithms are produced by combination of a global optimization algorithm with a local search algorithm and the local search is used to improve the solution quality, not to explore the search space to find independently the global optimum. The focus of this research is on some simple and efficient hybrid algorithms by combining the Nelder–Mead simplex (NM) variants and the bidirectional random optimization (BRO) methods for optimization of continuous functions. The NM explores the whole search space to find some promising areas and then the BRO local search is entered to exploit optimal solution as accurately as possible. Also a new strategy for shrinkage stage borrowed from differential evolution (DE) is incorporated in the NM variants. To examine the efficiency of proposed algorithms, those are evaluated by 25 benchmark functions designed for the special session on real-parameter optimization of CEC2005. A comparison study between the hybrid algorithms and some DE algorithms and non-parametric analysis of obtained results demonstrate that the proposed algorithms outperform most of other algorithms and their difference in most cases is statistically considerable. In a later part of the comparative experiments, a comparison of the proposed algorithms with some other evolutionary algorithms reported in the CEC2005 confirms a better performance of our proposed algorithms.     

Handling equality constraints in evolutionary optimization

Over the last few decades several methods have been proposed for handling functional constraints while solving optimization problems using evolutionary algorithms (EAs). However, the presence of equality constraints makes the feasible space very small compared to the entire search space. As a consequence, the handling of equality constraints has long been a difficult issue for evolutionary optimization methods. This paper presents a Hybrid Evolutionary Algorithm (HEA) for solving optimization problems with both equality and inequality constraints. In HEA, we propose a new local search technique with special emphasis on equality constraints. The basic concept of the new technique is to reach a point on the equality constraint from the current position of an individual solution, and then explore on the constraint landscape. We believe this new concept will influence the future research direction for constrained optimization using population based algorithms. The proposed algorithm is tested on a set of standard benchmark problems. The results show that the proposed technique works very well on those benchmark problems.     

On a high-dimensional objective genetic algorithm and its nonlinear dynamic properties

The revival of multi-objective optimization is mainly resulted from the recent development of multi-objective evolutionary optimization that allows the generation of the overall Pareto front. This paper presents an algorithm called HOGA (High-dimensional Objective Genetic Algorithm) for high-dimensional objective optimization on the basis of evolutionary computing. It adopts the principle of Shannon entropy to calculate the weight for each object since the well-known multi-objective evolutionary algorithms work poorly on the high-dimensional optimization problem. To further discuss the nonlinear dynamic property of HOGA, a martingale analysis approach is then employed; some mathematical derivations of the convergent theorems are obtained. The obtained results indicate that this new algorithm is indeed capable of achieving convergence and the suggested martingale analysis approach provides a new methodology for nonlinear dynamic analysis of evolutionary algorithms.     

Local models—an approach to distributed multi-objective optimization

When solving real-world optimization problems, evolutionary algorithms often require a large number of fitness evaluations in order to converge to the global optima. Attempts have been made to find techniques to reduce the number of fitness function evaluations. We propose a novel framework in the context of multi-objective optimization where fitness evaluations are distributed by creating a limited number of adaptive spheres spanning the search space. These spheres move towards the global Pareto front as components of a swarm optimization system. We call this process localization. The contribution of the paper is a general framework for distributed evolutionary multi-objective optimization, in which the individuals in each sphere can be controlled by any existing evolutionary multi-objective optimization algorithm in the literature.     

Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization

Although recent studies have shown that evolutionary algorithms are effective tools for solving multi-objective optimization problems, their performances are often bottlenecked by the suitability of the evolutionary operators with respect to the optimization problem at hand and their corresponding parametric settings. To adapt the search dynamic of evolutionary operation in multi-objective optimization, this paper proposes an adaptive variation operator that exploits the chromosomal structure of binary representation and synergizes the function of crossover and mutation. The overall search ability is deterministically tuned online to maintain a balance between extensive exploration and local fine-tuning at different stages of the evolutionary search. Also, the coordination between the two variation operators is achieved by means of an adaptive control that ensures an efficient exchange of information between the different chromosomal sub-structures throughout the evolutionary search. Extensive comparative studies with several representative variation operators are performed on different benchmark problems and significant algorithmic performance improvements in terms of proximity, uniformity and diversity are obtained with the incorporation of the proposed adaptive variation operator into the evolutionary multi-objective optimization process.     

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.     

Differential evolution framework for big data optimization

During the last two decades, dealing with big data problems has become a major issue for many industries. Although, in recent years, differential evolution has been successful in solving many complex optimization problems, there has been research gaps on using it to solve big data problems. As a real-time big data problem may not be known in advance, determining the appropriate differential evolution operators and parameters to use is a combinatorial optimization problem. Therefore, in this paper, a general differential evolution framework is proposed, in which the most suitable differential evolution algorithm for a problem on hand is adaptively configured. A local search is also employed to increase the exploitation capability of the proposed algorithm. The algorithm is tested on the 2015 big data optimization competition problems (six single objective problems and six multi-objective problems). The results show the superiority of the proposed algorithm to several state-of-the-art algorithms.