Improving the performance and scalability of Differential Evolution on problems exhibiting parameter interactions

Differential Evolution (DE) is a powerful optimization procedure that self-adapts to the search space, although DE lacks diversity and sufficient bias in the mutation step to make efficient progress on non-separable problems. We present an enhancement to DE that introduces greater diversity while also directing the search to more promising regions. The Combinatorial Sampling Differential Evolution (CSDE) is introduced which can sample vectors in two ways; highly correlated with the search space or around a ‘better’ individual. The CSDE approach can provide a similar number of samples as crossover, without being biased towards the principle coordinate axes of a decision space. This approach to sampling vectors is capable of optimizing problems with extensive parameter interactions. It also demonstrates fast convergence towards the global optimum and is highly scalable in the decision space on a variety of single and multi-objective problems due to the balance between sampling highly directed correlated vectors and non-correlated vectors which contribute to sampling diversity.     

Game model-based co-evolutionary algorithm with non-dominated memory and Euclidean distance selection mechanisms for multi-objective optimization

Many real-world problems involve simultaneous optimization of several incommensurable and often competing objectives. In the search for solutions to multi-objective optimization problems (MOPs), we find that there is no single optimum but rather a set of optimums known as the “Pareto optimal set”. Co-evolutionary algorithms are well suited to optimization problems which involve several often competing objectives. Co-evolutionary algorithms are aimed at evolving individuals through individuals competing in an objective space. In order to approximate the ideal Pareto optimal set, the search capability of diverse individuals in an objective space can be used to determine the performance of evolutionary algorithms. Non-dominated memory and Euclidean distance selection mechanisms for co-evolutionary algorithms have the goal of overcoming the limited search capability of diverse individuals in the population space. In this paper, we propose a method for maintaining population diversity in game model-based co-evolutionary algorithms, and we evaluate the effectiveness of our approach by comparing it with other methods through rigorous experiments on several MOPs.     

Multi-objective genetic local search algorithm using Kohonen’s neural map

Genetic Algorithms (GAs) are population based global search methods that can escape from local optima traps and find the global optima regions. However, near the optimum set their intensification process is often inaccurate. This is because the search strategy of GAs is completely probabilistic. With a random search near the optimum sets, there is a small probability to improve current solution. Another drawback of the GAs is genetic drift. The GAs search process is a black box process and no one knows that which region is being searched by the algorithm and it is possible that GAs search only a small region in the feasible space. On the other hand, GAs usually do not use the existing information about the optimality regions in past iterations.In this paper, a new method called SOM-Based Multi-Objective GA (SBMOGA) is proposed to improve the genetic diversity. In SBMOGA, a grid of neurons use the concept of learning rule of Self-Organizing Map (SOM) supporting by Variable Neighborhood Search (VNS) learn from genetic algorithm improving both local and global search. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm is developed to enhance the local search efficiency in the Evolutionary Algorithms (EAs). The SOM uses a multi-objective learning rule based-on Pareto dominance to train its neurons. The neurons gradually move toward better fitness areas in some trajectories in feasible space. The knowledge of optimum front in past generations is saved in form of trajectories. The final state of the neurons determines a set of new solutions that can be regarded as the probability density distribution function of the high fitness areas in the multi-objective space. The new set of solutions potentially can improve the GAs overall efficiency. In the last section of this paper, the applicability of the proposed algorithm is examined in developing optimal policies for a real world multi-objective multi-reservoir system which is a non-linear, non-convex, multi-objective optimization problem.     

A multi-objective differential evolutionary algorithm for constrained multi-objective optimization problems with low feasible ratio

Most current evolutionary multi-objective optimization (EMO) algorithms perform well on multi-objective optimization problems without constraints, but they encounter difficulties in their ability for constrained multi-objective optimization problems (CMOPs) with low feasible ratio. To tackle this problem, this paper proposes a multi-objective differential evolutionary algorithm named MODE-SaE based on an improved epsilon constraint-handling method. Firstly, MODE-SaE self-adaptively adjusts the epsilon level in line with the maximum and minimum constraint violation values of infeasible individuals. It can prevent epsilon level setting from being unreasonable. Then, the feasible solutions are saved to the external archive and take part in the population evolution by a co-evolution strategy. Finally, MODE-SaE switches the global search and local search by self-switching parameters of search engine to balance the convergence and distribution. With the aim of evaluating the performance of MODE-SaE, a real-world problem with low feasible ratio in decision space and fourteen bench-mark test problems, are used to test MODE-SaE and five other state-of-the-art constrained multi-objective evolution algorithms. The experimental results fully demonstrate the superiority of MODE-SaE on all mentioned test problems, which indicates the effectiveness of the proposed algorithm for CMOPs which have low feasible ratio in search space.     

Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min–max technique

