Efficiency of adaptive genetic algorithm with mutation matrix in the solution of the knapsack problem of increasing complexity

An adaptive genetic algorithm using mutation matrix is introduced for the solution of a series of zero/one knapsack problems of increasing complexity and structure. The evolution of the population in our adaptive genetic algorithm is based on a time dependent mutation matrix that is co-evolving, guided by the locus statistics and the fitness distribution of the population. This co-evolution of the mutation matrix provides a parameter free framework for the adaptive genetic algorithm, but different implementations of the mutation matrix have different performance for the knapsack problem. Here three structures of the knapsack problems are used as the benchmark tests: simple knapsack, parallel knapsack, and hierarchical or layer knapsack. For each type of knapsack structure, an index of difficulty is constructed based on the number of items and constraints. Numerical experiments are performed to test three models of implementation of the mutation matrix corresponding to three different way of controlling the number of mutation operations used. The numerical results for the three different knapsack problems using these three different implementations are discussed, along with a heuristic explanation for their different efficiencies. The conclusion is that an adaptive mutation matrix is best, where adaptation is based on the fitness distribution of the population, so that the mutation probability is implicitly time dependent. Furthermore, a directed mutation greatly improves the performance of all three models of implementation as this involves the imitation of the best chromosome by the less fit ones.