论文部分内容阅读
研究一种基于多人纯策略非合作博弈的演化优化算法,可用于一类组合优化问题的求解,该算法的演化过程可建模为一个马尔科夫链模型,它将组合优化问题映射为多人非合作博弈,通过博弈主体的理性行为对问题的解进行优化,给出定义良好并可供扩展的算法框架,明确算法的要素所必须满足的3个约束:有限性约束、弱一致性约束和收敛性约束,并应用于若干典型NP-Hard的组合优化问题的求解。理论和实验结果表明,与一些传统优化算法相比,本算法在实际应用中具有良好的问题求解能力。
This paper studies a evolutionary optimization algorithm based on multiplayer pure strategy for non-cooperative game, which can be used to solve a combinatorial optimization problem. The evolution of the algorithm can be modeled as a Markov chain model, which maps the combinatorial optimization problem Human non-cooperative game, the problem solution is optimized by the game player’s rational behavior, and a well-defined and scalable algorithm framework is given. Three constraints that must be satisfied by the elements of the algorithm are defined: finite constraint, weak consensus constraint And convergence constraints, and applied to solve some typical NP-Hard combinatorial optimization problems. Theoretical and experimental results show that compared with some traditional optimization algorithms, this algorithm has good problem-solving abilities in practical application.