Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling

This paper shows how the performance of evolutionary multiobjective optimization (EMO) algorithms can be improved by hybridization with local search. The main positive effect of the hybridization is the improvement in the convergence speed to the Pareto front. On the other hand, the main negative effect is the increase in the computation time per generation. Thus, the number of generations is decreased when the available computation time is limited. As a result, the global search ability of EMO algorithms is not fully utilized. These positive and negative effects are examined by computational experiments on multiobjective permutation flowshop scheduling problems. Results of our computational experiments clearly show the importance of striking a balance between genetic search and local search. In this paper, we first modify our former multiobjective genetic local search (MOGLS) algorithm by choosing only good individuals as initial solutions for local search and assigning an appropriate local search direction to each initial solution. Next, we demonstrate the importance of striking a balance between genetic search and local search through computational experiments. Then we compare the modified MOGLS with recently developed EMO algorithms: the strength Pareto evolutionary algorithm and revised nondominated sorting genetic algorithm. Finally, we demonstrate that a local search can be easily combined with those EMO algorithms for designing multiobjective memetic algorithms.     

Towards faster convergence of evolutionary multi-criterion optimization algorithms using Karush Kuhn Tucker optimality based local search

Evolutionary multi-criterion optimization (EMO) algorithms emphasize non-dominated and less crowded solutions in a population iteratively until the population converges close to the Pareto optimal set. During the search process, non-dominated solutions are differentiated only by their local crowding or contribution to hypervolume or using a similar other metric. Thus, during evolution and even at the final iteration, the true convergence behavior of each non-dominated solutions from the Pareto optimal set is unknown. Recent studies have used Karush Kuhn Tucker (KKT) optimality conditions to develop a KKT Proximity Measure (KKTPM) for estimating proximity of a solution from Pareto optimal set for a multi-objective optimization problem. In this paper, we integrate KKTPM with a recently proposed EMO algorithm to enhance its convergence properties towards the true Pareto optimal front. Specifically, we use KKTPM to identify poorly converged non-dominated solutions in every generation and apply an achievement scalarizing function based local search procedure to improve their convergence. Assisted by the KKTPM, the modified algorithm is designed in a way that maintains the total number of function evaluations as low as possible while making use of local search where it is most needed. Simulations on both constrained and unconstrained multi- and many objectives optimization problems demonstrate that the hybrid algorithm significantly improves the overall convergence properties. This study brings evolutionary optimization closer to mainstream optimization field and should motivate researchers to utilize KKTPM measure further within EMO and other numerical optimization algorithms.     

Dynamic multiobjective optimization problems: test cases, approximations, and applications

After demonstrating adequately the usefulness of evolutionary multiobjective optimization (EMO) algorithms in finding multiple Pareto-optimal solutions for static multiobjective optimization problems, there is now a growing need for solving dynamic multiobjective optimization problems in a similar manner. In this paper, we focus on addressing this issue by developing a number of test problems and by suggesting a baseline algorithm. Since in a dynamic multiobjective optimization problem, the resulting Pareto-optimal set is expected to change with time (or, iteration of the optimization process), a suite of five test problems offering different patterns of such changes and different difficulties in tracking the dynamic Pareto-optimal front by a multiobjective optimization algorithm is presented. Moreover, a simple example of a dynamic multiobjective optimization problem arising from a dynamic control loop is presented. An extension to a previously proposed direction-based search method is proposed for solving such problems and tested on the proposed test problems. The test problems introduced in this paper should encourage researchers interested in multiobjective optimization and dynamic optimization problems to develop more efficient algorithms in the near future.     

Evolutionary multiobjective optimization using an outranking-based dominance generalization

One aspect that is often disregarded in the current research on evolutionary multiobjective optimization is the fact that the solution of a multiobjective optimization problem involves not only the search itself, but also a decision making process. Most current approaches concentrate on adapting an evolutionary algorithm to generate the Pareto frontier. In this work, we present a new idea to incorporate preferences into a multi-objective evolutionary algorithm (MOEA). We introduce a binary fuzzy preference relation that expresses the degree of truth of the predicate “x is at least as good as y”. On this basis, a strict preference relation with a reasonably high degree of credibility can be established on any population. An alternative x is not strictly outranked if and only if there does not exist an alternative y which is strictly preferred to x. It is easy to prove that the best solution is not strictly outranked. For validating our proposed approach, we used the non-dominated sorting genetic algorithm II (NSGA-II), but replacing Pareto dominance by the above non-outranked concept. So, we search for the non-strictly outranked frontier that is a subset of the Pareto frontier. In several instances of a nine-objective knapsack problem our proposal clearly outperforms the standard NSGA-II, achieving non-outranked solutions which are in an obviously privileged zone of the Pareto frontier.     

