张寒野，凌建忠

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

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

张寒野，凌建忠

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

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

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

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

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