Research On Game Theory Idea Based Optimization Algorithm

Based on the idea of Nature Inspired Computation and Game Theory, by imitating economic system of human society, this thesis creates a multi-agent system through modeling people's behaviors and interactions in economic system. The multi-agent system shows a capability for Optimization Problems solving during evolution. Speaking in detail, using design mode of 'from bottom to top', we construct agent with rationality, then put plenty of agents into one system, and define profit assignment of agents caused by game play to make sure that the whole system has ability to optimize problems during evolution process of agents' strategy deciding.This thesis proposes the following main contributions:First of all, this thesis creates an evolutionary algorithm based on multi-players game theory (EAMG) for Combinatorial Optimization Problems (COPs), which embodies five basic elements, and proposes a well-defined and expandable frame of algorithm. We define three constraints of 'finite constraint, weak-inconsistent constraint and convergent constraint' that are necessary make algorithm effective, and prove that EAMG can converge to the global optimal solution of problem if the three constraints are satisfied. Then seven attributes of EAMG are illuminated: Local, Global, Incomplete, Any-time, Robust, Self-organized and Dynamic.Based on the framework of the algorithm, we use EAMG to solve two typical Combinatorial Optimization Problems: Bin-Packing Problem (BPP) and Traveling Salesman Problem (TSP). The results show that EAMG can find solutions with high quality in short time. and compared with other optimization algorithms, EAMG has a good ability of problem solving. We validate some attributes of EAMG by experiment, such as Self-Organized Criticality, Dynamic, Robust, etc. We also give the best parameters' value of the algorithm.After analyzing attributes of EAMG, we propose two varietal algorithms of...