基于博弈思想的优化算法研究

论文摘要

本文参考自然计算方法的思路，借鉴了博弈理论，模拟人类社会中的经济系统，通过对经济系统中人的行为和相互作用建立模型来构造出一个多主体系统，并使得系统在整个演化过程中呈现出一些可以进行问题求解的特性。具体方法是：采用自下而上的设计方式，构造具有理性人特性的主体，并将大量的主体放到同一个系统中，定义主体之间的博弈引起的利益分配，在主体行为选择的演化过程中使系统呈现出问题寻优的能力。 本文的主要研究工作有： 首先建立一种基于多人博弈的优化算法（EAMG），用于求解组合优化问题。说明了算法的五个要素，并给出了定义良好、可供扩展的算法框架。给出了算法有效所必须满足的三个约束条件（有限性约束：弱一致性约束；收敛性约束）的定义。证明了EAMG算法只要满足这三个约束条件就能以概率1收敛到问题的全局最优解。说明了EAMG算法具有的特性：局部性和全局性、非完备性、任意时间性、鲁棒性、自组织性、动态性等等。 在算法框架的基础上，进一步针对两个经典的组合优化（CO）问题：装箱问题和旅行商问题，应用EAMG进行求解。实验结果表明本算法具有能够在相对短的时间内求得高质量解的优点，与一些经典的优化算法相比具有良好的问题求解能力。通过实验验证了其中的部分特性，如自组织临界性、算法演化过程的动态性、求解的有效性和鲁棒性等。并通过实验说明算法中涉及的参数如何取值能够较有效地求解。 仔细分析了EAMG算法的特点之后，提出了两种变种算法。分别是多群体EAMG和采用better-move主体行动决策方案的EAMG算法。并分别应用两种变种算法对TSP问题进行求解。并将实验结果与原算法作对比。 将演化博弈的思想引入多目标优化问题的求解，提出了一种基于演化博弈的优化算法（EGOA）。EGOA借鉴了演化博弈的思想和选择机制，每一代，我们随机从群体中抽取成对个体并进行重复博弈，以在博弈中取得的效用来确定个体

论文目录

• 目录
• 摘要
• Abstract
• 第一章 引言
• 1.1 优化问题概述
• 1.1.1 用于优化问题求解的计算智能方法
• 1.1.2 演化指导函数
• 1.1.2.1 评价函数
• 1.1.2.2 全局评价函数
• 1.1.2.3 局部评价函数
• 1.1.3 优化问题求解面临的困难和挑战
• 1.2 结合博弈理论的优化算法
• 1.2.1 博弈论概述
• 1.2.2 基于博弈论的优化算法研究现状
• 1.3 本文主要研究内容与技术路线
• 1.3.1 技术路线
• 1.3.2 研究内容
• 1.4 本文组织与章节安排
• 1.5 本章小结
• 参考文献
• 第二章 基于多人博弈的优化算法框架
• 2.1 算法的基本思路
• 2.2 算法的要素
• 2.2.1 主体集合
• 2.2.2 行动集合
• 2.2.3 效用函数
• 2.2.4 均衡扰动函数
• 2.2.5 停止准则
• 2.3 基于多人博弈的优化算法
• 2.4 算法模型必须满足的约束
• 2.4.1 有限性约束
• 2.4.2 弱一致性约束
• 2.4.3 收敛约束
• 2.5 算法模型的基本特性
• 2.6 本章小结
• 参考文献
• 第三章 基于多人博弈的优化算法应用于若干典型优化问题的求解
• 3.1 装箱问题
• 3.1.1 装箱问题描述
• 3.1.2 问题求解的要素
• 3.1.3 要素满足的约束
• 3.1.3.1 有限性约束
• 3.1.3.2 弱一致性约束
• 3.1.3.3 收敛约束
• 3.1.4 实验结果及讨论
• 3.2 旅行商问题
• 3.2.1 旅行商问题描述
• 3.2.2 问题求解的要素
• 3.2.3 要素满足的约束
• 3.2.3.1 有限性约束和弱一致性约束
• 3.2.3.2 收敛约束
• 3.2.4 实验结果及讨论
• 3.3 其它问题
• 3.4 模型特性的实验验证
• 3.4.1 自组织临界性
• 3.4.1.1 自组织临界性与幂率
• 3.4.1.2 EAMG的自组织临界性
• 3.4.2 动态性
• 3.4.3 求解的有效性和鲁棒性
• 3.5 本章小结
• 参考文献
• 第四章 算法的变种
• 4.1 原算法模型分析
• 4.2 基于多群体博弈的算法
• 4.2.1 算法思路
• 4.2.2 算法描述及流程图
• 4.2.3 实验结果及讨论
• 4.3 Better-Move-有限理性的主体模型
• 4.3.1 策略选择函数
• 4.3.2 实验结果及讨论
• 4.4 本章小结
• 参考文献
• 第五章 可求解多目标优化问题的演化博弈优化算法
• 5.1 多目标优化问题
• 5.1.1 问题定义
• 5.1.2 研究背景
• 5.2 用于求解多目标优化问题的演化博弈优化算法
• 5.2.1 算法的理论基础
• 5.2.2 算法框架及流程图
• 5.3 实验结果及分析
• 5.3.1 测试函数
• 5.3.2 演化稳定策略集合及分析
• 5.3.3 种群在群体中所占比例对演化稳定策略的影响
• 5.4 本章小结
• 参考文献
• 第六章 全文总结及进一步研究
• 6.1 总结
• 6.2 本文贡献及创新之处
• 6.3 进一步工作展望
• 本文使用的缩写列表
• 致谢
• 攻博期间发表的论文和参加的科研项目
• 作者简历