Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-05T09:44:02.374Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics

Published online by Cambridge University Press:  15 February 2005

INGO WEGENER  and
CARSTEN WITT
INGO WEGENER
Affiliation:
FB Informatik, LS 2, Universität Dortmund, 44221 Dortmund, Germany (e-mail: [email protected], [email protected])
CARSTEN WITT
Affiliation:
FB Informatik, LS 2, Universität Dortmund, 44221 Dortmund, Germany (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Randomized search heuristics like evolutionary algorithms and simulated annealing find many applications, especially in situations where no full information on the problem instance is available. In order to understand how these heuristics work, it is necessary to analyse their behaviour on classes of functions. Such an analysis is performed here for the class of monotone pseudo-Boolean polynomials. Results depending on the degree and the number of terms of the polynomial are obtained. The class of monotone polynomials is of special interest since simple functions of this kind can have an image set of exponential size, improvements can increase the Hamming distance to the optimum and, in order to find a better search point, it can be necessary to search within a large plateau of search points with the same fitness value.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 14 , Issue 1-2 , January 2005 , pp. 225 - 247
Copyright
© 2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)