论文部分内容阅读
摘 要 气象自动站是气象现代化步伐中的重中之重，是现代天气测报、预报的重要手段，但是由于恶劣天气，周围环境的影响自动气象站可能出现问题需要专人进行维护，蚁群算法是解决TSP问题比较经典的一种算法，本文基于蚁群算法运用matlab进行计算给出了东港市气象自动站的最佳巡视路径，帮助自动站维护人员能够在最短时间内完成自动站的巡视工作。
关键词 蚁群算法；matlab；自动气象站巡视；东港市
中图分类号：P4 文献标识码：A 文章编号：1671-7597（2015）04-0061-02
1 研究背景
自动气象站实际上就是实现了自动化的传统气象站，目的是节省人力和测量偏远地区的气象数据。通过通信网络进行实时回报或把数据存储起来以后传送。自动气象站是实现气象现代化的重要工具，然而由于其地理位置较为分散且大多数处于偏远地区，维修工作比较困难，应对其进行定期的巡视维护工作，东港市做为我国极为特殊的沿海、沿边、沿江的三沿地区，其气象工作较为重要，因此本文选择东港市作为研究对象。
2 算法模型
蚁群算法是由Marco Dorigo1992年在他的博士论文中提出的一种用来在图中寻找最优化路径的模拟进化算法。该算法来源于蚂蚁在寻找食物的过程中发现最优路径的过程。每只蚂蚁在未知食物所在地的情况下出发寻找食物。其中一只找到食物后，它就会向周围释放一种挥发性分泌物，我们称之为信息素，该挥发物会随着时间的推移逐渐挥发消失，它的浓度大小表征路径的远近，其他的蚂蚁会被吸引过来，这样更多蚂蚁能找到食物。这些蚂蚁走过的路并不同，会发现新的道路，如果新发现的道路比原道路短，那么，更多的蚂蚁被吸引到这条比较短的路上来。如果蚂蚁的数量足够多并且时间足够长，一定可以发现一条最短的路径。
蚁群算法的基本思路如下面的流程图1所示。
1）初始状态下，蚁群刚刚生成，此时并没有信息素，因此每只蚂蚁只能随机生成路径去寻找食物。
2）经过一次循环，每只蚂蚁的坐标发生了改变，从初始坐标到这些坐标之间留下了信息素，他们中一些已经到达了目标点，这些蚂蚁会返回，剩余蚂蚁将会继续行走，同时，另外一批蚂蚁将会出发，它们按照每条路径上的信息素多少选择路线，信息素越多蚂蚁选择的可能性越大。
3）到目标点近的路线的信息素会越来越多，而比较远的路径上的信息会逐渐消失，不断地重复迭代步骤2。在迭代次数达到一个足够大的值后，就可以发现一条最优化的觅食路线，算法中比较关键的部分在于蚂蚁在步骤2中选择路线的概率是随机的以及步骤3中信息素的挥发与增强的算法该如何定义。
因此我们需要进行一些数学定义：
设蚂蚁选择某条路线的概率为k，一条路线上的信息素为x
则k=x/∑x
设p（i，j）表示蚂蚁从i点到达j点的概率，而x（i，j）表示ij两点间的信息素，则：
p（i，j）=x（i，j）/∑x（i）；
在初始状态，所有可选路径的信息素均为0，则p（i，j）为一个0到1的随机值
设信息素的挥发因子为ρ，n为迭代次数
ρ（n）=1-lnn/ln（n+1） ；
初始设定每条路线的信息素 x（i，j，0）为同一值，当进行第n+1次迭代后
x（i，j，n+1）=（1-ρ（n））*x（i，j，n）；
从这个公式可以看出，如果没有蚂蚁经过，那么该路径的信息素会逐渐的减少。
对于有蚂蚁可能经过的路线：
x（i，j，n+1）=（1-ρ（n））*x（i，j，n）+ρ（n）/|W|；W为所有点的集合。
图1
3 模型求解
3.1 坐标转换
我们通过GPS定位得到东港市23个自动气象站的经度，纬度，通过软件转化成基于北京54的大地坐标，结果如表1所示。
表1 自动站坐标
编号 地址 经度 纬度 X Y
1 铁甲 1240959 400250 13065257.57 -1919160
2 罗圈背 1232924 400223 12999407.65 -1872568
3 太平 1235355 400006 13040772.75 -1898400
4 椅圈 1234910 395141 13038353.75 -1885348
5 长安 1240437 400610 13054363.4 -1916113
6 十字街 1240610 395950 13060938.64 -1912070
7 龙王庙 1234507 400138 13025456.24 -1889787
8 合隆 1240151 400026 13053506.57 -1907718
9 海洋红 1233305 394929 13013511.71 -1865140
10 新农 1233017 395729 13003928.45 -1869169
11 黄土坎 1233928 395119 13022763.13 -1874028
12 北井子 1235349 395205 13045691.85 -1890978
13 长山 1240211 395207 13059339.67 -1900480
14 小甸子 1233547 395521 13014223.1 1873495
15 汤池 1241733 400347 13077015.8 -1928634
16 前阳 1241132 395817 13070698.97 -1916735
17 黑沟 1233630 400459 13009310.86 -1883001
18 长盛村 1233294 3947874 13013302.95 -1861675
19 孤山村 1233531 3954003 13014638.39 -1871974
20 大鹿岛村 1233272 3945510 13014023.03 -1860638
21 迟家店 1234063 3955049 13021270.36 -1878026
22 棋盘村 1240636 3956885 13064090.03 -1909044
23 山城村 1241211 4000696 13070664.76 -1919053
3.2 Matlab编程
我们将上述23个自动站按照顺序进行编号分别为1～23，通过Matlab进行编程，每次出动23只蚂蚁（当蚂蚁与自动站数目相近或相等时可以尽快得到最佳路径），循环运算200次，记录下每次的路径长度，最终选择200次中最短的可以视作最佳路径。
我们最终得到的最短路径为20 ，18，9，19，14，21，11，7，4，12，13，6，22，1，23，16，15，5，8，3，17，2，10，即大鹿岛，长盛村，海洋红，孤山村，小甸子，迟家村，黄土坎，，龙王庙，椅圈，北井子，长山，十字街，棋盘村，铁甲，山城村，前阳，汤池，长安，合隆，太平，黑沟，罗圈背，新农，基本路线图如图3所示。
图2 200次循环过程得出的最短路径
图3 通过蚁群算法得到的最短路径图
4 总结
气象自动站的理论上的最佳巡视路径，给自动站维护人员提供了自动站维护路径上的理论参考，给自动站维护工作提供了较大的帮助。
参考文献
[1]田一鸣.无线传感器网络节能优化技术研究[J].2009.
[2]李超迁.基于Ad hoc网络的按需路由协议的研究[J].2011.
[3]蚁群算法简介2.百度文库.
关键词 蚁群算法；matlab；自动气象站巡视；东港市
中图分类号：P4 文献标识码：A 文章编号：1671-7597（2015）04-0061-02
1 研究背景
自动气象站实际上就是实现了自动化的传统气象站，目的是节省人力和测量偏远地区的气象数据。通过通信网络进行实时回报或把数据存储起来以后传送。自动气象站是实现气象现代化的重要工具，然而由于其地理位置较为分散且大多数处于偏远地区，维修工作比较困难，应对其进行定期的巡视维护工作，东港市做为我国极为特殊的沿海、沿边、沿江的三沿地区，其气象工作较为重要，因此本文选择东港市作为研究对象。
2 算法模型
蚁群算法是由Marco Dorigo1992年在他的博士论文中提出的一种用来在图中寻找最优化路径的模拟进化算法。该算法来源于蚂蚁在寻找食物的过程中发现最优路径的过程。每只蚂蚁在未知食物所在地的情况下出发寻找食物。其中一只找到食物后，它就会向周围释放一种挥发性分泌物，我们称之为信息素，该挥发物会随着时间的推移逐渐挥发消失，它的浓度大小表征路径的远近，其他的蚂蚁会被吸引过来，这样更多蚂蚁能找到食物。这些蚂蚁走过的路并不同，会发现新的道路，如果新发现的道路比原道路短，那么，更多的蚂蚁被吸引到这条比较短的路上来。如果蚂蚁的数量足够多并且时间足够长，一定可以发现一条最短的路径。
蚁群算法的基本思路如下面的流程图1所示。
1）初始状态下，蚁群刚刚生成，此时并没有信息素，因此每只蚂蚁只能随机生成路径去寻找食物。
2）经过一次循环，每只蚂蚁的坐标发生了改变，从初始坐标到这些坐标之间留下了信息素，他们中一些已经到达了目标点，这些蚂蚁会返回，剩余蚂蚁将会继续行走，同时，另外一批蚂蚁将会出发，它们按照每条路径上的信息素多少选择路线，信息素越多蚂蚁选择的可能性越大。
3）到目标点近的路线的信息素会越来越多，而比较远的路径上的信息会逐渐消失，不断地重复迭代步骤2。在迭代次数达到一个足够大的值后，就可以发现一条最优化的觅食路线，算法中比较关键的部分在于蚂蚁在步骤2中选择路线的概率是随机的以及步骤3中信息素的挥发与增强的算法该如何定义。
因此我们需要进行一些数学定义：
设蚂蚁选择某条路线的概率为k，一条路线上的信息素为x
则k=x/∑x
设p（i，j）表示蚂蚁从i点到达j点的概率，而x（i，j）表示ij两点间的信息素，则：
p（i，j）=x（i，j）/∑x（i）；
在初始状态，所有可选路径的信息素均为0，则p（i，j）为一个0到1的随机值
设信息素的挥发因子为ρ，n为迭代次数
ρ（n）=1-lnn/ln（n+1） ；
初始设定每条路线的信息素 x（i，j，0）为同一值，当进行第n+1次迭代后
x（i，j，n+1）=（1-ρ（n））*x（i，j，n）；
从这个公式可以看出，如果没有蚂蚁经过，那么该路径的信息素会逐渐的减少。
对于有蚂蚁可能经过的路线：
x（i，j，n+1）=（1-ρ（n））*x（i，j，n）+ρ（n）/|W|；W为所有点的集合。
图1
3 模型求解
3.1 坐标转换
我们通过GPS定位得到东港市23个自动气象站的经度，纬度，通过软件转化成基于北京54的大地坐标，结果如表1所示。
表1 自动站坐标
编号 地址 经度 纬度 X Y
1 铁甲 1240959 400250 13065257.57 -1919160
2 罗圈背 1232924 400223 12999407.65 -1872568
3 太平 1235355 400006 13040772.75 -1898400
4 椅圈 1234910 395141 13038353.75 -1885348
5 长安 1240437 400610 13054363.4 -1916113
6 十字街 1240610 395950 13060938.64 -1912070
7 龙王庙 1234507 400138 13025456.24 -1889787
8 合隆 1240151 400026 13053506.57 -1907718
9 海洋红 1233305 394929 13013511.71 -1865140
10 新农 1233017 395729 13003928.45 -1869169
11 黄土坎 1233928 395119 13022763.13 -1874028
12 北井子 1235349 395205 13045691.85 -1890978
13 长山 1240211 395207 13059339.67 -1900480
14 小甸子 1233547 395521 13014223.1 1873495
15 汤池 1241733 400347 13077015.8 -1928634
16 前阳 1241132 395817 13070698.97 -1916735
17 黑沟 1233630 400459 13009310.86 -1883001
18 长盛村 1233294 3947874 13013302.95 -1861675
19 孤山村 1233531 3954003 13014638.39 -1871974
20 大鹿岛村 1233272 3945510 13014023.03 -1860638
21 迟家店 1234063 3955049 13021270.36 -1878026
22 棋盘村 1240636 3956885 13064090.03 -1909044
23 山城村 1241211 4000696 13070664.76 -1919053
3.2 Matlab编程
我们将上述23个自动站按照顺序进行编号分别为1～23，通过Matlab进行编程，每次出动23只蚂蚁（当蚂蚁与自动站数目相近或相等时可以尽快得到最佳路径），循环运算200次，记录下每次的路径长度，最终选择200次中最短的可以视作最佳路径。
我们最终得到的最短路径为20 ，18，9，19，14，21，11，7，4，12，13，6，22，1，23，16，15，5，8，3，17，2，10，即大鹿岛，长盛村，海洋红，孤山村，小甸子，迟家村，黄土坎，，龙王庙，椅圈，北井子，长山，十字街，棋盘村，铁甲，山城村，前阳，汤池，长安，合隆，太平，黑沟，罗圈背，新农，基本路线图如图3所示。
图2 200次循环过程得出的最短路径
图3 通过蚁群算法得到的最短路径图
4 总结
气象自动站的理论上的最佳巡视路径，给自动站维护人员提供了自动站维护路径上的理论参考，给自动站维护工作提供了较大的帮助。
参考文献
[1]田一鸣.无线传感器网络节能优化技术研究[J].2009.
[2]李超迁.基于Ad hoc网络的按需路由协议的研究[J].2011.
[3]蚁群算法简介2.百度文库.