Study of Chemical Reaction Based Algorithms for Knapsack Problems

摘要

背包问题在众多工业领域中都能遇到，诸如交通、物流、切割及包装、电信、可靠性、广告、投资、预算分配和生产管理。在这些应用中，背包问题一般作为独立的问题或复杂的子问题出现。
　　 从化学反应优化算法(chemical reaction optimization, CRO)中得到启发，本研究提出了两种启发式化学反应算法，并应用于0-1背包问题和多选择背包问题。首先，化学反应优化算法应用于求解0-1背包问题。在该算法中，五个特定化学反应操作算子来实现平衡强化和多元化。
　　 其次，在解决0-1背包问题的化学反应优化算法中，提出了一个贪婪的策略。第三，提出了一个新的基于化学反应优化的方法解决多选择背包问题。第四，在多选择背包问题中，提出了一个并行版本的化学反应优化算法。
　　 我们在一个大范围的数据集中使用这些新的方法进行了测试。实验结果表明，这些算法在解决背包问题等有很大的优势。
　　 论文结构:
　　 论文的结构分为六章。在第一章，介绍了0-1背包问题，并提出了多选择背包问题。同时提出了两个元启发式化学反应算法。第二章提出了一种新的具有贪婪策略的化学反应优化算法来解决0-1背包问题。一个新的集成了贪婪策略和随机选择的修复算子用于修复不可行的解方案。第三章提出了一种新的具有贪婪策略化学反应优化算法(CROG)来解决0-1背包问题。同时，还讨论了CROG算法的算子的设计和参数的选择。实现了一个新的具有贪婪策略和随机选择的修复函数用于修复不可行解的方案。第四章提出了一种新的基于元启发式的化学反应优化算法来解决多选择背包问题(MCKP)。提出新的方法，在一个MCKP的大测试集中进行测试，与遗传算法(GA)相比，显示出了更好的性能。第五章，提出了一个并行的化学反应优化算法以解决多选择背包问题， MCKP是一个著名的NP难问题。仿真结果表明，该方法在解质量的优化和计算时间两个方面均要好于CRO，同时新方法也显示出了解决这一问题的能力。第六章，总结了全文以及对未来的发展方向做了一个简单的讨论。
　　 第一章
　　 本章介绍了两种背包问题:0-1背包问题和多选择背包问题。并对这两个问题进行了文献回顾及综述。
　　 0-1背包问题:Maximize nΣi=1xipi(1) Subject to n∑i=1xiqi≤C,xi∈{0,1},(V)i∈{1,2，…，n}(2)变量xi的值为1或0，代表是选取或非选取第ith项。
　　 多选择背包问题:minimize mΣi=1niΣj=1cijxij(3)subject to m∑i=1ni∑j=1wijxij≤W(4)ni∑j=1xij=1,(V)i∈{1,2，…，m}(5)xij∈{0，1}，(V)i∈{1，2，…，m}，j∈Ni(6)所有的系数cij，wij，W都是正数，所有的N1，…，Nm均互不相交文献回顾
　　 0-1背包问题
　　 在过去的四十年里，研究人员已经提出了很多方法来解决0-1背包问题。这些方法中，我们可以分为两类:精确算法和近似算法。
　　 精确算法包括Bellman提出的[34]动态规划法和Kolesar提出的分支定界法[35]。最近，研究人员，如Kellerer等[32]，所做的工作是寻求完全解决大的背包问题的实例的方法。许多算法都涉及寻求解决背包问题的“核心”方法，然后构建部分解并获得全部的解。李等提出了一个基于共享存储器的EREW-SIMD并行算法[56]。
　　 在早期的启发式方法， Sahni首次提出了一个“多项式近似方案”来解背包问题[64]。在求解之前的一些有解质量保障的解方案，被认为是合适的解。正因为如此，随着解质量要求的提高，工作量也迅速增大。紧接着，权衡了解质量和效率之间的关系，Ibarra和Kim提出了一个完全多项式近似解决方案，以保持均衡。Martello和Toth提出了一个特殊解决方案来解背包问题，并产生了一些改变的算法[34]。
　　 近年来，许多启发式算法已被广泛应用来解决0-1背包问题:周等[30]提出了一种蚁群优化(ACO);施等[31]提出了修改参数的蚁群优化模型来适应求解0-1背包问题;李等[57]提出了基于多变异策略的二进制粒子群优化(MMBPSO)来解决背包问题;Han和Kim[63]提出了一种量子启发式进化算法(QEA)来解0-1背包问题;刘等[10]提出了一个模式引导的进化算法(SGEA)来解决0-1背包问题，邹等[44]发明了全局和谐搜索算法来解决0-1背包问题。
　　 多选择背包问题
　　 解决MCKP问题的算法也可以分为两类:精确算法和近似算法。
　　 对于精确算法，分支界限法是一种枚举的方法，通过排除不可能的解方案来减少搜索空间。在文献[4、15、17]中讨论了分支界限法算法和它的变种。在文献[3、16]中提出了动态规划算法。在文献[5、16]中提出了动态规划和分支界限法的混合型算法。
　　 因为MCKP是一个NP难问题。精确算法的时间复杂度是一个指数函数。启发式算法更有优势在多项式时间内找到近似最优解。一个著名的启发式算法是遗传算法[12]。虽然，GA首先解决了MCKP但它仍然是遇见了一个缺点，它容易陷入局部最优解。
　　 第二章0-1背包问题的化学反应优化算法
　　 本研究提出了一种新的基于贪婪策略的化学反应优化算法来解决0-1背包问题。化学反应优化(ACROA)受化学反应过程的启发来实现局部和全局搜索。本文提出了一个新的结合了贪婪策略和随机选择的修复算子，用于修复不可行的解方案。实验结果证明ACROA算法性能优越于遗传算法(GA)算法和量子启发进化算法(QEA)。
　　 尽管通过已有的研究方法，许多0-1背包问题已经圆满地解决了，但研究它们仍然是重要的，因为一些新的和更困难的0-1背包问题隐藏在现实世界中尚未解决。许多算法提供解决0-1背包问题的可能性，但他们是以牺牲效率为前提来解决，这是它们的不足。例如，最近提出解决0-1背包问题的方法，只能解决非常低维度的背包问题，但他们可能无法解决高维度的0-1背包问题。
　　 鉴于以上考虑，我们设计了一个基于ACROA和贪婪策略的算法来求解0-1背包问题。ACROA具有良好的搜索能力，展示了优秀的操作算子，其性能表现在两个重要的元启发式优化特征值:集约化和多样化。此外，它还结合了遗传算法的交叉算子和变异算子的优势。同时，本研究中，在修复算子的一个阶段采用贪婪策略，但在另一个阶段则采用一个随机方法[63]。本文中提到修复算子所采用的两个优点，首先通过使用贪婪策略使该算法具有快速收敛性，其次是通过随机搜索保证多样性[20]。
　　 第三章0-1背包问题的具有贪婪策略的化学反应优化算法
　　 0-1背包问题(KP01)是一个著名的组合优化问题。它是一个NP难问题，在计算理论和在许多现实生活中都扮演着重要的角色。化学反应优化(CRO)是一种新的优化框架，灵感来自于大自然的化学反应。CRO在解决许多工程问题上有着优良的性能，如二次分配问题、神经网络训练、多通道连续问题等。本文提出了一种新的结合贪婪策略的化学反应优化算法(CROG)来解决0-1背包问题。同时，还讨论了CROG算法的算子的设计和参数的选择。实现了一个新的具有贪婪策略和随机选择的修复函数用于修复不可行的解方案。实验结果证明CROG算法比遗传算法(GA)，蚁群优化(ACO)和量子激发了进化算法(QEA)等具有优越的性能。本章的内容发表在文献[18]。
　　 第四章多选择背包问题的化学反应优化算法
　　 本研究提出一个新的解多选择背包问题的基于元启发式化学反应优化的算法(MCKP)。MCKP是一个著名的NP难问题，在现实和理论上它有很多应用。化学反应优化(CRO)是一种模拟化学反应过程的新的优化方法。最近，在连续和离散两个领域，CRO已被证明比很多其他的方法优秀。提出的新方法，在一个大的MCKP问题测试集上实验，与遗传算法(GA)相比，显示了更好的性能。
　　 我们观察的收敛曲线的是强相关的测试集中的三个测试实例。这三个测试实例是(m=10，n=10)，(m=100，n=100)和(m=1000，n=1000)。如图4.2所示，图中显示的是在3个测试实例中运行25次的平均总成本。它表明了算法具有全局搜索能力和收敛能力。几个观察值如下:
　　 在(m=10，n=10)的情况下，如图4.2a所示，GA的收敛曲线与CRO相近，但CRO仍然好一些。在(m=100，n=100)的情况下，如图4.2b所示，CRO比GA有着更快的收敛速度。对于大的测试实例，(m=1000，n=1000)，如图4.2c所示，当GA收敛速度很慢时，CRO仍然有着较好的收敛速度。
　　 从图4.2中可知，CRO对于解大型的MCKP问题，比GA有更好的收敛速度和解质量。
　　 第五章多选择背包问题的并行化学反应优化算法
　　 提出了一个并行的化学反应优化算法来解决多选择背包问题，多选择背包问题是一个著名的NP难问题。该算法使用了四个具体的反应算子。仿真实验结果表明，该方法在解质量优化和计算时间等两个方面均要好于化学反应算法。新方法显示了对于这一难题的潜在解决能力。在未来，我们将研究基本反应算子和参数选择对PCRO算法的影响。
　　 实验环境为AMD Opteron6134处理器，主频2.3 GHz，8 GB内存，二个CPU，每个包含8个核。操作系统是Windows XP。所有的算法都用MatlabR2011b和Java语言编程，其中Java使用的JDK为1.6.0.33版本。
　　 为了对PCRO和CRO算法的计算时间进行比较，我们使用了加速比值，定义如下:Speedupk=E[T1]/E[Tk](7)其中，k代表并行结点的数量。E[Ti]， i=1,(..)(k)是PCRO算法的平均计算时间。分别对于表5.1和表5.2的实例进行仿真实验，结果表明PCRO不仅加快了运行时间，同时也提高了解的质量。
　　 CRO[2]是一个模仿化学反应过程的元启发式方法。在CRO算法中，一个分子(M)包含势能(PE)，动能(KE)，撞击数及其他特征，它代表了一种潜在的解方案。在化学反应过程中，它模拟了四种类型的化学反应包括:撞墙，分解，分子间碰撞和合成，并在化学反应过程中，势能(PE)向最低状态转换，并达到一个最佳平衡。对于优化问题，化学反应过程中的势能用于表示问题的一个次优解，势能(PE)通常作为目标函数的适应度。
　　 CRO，由于其好过许多现有的进化算法，在最近几年已经成功地解决了许多问题。CRO已经成功应用于二次分配问题[2]，资源受限项目调度问题[2]，在无线MESH网络通道分配问题[34]、在对等流中的种群过渡问题[35]，感知的无线电频谱分配问题[36]，电网调度问题[37、38]，标准连续基准函数[39]，股票投资组合的选择问题[40]，人工1神经网络训练[41]、网络编码优化[42]等许多其他问题。
　　 修复算子
　　 修复算子是基于重复性的随机选择，直到背包约束得到满足，尽管在某些情况下，这可能消耗大量的CPU时间。对于背包问题中，在文献[23]中分析了传统的贪婪策略的一些缺点。在本文中，一个新的修复算子采用了基于贪婪的策略和随机选择策略。这个修复过程的优势是平衡了CPU时间成本和不陷入局部最优解。根据价值重量比pi/qi(i=1，2，…，n)非增序排序。这意味着:pi/qi≥pj/qjfori＜j这个修复算子由两个阶段组成。第一阶段(称为ADD)，每个变量按pj/qj的降序排序，并在不违反可行性原则下变化从0到1。第二阶段(称为DROP)检查，如果违反了可行性，随机将一个变量从1变为0。DROP阶段的目的是从一个不可行解中获得一个可行的解决方案，而ADD寻求改善适应度高的可行解。修复算子的伪代码在算法8中给出。
　　 PCRO结构
　　 PCRO的流程图如图5.1所示。这个算法包括三个阶段，初始阶段，并行阶段，交换和终止阶段。在初始阶段，加载系统参数、创建初始种群。在并行阶段，化学反应算法在计算节点上执行。经过一定次数的循环后，全局最好的分子被广播，在每个节点上最坏的分子被丢弃。
　　 基本操作
　　 1)撞墙算子
　　 这个操作被ON-wall ineffective collision reaction所调用。在{1，…，m}中随机选取第i也位置，并且yi用一个在{1，…，ni}范围内的随机数代替。
　　 2)分子间碰撞
　　 通过两个w1和w2，采用两点交叉算子，获得两个新解w1'和w2'。
　　 3)分解算子
　　 通过分解操作可以从一个原始解变换出两个新解w1'和w2'。这个操作算子的作用使得算法具有多样化和使算法可以搜索解空间。分解算子的设计是受“HALF-TOTAL-EXCHANGE”算子启发，主要用于解决信道分配问题[2]。
　　 4)合成算子
　　 在本算法中，使用了合成算子[74]。这个算子的作用是将两个解w1和w2合成一个分子w1'，每一个w'(i)是随机从w1(i)和w2(i)选取的。
　　 第六章多选背包问题的人工化学反应优化算法
　　 一、简介
　　 背包问题(MCKP)是一个著名的np困难问题，它有很多应用在现实和理论。在这项研究中，一个人工化学反应优化算法(ACROA)，使用整数字符串代码来解决MCKP开发。四个具体反应算子的设计包含了局部和全局搜索。一种新的罚函数，旨在迫使算法在搜索空间可行和不可行的空间中都能搜索。这个实验表明，ACROA MCKP测试组优于遗传算法。更多的细节关于这个研究可以发现在[104]。
　　 二、目标和罚函数
　　 设x是在当前种群中的染色体，并且xij是与其相应的决策变量。在反应中，这些焓是非负的，且焓是反应过程是减少的。对于焓，设置如下:enthalpy(x)=∑mi=1∑nii=1cijxij(8)其中g(x)是焓函数，具体如下:g(x)={0if(4)is satified;Ω0+(∑mi=1∑nii=1ωijxij-W) otherwise.(9)Ω0是一个给定的正常数。思想是对于违反的解决方案将会有更大的焓。它迫使搜索算法搜索整个空间，不管是可行和不可行域。
　　 三、操作算子
　　 合成
　　 这个操作算子将从两个原始反应物合成一个反应物。为了使算法能向多元化发展，合成算子是针对这个问题重新设计的[96]。合成算子的伪代码描述见算法11。
　　 位移
　　 这个操作算子从两个原始反应物中创建两个新的反应物。两个反应物字符串的每个位置都是考虑基于随机生成的MASK信息交换，其类似于在均匀交叉遗传算法中使用MASK一样。在MASK的位置值为0时，反应物值交换，否则反应物值不变。
　　 redoX2
　　 有源的交叉是遗传算法常用的。这个操作算子体现了强化功能。
　　 分解
　　 在反应物字符串中随机选择两个点，在这两个点之间的值都进行逆转。这个算子代表了算法多元化。
　　 redox1
　　 这个操作算子实现多元化操作。一个新的反应物（解决方案）从一个原始反应物中生成出来。
　　 评估。
　　 四、实验结果
　　 所有的算法都用Matlab R2011b实现了。
　　 测试环境:在个人电脑E6700奔腾CPU在3.2 GHz CPU，2 g内存，操作系统Windows XP。
　　 我们已经考虑算法在不同问题大小，测试实例和数据范围的测试用例。我们对对于强烈相关的测试集合进行实验，观察到三个测试实例的收敛曲线。在实验中采用了这三个实例(m=10;n=10)、(m=100;n=100)、和(m=1000;n=100)。图6.2显示了对于这三个测试实例，运行25次的总成本最好的均值情况。它表明了算法具有全局搜索能力和较好的收敛能力。几个观察到的实验情况如下:在案例(m=10;n=10)，a）GA的收敛曲线与CRO相当，但CRO更好。对于(m=100;n=100)、无花果。图6.2 b）表明，与遗传算法进行比较CRO有更快速的收敛性。对于较大的实例(m=1000;n=100)、图6.2 c显示，CRO仍有很好的收敛性，而遗传算法显示了一个非常缓慢的收敛。从图6.2显示，在解决大的MCKP时，CRO比GA有更好的收敛率和解的质量。
　　 第七章结论和未来的工作
　　 背包问题在众多工业领域中都能遇到，诸如交通、物流、切割及包装、电信、可靠性、广告、投资、预算分配和生产管理。在这些应用中，背包问题一般作为独立的问题或复杂的子问题出现。
　　 从化学反应过程中得到启发，本研究提出了两种启发式化学反应算法，并应用于0-1背包问题和多选择背包问题。论文的主要贡献有四个方面:
　　 首先，化学反应优化算法应用于求解0-1背包问题。在该算法中，五个特定化学反应操作算子来实现平衡强化和多元化。
　　 其次，在解决0-1背包问题的化学反应优化算法中，提出了一个贪婪的策略。
　　 第三，提出了一个新的基于化学反应优化的方法解决多选择背包问题。
　　 最后，在多选择背包问题中，提出了一个并行版本的化学反应优化算法。我们在一个大范围的数据集中使用这些新的方法进行了测试。实验结果表明，这些算法在解决背包问题等有很大的优势。
　　 在未来，我们将进一步在以下三方面进行研究:一是将在许多不同并行平台去实现及并行化这些算法，达到让这些运行得更快的目的;二是研究如何通过设置参数来进一步提高算法效率;三是对于其他各种类型的背包问题，也考虑使用化学反应算法来进行实验和研究。

目录

声明

ABSTRACT

摘要

TABLE OF CONTENTS

LIST OF FIGURES

LIST OF TABLES

CHAPTER 1：INTRODUCTION

1．1 Background and motivation

1．2 Research objectives

1．3 0-1 knapsack problem

1．3．1 Brand-and-bound algorithms

1．4 Multiple-choice knapsack problem

1．5 Chemical reaction optimization

1．5．1 Basic reaction operators

1．5．2 Algorithm design

1．6 Artificial chemical reaction optimization algorithm

1．6．1 Chemical reactions

1．6．2 Reactants update

1．6．3 Termination criterion check

1．7 Dissertation Structure

CHAPTER 2：AN ARTIFICIAL CHEMICAL REACTION OPTIMIZATION ALGORITHM FOR 0-1 KNAPSACK PROBLEM

2．1 Introduction

2．2 Artificial chemical reaction optimization algorithm

2．2．1 Chemical reactions

2．2．2 Reactants update

2．3 Designing ACROA For KP01

2．3．1 Solution Representation

2．3．2 Objective function

2．3．3 Repair operator

2．4 Simulation Results

2．5 Summary

CHAPTER 3：CHEMICAL REACTION OPTIMIZATION WITH GREEDY STRATEGY FOR THE 0-1 KNAPSACK PROBLEM

3．1 Introduction

3．2 Related works

3．2．1 Chemical Reaction Optimization

3．2．2 Quantum-Inspired Evolutionary Algorithm

3．2．3 Ant Colony Algorithm(ACO)

3．2．4 Genetic Algorithm

3．3 Designing CROG for KP01

3．3．1 Solution Representation

3．3．2 Neighborhood Search Operator

3．3．3 Other implementation

3．4 Simulation Results

3．5 Summary

CHAPTER 4：CHEMICAL REACTION OPTIMIZATION FOR MULTIPLE-CHOICE KNAPSACK PROBLEM

4．1 1 Introduction

4．2 Genetic algorithm

4．3 Designing CRO for MCKP

4．3．1 Solution Representation

4．3．2 3．2 Objective function

4．3．3 Elementary operators

4．4 Experiment and analysis

4．4．1 Data test set

4．4．2 Parameter setting

4．4．3 Experiment results

4．5 Summary

CHAPTER 5：A PARALLEL CHEMICAL REACTION OPTIMIZATION FOR MULTIPLE-CHOICE KNAPSACK PROBLEM

5．1 1 Introduction

5．2 A basic Chemical Reaction Optimization

5．2．1 Elementary reactions

5．3 A PCRO for MCKP

5．3．1 PCRO structure

5．3．2 Solution Representation

5．3．3 Objective function

5．3．4 Elementary operators

5．4 Experiment and analysis

5．4．1 Data test set

5．4．2 Experiment results

5．5 Summary

CHAPTER 6：AN ARTIFICIAL CHEMICAL REACTION OPTIMIZATION ALGORITHM FOR MULTIPLE-CHOICE KNAPSACK PROBLEM

6．1 Introduction

6．2 Genetic algorithm for MCKP

6．3 Artificial chemical reaction optimization algorithm

6．3．1 Chemical reactions

6．3．2 Termination criterion check

6．4 Designing ACROA for MCKP

6．4．1 Solution Representation

6．4．2 Objective and penalty functions

6．4．3 Reaction operators

6．4．4 Reactants update

6．4．5 Termination criterion check

6．5 Experiment and analysis

6．5．1 Data test set

6．5．2 Parameter setting

6．5．3 Experiment results

6．6 Summary

CONCLUSIONS

REFERENCES

APPENDIX A：LIST OF PUBICATIONS

APPENDIX B：ACKNOWLEDGEMENTS