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

《蚁群算法在连续函数优化求解中的应用.doc》由会员分享，可在线阅读，更多相关《蚁群算法在连续函数优化求解中的应用.doc（5页珍藏版）》请在三一办公上搜索。

1、一种用于快速全局优化的蚁群算法* 摘 要：针对蚁群算法不太适用于连续优化问题，且在搜索过程中容易陷入局部极值的缺点，提出了一种快速全局优化的改进蚁群算法，该算法同时采用在最好解蚂蚁领域内进行搜索及将本次循环得到的最优解作为起始解的搜索方式，以扩大其搜索范围，避免其陷入局部最优。通过对三个典型函数优化问题进行测试并与其他优化算法进行比较，结果表明该改进算法不仅能应用于对连续对象的优化，同时具有良好的全局优化性能，收敛速率快，寻优精度高。关键词：蚁群算法; 全局优化; 连续优化; 局部极值中图分类号： TP301. 6 文献标识码：A AN IMPROVED ANT COLONY ALGORITH

2、M SOLVING FAST GLOBAL OPTIMIZATION PROBLEMSAbstract: Aim to the disadvantages that ant colony optimization is not applied to continuous optimization problems and easy to get into local optimum, a fast global ant colony algorithm is proposed. In this algorithm the searching way that searches near the

3、 best solution and makes the best solution as the initial solution is adopted in order to widen searching scope to avoid getting into local optimum, and then it is applied to test some typical functions. The result that compares with other optimizations on testing these functions showed that the imp

4、roved algorithm is not only applied to continuous optimization problems, but also has fast global optimization, fast searching rate and high optimizing precision.Keywords: Ant colony algorithm; Global optimization; Continuous optimization; Local optimum 50 引言全局优化问题在实际工程中有较广泛的应用价值，其求解方法（如自适应随机搜索，遗传算法

5、，模拟退火算法，蚁群算法等）也越来越受到人们的重视。其中蚁群算法采用分布式并行计算机制，具有较强的鲁棒性，容易于其它算法结合，因此比其它算法的应用性更广泛4, 5。文献6针对蚁群算法不适用于连续问题的求解，提出了一种适用于连续域的改进蚁群算法，但仍然存在着容易陷入局部最优解，收敛速度慢的缺点，文献7针对蚁群算法易于陷入局部最优解的问题，对蚁群算法引入遗传算法，进行一定的改进，改进的算法能克服局部极值问题，但收敛速度不够快。由于蚁群算法存在着上述这些缺点，制约着它向众多领域的进一步推广应用。* 辽宁省创新团队项目资助（NO. 2006T089）为了克服这些问题，本文提出了一种改进蚁群算法，该算法

6、同时采用在最好解蚂蚁的领域内进行搜索及将本次循环得到的最优解作为下次循环起始解的搜索方式。通过有效扩大其搜索范围来避免陷入局部最优问题，在一定程度上提高了蚁群算法的优化质量和收敛效率，并利用该算法对三个典型优化函数进行测试，结果进一步证明了该算法的有效性。1 蚁群算法蚁群算法8(ACO)是由意大利学者Dorigo等人在九十年代提出的，用于解决组合优化问题的一种随机搜索算法。该算法的原理是基于蚂蚁在寻找食物的过程中，会在所经路径释放一种化学物质（即信息素），蚂蚁之间的交流就是依靠这种物质，凭借残留在路径上信息素量的大小，蚂蚁总能找到一条从食物源与蚁巢的最短路径。现以著名的双桥实验来说明蚁群算法的

7、原理，假定所有蚂蚁从蚁巢到食物源的路径有两条，开始时两条分支上都不存在信息素，蚂蚁对这两条分支的选择不存在任何偏向性，并以相同的概率进行选择。由于蚂蚁在所经过的路径上会释放信息素，那么会有更多的蚂蚁选择短路径，短路径上的信息素量就越多，而这种高浓度的信息素将促使更多的蚂蚁选择这条分支，最终所有的蚂蚁都集中到这条分支上。其中每一只蚂蚁的选择都是根据路径上信息素量大小决定的。一般来说，蚁群算法可以认为是三个过程的相互作用：初始化参数、蚂蚁构建解、更新信息素。第一个步骤，主要是信息素和各参数的初始化；第二个步骤，每一个蚂蚁根据转移概率准则来选择下一地点，直到创建一个完整路径，其中转移概率是分支上信息

8、素的函数；第三个步骤，信息素的更新，它的更新规则有两种：(a) 信息素的挥发，它有助于搜索更好解，“忘记”先前的较差解。信息素蒸发公式如下： (1) 式中表示在路径ij上的信息素大小，代表信息素的挥发系数，代表信息素的残留系数。(b) 信息素的增加，它与蚂蚁所经路径长度成正比。 (2) 式中m表示蚂蚁数，表示第k只蚂蚁在路径ij上信息素增量，表示路径ij上的信息素大小。2 基于蚁群算法的全局优化方法在优化函数中求解一个全局极值问题即要找一点，满足对于区间S中的任意一点，都有成立。其中解空间是一种区域性的表示，而不是离散的点。所以在连续空间寻优问题求解中，蚁群选择行进方式的依据不是各点的信息素大

