Research On P System And Membrane Evolutionary Algorithm For Solving The Travelling Salesman Problem

With the continuous development of the Internet,the daily data generated by human beings show explosive growth,which requires more and more computer computing power.Supported by Moore's Law,early electronic computers showed exponential growth in storage,computing time,and computing performance.However,limited by the integration limit of core components,the computing power of electronic computers is gradually approaching the bottleneck of Moore's Law.It is very important to study new computing models to deal with the problem of insufficient computing power in the future.Membrane computing is a branch of natural computing.It is a kind of computational model inspired by the structure and activity of biological cells.The machine of membrane calculation is also called The P system.According to the maximum parallelism and uncertainty of material transformation in biological cells,the P system can make better use of this property and solve NP-hard problems in polynomial time by means of exchanging controls for time.In addition to the design of P system model,the theory of P system has also been widely applied in practical fields,such as computer graphics,combinatorial optimization,automatic control,etc.Travelling salesman problem is a classical combinatorial optimization problem,and also an NP-hard problem.It requires the ability to find a shortest path through all vertices once and only once in a given graph.The travelling salesman problem has real-world applications in transportation,logistics,circuit board printing,and DNA sequencing.In solving TSP,with the increasing scale of the problem,it has always been the goal of the researchers to design algorithms with high precision,short time and better stability.Based on the above two points,this thesis conducts relevant research.Based on the definition of cell-like P system in membrane computing theory,a cell-like P system?_TSPof solving the traveling salesman problem,was designed and its membrane structure and evolution rules were also designed.At the same time,inspired by Membrane computation and biological cells,a Membrane Evolutionary Algorithm(MEA)is proposed.On this basis,the corresponding Membrane Evolutionary operator is designed for the traveling Salesman Problem,and MEATSP,the Evolutionary Algorithm for the traveling Salesman Problem,is proposed.The main research work of this thesis is as follows:According to the theory of membrane calculation and the definition of the cell-like P-system,?_TSP,a cell-like P-system for solving the traveling salesman problem,was designed.A new solution is proposed for the membrane model to solve the combinational optimization problem,and an example is given to demonstrate the feasibility of the model to calculate the traveling salesman problem.The membrane evolution algorithm MEA is proposed,and based on this,the membrane evolution algorithm MEATSP is proposed to solve the travel agent problem through the design of the membrane evolution algorithm operator and fitness function.It is a breakthrough in applying the theory of membrane computation to practical problems.Moreover,experiments on TSPLIB examples are compared with the excellent heuristic algorithms in recent years.The results show that MEATSP has excellent performance and stability in solving TSP of different sizes and types.The membrane evolutionary algorithm proposed in this thesis is an abstract heuristic algorithm based on the membrane computing theory for the structure and function of biological cells,which has certain reference value for solving combinatorial optimization problems.