A Connectionist Machine for Genetic Hillclimbing / Edition 1

by David Ackley

Overview

In the "black box function optimization" problem, a search strategy is required to find an extremal point of a function without knowing the structure of the function or the range of possible function values. Solving such problems efficiently requires two abilities. On the one hand, a strategy must be capable of learning while searching: It must gather global information about the space and concentrate the search in the most promising regions. On the other hand, a strategy must be capable of sustained exploration: If a search of the most promising region does not uncover a satisfactory point, the strategy must redirect its efforts into other regions of the space. This dissertation describes a connectionist learning machine that produces a search strategy called shastic iterated genetic hillclimbing (SIGH). Viewed over a short period of time, SIGH displays a coarse-to-fine searching strategy, like simulated annealing and genetic algorithms. However, in SIGH the convergence process is reversible. The connectionist implementation makes it possible to diverge the search after it has converged, and to recover coarse-grained information about the space that was suppressed during convergence. The successful optimization of a complex function by SIGH usually involves a series of such converge/diverge cycles.

Product Details

ISBN-13:	9780898382365
Publisher:	Springer US
Publication date:	08/31/1987
Series:	The Springer International Series in Engineering and Computer Science , #28
Edition description:	1987
Pages:	260
Product dimensions:	6.10(w) x 9.25(h) x 0.03(d)

Table of Contents

1. Introduction.- 1.1. Satisfying hidden strong constraints.- 1.2. Function optimization.- 1.3. High-dimensional binary vector spaces.- 1.4. Dissertation overview.- 1.5. Summary.- 2. The model.- 2.1. Design goal: Learning while searching.- 2.2. Design goal: Sustained exploration.- 2.3. Connectionist computation.- 2.4. Shastic iterated genetic hillclimbing.- 2.5. Summary.- 3. Empirical demonstrations.- 3.1. Methodology.- 3.2. Seven algorithms.- 3.3. Six functions.- 4. Analytic properties.- 4.1. Problem definition.- 4.2. Energy functions.- 4.3. Basic properties of the learning algorithm.- 4.4. Convergence.- 4.5. Divergence.- 5. Graph partitioning.- 5.1. Methodology.- 5.2. Adding a linear component.- 5.3. Experiments on random graphs.- 5.4. Experiments on multilevel graphs.- 6. Related work.- 6.1. The problem space formulation.- 6.2. Search and learning.- 6.3. Connectionist modelling.- 7. Limitations and variations.- 7.1. Current limitations.- 7.2. Possible variations.- 8. Discussion and conclusions.- 8.1. Stability and change.- 8.2. Architectural goals.- 8.3. Discussion.- 8.4. Conclusions.- References.

Editorial Reviews

‘ It is a good source for those interested in a concrete application of Boltzmann machines or (at several places) thoughtful treatise on their potential impact on the broader fields of artificial intelligence and machine learning. '
B.P. Buckles, Computing Reviews, January 1989

From the Publisher