遗传算法在网络优化问题中的应用

论文摘要

许多网络优化问题都是NP-hard问题,这些问题的求解时间随着问题规模增大而呈指数增长,因此往往需要采用近似算法进行求解。遗传算法（Genetic Algorithm, GA）作为一种全局优化搜索算法,由于其具有自学习、隐并行性等特点,所以能较快的求解NP-hard问题,最终得到较好的近似最优解。本文讨论了遗传算法在chord环查询映射系统优化、IP网络域内流量规划和LISP网络域内流量规划这三个典型的网络优化问题中的应用。Chord环查询映射系统优化是要找到一种虚节点和物理节点的映射关系,使得每次访问的平均查询延迟最短。针对该问题,本文第二章提出了GAOQCS算法来进行优化求解。在GAOQCS算法中,先对不同的映射关系进行编码,并设计杂交算子保证算法子代个体的可行性,通过仿真分析确定算法的遗传参数。使用随机网络拓扑和业务量矩阵所作的实验表明,相比随机产生节点映射关系的情况,GAOQCS的性能平均提高了30%左右。IP网络域内流量规划是要寻找一套链路权重,使得全网流量负载均衡（即最大链路利用率最小）。与传统邻域搜索算法不同,第三章提出新的方法来精确调整链路权重,该方法从搬移业务的角度出发,根据搬移的业务量来确定某条链路的权值增加量,以达到期望的网络流量分布。本章最后提出了IGAOSPF算法,将上述方法作为性能提高模块嵌套在遗传算法框架中。实验表明,IGAOSPF算法较以前的遗传算法性能提高了3%左右。不同于IP网络域内流量规划,LISP网络域内流量规划包括入口路由器的选择和链路权重设置两个方面的内容。由于这两个方面的优化存在相互影响,在第四章中,本文提出了个体性能优化模块,采用去耦合的思想消除两个问题之间的相互影响,分别对它们进行优化。本章提出了GALISP算法,将上述模块嵌套在遗传算法框架中。实验表明,在引入了个体性能优化模块后,遗传算法求解LISP网络域内流量规划问题的性能最大可提高23%。

论文目录

• 摘要
• ABSTRACT
• 图目录
• 表目录
• 缩略语表
• 第一章 引言
• 1.1 网络优化问题的困难
• 1.3 遗传算法概述
• 1.3.1 遗传操作
• 1.3.2 算法收敛性
• 1.4 本文拟解决的几个优化问题的讨论
• 1.4.1 Chord 的优化
• 1.4.2 域内流量规划
• 1.5 论文主要研究内容及结构
• 第二章 GA 用于chord 环查询映射优化
• 2.1 概述chord 环查询系统
• 2.2 chord 环查询映射优化问题
• 2.3 GAOQCS 算法框架设计
• 2.3.1
• 2.3.1.1 编码
• 2.3.1.2 种群的维护
• 2.3.1.3 适应度函数
• 2.3.1.4 遗传算子的设计
• 2.4 GAOQCS 算法流程
• 2.5 GAOQCS 算法仿真
• 2.5.1 算法性能仿真
• 2.5.2 参数设置对算法性能的影响
• 2.6 本章小结
• 第三章 GA 用于IP 网络域内流量规划
• 3.1 IP 网络域内流量规划概述
• 3.2 权值规划特点
• 3.2.1 比例性
• 3.2.2 两条链路权值的相互影响
• 3.2.2.1 实验场景
• 3.2.2.2 实验步骤
• 3.2.2.3 实验结果
• 3.3 算法框架设计
• 3.3.1 编码和初始化种群
• 3.3.2 适应度函数
• 3.3.3 种群分类
• 3.3.4 遗传算子
• 3.3.5 收敛准则
• 3.4 性能提高模块（Improvement module）
• 3.4.1 问题分析
• 3.4.1.1 业务的角度
• 3.4.1.2 链路的角度
• 3.4.2 模块实现
• 3.5 算法流程
• 3.6 算法仿真
• 3.6.1 仿真场景
• 3.6.2 算法性能仿真
• 3.6.3 参数设置对算法性能的影响
• 3.7 本章小结
• 第四章 GA 用于LISP 网络域内流量规划
• 4.1 LISP 网络概述
• 4.2 LISP 域内流量规划特点
• 4.3 算法框架设计
• 4.3.1 编码
• 4.3.2 初始化种群
• 4.3.3 适应度函数
• 4.3.4 种群分类
• 4.3.5 遗传算子
• 4.3.5.1 选择
• 4.3.5.2 杂交和变异
• 4.4 个体优化模块（Improving Individual module）
• 4.5 算法流程
• 4.6 算法仿真
• 4.6.1 算法性能仿真
• 4.6.2 参数设置对算法性能的影响
• 4.7 本章小结
• 第五章 结论
• 致谢
• 参考文献
• 个人简历
• 在学期间的研究成果