Many -objective evolutionary algorithms have gained significant achievements over the years. However, the difficulty in balancing convergence and diversity of the population remains. In this paper, we propose a cascad...
详细信息
Many -objective evolutionary algorithms have gained significant achievements over the years. However, the difficulty in balancing convergence and diversity of the population remains. In this paper, we propose a cascading elimination based evolutionary algorithm with variable classification mutation, termed CEEA, for many -objective optimization. In CEEA, a cascading elimination mechanism based on the binary quality indicator and balanceable fitness estimation (BFE) is proposed for eliminating poor individuals one by one and further balancing convergence and diversity of the population. To be specific, two individuals with the minimum binary quality indicator value are found from the population, where these two individuals may exist in the dominance relation and have more similar search directions. If the relation of two selected individuals is dominance, the dominated individual is eliminated. Otherwise, one individual is eliminated by the BFE method. In addition, a binary quality indicator based variable classification mutation strategy is developed to produce promising individuals, and further improve the search efficiency of CEEA. Experimental studies on three well-known benchmark test suites, a combinational optimization problem, and a real -world engineering application have demonstrated that our CEEA has a superior performance to its peer competitors on various manyobjective problems.
In this study, we have thoroughly researched on performance of six state-of-the-art Multiobjective evolutionary algorithms (MOEAs) under a number of carefully crafted many-objective optimization benchmark problems. Ea...
详细信息
In this study, we have thoroughly researched on performance of six state-of-the-art Multiobjective evolutionary algorithms (MOEAs) under a number of carefully crafted many-objective optimization benchmark problems. Each MOEA apply different method to handle the difficulty of increasing objectives. Performance metrics ensemble exploits a number of performance metrics using double elimination tournament selection and provides a comprehensive measure revealing insights pertaining to specific problem characteristics that each MOEA could perform the best. Experimental results give detailed information for performance of each MOEA to solve many-objective optimization problems. More importantly, it shows that this performance depends on two distinct aspects: the ability of MOEA to address the specific characteristics of the problem and the ability of MOEA to handle high-dimensional objective space. (C) 2014 Elsevier Ltd. All rights reserved.
Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute to the theoretical understanding of evolutionary algorithms and carry out a pa...
详细信息
Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound their runtime. We analyze the runtime in dependence of the number of inner points k. In the first part of the paper, we study a (mu + lambda) EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time O (n . A(epsilon) . max ((mu/lambda) . n(2), 1) + (mu/lambda) . n(4k)(2k - 1)!) where A is a function of the minimum angle epsilon between any three points. Based on insights provided by the analysis, we improve this upper bound by introducing a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps. This strategy improves the upper bound to O(n . A(epsilon) . max {(mu/lambda) . n(2), 1} + (mu/lambda) . n(2k)(k - 1)!). In the second part of the paper, we use the information gained in the analysis to incorporate domain knowledge to design two fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a (mu + lambda) EA based on an analysis by M. Theile, 2009, "Exact solutions to the traveling salesperson problem by a population-based evolutionary algorithm," Lecture notes in computer science, Vol. 5482 (pp. 145-155), that solves the TSP with k inner points in O(max{2(k)k(2)n(2)lambda(-1), n}) generations with probability 1 - e(-Omega(n)). We then design a (mu + lambda) EAthat incorporates a dynamic programming step into the fitness evaluation. We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after O(max{(k - 2)!k(2k-2)lambda(-1), 1}) steps
The widespread use and applicability of evolutionary algorithms is due in part to the ability to adapt them to a particular problem-solving context by tuning their parameters. This is one of the problems that a user f...
详细信息
The widespread use and applicability of evolutionary algorithms is due in part to the ability to adapt them to a particular problem-solving context by tuning their parameters. This is one of the problems that a user faces when applying an evolutionary Algorithm to solve a given problem. Before running the algorithm, the user typically has to specify values for a number of parameters, such as population size, selection rate, and probability operators. This paper empirically assesses the performance of an automatic parameter tuning system in order to avoid the problems of time requirements and the interaction of parameters. The system, based on Bayesian Networks and Case-Based Reasoning methodology, estimates the best parameter setting for maximizing the performance of evolutionary algorithms. The algorithms are applied to solve a basic problem in constraint-based, geometric parametric modeling, as an instance of general constraint-satisfaction problems. The experimental results demonstrate the validity of the proposed system and its potential effectiveness for configuring algorithms. (C) 2014 Elsevier B.V. All rights reserved.
In this paper, a novel general class of optimality criteria is defined and proposed to solve multi-objective optimization problems by using evolutionary algorithms. These criteria, named p-optimality criteria, allow u...
详细信息
In this paper, a novel general class of optimality criteria is defined and proposed to solve multi-objective optimization problems by using evolutionary algorithms. These criteria, named p-optimality criteria, allow us to value (assess) the relative importance of those solutions with outstanding performance in very few objectives and poor performance in all others, regarding those solutions with an equilibrium (balance) among all the objectives. The optimality criteria avoid interrelating the relative values of the different objectives, respecting the integrity of each one in a rational way. As an example, a simple multi-objective approach based on the p-optimality criteria and genetic algorithms is designed, where solutions used to generate new solutions are selected according to the proposed optimality criteria. It is implemented and applied on several benchmark test problems, and its performance is compared to that of the nondominated sort genetic algorithm-II method, in order to analyze the contribution and potential of these new optimality criteria.
Chaotic maps play an important role in improving evolutionary algorithms (EAs) for avoiding the local optima and speeding up the convergence. However, different chaotic maps in different phases have different effects ...
详细信息
Chaotic maps play an important role in improving evolutionary algorithms (EAs) for avoiding the local optima and speeding up the convergence. However, different chaotic maps in different phases have different effects on EAs. This paper focuses on exploring the effects of chaotic maps and giving comprehensive guidance for improving multiobjective evolutionary algorithms (MOEAs) by series of experiments. NSGA-II algorithm, a representative of MOEAs using the nondominated sorting and elitist strategy, is taken as the framework to study the effect of chaotic maps. Ten chaotic maps are applied in MOEAs in three phases, that is, initial population, crossover, and mutation operator. Multiobjective problems (MOPs) adopted are ZDT series problems to show the generality. Since the scale of some sequences generated by chaotic maps is changed to fit for MOPs, the correctness of scaling transformation of chaotic sequences is proved by measuring the largest Lyapunov exponent. The convergence metric.. and diversity metric. are chosen to evaluate the performance of new algorithms with chaos. The results of experiments demonstrate that chaotic maps can improve the performance of MOEAs, especially in solving problems with convex and piecewise Pareto front. In addition, cat map has the best performance in solving problems with local optima.
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...
详细信息
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.
The problem of finding a cohesive subgraph, notably the s-club model, which is a subgraph with diameter at most s, is a widely applied topic in social network analysis and group of objects modeling. In particular, the...
详细信息
The problem of finding a cohesive subgraph, notably the s-club model, which is a subgraph with diameter at most s, is a widely applied topic in social network analysis and group of objects modeling. In particular, the minimum s-club cover problem (min s-club cover) is a recently introduced variant in the literature which asks to cover the vertices of a graph with a minimum number of s-clubs. The existence of common connections among these highly connected components encourages the application of multitasking optimization to leverage the shared meaningful knowledge in the discovery of multiple s-clubs at the same time. Therefore, this study proposes a multitasking evolutionary algorithm to solve the minimum s-club cover problem. Our proposal is designed with an effective solution representation method and evolutionary operators for the variation in the number of clubs. Each solution is represented by two components, where the gene number of a component can be different for each individual and can change during performing evolutionary operations. We also propose a solution generation method based on a random greedy algorithm that helps to ensure individual quality and population diversity in the initial population. The proposed algorithm is evaluated on two datasets in the DIMACS library. This study then analyzed the influence of different factors of the input data on the proposed algorithm results. Based on statistical analysis of the performance results, it is clear that our proposal's solution is superior to an existing algorithm on two-thirds of the experimental data set.
A feature model is a compact representation of the products of a software product line. The automated extraction of information from feature models is a thriving topic involving numerous analysis operations, technique...
详细信息
A feature model is a compact representation of the products of a software product line. The automated extraction of information from feature models is a thriving topic involving numerous analysis operations, techniques and tools. Performance evaluations in this domain mainly rely on the use of random feature models. However, these only provide a rough idea of the behaviour of the tools with average problems and are not sufficient to reveal their real strengths and weaknesses. In this article, we propose to model the problem of finding computationally hard feature models as an optimization problem and we solve it using a novel evolutionary algorithm for optimized feature models (ETHOM). Given a tool and an analysis operation, ETHOM generates input models of a predefined size maximizing aspects such as the execution time or the memory consumption of the tool when performing the operation over the model. This allows users and developers to know the performance of tools in pessimistic cases providing a better idea of their real power and revealing performance bugs. Experiments using ETHOM on a number of analyses and tools have successfully identified models producing much longer executions times and higher memory consumption than those obtained with random models of identical or even larger size. (C) 2013 Elsevier Ltd. All rights reserved.
In this article, a new fitness assignment scheme to evaluate the Pareto-optimal solutions for multi-objective evolutionary algorithms is proposed. The proposed DOmination Power of an individual Genetic Algorithm (DOPG...
详细信息
In this article, a new fitness assignment scheme to evaluate the Pareto-optimal solutions for multi-objective evolutionary algorithms is proposed. The proposed DOmination Power of an individual Genetic Algorithm (DOPGA) method can order the individuals in a form in which each individual (the so-called solution) could have a unique rank. With this new method, a multi-objective problem can be treated as if it were a single-objective problem without drastically deviating from the Pareto definition. In DOPGA, relative position of a solution is embedded into the fitness assignment procedures. We compare the performance of the algorithm with two benchmark evolutionary algorithms (Strength Pareto evolutionary Algorithm (SPEA) and Strength Pareto evolutionary Algorithm 2 (SPEA2)) on 12 unconstrained bi-objective and one tri-objective test problems. DOPGA significantly outperforms SPEA on all test problems. DOPGA performs better than SPEA2 in terms of convergence metric on all test problems. Also, Pareto-optimal solutions found by DOPGA spread better than SPEA2 on eight of 13 test problems.
暂无评论