自适应Shannon熵驱动的混沌灰狼优化(ASE-CGWO)及其在组合优化问题中的应用

《Biomimetics》:Adaptive Shannon Entropy-Driven Chaotic Grey Wolf Optimization (ASE-CGWO) for Combinatorial Optimization Problems

【字体: 大 中 小 】 时间:2026年09月24日 来源:Biomimetics 4.2

编辑推荐:

  组合优化问题包含许多NP-hard问题,如分配、调度和路径规划;对于大规模实例,传统求解方法在计算上变得不可行,因此有必要采用元启发式算法。本研究提出一种面向组合优化问题的自适应Shannon熵驱动的混沌灰狼优化算法(Adaptive Shannon Entr

  
组合优化问题包含许多NP-hard问题,如分配、调度和路径规划;对于大规模实例,传统求解方法在计算上变得不可行,因此有必要采用元启发式算法。本研究提出一种面向组合优化问题的自适应Shannon熵驱动的混沌灰狼优化算法(Adaptive Shannon Entropy-Driven Chaotic Grey Wolf Optimization, ASE-CGWO)。该方法利用基于熵的多样性度量自适应调节混沌程度,以确保探索与利用之间的有效权衡。该方法还采用熵自适应狩猎参数,将探索广度直接与狼群的信息含量耦合。同时引入精英记忆档案(Elite Memory Archive)以及交换(swap)、插入(insertion)和翻转(flip)算子以增强邻域搜索,从而保持高质量解。将ASE-CGWO与标准灰狼优化(Standard GWO)、固定r=3.9 Logistic映射的混沌灰狼优化(Chaotic GWO)、仅以熵自适应“a”的熵自适应灰狼优化(Entropy-Adaptive GWO)、遗传算法(Genetic Algorithm, GA)、粒子群优化(Particle Swarm Optimization, PSO)和蚁群优化(Ant Colony Optimization, ACO)在三个NP-hard组合优化问题上进行基准比较:二次分配问题实例chr15a、Fisher–Thompson 10×10作业车间调度问题(FT10)以及20城市旅行商问题(TSP20),每个问题独立运行20次。ASE-CGWO在chr15a上取得最佳平均分配成本(9921.6 ± 147.3,原生QAPLIB单位),其最佳运行达到已知最优值9896,并在FT10上取得第二佳平均最大完工时间(1182.05 ± 3.32)。ASE-CGWO的自适应与自调节特性也表明其在复杂工程优化问题(包括太阳能系统的设计与运行)中具有未来应用潜力。
自适应Shannon熵驱动的混沌灰狼优化(ASE-CGWO)论文解读

1. 研究背景与问题
组合优化问题包含大量NP-hard问题,例如分配、调度与路径规划;当问题规模增大时,精确算法的计算代价呈指数增长,因此元启发式算法成为求解近优解的主流工具。灰狼优化(Grey Wolf Optimization, GWO)由Mirjalili等提出,具有结构简单、参数少和计算效率高等优点,但其标准形式存在两个固有缺陷:一是控制参数a按线性计划从2降至0,探索与利用的平衡在搜索过程中固定不变,容易导致早熟收敛;二是每代仅由最优的三头狼α、β、δ引导更新,其余狼群携带的搜索信息被丢弃,造成搜索信息损失。已有混沌GWO变体虽然使用Logistic映射替代线性a,但大多将映射参数r固定(例如r=3.9),无法根据种群当前状态调整混沌强度;熵自适应GWO又只利用Shannon熵调整a,未与混沌机制耦合。因此,研究人员提出自适应Shannon熵驱动的混沌灰狼优化(Adaptive Shannon Entropy-Driven Chaotic Grey Wolf Optimization, ASE-CGWO),以Shannon熵作为种群多样性指标,同时调控混沌参数和狩猎参数,并加入精英记忆档案与邻域搜索,以期提高组合优化问题的求解质量与稳定性。

2. 研究内容与意义
研究人员将ASE-CGWO与标准GWO、固定r=3.9的混沌GWO、熵自适应GWO(仅用熵调整a)、遗传算法(Genetic Algorithm, GA)、粒子群优化(Particle Swarm Optimization, PSO)和蚁群优化(Ant Colony Optimization, ACO)在三个NP-hard基准问题上进行对比:QAPLIB的chr15a二次分配问题、Fisher–Thompson 10×10作业车间调度问题(FT10)和20城市旅行商问题(TSP20),每个算法独立运行20次。结果表明,ASE-CGWO在chr15a上获得最低平均分配成本(9921.6±147.3),最佳运行达到已知最优值9896;在FT10上取得第二佳平均最大完工时间(1182.05±3.32);在TSP20上具有竞争力,最佳巡回长度386.43。该算法通过熵-混沌耦合形成自调节多样性控制器,改善了探索与利用的平衡,其自适应特性为太阳能系统设计优化等复杂工程问题提供了潜在应用方向。

3. 关键方法
研究人员采用以下主要关键技术:基于适应度的Shannon熵计算种群多样性指数d(t)=H(t)/lnN;熵门控混沌机制将Logistic映射参数设为r(t)=rmin+(rmax?rmin)(1?d(t)),其中rmin=2.80,rmax=3.95;熵自适应狩猎参数a(t)=2d(t),并用交换序列实现向α、β、δ三头领狼的离散位置更新;设规模K=15的精英记忆档案(Elite Memory Archive, EMA)与停滞重启机制;采用交换、插入、翻转三类邻域算子进行局部精化(常规12次探测,每5代对α狼24次探测)。基准来自QAPLIB chr15a、Fisher–Thompson FT10和20城市TSP20;参数为种群30、迭代300、20次独立运行,并使用单侧Wilcoxon符号秩检验。

4. 研究结果
4.1 二次分配问题chr15a结果
在QAP chr15a上,ASE-CGWO取得最低平均目标值9921.6和最小标准差147.3,最佳运行达到已知最优9896。ACO是最接近的竞争者(平均10038.0),但平均执行时间更长(0.87秒对比0.31秒)。EGWO表现极差(15659.2±3494.4),说明仅熵自适应而无混沌耦合在该多模态问题上无法保持稳定。

4.2 作业车间调度问题FT10结果
ASE-CGWO在FT10上取得第二佳平均最大完工时间(1182.05±3.32),仅比GA差0.08%;两者最佳解均为1181。ASE-CGWO优于标准GWO、CGWO、EGWO、PSO和ACO。ACO表现最差(平均1187.75,标准差9.71)。GA的优势归因于其顺序交叉算子(order crossover, OX)能保留调度中的相对作业顺序。

4.3 旅行商问题TSP20结果
ACO在TSP20上最优(387.71±2.98),因其信息素引导的路径构建适合欧氏TSP。ASE-CGWO(441.81±61.64)与PSO(447.72±31.67)有竞争力,均优于GWO和CGWO;EGWO最差(861.85±35.66)。ASE-CGWO最佳运行达到386.43,接近已知近优解。高方差源于交换序列更新有时产生中间质量较差的排列,后续可引入2
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号