Read by QxMD icon Read

Evolutionary Computation

Iwo Błądek, Krzysztof Krawiec, Jerry Swan
Conventional genetic programming (GP) can only guarantee that synthesized programs pass tests given by the provided input-output examples. The alternative to such test-based approach is synthesizing programs by formal specification, typically realized with exact, non-heuristic algorithms. In this paper, we build on our earlier study on Counterexample-Based Genetic Programming (CDGP), an evolutionary heuristic that synthesizes programs from formal specifications. The candidate programs in CDGP undergo formal verification with a Satisfiability Modulo Theory (SMT) solver, which results in counterexamples that are subsequently turned into tests and used to calculate fitness...
May 22, 2018: Evolutionary Computation
Leticia Hernando, Alexander Mendiburu, Jose A Lozano
Solving combinatorial optimization problems efficiently requires the development of algorithms that consider the specific properties of the problems. In this sense, local search algorithms are designed over a neighborhood structure that partially accounts for these properties. Considering a neighborhood, the space is usually interpreted as a natural landscape, with valleys and mountains. Under this perception, it is commonly believed that, if maximizing, the solutions located in the slopes of the same mountain belong to the same attraction basin, with the peaks of the mountains being the local optima...
May 22, 2018: Evolutionary Computation
Hisao Ishibuchi, Ryo Imada, Yu Setoguchi, Yusuke Nojima
The hypervolume indicator has frequently been used for comparing evolutionary multi-objective optimization (EMO) algorithms. A reference point is needed for hypervolume calculation. However, its specification has not been discussed in detail from a viewpoint of fair performance comparison. A slightly worse point than the nadir point is usually used for hypervolume calculation in the EMO community. In this paper, we propose a reference point specification method for fair performance comparison of EMO algorithms...
May 22, 2018: Evolutionary Computation
Edgar Covantes Osuna, Dirk Sudholt
Clearing is a niching method inspired by the principle of assigning the available resources among a niche to a single individual. The clearing procedure supplies these resources only to the best individual of each niche: the winner. So far, its analysis has been focused on experimental approaches that have shown that clearing is a powerful diversity-preserving mechanism. Using rigorous runtime analysis to explain how and why it is a powerful method, we prove that a mutation-based evolutionary algorithm with a large enough population size, and a phenotypic distance function always succeeds in optimising all functions of unitation for small niches in polynomial time, while a genotypic distance function requires exponential time...
May 10, 2018: Evolutionary Computation
William La Cava, Thomas Helmuth, Lee Spector, Jason H Moore
Lexicase selection is a parent selection method that considers training cases individually, rather than in aggregate, when performing parent selection. Whereas previous work has demonstrated the ability of lexicase selection to solve difficult problems in program synthesis and symbolic regression, the central goal of this paper is to develop the theoretical underpinnings that explain its performance. To this end, we derive an analytical formula that gives the expected probabilities of selection under lexicase selection, given a population and its behavior...
May 10, 2018: Evolutionary Computation
Yifan Li, Hai-Lin Liu, E D Goodman
For a many-objective optimization problem with redundant objectives, we propose two novel objective reduction algorithms for linearly and nonlinearly degenerate Pareto fronts. They are respectively called LHA and NLHA. The main idea of the proposed algorithms is to use a hyperplane with non-negative sparse coefficients to roughly approximate the structure of the PF. This approach is quite different from the previous objective reduction algorithms that are based on correlation or dominance structure. Especially in NLHA, in order to reduce the approximation error, we transform a nonlinearly degenerate Pareto front into a nearly linearly degenerate Pareto front via a power transformation...
May 1, 2018: Evolutionary Computation
Katherine M Malan, I Moser
The notion and characterisation of fitness landscapes has helped understand the performance of heuristic algorithms on complex optimisation problems. Many practical problems, however, are constrained, and when significant areas of the search space are infeasible, researchers have intuitively resorted to a variety of constraint-handling techniques intended to help the algorithm manoeuvre through infeasible areas and towards feasible regions of better fitness. It is clear that providing constraint-related feedback to the algorithm to influence its choice of solutions overlays the violation landscape with the fitness landscape in unpredictable ways whose effects on the algorithm cannot be directly measured...
March 12, 2018: Evolutionary Computation
Michael Fenton, David Lynch, David Fagan, Stepan Kucera, Holger Claussen, Michael O'Neill
Evolutionary Computation is used to automatically evolve small cell schedulers on a realistic simulation of a 4G-LTE heterogeneous cellular network. Evolved schedulers are then further augmented by human design to improve robustness. Extensive analysis of evolved solutions and their performance across a wide range of metrics reveals evolution has uncovered a new human-competitive scheduling technique which generalises well across cells of varying sizes. Furthermore, evolved methods are shown to conform to accepted scheduling frameworks without the evolutionary process being explicitly told the form of the desired solution...
March 12, 2018: Evolutionary Computation
José Luis Soncco-Álvarez, Daniel M Muñoz, Mauricio Ayala-Rincón
Sorting unsigned permutations by reversals is a difficult problem; indeed, it was proved to be NP-hard by Caprara (1997). Because of its high complexity, many approximation algorithms to compute the minimal reversal distance were proposed until reaching the nowadays best-known theoretical ratio of 1.375. In this article, two memetic algorithms to compute the reversal distance are proposed. The first one uses the technique of opposition-based learning leading to an opposition-based memetic algorithm; the second one improves the previous algorithm by applying the heuristic of two breakpoint elimination leading to a hybrid approach...
February 21, 2018: Evolutionary Computation
Josu Ceberio, Borja Calvo, Alexander Mendiburu, Jose A Lozano
In the last decade, many works in combinatorial optimisation have shown that, due to the advances in multi-objective optimisation, the algorithms from this field could be used for solving single-objective problems as well. In this sense, a number of papers have proposed multi-objectivising single-objective problems in order to use multi-objective algorithms in their optimisation. In this article, we follow up this idea by presenting a methodology for multi-objectivising combinatorial optimisation problems based on elementary landscape decompositions of their objective function...
February 15, 2018: Evolutionary Computation
Elena Popovici
Co-optimization problems often involve settings in which the quality ( utility) of a potential solution is dependent on the scenario within which it is evaluated, and many such scenarios exist. Maximizing expected utility is simply the goal of finding the potential solution whose expected utility value over all possible scenarios is best. Such problems are often approached using coevolutionary algorithms. We are interested in the design of generally well-performing black-box algorithms for this problem, that is, algorithms which have access to the utility function only via input-output queries...
2018: Evolutionary Computation
Krzysztof L Sadowski, Dirk Thierens, Peter A N Bosman
Learning and exploiting problem structure is one of the key challenges in optimization. This is especially important for black-box optimization (BBO) where prior structural knowledge of a problem is not available. Existing model-based Evolutionary Algorithms (EAs) are very efficient at learning structure in both the discrete, and in the continuous domain. In this article, discrete and continuous model-building mechanisms are integrated for the Mixed-Integer (MI) domain, comprising discrete and continuous variables...
2018: Evolutionary Computation
Patrik Gustavsson, Anna Syberfeldt
Non-dominated sorting is a technique often used in evolutionary algorithms to determine the quality of solutions in a population. The most common algorithm is the Fast Non-dominated Sort (FNS). This algorithm, however, has the drawback that its performance deteriorates when the population size grows. The same drawback applies also to other non-dominating sorting algorithms such as the Efficient Non-dominated Sort with Binary Strategy (ENS-BS). An algorithm suggested to overcome this drawback is the Divide-and-Conquer Non-dominated Sort (DCNS) which works well on a limited number of objectives but deteriorates when the number of objectives grows...
2018: Evolutionary Computation
Emma Hart, Kevin Sim
Although the use of ensemble methods in machine-learning is ubiquitous due to their proven ability to outperform their constituent algorithms, ensembles of optimisation algorithms have received relatively little attention. Existing approaches lag behind machine-learning in both theory and practice, with no principled design guidelines available. In this article, we address fundamental questions regarding ensemble composition in optimisation using the domain of bin-packing as an example. In particular, we investigate the trade-off between accuracy and diversity, and whether diversity metrics can be used as a proxy for constructing an ensemble, proposing a number of novel metrics for comparing algorithm diversity...
2018: Evolutionary Computation
Uday Kamath, Carlotta Domeniconi, Kenneth De Jong
Many real-world problems involve massive amounts of data. Under these circumstances learning algorithms often become prohibitively expensive, making scalability a pressing issue to be addressed. A common approach is to perform sampling to reduce the size of the dataset and enable efficient learning. Alternatively, one customizes learning algorithms to achieve scalability. In either case, the key challenge is to obtain algorithmic efficiency without compromising the quality of the results. In this article we discuss a meta-learning algorithm (PSBML) that combines concepts from spatially structured evolutionary algorithms (SSEAs) with concepts from ensemble and boosting methodologies to achieve the desired scalability property...
2018: Evolutionary Computation
Chao Qian, Yang Yu, Zhi-Hua Zhou
Many optimization tasks must be handled in noisy environments, where the exact evaluation of a solution cannot be obtained, only a noisy one. For optimization of noisy tasks, evolutionary algorithms (EAs), a type of stochastic metaheuristic search algorithm, have been widely and successfully applied. Previous work mainly focuses on the empirical study and design of EAs for optimization under noisy conditions, while the theoretical understandings are largely insufficient. In this study, we first investigate how noisy fitness can affect the running time of EAs...
2018: Evolutionary Computation
Siang Yew Chong, Peter Tiňo, Jun He, Xin Yao
Studying coevolutionary systems in the context of simplified models (i.e. games with pairwise interactions between coevolving solutions modelled as self plays) re-mains an open challenge since the rich underlying structures associated with pairwise-comparison-based fitness measures are often not taken fully into account. Although cyclic dynamics have been demonstrated in several contexts (such as intransitivity in coevolutionary problems), there is no complete characterization of cycle structures and their effects on coevolutionary search...
November 20, 2017: Evolutionary Computation
Leonardo C T Bezerra, Manuel López-Ibáñez, Thomas Stützle
Research on multi-objective evolutionary algorithms (MOEAs) has produced over the past decades a large number of algorithms and a rich literature on performance assessment tools to evaluate and compare them. Yet, newly proposed MOEAs are typically compared against very few, often a decade older MOEAs. One reason for this apparent contradiction is the lack of a common baseline for comparison, with each subsequent study often devising its own experimental scenario, slightly different from other studies. As a result, the state of the art in MOEAs is a disputed topic...
November 20, 2017: Evolutionary Computation
Jorge Pérez Heredia
There has been renewed interest in modelling the behaviour of evolutionary algorithms (EAs) by more traditional mathematical objects, such as ordinary differential equations or Markov chains. The advantage is that the analysis becomes greatly facilitated due to the existence of well established methods. However, this typically comes at the cost of disregarding information about the process. Here, we introduce the use of stochastic differential equations (SDEs) for the study of EAs. SDEs can produce simple analytical results for the dynamics of stochastic processes, unlike Markov chains which can produce rigorous but unwieldy expressions about the dynamics...
November 20, 2017: Evolutionary Computation
Pascal Kerschke, Lars Kotthoff, Jakob Bossek, Holger H Hoos, Heike Trautmann
The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers-namely, LKH, EAX, restart variants of those, and MAOS-on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP...
August 24, 2017: Evolutionary Computation
Fetch more papers »
Fetching more papers... Fetching...
Read by QxMD. Sign in or create an account to discover new knowledge that matter to you.
Remove bar
Read by QxMD icon Read

Search Tips

Use Boolean operators: AND/OR

diabetic AND foot
diabetes OR diabetic

Exclude a word using the 'minus' sign

Virchow -triad

Use Parentheses

water AND (cup OR glass)

Add an asterisk (*) at end of a word to include word stems

Neuro* will search for Neurology, Neuroscientist, Neurological, and so on

Use quotes to search for an exact phrase

"primary prevention of cancer"
(heart or cardiac or cardio*) AND arrest -"American Heart Association"