Research On Membrane Evolutionary Algorithm For Solving The Graph Coloring Problem

The graph coloring problem(GCP)is one of the famous NP(Non-deterministic Polynomial)-hard problems,which is related to combinatorial optimization problems such as the maximum cluster problem and the maximum independent set problem.In addition,it has many engineering applications,such as: communication constraints in communication problems,resource allocation in vehicle network problems,scheduling of devices,etc.Therefore,researching the problem of graph coloring has greater significance in both theory and practice.For the graph coloring problem,there are many heuristic algorithms at this stage,but all of them have problems such as poor stability and long computation time.As the size of the data continues to grow,the difficulty of dealing with this problem increases exponentially,and there is an urgent need to find new computational models to solve the graph coloring problem.In order to improve the efficiency of solving graph coloring problem,this thesis first analyzes one of the excellent algorithms for solving graph coloring problem—HEAD(Hybrid Evolutionary Algorithm in Duet),and proposes an improved algorithm NERS＿HEAD(A New Elite Replacement Strategy for HEAD)for the problem of poor diversity of management populations.Then,to further improve the efficiency of solving the graph coloring problem,the MEA＿GCP(A Membrane Evolutionary Algorithm for Solving the Graph Coloring Problem)algorithm is proposed based on NERS＿HEAD and the membrane evolutionary algorithm framework.This thesis also presents an experimental analysis of the proposed NERS＿HEAD and MEA＿GCP on the benchmark instances.The main research work of this thesis includes:(1)The NERS＿HEAD algorithm is proposed based on the HEAD algorithm.A new approach to managing population diversity is proposed in the NERS＿HEAD algorithm,including a strategy for determining whether the evolutionary process is trapped in a local optimum and a strategy for stepping out of the local optimum.Experimental comparison with the results of HEAD on the benchmark instances is able to reduce the evolutionary generations of the vast majority of instances and the computation time of most instances,with an average of 28.3% reduction in evolutionary generations and22.11% reduction in computation time,while ensuring the solution quality and stability.(2)To further improve the efficiency of solving graph coloring problem,the MEA＿GCP algorithm is proposed on the basis of the NERS＿HEAD algorithm.Inspired by the membrane evolution algorithm,MEA＿GCP optimizes the complex process of population diversity management in NERS＿HEAD.In the MEA＿GCP,membrane objects and membrane structures are designed for the graph coloring problem;six membrane evolution operators,namely,copy,fusion,division,cytolysis,fusion＿division,and tabu operator,are designed and implemented,and each evolution operator divides the work and cooperates to complete the membrane structure and membrane object evolution.Experiments on the benchmark instances are compared with the results of excellent algorithms in recent years and the NERS＿HEAD algorithm,which can effectively reduce the solution time while guaranteeing the solution quality and stability,with 58% of the instances prevailing.The research work in this thesis obtains a more efficient algorithm for solving graph coloring problem,verifies the effectiveness of the improved algorithm,and also verifies the feasibility of the membrane evolutionary algorithm for solving graph coloring problem.