基于改进的遗传模拟退火算法解0-1背包问题

２０１４年７月下半月刊　基于改进的遗传模拟退火算法解０—１背包问题　吴菲　（兰州交通大学交通运输学院甘肃兰州７３００７０）　【摘要】本文提出了一种具有分组背包的思想的改进的模拟遗传退火算法，并将这种算法应用于０－１背包问题。利用具体的数据实验　表明，该算法优于遗传算法和模拟退火算法，从而证明了该算法的可行性和实用性。　［关键词】分组背包遗传算法模拟退火算法模拟遗传退火算法　［中图分类号】ＴＰ３０１．６［文献标识码］Ｂ【文章编号］１　００２—２５６２（２０１　４）一１　４—１　３９—２　Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｓｏｌｖｅ　０－１　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍｓ　ＷＵ　ｆｅｉ　（Ｓｃｈｏｏｌ　ｏｆ　ｔｒａｆｉｆｃ＆Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｌａｎｚｈｏｕ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ　７３００７０）　Ａｂｓｔｒａｃｔ：Ｗｉｔｈ　ｐａｃｋｅｔ　ｂａｃｋｐａｃｋ　ｉｄｅａ，ａ　ｍｏｄｉｉｆｅｄ　ｇｅｎｅｔｉｃ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｂｙ　ｔｈｉｓ　ｐａｐｅｒ，ａｎｄ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｐｐｌｉｅｄ　ｔｏ　Ｏ－１　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ．Ｕｓｉｎｇ　ｓｐｅｃｉｆｉｃ　ｄａｔａ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｕｐｅｒｉｏｒ　ｔｏ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｔｈｕｓ　ｐｒｏｖｉｎｇ　ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ａｎｄ　ｐｒａｃｔｉｃａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙｗｏｒｄｓ：Ｐａｅｋｅｔ　ｂａｃｋｐａｃｋ；Ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；Ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ；Ｇｅｎｅｔｉｃ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ．　０引言　背包问题（ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ，　）是一个经典的ⅣＰ完全问　题。　Ｐ问题有很大的理论与应用价值，主要应用于管理中的资　源分配、投资决策、装载问题的建模。遗传算法与模拟退火算　法是近几年用于优化问题的两种智能算法。遗传算法采用了生　物进化论的思想，具有较强的全局搜索性能，但其在实际应用　中容易产生早熟现象。模拟退火算法是模拟热力学中物理淬火　过程的一种学习规则，该算法能避免陷入局部最优解，从而保　证获得全局最优解的可靠性。本文将模拟退火的思想代人遗传　算法中，最后在利用分组背包的思想进行改进，不仅增强了遗　传算法的全局收敛性，而且加快了后期的收敛速度。　１背包问题描述　背包问题可以描述为：给定ｎ个物品，在每件物品的重　量、价值以及背包的最大载重已知的情况下，如何进行选择才　能使装入背包中的物品总价值最高。　Ｐ问题的一般提法为：己知　个物品的容积及价值分别为　大的个体有较大的选取概率。交叉可以使父代进行基因交换而　产生更优的个体。变异扩大了染色体选择范围的手段，得到一　些新的基因，以免过早地陷入局部最优群体的现象即为早熟　（ｐｒｅｍａｔｕｒｅ）现象。　３模拟退火算法　模拟退火算法是一种基于物理过程中，金属物体的退火过　程与组合优化问题之间进行类比。直观的解释为：在一个给定　的温度，搜索从一个状态随机地变化到另一个状态，每一个状　态到达的次数服从一个概率分布。当温度很低时，以某一概率　停留在最优解。　模拟退火算法主要分为两类：时齐算法和非时齐算法，目　前都是用时齐算法。基本框架为：在状态转移方程中对每一个　固定的　，计算对应的马尔科夫链，直到达到一个稳定状态，　然后再让温度下降…。　４遗传模拟退火算法解背包问题　４．１数据的预处理　用Ｃ　和　表示物品是价值，ｅｉ　表示物品ｆ的价值密　入背包，使得在背包最大容量限制之内，所装入的物品的总价　度，Ｍ为背包的最大载重量，蕾为物品的Ｚ决策变量，并规定其　值最大。其严格的数学描述如下：　中的Ｃ　，　和Ｍ都为正数，先做如下处理：将物品按价值密度　己知Ｃ＝（Ｃ１，Ｃ２…，Ｃｎ）　，Ｗ＝（　，ｗ２，…，　）　，　Ｃｉ　口一和ｃｆ（１≤ｆ　，ｚ），背包的最大容量限制为　，如何选择物品装　其中ｃ　，　∈Ｚ，１≤ｆ≤，ｚ，Ｍ∈Ｚ，Ｚ为正整数集，求一个　元向量　‘ｉ一　非增排序　ｌ：　ｉ　Ｘ＝（五，Ｘ２，…，　）　∈ｆ０，ｌ　使得　＿ＣＬ＞　＞…＞　，　、　ｍａｘ，【Ｘｌ，Ｘ２，…，ＸｎＪ　己ＣｉＸｉ　“．１　ｇ（ＸＤＸ２￣＂％Ｘｎ）　ＩＸｉ∈（０，１）　、－　‘ｉ＝１，２，…，　－　…　制串　ｋ＝（Ｘ１，…，Ｘｉ，…，　），变量　ｆＯ，不选择物品ｆ　以后若为特别说明，都指经过这种排序的序列。　４．２编码方式　采用二进制编码，，ｚ个项目的背包问题的解可以表示为二进　显然，Ｃ＝（Ｃ　，Ｃ，…，Ｃ　）　为　个物品的价值构成的向量，　Ｗ：ｆ　，ｗ１，…，ｗ．）　为，ｚ个物品的容积构成的向量，Ｍ为背包的最　ｉ＝｛　　ｌｌ，选择物品　（ｉ＝１，２，…，　）Ｘｉ＝１表示第　个项目被选人背　装入背包；当五＝Ｏ时，第ｆ个物品不装入背包。　为装入背包中　包问题中，（１，１，０，０，０，１，０，０，１，Ｏ）表示项目１，２，６和９被选人背　物品的总容积，而　为此时物品的总价值。　包，而其他项目则不选人背包的解。　２遗传算法（　）　４．３评价种群中个体适应度　遗传算法是将问题表示成求解“染色体”的适者生存过　背包问题有约束条件，因此在一般处理时应采用罚函数改　程，通过“染色体”群的一代代不断进化，其中包括选择、交　造目标函数得到适应度函数　】。　叉和变异等操作，最终收敛到“最适应环境”的个体，从而求　其中　为罚系数，这里取０．１；　得问题的最优解或满意解　】。　这里设置罚函数的目的是，降低适应度最小个体的适应　遗传算法通过　个算子：种群选取、交配和变异，　度，以减少它被选出的概率。　使种群不断优化，最终收敛于最优状态。种群选取是以一个　４．４选择　概率分布——轮盘赌的形式选择个体而产生的，适应度函数值　精英选择，这里所用的规则是：轮盘赌选择。染色体在种　青年科学　大容量。对于向量Ｘ＝（ｘｊ，ｘ２，…，　）　，当　＝１时，第　个物品　包；　＝０表示第　个项目不被选人背包。例如，ｌＯ个项目的背　学术研究与探讨　Ａｅａｄｅｍｉｅ　ｒｅｓｅａｒｃｈ　ａｎｄ　ｄｉｓｅｕｓｓｉｏｎ　群中被选择的可能性与其个体的适应度大小成正比。　４．５交叉　定义参数　作为交配操作的概率，这里采用固定交配概　率，由４，４中选择得到的两个个体以概率ｐ　交换各自的部分染色　体（这里使用单点杂交），得到新的两个个体。　４．６变异　定义参数Ｐ　＝０．０５作为变异操作的概率，由４．５得到每个个　体中的每个基因指都以概率ｐ　进行变异。　４．７遗传模拟退火过程　遗传模拟退火算法采用内外双层循环，外层循环采用模拟　退火算法的降温过程，内层循环采用遗传算法的解的搜索过程　［６１　ｏ　６仿真研究　按照前文所述，利用遗传算法、模拟退火算法，遗传模拟　退火算法，改进的遗传模拟退火算法分别进行测试，具体数值　如下：　Ｗｅｉｇｈｔ＝｛１７２，２４０，６６１，８８３，９８９，３５３，３４７，２５，４４１，７０，９３４，４６７，６６１，２２０，３　２９，４４０，７７４，５９５，９８，４２４，３７，８０７，３２０，５４１，３０９，８３４，８１，３４，４８９，１　１　１，２５３，１　５９，８５８，７９３，１４５，６ｌ　１，８５６，６４０，２８５，２０５，９５，３９１，１９，９１６，２３，１５２，４７３，４４８，　１】．　Ｗｏ￣ｈ＝｛６１，７５４，６９，５８７，７８９，９１２，８１９，３４７，５１１，２８７，５４１，７１４，６７６，１　９８，５７２，９１４，９８，４，３５５，５６９，１４４，２７２，５３１，５９６，１４１，４８９，３２１，８４，１９４，４３，２０　５，６０７，３９９，７４７，１１８，６５１，８０６，９，６０７，１２１，３７０，９４３，４９４，７４３，９６７，７６１，３９７，　５８９，１９３，３５１）．　Ｍ＝１４００６．　在一个种群进化周期内，即一个退火周期，设定初始退火　温度　和该　值的迭代次数，即相当于种群进化代数ｍａｘｇｅｎｓ；　在每一个退火周期内，令Ｔ：ｋ×Ｔ，其中ｋ为退火系数，这里　取０．９８。依据遗传算法得到的新种群，然后比新旧种群中各自　最大适应度个体，按模拟退火的接受概率接受或拒绝。退火过　程直到问题下降到一个预定的值或达到既定的退火周期为止。　５分组背包　得出以下结果：　表１各种算法结果比较　算法　遗传算法　模拟退火算法ｆ　＝１００　遗传模拟退火算法ｆ０＝１　００　改进的遗传模拟退火算法　最优解／重量　１３９６４　ｌ３９７８　１３９９９　ｌ４００６　最优解／价值　ｌ５８ｌｌ　ｌ５８３２　ｌ５８５４　ｌ５８６９　利用遗传模拟退火算法得出满意解，但是否是最优解还有　待考察。于是我们引进分组背包思想来进行进一步地优化。　在这里将通常的分组背包问题做了一些调整，即分组背包　问题可以描述为：有Ⅳ件物品和一个容量为　的背包。第　件　物品的费用是Ｃ　，价值是　。这些物品被划分为两组，一组全　装进包内，一组全部在包外（依据上述算法得出的满意解，被　选中的物品装入包内，其余的放在包外）。包内物品只能选一　件，包外物品至少选两件（在这里为了求解方便，包外物品取　只选两件的情况）。求解将哪些物品装入背包可使这些物品的　费用总和不超过背包容量，且价值总和最大。　这个问题变成了每组物品有若干种策略：是选择本组的哪　件或哪两件。分组的背包问题将彼此互斥的若干物品称为一　个组，这建立了一个很好的模型。不少背包问题的变形都可以　转化为分组的背包问题。　具体实现过程如下：　ｓｔｅｐｌ：取背包内物品，背包外物品　＝１；　，　Ｏ，Ｘ　＝０　　１，ｘｋ＝１　ｓｔｅｐ２：若ｃｃ　＋ｃ　，且　＞ｗｆ＋ｗｋ一＝０，则令。　’　。　一７结论　遗传模拟退火算法结合了遗传算法和模拟退火算法的优　点，即避免了陷入局部最优解，扩大了解的搜索空间，又在算　法后期加快收敛速度。本文算法中还加入了分组背包的思想，　进一步改进了遗传模拟退火算法。数值模拟实验说明，改进的　遗传模拟退火算法是求解一维０—１背包问题的有效算法，但对于　二维０—１背包的求解还有待进一步研究。　参考文献　［１］刘林忠最优化理论与智能算法［Ｍ］兰州交通大学，２００６．　［２】金慧敏，马良．遗传退火算法在背包问题中的应用［Ｊ】．上海理工大学学报，　２　００４（２６）：５６１－５６４，　［３】许小勇．基于改进的模拟退火算法求解０／１背包问题…，海南大学学报自然科　学版，版，２　００８（２６）：３５６－３５９．　［４］马良．高级运筹学［Ｍ］．北京：机械工业出版社，２００８．０６．　［５】宋海洲，魏旭真．求解Ｏ／１背包问题的混合遗传算法【Ｊ］．华侨大学学报：自然科　学版，２　００７（４）：１　６—１　９．　＝．　．，ｓｔｅｐ３：重复以上两步，直至检查完所有包内物品。　（上接第２３６页）　【６】张盛意，蔡之华，占志刚．基于改进模拟退火的遗传算法求解０—１背包问题【Ｊ］．　微电子学与计算机，２　０ｌ１（２８）：６１—６４．　导的关系。因而要实现民主政治，中国共产党在确保自己执政　地位的同时，必须在相应的宪法和法律范围内活动。　第一，提高民主协商的合法性。完善人民政协制度体系，　进一步提高人民政协会议三大职能的法律效应。实现政协能够　依法履行职能并且能够得到法律的保障。　第二，加强各党派委员参政议政的权利。政协委员来源　广，文化层次高，社会影响力较大，因此，他们是国家与人民　之间的纽带。在法律上进一步细化委员们的权利和责任，让他　们通过行驶自己的职权来为国家和人民谋利。　３．２完善政治协商的制度建设　中国共产党在努力践行依法执政、民主执政的同时，努　力创造团结与民主的有机统一，其实践的基本制度平台就是　中国人民政治协商会议。在党的领导下，以经济社会发展重大　问题和涉及群众切身利益的实际问题为内容，在全社会开展广　泛协商，并将协商贯彻于政治决策当中，推进广泛多层制度化　发展。规范协商内容、协商程序。重点推进政治协商、民主监　督、参政议政的制度化、规范化和程序化。　第一，建立协商组织形式的实效性。从现状来看，越强调　民主，决策效率越低，因此人民政协会议要拓展有实效性的分　支机构。拓展民主协商形式，活跃有序地组织各种协商形式，　以增加协商密度，提高协商成效。　第二，扩大民主政治的监督体系以防止腐败专权。建立相　关的组织机构并通过合法的渠道让民众参与到政治当中；创新　民主政治监督的新机制让政治决策透明化、政治监督民主化，　政治参与大众化。　３．３提高公民政治参与的意识　政治参与是民主的体现，在如何有效地进行政治参与是体　现我国政治协商制度是否真正民主的关键所在。首先，通过教　育提高个人的政治素质，实现人们对社会主义核心价值观的认　青年科学　同；其次，增强社会成员对中国特色社会主义政治体系的归属　感，从而激发他们作为社会政治的主要参与主体并通过政治实　践推动中国民主政治的发展；再次，良好的政治素质和相同的　政治价值有助于市民社会的形成，为民主协商创建良好的社会　环境。　４结语　执政党必须有政治宽容的视域，以政治协商制度的改革与　完善为切人点，不断增强党的凝聚力，扩大党的群众基础，承　认并容纳多元主体和社会阶层参政、议政和督政的合法性与正　当性，提高人民政协的制度化水平，从而真正体现中国社会主　义政治的包容精神与民主特质，彰显中国当下政治宽容的特点　和价值，从而推动现代民主政治的良性发展和提升。由此可　见，中国的政治协商制度改革必须立足同情走一条中国式的政　治宽容之路。　参考文献　［１］（英）安东尼・阿巴拉斯特．西方自由主义的兴衰【Ｍ］曹海军等译，吉林人民出　版社，２００４．　［２］（英）戴维・米勒出版社，２　００２　布莱克威尔政治学百科全书［Ｍ】　邓正来译，中国政法大学　［３］杨楹．宽容：现代政治的伦理内蕴［Ｊ】．哲学动态，２　００５，（１１）．　（４］金龙．政治宽容：概念的厘定［Ｊ】长春理工大学学报，２　００８，（３）．　［５］罗建平．论邓小平的政治宽容思想［Ｊ］．厦门理工学院学报，２００７，（１　２）．　［６］霍磊．政治宽容内涵探析［Ｊ】．广西大学学报，２　００９，（２）．　【７】（美）塞缪尔・Ｐ．亨廷顿．变化社会中的政治秩序ｍ】，王冠华等译，上海世纪　出版集团，２００８　［８】刘薇．中国特色的政治宽容一统一战线…．学理论，２００９，（２７）．　【９】《人民政协重要文献选编》（上），第４７页．　［１　０】代吉成．协商政治：多党合作与民主参与的实现途径［Ｊ］．求实，２　００６，（５）