基于编码转换的离散演化算法设计与应用

为了求解离散域上的组合优化问题,借鉴遗传算法(GA)、二进制粒子群优化(BPSO)和二进制差分演化(HBDE)中的映射方法,给出了一种基于映射变换思想设计离散演化算法(DisEA)的实用方法——编码转换法(ETM).为了说明ETM的实用性与有效性,首先,基于ETM给出了一个离散粒子群优化算法(DisPSO);然后,分别利用BPSO,HBDE和DisPSO等基于ETM构造的演化算法求解集合联盟背包问题和折扣{0-1}背包问题.通过与GA的计算结果比较指出,BPSO,HBDE和DisPSO的求解性能均优于GA,说明基于ETM提出的DisEA在求解背包问题方面具有良好的性能.由此表明,利用ETM方法设计DisEA是一种实用的有效方法.

改进的教与学优化算法求解集合联盟背包问题

针对集合联盟背包问题(set-union knapsack problem,SUKP)难以使用确定性算法求解的情况,提出了一种快速求解SUKP问题的改进二进制教与学优化算法(modified binary teaching-learning-based optimization,MBTLBO)。首先,给出了教与学优化算法的二进制编码方法;然后,针对求解SUKP问题中的候选解,提出改进的修复优化策略(modified SUKP greedy repairing and optimization algorithm,MS-GROA)。该策略增加了修复后可行解的二次优化,从而提升了对SUKP问题的求解精度。另外为了克服教与学优化算法易早熟,求解精度低,后期收敛速度慢等弱点,在"教"阶段和"学"阶段引入差分算法的交叉算子,通过平衡算法的开发能力和勘探能力,避免算法过早陷入局部极值;在精英个体周围按正态分布进行自适应局部搜索,提高算法的收敛速度和求解精度。三类SUKP实例测试表明,MBTLBO算法具有较高的求解精度和更快的收敛速度,是有效求解SUKP问题的方法。

求解集合联盟背包问题的二次贪心变异乌鸦算法

针对确定性算法难以求解的集合联盟背包问题(Set-Union Knapsack Problem,SUKP),提出了二次贪心变异乌鸦算法(quadratic greedy mutated crow search algorithm,QGMCSA).首先结合SUKP问题模型对贪心策略进行改进,提出了处理其潜在解的二次贪心修复和优化策略;其次,为了扩大乌鸦个体的搜索范围,对乌鸦算法进行变异操作,在跟踪过程中引入莱维飞行;最后,利用三类SUKP实例验证本文算法.仿真结果表明:QGMCSA是比二进制人工蜂群算法求解SUKP的结果更优的一个高效算法.