A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows

This paper addresses the multiobjective vehicle routing problem with time windows (MOVRPTW). The objectives are to minimize the number of vehicles and the total distance simultaneously. Our approach is based on an evolutionary algorithm and aims to find the set of Pareto optimal solutions. We incorporate problem-specific knowledge into the genetic operators. The crossover operator exchanges one of the best routes, which has the shortest average distance, the relocation mutation operator relocates a large number of customers in non-decreasing order of the length of the time window, and the split mutation operator breaks the longest-distance link in the routes. Our algorithm is compared with 10 existing algorithms by standard 100-customer and 200-customer problem instances. It shows competitive performance and updates more than 1/3 of the net set of the non-dominated solutions.     

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     

A preference multi-objective optimization based on adaptive rank clone and differential evolution

Evolutionary multi-objective optimization (EMO) algorithms have been used in various real-world applications. However, most of the Pareto domination based multi-objective optimization evolutionary algorithms are not suitable for many-objective optimization. Recently, EMO algorithm incorporated decision maker’s preferences became a new trend for solving many-objective problems and showed a good performance. In this paper, we first use a new selection scheme and an adaptive rank based clone scheme to exploit the dynamic information of the online antibody population. Moreover, a special differential evolution (DE) scheme is combined with directional information by selecting parents for the DE calculation according to the ranks of individuals within a population. So the dominated solutions can learn the information of the non-dominated ones by using directional information. The proposed method has been extensively compared with two-archive algorithm, light beam search non-dominated sorting genetic algorithm II and preference rank immune memory clone selection algorithm over several benchmark multi-objective optimization problems with from two to ten objectives. The experimental results indicate that the proposed algorithm achieves competitive results.     

The mean–variance cardinality constrained portfolio optimization problem: An experimental evaluation of five multiobjective evolutionary algorithms

This paper compares the effectiveness of five state-of-the-art multiobjective evolutionary algorithms (MOEAs) together with a steady state evolutionary algorithm on the mean–variance cardinality constrained portfolio optimization problem (MVCCPO). The main computational challenges of the model are due to the presence of a nonlinear objective function and the discrete constraints. The MOEAs considered are the Niched Pareto genetic algorithm 2 (NPGA2), non-dominated sorting genetic algorithm II (NSGA-II), Pareto envelope-based selection algorithm (PESA), strength Pareto evolutionary algorithm 2 (SPEA2), and e-multiobjective evolutionary algorithm (e-MOEA). The computational comparison was performed using formal metrics proposed by the evolutionary multiobjective optimization community on publicly available data sets which contain up to 2196 assets.     

WBMOAIS: A novel artificial immune system for multiobjective optimization

This study presents a novel weight-based multiobjective artificial immune system (WBMOAIS) based on opt-aiNET, the artificial immune system algorithm for multi-modal optimization. The proposed algorithm follows the elementary structure of opt-aiNET, but has the following distinct characteristics: (1) a randomly weighted sum of multiple objectives is used as a fitness function. The fitness assignment has a much lower computational complexity than that based on Pareto ranking, (2) the individuals of the population are chosen from the memory, which is a set of elite solutions, and a local search procedure is utilized to facilitate the exploitation of the search space, and (3) in addition to the clonal suppression algorithm similar to that used in opt-aiNET, a new truncation algorithm with similar individuals (TASI) is presented in order to eliminate similar individuals in memory and obtain a well-distributed spread of non-dominated solutions. The proposed algorithm, WBMOAIS, is compared with the vector immune algorithm (VIS) and the elitist non-dominated sorting genetic system (NSGA-II) that are representative of the state-of-the-art in multiobjective optimization metaheuristics. Simulation results on seven standard problems (ZDT6, SCH2, DEB, KUR, POL, FON, and VNT) show WBMOAIS outperforms VIS and NSGA-II and can become a valid alternative to standard algorithms for solving multiobjective optimization problems.     

A hybrid evolutionary multiobjective optimization strategy for the dynamic power supply problem in magnesia grain manufacturing

The supply trajectory of electric power for submerged arc magnesia furnace determines the yields and grade of magnesia grain during the manufacture process. As the two production targets (i.e., the yields and the grade of magnesia grain) are conflicting and the process is subject to changing conditions, the supply of electric power needs to be dynamically optimized to track the moving Pareto optimal set with time. A hybrid evolutionary multiobjective optimization strategy is proposed to address the dynamic multiobjective optimization problem. The hybrid strategy is based on two techniques. The first one uses case-based reasoning to immediately generate good solutions to adjust the power supply once the environment changes, and then apply a multiobjective evolutionary algorithm to accurately solve the problem. The second one is to learn the case solutions to guide and promote the search of the evolutionary algorithm, and the best solutions found by the evolutionary algorithm can be used to update the case library to improve the accuracy of case-based reasoning in the following process. Due to the effectiveness of mutual promotion, the hybrid strategy can continuously adapt and search in dynamic environments. Two prominent multiobjective evolutionary algorithms are integrated into the hybrid strategy to solve the dynamic multiobjective power supply optimization problem. The results from a series of experiments show that the proposed hybrid algorithms perform better than their component multiobjective evolutionary algorithms for the tested problems.     