In the literature of multi-objective problem, there are different algorithms to solve different optimization problems. This paper presents a min–max multi-objective procedure for a dual-objective, namely make span, and sum of the earliness and tardiness of jobs in due window machine scheduling problems, simultaneously. In formulation of min–max method when this method is combined with the weighting method, the decision maker can have the flexibility of mixed use of weights and distance parameter to yield a set of Pareto-efficient solutions. This research extends the new hybrid metaheuristic (HMH) to solve parallel machines scheduling problems with sequence-dependent setup time that comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) as an evolutionary algorithm employs certain probability to avoid becoming trapped in a local optimum, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. In addition, two VNS-based HMHs, which are a combination of two methods, SA/VNS and ACO/VNS, are also proposed to solve the addressed scheduling problems. A design of experiments approach is employed to calibrate the parameters. The non-dominated sets obtained from HMH and two best existing bi-criteria scheduling algorithms are compared in terms of various indices and the computational results show that the proposed algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans. Aside, an extensive computational experience is carried out to analyze the different parameters of the algorithm.     

Effective local evolutionary searches distributed on an island model solving bi-objective optimization problems

Using multiple local evolutionary searches, instead of single and overall search, has been an effective technique to solve multi-objective optimization problems (MOPs). With this technique, many parallel and distributed multi-objective evolutionary algorithms (dMOEAs) on different island models have been proposed to search for optimal solutions, efficiently and effectively. These algorithms often use local MOEAs on their islands in which each local search is considered to find a part of optimal solutions. The islands (and the local MOEAs), however, need to communicate to each other to preclude the possibility of converging to local optimal solutions. The existing dMOEAs rely on the central and iterative process of subdividing a large-scale population into multiple subpopulations; and it negatively affects the dMOEAs performance. In this paper, a new version of dMOEA with new local MOEAs and migration strategy is proposed. The respective objective space is first subdivided into the predefined number of polar-based regions assigned to the local MOEAs to be explored and exploited. In addition, the central and iterative process is eliminated using a new proposed migration strategy. The algorithms are tested on the standard bi-objective optimization test cases of ZDTs, and the result shows that these new dMOEAs outperform the existing distributed and parallel MOEAs in most cases.     

基于自变量简约的大规模稀疏多目标优化

现有的大多数进化算法在求解大规模优化问题时性能会随决策变量维数的增长而下降。通常,多目标优化的Pareto有效解集是自变量空间的一个低维流形,该流形的维度远小于自变量空间的维度。鉴于此,提出一种基于自变量简约的多目标进化算法求解大规模稀疏多目标优化问题。该算法通过引入局部保持投影降维,保留原始自变量空间中的局部近邻关系,并设计一个归档集,将寻找到的非劣解存入其中进行训练,以提高投影的准确性。将该算法与四种流行的多目标进化算法在一系列测试问题和实际应用问题上进行了比较。实验结果表明,所提算法在解决稀疏多目标问题上具有较好的效果。因此,通过自变量简约能降低问题的求解难度,提高算法的搜索效率,在解决大规模稀疏多目标问题方面具有显著的优势。     

基于高斯混沌变异和精英学习的自适应多目标粒子群算法

为平衡多目标粒子群的全局和局部搜索能力, 提出一种基于高斯混沌变异和精英学习的自适应多目标粒子群算法. 首先, 提出一种新的种群收敛状态检测方法, 自适应调整惯性权重和学习因子的值, 以达到探索和开发的最佳平衡. 然后, 当检测到种群收敛停滞时, 采用一种带有高斯函数和混沌特性的变异算子协助种群跳出局部最优, 以增强全局搜索能力. 最后, 外部档案中的精英解相互学习, 增强算法的局部搜索能力. 在多目标标准测试问题上的仿真结果表明了所提出算法的有效性.

     

Integrating Conjugate Gradients Into Evolutionary Algorithms for Large-Scale Continuous Multi-Objective Optimization

Large-scale multi-objective optimization problems (LSMOPs) pose challenges to existing optimizers since a set of well-converged and diverse solutions should be found in huge search spaces. While evolutionary algorithms are good at solving small-scale multi-objective optimization problems, they are criticized for low efficiency in converging to the optimums of LSMOPs. By contrast, mathematical programming methods offer fast convergence speed on large-scale single-objective optimization problems, but they have difficulties in finding diverse solutions for LSMOPs. Currently, how to integrate evolutionary algorithms with mathematical programming methods to solve LSMOPs remains unexplored. In this paper, a hybrid algorithm is tailored for LSMOPs by coupling differential evolution and a conjugate gradient method. On the one hand, conjugate gradients and differential evolution are used to update different decision variables of a set of solutions, where the former drives the solutions to quickly converge towards the Pareto front and the latter promotes the diversity of the solutions to cover the whole Pareto front. On the other hand, objective decomposition strategy of evolutionary multi-objective optimization is used to differentiate the conjugate gradients of solutions, and the line search strategy of mathematical programming is used to ensure the higher quality of each offspring than its parent. In comparison with state-of-the-art evolutionary algorithms, mathematical programming methods, and hybrid algorithms, the proposed algorithm exhibits better convergence and diversity performance on a variety of benchmark and real-world LSMOPs.      

