Effects of nongeometric binary crossover on multiobjective 0/1 knapsack problems

Standard binary crossover operators (e.g., one-point, two-point, and uniform) tend to decrease the diversity of solutions while they improve the convergence to the Pareto front. This is because standard binary crossover operators, which are called geometric crossovers, always generate an offspring in the line segment between its parents under the Hamming distance in the genotype space. In our former study, we have already proposed a nongeometric binary crossover operator to generate an offspring outside the line segment between its parents. In this article, we examine the effect of our crossover operator on the performance of evolutionary multiobjective optimization (EMO) algorithms through computational experiments on various multiobjective knapsack problems. Experimental results show that our crossover operator improves the search ability of EMO algorithms for a wide range of test problems. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

基于目标分解的高维多目标并行进化优化方法

高维多目标优化问题普遍存在且难以解决, 到目前为止, 尚缺乏有效解决该问题的进化优化方法. 本文提出一种基于目标分解的高维多目标并行进化优化方法, 首先, 将高维多目标优化问题分解为若干子优化问题, 每一子优化问题除了包含原优化问题的少数目标函数之外, 还具有由其他目标函数聚合成的一个目标函数, 以降低问题求解的难度; 其次, 采用多种群并行进化算法, 求解分解后的每一子优化问题, 并在求解过程中, 充分利用其他子种群的信息, 以提高Pareto非被占优解的选择压力; 最后, 基于各子种群的非被占优解形成外部保存集, 从而得到高维多目标优化问题的Pareto 最优解集. 性能分析表明, 本文提出的方法具有较小的计算复杂度. 将所提方法应用于多个基准优化问题, 并与NSGA-II、PPD-MOEA、ε-MOEA、HypE和MSOPS等方法比较, 实验结果表明, 所提方法能够产生收敛性、分布性, 以及延展性优越的Pareto最优解集.     

Incorporating ϵ-dominance in AMOSA: Application to multiobjective 0/1 knapsack problem and clustering gene expression data

Recently, a new model of multiobjective simulated annealing, AMOSA, was developed which was found to provide improved performance for several multi objective optimization problems especially for problems with many objectives. In this article, we aim to further improve the performance of AMOSA by incorporating the concept of ?-dominance which is a more generalized form of conventional dominance. This strategy is referred to as ?-AMOSA. The result of ?-AMOSA is compared with those of AMOSA, NSGA-II and ?-MOEA and AMOSA for several test problems with number of objectives varying from two to fifteen and the number of variables varying from one to thirty. The performance of ?-AMOSA is also compared with other strategies for multiobjective 0/1 knapsack problem. A real life application of ?-AMOSA for clustering genes from gene expression data is also demonstrated. The results demonstrate the effectiveness of ?-AMOSA.     

基于新的适应度函数和多搜索策略的高维多目标进化算法

为提高高维多目标进化算法的性能,提出了一个基于新的适应度函数和多搜索策略的高维多目标进化算法。该算法提出了一个新的适应度函数来平衡多样性和收敛性,并且设计了一个多搜索策略来帮助交叉算子产生优秀的后代进而提高收敛性。该适应度函数首先从当前种群和新产生的后代中挑出收敛性较好的个体,然后计算这些个体的稀疏程度;该多搜索策略选择稀疏且收敛的解来执行全局和局部搜索。数值实验测试了CEC2018高维多目标竞赛的15个测试问题,每个测试问题的目标个数分别为5、10、15。实验结果表明,该算法能找到一组比四种代表性算法（如NSGAIII、MOEA/DD、KnEA、RVEA）具有更好的多样性和收敛性的解集。     

A many-objective evolutionary algorithm based on a projection-assisted intra-family election