An efficient evolutionary optimization algorithm for multiobjective distribution feeder reconfiguration

In this paper, a Multi-objective Modified Honey Bee Mating Optimization (MMHBMO) evolutionary algorithm is proposed to solve the multi-objective Distribution Feeder Reconfiguration (DFR). The real power loss, the number of the switching operations and the deviation of the voltage at each node are considered as the objective functions. Conventional algorithms for solving the multiobjective optimization problems convert the multiple objectives into a single objective using a vector of the user-predefined weights. This paper presents a new MHBMO algorithm for the DFR problem. In the proposed algorithm an external repository is utilized to save non-dominated solutions found during the search process. A fuzzy clustering technique is used to control the size of the repository within the limits because of the objective functions are not the same. The proposed algorithm is tested on a distribution test feeder.     

Multiobjective evolutionary algorithms for electric power dispatch problem

The potential and effectiveness of the newly developed Pareto-based multiobjective evolutionary algorithms (MOEA) for solving a real-world power system multiobjective nonlinear optimization problem are comprehensively discussed and evaluated in this paper. Specifically, nondominated sorting genetic algorithm, niched Pareto genetic algorithm, and strength Pareto evolutionary algorithm (SPEA) have been developed and successfully applied to an environmental/economic electric power dispatch problem. A new procedure for quality measure is proposed in this paper in order to evaluate different techniques. A feasibility check procedure has been developed and superimposed on MOEA to restrict the search to the feasible region of the problem space. A hierarchical clustering algorithm is also imposed to provide the power system operator with a representative and manageable Pareto-optimal set. Moreover, an approach based on fuzzy set theory is developed to extract one of the Pareto-optimal solutions as the best compromise one. These multiobjective evolutionary algorithms have been individually examined and applied to the standard IEEE 30-bus six-generator test system. Several optimization runs have been carried out on different cases of problem complexity. The results of MOEA have been compared to those reported in the literature. The results confirm the potential and effectiveness of MOEA compared to the traditional multiobjective optimization techniques. In addition, the results demonstrate the superiority of the SPEA as a promising multiobjective evolutionary algorithm to solve different power system multiobjective optimization problems.     

Rank-density-based multiobjective genetic algorithm and benchmark test function study

Concerns the use of evolutionary algorithms (EA) in solving multiobjective optimization problems (MOP). We propose the use of a rank-density-based genetic algorithm (RDGA) that synergistically integrates selected features from existing algorithms in a unique way. A new ranking method, automatic accumulated ranking strategy, and a "forbidden region" concept are introduced, completed by a revised adaptive cell density evaluation scheme and a rank-density-based fitness assignment technique. In addition, four types of MOP features, such as discontinuous and concave Pareto front, local optimality, high-dimensional decision space and high-dimensional objective space are exploited and the corresponding MOP test functions are designed. By examining the selected performance indicators, RDGA is found to be statistically competitive with four state-of-the-art algorithms in terms of keeping the diversity of the individuals along the tradeoff surface, tending to extend the Pareto front to new areas and finding a well-approximated Pareto optimal front.     

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

On Set-Based Multiobjective Optimization

Assuming that evolutionary multiobjective optimization (EMO) mainly deals with set problems, one can identify three core questions in this area of research: 1) how to formalize what type of Pareto set approximation is sought; 2) how to use this information within an algorithm to efficiently search for a good Pareto set approximation; and 3) how to compare the Pareto set approximations generated by different optimizers with respect to the formalized optimization goal. There is a vast amount of studies addressing these issues from different angles, but so far only a few studies can be found that consider all questions under one roof. This paper is an attempt to summarize recent developments in the EMO field within a unifying theory of set-based multiobjective search. It discusses how preference relations on sets can be formally defined, gives examples for selected user preferences, and proposes a general preference-independent hill climber for multiobjective optimization with theoretical convergence properties. Furthermore, it shows how to use set preference relations for statistical performance assessment and provides corresponding experimental results. The proposed methodology brings together preference articulation, algorithm design, and performance assessment under one framework and thereby opens up a new perspective on EMO.      

Vector optimization of laser solid freeform fabrication system using a hierarchical mutable smart bee-fuzzy inference system and hybrid NSGA-II/self-organizing map