A multi-objective artificial physics optimization algorithm based on ranks of individuals

This paper proposes a multi-objective artificial physics optimization algorithm based on individuals’ ranks. Using a Pareto sorting based technique and incorporating the concept of neighborhood crowding degree, evolutionary individuals in the search space are evaluated at first. Then each individual is assigned a unique serial number in terms of its performance, which affects the mass of the individual. Thereby, the population evolves towards the direction of the Pareto-optimal front. Synchronously, the presented approach has good diversity, such that the population is spread evenly on the Pareto front. Results of simulation on a number of difficult test problems show that the proposed algorithm, with less evolutionary generations, is able to find a better spread of solutions and better convergence near the true Pareto-optimal front compared to classical multi-objective evolutionary algorithms (NSGA, SPEA, MOPSO) and to simple multi-objective artificial physics optimization algorithm.     

Introducing robustness in multi-objective optimization

In optimization studies including multi-objective optimization, the main focus is placed on finding the global optimum or global Pareto-optimal solutions, representing the best possible objective values. However, in practice, users may not always be interested in finding the so-called global best solutions, particularly when these solutions are quite sensitive to the variable perturbations which cannot be avoided in practice. In such cases, practitioners are interested in finding the robust solutions which are less sensitive to small perturbations in variables. Although robust optimization is dealt with in detail in single-objective evolutionary optimization studies, in this paper, we present two different robust multi-objective optimization procedures, where the emphasis is to find a robust frontier, instead of the global Pareto-optimal frontier in a problem. The first procedure is a straightforward extension of a technique used for single-objective optimization and the second procedure is a more practical approach enabling a user to set the extent of robustness desired in a problem. To demonstrate the differences between global and robust multi-objective optimization principles and the differences between the two robust optimization procedures suggested here, we develop a number of constrained and unconstrained test problems having two and three objectives and show simulation results using an evolutionary multi-objective optimization (EMO) algorithm. Finally, we also apply both robust optimization methodologies to an engineering design problem.     

求解连续空间优化问题的改进蜂群算法

为了有效地解决人工蜂群算法容易陷入局部最优的缺陷,提出了一种改进蜂群算法。首先,利用反向学习方法构建初始种群,以提高初始化解的质量。同时,利用分布估计算法构造优秀个体解空间的概率模型以进行邻域搜索,以改善算法的搜索性能并防止陷入局部最优。对连续空间优化问题进行了仿真实验,结果表明改进算法具有较快的收敛速度,全局寻优能力显著提高。     

Learning algorithm for multimodal optimization

We present a new evolutionary algorithm—“learning algorithm” for multimodal optimization. The scheme for reproducing a new generation is very simple. Control parameters, of the length of the list of historical best solutions and the “learning probability” of the current solutions being moved towards the current best solutions and towards the historical ones, are used to assign different search intensities to different parts of the feasible area and to direct the updating of the current solutions. Results of numerical tests on minimization of the 2D Schaffer function, the 2D Shubert function and the 10D Ackley function show that this algorithm is effective and efficient in finding multiple global solutions of multimodal optimization problems.     

基于自适应学习的多目标粒子群优化算法

将进化算法应用于某些多目标优化问题时,采用增加种群规模和进化代数的方法往往耗费大量的目标函数计算开销,且达不到提高种群进化效率的目的,为此提出了一种基于自适应学习最优搜索方向的多目标粒子群优化算法。采用自适应惯性权值平衡算法的全局和局部搜索能力,采用聚类排挤方法保持Pareto非支配解集的分布均匀性,使用最近邻学习方法为每个粒子在Pareto非支配解集中寻找一个最优飞行目标来提高其收敛速度并保持粒子群搜索方向的多样性。实验结果表明,提出的算法可在显著地降低函数评估成本的前提下实现快速的搜索,并使粒子群均匀地逼近Pareto最优面。     

A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem

