模拟谐振子算法在求解整数规划问题中的应用
本文研究整数规划问题的特性，考察模拟谐振子算法，并以此为基础解决整数规划问题。通过调整参数，并分阶段采用不同的新解生成策略，实现全局探索与局部搜索的协同。实际测试表明，该算法用于整数规划，能提升搜索速度和结果准确性。
关键词： 整数规划；模拟谐振子；全局寻优；局部寻优
整数规划属于规划论的一个分支，同时也是运筹学中的一项关键组成部分。这类规划问题在工程实践和管理活动中应用广泛，例如在资源调配、生产安排、可靠度提升、目标配置、资金规划、证券评估以及超大规模集成电路构建等方面都有实际应用。
对于变量数量不多的整数规划情形，惯用的求解途径有分支界定策略、切割平面技巧以及隐式枚举策略等。然而面对规模较大的问题，常规手段的计算过程往往极为缓慢开yun体育app入口登录，而且所得结果常常不尽如人意，例如普遍采用的处理方式是将线性规划方法得出的非整数结果进行四舍五入，但这样操作在实际应用中获取的答案或许并非原问题的有效解，或者不是整数条件下的最优解。现有的文献在借鉴传统分支定界方法的同时，开发了创新的切割和分支技术来解决问题，然而，因为其分支环节仍然依赖常规的分支定界方案，所以最终的处理速度依然会受到分支标准选择的影响。近些年，众多研究者借助遗传算法、模拟退火算法、粒子群优化算法以及蚁群优化算法等手段处理整数规划问题，获得了一定成效，不过当问题复杂程度提升时，在最终解的精确度和求解效率上仍需进一步优化。
模拟谐振子SHO算法是近期出现的全新智能方法，该算法在处理旅行商问题以及多项目调度方面展现出优越性能，不过对于其他领域的适用性仍需进一步探索和验证。这项研究用于解决整数规划课题，需要设定波动幅度、起始步距、稳定步距，以此明确新解接受标准、步距调整原则，限定各环节的最大运算次数和结果稳定次数的界限，并且在不同环节采用不同的新解生成策略，从而实现全局探索与局部探索的有效融合。实验数据证实了这种方法在处理大型的整数规划任务时，展现出卓越的探索能力与结果准确性。
1 SHO算法简介
SHO算法借鉴了自然谐振子运动的物理原理，形成了一种通用的随机寻找方法。在简谐振动模型里，弹簧上的质点从两端移动到中心位置时，其所在位置和能量状态相互关联。质点的运动是连贯不断的，因此它必然会经历系统中的所有位置情形。相应地，整个能量分布区域也会被完整探索。当把质点的位置情形看作优化问题中的某个答案情形时，理论上能够通过检查质点的位置情形来检查优化问题的答案范围，进而找到最佳答案。
算法包含三个阶段，分别是初始步骤、常规简谐振动步骤以及基态附近的量子简谐振动步骤。针对一个计算任务，算法会先在解域中多次探寻极值点和振动中心，也就是最不理想解与最佳解，从而得到系统的大致最大势能值。接着以基态间隔为界限，当间隔大于基态间隔时，进入整体优化阶段，这个阶段相当于经典振动子的运动过程。这一时期，该算法在解域中随意探寻近似最优值，同时运用取舍原则处理较差的方案，使得邻近解能在局部高峰地带来回移动，进而有效约束算法整体探索的盲目性，防止其落入局部最优的困境。当步长值小于基准步长值，就进入局部搜索环节，这类似于量子谐振子的摆动，系统整体表现为在平衡位置附近的量子式波动开yun体育官网入口登录app，算法在解域内不再发生大幅度的移动，对于偏差解，采取直接舍弃的处理方式，从而实现向最优解的逐步靠拢，算法的具体实施流程请参考相关文献资料。
SHO方法是一种通用的智能策略，在专门处理整数规划任务时，必须对算法的初始值设定、新方案生成方式以及不同方案接受标准等环节进行专门调整和明确规范。
2.1 算法参数初始化
SHO方法在起始环节必须设定振动幅度、起始间距和基本间距，明确间距调整方式，还要选定谐振器边界位置和振动源头。初始步长用来区分问题的不同能量层次，并指向每个层次能量的峰值，这个数值反映了整个能量分布区域；基态步长则表示某个较低能量的状态，其数值代表从基态到该状态之间所有能量层次的总量；每个步长对应一个能量间隔，这种间隔的变动可能是不规则的突变，也可能是逐渐减弱的过程（减弱的方式取决于具体情境）。针对当前阶段的整数规划求解，振幅需设定为某个变量的取值区间，初始步长应当是振幅的若干倍（倍数多少取决于变量的大小和取值跨度），基准步长以取正整数1最为恰当。谐振子的两个极端点以及振源的位置，可以通过多次随机求解来大致确定（计算期间，目标函数值最大的解作为端点，目标函数值最小的解作为振源）
2.2 新解产生方法
SHO算法的随机特征主要表现在新解的生成过程中。求解目标、搜索方案以及新解的搜索范围不同，导致产生新解的方式也不同。新解生成的方式对算法的运行速度和结果准确性有显著影响。产生新解的方法有多种多样，SHO算法采用的方式包括：随机均匀选取法、两点交换（两点优化）法、任意两解互换法、随机嵌入法等。处理整数规划议题时，这些创新求解途径并不管用，必须另行构思，在解的构造环节，借助随机机制生成新方案是一种普遍做法，然而追求精确结果就要付出大量运算步骤，尤其变量数量众多的情况下。在制定整数规划问题新解生成方案时，起始环节及全局探索的初步环节采用了借助随机运算构造新解的途径；当步长参数为2的情况下，研发了一种借助随机运算选定当前最优解的某个维度元素，并对其数值实施减去3、加上3、减去2、加上2的调整以形成新解的技术，这种技术有助于全局探索的后期阶段提升收敛效能并增强精确度；当步长参数为1的情况下，设计了一种借助随机运算选定当前最优解的某个维度元素，并对其数值实施减去1、加上1的调整以生成新解的技术，这种技术适用于基本状态时的局部探索过程。经过检测分析，这些新构思的解法方案，在处理整数规划任务时，显得更为适宜。
接受新解的准则指出，若新解在整个势能中所占的比重，低于近似基态能级在整体势能中的占比，或者说新解的相对势能处在近似基态能级的区间内，那么就应当采纳这个新解，即便它比当前解要差，因为在这个情况下，新解的能级确实比旧解更低，这正符合算法寻求系统基态的目标。
2.4 算法步骤
求解整数规划问题的SHO算法的步骤设计如下：
设定振幅A为某个变量取值区间的宽度，初始步长L0为振幅的若干倍，基态步长LS为1，步长调整方式为逐步缩小（借助L0实现）。另外，分别规定在明确振源和端点、步长L属于特定阶段、L等于2以及L等于1时，允许的最大迭代次数和结果不变的次数限制。
生成新解s借助随机函数，选取目标函数值f（s）最高的作为端点End，选择值最小的作为振源Init，若未达到预设的最大计算次数，或解未发生变化的次数已满，则重复步骤（2）进行操作。
该算法使用Java语言完成编码，开发环境是Eclipse IDE for Java Developers（版本号Indigo Service Release 1），执行环境是Java（TM）SE Runtime Environment（构建版本1.7.0_07-b10）。振幅值设定为21，初始步长L0是振幅的n倍数，基态步长LS等于1，步长依照L0逐渐减小进行调整。以寻得全局最优点作为收敛依据。限定最大迭代次数为10 000次，若未达此次数则判定为不收敛。确定振源和端点阶段，最大计算次数限制为200次，解无变化次数的上限设定为100次；L属于该阶段时，最大求解次数为500次，解无变化次数的上限为200次；当L等于2时，最大计算次数为500次，解无变化次数的上限同样为200次；若L等于1，则控制解无变化次数的上限为2000次。另外，需要按照参考文献的说明来计算f2（x），此时将f2（x）变量取值区间调整为-100≤xi≤100，同时把振幅A设为201，在函数维度为15、20、30的多种情形下开yunapp体育官网入口下载手机版，算法都要执行20遍，比较结果见表1。
表1里用“－”代表那种情形，算法未能完全收敛，这个指标的数据无法统计，表1表明，本文所提用于整数规划问题的SHO算法，在收敛的最优程度和收敛的快慢方面都表现出色，尤其当变量数量很多时，而且算法的稳定性强，维度和变量取值范围的变化对计算结果的影响很小。
求解变量数量众多的整数规划课题时，常规手段会耗费较多时间且容易产生偏差，部分人工智能技术虽然能提升最优结果，但在逐步逼近最优值的过程里速度偏慢。本研究以SHO算法为出发点，专门为整数规划任务改进了该算法，并且通过实践检验了其性能。实验数据对比显示，SHO方法将简单振动原理成功运用于解决复杂情形，实现了全局探寻与局部探寻的良好融合，所得结果品质优越，并且该方式耗时不多，实践层面具备可行性。
