| 基于博弈论的背包问题优化算法 |
| |
| 引用本文： | 叶俊,刘贤德,韩露. 基于博弈论的背包问题优化算法[J]. 华中科技大学学报(自然科学版), 2003, 31(9): 53-55 |
| |
| 作者姓名： | 叶俊 刘贤德 韩露 |
| |
| 作者单位： | 华中科技大学,光电子工程系;华中科技大学,电子信息工程系 |
| |
| 摘 要： | 基于博弈粤论提出了一种背包问题优化算法。将背包问题的搜索空间映射为博弈的策略组合空间,背包问题的目标函数映射为博弈的效用函数,通过理性博弈主体的最优反应动态与均衡的扰动恢复过程达到优化目标。给出了算法的形式定义及描述,证明了算法的全局收敛性。仿真运算及与遗传算法的比较结果验证了算法的有效性。
|
| 关 键 词： | 背包问题 演化博弈 理性主体 最优反应 纳什均衡 |
| 文章编号： | 1671-4512(2003)09-0054-03 |
| 修稿时间： | 2003-01-03 |
An algorithm for optimizing knapsack problem based on game theory |
| |
| Ye JunLiu XiandeHan LuDoctoral Candidate, Dept. of Optoelectronical Engimeering,Huazhong Univ. of Sci. & Tech.,Wuhan ,China.. An algorithm for optimizing knapsack problem based on game theory[J]. JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE, 2003, 31(9): 53-55 |
| |
| Authors: | Ye JunLiu XiandeHan LuDoctoral Candidate Dept. of Optoelectronical Engimeering Huazhong Univ. of Sci. & Tech. Wuhan China. |
| |
| Affiliation: | Ye JunLiu XiandeHan LuDoctoral Candidate, Dept. of Optoelectronical Engimeering,Huazhong Univ. of Sci. & Tech.,Wuhan 430074,China. |
| |
| Abstract: | An algorithm was proposed to optimize knapsack problem based on game theory. The algorithm makes the mapping of the search space and objective function of knapsack problem to the strategy profile space and utility function of game respectively, and helps to achieve the optimization objective through the best response dynamics of rational game agents and the perturb recover process of equilibrium states. The formal definition and detailed description of the algorithm were presented, and the global convergence property of the algorithm was proved. The efficiency of the proposed algorithm was verified by the simulation testing and the comparison with Genetic Algorithm. |
| |
| Keywords: | knapsack problem evolutionary game rational agent best response Nash equilibrium |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
