ORCID Profile
0000-0003-1295-6715
Current Organisation
University of Minnesota Duluth
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: Springer Berlin Heidelberg
Date: 2015
Publisher: Elsevier BV
Date: 2015
Publisher: ACM
Date: 20-07-2016
Publisher: ACM
Date: 12-07-2014
Publisher: ACM
Date: 02-07-2018
Publisher: ACM
Date: 11-07-2015
Publisher: ACM
Date: 07-07-2012
Publisher: MIT Press
Date: 06-2015
DOI: 10.1162/EVCO_A_00130
Abstract: Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: MIT Press - Journals
Date: 11-2013
DOI: 10.1162/EVCO_A_00098
Abstract: The frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized s ling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities (called moments) that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over length-n strings from a finite alphabet of cardinality q. Many problems in combinatorial optimization can be specified as search problems over functions of this type. Employing Fourier analysis of functions over finite groups, we derive an efficient method for computing the exact moments of the frequency distribution of fitness functions over Hamming regions of the q-ary hypercube. We then use this approach to derive equations that describe the expected fitness of the offspring of any point undergoing uniform mutation. The results we present provide insight into the statistical structure of the fitness function for a number of combinatorial problems. For the graph coloring problem, we apply our results to efficiently compute the average number of constraint violations that lie within a certain number of steps of any coloring. We derive an expression for the mutation rate that maximizes the expected fitness of an offspring at each fitness level. We also apply the results to the slightly more complex frequency assignment problem, a relevant application in the domain of the telecommunications industry. As with the graph coloring problem, we provide formulas for the average value of the fitness function in Hamming regions around a solution and the expectation-optimal mutation rate.
Publisher: IEEE
Date: 06-2013
Publisher: MIT Press - Journals
Date: 06-2016
DOI: 10.1162/EVCO_A_00178
Abstract: Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses have focused on combinatorial problems such as path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo-Boolean functions under additive posterior noise. We study noise distributions whose tails decay exponentially fast, including the classical case of additive Gaussian noise. Without noise, the classical [Formula: see text] EA outperforms any ACO algorithm, with smaller [Formula: see text] being better however, in the case of large noise, the [Formula: see text] EA fails, even for high values of [Formula: see text] (which are known to help against small noise). In this article, we show that ACO is able to deal with arbitrarily large noise in a graceful manner that is, as long as the evaporation factor [Formula: see text] is small enough, dependent on the variance [Formula: see text] of the noise and the dimension n of the search space, optimization will be successful. We also briefly consider the case of prior noise and prove that ACO can also efficiently optimize linear functions under this noise model.
Publisher: ACM
Date: 07-07-2012
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: ACM
Date: 02-07-2018
Publisher: Elsevier BV
Date: 03-2012
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: IEEE
Date: 2007
Publisher: MIT Press - Journals
Date: 12-2015
DOI: 10.1162/EVCO_E_00165
Publisher: Elsevier BV
Date: 08-2014
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2016
Publisher: ACM
Date: 11-07-2015
Publisher: Springer International Publishing
Date: 2016
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2017
Publisher: ACM
Date: 12-07-2023
Publisher: Springer Science and Business Media LLC
Date: 29-08-2017
Publisher: ACM
Date: 08-07-2009
Publisher: ACM
Date: 12-01-2017
Publisher: ACM
Date: 08-07-2009
Publisher: ACM
Date: 06-07-2013
Publisher: ACM
Date: 12-07-2014
Publisher: Elsevier BV
Date: 08-2014
Publisher: ACM
Date: 07-07-2007
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: Elsevier BV
Date: 11-2016
Publisher: Springer Science and Business Media LLC
Date: 04-11-2020
Publisher: Springer International Publishing
Date: 2016
Publisher: ACM
Date: 11-07-2015
Publisher: ACM
Date: 30-08-2023
Publisher: ACM
Date: 30-08-2023
Publisher: Springer International Publishing
Date: 2016
Publisher: ACM
Date: 05-01-2011
Publisher: Elsevier BV
Date: 10-2015
Publisher: Springer Science and Business Media LLC
Date: 21-07-2015
Publisher: MIT Press - Journals
Date: 12-2014
DOI: 10.1162/EVCO_A_00119
Abstract: 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 [Formula: see text] EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time [Formula: see text] where A is a function of the minimum angle [Formula: see text] 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 [Formula: see text]. 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 [Formula: see text] 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 [Formula: see text] generations with probability [Formula: see text]. We then design a [Formula: see text] EA that 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 [Formula: see text] steps in expectation with a cost of [Formula: see text] for each fitness evaluation.
Publisher: ACM
Date: 02-07-2018
Publisher: IEEE
Date: 06-2013
Publisher: ACM
Date: 12-07-2014
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 06-2018
Publisher: ACM
Date: 20-07-2016
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: Springer International Publishing
Date: 2021
Publisher: ACM
Date: 12-07-2011
Publisher: ACM
Date: 20-07-2016
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: IEEE
Date: 09-2008
No related grants have been discovered for Andrew Sutton.