基于遗传算法求解折扣{0-1}背包问题的研究

目前,求解折扣{0-1}背包问题(D{0-1}KP)的主要算法是基于动态规划的具有伪多项式时间的确定性算法,当D{0-1}KP实例中各项的价值系数与重量系数在大范围内取值时缺乏实用性.文中基于杰出者保留策略遗传算法(EGA)求解D{0-1}KP,首先建立了D{0-1}KP的两个新的数学模型;然后,为了利用EGA和第一数学模型求解D{0-1}KP,提出了一种处理非正常编码个体的贪心修复与优化算法GROA,并将其与EGA相结合给出了求解D{0-1}KP的第一遗传算法FirEGA;紧接着,利用EGA和第二数学模型求解D{0-1}KP,提出了处理非正常编码个体的另一种有效算法NROA,并将其与EGA相结合给出了求解D{0-1}KP的第二遗传算法SecEGA;最后,利用四类大规模D{0-1}KP实例,确定了FirEGA和SecEGA的交叉概率与变异概率的合理取值,比较了两个算法的实际求解性能.对四类实例的计算结果表明:FirEGA和SecEGA都非常适于求解大规模的难D{0-1}KP实例,均能够得到一个近似比非常接近于1的近似解,并且FirEGA的平均求解性能比SecEGA的更优.

二次背包问题的贪婪量子进化算法求解

二次背包问题是一种NP难组合优化问题,其精确算法求解难度大,针对该问题提出了一种量子进化算法求解方法。该算法采用一种相对贪婪修补算子,该修补算子不但考虑了二次背包问题的每一物品项价值,而且考虑了物品的协作价值,是一种动态修补算子。同时算法借鉴粒子群算法中粒子的运动方程,提出了一种具有三类知识学习能力的量子更新模式,使得量子进化中获得的知识更全面。通过对100个国际上大规模二次背包问题进行测试实验,验证了提出的求解算法比相应的其他启发式算法性能有较大提升。

贪心核加速动态规划算法求解折扣{0-1}背包问题

针对现有动态规划算法求解折扣{0-1}背包问题(D{0-1}KP)缓慢的问题,基于动态规划思想并结合新型贪心修复优化算法(NGROA)与核算法,通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划(GCADP)算法。首先利用NGROA对问题进行贪心求解,得到非完整项;然后通过计算得到模糊核区间的半径和模糊核区间范围;最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划(BDP)算法求解。实验结果表明:GCADP算法适用于求解D{0-1}KP,且在求解速度上相比BDP算法平均提升了76.24%,相比FirEGA算法平均提升了75.07%。

改进修复策略遗传算法求解折扣{0-1}背包问题

第一遗传算法(FirEGA)在求解折扣{0-1}背包问题(D{0-1}KP)过程中对非正常编码的修复未能较好运用物品折扣关系,影响修复效果,导致求解结果不理想。针对该问题,对FirEGA中的贪心修复与优化算法(GROA)进行修正:传统贪心修复按照价值密度对项进行选取,当出现同一项集中两个项均被选取时,文中不再选取价值密度较大项,而是选择价值较大项,得到处理非正常编码个体的新的贪心修复优化算法(NGROA)。在FirEGA中采用NGROA,构成求解D{0-1}KP新的第一遗传算法(NFirEGA)。最后,利用NFirEGA求解四类大规模D{0-1}KP问题,结果表明,NFirEGA在求解精度上明显优于FirEGA。

差分进化帝王蝶优化算法求解折扣{0-1}背包问题

帝王蝶优化算法(Monarch Butterfly Optimization,MBO)是一种新颖的群体智能算法,自从提出就在实际优化问题上表现出很好的性能.但是,帝王蝶优化算法的迁移算子采用随机选择两个个体来生成新个体,并没有记忆整个种群的最优解,容易造成全局最优帝王蝶搜索经验的丢失.根据MBO寻优过程的内在机制以及差分进化算法的变异算子能够利用个体间的差异信息,将MBO分别与目前性能最优、应用范围最广的7种差分进化(Differential Evolution,DE)变异策略相结合,实验验证了7种不同算法的性能.基于性能最优的DE/best/2/bin变异模式,提出了一种差分进化帝王蝶优化算法(Monarch Butterfly Optimization Algorithm with Differential Evolution,DEMBO),使得算法能够记忆种群最优解并实现种群内部信息的充分共享,达到既加快收敛速度又提高解的精度的目的.在30个典型折扣{0-1}背包问题(D{0-1}KP)实例上进行了一系列实验,实验结果表明:(1)DEMBO能够在时间复杂度不变的条件下,显著提高算法的求解精度和收敛速度;(2)DEMBO在求解所有D{0-1}KP实例时,均能够获得一个近似比非常接近1的近似解.

基于细菌觅食算法求解折扣{0-1}背包问题的研究

折扣{0-1}背包问题(D{0-1}KP)是新型的0-1背包问题。提出了基于细菌觅食算法(BFO)求解D{0-1}KP的方法,首先描述了D{0-1}KP的两个数学模型,然后将BFO分别与两个数学模型相结合,即细菌个体分别采用二进制向量和四进制向量的编码方法,并利用贪心策略优化初始解和修复非正常编码个体,给出了求解D{0-1}KP的FirBFO和SecBFO算法。对四类实例的计算结果表明,FirBFO和SecBFO都非常适于求解大规模的D{0-1}KP实例,能得到最优解或近似比接近1的近似解。

