基于自适应ε约束处理法的改进蛾子搜索算法  

Modified Moth Search Algorithm Based on Adaptiveε-Constrained Method

作　　者：冯艳红 王改革 李明亮 李晰 FENG Yanhong;WANG Gaige;LI Mingliang;LI Xi(School of Information Engineering,Hebei GEO University,Shijiazhuang 050031;Intelligent Sensor Network Engineering Research Center of Hebei Province,Hebei GEO University,Shijiazhuang 050031;Hebei Key Laboratory of Optoelectronic Information and Geo-detection Technology,Hebei GEO University,Shijiazhuang 050031;School of Computer Science and Technology,Ocean University of China,Qingdao 266100)

机构地区：[1]河北地质大学信息工程学院,石家庄050031 [2]河北地质大学河北省智能传感物联网技术工程研究中心,石家庄050031 [3]河北地质大学,河北省光电信息与地球探测技术重点实验室,石家庄050031 [4]中国海洋大学计算机科学与技术学院,青岛266100

出　　处：《模式识别与人工智能》2023年第6期483-494,共12页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.61806069);河北省重点研发计划项目(No.22375415D);河北省高校科学技术研究项目(No.ZD2022083)资助。

摘　　要：多需求多维背包问题包含相互冲突的两类不等式约束,对其可行域的搜索异常困难.因此,文中提出基于ε约束处理法的改进蛾子搜索算法.在莱维飞行阶段,根据当前进化代数调节步长值.在直接飞行阶段,引入突变率,增加算法的种群多样性.最后,对整个种群应用均匀变异算子,提高算法的全局探索遍历性.采用空间映射方法实现搜索空间到问题空间的转换,采用自适应ε约束处理法处理约束.在经典的96个测试用例上的验证实验表明:自适应莱维飞行算子、突变直接飞行算子、均匀变异算子对算法求解精度都具有显著效果,文中算法在求解绝大多数测试用例时的寻优精度较优.此外,文中应用正交实验方法分析参数对于ε约束处理法的影响.The multidemand multidimensional knapsack problem includes two types of inequality constraints with conflicts,making the search for the feasible solution region exceptionally difficult.Therefore,a modified moth search algorithm(MMS)based on adaptiveε-constrained method is proposed in this paper.In the Lévy flight phase,the step is adjusted according to the current iteration.In the straight flight phase,the mutation rate is introduced to increase the diversity of the population.Finally,the uniform mutation operator is applied to the whole population to improve the global search capability of the algorithm.The space mapping method is utilized to transfer the search space to the problem space,and the adaptiveε-constrained method is adopted.Experiments on classic 96 benchmark instances show that adaptive lévy flight operator,mutation straight flight operator and uniform mutation operator contribute significantly to the solution accuracy of the algorithm and the proposed algorithm performs better on the majority of instances.Furthermore,orthogonal experimental design method is utilized to analyze the influence of parameters on theε-constrained method.

关 键 词：进化算法 蛾子搜索算法(MS) 自适应ε约束处理法 多需求多维背包问题(MDMKP) 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]