基于EA多目标网络设计问题建模与优化研究

摘要

网络设计问题是最重要也是最常见的优化问题之一。随着来自现实世界中问题不断的规模化和复杂化，我们面临的网络优化间题经常是大规模的且同时存在多个且互斥的优化目标，传统的精确算法在这时往往显得有些无能为力。近些年来，随着进化算法（EA）的发展，使得解决这类大规模多目标网络设计问题出现了转机。然而实际应用场景的复杂性导致我们需要深入分析具体间题，根据问题特点设计出量身定制的算法。 针对双目标最短路径问题，我们提出了一种基于优先级的编码方式和与之对应的权重映射交叉操作，在提高了编码形成染色体的遗传性与可行性的同时，也保证了经交叉后种群基因的稳定性。然后我们在适应性权重遗传算法的基础上做出了改进，提出了互动式适应性权重适应度赋值方法。最后，我们还打破了传统的进化算法结构，引入了“迁移”操作以保证种群中个体的多样性。 针对双目标最小生成树问题，在借鉴普利姆算法贪心策略的同时，我们在基于前驱的编码方法基础上进行了优化，提出了基于普利姆前驱的编码方法和基于普利姆的交叉操作。我们还将一种局部搜索技术以基于最小权重的变异操作的形式引入了算法中，最后我们也验证了互动式适应性权重适应度赋值方法应用于该问题时的有效性。 通过实验，我们验证了算法在解决涵盖了大部分多目标网络优化问题特点的双目标最短路径问题和双目标最小生成树问题时的有效性，从而验证我们提出的进化算法在解决多目标网络优化问题时的普适性和有效性。

目录

第一个书签之前