利用改进的二进制狼群算法求解多维背包问题

(1. Materiel Engineering College, Armed Police Force Engineering University, Xi’an 710086, China; 2. Materiel Management and Safety Engineering College, Air Force Engineering University,  Xi’an 710051, China;3. Air Traffic Control and Navigation College, Air Force  Engineering University, Xi’an 710051, China)     

基于蚁群优化算法的0-1背包问题求解

蚁群优化算法在求解旅行商问题、指派问题、Job-shop调度问题和网络路由问题等获得了极大的成功．将蚁群优化算法应用于0—1背包问题，首先将0—1背包问题表示成相应的构造图，并针对该图设计了两个状态转移公式，蚂蚁根据这两个状态转移公式在带权图中移动直到死亡．此时，蚂蚁所走过的路径即构成背包问题的一个可行解．仿真实验对该算法的参数进行了讨论，再与遗传算法进行比较，结果显示该算法具有较高的性能．     

二进制反向学习烟花算法求解多维背包问题

为将烟花算法应用于离散优化领域并有效求解多维背包问题,构建一种二进制反向学习烟花算法。首先,通过定义二进制字符串距离、二进制转置算子将烟花算法的爆炸算子、变异算子离散化,构建二进制烟花算法;其次,设计不完全二进制反向算子并证明其收敛性,构建二进制反向学习烟花算法;最后,对10个多维背包问题典型算例进行仿真分析并与多种智能优化算法进行对比分析。仿真实验结果表明,二进制反向学习烟花算法在求解多维背包问题时具有良好的收敛效率、较高的寻优精度和很好的鲁棒性。     

求解多维0/1背包问题的二元粒子群算法

从一维细胞自动机模型入手,设计了一种求解二元离散优化问题的二元粒子群算法细胞自动机模型(BPSO-CA).粒子从起始细胞出发,根据本身携带的信息并感知存储在细胞中的全局最优粒子位置的信息随机选择状态(0或1),从而实现复杂智能的涌现.然后将其用来求解多维0/1背包问题,同时引入贪心算法对不符合约束条件的非怯个体进行修正.通过对Zuse Institute Berlin公布的测试集进行实验,表明该模型能在多项式时间内完成求解过程,且实验结果优于测试集记录的结果.     

求解大规模优化问题的改进狼群算法

针对狼群算法(wolf pack algorithm,WPA)求解大规模问题时存在解精度低、收敛速度慢和易陷入局部最优的缺点,提出了一种改进的狼群算法(improved wolf pack algorithm,IWPA).采用深度神经网络进行初始化狼群个体提高种群多样性;借助遗传算法挑选首狼提高算法寻优能力;设计距离优化因子以协同狼群算法个体的探索和开发能力;构建尺度系数改进围捕行为避免算法陷入局部最优,减少运行时间.选取18个大规模(100维,200维,500维和1000维)标准测试函数进行性能对比,结果表明,IWPA算法在求解精度和收敛速度上优于其他对比算法.     

一种求解背包问题的正态分布蚁群算法

背包问题是一类经典的NP完全问题,蚁群算法在解决此类问题时表现出良好的性能。为解决蚁群算法鲁棒性不强的问题,提出一种新颖的基于正态分布的改进蚁群算法。将物品的选择概率排序后以标准正态分布密度函数重新赋值,使其最大最小值保持在一定范围内,避免了因参数选择不当引起的选择概率过于悬殊而失去解的多样性。同时只允许成绩好于平均值的蚂蚁分泌信息素,并将每次迭代的最佳选择遗传到下一代,提高了算法的收敛性。同时还采用了一种快速的概率算法,大大提高了寻优速度。实验表明,这种改进的算法在鲁棒性能和时间性能上都明显优于现有算法。     

求解大规模多背包问题的高级人工鱼群算法

针对复杂的大规模多背包问题,提出了一种基于高级人工鱼群算法的求解方法。为了解决人工鱼群算法收敛速度慢、求解精度低的问题,所提算法通过改进其初始化方法,优化人工鱼个体的行为选择方式和追尾行为来加快问题求解的收敛速度;同时引入了动态视野及步长和人工鱼调整策略来提高算法搜索的精度。仿真实验表明:与现有的算法相比,所提算法不仅能快速收敛,而且可以达到更高的精度,尤其是对于规模越大的多背包问题算法性能提升越明显。     