In recent years, many researchers have put emphasis on the study of how to keep a good balance between convergence and diversity in many-objective optimization. This paper proposes a new many-objective evolutionary algorithm based on a projection-assisted intra-family election. In the proposed algorithm, basic evolution directions are adaptively generated according to the current population and potential evolution directions are excavated in each individual's family. Based on these evolution directions, a strategy of intra-family election is performed in every family and elite individuals are elected as representatives of the specific family to join the next stage, which can enhance the convergence of the algorithm. Moreover, a selection procedure based on angles is used to maintain the diversity. The performance of the proposed algorithm is verified and compared with several state-of-the-art many-objective evolutionary algorithms on a variety of well-known benchmark problems ranging from 5 to 20 objectives. Empirical results demonstrate that the proposed algorithm outperforms other peer algorithms in terms of both the diversity and the convergence of the final solutions set on most of the test instances. In particular, our proposed algorithm shows obvious superiority when handling the problems with larger number of objectives.     

An exact schema theorem for adaptive genetic algorithm and its application to machine cell formation

This paper proposes an exact schema theorem that is able to predict the expected number of copies of schemas in the next GA generation. It focuses on two-point crossover, which is widely used in many GA applications. As two important GA control parameters, crossover probability (p_c) and mutation probability (p_m) affect the performance of GAs drastically. A set of good GA parameters help in improving the ability of a GA to search for near global optimal solutions. This work shows that optimal p_c and p_m do not exist in most cases. As a result, a compromised pair of p_c and p_m may help improve the performance of GA. A multiple population search strategy enabled fuzzy c-means based evolutionary approach, which embeds the proposed exact schema theorem, to machine cell formation is then proposed. The approach enables the crossover and mutation probabilities of GAs to be made adaptive to suit different stages of the search for near optimal solutions. Three case studies were conducted. The proposed approach was able to provide better solutions consistently.     

Metaheuristics and exact methods to solve a multiobjective parallel machines scheduling problem

This paper deals with a multiobjective parallel machines scheduling problem. It consists in scheduling n independent jobs on m identical parallel machines. The job data such as processing times, release dates, due dates and sequence dependent setup times are considered. The goal is to optimize two different objectives: the makespan and the total tardiness. A mixed integer linear program is proposed to model the studied problem. As this problem is NP-hard in the strong sense, a metaheuristic method which is the second version of the non dominated sorting genetic algorithm (NSGA-II) is proposed to solve this problem. Since the parameters setting of a genetic algorithm is difficult, a fuzzy logic controller coupled with the NSGA-II (FLC-NSGA-II) is therefore proposed. The role of the fuzzy logic is to better set the crossover and the mutation probabilities in order to update the search ability. After that, an exact method based on the two phase method is also developed. We have used four measuring criteria to compare these methods. The experimental results show the advantages and the efficiency of FLC-NSGA-II.     

MOEA/D + uniform design: A new version of MOEA/D for optimization problems with many objectives

To extend multiobjective evolutionary algorithm based on decomposition (MOEA/D) in higher dimensional objective spaces, this paper proposes a new version of MOEA/D with uniform design, named the uniform design multiobjective evolutionary algorithm based on decomposition (UMOEA/D), and compares the proposed algorithm with MOEA/D and NSGA-II on some scalable test problems with three to five objectives. UMOEA/D adopts the uniform design method to set the aggregation coefficient vectors of the subproblems. Compared with MOEA/D, distribution of the coefficient vectors is more uniform over the design space, and the population size neither increases nonlinearly with the number of objectives nor considers a formulaic setting. The experimental results indicate that UMOEA/D outperforms MOEA/D and NSGA-II on almost all these many-objective test instances, especially on problems with higher dimensional objectives and complicated Pareto set shapes. Experimental results also show that UMOEA/D runs faster than NSGA-II for the problems used in this paper. In additional, the results obtained are very competitive when comparing UMOEA/D with some other algorithm on the multiobjective knapsack problems.     

一种改进的基于NSGA-II和DE的多目标混合进化算法

