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

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