An agent-oriented, massively distributed parallelization model of evolutionary algorithms
Susan E. Conry, Phaderm Nangsue · 1999
Evolutionary algorithms are adaptive search methods inspired by natural evolution. Because of their domain-independence characteristic, wide range of applications, such as numerical optimization, combinatorial optimization, and machine learning problems, have been applied. Their simplicity allows difficult problems with no obvious approach of solving to be solved. However, evolutionary algorithms have a major drawback of requiring much higher computational power than conventional techniques do. To speed up the computation of evolutionary algorithms, we propose a new parallelization model that utilizes large number of machines distributed across the Internet. Machines that are geographically close together may form a domain, which is an autonomous system that enables sharing of CPU cycles. A machine can join a domain simply by pointing its web browser to a certain URL. Domains can exchange information with one another via objects called super controllers, which hierarchically organize domains and regulate the amount of communication messages. A mobile software agent is used to travel from one domain to another, and assign a task to each domain along the way. A set of experiments was performed on thirty problems in the domain of numerical optimization, combinatorial optimization, and machine learning problems. Effects of various system parameters such as system size, migration attributes, and settings of control parameters are reported. Several problems in the test suite exhibit a superlinear speedup behavior. Moreover, the parallel efficiency increases as the number of machines increases. Some of the solutions obtained from the model have better quality than those previously published by other investigators.