改进狼群算法求解模具在模台上组合分配问题

为解决混凝土预制构件生产中存在的模具在模台上组合分配问题,提出一种BL(Bottom-Left)定位算法与改进狼群算法(Improved Wolf Pack Algorithm,IWPA)结合的方法.改进狼群算法用于优化构件的上线序,根据上线序依次将每个构件所使用的模具分配到模台上,采用BL定位算法确定模具在模台上摆放...     

双尺度变异离散粒子群算法求解背包问题

针对传统离散粒子群算法求解背包问题早熟收敛、精度低等缺点提出一种解决背包问题的双尺度变异离散粒子群算法.利用对当前最优解进行双尺度速度变异,可以实现提高算法局部最优解搜索能力的同时,保持算法的全局搜索能力和逃出局部极值的能力.在算法初期利用粗尺度速度变异可使粒子快速定位到最优解区域,算法后期则通过逐渐减小的细尺度变异可提高算法最优解的精度.粒子位置初始化过程中,把采用贫心策略所得的结果作为一个粒子的初始位置.将改进算法与其他算法比较证明该算法不仅能够有效解决其他算法搜索能力差的问题,同时还提高了最优解的精度和收敛速度.     

求解无容量设施选址问题的拉格朗日狼群算法及其应用

无容量设施选址问题(UFL)是应用于诸多领域的经典组合优化难题。首先,结合UFL问题的具体特征,重新定义了狼群算法中狼群协作捕食的智能行为,提出了求解该问题的狼群优化算法;其次,将狼群算法与拉格朗日松弛相结合,设计了一种求解UFL问题的拉格朗日狼群算法;最后,将本文提出的狼群智能优化算法及拉格朗日狼群算法用于UFL基准问题库中部分算例的求解,并将其求解结果与混合蚁群算法、半拉格朗日松弛方法以及优化软件CPLEX的求解结果进行比较。结果表明：拉格朗日狼群算法较狼群优化算法、混合蚁群算法及半拉格朗日松弛方法具有更好的求解效果,而且在一定程度上缓解了CPLEX求解时间长,消耗内存大的缺点,拥有良好的求解性能。     

基于多交换邻域搜索的多维0/1背包问题竞争决策算法

提出了一种求解多维0/1背包问题的竞争决策算法,算法采用一种新的资源交换规则——多交换的资源交换规则,使问题具有更大的邻域搜索空间,从而避免问题陷入局部最优解,同时通过对可行解的随机部分扰动进一步扩大问题的搜索空间.经过测试表明:算法具有计算时间短,求解效果好的特点.     

0-1规划问题的闭环DNA算法

提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。     

求解可分离连续凸二次背包问题的直接算法

经典算法一般采用迭代过程求解连续凸二次背包问题,研究了求解可分离连续凸二次背包问题的直接算法。分析了可分离连续凸二次背包问题的结构特性,通过两个命题和两个定理研究了可分离连续凸二次背包问题的解的特性,提出了一种快速的求解该问题的直接算法。该算法能快速有效地求解可分离连续凸二次背包问题的最优解,算法的时间复杂度和空间复杂度都是O(n),都比经典算法节约很多。     

求解折扣运输问题的遗传算法

将基于运输量提供运输费用折扣的情况推广至运输问题.对求解折扣运输问题的遗传算法进行了讨论,提出了一种生成随机可行解的方法以及两种能够保持可行性的遗传算子,并用数值例子说明了算法的有效性.     

处理动态优化问题的演化元胞遗传算法

已有演化元胞遗传算法中的演化规则多从元胞自动机中直接引入,未在状态演化中考虑个体间适应值的差异。根据密度制约关系提出一种新的演化元胞遗传算法来处理动态优化问题,在考虑个体适应值优劣与局部种群密度的前提下,通过密度制约与种内竞争实现个体在元胞空间内的生死演化,并建立种群规模增长模型控制元胞空间内存活个体规模。选取不同强度、复杂度的动态优化问题对算法性能进行验证,结果表明新算法具有良好的处理动态优化问题的能力。