Research On Constraint Satisfaction Problem Solving Algorithms Based On MBO

Constraint Satisfaction Problems(CSPs)solving algorithm research has always been the hot issue of research in the field of artificial intelligence.Usually,a set of variables,a set of the respective domain corresponding to variables and a set of constraints between variables constitute a basic constraint satisfaction problem.In the real world,many scheduling?planning and configuration problems can be described by constraint satisfaction problem.However,constraint satisfaction problem is generally of high complexity.In addition to the classical algorithms,heuristic search method can be used to find the feasible solution or even the optimal solution within reasonable time.Vehicle Routing Problem(VRP)is a kind of CSPs.It's the earliest proposed by Dantzig and Ramser in 1959.VRP is the problem in which a supplier has a certain number of customers,each of whom has different needs for the quantity of goods,and chooses the appropriate delivery routs to meet each customer's demand of goods under the condition of certain constraint,such as the minimum cost,minimum time or shortest path.In academic research and practical application,basic VRP has a lot of varietas,such as VRP with times windows,heterogeneous fleet VRP,VRP with pick-up and deliveries,multiple depot VRP(MDVRP),etc.Since VRP is NP-hard problem,it is difficult to solve it with precise algorithm.So the main method to deal with VRP is heuristic algorithm.A kind of heuristic algorithm is nature-inspired algorithm,which is inspired by one colony's collective behavior in nature.Usually this kind of colony follows the simple rules.Swarm intelligence and nature-inspired algorithm get great attention in the nowaday research,especially the algorithm based on swarm intelligence.In fact,these meta-heuristic algorithms inspired by nature have been widely applied in optimization and computational intelligence.Analyzing from nature-inspired algorithms' exploration and search space,there are two main components: exploitation and exploration,also called reinforcement and diversification.Exploitation is mainly to obtain relevant information from the search space of neighborhood to generate new solution superior to the current.But in the process it always presents to attempt to find the local optimal solution.Therefore,the advantage of exploitation is that it usually has fast convergence.But its disadvantage is also obvious that it is easy to fall into the local optimum.Exploration is the opposite.Generally speaking,the search space of exploration is within the global scope,so the diversity of search space is better.Therefore exploration could generate new solutions far away from the existing ones.It is not easy for exploration to fall into the local optimal,so the possibility of finding the global optimal will be greatly improved.But it is slow to converge and has a lot of calculation.In order to make the best performance of the algorithm,it is important to balance exploitation and exploration.Monarch Butterfly Optimization(MBO)is a new nature-inspired algorithm proposed by Gai-Ge Wang et al in 2015.The algorithm is obtained by simplifying and idealizing the migration behavior of monarch butterfly.The algorithm divides the butterfly population into two parts,one for exploitation and the other or exploration.In the process of iteration,migration operator and butterfly adjusting operator are respectively used to generation the new population.MBO is easy to operate,and the operation of two operators is theoretically parallel.This paper studies the principle and framework of MBO algorithm,and analyzes the search process of the algorithm.When the MBO algorithm chooses the individual of the new generation,only the new individual which has better performance can be preserved.It makes the algorithm easy to fall into local optimum,so we add the simulated annealing strategy to disturbance current search space,which is conducive to timely jumping out of local optimal algorithm.Moreover,we use the new algorithm to solve the multi-depot vehicle routing problem and test the performance of the new algorithm in practical applications.