9、小，而是某个区域信息素对该蚂蚁的影响。2.1 蚁群初始位置确定及信息素初始化本文以求取最小值为例说明改进蚁群算法，设优化函数：的取值范围为，蚁群规模为m，在优化空间内随机地放置m个蚂蚁，作为每个蚂蚁进行搜索的起点。当蚂蚁数为m时，各个子区间的长度为 (3) 蚂蚁的初始位置分布为： (4) 式中为区间上的一个随机数。根据蚂蚁所在位置的分布情况，按照寻优问题的不同来确定蚂蚁i的初始信息素大小 (5) 式中，为大于零的数。若为函数最小值寻优，取(可取)；若为函数最大值寻优，取。对于最小值优化问题，目标函数值越小，则在所在位置留下的信息素就越多；而对于最大值优化问题，目标函数值越大，则在所在位置留下的

10、信息素就越多。2.2 蚂蚁移动规则每只蚂蚁在完成本次搜索后，会根据相应的移动规则进行下次搜索。本文提出的改进蚁群算法中，蚁群在完成本次循环后，将本次循环得到的最优解作为其它蚂蚁下次循环时的起始位置，蚂蚁的移动规则分为两部分：一是将上次循环中没有找到最优解的蚂蚁向最优解移动；另一部分是指让获得最优解的蚂蚁在最优解领域进行搜索，以便找到更好解。下面分别介绍这两种移动规则：规则1：完成本次循环后，蚂蚁将向上次循环中找到最优解的蚂蚁进行转移。转移概率公式如下： (6) 式中 表示蚂蚁i处的信息素，表示蚂蚁在最优解处的信息素。蚂蚁在向最优解移动的过程中，可能会找到更优的解，设第i只蚂蚁向最好位置处转移的

11、步长为： (7) 式中，。规则2： 在上次循环过程中获得最优解的蚂蚁，在该解的领域范围内进行搜索。若新的位置比原来的位置更优，则用新的位置取代原来的位置；反之，则保留原来的位置。搜索步长应随着迭代次数的增加而减少，以便在以后的搜索中能够得到更精确的解。移动公式如下： (8)式中代表当前的最优解。移动步长公式如下：(9) 式中为步长，在完成本次搜索后，使搜索步长逐渐减小，提高解的质量。2.3 信息素更新规则在完成上述搜索后，将对蚂蚁i处的信息素进行更新，更新规则如下： (10) 式中为信息素挥发系数，。2.4 改进蚁群算法流程1) 根据具体优化问题确定最大循环次数I和蚂蚁数m。 确定变量的取值范

12、围，按照公式(3)到(5)初始化蚁群所在位置及信息素大小。2) 每只蚂蚁根据所在位置的信息素大小，搜索出本次循环中获得最好解的蚂蚁位置。3) 每只蚂蚁以先前找到的最好解作为起点，按公式(6)到(7)进行搜索。4) 获得最好解的蚂蚁位置以公式(8)到(9)在其附近领域进行搜索，更新当前解的位置。5) 对所有的蚂蚁在完成本次搜索后，按公式(10)进行信息素的更新。重复第2)步，直到满足停止条件。3 仿真实验为了验证所提出改进蚁群算法的有效性，本文选取了三个不同类型的函数进行测试。3.1 实验1采用一个一维函数来验证所提蚁群算法的有效性，所选的测试函数如下： 该函数的曲线图如图1所示，从图中我们可以

13、很清晰地看到该函数有两个极小值点，x=0和x=3处。其中x=0很明显是局部极小值点，而x=3是全极小值点。图 1 测试函数1的曲线图Figure 1 Curve of test function 1我们分别采用改进蚁群算法和自适应随机搜索算法对测试函数1进行寻优。在改进蚁群算法中，设定循环次数为20，蚁群规模为5，变量取值范围为-5 5，通过搜索寻优，经过循环20次，得到了最小值解。优化结果如表1所示。算法 最优点 最小值 训练次数 ARSET 3.000324 -2.9999998 40ACO 3 -3.000001 20表1 ARSET与ACO的优化结果比较Table 1 Comparin

14、g result via ARSET and ACO通过与自适应随机搜索算法的比较可知，蚁群算法只需循环20次就得到较好的解，而自适应随机搜索算法需要迭代40次。优化结果表明，改进的蚁群算法不仅可以应用于对连续问题的求解，同时又能较快地搜索到最好解，且不易陷入局部极值。3.2 实验2 采用一个二维函数来对改进蚁群算法进行验证，测试函数如下： 该函数的曲线如图2所示，该图像为函数y-10 10范围，x-10 10范围的图形。从图中可以看到，该图像为一凸凹不平的曲面，从图中不能准确地找到最小值点。图2 测试函数2的图像Figure 2 Curve of test function 2我们分别采用改

