Method and system for implementing evolutionary algorithms

Abstract

A method, computer program storage medium and system that implement evolutionary algorithms on heterogeneous computers; in which a central process resident in a central computer delegates subpopulations of individuals of similar fitness from a central pool to separate processes resident on peripheral computers where they evolve for a certain number of generations after which they return to the central pool before the delegation is repeated.

Description

CLAIM OF PRIORITY[0001]This application is a national stage application of PCT / US02 / 34571, filed Oct. 28, 2002, which claims priority to U.S. Ser. No. 60 / 335,654, filed Oct. 31, 2001, the contents of all of which are incorporated herein by reference in their entirety.FIELD OF THE INVENTION[0002]The present invention relates to methods and systems for implementing evolutionary algorithms in a parallel computing environment. More particularly, the invention efficiently performs evolutionary algorithms on computers interconnected via an intranet or the internet.BACKGROUND OF THE INVENTION[0003]Evolutionary algorithms (EA) have come to represent an important paradigm for solving or approximating the solutions to combinatorial optimization problems, especially hard optimization problems, e.g., the traveling salesman's problem. See, e.g., Zbigniew Michalewicz, Genetic Algorithms &Data Structures=Evolution Programs (Springer 1999).[0004]To use the EA paradigm for a particular problem requi...

AI Technical Summary

Benefits of technology

[0023]Objects of the present invention include overcoming these problems in the prior art. Accordingly, this invention provides an efficient and effective implementation of general evolutionary algorithms (EA) as a number of communicating and cooperating processes, which is particularly suited for heterogeneous computer networks such as intranets, the Internet, or the like. Especially, this invention enables exploitation of otherwise unused computing power of networked computers for application of EAs to large, real-world optimization problems.

[0027]Advantageously, this invention limits competition between individuals of widely different fitness by distributing subpopulations selected to have relatively similar fitness to the distributed processes. Individual selection and subpopulation evolution occur only in the peripheral processes. Communication between the processes is reduced because subpopulations evolve for several generations in the peripheral processes without any intervention by the central process.

Problems solved by technology

Communication in this model is purely local, and the computational requirements on each node are limited.

But some of the most ubiquitous parallel systems available currently, intranets or the Internet, meet none of these expectations.

In particular, they have heterogeneous capabilities, have unpredictable processor availability, and have unpredictable and generally low communications bandwidth.Heterogeneous capabilities: Usually, the computers connected to these networks are of widely differing capabilities, ranging from simple PCs to powerful workstations or mainframes.Unpredictable availability: The connected computers may be otherwise used, and spare computing power available for other tasks, such as EA processing, is therefore unpredictable.Low and unpredictable bandwidth: Different computers have vastly different network connections, ranging from direct connection to backbone to a slow analog modem.

Overall, the connections are slow compared to connections within local clusters of computers.

None of the known parallelization techniques are suited to these most common examples of parallel systems.

For example, low and unpredictable communication bandwidth severely limits the use of both the farming model and the diffusion model, since these models have communication demands that require high and predictable bandwidth.

Further, subpopulations that are local according to the selected topology may reside on real processors that are a considerable distance apart, further burdening the communications connections.

On the other hand, use of the island model is also severely limited by heterogeneous and unpredictable processor capabilities.

Variable processor capabilities lead to highly uneven evolution of the separate subpopulations.

Thus, computing resources of the slower processors is effectively wasted.

Images