Abstract

The genetic algorithm (GA) method for solving several complexes combinatorial optimization problems: simple plant location problem, uncapacitated network design problem and index selection problem is described. These NP-complete problems have various applications, not only in practical areas such as manufacturing, traffic, distribution planning or trading, but also in specific areas associated with computers and programming such as database design, telecommunications, local area networks, global area networks and Internet.

Sequential GA implementation contains various genetic operators of selection crossover and mutation realized on flexible way. Many variations of fitness function, GA finishing criteria and several generation replacement schemes are given too. All common GA variables are grouped into one structure, and adding the problem's depended functions is relatively easy. On this manner a fast way for solving new problems is provided.

This implementation is parallelized, and implemented on multiprocessor system, using the MPI standard (Message Passing Interface). MPI is fast and flexible practical interface for many multiprocessor architectures. For the program developing and performance testing the network of PC workstations is used. Distributed model for parallelizing GA is implemented. In this model every process executes GA on its own subpopulation with occasional exchange of good individuals between neighbor processes.

For further performance improvement of the sequential and parallel implementation a new technique, called caching GA is developed. Caching has not influence to the quality of solution, but only improve GA running time. Caching GA is a general technique, (applicable for solving many problems by genetic algorithms) giving, relatively, good results applying on NP-complete problems.

The computational results for given problems are presented to indicate that the sequential GA implementation is capable to produce high-quality solutions. In some cases this technique is superior to all known heuristic and other methods in the literature. Parallelization and implementation by MPI standard provides further improving performances. The compatible program code is obtained and could be executed on more powerful parallel platform.

Key words: Genetic Algorithms, Parallel Algorithms, NP-complete problems, Simple Plant Location Problem, Uncapacitated Network Design Problem, Index Selection Problem, Caching GA.

Back to Jozef's Home Page Some photos

Last update: 08. 03. 2000.