增强型群论优化算法求解折扣{0-1}背包问题

群论优化算法(GTOA)是基于群论方法提出的一个离散演化算法,非常适于求解以整型向量为可行解的组合优化问题。为了进一步提高GTOA求解折扣{0-1}背包问题(D{0-1}KP)的性能,首先指出了它的随机线性组合算子(RLCO)未能充分考虑当前个体位置信息的不足,基于个体基因保留策略对其进行改进。然后,在随机反向变异算子(IRMO)中引入增强0分量变异策略,用于处理因个体0分量无法及时变异而导致的解的质量下降、种群多样性降低等问题。在改进上述两个算子的基础上,提出了增强型GTOA(EGTOA),并基于它给出求解D{0-1}KP的新方法。随后,将改进策略应用于二进制GTOA(GTOA-2),提出了增强型GTOA-2(EGTOA-2)及其求解D{0-1}KP的新方法。为了验证EGTOA和EGTOA-2的性能提高程度与优异性,分别利用它们求解四类大规模D{0-1}KP实例,通过与GTOA、GTOA-2以及求解D{0-1}KP的已有8个最先进算法的比较表明:EGTOA和EGTOA-2求得最优解的能力比GTOA和GTOA-2提高了至少1.14倍,比8个最先进算法提高了5%~60%,它们的平均性能比GTOA、GTOA-2以及8个最先进算法的性能更佳。因此,EGTOA和EGTOA-2是当前求解D{0-1}KP的最佳算法。

求解随机时变背包问题的确定性算法

随机时变背包问题(RTVKP)是智能计算领域中的一个动态组合优化问题,具有重要的理论与应用价值.对于背包载重随机变化的RTVKP问题(记为RTVKP3),首先利用改进的动态规划法提出了一种适于求解具有较小物品价值和较大背包载重的RTVKP3的确定性算法(记为MDP-RTVKP),给出了MDP-RTVKP可成功求解RTVKP3的必要条件;然后,基于MDPRTVKP和DPforRTVKP的不同适用性提出了一种适于求解任意RTVKP3实例的有效方法 GenericDPfRTVKP,并通过对大规模RTVKP3实例的仿真计算验证了GenericDPfRTVKP的通用性与高效性.

一种求解多背包问题的改进的人工鱼群算法

多背包问题是优化领域中典型的NP难题,传统算法由于计算复杂性高或收敛速度慢等缺点,结果往往不能令人满意。针对上述问题提出了一种求解多背包问题的改进的人工鱼群算法(IAF-SA)。首先将多背包放入方式整数编码,其次对不可行人工鱼编码、不充分人工鱼编码采用"随机修复"策略进行修复,并对人工鱼群算法(AFSA)中觅食、聚群和追尾等行为和产生的人工鱼编码进行改进和修复,最后结合实验对IAFSA算法分析和检验。实验结果表明,求解多背包问题的IAFSA算法相对其它算法不仅具有更快收敛速度和更强鲁棒性,而且以较大的概率收敛于原问题的最优解。

求解0-1背包问题的改进混合遗传算法

针对一种混合遗传算法所采用的贪心变换法的不足,给出了一种改进的贪心修正法;并基于稳态复制的策略,对遗传算法的选择操作进行改进,给出了随机选择操作.在此基础上,提出了一种改进的混合遗传算法,并将新算法用于解决大规模的0-1背包问题,通过实例将新算法与HGA算法进行实验对比分析,并研究了变异概率对新算法性能的影响.实验结果表明新算法收敛速度快,寻优能力强.

求解0-1背包问题的量子狼群算法

针对0-1背包问题,在基本狼群算法的基础上,提出了量子狼群算法.借鉴量子编码方式,定义了种群中粒子的概率位置和准确位置,通过量子旋转门控制人工狼概率位置向全局最好位置逼近,然后以量子塌缩实现了概率位置向准确位置的映射,兼顾了算法的导向性与随机性.选取了8个经典0-1背包问题与3个高维背包问题进行了测试,并与其他算法进行比较,实验结果表明,量子狼群算法能够有效搜索全局最优解,特别是在高维背包问题中具有较好性能.

求解0-1背包问题的改进离散和声搜索算法

提出一种求解0-1背包问题的改进离散和声搜索算法(IDHS).该算法应用分布估计算法的概率思想,设计自适应调整策略,提高算法的搜索能力.引入精英培养机制,加强精英和声的开发,提高算法逃离局部最优的概率.通过随机修复方法和置换策略来改善和声的可行性,增加解的多样性.对背包问题进行测试,结果验证了IDHS算法的有效性.

一种新型量子演化算法及其应用研究

针对传统演化算法难以模拟量子物理特性的难题,提出一种新型量子演化算法模型。采用将进化算法与量子计算相结合的方法,在常规染色体结构上附加随机干涉,从数理角度模拟量子计算的叠态、纠缠等特性。将其应用于解决多维背包问题,实验结果表明,该算法能增加种群的基因多样性,并提高全局优化能力。

融合差异进化的混合算法求解多选择背包问题

针对典型的组合优化问题——多选择背包问题(MCKP),提出了一种融合差异进化的混合算法(IDEHA)。算法按照适应度值将个体分为3个阶级,实施差异进化;通过设计一种有效的随机贪心修复策略,引入精英库进行协同寻优来加速算法收敛。通过对典型的多选择背包算例的求解并与其他算法的对比分析,基于融合差异进化的混合算法具有收敛速度快、求解精度高、稳定性和鲁棒性强等优点。