遗传算法与蚁群算法在海洋调查路径规划中的应用

张寒野，凌建忠

（中国水产科学研究院东海水产研究所，农业部东海与远洋渔业资源开发利用重点实验室，上海 200090）

遗传算法与蚁群算法在海洋调查路径规划中的应用

张寒野，凌建忠

（中国水产科学研究院东海水产研究所，农业部东海与远洋渔业资源开发利用重点实验室，上海 200090）

分别以遗传算法与蚁群算法对23个站位的海洋渔业资源调查路径进行规划，寻找其最优路径。求解结果表明，遗传算法和蚁群算法都能找到同样的最短路径，比实际路径缩短了8.32%的里程。蚁群算法求得的平均路径长度小于遗传算法，但所耗时间比遗传算法多一倍左右。

路径规划；遗传算法；蚁群算法；海洋渔业；资源调查

我国拥有广袤的海洋面积，蕴藏着丰富的生物、能源和矿产资源。为了掌握海域资源环境现状，我国于1996年开始了专属经济区和大陆架勘测工作［1］，陆续开展了各种海洋资源与环境调查。海洋调查中常用的方法是派出调查船，沿预先设计的航线逐点采样观测。这是项耗资费时的工作，科学地规划调查路径对于提高调查效率、降低成本具有重要意义。

寻找最优路径是一类组合优化问题，实际上是一个旅行商问题（travelling salesman problem，TSP），TSP已被证明是一个多项式复杂程度的非确定性（non-deterministic polynomial，NP）问题，即没有确定的算法能在多项式时间内得到问题的解。如果用精确算法求解，随着节点数目的增加，可能的路径数目呈指数增长，难以解决大规模问题。因此一般采用遗传算法、蚁群算法等启发式算法，求得近似解满足要求。

遗传算法（genetic algorithm，GA）［2］是模拟自然界生物进化中遗传、突变、杂交和适者生存等现象，从一定数量的初始解开始，经过一系列进化，逐步逼近问题的最优解的一种算法。蚁群算法（ant colony optimization，ACO）［3－4］也是一种仿生算法，是模拟蚂蚁在搜索食物时寻找最优路径的过程而得到的算法：蚂蚁在觅食过程中会在经过的路径上留下一种信息素，并且信息素的浓度与路径长度成反比，经过同一路径的蚂蚁越多，该路径上的信息素浓度就越高，吸引后来的蚂蚁选择该路径的概率也越大，最终使整个蚁群趋于最优路径上。这类仿生算法已广泛应用于组合优化领域［5－8］。本文将遗传算法和蚁群算法应用于海洋渔业资源调查，比较两者的优劣，以期实现海洋调查最优化路径的分析和求解。

1 材料与方法

1.1 遗传算法

1.1.1 编码方式

0表示出发和返回位置，1，2，…n表示n个调查站位，以站位的遍历次序作为遗传算法的编码。一个编码是一个个体，代表一个可行解，即一条路径。随机产生N个编码，组成初始种群。

1.1.2 适应度函数

适应度函数是用于评价种群中每个个体路径优劣的指标，适应度值越大，该个体被遗传到下一代的概率也越大。路径越短说明这个解越好，其适应度也越大，因此可将适应度函数取为路径长度的倒数。

1.1.3 选择操作

选择的方式采用轮盘赌法，每个个体被选中遗传到下一代的概率与其在群体中的相对适应度成正比。此外还采用了精英保留策略，每一代适应度最高的个体原样遗传到下一代，以保证最优者生存下来。

1.1.4 变异操作与交叉操作

将被选择遗传到下一代的个体，按预先设定的概率进行变异和交叉操作，改变局部编码，生成新个体。变异操作是随机选择路径上的两个点交换位置，从而产生一个新个体。交叉操作是选择两个父代个体，随机选择两个交叉点，并互换这两个交叉点之间的编码，为保证每个站位都遍历一次且仅有一次，互换后将交叉点以外的部分中与交叉点之间重复的站位用另一个父代的相应位置代替，这样形成两个新个体。

1.1.5 进化中止

当适应度达到期望的结果或迭代超过预设的次数，则进化中止。

1.1.6 参数设置

遗传算法运行时所使用的参数如表1所示。

表1 遗传算法的参数设置Tab.1 Parameters of GA

1.2 蚁群算法

1.2.1 选择概率［9］

t时刻时，位于站位i的蚂蚁k选择向下一个站位j移动的概率为：

