求解背包问题的并行混合遗传算法  

A parallel hybrid genetic algorithm of sovling knapsack problem

作　　者：张旭风[1] 王纪川[1] 牟莉[1] 

机构地区：[1]西安工程大学计算机科学学院,陕西西安710048

出　　处：《西安工程科技学院学报》2007年第1期83-87,共5页Journal of Xi an University of Engineering Science and Technology

摘　　要：针对基本遗传算法在求解大规模问题时,收敛速度缓慢、容易早熟的现象,借鉴生物区域性进化的原理,设计了一种基于星型迁移策略的并行混合遗传算法(Parallel Hybrid Genetic Algo-rithm,简称PHGA).该算法采用高效的超贪心算子进行解码,使遗传进化过程从多个平均适应度较高的文明群体开始进化,并采用定期将各群体的最优个体输出给其他群体,使得最优个体共享,促进所有群体共同进化的共产主义迁移策略.在PVM环境下,对背包问题进行求解的实验,已取得超线性的加速比,并改进了解质量.Aim at the convergence speed tardiness and premature phenomena when Simple Genetic Algorithm （SGA） sovles cosmically problem, use for reference the theory of biology territorial evolution, a Parallel Hybrid Genetic Algorithm（PHGA） which based on a star transfer tactic developed is presented. The algorithm uses an efficiency and more cupidity operator to decode, it makes genetic evolution beginning from several civilization populations which has more high average fitness. It use ＂communism＂ transfer tactic which output the best individual of population to all of other population termly, to make best individual shared, and lastly make all population together evolving. Under PVM environment, it has been proved that the algorithm has get exceed linearity speed up ratio and improved the quality of answer in experiment of settling knapsack problem.

关 键 词：遗传算法 超贪心算子 文明群体 背包问题 迁移 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]