论文部分内容阅读
背包问题(Knapsack problem)是最著名的NP难问题之一，它的应用场景极为广泛，包括运输、物流、切割包装、电信、可靠性、广告、投资、预算分配和生产管理等许多工业领域。它既可以作为独立问题出现，也可以作为更复杂的编程模型的子问题出现。
同时，背包问题在信息加密、预算控制、工程选择、材料切割、货物装载、网络信息安全等方面具有重要的应用价值。从计算复杂性理论的角度来看，背包问题是一个经典的NP问题，经过半个多世纪的研究，这个问题一直是算法和复杂性研究的热点问题之一。背包问题有很多变种，研究人员从：多选择、多维度、多背包、多目标、二次和非线性目标、相关、无关、随机和模糊参数等多个方面进行了研究，其中大部分是NP难问题。
近年来研究人员已经提出了许多解决背包问题的方法。该问题的方法分为两类：精确算法和近似算法。对于精确算法，包括递归算法、动态规划法、分支定界法。对于近似算法，背包问题有许多元启发式算法，如模拟退火算法、禁忌搜索算法、遗传算法、蚁群算法、量子进化算法和蜂群算法等，元启发式算法的优点是在合理的时间内找到问题的近似最优解。
本文首先对背包问题的相关算法进行研究，包括：递归算法、动态规划法、分支定界法、图论法、启发式算法（蚂蚁算法、贪婪算法、遗传算法）。
（1）递归算法：
作为研究的基础，普通的递归算法解决了0-1背包问题。该方法本身是深度优先的穷举算法，因此不适合解决大规模问题。为了提高搜索效率，该算法采用一定的优化方法来修剪搜索树，避免了一定程度的盲搜，提高了效率。该算法首先根据单位质量的值密度对项目进行排序，然后从前到后进行探测。在运行程序的过程中，保存了当前找到的最佳解决方案。在下一次搜索中，如果当前密度小于最佳值的密度，则程序退出当前循环并返回上一循环以继续搜索。通过使用该方法，可以大大提高程序的运行速度。
（2）动态规划法
动态规划是解决多阶段决策过程优化的一种数学方法。根据一类多阶段决策问题的特点，美国数学家伯曼等人将多阶段决策问题转化为一系列相互关联的单阶段决策问题，并逐一解决，从而创建了一种动态规划方法。其特点是解决多阶段和离散问题。它使用最优性原则来建立用于计算最优解的递归公式。所谓的最优原则是，无论先前的策略是什么，后续决策必须基于先前决策在当前状态下做出的最优决策。因为某些问题的一些递归公式不一定能保证最优原理，所以在解决问题时有必要对其进行验证。如果不能保持最优原理，则不能应用动态编程方法。在获得最优解的递归公式后，有必要进行回溯以构造最优解。
（3）分支定界法
分支定界法在用于求解纯整数或混合的整数规划问题。其基本思路如下设有最大化的整数规划问题，与它相应的线性规划为问题，从求解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z?的上界，记做z；而A的任意可行解的目标函数值将是z的一个下界z。分支定界法就是将B的可行域分成子区域称为分支的方法。逐步减小z和增大
（4）图论法
图论是应用一十分广泛的运筹学分支，它己广泛的应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。
随着科学技术的发展以及电子计算机的出现与广泛应用，二十世纪五十年代，图论的理论得到进一步发展。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少，距离最短，费用最省等。图论受到数学、工程技术及经营管理等各个方面越来越广泛的重视。图论中有许多基本的概念，如边，弧，无向图，有向图，树等等，还有许多现有的方法，如破圈法、避圈法、迪杰斯特拉算法、普里姆算法和克鲁斯卡尔算法等。
（5）启发式算法
启发式算法在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受或因问题的难度使其计算时间随问题规模的增加以指数速度增加，此时只能通过启发式算法求得问题的一个可行解。
早在40年代末期，由于实际问题的需要，人们己提出一些解决实际问题的快捷有效的启发式算法。随着70年代算法复杂性理论的完善，不再强调一定要求得到最优解，因此促使年代初兴起的现代优化算法在今天得到了巨大的发展。
本论文的动机是开发基于元启发式的新启发式方法来解决背包问题，即为有效集合生成高质量的近似。将在概述中解决解决背包问题的方法，许多元启发式已经适用于解决背包问题。但是大多数方法包括许多参数，并且有时非常复杂以至于难以深入理解这些方法的行为。它使这些方法的应用难以解决背包问题，并且不一定有效。对于本论文中开发的新方法，预计会有两个特征：简单性和有效性。这些方法应该尽可能简单，以便轻松地使它们适应不同的背包问题，并且比不同背包问题的最新结果提供更好的结果。还打算通过这项工作更好地了解背包问题的有效解决方案，并介绍解决背包问题的新技术。另一个动机是将所开发的方法应用于真正的背包问题。
元启发指定一种计算方法，通过迭代尝试改进关于给定质量度量的候选解决方案来优化问题。它可以搜索候选解决方案的非常大的选项空间。元启发是一种旨在解决大范围的硬优化问题算法，而不必深入适应遗传算法、粒子群优化、蚁群算法、化学反应优化算法、BAT算法等各个问题。元启发通常应用于没有令人满意的问题特定算法来解决它们的问题。根据无自由午餐定理，所有搜索极值的元启发式在对所有可能的目标函数进行平均时的性能完全相同。因此，作者应用并检查每个特定问题的元启发式。
许多研究人员已经开发出启发式算法来解决背包问题及其变体，并且已经在不同的问题集上进行了测试，并非所有用于解决给定问题的最优性或接近最优性的算法在性能上都是等效的。这些性能差异可能是计算时间、内存要求、解决方案质量或算法的复杂性。某些启发式算法在某些类型的测试问题上优于其他启发式算法，而在其他测试问题上表现不佳。很少的研究已经研究了为什么某些算法在某些测试问题上表现良好而在其他测试问题上表现不佳。几乎没有做任何工作来获得测试问题特征及其对算法性能的影响的知识，目的是将这些性能见解推广到改进的实际问题的启发式方法。
有许多学者采用元启发方法解决KP01问题，但是确切的最优解决方案之间仍然存在差距，每种语言只在某些情况下有其优势。作者研究改进了两种元启发式算法，即粒子群算法和社会蜘蛛算法。作者采用贪婪策略来提高新算法的收敛速度。许多传递函数将原始算法中的实变量转换为二进制变量，因此它可以解决KP01问题，在大量实例上测试算法以评估效率。
尽管通过这些方法已成功解决了许多SSP，但对它们的研究仍然很重要，因为现实世界中隐藏的一些新的和更困难的SSP尚未得到解决。许多算法为某些SSP提供了可能的解决方案，但由于它们自身的缺点，它们可能会失去解决这些问题的效率。
本文的主要贡献包括如下四个方面：
首先，针对0-1背包问题（即KP01问题），提出了一种基于贪婪策略的二元粒子群优化算法。提出了一种求解实码问题的粒子群算法。为了解决类似KP01的二元代码问题，本文使用了一个传递函数将实向量转换为二元向量。将贪婪修复算子与粒子群优化算法相结合，实现了算法的快速收敛和较好的最优解。对五个最先进的基准实例和强相关数据集的仿真结果表明，该算法与以前的算法相比具有更好的性能。新方法在解决大规模实例时提供了更好的质量解决方案。
其次，由于社会蜘蛛算法在探索和开发搜索空间方面表现出良好的能力，针对0-1背包问题，本文进一步提出了一种新的二元社会蜘蛛算法(Binary Social Spider Algorithm，BSSA)。在BSSA中，采用实码向量和二元向量的混合编码方案来表示蜘蛛个体。该算法采用了Sigmoid函数将实变量转换为二元变量，两种约束处理技术在BSSA中相互配合。约束处理技术不仅可以处理冲突解，而且可以提高解的质量。对五个最先进的基准实例和强相关数据集的仿真结果表明，该算法与以前的算法相比具有更好的性能。
再次，针对子集和问题，提出了一种求解子集和问题的二元BAT算法。BAT算法具有良好的搜索能力，在优化元启发式的两个重要特征：强化和多样化方面表现出良好的操作性。子集和问题的解决方案是一个二进制代码，所以本文使用sigmoid传递函数将实码转换为二元代码。约束处理技术与二元BAT算法配合使用，二元BAT算法是一种惩罚函数，有助于算法消除坏解。对九个基准数据集的仿真结果表明，该算法与遗传算法相比具有更好的性能。新方法在解决大规模实例时提供了更好的质量解决方案。
最后，针对MCKP问题，在前面工作的基础之上，提出了一种基于元启发式的化学反应优化(Chemical Reaction Optimization，CRO)算法。MCKP问题是一个著名的NP难问题，在现实世界和理论上有着广泛的应用。化学反应优化是模拟化学反应过程的一种新的优化方法，即CRO在连续和离散领域优于许多其他方法。与传统的随机函数相比，混沌函数具有生成随机序列的优点。本文将元启发式思想与CRO算法结合，其优势是使用了四种类型的搜索算子和一个罚函数来帮助算法快速、准确地找到最优解。实验结果表明，本文提出的方法在求解MCKP问题的大型测试集上比遗传算法具有更好的性能。
同时，背包问题在信息加密、预算控制、工程选择、材料切割、货物装载、网络信息安全等方面具有重要的应用价值。从计算复杂性理论的角度来看，背包问题是一个经典的NP问题，经过半个多世纪的研究，这个问题一直是算法和复杂性研究的热点问题之一。背包问题有很多变种，研究人员从：多选择、多维度、多背包、多目标、二次和非线性目标、相关、无关、随机和模糊参数等多个方面进行了研究，其中大部分是NP难问题。
近年来研究人员已经提出了许多解决背包问题的方法。该问题的方法分为两类：精确算法和近似算法。对于精确算法，包括递归算法、动态规划法、分支定界法。对于近似算法，背包问题有许多元启发式算法，如模拟退火算法、禁忌搜索算法、遗传算法、蚁群算法、量子进化算法和蜂群算法等，元启发式算法的优点是在合理的时间内找到问题的近似最优解。
本文首先对背包问题的相关算法进行研究，包括：递归算法、动态规划法、分支定界法、图论法、启发式算法（蚂蚁算法、贪婪算法、遗传算法）。
（1）递归算法：
作为研究的基础，普通的递归算法解决了0-1背包问题。该方法本身是深度优先的穷举算法，因此不适合解决大规模问题。为了提高搜索效率，该算法采用一定的优化方法来修剪搜索树，避免了一定程度的盲搜，提高了效率。该算法首先根据单位质量的值密度对项目进行排序，然后从前到后进行探测。在运行程序的过程中，保存了当前找到的最佳解决方案。在下一次搜索中，如果当前密度小于最佳值的密度，则程序退出当前循环并返回上一循环以继续搜索。通过使用该方法，可以大大提高程序的运行速度。
（2）动态规划法
动态规划是解决多阶段决策过程优化的一种数学方法。根据一类多阶段决策问题的特点，美国数学家伯曼等人将多阶段决策问题转化为一系列相互关联的单阶段决策问题，并逐一解决，从而创建了一种动态规划方法。其特点是解决多阶段和离散问题。它使用最优性原则来建立用于计算最优解的递归公式。所谓的最优原则是，无论先前的策略是什么，后续决策必须基于先前决策在当前状态下做出的最优决策。因为某些问题的一些递归公式不一定能保证最优原理，所以在解决问题时有必要对其进行验证。如果不能保持最优原理，则不能应用动态编程方法。在获得最优解的递归公式后，有必要进行回溯以构造最优解。
（3）分支定界法
分支定界法在用于求解纯整数或混合的整数规划问题。其基本思路如下设有最大化的整数规划问题，与它相应的线性规划为问题，从求解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z?的上界，记做z；而A的任意可行解的目标函数值将是z的一个下界z。分支定界法就是将B的可行域分成子区域称为分支的方法。逐步减小z和增大
（4）图论法
图论是应用一十分广泛的运筹学分支，它己广泛的应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。
随着科学技术的发展以及电子计算机的出现与广泛应用，二十世纪五十年代，图论的理论得到进一步发展。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少，距离最短，费用最省等。图论受到数学、工程技术及经营管理等各个方面越来越广泛的重视。图论中有许多基本的概念，如边，弧，无向图，有向图，树等等，还有许多现有的方法，如破圈法、避圈法、迪杰斯特拉算法、普里姆算法和克鲁斯卡尔算法等。
（5）启发式算法
启发式算法在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受或因问题的难度使其计算时间随问题规模的增加以指数速度增加，此时只能通过启发式算法求得问题的一个可行解。
早在40年代末期，由于实际问题的需要，人们己提出一些解决实际问题的快捷有效的启发式算法。随着70年代算法复杂性理论的完善，不再强调一定要求得到最优解，因此促使年代初兴起的现代优化算法在今天得到了巨大的发展。
本论文的动机是开发基于元启发式的新启发式方法来解决背包问题，即为有效集合生成高质量的近似。将在概述中解决解决背包问题的方法，许多元启发式已经适用于解决背包问题。但是大多数方法包括许多参数，并且有时非常复杂以至于难以深入理解这些方法的行为。它使这些方法的应用难以解决背包问题，并且不一定有效。对于本论文中开发的新方法，预计会有两个特征：简单性和有效性。这些方法应该尽可能简单，以便轻松地使它们适应不同的背包问题，并且比不同背包问题的最新结果提供更好的结果。还打算通过这项工作更好地了解背包问题的有效解决方案，并介绍解决背包问题的新技术。另一个动机是将所开发的方法应用于真正的背包问题。
元启发指定一种计算方法，通过迭代尝试改进关于给定质量度量的候选解决方案来优化问题。它可以搜索候选解决方案的非常大的选项空间。元启发是一种旨在解决大范围的硬优化问题算法，而不必深入适应遗传算法、粒子群优化、蚁群算法、化学反应优化算法、BAT算法等各个问题。元启发通常应用于没有令人满意的问题特定算法来解决它们的问题。根据无自由午餐定理，所有搜索极值的元启发式在对所有可能的目标函数进行平均时的性能完全相同。因此，作者应用并检查每个特定问题的元启发式。
许多研究人员已经开发出启发式算法来解决背包问题及其变体，并且已经在不同的问题集上进行了测试，并非所有用于解决给定问题的最优性或接近最优性的算法在性能上都是等效的。这些性能差异可能是计算时间、内存要求、解决方案质量或算法的复杂性。某些启发式算法在某些类型的测试问题上优于其他启发式算法，而在其他测试问题上表现不佳。很少的研究已经研究了为什么某些算法在某些测试问题上表现良好而在其他测试问题上表现不佳。几乎没有做任何工作来获得测试问题特征及其对算法性能的影响的知识，目的是将这些性能见解推广到改进的实际问题的启发式方法。
有许多学者采用元启发方法解决KP01问题，但是确切的最优解决方案之间仍然存在差距，每种语言只在某些情况下有其优势。作者研究改进了两种元启发式算法，即粒子群算法和社会蜘蛛算法。作者采用贪婪策略来提高新算法的收敛速度。许多传递函数将原始算法中的实变量转换为二进制变量，因此它可以解决KP01问题，在大量实例上测试算法以评估效率。
尽管通过这些方法已成功解决了许多SSP，但对它们的研究仍然很重要，因为现实世界中隐藏的一些新的和更困难的SSP尚未得到解决。许多算法为某些SSP提供了可能的解决方案，但由于它们自身的缺点，它们可能会失去解决这些问题的效率。
本文的主要贡献包括如下四个方面：
首先，针对0-1背包问题（即KP01问题），提出了一种基于贪婪策略的二元粒子群优化算法。提出了一种求解实码问题的粒子群算法。为了解决类似KP01的二元代码问题，本文使用了一个传递函数将实向量转换为二元向量。将贪婪修复算子与粒子群优化算法相结合，实现了算法的快速收敛和较好的最优解。对五个最先进的基准实例和强相关数据集的仿真结果表明，该算法与以前的算法相比具有更好的性能。新方法在解决大规模实例时提供了更好的质量解决方案。
其次，由于社会蜘蛛算法在探索和开发搜索空间方面表现出良好的能力，针对0-1背包问题，本文进一步提出了一种新的二元社会蜘蛛算法(Binary Social Spider Algorithm，BSSA)。在BSSA中，采用实码向量和二元向量的混合编码方案来表示蜘蛛个体。该算法采用了Sigmoid函数将实变量转换为二元变量，两种约束处理技术在BSSA中相互配合。约束处理技术不仅可以处理冲突解，而且可以提高解的质量。对五个最先进的基准实例和强相关数据集的仿真结果表明，该算法与以前的算法相比具有更好的性能。
再次，针对子集和问题，提出了一种求解子集和问题的二元BAT算法。BAT算法具有良好的搜索能力，在优化元启发式的两个重要特征：强化和多样化方面表现出良好的操作性。子集和问题的解决方案是一个二进制代码，所以本文使用sigmoid传递函数将实码转换为二元代码。约束处理技术与二元BAT算法配合使用，二元BAT算法是一种惩罚函数，有助于算法消除坏解。对九个基准数据集的仿真结果表明，该算法与遗传算法相比具有更好的性能。新方法在解决大规模实例时提供了更好的质量解决方案。
最后，针对MCKP问题，在前面工作的基础之上，提出了一种基于元启发式的化学反应优化(Chemical Reaction Optimization，CRO)算法。MCKP问题是一个著名的NP难问题，在现实世界和理论上有着广泛的应用。化学反应优化是模拟化学反应过程的一种新的优化方法，即CRO在连续和离散领域优于许多其他方法。与传统的随机函数相比，混沌函数具有生成随机序列的优点。本文将元启发式思想与CRO算法结合，其优势是使用了四种类型的搜索算子和一个罚函数来帮助算法快速、准确地找到最优解。实验结果表明，本文提出的方法在求解MCKP问题的大型测试集上比遗传算法具有更好的性能。