Landscape Analysis and Algorithm Development for Plateau Plagued Search Spaces

Abstract

Over the last 10 to 20 years, heuristic search in the Operations Research and Artificial Intelligence communities has focused on developing high level general purpose algorithms, such as Tabu Search and Genetic Algorithms. However, understanding of when and why these algorithms perform well still lags. Our project extended the theory of certain combinatorial optimization problems to develop analytical characterizations of portions of search spaces and as the basis for creating new algorithms for two well known problems. We focused attention on two specific subclasses of NP-Hard problems: elementary landscapes, which include Traveling Salesman Problem (TSP) and embedded landscapes, which include Maximum Satisfiability (MAXSAT). Our analysis supports calculating exactly the statistical moments of the distributions of values in regions of MAXSAT search spaces and explains why true plateaus are rare. Our new algorithm for TSP is competitive with the state of the art, while being much simpler and easier to understand.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 28, 2011
Accession Number
ADA547002

Entities

People

  • Adele Howe
  • L. D. Whitley

Organizations

  • Colorado State University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computations
  • Computer Science
  • Eigenvalues
  • Eigenvectors
  • Equations
  • Evolutionary Algorithms
  • Frequency
  • Genetic Algorithms
  • Mathematics
  • Numbers
  • Operations Research
  • Optimization
  • Plateaus
  • Test And Evaluation
  • Theoretical Computer Science

Readers

  • Oncology
  • Operations Research
  • Theoretical Analysis.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • Biotechnology
  • Space