Optimization By Evolutionary Game

Many of the problem solving strategies in the real world may boil down to the optimization process on complex objectives. Traditional optimization approaches are usually based on the gradient properties of objective functions. They are computational efficiently but often fail in finding the global optima of the given problems. Moreover, the curse of dimensionality is another difficulty that requires serious consideration for this kind of approaches. In contrast, modern optimization approaches, such as artificial neural networks, simulated annealing, evolutionary algorithm and artificial immunity system, introduce random factors and/or analogies between the mechanism of nature process and optimization. These so-called computational intelligence methods have been recently applied with success to a broad class of difficult optimization problems for their flexibility, robustness and commitment of global search.In this dissertation, we propose a novel evolutionary game approach for optimization problem solving based on economic game theory. The proposed approach sets up relevant mappings between the search space and objective function of optimization problem and the strategy profile space and utility function of non-cooperative game respectively, and achieves the optimization objective through the dynamic evolutionary game process of adaptive agents.To begin with, we present the mapping principle and general framework of evolutionary game approach. Then for function optimization problems, we have discussed the Best-Response dynamics model with continuous strategies and discrete strategies, and clarified that game agents can reduce the searching space of equilibrium points with joint decisions; for constrained optimization problems, we have developed a solving model based on the amendatory process of fictitious play, and introduced a learning rate adapting technique combined with a fitness comparison schema for handling nonlinear equality and inequality constraints; furthermore, we have researched knapsack problem solving as a typical example of combinational optimization and the parallelization potential of evolutionary game models, and demonstrated the applications of evolutionary game approach in the domain of optimal control, nonlinear parameter estimation and path schedule problem in information gathering.In the dissertation, we have presented relevant theoretical analysis about convergence property and parallel efficiency based on the formal definition of above models, and carried out computer simulation experiments on corresponding benchmark problems and showed the performance comparisons with other evolutionary algorithms. The results indicate that evolutionary game approach is a promising way for constructing robust, widely applicable and high-performance optimization algorithms, and has great values both in theoretical and applied area.The contributions of this work are: (1) it disclosed profound relationships between optimization problem solving and evolutionary game process, and established the basic mappings and general framework of evolutionary game approach; (2) proposed the evolutionary game models for solving function optimization, constrained optimization and combinational optimization problems; (3) researched the parallelization strategies based on time distribution, simultaneous decision-making and strategy learning in groups; (4) verified the validity of the evolutionary game approach by theoretical analysis and detailed simulation experiments; (5) and presented the applications of the evolutionary game approach in several engineering domain.The future work of this study includes the theoretical fundamental of evolutionary game approach, other evolutionary game models, applications to multi-objective optimization, objective optimization with noise, dynamic objective optimization, and the integration with other types of optimization approaches.