A genetic algorithm for a special class of the quadratic assignment problem. (English) Zbl 0817.90053

Pardalos, Panos M. (ed.) et al., Quadratic assignment and related problems. DIMACS Workshop, May 20-21, 1993, Rutgers Univ., New Brunswick, NJ, USA. Providence, RI: AMS. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 16, 99-116 (1994).
Summary: A special class of the quadratic assignment problem (QAP) is considered. This class of QAP describes the multiway partitioning problem which is the problem of partitioning a graph into disjoint subgraphs of prescribed sizes by removing the fewest number of edges. A genetic algorithm (GA) for solving this problem is described. A novel feature of this algorithm is the schema preprocessing phase that helps create important building blocks, which in turn improves the performance of the GA. Experimental tests on graphs with published solutions showed that the algorithm performed comparable to or better than the simulated annealing algorithm.
For the entire collection see [Zbl 0797.00027].


90B80 Discrete location and assignment
90C20 Quadratic programming
68T05 Learning and adaptive systems in artificial intelligence
90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks