Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm. (15th July 2016) - Lim, Ting Yee; Al-Betar, Mohammed Azmi; Khader, Ahamad Tajudin
Highlights: Introduced pair bonding, inspired by social monogamy into genetic algorithm. Monogamous parent chromosomes are re-mated every generation until pair bond expires. Occasional infidelity generates variety and promotes diversity in the population. Applied the algorithm in solving 25 benchmark 0/1 knapsack problems. Convergence behavior, diversity analysis and computational effort are presented. Abstract: 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.