一种基于蚁群算法的信息素更新方法

IPRDB

API 数据接口

专利申请

使用指引 chat嘟嘟

会员体验

联系我们

交流群

现在联系顾问~

一种基于蚁群算法的信息素更新方法
申请号	CN201610555497.2	申请日	2016-07-14	公开(公告)号	CN106156893A	公开(公告)日	2016-11-23
申请人	陕西科技大学;			发明人	夏田; 王娜; 胡传波; 折贝;
摘要	本发明涉及一种基于蚁群算法的信息素更新方法，包括如下步骤：步骤1，路径长度排列；步骤2，计算路径总和；步骤3，路径总和与各代路径对应成比例排列；步骤4，最大最小相乘取最小，更新信息素。本发明经过大量实验验证，以算法运行时间和迭代收敛为判断标准，结果应用较小的时间成本，在求解过程中不断的跳出局部最优得到新解，加快了算法寻优时的收敛速度，使得优化效率逐渐提高。
权利要求	1.一种基于蚁群算法的信息素更新方法，其特征在于，包括如下步骤：步骤1，路径长度排列，所述路径长度排列是将每一次迭代的路径长度按照从小到大的顺序排列，即L11，L12...Lq1,Lq2。。。Lqi,Ln1...Lnm；步骤2，计算路径总和，所述路径总和是对步骤1中获取的各代路径长度相加求总和；步骤3，路径总和与各代路径对应成比例排列，所述路径总和与各代路径对应成比例排列是基于步骤1和步骤2中得到的路径长度排列、路径总和，通过各代路径与路径总和对应成比例，按照从大到小排列；步骤4，最大最小相乘取最小，更新信息素。 2.根据权利要求1所述的一种基于蚁群算法的信息素更新方法，其特征在于，所述最大最小相乘取最小，更新信息素是基于步骤1—3处理后得到的路径长度排列、路径总和、路径与路径总和对应比例，规定同一种路径在N次内没有变化时，信息素更新方法为：将步骤1得到的各代路径赋值于向量A，则设路径长度向量A＝[L11，L12...Lq1,Lq2。。。Lqi,Ln1...Lnm]，各代路径长度总和M，各代路径与路径总和成比例排列则Lq信息素更新为: 其中Lnm表示第n种路径长度出现m次，Lq1Lqi与LqiLq1有可能相等。 3.根据权利要求1所述的一种基于蚁群算法的信息素更新方法，其特征在于，所述同一种路径为路径长度相等。 4.根据权利要求1所述的一种基于蚁群算法的信息素更新方法，其特征在于，在步骤1中，所述的路径长度均赋值于向量A,都属于向量A中的一个元素。 5.根据权利要求2所述的一种基于蚁群算法的信息素更新方法，其特征在于，在步骤4中，当N＝1时，无需取最小，1＜N＜J,J是每次迭代中同一种路径出现的最大次数。
说明书全文	一种基于蚁群算法的信息素更新方法技术领域 [0001] 本发明涉及计算机技术领域，特别是涉及一种基于蚁群算法的信息素更新方法。背景技术 [0002] 目前，基于路径优化算法有很多，常见的路径优化算法有遗传算法、粒子群算法，模拟退火算法等。 [0003] 遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索出，但是编程较复杂，需先编码在解码，局部搜索能力较差，易产生早熟收敛，导致单纯的遗传算法比较费时，在进化后期搜索效率较低。 [0004] 粒子群算法一方面规则简单，容易实现，可调参数少，并且对于参数的选择已经有成熟的理论研究成果，另一方面对于离散的优化问题处理不佳，容易陷入局部最优。 [0005] 模拟退火算法虽具有摆脱局部最优解的能力，能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。但是，由于模拟退火算法对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，使得模拟退火算法的运算效率不高。模拟退火算法对参数(如初始温度)的依赖性较强，且进化速度慢。 [0006] 遗传算法局部搜索能力差，耗时且难以达到问题最优解；粒子群算法的全局搜索能力差，易陷入局部最优；模拟退火算法运算效率不高，不仅费时而且进化速度慢。发明内容 [0007] 为了克服上述现有技术的不足，本发明提供了一种基于蚁群算法的信息素更新方法，按照最大最小相乘取最小更新信息素，减少了算法运行的时间，提高求解过程中不断的跳出局部最优得到新解的能力，加快了算法寻优时的收敛速度。 [0008] 一种基于蚁群算法的信息素更新方法，包括如下步骤： [0009] 步骤1，路径长度排列，所述路径长度排列是将每一次迭代的路径长度按照从小到大的顺序排列，即L11，L12...Lq1,Lq2。。。Lqi,Ln1...Lnm； [0010] 步骤2，计算路径总和，所述路径总和是对步骤1中获取的各代路径长度相加求总和； [0011] 步骤3，路径总和与各代路径对应成比例排列， [0012] 所述路径总和与各代路径对应成比例排列是基于步骤1和步骤2中得到的路径长度排列、路径总和，通过各代路径与路径总和对应成比例，按照从大到小排列； [0013] 步骤4，最大最小相乘取最小，更新信息素。 [0014] 在本发明的一个优选实施例中，所述最大最小相乘取最小，更新信息素是基于步骤1—3处理后得到的路径长度排列、路径总和、路径与路径总和对应比例，规定同一种路径在N次内没有变化时，信息素更新方法为： [0015] 将步骤1得到的各代路径赋值于向量A，则设路径长度向量A＝[L11，L12...Lq1,Lq2。。。Lqi,Ln1...Lnm]，各代路径长度总和M，各代路径与路径总和成比例排列[0016] 则Lq信息素更新为: [0017] 其中Lnm表示第n种路径长度出现m次，Lq1Lqi与LqiLq1有可能相等。 [0018] 在本发明的一个优选实施例中，所述同一种路径为路径长度相等。 [0019] 在本发明的一个优选实施例中，在步骤1中，所述的路径长度均赋值于向量A,都属于向量A中的一个元素。 [0020] 在本发明的一个优选实施例中，在步骤4中，当N＝1时，无需取最小，1＜N＜J,J是每次迭代中同一种路径出现的最大次数。 [0021] 本发明的有益效果为； [0022] 本发明经过大量实验验证，以算法运行时间和迭代收敛为判断标准，结果应用较小的时间成本，在求解过程中不断的跳出局部最优得到新解，加快了算法寻优时的收敛速度，使得优化效率逐渐提高。附图说明 [0023] 图1为某次实验各代路径与迭代次数关系图。附图说明 [0024] [0025] 蚁群算法核心思想是，蚂蚁在寻找食物的前行过程中会不断释放一种物质即信息素，后面的蚂蚁选择路径时根据前面蚂蚁留在路径上的信息素浓度大小做判断，路径选择概率与信息素浓度成正比。 [0026] 结合图1，为某次实验各代路径与迭代次数关系图，具体地： [0027] 一种基于蚁群算法的信息素更新方法，包括如下步骤： [0028] 步骤1，路径长度排列，所述路径长度排列是将每一次迭代的路径长度按照从小到大的顺序排列，即L11，L12...Lq1,Lq2。。。Lqi,Ln1...Lnm； [0029] 步骤2，计算路径总和，所述路径总和是对步骤1中获取的各代路径长度相加求总和； [0030] 步骤3，路径总和与各代路径对应成比例排列， [0031] 所述路径总和与各代路径对应成比例排列是基于步骤1和步骤2中得到的路径长度排列、路径总和，通过各代路径与路径总和对应成比例，按照从大到小排列； [0032] 步骤4，最大最小相乘取最小，更新信息素：所述最大最小相乘取最小，更新信息素是基于步骤1—3处理后得到的路径长度排列、路径总和、路径与路径总和对应比例，规定同一种路径(即路径长度相等)在N次内没有变化时，信息素更新方法为： [0033] 将步骤1得到的各代路径赋值于向量A，则设路径长度向量A＝[L11，L12...Lq1,Lq2。。。Lqi,Ln1...Lnm]，各代路径长度总和M，各代路径与路径总和成比例排列[0034] 则Lq信息素更新为: [0035] 其中Lnm表示第n种路径长度出现m次，Lq1Lqi与LqiLq1有可能相等。 [0036] 具体地，在步骤1中，所述的路径长度均赋值于向量A,都属于向量A中的一个元素。 [0037] 进一步地，在步骤4中，当N＝1时，无需取最小，1＜N＜J,J是每次迭代中同一种路径出现的最大次数。 [0038] 本发明根据蚁群算法核心思想，对信息素进行更新，从而能够降低算法运行时间，提高不断跳出局部最优寻找更优值得能力，增强算法收敛速度。