Andrew M. Sutton

TCS Journal 2023 Journal Article

Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs

• Luke Branson
• Andrew M. Sutton

Repair operators are often used for constraint handling in constrained combinatorial optimization. We investigate the (1+1) EA equipped with a tailored jump-and-repair operation that can be used to probabilistically repair infeasible offspring in graph problems. Instead of evolving candidate solutions to the entire graph, we expand the genotype to allow the (1+1) EA to develop in parallel a feasible solution together with a growing subset of the instance (an induced subgraph). With this approach, we prove that the EA is able to probabilistically simulate an iterative compression process used in classical fixed-parameter algorithmics to obtain a randomized FPT performance guarantee on three NP -hard graph problems. For k-VertexCover, we prove that the (1+1) EA using focused jump-and-repair can find a k-vertex cover (if one exists) in O ( 2 k n 2 log ⁡ n ) iterations in expectation. This leads to an exponential (in k) improvement over the best-known parameterized bound for evolutionary algorithms on VertexCover. For the k-FeedbackVertexSet problem in tournaments, we prove that the EA finds a feasible feedback set in O ( 2 k k! n 2 log ⁡ n ) iterations in expectation, and for OddCycleTransversal, we prove the optimization time for the EA is O ( 3 k k m n 2 log ⁡ n ). For the latter two problems, this constitutes the first parameterized result for any evolutionary algorithm. We discuss how to generalize the framework to other parameterized graph problems closed under induced subgraphs and report experimental results that illustrate the behavior of the algorithm on a concrete instance class.

SAT Conference 2021 Conference Paper

Solving Non-uniform Planted and Filtered Random SAT Formulas Greedily

• Tobias Friedrich 0001
• Frank Neumann 0001
• Ralf Rothenberger
• Andrew M. Sutton

Abstract Recently, there has been an interest in studying non-uniform random k -satisfiability ( k -SAT) models in order to address the non-uniformity of formulas arising from real-world applications. While uniform random k -SAT has been extensively studied from both a theoretical and experimental perspective, understanding the algorithmic complexity of heterogeneous distributions is still an open challenge. When a sufficiently dense formula is guaranteed to be satisfiable by conditioning or a planted assignment, it is well-known that uniform random k -SAT is easy on average. We generalize this result to the broad class of non-uniform random k -SAT models that are characterized only by an ensemble of distributions over variables with a mild balancing condition. This balancing condition rules out extremely skewed distributions in which nearly half the variables occur less frequently than a small constant fraction of the most frequent variables, but generalizes recently studied non-uniform k -SAT distributions such as power-law and geometric formulas. We show that for all formulas generated from this model of at least logarithmic densities, a simple greedy algorithm can find a solution with high probability. As a side result we show that the total variation distance between planted and filtered (conditioned on satisfiability) models is o (1) once the planted model produces formulas with a unique solution with probability \(1-o(1)\). This holds for all random k -SAT models where the signs of variables are drawn uniformly and independently at random.

TCS Journal 2020 Journal Article

Theory of evolutionary computation – Special Issue Editorial

• Pietro S. Oliveto
• Andrew M. Sutton

AAAI Conference 2019 Conference Paper

Evolving Solutions to Community-Structured Satisfiability Formulas

• Frank Neumann
• Andrew M. Sutton

We study the ability of a simple mutation-only evolutionary algorithm to solve propositional satisfiability formulas with inherent community structure. We show that the community structure translates to good fitness-distance correlation properties, which implies that the objective function provides a strong signal in the search space for evolutionary algorithms to locate a satisfying assignment efficiently. We prove that when the formula clusters into communities of size s ∈ ω(log n) ∩ O(nε/(2ε+2) ) for some constant 0 < ε < 1, and there is a nonuniform distribution over communities, a simple evolutionary algorithm called the (1+1) EA finds a satisfying assignment in polynomial time on a 1 − o(1) fraction of formulas with at least constant constraint density. This is a significant improvement over recent results on uniform random formulas, on which the same algorithm has only been proven to be efficient on uniform formulas of at least logarithmic density.

TCS Journal 2015 Journal Article

Population size matters: Rigorous runtime results for maximizing the hypervolume indicator

• Anh Quang Nguyen
• Andrew M. Sutton
• Frank Neumann

