Digital library of construction informatics and information technology in civil engineering and construction
Digital library
Paper: w78-2000-708
| Paper title: | A probabilistic search algorithm for finding optimally directed solutions |
| Authors: | Raphael B, Smith I |
| Summary: | "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." |
| Type: | |
| Year of publication: | 2000 |
| Series: | w78:2000 |
| ISSN: | 2706-6568 |
| Download paper: | /pdfs/w78-2000-708.content.pdf |
| Citation: | Raphael B, Smith I (2000). A probabilistic search algorithm for finding optimally directed solutions. Construction Information Technology 2000. Taking the construction industry into the 21st century.; ISBN 9979-9174-3-1; Reykjavik, Iceland, June 28 - 30, 2000 (ISSN: 2706-6568), http://itc.scix.net/paper/w78-2000-708 |
hosted by University of Ljubljana
includes:
W78
includes:
W78
inspired by SciX, ported by Robert Klinc [2019]