Digital library of construction informatics
and information technology in civil engineering and construction


Paper w78-2000-708:
A probabilistic search algorithm for finding optimally directed solutions

Facilitated by the SciX project

Raphael B, Smith I

A probabilistic search algorithm for finding optimally directed solutions

Abstract: "Evolutionary search techniques such as Genetic Algorithms (GA) have recently gained considerable attention. They have been used for solving a wide range of problems including function optimisation and learning. In this paper, a new global search technique, called Probabilistic Global Search (PGS), is presented. Results of benchmark tests indicate that this technique performs better than genetic algorithms on a wide range of problems. PGS is a stochastic search technique. It works by generating points in the search space according to a probability distribution function (PDF) defined over the search space. Each axis is divided into a fixed number of intervals with equal probability density. The probability densities of intervals are modified dynamically so that points are generated with higher probability in regions containing good solutions. The algorithm includes four nested cycles: 1. Sampling 2. Probability updating 3. Focusing 4. Subdomain cycle In the sampling cycle (innermost cycle) a certain number of points are generated randomly according to the current PDF. Each point is evaluated by the user defined objective function and the best point is selected. In the next cycle, probabilities of regions containing good solutions are increased and probabilities decreased in regions containing less attractive solutions. In the third cycle, search is focused on the interval containing the best solution after a number of probability updating cycles, by further subdivision of the interval. In the subdomain cycle, the search space is progressively narrowed by selecting a subdomain of smaller size centred on the best point after each focusing cycle. Each cycle serves a different purpose in the search for a global optimum. The sampling cycle permits a more uniform and exhaustive search over the entire search space than other cycles. Probability updating and focusing cycles refine search in the neighbourhood of good solutions. Convergence is achieved by means of the subdomain cycle. The algorithm was tested on highly non-linear, non-separable functions in ten to hundred variables. Results are compared with those from three versions of GAs. In most cases PGS gives better results in terms of the number of times global optima were found and the number of evaluations required to find them. The application of the technique to non-parametric optimisation problems is further illustrated using an example from conceptual structural design."



Full text: content.pdf (373,661 bytes) (available to registered users only)

Series: w78:2000 (browse)
Cluster: papers of the same cluster (result of machine made clusters)
Class: class.retrieve (0.019177) class.impact (0.015651) class.deployment (0.013039)
Similar papers:
Sound: read aloud.

Permission to reproduce these documents have been graciously provided by Icelandic Building Research Institute. The assistance of the editor, Mr. Gudni Gudnason, is gratefully appreciated


hosted by University of Ljubljana



© itc.scix.net 2003
FIRST PREVIOUS NEXT LAST Home page of this database login Powered by SciX Open Publishing Services 1.002 February 16, 2003