15、进蚁群算法和自适应随机搜索算法对测试函数2进行寻优，在改进 蚁群算法中，首先设定循环次数为100，蚁群规模为20，变量取值范围为y-10 10，x -10 10，进行搜索寻优，经过循环100次，搜索到了最小值解。我们再次设定循环次数为150，200次，比较其与自适应随机搜索算法的搜索结果，优化结果如表2所示。算法 最优x 最优y 最优f(x, y) 训练次数ARSET -9.9968 3.46E-009 -9.9968 100ACO -9.9989 2.01E-004 -9.9989 100ARSET -9.9996 -2.08E-018 -9.9996 150ACO -9.9999 -6.0

16、5E-008 -9.9999 150ARSET -10 6.67E-008 -10 200ACO -10 8.07E-011 -10 200表2 ARSET与ACO的优化结果比较Table 2 Comparing result via ARSET and ACO从表2中可知，对于同样的迭代次数，所提出的改进蚁群算法比自适应随机搜索方法的收敛效果好，搜索到的解的精度高，与真实解的误差小。3.3 实验3 甲醛生产过程成本优化对于甲醛生产装置来说，直接的优化目标函数是总的生产成本，生产状况主要是由四个指标反映：反应温度T，氧醇分子比E，蒸汽量G和空速V。在实际生产中，空速是固定不变的，此时T，E，G

17、中有两个是独立变量，只要确定其中任意两个，另一个就唯一确定。因此所要解决的优化问题可以描述为下式： 其中S为反应单耗，反应温度T的变化范围为 ，氧醇分子比E的变化范围为对于该优化问题，其目标函数值即反应单耗S与氧醇比E，反应温度T 的大致函数关系如图3所示。图3 甲醛生产过程成本优化函数图像Figure3 Curve of the cost function on produce process of formaldehyde针对该优化问题，分别采用改进蚁群算法和遗传算法对其进行优化，在遗传算法中，参数E和T的编码二进制串长取16位，所使用的遗传参数为：群体大小为50，淘汰率为0.02，变异率

18、为0.01，交叉率为0.06，迭代次数分别为10，20次。在蚁群算法中，设蚂蚁数分别为20，30，变量E，T的变化范围如图3，循环次数为100，。两种算法的优化结果比较如表3所示。项目遗传代数g=10 g=20蚁群数目m=20 m=30最优反应温度T538.54 638.65640.89 645.41最优氧醇比E0.4038 0.40350.3891 0.3754最小单耗S437.59 437.39431.74 429.87表3 改进蚁群算法与遗传算法对甲醛生产过程成本优化结果的比较Table 3 Comparing result via GA and ACO on the cost func

19、tion on produce process of formaldehyde从表3可以看出，改进蚁群算法的优化效果明显优于标准遗传算法，优化结果最小单耗更小。遗传算法的迭代次数比蚁群算法的循环次数要少，但是简单凭借迭代次数不能准确反映算法的搜索速度和效果，还要结合解空间搜索过的可行解的个数，改进蚁群算法能进行全局优化，避免早收敛现象，从而达到更好的优化结果。4 结论本文中提出了一种利用蚁群算法来实现全局优化的方法。通过测试并与其他优化算法相比较，可以很清晰地看到该算法的优越性。但它也存在一些不足，若将其与遗传算法，禁忌搜索，模拟退火及神经网络等结合构成混合算法，将会有更广阔的应用前景。参考文

20、献1 C. Hamzacebi, F. Kutay. A heuristic approach for finding the global minimum: adaptive random search techniqueJ. Applied Mathematics and Computation, 2005, pp: 427-444.2 涂承媛; 涂承宇. 一种新的收敛于全局最优解的遗传算法J. 信息与控制, 2001, 30(2): 116-119.3 王华, 唐国金. 函数优化问题的一种异步并行模拟退火算法J. 控制与决策, 2005, 20(5): 579-582.4 M. Dura

21、n Toksari. Ant colony optimization for finding the global minimumJ, Applied Mathematics and Computation, 2006, pp: 308-316.5 段海滨, 王道波. 一种快速全局优化的改进蚁群算法及仿真J. 信息与控制, 2004, 33(2): 241-244.6 汪镭, 吴启迪. 蚁群算法在连续空间寻优问题求解中的应用J. 控制与决策, 2003, 18(1):45-48,52.7 潘丰, 李海. 连续函数优化的一种新方法蚁群算法J. 计算机测量与控制, 2005, 13(3): 270-272.8 张军, 胡晓敏, 罗旭耀. 蚁群优化M. 北京: 清华大学出版社,2007:1-1159 王强, 邵惠鹤. 遗传算法在甲醛生产过程优化中的应用J. 控制理论与应用, 1996, 13(4):477-481.