以多人博弈效用函数为演化指导函数的演化算法

摘要：

研究一种基于多人纯策略非合作博弈的演化优化算法,可用于一类组合优化问题的求解.该算法的演化过程可建模为一个马尔科夫链模型.它将组合优化问题映射为多人非合作博弈,通过博弈主体的理性行为对问题的解进行优化.给出定义良好并可供扩展的算法框架,明确算法的要素所必须满足的3个约束:有限性约束、弱一致性约束和收敛性约束,并应用于若干典型NP-Hard的组合优化问题的求解.理论和实验结果表明,与一些传统优化算法相比,本算法在实际应用中具有良好的问题求解能力.

关键词：博弈论、组合优化问题、效用函数(UF)、演化指导函数、全局评估函数(GEF)

所属期刊栏目：19

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金委员会海外青年学者合作研究基金项目60428202

在线出版日期：2009-08-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：708-714