Parallel Genetic Algorithms for Constrained Ordering Problems
Kay C. Wiese, Sivakumar Nagarajan, Scott D. Goodwin · 1998
This paper proposes two different parallel genetic al-gorithms (PGAs) for constrained ordering problems. Constrained ordering problems are constraint opti-mization problems (COPs) for which it is possible represent a candidate solution as a permutation of ob-jects. A decoder is used to decode this permutation into an instantiafion of the COP vm-iables. Two ex-amples of such constrmnsd ordering problems are the travel;n ~ salesman problem (TSP) and the job shop schedldin ~ problem (JSSP). The first PGA we pro-pose (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 dif-ferent selection strategy, called kesp.bemt 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 & Goodwin 1997; 1998a; 1998b). The second PGA (PGA2) is differ-ent from PGAI: while it also works with independent subpopulations, each subpopulation uses a different crossover operator. It is not a priori known which op-erator performs the best. PGA2 also uses KBR and its subpopulations exrhange 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 ~ of its fittest individuals to all other subpopulations. This will enmn ~ that for a particular problem instance the operator that works best will have an increasing num-ber of ot~pring sampled in the global population. This design also tAlt ~ 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.