求解最短路径问题的一种改进的人工蜂群算法

蜂群算法在动态路径规划问题中的实验验证引言动态路径规划是指在一个动态环境中，根据实时输入的信息和目标，实时更新路径规划，以实现有效的路径选择。

蜂群算法是一种基于自然界蜜蜂行为的启发式搜索算法，被广泛应用于解决动态路径规划问题。

本文将探讨蜂群算法在动态路径规划问题中的实验验证，以验证其在这一领域的应用潜力。

动态路径规划问题概述动态路径规划问题是一个重要的研究领域，涉及到交通、物流等许多实际问题。

在现实情况下，道路网络中的交通流量、道路状况等会发生变化，因此静态的路径规划无法满足实际需求。

动态路径规划需要根据实时变化的信息对路线进行实时调整，以找到最优路径。

蜂群算法概述蜂群算法是一种模拟蜜蜂觅食行为的启发式搜索算法，由Dorigo等人在1992年提出。

蜂群算法模拟了蜜蜂在搜索食物过程中的行为，包括来源采集、信息传递和路径选择等。

这些行为可以被抽象为一些启发式的搜索规则，使得算法能够在多维搜索空间中找到最优解。

蜂群算法在动态路径规划中的应用蜂群算法在动态路径规划中的应用主要涉及两个方面：路径更新和路径选择。

路径更新是指在动态环境中，根据实时变化的信息对路径进行实时调整。

蜂群算法通过源-汇模型将路径更新视为一个信息传递的过程。

蜜蜂从源地出发，通过与其他蜜蜂进行信息交流来寻找最短路径。

在路径更新过程中，蜂群算法利用信息素作为路径选择的指导，根据信息素浓度和路径长度来评估路径的好坏。

通过反复的信息传递和路径调整，蜂群算法能够在动态环境中找到较优路径。

路径选择是指在多个可选路径中选择最优路径。

蜂群算法通过模拟蜜蜂觅食行为，将可选路径视作食物源。

蜜蜂根据食物源的信息素浓度来进行路径选择，信息素浓度较高的路径被认为是更好的路径。

在动态路径规划中，蜂群算法将实时变化的路径信息通过信息素的更新传递给蜜蜂群体，使其能够及时选择最优路径。

通过不断迭代和更新，蜂群算法能够适应动态环境，并寻找到最优路径。

实验验证与结果分析为了验证蜂群算法在动态路径规划中的应用效果，我们设计了一系列实验，并进行了实验验证。

一种求解旅行商问题的改进人工蜂群算法程国;丁正生【摘要】Aiming at the premature convergence problem and easily plunged into local optimal solution in artificial bee colony algorithm when dealing with large⁃scale travlling salesman problem,this paper proposes an improved artificial bee colony algorithm. The Cauchy mutation operator is introduced into the bee food source update formula. A kind of adaptive logarithm step is designed instead of generated random step to improve the random solution formula. The improved algorithm is used for solving symmetric TSP problem,the experimental results show that the improved algorithm can effectively solve the artificial colony algorithm problem such as premature convergence and slow search speed,and it is really effective and feasible in solving TSP problem.%针对人工蜂群算法在处理大规模旅行商问题时普遍存在易陷入局部最优解和早熟收敛的问题，提出一种改进的人工蜂群算法。

人工蜂群算法综述作者：陈阿慧李艳娟郭继峰来源：《智能计算机与应用》2014年第06期摘要：人工蜂群算法是Karaboga在2005年提出的一种基于蜜蜂觅食行为的群体智能算法，该算法可以很好的解决连续函数的求解问题，后因其强大的性能深受研究者的青睐，得以广泛的研究和应用。

本文首先简要介绍了群体智能和人工蜂群算法的发展，然后详细介绍了人工蜂群算法的原理及实现步骤，最后综述近十年来国内外对该算法及其应用的研究状况，进而总结出该算法具有控制参数少、强鲁棒性等优点，并指出该算法时间复杂度略高的基本事实，可成为今后改进的研究方向。

关键词：人工蜂群算法；群体智能；觅食行为；连续函数；强鲁棒性中图分类号：TP301 文献标识号：A 文章编号：2095-2163（2014）06-Abstract： Artificial bee colony algorithm is a kind of swarm intelligence algorithm based on bees foraging behavior which is proposed by Karaboga on 2005. The algorithm can solve continuous function very well，then get many researchers’ favor because of its powerful performance and be researched and used widely. Firstly， this paper introduces the development of swarm intelligence and artificial bee colony algorithm briefly. Secondly， this paper introduces the principle and steps of artificial bee colony algorithm in details， and reviews the decade research situation of domestic and overseas. The conclusion is given that the algorithm has the advantages of less control parameters and strong robustness. However， the algorithm has slightly high time complexity which can be the future research direction.Key words： Artificial Bee Colony Algorithm； Swarm Intelligence； Foraging Behavior；Continuous Function； Strong Robustness0 引言自然界中的群居性昆虫，虽然其中每一个体均呈现为结构简单，以及行为单一，但是群居后的昆虫整体却构建了一种复杂的行为模式。

基于差分变异算子的改进人工蜂群算法人工蜂群算法（ABC）是一种基于蜜蜂族群行为和现象的全局优化算法，具有良好的全局搜索能力和鲁棒性。

ABC算法将问题空间视为一个蜜蜂群，在空间中随机生成若干蜜蜂，并利用信息交流的方式，逐步寻找最优解。

