基于多目标遗传算法求解Steiner树问题

论文摘要

Steiner树问题是组合优化中的一个经典问题,它在很多领域得到了广泛应用和深入发展。但当前对Steiner树问题的研究大都集中在单个目标上,即最终只需要达到一种优化目标。而现实中需要解决的问题,往往不止一个目标,而是多个目标相互制约、影响,由此提出了多目标的Steiner树问题,使Steiner树问题变成多目标优化问题。目前有很多种解决多目标优化问题的算法,但这些传统的算法只是提供了一些不同的途径,将多目标优化问题转化为单目标优化问题,然后采用较为成熟的单目标优化方法来进行求解。其解决问题的基础仍是依赖单目标优化,往往难以得到令人满意的最优解集。由于遗传算法内在的并行性,善于在全局范围内进行搜索,适用于解决多目标优化问题。本文提出利用多目标遗传算法解决一种两个目标的Steiner树问题。本文的算法中,Steiner生成树由贪婪算法计算,多目标遗传算法对每一代的个体搜索其Pareto最优解集,直到算法结束,最终得到一组Pareto最优解,这些解包含了总体开销和边数两个目标,使决策者可以根据喜好选取最适当的方案。为了证明算法的有效性和先进性,测试了Beasley提供的B-problem数据集,并选择了解决Steiner树问题的三种经典算法进行了单个目标的比较,结果说明,本文的算法能搜索到单目标Steiner树的最优解,同时能搜索到多目标Steiner树的Pareto最优解集。

论文目录

• 中文摘要
• ABSTRACT
• 第1章 绪论
• 1.1 问题背景
• 1.2 Steiner树问题概述
• 1.3 遗传算法和多目标遗传算法概述
• 1.3.1 遗传算法概述
• 1.3.2 多目标遗传算法概述
• 1.4 本文主要研究内容及章节安排
• 第2章 STEINER树问题和多目标优化问题
• 2.1 Steiner树问题的定义
• 2.2 Steiner树问题的启发式算法
• 2.3 多目标优化问题简介
• 2.3.1 多目标优化问题的产生、发展及应用
• 2.3.2 多目标优化问题的模型、基本概念
• 2.3.3 多目标优化算法简介
• 2.4 本章小结
• 第3章 多目标遗传算法
• 3.1 遗传算法基本概念和基本理论
• 3.1.1 遗传算法的产生与发展
• 3.1.2 遗传算法的基本操作
• 3.1.3 遗传算法的一般流程
• 3.2 多目标遗传算法基本理论
• 3.2.1 多目标遗传算法一般流程
• 3.2.2 多目标遗传算法常用策略
• 3.3 多目标遗传算法分类
• 3.3.1 按不同的选择机制分类
• 3.3.2 按不同的决策方式分类
• 3.4 多目标遗传算法的研究现状
• 3.5 常见多目标遗传算法简介
• 3.6 本章小结
• 第4章 基于MOGA求解STEINER树问题
• 4.1 问题描述
• 4.2 算法流程
• 4.2.1 编码
• 4.2.2 初始化
• 4.2.3 评价
• 4.2.4 选择
• 4.2.5 交叉
• 4.2.6 变异
• 4.2.7 区别相同个体
• 4.2.8 检查生成树
• 4.3 本章小结
• 第5章 实验与结果
• 5.1 算法参数
• 5.2 实验方法
• 5.3 实验结果
• 5.4 本章小结
• 第6章 总结与展望
• 参考文献
• 致谢