Empirical Model with Cooperative-Competitive Genetic Operators to Improve GAs : Performance Investigation with 0/1 Multiple Knapsack Problems

概要

論文の詳細を見る
This work explores an empirical model that puts genetic operators in a cooperative-competitive stand with each other. Two parallel operators produce offspring and fulfill specific roles: Self-Reproduction with Mutation(SRM)as a permanent source of diversity to induce the appearance of beneficial mutations and Crossover and Mutation(CM)to propagate them in the population. An extinctive selection mechanism subjects CM's and SRM's offspring to compete for survival and to guarantee the preservation of beneficial mutations for the next generation. SRM is implemented with an adaptive mutation schedule, which acts depending on SRM's contribution to the actual population, and varies mutation rates from high to small values to keep control of the exploration-exploitation balance. Two adaptive mutation schemes are investigated for SRM, adaptive dynamic segment(ADS)and adaptive dynamic probability(ADP). Mutation in CM is applied with a constant small probalility. Thus, the expected cooperation between CM and SRM emerges resulting in higher search velocity and higher search reliability. The proposed model is investigated with the 0/1 multiple knapsack NP-hard combinatorial optimization problem where it outperforms a canonical genetic algorithm as well as other enhanced GAs.
一般社団法人情報処理学会の論文
2000-10-15