求解多背包问题的混合蛙跳算法

1、【word】求解多背包问题的混合蛙跳算法求解多背包问题的混合蛙跳算法总第263期2011年第9期计算机与数字工程Computer&DigitalEngineeringVo1.39No.913求解多背包问题的混合蛙跳算法马竹根”舒少华.（怀化学院计算机科学与技术系”怀化418008）（中方县职业中等专业学校怀化418000）摘要针对多背包问题,提出一种改进的离散混合蛙跳算法.算法中对青蛙个体采用十进制整数编码方式,应用遗传算法中的交叉操作来对个体进行更新,扩展了传统混合蛙跳算法模型.将改进的算法用于多背包问题求解,仿真实验表明了所提算法的有效性.关键词混合蛙跳算法;多背包问题;组

2、合优化;交叉算子中图分类号TP301.6ShuffledFrogLeapingAlgorithmforSolvingMultipleKnapsackProblemMaZhugenShuShaohua.,Huaihu(DepartmentofComputerScienceandTechnology,HuaihuaUniversitya418008)(SpecializedSchoolofZhongfangCountryVocationalSencondarf,Huaihua418008)AbstractADiscreteShuffledFrogLeapingAlgorithmisproposed

3、tosolvetheMultipleKnapsackProblem.ThealgorithmadoptsintegercodedschemeandanewmethodofindividualproductionbycrossoveroperationtOextendthetraditionalmodelofShuffledFrogLeapingAlgorithm.Theexperimentalresultsshowthattheproposedalgorithmiseffectiveandeffient.KeyWordsshuffledfrogleapingalgorithm(SFLA),mu

4、ltipleknapsackproblem(MKP),combinatorialoptimization,crossoveroperationClassNumberTP301.61 引言多背包问题(MultipleKnapsackProblem,MKP是一个经典的组合优化问题，在现实生活中有着广泛的应用,如资源分配,投资决策,货物装载等均可建模为多背包问题.因此,多背包问题的求解一直以来是人们关注的一个研究热点,目前已经提出了如精确算法1,动态规划法2,启发式算法引,遗传算法,蚁群算法引,人工鱼群算法.等多种求解方法.由于精确求解的时间复杂度大,所以精确算法仅能适用于小规模的MKP基于生物进化

5、和仿生的遗传算法,蚁群算法,人工鱼群算法等,由于具有自组织性,鲁棒性好,易于获得全局解等特点,在求解大规模组合优化问题中应用越来越广泛.混合蛙跳算法(ShuffledFrogLeapingA1一gorithm,以下简称SFIA)是一种新型仿生群体智能优化算法,它结合了基于基因进化的模因演算法(MemeticAlgorithm,MA)和基于群体行为的粒子群算法(ParticleSwarmOptimization,PSO)两者的优hE,具有概念简单，参数少,计算速度快，全局寻优能力强,易于实现的特点,在资源分配,车间作业流程安排,旅行商问题,0-1背包问题1n等工程实际问题中得到有效的应用.文献E

6、lo和文献11都是采用二进制编码对标准的01背包问题进行求解.本文针对多维背包问题,采用十进*收稿日期:2011年3月15日,修回日期:2011年4月28日作者简介:马竹根,男,讲师,研究方向:人工智能,软件工程.马竹根等:求解多背包问题的混合蛙跳算法第39卷制整数编码方式,应用遗传算法中的交叉操作对个体进行更新,提出一种求解多维背包问题的离散混合蛙跳算法,在具体实例上的实验结果表明该算法对解决多维背包问题是行之有效的.2多背包问题数学模型多背包问题是指在一个物品集合N1,2,n中选出一个子集分别装入m个背包中，在不超出每个包的限制容量6,的条件下,使选出的全部物品的总价值最大，其中？M,M1

7、,2,，m.背包问题可形式化地描述为6:Max?CiX(1)f2aijzbiJ1,2,m(2)满足.?Nlz?0,1i1,2,(3)其中:C表示物品i的价值a表示物品i放人背包所占的容量.式(2)表示背包约束,由于具有m个约束,多背包问题又被称为多维背包问题.在多背包问题中,除了确定每个物体是否装入背包外,还需要确定它将装入哪个背包.显然对于多背包问题的优化会比背包问题复杂得多，它是一个NP一完全问题.3混合蛙跳算法混合蛙跳算法是模拟青蛙觅食过程中信息共享和交流的特点而提出的一种仿生算法.在SFLA中，种群(解集)由一群具有相同结构的青蛙组成,每只青蛙代表一个解.种群被分成多个族群,不同的族群

8、被认为是具有不同思想和行为方式的青蛙的集合,不同的族群之间能够相互影响.在每个族群内以更新最差蛙为策略,按照预先定义的局部更新迭代次数进行更新,当所有族群内最差蛙完成局部更新后,各个族群间进行思想交流实现族群间的混合,重新产生新的族群.局部搜索和混合过程一直持续到满足收敛条件或达到最大迭代次数为止.具体来说,SFLA可分成以下步骤：1)初始化种群：随机生成P只青蛙组成初始种群,第i只青蛙表示问题的解为X=(,.27,),其中s为解空间的维数,即变量的个数.2) 划分族群:将所有青蛙按照它们的适应值降序排列，然后将整个种群分成m个族群，每个族群包含n只蛙,要求满足P=mXn在迭代过程中第一只蛙分

9、人第一个族群,第二只蛙分人第二个族群,一直分配下去，直到第m只蛙分人第rn个族群.然后第十1只蛙分人第一个族群,第m+2只蛙分入第二个族群,依此类推,直到所有青蛙分配完毕.3) 族群进化:在每个族群中,用和X分别表示该族群中适应值最好和最差的青蛙,用X表示整个种群中最好的青蛙.然后对每个族群进行局部深度搜索,即对每个族群中的最差蛙按下式进行更新操作:D=rand()*(X一)(4)新的位置Xne-u2-X(当前位置)+D,(DD三三二一D)(5)式中rand()是0,l之间的随机数,D表示青蛙所允许改变位置的最大值.如果这个过程能够产生一个较好解,那么就用新位置青蛙取代最差蛙;如果没有改进,则

10、用X代替X重复执行式(4)和式(5);如果仍没有改进,则在可行域中随机产生一个新解取代原来最差青蛙X.重复这种更新操作,直到达到设定的局部搜索迭代次数.4) 混合:当所有族群的局部搜索完成后,将所有族群内的青蛙重新混合并排序,重复执行第2步和第3步直到满足终止条件,输出全局最优解.4离散混合蛙跳算法求解多背包问题在蛙跳算法中,相关参数大部分属于连续实数域,因此蛙跳算法主要适用于求解连续空间域的优化问题,难于直接处理离散的组合优化问题.在分析传统蛙跳算法优化机理的基础上,本文采用了整数编码方式和新的个体更新策略,提出一种解决多背包问题的离散蛙跳算法.4.1 蛙体结构的编码和解性能评价设计蛙跳算法首先要建立个体矢量与问题域之间的映射关系.在蛙跳算法中,一只青蛙对应所求问题的一个解.设有n个物品m个背包，将n个物品按顺序组成一向量X(z,35z,)表示青蛙个体，其中.?0,1,n,i1,2,n.=表示将第i个物品放人第m个背包,.270表示第i个物品不放入任何背包.例如,X=(2,3,1,0,0,0,2,3,3,2,0,1