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

Bui, Thang Nguyen; Moon, Byung Ro

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].

MSC:

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

Keywords:

quadratic assignment; multiway partitioning; genetic algorithm; simulated annealing