融合不规则三角网和遗传算法的大洋科考航线设计方法

doi:10.3785/j.issn.1008-973X.2009.11.002

2009, Vol. 43

Issue (11): 1951-1957 DOI: 10.3785/j.issn.1008-973X.2009.11.002

自动化技术、计算机技术

融合不规则三角网和遗传算法的大洋科考航线设计方法

陈华锋¹,叶时平²,黄智才¹,章孝灿¹

（1.浙江大学地球科学系,浙江杭州 310027； 2.浙江树人大学信息科技学院,浙江杭州 310015）

Ocean scientific survey route designing method syncretizing triangulated irregular networks and genetic algorithm

CHEN Hua-feng¹, YE Shi-ping², HUANG Zhi-cai¹, ZHANG Xiao-can¹

(1. Department of Earth Sciences, Zhejiang University, Hangzhou 310027, China;
2. College of Information, Zhejiang Shuren University, Hangzhou 310015, China)

全文: PDF(902 KB)

摘要：

针对由于高耗时而无法使用精确方法的大洋科考航线设计问题,提出一种融合不规则三角网和遗传算法的航线设计方法（TIN-GA）.该方法由港口、作业区和拐点生成不规则三角网（TIN）,遍历搜索TIN中的所有路径,并将搜索获得的路径作为遗传算法初始路径种群的一部分参与优化繁殖,由进化结果生成航线.TIN将距离较近的点连接为三角形的边,具有很好的描述点邻近关系的自适应性,因此TIN中的路径必是所有可能路径中相对较优的路径.将这些路径作为初始路径种群的一部分能够加速遗传算法的收敛速度,并提高结果的最优性.大量仿真实验表明,该方法具有比遍历方法更高的效率,同时能够获得比遗传算法更优的结果.

关键词： 大洋科考; 航线设计; 流浪推销商问题; 不规则三角网; 遗传算法

Abstract:

A method syncretizing triangulated irregular networks (TIN) and genetic algorithm (GA) was presented for designing ocean scientific survey route when precise methods could not be used because of low efficiency. The method first builds TIN from ports, work areas and inflexion points, then full searches all paths in TIN and makes the search result be part of GAs initial population to participate in the breeding, finally creates a route according to the anagenesis result. As closer points are linked as edges of triangles, paths in TIN should be comparatively the shortest of all possible paths because of its good adaptability to describe the neighborhood relationship of points. Therefore, GAs convergence is fast and the result is good with these paths being part of the initial population. Many simulation experiments showed that the TIN-GA method is more efficient than the full search method (FS) and can obtain better result than that of GA.

Key words: ocean scientific survey route designing wandering salesman problem (WSP) triangulated irregular networks (TIN) genetic algorithm (GA)

出版日期: 2009-12-01

P 208

通讯作者: 章孝灿，男，教授，博导. E-mail: zxc@daditech.cn

作者简介: 陈华锋（1982-），男，安徽怀宁人，博士生，从事地理信息系统应用与算法研究.

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	陈华锋
	叶时平
	黄智才
	等

引用本文:

陈华锋, 叶时平, 黄智才, 等. 融合不规则三角网和遗传算法的大洋科考航线设计方法[J]. J4, 2009, 43(11): 1951-1957.

CHEN Hua-Feng, XIE Shi-Beng, HUANG Zhi-Cai, et al. Ocean scientific survey route designing method syncretizing triangulated irregular networks and genetic algorithm. J4, 2009, 43(11): 1951-1957.

链接本文:

http://www.zjujournals.com/xueshu/eng/CN/10.3785/j.issn.1008-973X.2009.11.002 或 http://www.zjujournals.com/xueshu/eng/CN/Y2009/V43/I11/1951

