Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm

This paper defines and explores a somewhat different subclass of genetic algorithm (GA)-a monogamous pairs genetic algorithm (MopGA) for solving the 0/1 knapsack problems (0/1-KP). The MopGA incorporates two important operations borrowed from social monogamy: Pair bonding and infidelity at a low probability. Unlike conventional GAs, same pairs of parents (monogamous parents) are re-mated at each generation until their bonds expire. Nonetheless, this monogamy rule may be violated at the presence of infidelity. Our technique emphasizes on the thorough exploitation of the current search region via pair bonding, while allowing sufficient exploration to other unknown regions via infidelity. Consequently, MopGA is able to preserve higher population diversity by shielding offspring under the monogamous parents from population-wide selection pressure and restrictive mating strategy. As a side benefit from economical use of selection mechanism, the MopGA is computationally more efficient, especially when dealing with high-dimensionality 0/1-KPs. The empirical results on 0/1-KPs also show considerable performance in favour of the proposed methodology in terms of solution quality.