为提高非支配排序遗传算法（NSGA-II）的搜索精度和多样性,本文借鉴差分进化中加强局部搜索的策略,提出了一种改进的NSGA-II算法（LDMNSGA-II）。该算法利用拉丁超立方体抽样技术对解种群进行初始化,保证种群的初始分布能够均匀,采用差分进化中的变异引导算子和交叉算子替换NSGA-II的交叉算子,加强局部搜索能力和提高搜索精度,同时保留NSGA-II中的变异算子,保留算法多样性。四个经典测试函数的仿真结果表明,文中算法LDMNSGA-II在解决多目标优化问题中表现出良好的综合性能。     

Application of modified NSGA-II algorithm to multi-objective reactive power planning

This paper discusses the application of Modified Non-Dominated Sorting Genetic Algorithm-II (MNSGA-II) to multi-objective Reactive Power Planning (RPP) problem. The three objectives considered are minimization of combined operating and VAR allocation cost, bus voltage profile improvement and voltage stability enhancement. For maintaining good diversity in nondominated solutions, Dynamic Crowding Distance (DCD) procedure is implemented in NSGA-II and it is called as MNSGA-II. The standard IEEE 30-bus test system, practical 69-bus Indian system and IEEE 118-bus system are considered to analyze the performance of MNSGA-II. The results obtained using MNSGA-II are compared with NSGA-II and validated with reference pareto-front generated by conventional weighted sum method using Covariance Matrix Adapted Evolution Strategy (CMA-ES). The performance of NSGA-II and MNSGA-II are compared with respect to best, mean, worst and standard deviation of multi-objective performance measures namely gamma, spread, minimum spacing and Inverted Generational Distance (IGD) in 15 independent runs. The results show the effectiveness of MNSGA-II and confirm its potential to solve the multi-objective RPP problem. A decision-making procedure based on Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) method is used for finding best compromise solution from the set of pareto-solutions obtained through MNSGA-II.     

An improved evolutionary algorithm for handling many-objective optimization problems

It has been shown that the multi-objective evolutionary algorithms (MOEAs) act poorly in solving many-objective optimization problems which include more than three objectives. The research emphasis, in recent years, has been put into improving the MOEAs to enable them to solve many-objective optimization problems efficiently. In this paper, we propose a new composite fitness evaluation function, in a novel way, to select quality solutions from the objective space of a many-objective optimization problem. Using this composite function, we develop a new algorithm on a well-known NSGA-II and call it FR-NSGA-II, a fast reference point based NSGA-II. The algorithm is evaluated for producing quality solutions measured in terms of proximity, diversity and computational time. The working logic of the algorithm is explained using a bi-objective linear programming problem. Then we test the algorithm using experiments with benchmark problems from DTLZ family. We also compare FR-NSGA-II with four competitive algorithms from the extant literature to show that FR-NSGA-II will produce quality solutions even if the number of objectives is as high as 20.     

MaOEA/d2:一种基于双距离构造的高维多目标进化算法

传统的基于Pareto支配关系的多目标进化算法(MOEA)难以有效求解高维多目标优化问题(MaOP). 提出一种利用PBI效用函数的双距离构造的支配关系, 且无需引入额外的参数. 其次, 利用双距离定义了一种多样性保持方法, 该方法不仅考虑了解个体的双距离, 而且还可以根据优化问题的目标数目自适应地调整多样性占比, 以较好地平衡高维目标解群的收敛性和多样性. 最后, 将基于双距离构造的支配关系和多样性保持方法嵌入到NSGA-II算法框架中, 设计了一种基于双距离的高维多目标进化算法MaOEA/d². 该算法与其他5种代表性的高维多目标进化算法一同在5-、10-、15-和20-目标的DTLZ和WFG基准测试问题上进行了IGD和HV性能测试, 结果表明, MaOEA/d²算法具有较好的收敛性和多样性. 由此表明, MaOEA/d²算法是一种颇具前景的高维多目标进化算法.     

采用放松支配关系的高维多目标微分进化算法

为了提高进化算法在求解高维多目标优化问题时的收敛性和多样性,提出了采用放松支配关系的高维多目标微分进化算法。该算法采用放松的Pareto支配关系,以增加个体的选择压力;采用群体和外部存储器协同进化的方案,并通过混合微分变异算子,生成子代群体;采用基于指标的方法计算个体的适应度并对群体进行更新;采用基于Lp范数（0相似文献   

