求解多维0/1背包问题的Memetic算法  

A Memetic Algorithm for Solving Multidimensional 0/1 Knapsack Problem

作　　者：刘梦佳 向凤红[1] 郭宁[1] 毛剑琳[1] 

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500

出　　处：《软件导刊》2017年第12期70-73,共4页Software Guide

基　　金：国家自然科学基金项目(61163051);云南省教育厅科学研究基金项目(2015Y071)

摘　　要：根据多维0/1背包问题的特点,结合遗传算法和模拟退火算法的优点,设计了一种Memetic算法。该算法以基于模式替换的改进遗传算法作为全局搜素算法,采用模拟退火算法进行局部搜索。全局搜索算法引入了模式替换,使每代种群中的最好基因个体保存下来形成模式,引导种群搜索方向,提高搜索性能,然后进行选择、均匀交叉和变异操作,最后采用最大化修复策略,对不可行解进行修复,并对可行解进行修正。模拟退火算法以一定概率接受较差的解,从而避免陷入局部最优解。通过实验仿真和算法比较验证了Memetic算法的优越性和有效性。According to the characteristics of multidimensional 0/1 knapsack problem and the advantages of genetic algorithm and simulated annealing algorithm,a Memetic algorithm is designed.The Memetic algorithm uses the improved genetic algorithm introduced model of replacementas the global search algorithm,and uses the simulated annealing algorithm to perform local search.The global search algorithm introduced the pattern substitution,so excellent genes from each generation population are preserved to form mode and guide the search direction of the population,which improve the search performance.After that,through selection,uniform crossover and mutation operation,the solutions are obtained.Finally the infeasible solution and the feasible solution are repaired by introduced maximum repair strategy.The simulated annealing algorithm accepted poor solutions with a certain probability,thus avoiding trapping in local optimal solutions.The superiority and effectiveness of the Memetic algorithm are verified by experimental simulation and algorithm comparison.

关 键 词：多维0/1背包 MEMETIC算法 遗传算法 模拟退火算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]