然而，ABC算法存在一些不足，例如易陷入局部最优、搜索速度慢等问题。

为了提高ABC算法的优化效率和精度，本文提出一种基于差分变异算子的改进ABC算法。

具体来说，本算法通过引入差分变异算子，将参与局部搜索和全局搜索的策略统一起来，以增强搜索的能力。

同时，采用自适应权重的机制，避免算子参数的手动设置。

改进ABC算法的流程如下：1.初始化：随机生成初始种群，包含若干个蜜蜂。

2.自适应权重设置：根据历史最优解和群体当前适应度值的情况，设置变异率和交叉率的自适应参数。

3.基于差分变异的搜索：采用差分变异算子对当前种群进行局部和全局搜索，得到子代个体。

4.更新蜜蜂群体：根据适应度值的高低，更新种群状态和最优解。

5.停止条件：如果满足停止条件（如达到最大迭代次数或达到精度要求），则输出最优解；否则，返回第2步继续迭代搜索。

差分变异算子是一种常用的进化算法，其思想是对种群中的不同个体进行差分运算，以获得新的进化个体。

具体来说，差分变异算子包括三个关键参数：变异率、交叉率和差分因子。

其中，差分因子用于控制差分计算的大小，变异率和交叉率分别用于控制变异和交叉的概率。

改进ABC算法中，差分变异算子被用于实现全局和局部搜索。

对于全局搜索，差分变异算子将当前最优个体和随机选择的两个个体进行差分计算，得到新的进化个体。

对于局部搜索，差分变异算子将当前个体和邻域内最优个体进行差分计算，得到新的进化个体。

通过差分变异算子，全局搜索和局部搜索的策略被统一起来，从而增强了搜索的能力和精度。

自适应权重的设置是改进ABC算法的另一个重要组成部分。

自适应权重能够根据不同的搜索状态和需求，自动调整变异率和交叉率的大小，从而避免了手动选择参数的繁琐和不准确。

一种人工蜂群算法改进方案梁静;葛宇;冉晓娟;李琦【期刊名称】《计算机应用研究》【年(卷),期】2015(32)11【摘要】In order to improve the efficiency of artificial bee colony algorithm,this paper improved search strategy of onlooker bees and scout bees.Specifically,the improved algorithm presented crowd indicators and designed an adaptive neighborhood search strategy for onlooker bees based on crowd indicators.Meanwhile,in order to keep the diversity of population and avoid premature convergence,this paper designed poor individual reset mechanism for scout bees.The simulation results of eight typical functions show that the improved algorithm has achieved good results in convergence speed and accuracy,compared with the basic artificial bee colony algorithm and other similar algorithms.%为提高人工蜂群算法的寻优效率，对算法中跟随蜂和侦察蜂的搜索策略进行了改进，提出了一种反映个体拥挤程度的 crowd 指标，并基于该指标为跟随蜂设计了针对优秀个体的自适应邻域搜索策略；针对侦察蜂的搜索行为，设计了一种较差个体重置机制，以保持种群多样性，防止算法可能出现的早熟收敛。

⼈⼯蜂群算法简介与程序分析⽬前⼈⼯蜂群算法主要分为基于婚配⾏为与基于⾤蜜⾏为两⼤类，本⽂研究的是基于⾤蜜⾏为的⼈⼯蜂群算法。

蜜蜂采蜜⾃然界中的蜜蜂总能在任何环境下以极⾼的效率找到优质蜜源，且能适应环境的改变。

蜜蜂群的采蜜系统由蜜源、雇佣蜂、⾮雇佣蜂三部分组成，其中⼀个蜜源的优劣有很多要素，如蜜源花蜜量的⼤⼩、离蜂巢距离的远近、提取的难易程度等；雇佣蜂和特定的蜜源联系并将蜜源信息以⼀定概率形式告诉同伴；⾮雇佣蜂的职责是寻找待开采的蜜源，分为跟随蜂和侦查蜂两类，跟随峰是在蜂巢等待⽽侦查蜂是探测蜂巢周围的新蜜源。

蜜蜂采蜜时，蜂巢中的⼀部分蜜蜂作为侦查蜂，不断并随机地在蜂巢附近寻找蜜源，如果发现了花蜜量超过某个阈值的蜜源，则此侦査蜂变为雇佣蜂开始⾤蜜，采蜜完成后飞回蜂巢跳摇摆舞告知跟随峰。

摇摆舞是蜜蜂之间交流信息的⼀种基本形式，它传达了有关蜂巢周围蜜源的重要信息如蜜源⽅向及离巢距离等，跟随峰利⽤这些信息准确评价蜂巢周围的蜜源质量。

当雇佣蜂跳完摇摆舞之后，就与蜂巢中的⼀些跟随蜂⼀起返回原蜜源采蜜，跟随蜂数量取决于蜜源质量。

以这种⽅式，蜂群能快速且有效地找到花蜜量最⾼的蜜源。

蜜蜂采蜜的群体智能就是通过不同⾓⾊之间的交流转换及协作来实现的。

具体采蜜过程如图所⽰。

在最初阶段，蜜蜂是以侦查蜂的形式出现，且对蜂巢周闱的蜜源没有任何了解，由于蜜蜂内在动机和外在的条件不同侦查蜂有两种选择：①成为雇佣蜂，开始在蜂巢周围随机搜索蜜源，如图中路线②成为跟随峰，在观察完摇摆舞后开始搜索蜜源，如图中路线。

