基于可视性分析的最优路径问题是一种以地形可视性信息为主要代价的最优路径搜索,属于空间决策支持范畴,在理论研究和实际应用两方面都有重要意义。在传统基于可视性分析的最优路径问题中,影响通行能力的可视性代价信息通常都是互不相关的0维数值,而互不相关的0维代价不能反映三维地形上不同点视域的重叠特征。本文采用二维视域描述三维地形的可视性信息,提出基于栅格邻域可视性相关的最优路径问题。路径总的可视性信息由所有路径点的视域融合求得,即为路径可视覆盖。根据路径可视覆盖最优和路径长度最优两个目标将最优路径问题分为:(1)全区域可视覆盖最短路径,(2)可视覆盖最小最短路径,(3)平均视距最大可视覆盖路径,(4)平均视距最小可视覆盖路径等。本文针对这四类问题进行深入研究,通过对各类问题本质的分析,以及对当前国内外进化算法领域研究热点的追踪,确定了解决各类问题的研究方向和总体思路。在此基础上,设计并实现了针对每类问题的新算法。(1)对于栅格地形上视域覆盖整个地形的最小可视覆盖问题,针对现有方法时间复杂度高以及不能实现全覆盖的问题,根据邻近地形点视域的重叠特性,提出了一个以累积可视性为启发信息的新方法,称为反向累积可视去冗余法(RVRR)。通过去除冗余地形观察点,以较低的时间复杂度得到了覆盖整个地形的近似最小数量的观察点集。与传统的贪婪算法相比,该方法在解的质量与算法效率上都有了明显提高。(2)以RVRR方法获得的覆盖整个地形的观察点集为基础,进一步提出了结合分而治之思想的两级进化算法,获得近似最优的全区域可视覆盖路径。首先把观察点分为若干簇,每个簇所在的位置称为子区,通过第一级遗传算法得到遍历子区的最优顺序,而后通过第二级多种群进化算法分别得到连接每个子区中观察点的最短路径段。根据子区遍历顺序,连接各路径段形成覆盖整个地形的完整路径。这种方法不仅能够高效获得覆盖整个地形的最优路径,而且易于扩展到多条路径协同对地形进行可视覆盖的情况。(3)详细分析了以平均视距最优为目标的路径搜索问题,给出了该类问题的两个基本性质并进行了证明:平均视距最优的路径搜索是栅格地形上一类存在负权弧但没有负权环的最优路径问题;平均视距最优的路径搜索不满足最优化原理。(4)通过对混合单目标进化算法的研究,设计了搜索平均视距最大路径的混合进化算法框架。采用变长染色体结构,并对关键点数的范围进行限定,既节省了时间与空间,又保证了染色体的灵活多样。同时通过自适应调整变异算子,使得算法能够快速搜索到近似最优解。算法在保持稳定性的同时,在解的质量与搜索效率上都比模拟退火算法有较大的改进。(5)分析了可视覆盖最小最短路径问题,是一类特殊类型的双权最短路径,属于多目标组合优化问题。通过对混合多目标进化算法的研究,设计了解决可视覆盖最小最短路径问题的混合多目标进化算法框架。除变长染色体结构和自适应变异算子外,设计了多级邻域结构,采用可变邻域搜索做为局部搜索器。另外,设计了以视域大小为索引的外部archive,保留进化过程和局部搜索过程中产生的更优的解。算法获得的解比已知的通用多目标算法NSGA-II更接近真实的Pareto前沿。(6)采用超体积和archive的种群更新策略,设计了基于超体积的多目标进化算法(HCEA)解决可视覆盖最小最短路径问题。另外把所设计的进化算法基本要件嵌入NSGA-II和SMS-EMOA算法的框架中,使其适于解决可视覆盖最小最短路径问题,并且与HCEA方法具有可比性。实验表明,我们的方法在超体积测度上优于其它两个方法,而且所得的结果具有更接近于视域极值的分布。(7)分析了平均视距最小路径问题的建模方法,并把多目标化的思想应用于对平均视距最小路径的求解。该方法在解的质量与搜索效率上都优于单目标的模拟退火算法和进化算法。本研究为基于可视性的最优路径问题提供了解决方法,也为进一步的研究提供了新方法、新思路。