The purpose of current investigation is to develop a robust intelligent framework to achieve efficient and reliable operating process parameters for laser solid freeform fabrication (LSFF) process as a recent and ongoing topic of investigation. Firstly, based on mutable smart bee algorithm (MSBA) and fuzzy inference system (FIS) two models are developed to identify the clad hight (deposited layer thickness) and the melt pool depth as functions of scanning speed, laser power and mass powder. Using the obtained model, the well-known multiobjective evolutionary algorithm called non-dominated sorting genetic algorithm (NSGA-II) is used for multi-criterion optimization of LSFF process. According to the available reported information and also the author’s experiments, it is observed that the obtained Pareto front is not justifiable since it fails to cover the entire Pareto hyper-volume due to the lack of intensified exploration. To tackle this deficiency, authors execute a post optimization process through utilizing a competitive unsupervised machine learning approach known as self-organizing map (SOM) with cubic spatial topology. Achieved results indicate that this grid based network is capable of enhancing the intensification of Pareto solutions since its synaptic weights successfully imitate the characteristics of non-dominated solutions (optimal values of mass powder, laser power and scanning speed). For extracting the corresponding objective functions of these non-dominated synaptic weights, MSBA–FIS is used again to map the operating parameters to objective functions space. After the termination of abovementioned procedures, a valuable archive, containing a set of non-dominated solutions, is obtained which lets the authors to make a deliberate engineering trade-off. Simulation experiments reveal that the proposed intelligent framework is highly capable to cope with complex engineering systems. Besides, it is observed that MSBA is more efficient in evolving the structure of hierarchical fuzzy inference system in comparison with classic hierarchical GA-FIS model. This rises from the simple structure of MSBA that turns it into a fast and robust algorithm for handling constraint distributed systems (i.e. hierarchical FIS in current investigation). The obtained results also indicate that the introduced intelligent framework is applicable for optimal design of complex engineering systems where there exists no analytical formulation that describes the phenomenon as well as information of optimal operating parameters.     

Convergence Acceleration Operator for Multiobjective Optimization

A convergence acceleration operator (CAO) is described which enhances the search capability and the speed of convergence of the host multiobjective optimization algorithm. The operator acts directly in the objective space to suggest improvements to solutions obtained by a multiobjective evolutionary algorithm (MOEA). The suggested improved objective vectors are then mapped into the decision variable space and tested. This method improves upon prior work in a number of important respects, such as mapping technique and solution improvement. Further, the paper discusses implications for many-objective problems and studies the impact of the use of the CAO as the number of objectives increases. The CAO is incorporated with two leading MOEAs, the non-dominated sorting genetic algorithm and the strength Pareto evolutionary algorithm and tested. Results show that the hybridized algorithms consistently improve the speed of convergence of the original algorithm while maintaining the desired distribution of solutions. It is shown that the operator is a transferable component that can be hybridized with any MOEA.      

基于分解和多策略变异的多目标差分进化算法*

差分进化是一种有效的优化技术,已成功用于多目标优化问题。但也存在Pareto最优集合的收敛慢和多样性差等问题。针对上述不足,本文提出了一种基于分解和多策略变异的多目标差分进化算法(MODE/DMSM)。该算法利用基于分解的方法将多目标优化问题分解为多个单目标优化问题;通过高效的非支配排序方法选择具有良好收敛性和多样性的解来指导差分进化过程;采用了多策略变异方法来平衡进化过程中收敛性和多样性。在ZDT和DTLZ的10个测试函数上的仿真结果表明,本文算法在Parato最优集合的收敛性和多样性优于其他六种代表性多目标优化算法。     

Convergence analysis of some multiobjective evolutionary algorithms when discovering motifs

An important issue in multiobjective optimization is the study of the convergence speed of algorithms. An optimization problem must be defined as simple as possible to minimize the computational cost required to solve it. In this work, we study the convergence speed of seven multiobjective evolutionary algorithms: DEPT, MO-VNS, MOABC, MO-GSA, MO-FA, NSGA-II, and SPEA2; when solving an important biological problem: the motif discovery problem. We have used twelve instances of four different organisms as benchmark, analyzing the number of fitness function evaluations required by each algorithm to achieve reasonable quality solutions. We have used the hypervolume indicator to evaluate the solutions discovered by each algorithm, measuring its quality every 100 evaluations. This methodology also allows us to study the hit rates of the algorithms over 30 independent runs. Moreover, we have made a deeper study in the more complex instance of each organism. In this study, we observe the increase of the archive (number of non-dominated solutions) and the spread of the Pareto fronts obtained by the algorithm in the median execution. As we will see, our study reveals that DEPT, MOABC, and MO-FA provide the best convergence speeds and the highest hit rates.