假设发现两个蜜源和，在发现蜜源后，该侦查蜂变成⼀只雇佣蜂，雇佣蜂利⽤其⾃⾝属性记住蜜源的位置，并⽴刻投⼊到采蜜中。

采蜜完成后蜜蜂带着满载花蜜返回蜂巢，将花蜜卸载到卸蜜房，卸载完成后雇佣蜂有三种可能的⾏为①放弃⾃⼰发现的花蜜量不⾼的蜜源，变成⼀个不受约束的⾮雇佣蜂，如图中的路线；②在招募区跳摇摆舞，招募⼀些待在蜂巢中跟随峰，带领其再次返回所发现的蜜源如图中的路线；③不招募其他蜜蜂，继续回到原来的蜜源采蜜如图中的路线。

改进的蜂群算法王辉【期刊名称】《计算机工程与设计》【年(卷),期】2011(032)011【摘要】In order to overcome the problem of premature convergence frequently and convergence slowly appeared in artificial bee colony algorithm (ABC), an improved artificial bee colony algorithm (1ABC) is proposed out In this approach, the information shared by individual and its neighborhood changing according to the food source quality of neighborhood at the onlooker stage. Moreover, the influence of food source currently weakened and the shared information of neighborhood enhanced according to the search process. Then bee colony can convergence to the region where global solution stayed at the initial stage and improve the global convergence of it at the last stage. The functional test result shows that IABC can search for global optimization more quickly and precisely than ABC, especially shows excellent performance in dealing complex problems.%针对蜂群算法收敛速度缓慢、容易出现早熟的问题,提出一种改进的蜂群算法(IABC).IABC在跟随阶段食物源更新中根据邻域个体食物源质量调整信息共享程度,并且随着搜索进程减弱当前食物源的影响、增强邻域信息共享强度,使蜂群在搜索初期快速收敛到最优食物源所在区域、在搜索后期提高全局收敛性能.函数测试结果表明,IABC有效地提高了ABC的收敛速度和优化精度,特别适合复杂函数的优化问题.【总页数】5页(P3869-3872,3876)【作者】王辉【作者单位】上海应用技术学院计算机科学与信息工程学院,上海200235【正文语种】中文【中图分类】TP301.6【相关文献】1.面向无人机航迹规划的改进人工蜂群算法 [J], 刘琨;封硕2.基于改进蜂群算法和灰色模型的管道腐蚀预测 [J], 秦谢勋;刘文彬;陈良超3.基于改进人工蜂群算法的砂型铸造打磨工序并行机调度 [J], 陈发源;卢旭锋;侯蔼麟;计效园;王泽明;周建新4.蜂群算法的改进及在热膨胀系数优化上的应用 [J], 片锦香;王国辉5.基于一致分布佳点集改进的交叉人工蜂群算法 [J], 张平华;贾万祥;程晓蕾因版权原因，仅展示原文概要，查看原文内容请购买。

