Research On Co-evolutionary Algorithm Based On Game Theory

Co-evolutionary algorithms are a very active research area of computational intelligence in recent years,this work develops construction mechanism of co-evolutionary algorithms by combining evolutionary algorithm with game theory,and designs new co-evolutionary algorithms based on the idea of mixed strategy in game theory.This work modifies previous mixed strategy framework,adding new mutation operators and extending to crossover operation,and proposes co-evolutionary algorithms based on mixed strategy.The algorithms present new collaborative strategy for mutation operators,crossover operators,selection operator of EA and search mechanisms,and builds efficient co-evolutionary model.The proposed algorithms is applied to solve the optimization questions,such as function optimization,evolutionary clustering,multi-issue negotiation and winner determination question in combinatorial auction.Detail works are listed as below:(1)Inspired by evolutionary game theory,this paper modifies previous mixed strategy framework,adding a new mutation operator and extending to crossover operation,and proposes co-evolutionary algorithms based on mixed crossover and/or mutation strategy.The novel algorithms automatically select crossover and/or mutation operators from a given mixed strategy set,and improve the evolutionary performance by dynamically utilizing the most effective operator at different stages of evolution.The algorithms possess potential multiple sub-populations due to different evolution patterns simultaneously,next generation population is generated under co-operation of various evolution patterns.(2)With the developments of research for multi-objective optimization problem,more and more novel algorithm frameworks are introduced into the area of multi-objective optimization.Due to slow convergence of basic evolutionary multi-objective optimization algorithms in complex space,the local search is introduced to maintain a balance between exploration and exploitation.A novel algorithm,called multi-objective mixed strategy evolutionary algorithm with local search,is presented based on the frame of MOEA/D(multi-objective evolutionary algorithm based on decomposition),to solve a set of scalar optimization sub-problems.The uniform design method is applied to generate the aggregation coefficient vectors,the mixed strategy can make full use of the advantage of each crossover operator,the algorithm combines local search strategy,to approximate the Pareto-optimal set.(3)Though FCM has already been widely used in clustering,its alternative calculation of the membership and prototype matrix causes a computational burden for large-scale data sets.An efficient algorithm,called accelerated fuzzy C-means(AFCM),is presented for reducing the computation time of FCM and FCM-based clustering algorithms.The proposed algorithm works by sampling initiation to generate better initial cluster centers,and motivated by the observation that there is the increasing trend for large membership degree values of data points at next iteration,updating cluster center using one step k-means for those data points with large membership degree values and only updating membership of data points with small values at next iteration.(4)In complex automated negotiations,a challenging issue is how to design effective learning mechanisms of agents that can deal with incomplete information and dynamic negotiation scenarios.In this paper,we present a time dependent,bilateral multi-issue optimized negotiation model by combining Bayesian learning with evolutionary algorithm based on mixed strategy.Using the historical offers only,the proposed model enable agents to estimate accurately about the probability distribution of its opponent's negotiation parameters(i.e.,the deadline,reservation offer,issue weight)and to adjust adaptively concession strategy to benefit two partners to improve the utility and success rate of negotiation agreement.(5)To address computational complexity of winner determination in combinatorial auction,two new co-evolutionary algorithms are developed based on mixed mutation and self-organization optimization for finding high quality solutions quickly.Mixed mutation strategy can select adaptively mutation operators which are suitable for discrete space.Self-organization optimization makes the search to jump out of local optima.This paper proposes and investigates two ways to combine mixed mutation with self-organization optimization,the results of experiment show the effectiveness of the second way that self-organization optimization is added to mixed mutation strategy set as a pure mutation operator.