Evolutionary multi-objective optimization is one of the most successful areas in the field of evolutionary computation. Using the hypervolume indicator to guide the search of evolutionary multi-objective algorithms has become very popular in recent years. We contribute to the theoretical understanding of these algorithms by carrying out rigorous runtime analyses. We consider multi-objective variants of the problems OneMax and LeadingOnes called OneMinMax and LOTZ, respectively, and investigate hypervolume-based algorithms with population sizes that do not allow coverage of the entire Pareto front. Our results show that LOTZ is easier to optimize than OneMinMax for hypervolume-based evolutionary multi-objective algorithms, which is contrary to the results on their single-objective variants and the well-studied ( 1 + 1 ) EA. Furthermore, we study multi-objective genetic programming using the hypervolume indicator. We show that the classical ORDER problem is easy to optimize if the population size is large enough to cover the whole Pareto front and point out situations where a small population size leads to an exponential optimization time.

TCS Journal 2014 Journal Article

The component model for elementary landscapes and partial neighborhoods

• Darrell Whitley
• Andrew M. Sutton
• Gabriela Ochoa
• Francisco Chicano

Local search algorithms exploit moves on an adjacency graph of the search space. An “elementary landscape” exists if the objective function f is an eigenfunction of the Laplacian of the graph induced by the neighborhood operator; this allows various statistics about the neighborhood to be computed in closed form. A new component based model makes it relatively simple to prove that certain types of landscapes are elementary. The traveling salesperson problem, weighted graph (vertex) coloring and the minimum graph bisection problem yield elementary landscapes under commonly used local search operators. The component model is then used to efficiently compute the mean objective function value over partial neighborhoods for these same problems. For a traveling salesperson problem over n cities, the 2-opt neighborhood can be decomposed into ⌊ n / 2 − 1 ⌋ partial neighborhoods. For graph coloring and the minimum graph bisection problem, partial neighborhoods can be used to focus search on those moves that are capable of producing a solution with a strictly improving objective function value.

TCS Journal 2014 Journal Article

The Max problem revisited: The importance of mutation in genetic programming

• Timo Kötzing
• Andrew M. Sutton
• Frank Neumann
• Una-May O'Reilly

We study the importance of mutation in genetic programming and contribute to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses for the well-known Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved efficiently using simple mutation-based genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutation-based genetic programming algorithms.

TCS Journal 2012 Journal Article

Computing the moments of k -bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time

• Andrew M. Sutton
• L. Darrell Whitley
• Adele E. Howe

We show that given a k -bounded pseudo-Boolean function f, one can always compute the c th moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.

SoCS Conference 2010 Conference Paper

Directed Plateau Search for MAX-k-SAT

• Andrew M. Sutton
• Adele E. Howe
• L. Darrell Whitley

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.

ICAPS Conference 2007 Conference Paper

Using Adaptive Priority Weighting to Direct Search in Probabilistic Scheduling

• Andrew M. Sutton
• Adele E. Howe
• L. Darrell Whitley

Many scheduling problems reside in uncertain and dynamic environments -- tasks have a nonzero probability of failure and may need to be rescheduled. In these cases, an optimized solution for a short-term time horizon may have a detrimental impact over a broader time scale. We examine a scheduling domain in which time and energy on a phased array radar system is allocated to track objects in orbit around the earth. This domain requires probabilistic modeling to optimize the expected number of successful tasks on a particular day. Failed tasks must be attempted again on subsequent days. Given a set of task requests, we study two long-term objectives: percentage of requests initially successful, and the average time between successful request updates. We investigate adaptive priority weighting strategies that directly influence the short-term objective function and thus indirectly influence the long-term goals. We find that adapting priority weights based on when individual tasks succeed or fail allows a catalog of requests to be filled more quickly. Furthermore, with adaptive priorities, we observe a Pareto-front effect between the two long-term objectives as we modify how priorities are weighted, but an inverse effect of weighting when the priorities are not adapted.

ICAPS Conference 2006 Conference Paper

Spacetrack: Trading off Quality and Utilization in Oversubscribed Schedules

• Andrew M. Sutton
• Adele E. Howe
• L. Darrell Whitley

Many scheduling problems are posed as optimization problems where the goal is to find a feasible schedule that maximizes the utilization of some resource. In some domains it is also necessary to consider the quality of the resulting schedule. In most research these two quantities are independent. This paper introduces a real world problem in which radar tasks must be allocated to track objects in space. We explore the trade-off between off-line task resource utilization and a measure of task quality that correlates to whether tasks are actually successfully executed. We develop two general types of algorithms that differ in the way they reason about quality and explore the trade-off between high quality solutions and solutions with high resource utilization.