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
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.
Developing physical closure models with explicit expressions based on a given dataset is essential to science and engineering. For such symbolic regression tasks, biology-inspired evolutionary algorithms are most wide...
详细信息
Developing physical closure models with explicit expressions based on a given dataset is essential to science and engineering. For such symbolic regression tasks, biology-inspired evolutionary algorithms are most widely used. However, typical evolutionary algorithms do not utilize any structural information inherent in training data, which limits their performance in finding accurate model structures and coefficients. By combining one evolutionary algorithm, gene expression programing (GEP), with an artificial neural network (ANN) for symbolic regression, we propose a novel evolutionary neural network method, in which candidate expressions are specifically designed so that they can be transformed between the GEP and ANN structures during training iterations. By combining the GEP's global searching and the ANN's gradient optimization capabilities, efficient and robust convergence to accurate models can be achieved. In addition, sparsity-enhancing strategies have been introduced to improve the interpretability of the trained models. The present method has been tested for finding different physical laws and then applied to turbulence modeling problems with different configurations, showing advantages compared to the existing GEP and ANN methods.
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.
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.
Design change is an important issue in complex product development projects. In a complex product with numerous parts (also known as components), the change of one key part may spread to other parts associated with it...
详细信息
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.
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.
This paper tackles the optimization of a stand-alone hybrid photovoltaic-batteries-hydrogen (PV-hydrogen) system, using an evolutionary algorithm. Specifically, a stand alone power system for feeding a remote telecomm...
详细信息
This paper tackles the optimization of a stand-alone hybrid photovoltaic-batteries-hydrogen (PV-hydrogen) system, using an evolutionary algorithm. Specifically, a stand alone power system for feeding a remote telecommunications facility is studied. The considered system is specifically designed to cover the power necessities of remote, isolated telecommunications facilities, so it must be able to work in an unattended way during a long time period. On the other hand, if maintenance visits are scheduled, it is intuitive that the cost of the stand alone system could be reduced. Thus, two different optimization problems have been considered in this work. The first one consists in the obtention of the optimal number, distribution (two different arrays of batteries must be fed) and disposition (slope and azimuth) of the PV panels in the facility, for the case of autonomous operation of the telecommunication system during at least two years. The second problem considered consists of scheduling a maintenance visit per year, where a technician is able to reconfigure the system. In this case, the problem consists of obtaining the optimal number, distribution, disposition of the PV panels, and also the time of the year where the maintenance visit should take place. An evolutionary algorithm, able to tackle both problems with very few changes, is described in this paper. The proposed evolutionary algorithm has been analyzed in a simulation of a real PV-hydrogen system sited at National Spanish Institute for Aerospace Technology (INTA), at Torrejon de Ardoz, Madrid, Spain. The well-known software TRNSYS has been used in order to simulate the behavior of this PV-hydrogen system. Several simulations of the system recreating different weather conditions of three Spanish cities (Madrid, Barcelona and La Coruna) have been carried out, and a comparative analysis of the results obtained by the evolutionary algorithm has been done. The results obtained in the first problem tackled show
The analysis of the performance of different approaches is a staple concern in the design of Computational Intelligence experiments. Any proper analysis of evolutionary optimization algorithms should incorporate a ful...
详细信息
The analysis of the performance of different approaches is a staple concern in the design of Computational Intelligence experiments. Any proper analysis of evolutionary optimization algorithms should incorporate a full set of benchmark problems and state-of-the-art comparison algorithms. For the sake of rigor, such an analysis may be completed with the use of statistical procedures, supporting the conclusions drawn. In this paper, we point out that these conclusions are usually limited to the final results, whereas intermediate results are seldom considered. We propose a new methodology for comparing evolutionary algorithms' convergence capabilities, based on the use of Page's trend test. The methodology is presented with a case of use, incorporating real results from selected techniques of a recent special issue. The possible applications of the method are highlighted, particularly in those cases in which the final results do not enable a clear evaluation of the differences among several evolutionary techniques. (C) 2014 Published by Elsevier Inc.
暂无评论