| 标题 | 一种求解0—1背包问题的热力学演化算法 |
| 范文 | 王轩++黄磊 摘 要：为了提高演化算法的求解性能，提出了一种新的演化算法，该算法基于热力学中的自由能极小化原理，在变异算子的设计中融入了模拟退火策略。通过利用该算法对0-1背包问题实施的数值实验，测试了其优良性能。实验结果表明，该算法是求解0-1背包问题的高效算法。 关键词：热力学演化算法；0-1背包问题；自由能极小化原理 DOIDOI：10.11907/rjdk.1511250 中图分类号：TP312 文献标识码：A 文章编号文章编号：16727800（2015）012004303 0 引言 0-1背包问题（Zeroone Knapsack Problem，ZKP）是组合优化问题中比较著名的NP完全问题之一，该问题描述为：假定一共有n个物品，从其中选择若干个物品放入背包，要求放入背包的物品重量之和小于等于b，且使所选物品的总价值尽可能最大。假设放入背包中的第i个物品的重量用wi表示，价值用ci表示（i=1，2，…，n），则ZKP可定义为如下优化问题： 解空间：S={0，1}n 解向量：x=（ x1，x2，…，xn）∈S，xi=0表示第i个物品未选中，xi=1表示第i种物品被选中。 目标：max f（x）=∑ni=1cixi 约束：∑ni=1wixi≤b 求解ZKP在工程应用中一直是被关注的焦点，解决该问题比较经典的精确求解算法[1]有动态规划、分枝定界等，近似求解算法有贪婪法[2]、桑尼算法、伊巴拉-基姆算法等。近年来越来越多研究者在求解ZKP时选择启发式方法，如蚁群优化[3]、粒子群优化以及遗传算法[4]等。本文基于热力学中的自由能极小原理，提出了一种全新的演化算法来求解ZKP。该算法因为基于热力学原理，因此命名为热力学演化算法（Thermodynamics Evolutionary Algorithms，TDEA）。 1 求解KZP的TDEA描述 1.1 解空间 ZKP的解空间表示如下：S={（ x1，x2，…，xn）|∑ni=1wixi≤b，xi取值0或1}xi=1表示物品i被选中放入背包中，xi=0则表示物品i没有被选中放入背包中。 1.2 目标与适应值 表示目标的函数f（x1，x2，…，xn）=c1x1+c2x2+...+cnxn。表示适应值的函数与表示目标的函数相同，此时个体的适应值函数值越大，表示个体的解越优。 1.3 变异算子 变异率Pm的值被设置为1，随机选取物品i，分以下两种情况讨论：①若物品i还没有放入背包中，则选择将该物品放入背包中。如果物品i在被选中放入背包中之后，此时达不到约束条件，就从背包中拿出另—件物品j，该物品是当前背包中价值与重量之比最小的物品，如果满足条件的物品不止一个，就随机选择其中之一；②若物品i已经放入背包中，则将其从背包中取出，并随机选择另一物品j装入背包，若此时不满足约束条件，则依照（1）中的办法执行。 1.4 种群熵和自由能定义 对于种群熵S的定义如下： Pij=nij2N（i=1，2，…，n，j=0，1）（1）S=∑ni=1（-∑1j=0PijlnPij）（2） 式（1）中Pij表示从种群中选择某个体时，其表示解中物品i被选择放入（用j=1表示）或者不被选择放入（用j=0表示）背包的概率；种群所有个体表示的解中，第i位分量上的值是j的数量，用nij表示；种群中的个体总数用N表示。 定义自由能E为： E=U-TS（3） 式（3）中U是种群中所有个体适应值的均值。 2 求解KZP的TDEA算法框架 将模拟退火策略融入TDEA中，系统初始温度用参数Tmax表示，凝固温度用Tmin表示，冷却率用λ表示，接收率用μ表示，停机参数用k表示[5]。 求解ZKP的TDEA框架可细化如下： void TDEA-ZKP（） { 设置初值：种群数量N，初温Tmax，凝固温度Tmin，变异率Pm，接收率μ，冷却率λ，停机参数k； T=0，T=Tmax； 随机初始化Q（t）={xt（1），xt（2），......，xt（N）}； While （不满足停机条件） { for （i=1；i<=N；i++） { 对xt（i）进行评价； x=xt（i）； //假定赋值后x=（x1，x2… xn） j=random [0，1）； 如果xj等于0，将x中xj变为1； 否则 { 随机选取k满足条件xk等于0，并将x中xk变为1； 然后将x中xj变为0； } 如果x满足约束条件，则x′←x 否则 { 对背包中物品的价值与重量之比由小到大按序排列，按照优先取出价值与重量之比最小的原则从背包中取出未被取出过的物品，并且取出后一物品的同时放回前次取出的物品，此时对应解为x′； } 对x′进行评价； 如果eval（x′）的值优于eval（xt（i），则令xt（i+N）=x′ 否则如果random [0，1） } 接下来令Q（t）′={xt（1+N），xt（2+N），......，xt（2N）}； 然后从Q （t）与Q （t）′中选取适应值最优的N/k个个体加入到Q（t+1）中； 以下过程循环k-1次 { for （j=1；j<=N；j++） { 按照前述的公式（3）计算将xt（j）加入到Q（t+1）后整个群体的自由能Ej； 对Ej按照从小到大的顺序进行排序，选择其中最小的前N/k个Ej对应的xt（j）加入到Q（t+1）； } }循环结束； T=λT，t++； 如果T } 3 数值实验 选取以下随机生成的7个测试实例作为实验对象，如表1所示。 在数值实验中各项参数的设定上，种群数量N=200，变异率Pm=1，凝固温度Tmin=0.4，冷却率λ=0.7，停机参数k=15。接受率μ定义为：对个体进行变异操作时接收变换数与提出变换数的比。初温Tmax的设定可以借鉴Aarts等[6]提出的方法：如果在确定某个T的值时产生了m个可尝试的值，其中m1是使目标函数减小的变换数，m2是使目标函数变大的变换数（m= m1+ m2），Δ+是m2次目标函数增大变换中增量的平均值，则接收率μ可以按照式（4）得到： μ=m1+m2.e（-Δ+/T）m1+m2（4） 初温Tmax可以按照式（5）得到： Tmax=Δ+lnm2m2μ-m1（1-μ）（5） 将回火退火的思想引入到停机条件的设定之中[7]，如果算法在连续迭代k次之后，每一代的最优解还是得不到显著改进，则选择停机[8]。凝固温度用参数Tmin表示，当凝固温度Tmin大于温度参数T时，如果停机条件还不能被满足，则将温度参数T重新设置为初温Tmax。 将表1中每个实例运行20次，取20次运行结果中的最优值。将TDEA的实验结果与贪心法的实验结果进行比较[9]，如表2所示。表2中显示的对比数据表明：相比于贪心法，TDEA的实验结果更优，并且运行时间也更快。 4 结语 本文基于热力学系统的视角，将种群中的个体类比为热力学系统中的单个粒子，将整个种群类比为由多个粒子组成的封闭、等压以及恒温的热力学系统。根据热力学系统在自发反应过程中遵循的自由能极小化原理，控制遗传算法中种群在每一代个体的选择和演化。 本文的创新之处在于，针对0-1背包问题的固有特性[10]设计出种群熵以及自由能的定义，根据自由能表达式H=U-TS，设计出一种选择策略。该选择策略在种群多样性和种群的选择性压力中进行了良好的均衡，同时还在变异算子的设计上，融入了模拟退火的思想，使算法能够在搜索解空间的过程中快速获取最优解。 参考文献参考文献： [1] 贺毅朝，田海燕，张新禄，等.基于动态规划法求解动态0-1背包问题[J].计算机科学，2012，39（7）：237241. [2] YVES ROBERT，ANNE BENOIT，FREDERIC VIVIEN.A guide to algorithm design：paradigms，methods，and complexity analysis[M].CRC Press Inc，2012. [3] 何小锋，马良.求解01背包问题的量子蚁群算法[J].计算机工程与应用，2011，47（16）：2931. [4] 吴迪，姜永增，宋广军.基于蜂群遗传算法的01背包问题[J].计算机工程与科学，2011，33（5）：102105. [5] 吕学勤，陈树果，林静.求解 0/1 背包问题的自适应遗传退火算法[J].重庆邮电大学学报，2013，25（1）：138142. [6] AARTS E H H，KORST J H M.Simulated annealing and Boltzmann machines[M].John Wiley and Sons，1989. [7] ZHANG YUPING，DENG ZHAORI，ZHANG RUIQI.A very fast simulated reannealing algorithm for the automotive trim industry[C].In Proceedings of the Third International Conference on Intelligent System Design and Engineering Applications.The IEEE Press，2013：209212. [8] CAMPAIGNE W R，FIEGUTH P W.Frozenstate hierarchical annealing[J].IEEE Transactions on Image Processing，2013. [9] YUXIANG SHAO，HONGWEN XU，WEIMING YIN.Solve zeroone knapsack problem by greedy genetic algorithm[C].In Proceedings of International IEEE Workshop on Intelligent Systems and Applications，2009：14. [10] SERVEDIO R A.Every linear threshold function has a lowweight approximator[C].In Proceedings of TwentyFirst Annual IEEE Conference on Computational Complexity，2006：1832. （责任编辑：黄 健） |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。