A Study On Genetic Algorithms For Distributed Constraint Optimization Problems

Distributed Constrained Optimization Problem(DCOP)is the fundamental framework of Multi-Agent System(MAS),which can model multi-agent coordination optimization problems,and it has been successfully applied to task scheduling,resource allocation and other fields.However,these existing algorithms for solving DCOP almost hammer at the single-candidate optimization,and those algorithms usually suffer from local premature convergence.Thus,we make a concerted effort to take the power of GA into solving DCOP.The main work is as follows:(1)Due to the fact that existing local search algorithms easily fall into local optima,we propose a GA-based framework(LSGA)to enhance local search algorithms.Considering the features of Genetic Algorithm(GA)and local search algorithms,we propose a parallel population-based framework for local search algorithms and a series of genetic operators which are redesigned for agents in DCOPs to improve the search ability of local search algorithms.Specifically,the framework provides a fitness function which is designed to evaluate the assignments for each agent and to balance local benefits and global benefits,a new method is provided to decide crossover positions in terms of agent-communication and topological structure of DCOPs to achieve the crossover operator in the distributed environment,a self-adaptive crossover probability and a self-adaptive mutation probability to control the uses of crossover operator and mutation operator.We provide the theoretical analyses for the convergence and complexity of LSGA,and the experimental results demonstrate the superiority of the use of LSGA in the typical search algorithms over many local search algorithms.(2)Since the diversity of population in the LSGA-based algorithms is confined single search strategy,we propose a GA-based Multi-Subswarm algorithm for solving DCOP(Multi-Subswarm?DCOP).Analyzing the features of different local search strategies,we combine the parallelism of GA and the local search ability of agents,design multi-subswarm structure,and design Multi-Subswarm?DCOP based this structure.Specifically,the algorithm builds three subswarms which contain individuals belong to different subswarms and arrays individuals in different subswarms alternately;and then,the three subswarms adopt hill-climbing Search,simulated annealing and variable neighborhood search to optimize parallelly for the diversity of population;the algorithm executes the rotation-like crossover based on the order of individuals to achieve the fusion for different local search strategies.We provide the theoretical analyses for the convergence and complexity of Multi-Subswarm?DCOP,and the experimental results demonstrate the superiority of Multi-Subswarm?DCOP over many incomplete algorithms for solving DCOPs.