کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
383270 660814 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm
ترجمه فارسی عنوان
تسخیر مشکل حلقه 0/1 با الگوریتم ژنتیکی همجنس گرا
کلمات کلیدی
0/1 مشکل حلقه الگوریتم ژنتیک؛ زوج یگانه پیوند زدن وفاداری
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی


• 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.

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Expert Systems with Applications - Volume 54, 15 July 2016, Pages 241–250
نویسندگان
, , ,