514 research outputs found
Approximating the distribution of fitness over hamming regions
No full textAndrew M. Sutton, L. Darrell Whitley, Adele E. How
Mutation rates of the (1+1)-EA on pseudo-Boolean functions of bounded epistasis
No full textAndrew M. Sutton, L. Darrell Whitley, Adele E. How
The impact of global structure on search
No full textAlso published as book chapter: Parallel Problem Solving from Nature – PPSN X, 2008 / Günter Rudolph, Thomas Jansen, Simon Lucas, Carlo Poloni, Nicola Beume (eds.), pp.498-507Population-based methods are often considered superior on multimodal functions because they tend to explore more of the fitness landscape before they converge. We show that the effectiveness of this strategy is highly dependent on a function’s global structure. When the local optima are not structured in a predictable way, exploration can misguide search into sub-optimal regions. Limiting exploration can result in a better non-intuitive global search strategy.Monte Lunacek, Darrell Whitley, and Andrew Sutto
Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic
No full textThe Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them
Understanding elementary landscapes
No full textThe landscape formalism unites a finite candidate solution set to a neighborhood topology and an objective function. This construct can be used to model the behavior of local search on combinatorial optimization problems. A landscape is elementary when it possesses a unique property that results in a relative smoothness and decomposability to its structure. In this paper we explain elementary landscapes in terms of the expected value of solution components which are transformed in the process of moving from an incumbent solution to a neighboring solution. We introduce new results about the properties of elementary landscapes and discuss the practical implications for search algorithms.L. Darrell Whitley, Andrew M. Sutton, Adele E. How
10361 Abstracts Collection and Executive Summary – Theory of Evolutionary Algorithms
No full textFrom September 5 to 10, the Dagstuhl Seminar 10361 ``Theory of Evolutionary Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general
Theory of Evolutionary Algorithms (Dagstuhl Seminar 13271)
No full textThis report documents the talks and discussions of Dagstuhl Seminar 13271 "Theory of Evolutionary Algorithms". This seminar, now in its 7th edition, is the main meeting point of the highly active theory of randomized search heuristics subcommunities in Australia, Asia, North America and Europe. Topics intensively discussed include a complexity theory for randomized search heuristics, evolutionary computation in noisy settings, the drift analysis technique, and parallel evolutionary computation
Partial neighborhoods of elementary landscapes
No full textThis paper introduces a new component based model that makes it relatively simple to prove that certain types of landscapes are elementary. We use the model to reconstruct proofs for the Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning. The same model is then used to efficiently compute the average values over particular partial neighborhoods for these same problems. For Graph Coloring and Min-Cut Graph Partitioning, this computation can be used to focus search on those moves that are most likely to yield an improving move, ignoring moves that cannot yield an improving move. Let x be a candidate solution with objective function value f(x). The mean value of the objective function over the entire landscape is denoted f. Normally in an elementary landscape one can only be sure that a neighborhood includes an improving move (assuming minimization) if f(x) > f. However, by computing the expected value of an appropriate partial neighborhood it is sometimes possible to know that an improving move exists in the partial neighborhood even when f(x) < f.L. Darrell Whitley and Andrew M. Sutto
Challenges in Benchmarking Optimization Heuristics (Dagstuhl Seminar 23251)
No full textThis report documents the program and outcomes of the Dagstuhl Seminar 23251 "Challenges in Benchmarking Optimization Heuristics". In the domain of optimization heuristics, a stable basis for fairly evaluating the performance of optimization algorithms and other solution approaches - commonly referred to as "benchmarking" - is fundamental to ensuring steady scientific progress. Although many pitfalls are well known in the community, the development of sound benchmarking protocols is slow, and the adoption of community-wide recognized and implementable standards requires lasting and joint efforts among research groups. This seminar brought together people from diverse backgrounds and fostered discussions among different optimization communities, focusing on how to cope with "horse racing papers", landscape analysis techniques for understanding problem instances, and discussions about the overarching goals of benchmarking
A Polynomial time computation of the exact correlation structure of k-satisfiability landscapes
No full textThe autocorrelation function and related correlation length are statistical quantities that capture the ruggedness of the fitness landscape: a measure that is directly related to the hardness of a problem for certain heuristic search algorithms. Typically, these quantities are estimated empirically by sampling along a random walk. In this paper, we show that a polynomial-time Walsh decomposition of the k-satisfiability evaluation function allows us to compute the exact autocorrelation function and correlation length for any given k-satisfiability instance. We also use the decomposition to compute a theoretical expectation for the autocorrelation function and correlation length over the ensemble of instances generated uniformly at random. We find that this expectation is invariant to the constrainedness of the problem as measured by the ratio of clauses to variables. However, we show that filtered problems, which are typically used in local search studies, have a bias that causes a significant deviation from the expected correlation structure of unfiltered, uniformly generated problems.Andrew M. Sutton, L. Darrell Whitley and Adele E. How
- …
