A multi-objective evolutionary algorithm for minimal visual coverage path problem in raster Terrain

作者：Li Jie^*; Zheng Chang Wen; Hu Xiaohui

来源：ICIC Express Letters, 2011, 5(7): 2299-2304.

• Average horizon
• Chromosome structure
• Computation time
• Effective operator
• If there are
• Minimal path
• Multi objective evolutionary algorithms
• Multiobjectivization
• Path problems
• Raster terrain
• Simulated annealing algorithms
• Single objective
• Visual coverages

Minimal visual coverage path problem has wide applications, such as selecting the marching route and searching the smuggler's path. Average horizon of a path, which is the ratio of its visual coverage to its length, can be used to measure how covert a path is. If there are loops in a path, the path is meaningless though its average horizon is small due to its infinite length. A compromise is to modify the objective of minimal average horizon as the ratio of the length to the invisible region of the path where minimal length and minimal view shed can be satisfied simultaneously. However, the modified objective is not completely equivalent with average horizon. This study treats two elements of average horizon as two objectives and presents a multi-objective evolutionary algorithm for the minimal path visual coverage problem with single objective. By multiobjectivizating as well as the proper chromosome structure and effective operators, the method presented is superior to the simulated annealing algorithm and the evolutionary algorithm for single objective with respect to both higher quality of the solution and less computation time.

• 出版日期2011
• 单位中国科学技术大学