Chain-reaction solution update in MOEA/D and its effects on multi- and many-objective optimization

MOEA/D is one of the promising evolutionary algorithms for multi- and many-objective optimization. To improve the search performance of MOEA/D, this work focuses on the solution update method in the conventional MOEA/D and proposes its alternative, the chain-reaction solution update. The proposed method is designed to maintain and improve the variable (genetic) diversity in the population by avoiding duplication of solutions in the population. In addition, the proposed method determines the order of existing solutions to be updated depending on the location of each offspring in the objective space. Furthermore, when an existing solution in the population is replaced by a new offspring, the proposed method tries to reutilize the existing solution for other search directions by recursively performing the proposed chain-reaction update procedure. This work uses discrete knapsack and continuous WFG4 problems with 2–8 objectives. Experimental results using knapsack problems show the proposed chain-reaction update contributes to improving the search performance of MOEA/D by enhancing the diversity of solutions in the objective space. In addition, experimental results using WFG4 problems show that the search performance of MOEA/D can be further improved using the proposed method.     

A hybridized angle-encouragement-based decomposition approach for many-objective optimization problems

Due to the large objective space when handling many-objective optimization problems (MaOPs), it is a challenging work for multi-objective evolutionary algorithms (MOEAs) to balance convergence and diversity during the search process. Although a number of decomposition-based MOEAs have been designed for the above purpose, some difficulties are still encountered for tackling some difficult MaOPs. As inspired by the existing decomposition approaches, a new Hybridized Angle-Encouragement-based (HAE) decomposition approach is proposed in this paper, which is embedded into a general framework of decomposition-based MOEAs, called MOEA/D-HAE. Two classes of decomposition approaches, i.e., the angle-based decomposition and the proposed encouragement-based boundary intersection decomposition, are sequentially used in HAE. The first one selects appropriate solutions for association in the feasible region of each subproblem, which is expected to well maintain the diversity of associated solutions. The second one acts as a supplement for the angle-based one under the case that no solution is located in the feasible region of subproblem, which aims to ensure the convergence and explore the boundaries. By this way, HAE can effectively combine their advantages, which helps to appropriately balance convergence and diversity in evolutionary search. To study the effectiveness of HAE, two series of well-known test MaOPs (WFG and DTLZ) are used. The experimental results validate the advantages of HAE when compared to other classic decomposition approaches and also confirm the superiority of MOEA/D-HAE over seven recently proposed many-objective evolutionary algorithms.     

Multi-objective K-connected Deployment and Power Assignment in WSNs using a problem-specific constrained evolutionary algorithm based on decomposition

The K-connected Deployment and Power Assignment Problem (DPAP) in WSNs aims at deciding both the sensor locations and transmit power levels, for maximizing the network coverage and lifetime objectives under K-connectivity constraints, in a single run. Recently, it is shown that the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) is a strong enough tool for dealing with unconstraint real life problems (such as DPAP), emphasizing the importance of incorporating problem-specific knowledge for increasing its efficiency. In a constrained Multi-objective Optimization Problem (such as K-connected DPAP), the search space is divided into feasible and infeasible regions. Therefore, problem-specific operators are designed for MOEA/D to direct the search into optimal, feasible regions of the space. Namely, a DPAP-specific population initialization that seeds the initial solutions into promising regions, problem-specific genetic operators (i.e. M-tournament selection, adaptive crossover and mutation) for generating good, feasible solutions and a DPAP-specific Repair Heuristic (RH) that transforms an infeasible solution into a feasible one and maintains the MOEA/D’s efficiency simultaneously. Simulation results have shown the importance of each proposed operator and their interrelation, as well as the superiority of the DPAP-specific MOEA/D against the popular constrained NSGA-II in several WSN instances.     

基于改进多目标优化算法的分布式数据中心负载调度