[1] 任建国. 我国海洋科学“十一五”发展战略与优先资助领域[J]. 中国科学基金, 2007, 21(1): 7-13．
REN Jian-guo. Developmental strategy and funding preferences of “the eleventh five-year plan” of oceanography in China [J]. Bulletin of National Natural Science Foundation of China, 2007, 21(1): 7-13．
[2] 马良. 旅行推销员问题的算法综述[J]. 数学的实践与认识, 2000, 30(2): 156-165．
MA Liang. Algorithmic review on the travelling salesman problem [J]. Mathematics in Practice and Theory, 2000, 30(2): 156-165．
[3] 严晨,王直杰. 以TSP为代表的组合优化问题研究现状与展望[J]. 计算机仿真, 2007, 24(6): 171-174．
YAN Chen, WANG Zhi-jie. Study on combinatorial optimization problem represented by TSP: recent research work and perspective [J]. Computer Simulation, 2007, 24(6): 171-174．
[4] GLOVER F. Future paths for integer programming and links to artificial intelligence [J]. Computers & Operations Research, 1986, 13(5): 533-549．
[5] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing [J]. Science, 1983, 220: 671-680．
[6] 刘宁钟,杨静宇. 遗传算法和Hopfield模型求解货郎担问题的比较和分析[J]. 计算机工程与应用, 2003,39(4): 95-97．
LIU Ning-zhong, YANG Jing-yu. Comparison and analyse between genetic algorithm and hopfield network to resolve TSP [J]. Computer Engineering and Applications, 2003,39(4): 95-97．
[7] RNDOLPH G. Convergence analysis of canonical genetic algorithms \[J\].IEEE Transactions on Neural Networks, 1994,5(1):96-101.
[8] 张晓缋，方浩，戴冠中.遗传算法的编码机制研究\[J\].信息与控制，1997,26(2):134-139.
ZHANG Xiao-hui, FANG Hao, DAI Guan-zhong. Study on encoding mechanism of genetic algorithms \[J\].Information and Control,1997,26(2):134-139.
[9] RNDOLPH G. Convergence analysis of canonical genetic algorithms [J]. IEEE Transactions on Neural Networks, 1994, 5(1): 96-101．
[10] BERTONI A, DORIGO M. Implicit parallelism in genetic algorithms \[J\].Artificial Intelligence，1993,61(2):307-314.
[11] SRINIVAS M, PATAIK L M. Genetic algorithms: a survey \[J\].IEEE Computer,1994,27(6):17-26.
[12] DORIGO M, GAMBARDELLA 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．
[13] POTVIN J Y, ROUSSEAUA J M. Parallel route building algorithm for the vehicle routing and scheduling problem with time windows [J]. European Journal of Operational Research, 1993, 66(3): 331-340．
[14] 邬伦,刘瑜,张晶,等. 地理信息系统：原理、方法和应用[M]. 北京：科学出版社, 2001:199-204.
[15] 武晓波,王世新,肖春生. 一种生成Delaunay三角网的合成算法[J]. 遥感学报, 2000, 4(1): 32-35．
WU Xiao-bo, WANG Shi-xin, XIAO Chun-sheng. A hybridized method for building Delaunay triangulation [J]. Journal of Remote Sensing, 2000, 4(1): 32-35．
[16] 章孝灿,黄智才,戴企成,等. GIS中基于拓扑结构和凸壳技术的快速TIN生成算法[J]. 计算机学报, 2002, 25(11): 1212-1218．
ZHANG Xiao-can, HUANG Zhi-cai, DAI Qi-cheng, et al. An algorithm of speedily building TIN based on topological structure and convex shell in GIS [J]. Chinese Journal of Computers, 2002, 25(11): 1212-1218.

[1]	赵斌, 张松, 李剑峰. 基于零件摩擦学性能的磨削参数优化[J]. 浙江大学学报(工学版), 2018, 52(1): 16-23.
[2]	张玄武, 郑耀, 杨波威, 张继发. 基于级联前向网络的翼型优化设计[J]. 浙江大学学报(工学版), 2017, 51(7): 1405-1411.
[3]	张丽娜, 余阳. 海量O2O服务组合的优化[J]. 浙江大学学报(工学版), 2017, 51(6): 1259-1268.
[4]	苏亮, 宋明亮, 董石麟, 罗尧治. 循环遗传聚类法稳定图自动分析[J]. 浙江大学学报(工学版), 2017, 51(3): 514-523.
[5]	张俊红,郭迁,王健,徐喆轩,陈孔武. 塑料机油冷却器盖加强筋参数的多目标优化[J]. 浙江大学学报(工学版), 2016, 50(7): 1360-1366.
[6]	司恩波, 王晶, 靳其兵, 周靖林. 工业无线网络链路选择与时隙分配的同步优化[J]. 浙江大学学报(工学版), 2016, 50(6): 1203-1213.
[7]	王树朋,黄凯,严晓浪. 基于遗传算法的覆盖率驱动测试产生器[J]. 浙江大学学报(工学版), 2016, 50(3): 580-588.
[8]	李清,胡志华. 基于多目标遗传算法的灾后可靠路径选择[J]. 浙江大学学报(工学版), 2016, 50(1): 33-40.
[9]	刘扬,鲁乃唯,蒋友宝. 结构体系可靠度分析的改进支持向量回归[J]. 浙江大学学报(工学版), 2015, 49(9): 1692-1699.
[10]	高史义, 罗小华, 卢宇峰, 刘富春, 张晨秋. 基于遗传算法的功能覆盖率收敛技术[J]. 浙江大学学报(工学版), 2015, 49(8): 1509-1515.
[11]	赵琼,童水光,钟崴,葛俊旭. 基于GA-FEA的门座起重机变幅机构优化设计[J]. 浙江大学学报(工学版), 2015, 49(5): 880-886.
[12]	苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 2015, 49(5): 866-872.
[13]	艾小祥,俞慈君,方强,陈磊,方伟,沈立恒. 基于遗传算法的机翼壁板扫描路径优化[J]. 浙江大学学报(工学版), 2015, 49(3): 448-456.
[14]	过海,倪益华,王进,陆国栋. 车用空调冷凝器性能多目标优化方法[J]. 浙江大学学报(工学版), 2015, 49(1): 142-159.
[15]	肖文生,崔俊国,刘健,吴晓东,黄红胜. 直驱采油用永磁同步电机削弱齿槽转矩优化[J]. 浙江大学学报(工学版), 2015, 49(1): 173-180.

Viewed

Full text

Abstract

Cited

Shared

Discussed