具有学习机制的离散差分演化算法

如何将差分演化算法应用于离散领域是目前该领域的一个热点研究问题。用分布估计算法对搜索空间中优质解的分布进行建模,然后根据建立的模型抽样产生新解,利用分布估计这种全局信息学习的机制,提出具有学习机制的离散差分演化算法并用于求解多维背包问题。实验结果表明,提出的算法具有良好的性能。

基于分布估计的离散差分演化算法

差分演化(DE)是解决优化问题的非常有效的新兴智能算法,但它主要用于连续优化领域,至今尚不能象解决连续优化问题那样有效的处理组合优化问题。首先提出了离散DE用于组合优化问题,然后在离散DE中引入分布估计算法(EDA)来提高性能,把EDA抽样得到的全局统计信息和离散DE获得的局部演化信息相结合来产生新解,形成基于EDA的离散DE算法。为了保持种群多样性,在提出的算法中引入了位翻转变异操作。实验结果表明,EDA能大大提高离散DE的性能。

适应度平均选择的离散差分演化算法

如何将差分演化算法用于离散领域是该领域的一个重要问题.提出一种适应度平均选择的离散差分演化算法,提出的算法中每个个体有均等的机会被选择用于引导算法的进化,这种选择方式有助于克服贪婪选择操作导致的种群多样性下降过快而使算法易陷入局部最优的问题.最后在多维背包问题上的实验结果表明提出的算法具有良好性能.

基于离散差分演化的KPC问题降维建模与求解

具有单连续变量的背包问题(Knapsack Problem with a single Continuous variable,KPC)是标准0-1背包问题的一个新颖扩展形式,它既是一个NP完全问题,又是一个带有连续变量S的新颖组合优化问题,求解难度非常大.为了快速高效地求解KPC问题,该文提出了利用演化算法求解KPC的新思路,并给出了基于离散差分演化算法求解KPC的两个有效方法.首先,介绍了基本差分演化算法和具有混合编码的二进制差分演化算法(HBDE)的原理,给出了HBDE的算法伪代码描述,并分析了KPC的基本数学模型KPCM1的计算复杂度.然后,在基于降维法消除KPCM1中连续变量S的基础上,建立了KPC的一个新离散数学模型KPCM2;随后在基于贪心策略提出处理不可行解的有效算法基础上,基于单种群HBDE给出了求解KPC的第一个离散演化算法S-HBDE.第三,通过把连续变量S的取值范围划分为两个子区间将KPC分解为两个子问题,并基于降维法建立了KPC的适于并行求解的第二个数学模型KPCM3;在利用贪心策略给出处理子问题不可行解的两个有效算法基础上,基于双种群HBDE提出了求解KPC的第二个离散演化算法B-HBDE.最后,在给出四类大规模KPC实例的基础上,利用S-HBDE和B-HBDE分别求解这些实例,并与近似算法AP-KPC、遗传算法和离散粒子群优化算法的计算结果、耗费时间和稳定性等指标进行比较,比较结果表明S-HBDE和B-HBDE不仅在求解精度和稳定性方面均优于其它3个算法,而且求解速度很快,非常适于在实际应用中快速高效地求解大规模KPC实例.

新颖的离散差分演化算法求解D{0-1}KP问题

折扣{0-1}背包问题(D{0-1}KP)是0-1背包问题(0-1KP)的一种更复杂的扩展形式。为了利用离散差分演化高效求解D{0-1}KP,首先提出了一个新V型转换函数(NV),通过NV将个体的实向量映射为一个二进制向量,与已有的S型和V型转换函数相比,NV计算复杂度更低,求解效率更高。然后,基于新V型转换函数给出了一种新的离散差分演化算法(NDDE),并利用NDDE提出了求解D{0-1}KP的一个新的高效方法。最后,为了验证NDDE求解D{0-1}KP的性能,利用它求解四类大规模D{0-1}KP实例,并与基于群论的优化算法(GTOA)、基于环理论的演化算法(RTEA)、混合教学优化算法(HTLBO)和鲸鱼优化算法(WOA)等已有算法的最好计算结果进行比较,比较结果表明,NDDE不仅求解精度更高,而且算法的稳定性佳,非常适于求解大规模D{0-1}KP实例。