Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm. (15th July 2016)

• Record Type: Journal Article
• Authors: Lim, Ting Yee; Al-Betar, Mohammed Azmi; Khader, Ahamad Tajudin
• Is Part Of: Expert systems with applications. Volume 54(2016)
• Page Start: 241
• Page End: 250
• Publication Date: 2016-07-15
• Subjects: 0/1 knapsack problem -- Genetic algorithm -- Monogamous pair -- Pair bonding -- Infidelity; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2016.01.055
• Languages: English
• ISSNs: 0957-4174

Abstract

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.