In recent years, the historical data during the search process of evolutionary algorithms has received increasing attention from many researchers, and some hybrid evolutionary algorithms with machine-learning have been proposed. However, the majority of the literature is centered on continuous problems with a single optimization objective. There are still a lot of problems to be handled for multi-objective combinatorial optimization problems. Therefore, this paper proposes a machine-learning based multi-objective memetic algorithm (ML-MOMA) for the discrete permutation flowshop scheduling problem. There are two main features in the proposed ML-MOMA. First, each solution is assigned with an individual archive to store the non-dominated solutions found by it and based on these individual archives a new population update method is presented. Second, an adaptive multi-objective local search is developed, in which the analysis of historical data accumulated during the search process is used to adaptively determine which non-dominated solutions should be selected for local search and how the local search should be applied. Computational results based on benchmark problems show that the cooperation of the above two features can help to achieve a balance between evolutionary global search and local search. In addition, many of the best known Pareto fronts for these benchmark problems in the literature can be improved by the proposed ML-MOMA.     

一种基于偏好的多目标调和遗传算法

最近涌现了各种进化方法来解决多目标优化问题,多数方法使用Pareto优胜关系作为选择策略而没有采用偏好信息.这些算法不能有效处理目标数目许多时的优化问题.通过在不同准则之间引入偏好来解决该问题,提出一种多目标调和遗传算法MOCGA(multi-objective concordance genetic algorithm).当同时待优化的目标数目增加时,根据决策者提供的信息使用弱优胜关系进行个体优劣的比较.这种算法被证明为能收敛至全局最优.对于目标数目为很多的优化问题,测试实验结果表明了这种新算法的有效性.     

Attributed multi-objective comprehensive learning particle swarm optimization for optimal security of networks

In particle swarm optimization (PSO) each particle uses its personal and global or local best positions by linear summation. However, it is very time consuming to find the global or local best positions in case of complex problems. To overcome this problem, we propose a new multi-objective variant of PSO called attributed multi-objective comprehensive learning particle swarm optimizer (A-MOCLPSO). In this technique, we do not use global or local best positions to modify the velocity of a particle; instead, we use the best position of a randomly selected particle from the whole population to update the velocity of each dimension. This method not only increases the speed of the algorithm but also searches in more promising areas of the search space. We perform an extensive experimentation on well-known benchmark problems such as Schaffer (SCH), Kursawa (KUR), and Zitzler–Deb–Thiele (ZDT) functions. The experiments show very convincing results when the proposed technique is compared with existing versions of PSO known as multi-objective comprehensive learning particle swarm optimizer (MOCLPSO) and multi-objective particle swarm optimization (MOPSO), as well as non-dominated sorting genetic algorithm II (NSGA-II). As a case study, we apply our proposed A-MOCLPSO algorithm on an attack tree model for the security hardening problem of a networked system in order to optimize the total security cost and the residual damage, and provide diverse solutions for the problem. The results of our experiments show that the proposed algorithm outperforms the previous solutions obtained for the security hardening problem using NSGA-II, as well as MOCLPSO for the same problem. Hence, the proposed algorithm can be considered as a strong alternative to solve multi-objective optimization problems.     

Simultaneous concept-based evolutionary multi-objective optimization

In contrast to traditional multi-objective problems the concept-based version of such problems involves sets of particular solutions, which represent predefined conceptual solutions. This paper addresses the concept-based multi-objective problem by proposing two novel multi objective evolutionary algorithms. It also compares two major search approaches.The suggested algorithms deal with resource sharing among concepts, and within each concept, while simultaneously evolving concepts towards a Pareto front by way of their representing sets. The introduced algorithms, which use a simultaneous search approach, are compared with a sequential one. For this purpose concept-based performance indicators are suggested and used. The comparison study includes both the computational time and the quality of the concept-based front representation. Finally, the effect on the computational time of both the concept fitness evaluation time and concept optimality, for both the sequential and simultaneous approaches, is highlighted.     

面向多目标优化的适应度共享免疫克隆算法

多目标优化的日标在于使得解集能够快速的逼近真实Pareto前沿.针对解的分布性问题,以免疫克隆算法为框架,引入适应度共享策略,提出了一种新的具有良好分布性保持的多目标优化进化算法;算法建立外部群体以保存非支配解,以Pareto优和共亨适应度作为外部群体更新与激活抗体选择的双重标准.为了增强算法对决策空间的开发能力,引入...     

基于目标空间分解和连续变异的多目标粒子群算法

针对当前多目标粒子群优化算法收敛性和多样性不佳等问题,提出了一种基于目标空间分解和连续变异的多目标粒子群优化算法。利用目标空间分解方法将粒子群分配到预先设定好的子区域中,在该过程中,通过一种新适应值公式来对每个子区域中的粒子进行择优筛选,该适应值公式融入了支配强度因素;在全局搜索过程中,使用差分变异、高斯变异和柯西变异对全局引导粒子的位置进行连续变异操作。将该算法与当前主流的一些多目标优化算法进行对比实验,结果表明,本文提出的算法在提高粒子收敛性的同时,多样性也得到了提升。