基于邻域可视性相关的最优路径问题研究

项目名称： 基于邻域可视性相关的最优路径问题研究

项目编号： No.60873183

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 郑昌文

作者单位： 中国科学院软件研究所

项目金额： 30万元

中文摘要： 在传统基于可视性分析的最优路径问题中，影响通行能力的可视性代价信息通常都是互不相关的0维数值，而互不相关的0维代价不能反映三维地形上不同点的视域的重叠特征。本研究采用二维视域描述地形的可视性信息，提出了基于栅格邻域可视性相关的最优路径问题。首先，针对栅格全区域可视覆盖路径搜索问题，给出了一种反向累积可视去冗余的方法以获得可实现全区域可视覆盖最小观察点集；以全区域可视覆盖最小观察点集为基础，采用一种两层遗传算法，可有效实现全区域可视覆盖最优路径搜索。其次，在对栅格地形平均视距最大、平均视距最小和最小可视覆盖路径问题进行数学建模的基础上，详细分析了可视性相关路径搜索问题的性质，指出由于视域的融合特性，使得通常的解决该类问题的路径搜索方法不再适用；通过将进化计算的思想与具体的路径搜索问题相结合，提出了一种基于进化计算的路径搜索算法，采用一种变长实值基因编码方式和一套特定的进化算子，可根据不同的优化目标函数解决平均视距最大、平均视距最小和最小可视覆盖路径问题。最后，通过引入多目标进化计算，有效解决了可视覆盖最小最短路径搜索问题。

中文关键词： 可视性相关；可视覆盖；最优路径；进化计算；多目标进化。

英文摘要： In traditional approaches, the visibility information used to evaluate the traveling ability of the path in the terrain is zero-dimensional and independent in the neighborhood. However, it is not comprehensive to use the irrelative zero- dimensional numerical values to represent the overlapping characteristic of viewshed from the different points of the terrain. Two-dimensional viewsheds is used in this work to describe three-dimensional visibility; considering the visibility correlation caused by the overlapped of the adjacent points' viewsheds, the neighborhood visibility correlative optimal path problems in grid terrain is proposed. Firstly, for the problem of complete visual coverage path, a reverse cumulative visibility redundancy removal method is proposed to obtain the minimal visual coverage observers set in raster terrain, and a two level evolutionary algorithm is presented to search the optimal complete visual coverage path based on the observers set. Secondly, by modeling for the problems of optimal paths with maximal average horizon, minimal average horizon and least visual coverage, the properties of the problems are analyzed in detail. It proved that optimal path with maximal average horizon does not satisfy the principle of optimality. Combining the concepts of evolutionary computation with problem-specific representation of candidates and genetic operators, a novel route search algorithm for neighborhood visibility correlative optimal path problems is presented. With different objective functions, the algorithm can find optimal paths with maximal average horizon, minimal average horizon or least visual coverage respectively. Finally, introducing multiple-objective evolutionary computation, the minimal visual coverage shortest path problem is resolved effectively.

英文关键词： visibility correlative; visual coverage; optimal path; evolutionary computing; multi-objective evolution.