The Study On Improving Local Search Algorithms For Distributed Constraint Optimization Problems

Distributed Constraint Optimization Problem(DCOP)is a basic framework of multi-agent systems.It can be used to model multi-agent collaborative optimization problems and distributed problems and has been applied to real-world problems such as task scheduling,resource allocation and power system.Since DCOP is a NP-hard problem and local search algorithm is used for NP-hard problems.local search algorithms such as Distributed Stochastic Algorithm(DSA)are proposed for DCOP.However,such local search algorithms generally have disadvantages such as premature convergence and poor solution quality.Slope Dependent Probability Algorithm(DSA-SDP)is an improved variant of DSA.The probability of selecting the best-response value in DSA is replaced with the slope based on the new and old local benefits in DSA-SDP.DSA-SDP alleviates premature convergence of DSA and thus gets the quality improvements.DSA-SDP also attempts to increase the exploration ability by temporarily slightly reducing the solution quality,but the effect is very small.GA-based framework for Local Search(LSGA)is a population-based framework applied to local search algorithm.LSGA applies genetic algorithm to DCOP by periodically performing crossover operators and mutation operators.To solve these problems above,this thesis intends to start research from the local search algorithm and proposes novel routes to improve the local search algorithm.The specific research work is as follows:(1)The thesis makes depth analysis for essential theories of several existing local search algorithms and research works starts from the study to DSA.In this thesis,sampling method and firstly adjusting the solution structure by improving the variance make up for disadvantages of DSA.Specifically,this thesis firstly improves DSA by introducing Local Search with Sampling(LSs)and DSA based on Variance(VARDSA).LSs takes values between the best-response value and original value into account by sampling with local benefit improvement.VARDSA adjusts the solution structure by increasing the variance to improve the solution quality.The thesis also proposes the greedy strategy among multiple solutions(GSMSs)to improve DSA.GSMSs introduces the population coding method of LSGA framework to organize multiple solutions and uses the greedy strategy contained in DSA to adjust the solution structure.The experimental results show that LSs,VARDSA and GSMSs are better than the classical local search algorithm DSA in benchmark problems.(2)Based on the optimization mechanism above,Variance Slope Dependent Probability algorithm(VSDPs)introduces the slope descent strategy of DSA-SDP.VSDPs is based on single solution.The slope of local benefit is used to produce the probability of changing the value.Based on LSs,VSDPs introduces the slope from DSA-SDP to decide whether to change assginment and uses VARDSA to replace local disturbance in DSA-SDP for improvement of exploration ability.In addition,VSDPs randomly selects all assignments that may meet the slope condition to improve the fairness of agent assignment selection and avoid the drawback of lots of empirical parameters of DSA-SDP.The experimental results show that VSDPs is superior to most local search algorithms on the solution quality.(3)Introducing the coding method from the LSGA framework,variance based on LSs(VLSs)is proposed.Considering the characteristics of three optimization strategies proposed in(1),which can improve the exploration ability or the solution diversity of local search,VLSs combines the three strategies to enhance the solution quality by alternately executing variance improvement and greedy strategy in a population.The experimental results show that VLSs is better than the exsiting incomplete algorithms based on local search.All in all,the thesis proposes three strategies: LSS,GSMSs and VARDSA,and proposes single solution and multi-solutions optimization algorithms based on these strategies,Besides,we verify their effectiveness from theory and experiments in the thesis,which promotes the development of local search algorithm in distributed constrained optimization problems and the content in it has great value in theory and practical application.