式中，τij（t）表示t时刻从i站位到j站位路径上信息素的浓度，dij表示站位i和j之间的距离，α表示信息素浓度的相对重要性，β表示站位间距离的相对重要性，allowedk表示允许蚂蚁k下一步选择的站位的集合。

1.2.2 信息素更新

初始状态下信息素浓度设为1。当所有蚂蚁完成一次遍历后，对路径上的信息素浓度进行更新，t＋1时刻从i站位到j站位路径上信息素的浓度为：

式中，Q为每只蚂蚁能释放的信息素总量，是一个常数，Lk表示蚂蚁k在本次遍历经过路径的总长度。

1.2.3 参数设置

蚁群算法运行时所使用的参数如表2所示。

表2 蚁群算法的参数设置Tab.2 Parameters of ACO

1.3 路径距离计算

假设地球是完美的球体，任意两个调查站位i和j经度分别为λi和λj，纬度分别为φi和φj，则两个站位间的距离为：

式中，R为地球半径。

1.4 调查站位

以2014年5月东海北部的一次渔业资源调查为例，分别以遗传算法和蚁群算法进行调查路径规划，此次调查共有23个站位，分布如图1所示。

图1 站位分布图Fig.1 Distribution of survey stations

表3 两种算法结果对比Tab.3 Com parison of results between GA and ACA

2 结果与分析

用遗传算法和蚁群算法分别进行100次路径规划运算，其结果如表3所示。由表3可见，遗传算法和蚁群算法都能找到同样的最短路径；蚁群算法求得的平均路径长度小于遗传算法，并且解的分布也比较集中；但是蚁群算法计算过程较复杂，运行所需时间比遗传算法多一倍左右。

两种算法所找到的最优路径如图2所示，图3是调查船实际航行轨迹，最优路径比实际路径缩短了8.32%的里程。

图2 最优路径Fig.2 Optimal path

图3 实际路径Fig.3 Actual path

图4是遗传算法的收敛曲线，从中可以看到其迭代过程，遗传算法在初始阶段收敛较快，随后进入平稳阶段，进化5 000代后，其平均值已接近最优解。

图4 遗传算法收敛曲线Fig.4 Convergent curve of GA

图5是蚁群算法的迭代曲线，也是进行100次运算后统计所得。蚁群算法收敛速度非常快，在运行初期就已经接近最优解。

图5 蚁群算法的迭代曲线Fig.5 Iterative curve of ACO

运算结果表明，蚁群算法在求解最优路径时具有较快的收敛性，适用于较精确的求解。遗传算法运行速度较快，适用于快速求解并且对结果准确度要求不高的场合。

3 讨论

遗传算法与蚁群算法通过不断迭代，使所要解决的问题从初始解逐渐向最优解逼近。但是最终求得的解可能是次优解，不一定是全局最优解。特别是针对大规模问题，即站位点比较多时，容易陷入早熟和难以跳出局部最优的状态，出现搜索停滞的现象。不少研究提出了改进方法，如最大最小蚁群系统（max-min ant system，MMAS）［10］修改了蚁群算法中信息素的更新方式，每次迭代后路径上的信息素浓度被限制在［min，max］范围内，可以改善算法的停滞现象。也有研究将蚁群算法和遗传算法相结合［11］，以蚁群算法的解作为遗传算法的初始种群，加快算法的收敛速度。另外在每次迭代过程中，引入2-opt等局部搜索算法可进一步改善解的质量。

遗传算法和蚁群算法的参数设定对算法的性能优劣颇为重要。群体规模影响到算法的性能和效率，群体过小则由于搜索空间较小而效果不佳，群体过大则计算量较大导致速度变慢。遗传算法中变异概率和交叉概率影响着种群的更新速度，概率过高则更新过于频繁而使算法变成随机搜索，概率过低则子代和父代过于相似而使进化停滞。蚁群算法中α值越大，蚂蚁选择以前经过路径的概率也越大；β值越大，选择局部最短路径的可能性也越大；ρ值从大到小变化，其算法的随机性和全局搜索能力变弱，但是能提高收敛速度。遗传算法和蚁群算法的参数选择虽然比较重要，但尚没有数学解析方法求得最优值，在实际应用中一般采用经验值。

遗传算法和蚁群算法不仅可用于求解单目标优化问题，也适合求解多目标优化问题［12－15］。应用于海洋调查路径规划，除了可以求解单船最短路径，也可求解多条船同时调查情况下，总成本最低或总路径最短，且各船经过站位尽可能均衡的问题。对于多目标优化问题，往往不存在满足所有条件的全局最优解，通常是得到一组Pareto最优解。

