基于博弈策略的多目标进化算法研究

论文摘要

多目标优化问题（MOP）是科学研究与工程实践中普遍存在又非常重要的一类基础性优化问题，具有广泛的应用前景。起源于生物进化理论的多目标进化算法（MOEA）是求解该问题的一种主流方法。目前该方法主要基于非支配解排序，随着种群的进化，候选解的层次数不断减少，种群多样性逐渐丢失，造成种群进化动力不足，使算法容易出现收敛速度慢、容易进入局部最优、全局寻优能力弱等问题。博弈论（Game Theory）是研究主体为争取最大利益如何做出决策的一门科学，它和多目标问题都属于多主体优化问题。借鉴博弈论的基本知识和理论求解多目标优化问题，无论是对提高多目标进化算法性能，还是拓展多目标优化问题工程应用领域都有积极的意义。本文围绕基于博弈的多目标优化算法以及在网格任务调度中的应用展开工作，主要内容包括：首先，介绍多目标优化问题并总结目前已有的求解方法，给出了几种常见的群智能算法基本原理和求解过程。另外，讲解了博弈论的基本知识，并结合对多目标进化算法中种群进化过程的分析，指出了两者结合的可能性；其次，在研究多目标进化算法和各种博弈模型的基础上，本文提出了一种基于混合策略博弈的多目标进化算法（MSG-MOEA）。将种群每次迭代过程看做是一场博弈，各博弈参与人不断调整博弈策略，追求自身利益最大化，带动种群向Pareto前沿进化。算法分析和仿真实验表明本算法在解的分布性和收敛性方面都有较好的表现；最后，提出了一种基于MSG-MOEA的多目标网格任务调度算法。针对现实网格环境中存在计算资源失效等问题，提出了基于任务生存性和任务完成时间的网格调度模型。设计了符合该模型的基于MSG-MOEA的调度算法。仿真实验结果表明，该算法可以很好的解决多目标网格调度问题。

论文目录

• 摘要
• Abstract
• 目录
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景与意义
• 1.1.1 研究背景
• 1.1.2 意义
• 1.2 国内外研究现状
• 1.3 主要研究内容与文章结构
• 1.3.1 主要研究内容
• 1.3.2 本文的工作安排
• 第2章 多目标优化问题和优化算法
• 2.1 多目标优化问题概述
• 2.1.1 多目标优化问题描述
• 2.1.2 多目标优化算法发展
• 2.2 传统的多目标优化算法
• 2.2.1 几种典型的传统多目标优化算法
• 2.2.2 传统算法存在的不足
• 2.3 群体智能多目标优化算法
• 2.3.1 群体智能进化算法简介
• 2.3.2 几种常见的群体智能算法
• 2.4 小结
• 第3章 基于博弈思想的多目标优化算法
• 3.1 博弈论概述
• 3.1.1 博弈论的研究发展
• 3.1.2 博弈论基本要素
• 3.1.3 几种常见的博弈论模型
• 3.2 多目标优化算法与博弈论
• 3.2.1 两者结合的可能性
• 3.2.2 两者结合的必要性
• 3.2.3 多目标优化与博弈论的研究
• 3.3 蕴含博弈思想的多目标优化算法
• 3.3.1 协同进化算法
• 3.3.2 基于静态贝叶斯博弈的多目标遗传算法
• 3.4 小结
• 第4章 基于混合策略博弈的多目标进化算法
• 4.1 混合策略的博弈
• 4.2 基于混合策略博弈的多目标遗传算法
• 4.2.1 博弈模型
• 4.2.2 算法描述
• 4.3 算法分析
• 4.3.1 算法复杂性分析
• 4.3.2 算法收敛性分析
• 4.4 实验分析
• 4.4.1 测试函数
• 4.4.2 实验参数
• 4.4.3 实验结果
• 4.5 小结
• 第5章 基于 MSG-MOEA 的多目标网格调度问题求解
• 5.1 网格任务调度概述
• 5.1.1 网格任务调度的主要特点
• 5.1.2 网格任务调度的主要目标
• 5.1.3 网格任务调度算法的研究现状
• 5.2 基于 MSG-MOEA 算法的网格任务调度
• 5.2.1 问题模型及系统建模
• 5.2.2 算法描述
• 5.3 实验仿真与分析
• 5.3.1 网格环境参数
• 5.3.2 实验结果及分析
• 5.4 小结
• 结论
• 参考文献
• 致谢
• 附录A （攻读学位期间发表的论文与获得的成果）
• 附录B （攻读学位期间参加的科研项目）