蚁群算法在连续函数优化求解中的应用

1一种用于快速全局优化的蚁群算法*摘要：针对蚁群算法不太适用于连续优化问题，且在搜索过程中容易陷入局部极值的缺点，提出了一种快速全局优化的改进蚁群算法，该算法同时采用在最好解蚂蚁领域内进行搜索及将本次循环得到的最优解作为起始解的搜索方式，以扩大其搜索范围，避免其陷入局部最优。通过对三个典型函数优化问题进行测试并与其他优化算法进行比较，结果表明该改进算法不仅能应用于对连续对象的优化，同时具有良好的全局优化性能，收敛速率快，寻优精度高。关键词：蚁群算法;全局优化;连续优化;局部极值中图分类号：TP301.6文献标识码：AANIMPROVEDANTCOLONYALGORITHMSOLVINGFASTGLOBALOPTIMIZATIONPROBLEMSAbstract:Aimtothedisadvantagesthatantcolonyoptimizationisnotappliedtocontinuousoptimizationproblemsandeasytogetintolocaloptimum,afastglobalantcolonyalgorithmisproposed.Inthisalgorithmthesearchingwaythatsearchesnearthebestsolutionandmakesthebestsolutionastheinitialsolutionisadoptedinordertowidensearchingscopetoavoidgettingintolocaloptimum,andthenitisappliedtotestsometypicalfunctions.Theresultthatcompareswithotheroptimizationsontestingthesefunctionsshowedthattheimprovedalgorithmisnotonlyappliedtocontinuousoptimizationproblems,butalsohasfastglobaloptimization,fastsearchingrateandhighoptimizingprecision.Keywords:Antcolonyalgorithm;Globaloptimization;Continuousoptimization;Localoptimum0引言全局优化问题在实际工程中有较广泛的应用价值，其求解方法（如自适应随机搜索]1[，遗传算法]2[，模拟退火算法]3[，蚁群算法等）也越来越受到人们的重视。其中蚁群算法采用分布式并行计算机制，具有较强的鲁棒性，容易于其它算法结合，因此比其它算法的应用性更广泛[4,5]。文献[6]针对蚁群算法不适用于连续问题的求解，提出了一种适用于连续域的改进蚁群算法，但仍然存在着容易陷入局部最优解，收敛速度慢的缺点，文献[7]针对蚁群算法易于陷入局部最优解的问题，对蚁群算法引入遗传算法，进行一定的改进，改进的算法能克服局部极值问题，但收敛速度不够快。由于蚁群算法存在着上述这些缺点，制约着它向众多领域的进一步推广应用。为了克服这些问题，本文提出了一种改进蚁群算法，该算法同时采用在最好解蚂蚁的领域内进行搜索及将本次循环得到的最优解作为下次循环起始解的搜索方式。通过有效扩大其搜索范围来避免陷入局部最优问题，在一定程度上提高了蚁群算法的优化质量和收敛效率，并利用该算法对三个典型优化函数进行测试，结果进一步证明了该算法的有效性。1蚁群算法蚁群算法[8](ACO)是由意大利学者Dorigo等人在九十年代提出的，用于解决组合优化问题的一种随机搜索算法。该算法的原理是基于蚂蚁在寻找食物的过程中，会在所经路径释放一种化学物质（即信息素），蚂蚁之间的交流就是依靠这种物质，凭借残留在路径上信息素量的大小，蚂蚁总能找到一条从食物源与蚁巢的最短路径。现以著名的双桥实验来说明蚁群算法的原理，假定所有蚂蚁从蚁巢到食物源的路径有两条，开始时两条分支上都不存在信息素，蚂蚁对这两条分支的选择不存在任何偏向性，并以相同的概率进行选择。由于蚂蚁在所经过的路径上会释放信息素，那么会有更多的蚂蚁选择短路径，短路径上的信息素量就越多，而这种高浓度的信息素将促使更多的蚂蚁选择这条分支，最终所有的蚂蚁都集中到这条分支上。其中每一只蚂蚁的选择都是根据路径上信息素量大小决定的。一般来说，蚁群算法可以认为是三个过程的相互作用：初始化参数、蚂蚁构建解、更新信息素。第一个步骤，主要是信息素和各参数的初始*辽宁省创新团队项目资助（NO.2006T089）2化；第二个步骤，每一个蚂蚁根据转移概率准则来选择下一地点，直到创建一个完整路径，其中转移概率是分支上信息素的函数；第三个步骤，信息素的更新，它的更新规则有两种：(a)信息素的挥发，它有助于搜索更好解，“忘记”先前的较差解。信息素蒸发公式如下：ijij1(1)式中ij表示在路径ij上的信息素大小，代表信息素的挥发系数，1代表信息素的残留系数。(b)信息素的增加，它与蚂蚁所经路径长度成正比。mkkijijij1(2)式中m表示蚂蚁数，kij表示第k只蚂蚁在路径ij上信息素增量，ij表示路径ij上的信息素大小。2基于蚁群算法的全局优化方法在优化函数中求解一个全局极值问题即要找一点Sxmin，满足对于区间S中的任意一点x，都有)()(minxfxf成立。其中解空间是一种区域性的表示，而不是离散的点。所以在连续空间寻优问题求解中，蚁群选择行进方式的依据不是各点的信息素大小，而是某个区域信息素对该蚂蚁的影响。2.1蚁群初始位置确定及信息素初始化本文以求取最小值为例说明改进蚁群算法，设优化函数：),(),(min21nxxxxxfy的取值范围为2],[nES，蚁群规模为m，在优化空间内随机地放置m个蚂蚁，作为每个蚂蚁进行搜索的起点。当蚂蚁数为m时，各个子区间的长度为njmjSjEjL2,1,)()()((3)蚂蚁i的初始位置分布为：)))(),(()),2(),2(()),1(),1(((nEnSrandESrandESrandxi(4)式中))(),((jEjSrand为区间)](),([jEjS上的一个随机数。根据蚂蚁所在位置的分布情况，按照寻优问题的不同来确定蚂蚁i的初始信息素大小)()(iXfkait(5)式中a，k为大于零的数。若为函数最小值寻优，取1a(可取ea)；若为函数最大值寻优，取10a。对于最小值优化问题，目标函数值)(ixf越小，则ix在所在位置留下的信息素就越多；而对于最大值优化问题，目标函数值)(ixf越大，则ix在所在位置留下的信息素就越多。2.2蚂蚁移动规则每只蚂蚁在完成本次搜索后，会根据相应的移动规则进行下次搜索。本文提出的改进蚁群算法中，蚁群在完成本次循环后，将本次循环得到的最优解作为其它蚂蚁下次循环时的起始位置，蚂蚁的移动规则分为两部分：一是将上次循环中没有找到最优解的蚂蚁向最优解移动；另一部分是指让获得最优解的蚂蚁在最优解领域进行搜索，以便找到更好解。下面分别介绍这两种移动规则：规则1：完成本次循环后，蚂蚁ix将向上次循环中找到最优解的蚂蚁)(bestx进行转移。转移概率公式如下：)())()((),(besttitbestteebestip(6)式中)(it表示蚂蚁i处的信息素，)(bestt表示蚂蚁在最优解处的信息素。蚂蚁在向最优解移动的过程中，可能会找到更优的解，设第i只蚂蚁向最好位置处转移的步长为：其它,)1,1(),(),(0Lrandxpbestipxxxxiibestii(7)式中100p，10。规则2：在上次循环过程中获得最优解的蚂蚁bestx，在该解的领域范围内进行搜索。若新的位置比原来的位置更优，则用新的位置取代原来的位置；反之，则保留原来的位置。搜索步长应随着迭代次数的增加而减少，以便在以后的搜索中能够得到更精确的解。移动公式如下：其它,)()(,besttbestbestxbestttbesttxx(8)式中tbestx代表当前的最优解。移动步长公式如下：边，当前解在最优解的右边，当前解在最优解的左dxxdxxxbestbesttbest(9)式中dx为步长，在完成本次搜索后，1.0，使搜索步长逐渐减小，提高解的质量。2.3信息素更新规则3在完成上述搜索后，将对蚂蚁i处的信息素进行更新，更新规则如下：)()()(ititit(10)式中为信息素挥发系数，10，)()(ixfkait。2.4改进蚁群算法流程1)根据具体优化问题确定最大循环次数I和蚂蚁数m。确定变量的取值范围，按照公式(3)到(5)初始化蚁群所在位置及信息素大小。2)每只蚂蚁根据所在位置的信息素大小，搜索出本次循环中获得最好解的蚂蚁位置bestx。3)每只蚂蚁以先前找到的最好解bestx作为起点，按公式(6)到(7)进行搜索。4)获得最好解的蚂蚁位置bestx以公式(8)到(9)在其附近领域进行搜索，更新当前解的位置。5)对所有的蚂蚁在完成本次搜索后，按公式(10)进行信息素的更新。重复第2)步，直到满足停止条件。3仿真实验为了验证所提出改进蚁群算法的有效性，本文选取了三个不同类型的函数进行测试。3.1实验1采用一个一维函数来验证所提蚁群算法的有效性，所选的测试函数如下：)1(33)1()(min22xifxxifxxf该函数的曲线图如图1所示，从图中我们可以很清晰地看到该函数有两个极小值点，x=0和x=3处。其中x=0很明显是局部极小值点，而x=3是全极小值点。-5-4-3-2-1012345-50510152025xf(x)图1测试函数1的曲线图Figure1Curveoftestfunction1我们分别采用改进蚁群算法和自适应随机搜索算法对测试函数1进行寻优。在改进蚁群算法中，设定循环次数为20，蚁群规模为5，变量取值范围为[-55]，9.0，通过搜索寻优，经过循环20次，得到了最小值解。优化结果如表1所示。算法最优点最小值训练次数ARSET3.000324-2.999999840ACO3-3.00000120表1ARSET与ACO的优化结果比较Table1ComparingresultviaARSETandACO通过与自适应随机搜索算法的比较可知，蚁群算法只需循环20次就得到较好的解，而自适应随机搜索算法需要迭代40次。优化结果表明，改进的蚁群算法不仅可以应用于对连续问题的求解，同时又能较快地搜索到最好解，且不易陷入局部极值。3.2实验2采用一个二维函数来对改进蚁群算法进行验证，测试函数如下：yxyxf1),(该函数的曲线如图2所示，该图像为函数y[-1010]范围，x[-1010]范围的图形。从图中可以看到，该图像为一凸凹不平的曲面，从图中不能准确地找到最小值点。-10-50510-10-50510-10-50510xyf(x,y)图2测试函数2的图像Figure2Curveoftestfunction2我们分别采用改进蚁群算法和自适应随机搜索算法对测试函数2进行寻优，在改进蚁群算法中，首先设定循环次数为100，蚁群规模为20，变量取值范围为y[-1010]，x[-1010]，9.0，进行搜索寻优，经过循环100次，搜索到了最小值解。我们再次设定循环次数为150，200次，比较其与自适应随机搜索算法的搜索结果，优化结果如表2所示。4表2ARSET与ACO的优化结果比较Table2ComparingresultviaARSETandACO从表2中可知，对于同样的迭代次数，所提出的改进蚁群算法比自适应随机搜索方法的收敛效果好，搜索到的解的精度高，与真实解的误差小。3.3实验3甲醛生产过程成本优化]9[对于甲醛生产装置来说，直接的优化目标函数是总的生产成本，生产状况主要是由四个指标反映：反应温度T，氧醇