以多人博弈效用函数为演化指导函数的演化算法-模式识别与人工智能.pdf

第 19 卷摇 第6 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 模式识别与人工智能摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Vol.19摇 No.6 摇 2006年12月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 PR AI摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Dec摇 摇 2006 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 以以多人博弈效用函数为演化指导函数的演化算法* 徐摇 敏摇 摇 张四海摇 摇 王煦法 (中国科学技术大学 计算机科学技术系合肥摇 230027) 摘摇 要摇 研究一种基于多人纯策略非合作博弈的演化优化算法,可用于一类组合优化问题的求解.该算法的演化 过程可建模为一个马尔科夫链模型.它将组合优化问题映射为多人非合作博弈,通过博弈主体的理性行为对问题 的解进行优化.给出定义良好并可供扩展的算法框架,明确算法的要素所必须满足的3个约束:有限性约束、弱一 致性约束和收敛性约束,并应用于若干典型NP蛳Hard 的组合优化问题的求解.理论和实验结果表明,与一些传统优 化算法相比,本算法在实际应用中具有良好的问题求解能力. 关键词摇 博弈论,组合优化问题,效用函数(UF),演化指导函数,全局评估函数(GEF) 中图法分类号摇 TP181 An Evolutionary Algorithm Using Utility Function of Multi蛳Player Game as Evolution Directing Function XU Min,ZHANG Si蛳Hai,WANG Xu蛳Fa (Department of Computer Science and Technology,University of Science and Technology of China,Hefei230027) ABSTRACT An evolutionary algorithm based on multi蛳player non蛳cooperation game is proposed to solve the combinatorial optimization problems,andthealgorithmismodelledasaMarkov chain. Inthisalgorithm, combinatorial optimization problem is considered as an n蛳person game,and the solution of problem is optimized through agents爷 rational behavior. A well蛳defined and expandable frame of the algorithm is constructed,and three constraintsthat the algorithm must satisfy are presented:finite constraint,weakly consistent constraint and convergent constraint. The algorithm isused to solve some typical NP蛳Complete combinatorial optimization problems. The theoretical analysis and experimental results compared with other optimization algorithms show the proposed algorithm has a good ability of problem solvin