A Sub-population Genetic Algorithm II (SPGAII) for the Bi-criteria Knapsack Problem


The previous research shows the subpopulation Genetic Algorithm is effective in solving the multi-objective combinatorial problems. Based on the pioneer efforts, the paper extends the algorithm with a global Pareto archive technique and a two-stage approach. In the first stage, the areas next to the two single objectives are searched and solutions explored around these two extreme areas are reserved in the global archive for later evolutions. Then, in the second stage, larger searching areas except the middle area, however including the first part, are further explored to find the near-optimal frontiers. Through the extensive experimental results, SPGAII does outperform those of the SPGA, NSGAII, and SPEAII in the parallel scheduling problems and knapsack problems; it shows that the approach improves the subpopulation genetic algorithm significantly. It may be of interests for researchers in the bi-criteria knapsack problems.