A parallel genetic algorithm for the discrete p-median problem

Genetic Algorithms (GA) operate with a population of solutions that develops according to evolutionary rules. The design of the standard genetic operations is adapted to the special peculiarities of the location-allocation problems. The mutation of a solution is implemented by replacing a location point by a close one. The crossover between solutions also takes into account the closeness of the points in the solutions. The algorithm is parallelized by splitting the population in colonies; each colony is assigned to a processor. Besides these two standard genetic operations, a migration operation is used to communicate between the processors by moving members among near colonies. Several parameters within the algorithm, and the processor network topology have to be set. The authors discuss how and why they select them. Randomly generated and real problems are used to test the algorithm. The authors report the present results with the algorithm implemented in a Parallel Virtual Machine (PVM) on a Local Area Network (LAN).