核加速遗传算法求解折扣{0-1}背包问题

针对现有遗传算法求解折扣{0-1}背包问题(D{0-1}KP)易陷入局部最优解,同时存在大量无效交叉变异操作使得算法收敛较慢等问题,本文基于精英保存策略(EGA)和贪心修复算法(GROA),将核算法与遗传算法进行融合,提出求解D{0-1}KP的核加速遗传算法(CEGA)。将CEGA用于求解四类大规模D{0-1}KP实例,结果表明:CEGA适用于求解D{0-1}KP,且精确度和收敛速度均好于第一遗传算法(FirEGA)。

自适应细菌觅食算法求解折扣{0-1}背包问题

针对确定性算法难以求解的大规模折扣{0-1}背包问题(D{0-1}KP),提出了自适应细菌觅食算法(ABFO)求解D{0-1}KP的两种算法。首先,给出了D{0-1}KP的两种数学模型;然后,针对细菌觅食算法的趋化操作提出了自适应趋化策略;最后,利用两种贪心修复与优化策略处理两种数学模型中的不可行解,得到求解D{0-1}KP的Fir ABFO和Sec ABFO算法。仿真实验表明,Fir ABFO和Sec ABFO均能得到最优解或近似比几乎等于1的近似解,非常适于求解D{0-1}KP,并且Sec ABFO的求解性能比Fir ABFO更优。

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

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

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

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

折扣{0-1}背包问题粒子群算法的贪婪修复策略探究

群智能启发式算法求解折扣{0-1}背包问题(D{0-1}KP)时,为提升求解效率和求解质量,需采用某种修复与优化策略将非正常编码个体转换为符合解约束条件的编码个体。在引入项集价值密度概念基础上,以粒子群算法(PSO)为例,提出一组基于项集的贪婪修复与优化方法(group greedy repair and optimization algorithm,GGROA),并进一步构造PSO-GGRDKP算法(PSO based GGROA for solving D{0-1}KP)以探究GGROA方法的可行性和性能。PSO-NGROADKP(PSO based NGROA for solving D{0-1}KP)和PSO-GRDKP(PSO based GROA for solving D{0-1}KP)是基于项贪心修复与优化方法的粒子群算法。在D{0-1}KP标准数据集的实验结果表明:与PSO-NGROADKP和PSO-GRDKP相比,PSO-GGRDKP算法的解误差率略高,但算法时间性能分别提升了13.8%、12.9%。

一种求解软硬件划分问题的混合编码二进制差分演化算法

软硬件划分(HW/SW)是软硬件协同设计中的一个重要问题,也是一个NP-hard问题。当问题规模较大时,不仅求解困难而且非常耗时。为了快速高效地求解HW/SW,本文提出了一种利用混合编码的二进制差分演化算法(HBDE)求解HW/SW的新思路。首先,根据HW/SW的自身特点提出了一种处理不可行解的贪心修复优化算法GROA。然后,在利用GROA消除不可行解的基础上,使用HBDE求解HW/SW的问题。最后,使用HBDE和遗传算法(GA)求解11个不同规模的HW/SW实例。从计算结果可以看出,对于所有实例,HBDE求解性能明显优于GA,因此基于HBDE求解HW/SW问题是一种高效可行的方法。

基于混合编码的二进制差分演化算法求解软硬件划分问题

软硬件划分(HW/SW)是软硬件协同设计中的一个重要问题,也是一个NP-hard问题。当问题规模较大时,不仅求解困难而且非常耗时。为了快速高效地求解HW/SW,本文提出了一种利用混合编码的二进制差分演化算法(HBDE)求解HW/SW的新思路。首先,根据HW/SW的自身特点提出了一种处理不可行解的贪心修复优化算法GROA。然后,在利用GROA消除不可行解的基础上,使用HBDE求解HW/SW的问题。最后,使用HBDE和遗传算法(GA)求解11个不同规模的HW/SW实例。从计算结果可以看出,对于所有实例,HBDE求解性能明显优于GA,因此基于HBDE求解HW/SW问题是一种高效可行的方法。

基于B-RRT^(*)FND算法的移动机器人路径规划

针对RRT^(*)FN算法获取路径解的速度慢,且无法应用于动态环境等问题,提出固定节点数的动态双向渐近最优快速随机扩展树算法(bidrectional RRT^(*)fix-node dynamic,B-RRT^(*)FND),用于解决移动机器人在二维空间内快速实时获取无碰撞路径的问题.所提出算法基于RRT^(*)FN算法,采用双向贪婪搜索方法加快路径搜索速度,解决单向RRT算法由于随机采样的盲目性造成的搜索速度慢、在狭窄环境下难以搜索到解的问题;利用固定节点算法在规划过程中不占用过多计算量的特点,在路径迭代优化过程中,实时更新地图信息,并对被破坏的原始路径进行修复重连,以完成算法的动态规划.将所提出算法与RRT、RRT^(*)FN等算法在3种环境下进行对比仿真,验证结果表明,所提出算法在规划速度、路径解长度以及动态规划性能方面具有较好效果.