Parallel Genetic Algorithms for Constrained Ordering Problems

May 1998

Proceedings of the Eleventh International Florida Artificial Intelligence Research Society Conference (FLAIRS 1998)

Volume

Proceedings of the Eleventh International Florida Artificial Intelligence Research Society Conference (FLAIRS 1998)

All Papers

This paper proposes two different parallel genetic algorithms (PGAs) for constrained ordering problems. Constrained ordering problems are constraint optimization problems (COPs) for which it is possible to represent a candidate solution as a permutation of objects. A decoder is used to decode this permutation into an instantiation of the COP variables. Two examples of such constrained ordering problems are the traveling salesman problem (TSP) and the job shop scheduling problem (JSSP). The first PGA we propose (PGA1) implements a GA using p subpopulations, where p is the number of processors. This is known as the island model. What is new is that we use a different selection strategy, called keep-best reproduction (KBR) that favours the parent with higher fitness over the child with lower fitness. Keep-best reproduction has shown better results in the sequential case than the standard selection technique (STDS) of replacing both parents by their two children (Wiese and Goodwin 1997; 1998a; 1998b). The second PGA (PGA2) is different from PGA1: while it also works with independent subpopulations, each subpopulation uses a different crossover operator. It is not a priori known which operator performs the best. PGA2 also uses KBR and its subpopulations exchange a percentage q of their fittest individuals every x generations. In addition, whenever this exchange takes place, the subpopulation with the best average fitness broadcasts a percentage q_2 of its fittest individuals to all other subpopulations. This will ensure that for a particular problem instance the operator that works best will have an increasing number of offspring sampled in the global population. This design also takes care of the fact that in the early stages of a GA run different operators can work better than in the later stages. Over time PGA2 will automatically adjust to this new situation.