Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems (Q2505320)

Summary: We develop and test a new approach for generating initial populations for the application of genetic algorithms (GA) to problems in combinatorial optimisation, specifically the multidimensional knapsack problem. We focus the empirical study of our approach on a set of two dimensional knapsack problems (2KP) used in a past study of 2KP algorithm performance. Our proposed approach for initial population generation focuses on generating populations that are stronger in terms of solution quality, solution diversity and in terms of solutions hovering near the border of feasible and infeasible solutions within the problem solution space. We report the results of a Monte Carlo experiment comparing our approach with the traditional initial population generation approach and report the results of computational tests involving 1120 2KP instances that cover a range of problem constraint characteristics. The collective of these computational results show that our proposed approach provides an initial population of sufficient quality and diversity to produce improved convergence to near optimal solutions which can equate to reduced computational burden in applications involving complex computations.