［1］ 郑元甲，陈雪忠，程家骅，等.东海大陆架生物资源与环境［M］.上海：科技出版社，2003.

ZHENG Y J，CHEN X Z，CHENG J H，et al.Biological resources and the environment of East China Sea continental shelf［M］.Shanghai：Shanghai Science and Technology Press，2003.

［2］ HOLLAND JH.Adaptation in natural and artificial systems［M］.Ann Arbor：University of Michigan Press，1975.

［3］ DORIGO M，MANIEZZO V，COLORNIA.The ant system：Optimization by a colony of cooperating agents［J］.IEEE Transactions on System，1996，26（1）：28－41.

［4］ DORIGO M，GAMBARDELLA L M.Ant colonies for traveling salesman problem［J］.BioSystems，1997，43（2）：73－81.

［5］ DORIGO M，CAMBARDELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem［J］.IEEE Transactions on Evolutionary Computation，1997，1（1）：53－66.

［6］ COSTA D，HERTZ A.Ants can color graphs［J］.Journal of the Operational Research Society，1997，48（3）：295－305.

［7］ MANIEZZO V，COLORNIA.An ants heuristic for the frequency assignment problem［J］.Future Generation Computer Systems，2000，16（8）：927－935.

［8］ COLORNIA，DORIGOM，MANIEZZO V，et al.Ant system for job shop scheduling［J］.Operations Research，1994，34（1）：39－53.

［9］ MULLEN R J，MONEKOSSO D，BARMAN S，et al.A review of ant algorithms［J］.Expert Systems with Application，2009，36（6）：9608－9617.

［10］ STUTZLE T，HOOS H.Max-min ant system［J］.Future Generation Computer System，2000，16（8）：889－914.

［11］ LEE Z J，SU S F，CHUANG C C，et al.Genetic algorithm with ant colony optimization（GA-ACO）for multiple sequence alignment［J］.Applied Soft Computing，2008，8（1）：55－78.

［12］ KOH S P，ARIS I B，HO C K，et al.Design and performance optimization of a multi-TSP（traveling salesman problem）algorithm［J］.AIML Journal，2006，6（3）：29－33.

［13］ SINGH A，BAGHEL A S.A new grouping genetic algorithm approach to the multiple traveling salesperson problem［J］.Soft Computing-A Fusion of Foundations，Methodologies and Applications，2009，13（1）：95－101.

［14］ CARTER A E，RAGSDALEC T.A new approach to solving the multiple traveling salesperson problemusing genetic algorithms［J］.European Journal of Operational Research，2006，175（1）：246－257.

［15］ GHAFURIAN S，JAVADIAN N.An ant colony algorithm for solving fixed destination multi-depot multiple traveling salesmen problems［J］.Applied Soft Computing，2011，11（1）：1256－1262.

Research of genetic algorithm and ant colony optim ization on path p lanning for oceanography survey

ZHANG Han-ye，LING Jian-zhong
（Key Laboratory of East China Sea＆Oceanic Fishery Resources Exploitation and Utilization，Ministry of Agriculture，East China Sea Fisheries Institute，Chinese Academy of Fishery Sciences，Shanghai200090，China）

Searching for the optimal path is one of the most important combinatorial optimization problems.Since this problem belongs to NP-hard problems，an exact algorithm could not solve the large-scale problems in time，somemetaheuristic approaches have been used to solve it in recent years.Genetic algorithm works in a way similar to the process of natural evolution，such as inheritance，mutation，selection and crossover.A basic GA starts with a random ly generated population of candidate solutions.After the evolution of several generations，the optimal solution for the problem is obtained.Ant colony optimization algorithm is to mimic themovements of ants.Ants leave a trail of pheromoneswhen they search for food，and the pheromone density becomes higher on shorter paths than longer ones.As more ants use a particular trail，the pheromone concentration on it increases，hence attracting more ants.Consequently，all ants follow a best path.This article presented GA and ACO for solving the path planning of 23 stations for a fishing resource survey.The results indicate that both algorithm are able to find out the same shortest path，which is 8.32%shorter than the actual path.The average path length obtained by ACO is less than thatby GA，but it takes nearly twice as long.It is suggested that ACO has better convergence and more acurate calculation results，as well as GA is suitable for fastsolving and roughly estimating the problems.

path planning；genetic algorithm；ant colony optimization；marine fishery；resources survey

S 932.4

A

1004－2490（2016）01－0083－05

2015－07－10

农业部专项近海资源调查（2014）

张寒野（1974－），男，副研究员，硕士，从事海洋渔业资源研究。E-mail：hy＠eastfishery.ac.cn