路径优化问题,是运筹学与组合优化领域的研究热点,同时为智能物流提供优化配送参考。基于其通常为NP难,进化算法经常被应用于求解这类问题。演化计算是智能计算的一部分,是计算机科学利用生物演化的机制解决现实中复杂的优化问题。而演化计算成功解决问题的关键是“编码”,包括种群个体的表示以及搜索空间到可行解空间之间的映射。在路径优化问题中,变量之间是相互作用的:一个变量对适应值的贡献取决于其他变量的状态。这种问题特征在演化计算中称为“完全相关”(Entire Linkage)。研究显示:决策变量之间的相互作用往往会给进化算法求解问题带来困难。因此,当路径优化问题的规模增长或约束规则增加时,会带来更大的挑战。本博士论文围绕着演化计算如何利用路径优化问题中变量之间的相关特性进行研究,从编码方式入手,提出了一个“变量相关特性学习演化”(Evolution with Variable Interaction Learning,EVIL)的路径优化框架。在此框架下,以旅行商问题(Traveling Salesman Problems,TSP)和广义旅行商问题(Generalized Traveling Salesman Problems,GTSP)为研究对象,分别具体设计了几种进化算法。本论文的创新点和研究成果如下:(1)提出了一种基于构造图的邻接实数矩阵编码方式。该编码方式使种群个体以邻接实数矩阵的形式成为变量之间相关信息的载体,通过演化学习寻找最优或满意的实数相关矩阵。根据旅行商问题和广义旅行商问题构造图的特点,分别设计了相应的邻接实数矩阵编码方式:在旅行商问题中,种群个体以代表邻接城市之间相关权重的实数矩阵形式表示,通过伪随机比例规则采样与贪婪算法实现搜索空间到可行解空间的映射;在广义旅行商问题中,种群个体以代表邻接城市群之间相关权重的实数矩阵形式表示,通过伪随机比例规则采样与贪婪算法确定城市群的排列,接着采用最短路径算法确定城市排列,从而实现了搜索空间到可行解空间的映射。在TSPLIB数据库实例中进行实验研究,结果表明:基于构造图的邻接实数矩阵编码方式能有效提高进化算法求解旅行商问题以及广义旅行商问题的性能,分别仅利用4.38%至35.17%和0.67%至12.17%的评价次数即可得到最优解或满意解。(2)设计了一种矩阵重组差分搜索算子。该搜索算子使局部搜索后的信息、历史全局最优和个体自身最优的信息能够反馈到当前种群个体中并参与进化过程,实现了对路径优化问题中变量之间相关信息的有效演化学习。而且,矩阵重组差分算子是没有参数的算术操作,大大简化了实际操作的复杂性。在TSPLIB数据库实例中进行实验研究,结果表明:矩阵重组差分的搜索算子能有效结合邻接实数矩阵编码,求解旅行商问题以及广义旅行商问题。(3)提出了一种评价路径优化问题中变量之间相关程度的“完全相关指标”(Entire Linkage Index)。通过该指标探讨本论文所提出的“变量相关特性学习演化”模型利用路径优化问题中变量之间相关特性的情况。在TSPLIB数据库实例中进行实验研究,观察问题实例的完全相关特性与算法性能的关系,结果显示:当旅行商问题实例的完全相关指标值大于0.5时,矩阵重组差分进化算法的误差率相对偏低;在求解中大规模广义旅行商问题时,随着实例的完全相关指标值增长,邻接实数矩阵算法的误差率和评价次数利用率都会有降低的趋势。这些迹象揭示了,当路径优化问题的完全相关水平较高时,本论文所提出的“变量相关特性学习演化”模型的优势更加显著。