内容发布更新时间 : 2024/5/2 6:15:32星期一 下面是文章的全部内容请认真阅读。

减少到了O(N)级别，整个程序的时间复杂度为O(N^3)而且常系数也很低。

2、蚁群选址算法

蚁群算法，又称蚂蚁算法，是一种模拟进化算法，由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。该算法是群集智能的典型实现，不仅能够智能搜索、全局优化、而且具有强鲁棒性、正反馈机制等特点，求解结果不依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。基本思路是：多只蚂蚁利用信息素传递信息，经过多代循环后积累了足够的信息，便可以选择出较优秀的选址方案。

2.1基本算法

蚁群算法最重要的两步就是信息素的更新和轮盘方法选择最佳位置，前者保证了算法朝更优的方案前进，后者保证了算法具有随机性，否则算法将会快速收敛，得不到优秀的选址方案。

轮盘方法的实现：

随机产生一个0-1的阈值，将每个目标位置的概率累加，直到某个位置累和超过了阈值，

则该位置就是这次选中的位置，可见一个概率越大的位置，在某一次加上它，值超过阈值的概率越大。这就类似于轮盘游戏，一个区域对应的角度越大，选中该区域的概率越大。（初期没有意识到这个随机方法的重要性，导致结果快速收敛） 信息素更新：

信息素更新，包括信息素衰减和信息素增加的过程。我们参考了论文采取信息素递减

扩散的策略对信息素进行更新 。

每只蚂蚁会在经过的边上留下一定量的信息素，作为下一轮蚂蚁求解的依据。为了避免残留信息过多淹没启发信息，在每次迭代完成后对残留信息进行更新处理 。由此第k?1次迭代时在路径

??k?的信息量按如下规则进行调整：

ij??k?1???1?????ijij???ij?k?

??ij?k?????ij?k?

rr?1m式中?表示信息挥发系数其取值范围为?01?。???k?表示本次迭代中路径

ij?ij?上的信息素增量；??ij?k?表示第r只蚂蚁第k次迭代在路径 ?irj?上留下的信

息量。

其中 ???k?按下式进行计算：

rij?Q???ij?k???L??0r若第r只蚂蚁在本次循环中经过?i否则j?

式中Q表示信息素强度，L表示第r只蚂蚁在本次循环中所走路径的总长度。可通过指定迭代次数或者当迭代所得到的解不再发生变化作为算法停止条件 。

2.2算法描述

（1）初始化蚂蚁选中的地址列表； （2）初始化禁忌表；

（3）处理一只蚂蚁，得到最佳位置； （4）更新禁忌表；

（5）执行循环，直至遍历所有路径； （6）新旧方案对比，选出最优； （7）根据选址的结果更新信息素 。

2.3算法实现与改进

我们把算法实现为一个类（类名AntPmediate）并提供了几个接口，使用它的方法如下： AntPmediate an = new AntPmediate(density, road);//初始化数据

an.initialParameter(informationIndex, inspireIndex, volatilize, antNum, Q, targetNum, cnt); //初始化参数

an.getBestPosition();//执行选址

this.result = an.returnResult();//得到结果

蚁群算法仍然有时间复杂度的问题，我们采用和前一个算法类似的思路来优化它。有所更进的是，我们认识到，研究区域的数据在边缘区域都是无效数据，所以在最初的预处理过程中，通通剔除了，以减少运行的时间。

3、结果分析 最优网点选址方案

平台：NetBeans IDE 8.0.2 语言：Java

结果：最优顺丰快递网点选址方案

输入数据：populationdestiny.txt、distanceroad.txt 输出数据: 运行界面：

（1）打开人口密度文件和道路文件

（2）刷新得到如下的图像

（3）执行贪婪取走算法，选址结果如下：

（4）执行蚁群算法，选址结果如下：