学校代码*****分类号TP18学号**********密级公开西安电子科技大学博士学位论文人工蜂群算法研究及其应用作者姓名：张松一级学科：数学二级学科：应用数学学位类别：理学博士指导教师姓名、职称：刘三阳教授学院：数学与统计学院提交日期：2019年9月On the artificial bee colony algorithms andapplicationsA dissertation submitted toXIDIAN UNIVERSITYin partial fulfillment of the requirementsfor the degree of Doctor of Philosophyin Applied MathematicsByZhang SongSupervisor:Liu Sanyang ProfessorSeptember2019摘要摘要在传统最优化方法不断发展的同时,最近20多年兴起的进化算法异军突起,发展迅速.进化算法以达尔文的进化论为基础,通过模拟生物进化过程与机制来求解问题.进化算法不要求优化函数满足一定的条件或者性质,易于求解,已经成为智能算法的研究热点.其中人工蜂群算法就是一类求解速度较快、精度较高的进化算法,因其结构简单、易于实现,一经提出便受到众多学者的关注和研究.人工蜂群算法已被广泛应用于求解各种优化问题,如线性逼近、工程优化、车间调度等.本文通过改进人工蜂群算法在雇佣蜂阶段和观察蜂阶段的搜索方程,增加和调整搜索的结构,较好地提高了算法性能.进而把改进的人工蜂群算法应用于求解0-1背包问题、基于条件风险价值的投资组合模型、流水车间调度问题等,得到了较好的求解结果.本文主要工作如下:1.为了提高人工蜂群算法的求解速度和搜索能力,对搜索方程进行改进,提出改进人工蜂群算法（IABC算法）和新奇人工蜂群算法（NABC算法）.并进行大量数据实验,验证了改进搜索方程的优越性.对人工蜂群算法步骤中的雇佣蜂阶段、观察蜂阶段的搜索方程分别引入当前全局最优解,以当前全局最优解为中心,进行邻域搜索,进而用随机搜索策略跳出局部最优解,得到较好的求解结果,提高了算法随机搜索的能力.算法的局部搜索能力和全局搜索能力也得到有效平衡.用标准函数集进行测试,并通过反复数值实验,结果表明,从取得的最优值和求解速度上,改进的人工蜂群算法（IABC算法和NABC算法）都有较好的优越性.然后把改进的搜索方程应用于差分进化算法,数据结果显示,改进后的差分进化算法（IDE算法）收敛速度得到很大提高,也验证了差分进化算法在求解问题最优值过程中是一种比较稳定的进化算法.同时再一次证明改进的搜索方程是一种优秀的搜索方法.2.0-1背包问题是一种应用非常广泛的优化问题,本文尝试用IABC算法对0-1背包问题进行求解,得到了不错的数据结果.在改进的人工蜂群算法（IABC算法）基础上,通过对搜索方程进行取整和离散化处理,提出离散的人工蜂群算法（DIABC 算法）,并应用于求解0-1背包问题.利用0-1背包问题的标准测试集进行数值实验,求得了较好的最优值,求解用时相对较短,验证了离散人工蜂群算法（DIABC算法）在求解0-1背包问题上具有很好的收敛性和有效性.3.近年来,投资组合模型在金融领域被深入研究和广泛应用,本文把IABC算法应用于求解基于条件风险价值（CVaR）的投资组合优化问题上,并用实际数据进行数值分析,结果表明该模型可合理地分散投资组合的市场风险.能有效提高投资者的投资收益率,计算速度较快.进一步说明了改进人工蜂群算法在求解实际问题中的可西安电子科技大学博士学位论文靠性和广泛性.4.流水车间调度问题在各行各业中都有应用,主要用来减少工作时间、降低工作成本和提高工作效率.在改进人工蜂群算法（IABC算法）框架的基础上,对初始化阶段、雇佣蜂阶段、观察蜂阶段分别调整了搜索方程,设计出适合求解混合流水车间调度问题的离散人工蜂群算法（HIABC算法）.建立雇佣蜂、观察蜂和侦察蜂的搜索步骤,通过调度问题标准测试集进行数值实验,得到了较好的数值结果,验证了HIABC算法求解混合流水车间调度问题的有效性和稳定性.关键词：进化算法人工蜂群算法搜索方程离散化策略数据实验ABSTRACTABSTRACTThe traditional optimization method has been developing continuously.At the same time, evolutionary algorithm has sprung up and developed rapidly in the past20years.Based on Darwin’s evolutionary theory,evolutionary algorithm solves the problem by simulating the evolutionary process and mechanism of organisms.Evolutionary algorithm does not require optimization functions to satisfy certain condition or property and is easy to solve.It has become a research hot spot of the intelligence algorithms.Artificial bee colony algorithm is an evolutionary algorithm with higher speed and higher accuracy.The structure of the algorithm is simple and easy to implement.It has attracted the attention and research of many scholars.Artificial bee colony algorithm has been widely used to solve various optimization problems,such as linear approximation、engineering optimization、job shop scheduling and so on.In this paper,by improving the search equation of artificial bee colony algorithm on employed bees stage and onlooker bees stage,adding and adjusting the search structure, the performance of the algorithm is improved quickly.Artificial bee colony algorithm is applied to solve0-1knapsack problem,portfolio model based on conditional risk value,flow shop scheduling problem and so on,and good results are obtained.The main results are as follows:1.In order to increase the speed and search ability of the ABC algorithm,The search e-quations are improved.Improved artificial bee colony algorithm(IABC algorithm and NBC algorithm)are proposed.A large number of data experiments are carried out to verify the superiority of the improved search equation.In the search equations of the employed bees stage and the onlooker bees stage,the current search optimal solution is introduced into the search equations accordingly.Neighborhood Search Centers on the Current Global Optimal Solution.And using random search strategy to jump out of the local optimal solution,a better solution result is obtained.It improves the algorithm’s ability of random search,and balances the global search ability and the local search ability of the algorithm.The standard function set is used for testing,and a large number of numerical experiments are carried out. The results show that the improved artificial bee colony algorithms(IABC algorithm and NABC algorithm)have better advantages in terms of optimal value and solving speed.Then the improved search equation is applied to the differential evolution algorithm.The results show that the convergence speed of the improved differential evolution algorithm(IDE)is西安电子科技大学博士学位论文greatly improved.It is shown that the differential evolution algorithm is a relatively stable evolutionary algorithm in solving the optimal value of the problem.At the same time,it is shown again that the improved search equation is an excellent search method.2.The0-1knapsack problem is a widely used optimization problem.This paper tries to solve the0-1knapsack problem with IABC algorithm and get good data results.Based on the improved artificial bee colony algorithm(IABC algorithm),a discrete artificial bee colony algorithm(DIABC algorithm)is proposed by integrating and discretizing the search equa-tion.And it is used to solve the0-1knapsack problem.The standard test set of0-1knapsack problem is used to carry out numerical experiments,and a better optimal value is obtained. Solution time is relatively short.It is verified that the discrete artificial bee colony algorithm (DIABC algorithm)has good convergence and validity in solving0-1knapsack problem.3.In recent years,portfolio model has been deeply studied and widely applied in thefi-nancialfield.The improved artificial bee colony algorithm is applied to the CVaR portfolio optimization problem.And this paper analyzes the data with actual data.The results show that the model can reasonably diversify the market risk of portfolio.It can effectively im-prove the return on investment of investors.The calculation speed is better fast.It further illustrates the reliability and extensiveness of the improved artificial bee colony algorithm in solving practical problems.4.Flow shop scheduling problem is applied in all walks of life.It is mainly used to reduce working time,reduce working cost and improve working efficiency.On the basis of IABC algorithm framework,the search equation is adjusted for initialization stage,employed bees stage and onlooker bees stage respectively.A discrete artificial bee colony algorithm(HI-ABC algorithm)for solving hybridflow shop scheduling problem is designed.This paper stands establishing search procedures for employed bees,onlooker bees and scout bees. Through15classical examples,data experiments are carried out.And after repeated calcu-lations,good results are obtained.The effectiveness and stability of the improved discrete artificial bee colony algorithm(HIABC algorithm)for solving the hybridflow shop schedul-ing problem is demonstrated.Keywords:Evolutionary algorithm,Artificial bee colony algorithm,Search equation,Dis-cretization strategy,Data experiment插图索引1.1遗传算法基本流程图 (3)1.2分布估计算法基本流程 (10)2.1蜂群觅食过程图 (18)3.1f1−f4函数收敛曲线图(D=30) (28)3.2f5−f8函数收敛曲线图(D=30) (29)3.3f1−f4函数收敛曲线图(D=30) (37)3.4f5−f8函数收敛曲线图(D=30) (38)3.5f9−f10函数收敛曲线图(D=30) (42)3.6f1−f4函数收敛曲线图(D=30) (48)3.7f5−f8函数收敛曲线图(D=30) (49)3.8f9−f12函数收敛曲线图(D=30) (50)3.9f13−f16函数收敛曲线图(D=30) (51)4.1DIABC算法流程图 (62)5.1不同置信水平下算法搜索效果图 (74)表格索引3.1测试函数基本信息 (27)3.2ABC算法和IABC算法数据比较f1-f5 (31)3.3ABC算法和IABC算法数据比较f6-f10 (32)3.4GABC、EABC和IABC算法数据比较 (33)3.5DEs算法和IABC算法数据比较 (34)3.6PSOs算法和IABC算法数据比较 (34)3.7测试函数基本信息 (36)3.8ABC算法和NABC算法数据比较f1-f5 (39)3.9ABC和NABC算法数据比较f6-f11 (40)3.10GABC、EABC和NABC算法数据比较 (41)3.11ABC、EABC和NABC算法数据比较 (42)3.12ABC、IABC和NABC算法数据比较 (43)3.13DEs算法和NABC算法数据比较 (44)3.14PSOs算法和NABC算法数据比较 (44)3.15ABC算法和NABC算法求解用时比较 (45)3.16ABC算法和NABC算法求解用时比较 (45)3.17测试函数基本信息 (47)3.18DE算法和IDE算法数据比较f1-f4 (52)3.19DE和IDE算法数据比较f5-f8 (53)3.20DE和IDE算法数据比较f9-f12 (54)3.21DE和IDE算法数据比较f13-f16 (55)3.22ABC、EABC和IDE算法数据比较 (56)3.23IDE、IABC和NABC算法数据比较 (57)3.24DEs算法和IDE算法数据比较 (58)4.1测试函数基本信息表1 (63)4.2测试函数基本信息表2 (64)4.3测试函数基本信息表3 (64)4.4ABC算法和DIABC算法数据比较f1−f10 (65)4.5ABC算法和DIABC算法求得最优值数据比较f1−f10 (66)4.6ABC算法和DIABC算法数据比较f11−f18 (67)西安电子科技大学博士学位论文5.1所选股票期望收益率（R） (72)5.2PSO,GA,IABC算法搜索性能比较 (72)5.3最优个股权重 (73)6.1HIABC算法实验数据比较分析 (78)符号对照表符号符号名称min求解最小值s.t.约束条件D可行域R n实数域∥绝对值rand随机数⌈⌉取整Ω空间P概率分布∅空集X随机变量集∩交集∪并集∑求和∏求积lim求极限max取最大arg max取最大值点arg min取最小值点&且∈属于/∈不属于∃存在=不等于⊂包含于⊗and逻辑运算⊕xor逻辑运算缩略语对照表缩略语英文全称中文对照ABC算法Artificial bee colony algorithm人工蜂群算法ACO算法Ant Colony Optimization蚁群算法AFA算法Artificial Fish Algorithm人工鱼群算法AIS算法Artificial Immune System人工免疫算法BBO算法Biogeography-based Optimization生物地理学优化算法BFO算法Bacterial Foraging Optimization细菌觅食算法CRO算法Chemical Reaction Optimization化学反应优化算法CVaR Conditional Value at Risk条件风险价值DIABC算法Descreted improved artificial bee colony algorithm改进离散人工蜂群算法DE算法Differential evolution algorithm差分进化算法EDA算法Estimation of distribution algorithm分布估计算法GA算法Genetic algorithm遗传算法HFSP Hybridflow shop scheduling problem混合流水车间调度问题HIABC算法Hybrid improved artificial bee colony algorithm求解HFSP的人工蜂群算法HS算法Harmony Search Algorithm和声搜索算法IABC算法Improved artificial bee colony algorithm改进人工蜂群算法IDE算法Improved Differential evolution algorithm改进差分进化算法KHA算法Krill Herd Algorithm虾群算法NABC算法Novel artificial bee colony algorithm改进人工蜂群算法PMA算法Population Migration Algorithm人口迁移算法PSO算法Particle Swarm Optimization粒子群算法SFLA算法The shuffled frog leaping algorithm人工蛙跳算法VaR Value at Risk风险价值目录目录摘要 (I)ABSTRACT (III)插图索引 (VII)表格索引 (IX)符号对照表 (XI)缩略语对照表 (XIII)第一章绪论 (1)1.1研究背景 (1)1.2几种经典进化算法简介 (2)1.2.1遗传算法(GA) (2)1.2.2差分进化算法(DE) (7)1.2.3分布估计算法(EDA) (9)1.3进化算法的研究进展 (11)1.4主要内容与结构安排 (14)第二章人工蜂群算法概述 (17)2.1蜂群觅食行为 (17)2.2标准人工蜂群算法（ABC算法） (19)2.3人工蜂群算法的研究进展 (20)2.4本章小结 (23)第三章改进人工蜂群算法 (25)3.1IABC算法 (25)3.2数据实验 (26)3.2.1测试函数集 (26)3.2.2参数设置 (26)3.2.3实验结果 (26)3.3NABC算法 (30)3.4数据实验 (35)3.4.1测试函数集 (35)3.4.2参数设置 (36)3.4.3实验结果 (36)3.5IDE算法 (45)西安电子科技大学博士学位论文3.6数据实验 (46)3.6.1测试函数集 (46)3.6.2参数设置 (46)3.6.3实验结果 (46)3.7本章小结 (56)第四章改进人工蜂群算法求解0-1背包问题 (59)4.10-1背包问题 (59)4.2离散人工蜂群算法(DIABC算法) (60)4.3问题无约束转换 (61)4.4数据实验 (61)4.4.1测试函数集 (61)4.4.2参数设置 (62)4.4.3实验结果 (62)4.5本章小结 (64)第五章改进人工蜂群算法求解CVaR投资组合优化模型 (69)5.1条件风险价值（CVaR） (69)5.2改进人工蜂群算法(IABC算法) (71)5.3数据实验 (71)5.3.1数据选取 (71)5.3.2实验结果 (71)5.4本章小结 (73)第六章改进人工蜂群算法求解混合流水车间调度问题 (75)6.1混合流水车间调度问题(HFSP) (75)6.2离散人工蜂群算法(HIABC算法) (76)6.3数据实验 (77)6.3.1测试设置 (77)6.3.2实验结果 (77)6.4本章小结 (79)第七章结论与展望 (81)参考文献 (83)致谢 (96)作者简介 (98)第一章绪论第一章绪论1.1研究背景物流运输、生物医学、数据处理、投资组合等许多实际问题都涉及全局优化问题.一般地,全局优化问题可以描述为min f(x)s.t.x∈D⊂R n(1-1)其中f(x)为目标函数,x为决策变量,D为可行域.研究者们早期通过问题的性质(如:凸性、可微性、连续性等),用迭代搜索方法求得最优解(如:共轭梯度法、最速下降法、单纯形法等).但是我们知道全局最优问题一般都会有多个局部最优解,利用传统优化算法很容易陷入局部最优.怎样才能跳出局部最优,并快速有效地找到全局最优解,是很多学者一直关注的问题.如何判定找到的解为全局最优解,亦非易事.同时,随着问题维数的增加,在确保算法有效性的基础上,如何提高求解速度和效率也是一大难题.19世纪中后期,英国著名博物学家查尔斯·达尔文[1]在他的《进化论》中说,生物之间通过遗传、变异、竞争等,优胜略汰、适者生存.生物不断地进化着、发展着.种类由少到多,智力由低到高,结构从简单到复杂.在优胜略汰的自然选择中,适应环境的生物个体保留下来,并不断繁衍后代;同时生物个体也会随着环境的变化产生或多或少的优势变异来适应环境,逐渐改进,适者生存.因此,生物进化论的核心是优化,淘汰适应性差的个体,繁衍适应性强的个体.以上奠定了进化算法的理论基础.进化算法以达尔文的进化论为基础,通过模拟生物进化过程与机制来求解问题.近年来,进化算法已经成为人工智能的研究热点.在进化论的基础上，进化算法则相应地主要有选择、重组和变异三个操作步骤,进行逐步寻优,进而求出优化问题的最优解.进化算法主要包括遗传算法、遗传规划、进化规划和进化策略等.进化算法和传统优化算法都是迭代搜索算法,不同的是进化算法在寻优过程中,是从种群出发,一组一组的进行改进、优化,再通过交叉、变异等算子从改进的种群解出发再进行改进,适应值优的解被保留下来,适应值差的解被淘汰,进而求得最优解.进化计算可以根据不同条件、不同问题进行相应调整,具有很好的鲁棒性.在求解过程中,进化算法根据具体问题求解到比较满意的最优解.进化算法求解过程中用到的是目标函数值的信息,不考虑目标函数的具体性质(如:凸性、可微性、连续性等).进化算法的搜索过程中还会用到种群的随机信息,因此也是一种随机算法.进化西安电子科技大学博士学位论文算法为求解复杂优化问题和高维优化问题带来了崭新、有效的方法.相比传统优化算法,进化算法的应用比较广泛,求解问题可以是大规模、高维问题,并且求解过程具有较高的随机性和鲁棒性.随着进化算法队伍的壮大,算法研究的深入和创新,研究人员不断提出新的进化算法.并把算法运用到求解实际问题当中,产生了很大的影响,推动了工业、经济、社会的向前发展,加快了人工智能科学技术的发展.这些算法主要有:遗传算法（GA算法）[2]、差分进化算法(DE算法)[3]、蚁群算法(ACO算法)[4]、粒子群算法(PSO算法)[5]、分布式估计算法(EDA算法)[6]、和声搜索算法(HS算法)[7]、人工免疫算法(AIS算法)[8]、细菌觅食算法(BFO算法)[9]、人口迁移算法(PMA算法)[10]、人工鱼群算法(AFA算法)[11]、化学反应优化算法(CRO算法)[12]、生物地理学优化算法(BBO算法)[13][14]、人工蛙跳算法(SFLA算法)[15]、虾群算法(KHA算法)[16]、人工蜂群算法(ABC算法)[17]等.1.2几种经典进化算法简介本文第一章是进化算法的历史和基础,众多新型智能算法都是以遗传算法基本框架为基础的改进和提高,本文中的人工蜂群算法也不例外,作者学习进化算法就是以遗传算法为起点,然后把蚁群算法、粒子群算法、差分进化算法、和声搜索算法、生物地理优化算法、人工蜂群算法等进行了系统了解和学习的.了解遗传算法,对于读懂此篇论文的读者来说是一个基础和启发;最近几年,不管从应用还是算法改进,最广泛的就是差分进化算法,2019年有关差分进化算法的SCI发文量为智能算法之首,主要原因是算法搜索方程简单、高效，算法稳定性强,因此本文也简单介绍了此算法,并在第三章进行有效改进;分布估计算法一直以来是求解动态、多目标规划的有效方法,在实际应用当中发挥重要作用.作者博士第一年也尝试进行学习,并初步了解其基本知识点,希望把智能算法做得深一些,实用一些,不能只停留在连续函数、单目标、静态规划中,因此也是接下来要深度学习和进一步研究的重要内容.1.2.1遗传算法(GA)最早出现的进化算法是遗传算法[2],他是模拟生物进化过程的一种随机迭代搜索优化算法.遗传算法模仿生物的遗传、进化原理,并引入随机理论.在求解中,从初始变量种群出发,一代一代寻找问题最优解,直至满足收敛条件或终止迭代次数,它是一种迭代算法.与传统搜索算法不同,遗传算法从随机产生的初始种群解开始,在后续迭代中不断进化使得算法收敛于最好的解,它很可能就是问题的最优解或次优解.遗传算法主要通过交叉、变异、选择来实现的.遗传算法通过问题的适应度衡量各个个体的优劣程度,进而进行选择、淘汰.适应度对应于适应度函数,一般与具第一章绪论体求解问题有关.简单遗传算法的基本流程如图1.1.图1.1遗传算法基本流程图在实际计算过程中,遗传算法主要有下述几个步骤1.编码在确定了问题的目标函数和变量后,对变量进行编码,因为问题的解一般是用数字来表示的.编码方式可根据实际情况分为（1）二进制编码将一个二进制串(b0,b1,b2,···,b m)转化为区间[a,b]内对应的实数值xx=a+b−a2m+1·n∑i=1b i·2i(1-2)其中：m+1为二进制串的位数,x为对应的十进制实数.（2）实数编码二进制编码在对多维或者高精度函数问题求解最优值中,容易产生映射误差,因此用实数编码更加直接、便捷,且不存在解的精度问题.（3）格雷码编码格雷码编码的连续两个整数所对应的编码值之间仅仅只有一个码位是不同的,其余码位都完全相同.设一个二进制串(b m,b m−1,···,b2,b1),其对应的格雷码为G=(g m,g m−1,···,g2,g1),则{g m=b mg i=b i+1⊕b i,i=m−1,m−2,···,1(1-3)（4）符号编码在有些问题中,为了便于在遗传算法中利用所求问题的专门知识而产生了符号编码,符号可以是字符,也可以是数字,例如:旅行商问题,假设有n个城市分别记为: C1,C2,···,C n,则[C1,C2,···,C n]就可以构成一个旅行线路的个体.西安电子科技大学博士学位论文而具体使用哪种编码方式,要根据实际的优化问题来确定.2.遗传操作遗传操作是模拟生物基因进化的一种操作方法.遗传操作包括:选择,交叉,变异.（1）选择选择是从群体中选择优质个体并淘汰劣质个体的操作,是在适应值最优的基础上进行的,适应度越大,选择到的可能性越大.常用方法如下（i）轮盘赌选择法轮盘赌方法是目前最基本常用的根据适应值占比进行选取的选择方法.通过个体在种群中的适应值大小的占比,进行选择,一般是成正比的.即占比越大,被选取的概率就越大.个体被选概率p si为p si=f i∑Ni=1f i(1-4)其中N为种群个体数,个体适应度为f i.然后根据这个概率进行选择.（ii）最佳个体保留选择法把适应值最高的个体不进行交叉而直接保留到下一代中.这种方法容易导致局部最优,因此一般不单独使用.（iii）期望值选择法轮盘赌方法在选择个体时,容易把最优个体淘汰,为避免这种情况发生,引入了期望值法.1)M=f if =f i∑Ni=1f iN;2)通过M的整数部分决定个体被选中次数;3)M的小数部分则通过其它方法进行选择,选满为止.（iv）排序选择法根据个体适应值大小排序,基于排序号进行选择.（v）竞争选择法随机选择两个个体,选择适应度大的个体进入新一代,直至选满为止.f m=max(f i,f j)上述五种方法可以相互结合使用,以便提高搜索能力和避免局部最优的情况发生.为了提高GA性能,还有下述方法稳态繁殖:在迭代过程中,用部分优质个体（子代）更新目前群体中部分旧个体（父代）后,产生新一代群体.第一章绪论没有重串的稳态繁殖:在形成新一代群体时,使其中的个体均不重复.这样的好处是增大个体在群体中的分布区域,但增加了计算时间.(2)交叉交叉是指把两个父代个体的部分结构进行替换重组而生成新个体的操作,按照概率P c(0.6∼0.9)随机选取两个个体的操作.一般分为单点交叉:随机选定一个交叉点,两个个体在该点前后进行部分互换,产生新个体,如下000|11→000|01111|01→111|11两点交叉:与上述类似,只是随机地产生两个交叉点.多点交叉:上述两种交叉的推广.均匀交叉:由屏蔽字来决定是否进行交叉01011→0111000100→00001屏蔽字为:10101.屏蔽字为1的进行交叉,屏蔽字为0的不进行交叉.上述交叉方法可以结合使用来提高效果.(3)变异变异就是以很小的概率P m(P m<0.5)随机地改变群体中个体的某些值.对于种群中的个体的基因值,随机产生一个rand,若rand<P m,就进行变异操作,如下100101→100001变异操作是一种局部随机搜索,是一种防止算法早熟的措施.3.适应值函数一般来讲适应值函数视具体问题而定,在具体问题确定后,一般的适应值函数的确定原则为1)遗传算法搜索最大值要求;2)适应值非负的要求.确定适应值函数的方法有：一般方法、线性变换法、幂函数变换法和指数变换法.（1）一般方法最大化问题:F it(f(x))=f(x)最小化问题:F it(f(x))=−f(x)或:最大化问题:F it(f(x))=11+c+f(x),c≤0,c+f(x)≤0最小化问题:F it(f(x))=11+c−f(x),c≤0,c−f(x)≤0 c为目标函数的最大（小）估计.（2）线性变换法f′=α∗f+β其中:f avg=∑ni=1f iN,f max=C mult·f avg,C mult∈(1.2,2.0).则α=(C mult−1)·f avgf max−f avg ,β=(f max−C mult·f avg)·f avgf max−favg为了保证适应值的非负性,故α,β的调整如下α=f avgf avg−f min ,β=−f min·f avgf avg−fmin（3）幂函数变换法f′=f kk视具体问题而定,并经实验后才能确定.（4）指数变换法f′=e−αfα为复制强制指标,一般α越小,复制越趋向于最大适应度的个体.遗传算法的特点以及应用1)遗传算法利用变量的编码进行进化.2)遗传算法从多点出发寻找最优值.3)直接用适应度来进行最优判断.4)引用随机方法搜索和操作,提高搜索能力.5)并行性操作提高搜索区域.但是,遗传算法有两大缺点:欺骗问题、连锁问题.遗传算法表现优于传统优化设计.遗传算法打开了进化算法的大门,开启了进化算法的新篇章.其主要应用领域:优化求解、机器学习、模式识别、图像处理、优化控制、金融投资等,非常广泛.基本遗传算法描述如下Algorithm1遗传算法1:种群初始化;2:随机选取N个个体构成种群;3:从N个个体随机选择两个个体进行交叉;4:从N个个体随机选择一个个体进行变异;5:根据适应度满足终止条件,或者达到最大迭代次数为最终条件,终止.否则,转6;6:在新的个体中根据适应度，进行选择最优个体转入2.1.2.2差分进化算法(DE)美国Berkeley大学的Storn和Price于1997年受遗传算法的启发,提出了差分进化（differential evolution,DE）算法[3].差分进化算法的提出设想是为了求解切比雪夫多项式问题.DE算法通过群体内个体间的合作与竞争产生智能的搜索过程,它保留了遗传算法中基于种群的全局搜索策略,并采用实数编码,简化变异操作,降低算法复杂性.DE算法具有记忆功能,它可以通过动态跟踪当前的搜索状态进行相应的搜索策略的调整,因此有较好的随机性和鲁棒性.DE算法不需要问题的特征信息,结构简单,容易计算,通用性强.因此,它是一种高效的求解复杂优化问题的并行搜索随机优化算法.基本DE算法主要包含变异、交叉、选择三个算子步骤.在算法迭代过程中,三种算子分别对种群不断更新,直到满足迭代条件终止.DE算法的基本过程是:首先随机选取种群中的两个个体,再对两个个体进行差分和有限缩放,并与种群中的另一个个体相加得到新的个体;然后将新的个体与目标个体进行交叉操作产生一个新的个体;最后将得到的新个体与目标个体通过适应值进行比较,保留较优个体,并进入下一代种群中.接下来本文分别介绍差分进化算法中的三个算子:变异、交叉、选择.1.变异算子在每一代种群搜索过程中,变异算子为每一个个体x i产生一个变异个体t i,常见的几种变异操作如下•DE/rand/1t i=x r1+F∗(x r2−x r3)(1-5)•DE/best/1t i=x best+F∗(x r1−x r2)(1-6)•DE/rand/2t i=x r1+F∗(x r2−x r3)+F∗(x r4−x r5)(1-7)。

求解函数优化问题的改进人工蜂群算法唐凌芸;毛力;周长喜【期刊名称】《计算机科学与探索》【年(卷),期】2015(9)7【摘要】The standard artificial bee colony algorithm is limited in solving minimum function optimization prob-lems because of the poor local search ability, low computational precision of convengence and easily to fall to local optimum. Attempting to solve the problems emphasized above, this paper proposes an advanced artificial bee colony algorithm. This algorithm introduces chaos operator into the local search strategy of employed bees and onlooker bees, which is based on the current optimal solution. Also, this algorithm introduces bacterial chemotaxis behavior into onlooker bees to improve its local search ability. The simulation results of six test functions show that the algo-rithm can effectively avoid getting into local optimum, and the convergence accuracy is significantly improved.%标准人工蜂群算法由于局部搜索能力差，收敛精度低，容易陷入早熟收敛等缺陷，从而求解最小值函数优化问题的能力受到限制。