Open AccessA parallel genetic algorithm for the set partitioning problem
Author(s) -
D Levine
Publication year - 1996
Language(s) - English
Resource type - Reports
DOI - 10.2172/435291
Subject(s) - crew scheduling , genetic algorithm , integer (computer science) , mathematical optimization , set (abstract data type) , computation , algorithm , computer science , scheduling (production processes) , integer programming , ibm , parallel algorithm , mathematics , materials science , programming language , nanotechnology
This paper describes a parallel genetic algorithm developed for the solution of the set partitioning problem- a difficult combinatorial optimization problem used by many airlines as a mathematical model for flight crew scheduling. The genetic algorithm is based on an island model where multiple independent subpopulations each run a steady-state genetic algorithm on their own subpopulation and occasionally fit strings migrate between the subpopulations. Tests on forty real-world set partitioning problems were carried out on up to 128 nodes of an IBM SP1 parallel computer. We found that performance, as measured by the quality of the solution found and the iteration on which it was found, improved as additional subpopulations were added to the computation. With larger numbers of subpopulations the genetic algorithm was regularly able to find the optimal solution to problems having up to a few thousand integer variables. In two cases, high- quality integer feasible solutions were found for problems with 36, 699 and 43,749 integer variables, respectively. A notable limitation we found was the difficulty solving problems with many constraints