Abstract：An evolutionary algorithm based on multiplayer noncooperation game is proposed to solve the combinatorial optimization problems, and the algorithm is modelled as a Markov chain. In this algorithm, combinatorial optimization problem is considered as an nperson game, and the solution of problem is optimized through agents’ rational behavior. A welldefined and expandable frame of the algorithm is constructed, and three constraints that the algorithm must satisfy are presented: finite constraint, weakly consistent constraint and convergent constraint. The algorithm is used to solve some typical NPComplete combinatorial optimization problems. The theoretical analysis and experimental results compared with other optimization algorithms show the proposed algorithm has a good ability of problem solving.
[1] Ansari N, Hou E. Computational Intelligence for Optimization. Dordrecht, Netherlands: Kluwer Academic Publishers, 1997 [2] Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor, USA: University of Michigan Press, 1975 [3] Kirkpatrick S, Gelatt C D, Jr Vecchi M P. Optimization by Simulated Annealing. Science, 1983, 220(4598): 671-680 [4] Han Jing, Liu Jiming, Cai Qingsheng. From ALIFE Agent to a Kingdom of N Queens. // Liu Jiming, Zhong Ning, eds. Intelligent Agent Technology: Systems, Methodologies, and Tools. Hackensack, USA: The World Scientific Publishing, 1999: 110-120 [5] Osborne M J, Rubinstein A. A Course in Game Theory. Cambridge, USA: Massachusetts Institute of Technology, 1994 [6] Han Jing, Cai Qingsheng. Emergence from Local Evaluation Function. Journal of Systems Science and Complexity, 2003, 16(3): 372-390 [7] Ye Jun, Liu Xiande, Han Lu. An Algorithm for Optimizing Knapsack Problem Based on Game Theory. Journal of Huazhong University of Science and Technology: Nature Science Edition, 2003, 31(9): 53-55 (in Chinese) (叶 俊, 刘贤德, 韩 露. 基于博弈论的背包问题优化算法.华中科技大学学报: 自然科学版, 2003, 31(9): 53-55) [8] Martello S, Toth P. Lower Bounds and Reduction Procedures for the Bin Packing Problem. Discrete Applied Mathematics, 1990, 28(1): 59-70 [9] Rao R L, Iyengar S S. A Stochastic Approach to the Bin-Packing Problem // Deaton E, Oppenheim D, Urban J, et al, eds. Proc of the ACM Symposium on Applied Computing. Phoenix, USA, 1994: 261-265 [10] Xu Min, Zhang Sihai, Wang Xufa. An Evolutionary Algorithm Using Utility Function as Evolution Directing Function for the Traveling Salesman Problem // Proc of the 2nd International Conference on Neural Networks and Brain. Beijing, China, 2005, Ⅰ: 361-365
2006, Vol. 19 
