在大数据和人工智能时代,图越来越受到关注,许多研究领域致力于在图上应用神经网络、机器学习、数据分析技术,基于图对数据进行建模已经广泛应用于很多领域:如计算机网络、软件工程、图形数据库、社交网络、神经科学、流量管理等。大量的现实世界数据被建模为图形,而最短路径计算是这些图上执行的最典型操作之一。最短路径算法旨在找到一条路径,该路径包含给定网络/图中两个节点/顶点之间的最小开销。最短路径问题是计算机科学中的经典优化问题。它是图论中最基本的问题之一。经典的最短路径问题算法有两类:一是单源最短路径算法（single-source shortest-path,SSSP）,求解单个源S到所有其他顶点之间的最短路径;另一是全局最短路径问题,求解图中所有的顶点对之间的最短路径（all-pairs shortest-path,APSP）。解决最短路径问题的传统算法有一些缺点,这些算法仅搜索单个最优解（最短路径）,不能提供其他一些次优解,即k最短路径问题。例如在主动网络故障恢复机制中,往往需要一个以上的解决方案,将其中一个作为即时解决方案,而将其余的作为备选方案以防故障发生。而基于遗传算法的最短路径算法则既可以提供单一解,也可以提供n个解,其中n与种群规模一样大。这些解通常是次优解,往往应用于一些实时处理系统场景中,而且遗传算法天然就是具有并行性的,也有利于采用并行和分布式处理技术以实现进一步加速。然而,尽管针对最短路径问题的变长染色体直接编码遗传算法在许多领域得到了广泛应用,但该领域的研究远未令人满意。本文主要研究遗传算法变长染色体最短路径问题的多样性指标的推导与分析,并提出了一种新颖的基于对立学习的初始化算法。遗传算法（Genetic Algorithm,GA）是一种进化优化方法,使用一些个体（种群/染色体）作为解空间的代表。在称为世代的一些迭代中,染色体相互竞争;适应度函数评估个体的质量并确定每一代的竞争结果。在最短路径问题遗传算法（Genetic Algorithm for the Shortest Path problem,GA SP）中,每个个体都表示一对源目的之间的路径。每条路径都由多个不同的和有限的中继顶点组成。由于在一对源目的之间形成的路径包含的顶点数是可变的,因此染色体的长度也有所不同。遗传算法搜索过程的第一步需要进行初始猜测（初始种群）,初始种群的质量直接影响解的质量。一个好的初始猜测可以使遗传算法有更好的机会找到一个好的解,一个糟糕的初始猜测可能会阻碍算法找到最佳解的能力。初始种群的好坏的定义往往与特定问题密切相关,没有可以通用于各种类型问题的一般性初始化规则。此外,遗传算法不仅需要良好的初始种群,而且多样化的初始种群也同样重要,多样性一般会影响初始种群的质量和后续搜索过程。在整个优化过程中需要保持种群的多样性。遗传算法中保持多样性的目标是防止过早收敛,这是进化搜索中的一个重要问题。过早收敛的主要原因被称为探索/开发平衡（Exploration/Exploitation Balance,EEB）问题。在给定的优化空间中,探索旨在从新区域中寻找解决方案,而开发旨在评估（利用）当前区域。因此,增加探索将减少开发,反之亦然。平衡这两种行动具有挑战性。因此,进化算法社区提出了多样性作为EEB的衡量标准。基因型多样性指标衡量探索,而表型多样性指标衡量开发。基因型多样性是指群体在基因水平上的异质性/同质性程度,而表型多样性指标则衡量群体之间适应度的差异。高多样性表明高探索,而低多样性表明高开发。但是,许多多样性指标是根据特定问题的特征（例如其表示形式）来衡量EEB的。因此,针对研究问题及其特定特征的多样化性指标是至关重要的。本文工作的贡献可以总结如下:·通过比较研究设计和提出了基于基因和基于长度的多样性指标,据我们所知,这是第一个关注染色体长度多样性的工作。最后,使用综合数据分析量化了指标之间以及指标与种群适应性之间的关系。·提出了一种新的、简单和多样性感知的初始化方法。该初始化算法称为基于分层对立的抽样（stratified opposition-based sampling,SOBS）,通过考虑表型和基因型多样性,努力实现初始种群的最佳质量。通过使用四种用于模拟真实世界图的网络模型对SOBS进行测试,统计分析表明,SOBS在68%-100%的时间内产生更高精度的解。此外,本文还深入探讨了修复功能对染色体长度多样性的影响。虽然本文工作侧重于仿真部分的遗传算法,但本文建议的多样性度量和新的初始种群算法可以应用于其他解决最短路径问题和使用相同种群编码方法（即直接种群表示）的基于种群的演化算法,例如粒子群优化（particle swarm optimization,PSO）。