在数据中心的运营中运营商需要考虑如何在利润最大化的同时降低碳排放和提升服务质量,这些目标之间的平衡是一个巨大挑战.针对该问题,建立分布式数据中心负载调度的多目标优化模型,提出一种改进拥挤距离和自适应交叉变异的非支配排序遗传算法(ICDA-NSGA-II).在NSGA-II算法的基础上,通过对拥挤距离的改进能够提高算法的开采和勘探能力,引入正态分布交叉(NDX)算子和自适应变异算子增强种群的多样性,从而保证算法能快速、准确地得到Pareto解集.为了显示改进算法的有效性,对基准测试函数进行求解,仿真结果表明,改进算法相比于典型的NSGA-II和MOEA/D具有更快的收敛速度和精度,在分布式数据中心负载调度优化中,能够快速有效地给出满足利润、碳排放和服务质量等目标的Pareto最优解.     

Using objective reduction and interactive procedure to handle many-objective optimization problems

A number of practical optimization problems are posed as many-objective (more than three objectives) problems. Most of the existing evolutionary multi-objective optimization algorithms, which target the entire Pareto-front are not equipped to handle many-objective problems. Though there have been copious efforts to overcome the challenges posed by such problems, there does not exist a generic procedure to effectively handle them. This paper presents a simplify and solve framework for handling many-objective optimization problems. In that, a given problem is simplified by identification and elimination of the redundant objectives, before interactively engaging the decision maker to converge to the most preferred solution on the Pareto-optimal front. The merit of performing objective reduction before interacting with the decision maker is two fold. Firstly, the revelation that certain objectives are redundant, significantly reduces the complexity of the optimization problem, implying lower computational cost and higher search efficiency. Secondly, it is well known that human beings are not efficient in handling several factors (objectives in the current context) at a time. Hence, simplifying the problem a priori addresses the fundamental issue of cognitive overload for the decision maker, which may help avoid inconsistent preferences during the different stages of interactive engagement. The implementation of the proposed framework is first demonstrated on a three-objective problem, followed by its application on two real-world engineering problems.     

Solving a fuzzy multi objective model of a production–distribution system using meta-heuristic based approaches

This paper studies a multi-objective production–distribution system. The objectives are to minimize total costs and maximize the reliability of transportations system. Each transportation system is assumed to be of unique reliability. In the real world, some parameters may be of vagueness; therefore, some tools such as fuzzy logic is applied to tackle with. The problem is formulated using a mixed integer programming model. Commercial software can optimally solve small sized instances. We propose two novel HEURISTICS called ranking genetic algorithm (RGA) and concessive variable neighborhood search (CVNS) in order to solve the large sized instances. RGA utilizes various crossover operators and compares their performances so that better crossover operators are used during the solution process. CVNS applies several neighborhood search structures with a novel learning procedure. The heuristics can recognize which neighborhood structure performs well and applies those more than the others. The results indicated that RGA is of higher performance.     

Dynamic and heuristic fuzzy connectives-based crossover operators for controlling the diversity and convergence of real-coded genetic algorithms

Genetic algorithms are adaptive methods which may be used as approximation heuristic for search and optimization problems. Genetic algorithms process a population of search space solutions with three operations: selection, crossover, and mutation. A great problem in the use of genetic algorithms is the premature convergence, a premature stagnation of the search caused by the lack of diversity in the population and a disproportionate relationship between exploitation and exploration. The crossover operator is considered one of the most determinant elements for solving this problem. In this article we present two types of crossover operators based on fuzzy connectives for real-coded genetic algorithms. The first type is designed to keep a suitable sequence between the exploration and the exploitation along the genetic algorithm's run, the dynamic fuzzy connectives-based crossover operators, the second, for generating offspring near to the best parents in order to offer diversity or convergence in a profitable way, the heuristic fuzzy connectives-based crossover operators. We combine both crossover operators for designing dynamic heuristic fuzzy connectives-based crossover operators that show a robust behavior. © 1996 John Wiley & Sons, Inc.