Research And Application Of Combinatorial Optimization Algorithms Based On Membrane Computing

Membrane computing is inspired from the cells,tissues,organs and the other organisms.It focuses on the life activities,organizational structure and working mode of biological cells,and then abstracts and simulates them.It is a new branch of nature computing.Membrane computing has a distributed parallel computing framework.Its uncertainty and maximal parallelism greatly improve the computing power.It is excellent in solving the problem of large amount of data and attracts the attention of many researchers.The concepts related to membrane computing have been widely used in clustering problem,graph theory problem,combination optimization,etc.Combinatorial optimization is a problem of finding the optimal solution from the feasible solution set of the problem,and it is an important basis for the study of computational complexity theory.The 0-1 knapsack problem aims to find a loading method that maximizes the total value of the items in the knapsack without exceeding the carrying capacity of the knapsack.It belongs to the field of combinatorial optimization.The most characteristic of 0-1 knapsack problem is that the exponential growth in the solution space when the number of items in the knapsack increases.This makes 0-1knapsack problem NP problem.The immune system is a natural classification system,and has excellent characteristics of self-organization,learning,memory and so on.Immune classification is one of the key points in artificial immunity research.The distinction between"autologous"and"non-autologous"is a natural feature of the immune system,which will differentiate substances according to different response results after successful differentiation.A stronger and faster response will be acted on similar"non-self"encounters again.In this paper the P system is applied to combinatorial optimization and information processing,based on the characteristics of maximum parallelism and uncertainty of P system.The following is the main content:?1?An algorithm in linear time for finding the optimal solution of 0-1 knapsack problem is proposed based on the tissue P system with cell division.There are the corresponding P system named ?_KP,the rules used and the membrane relationship in the system.The computational performance and parallel characteristics of ?_KP are analyzed,and its correctness and practicability are illustrated by example description and simulation experiments on several data sets.?2?A classification P system named ?_NS is designed based on cell-like P system and immune algorithm,including its membrane structure and rules.The computational performance of ?_NS is analyzed,and its correctness and practicability are illustrated by simulation and comparative experiments.The maximum parallelism and uncertainty of membrane computing are applied to immune algorithm to improve the parallelism and speed up the search.The proposals of ?_KP and ?_NS are of great significance in the fields of membrane computing model,combinatorial optimization and classification problem.The emergence of ?_KP provides a new approach and solution pattern in which membrane computation obtains the optimal solution of combinatorial optimization problem with lower time complexity.?_NScombines membrane computing with immune algorithm to solve classification problems.It processes data according to biological concepts related to immune algorithm.Considering the flow of immune algorithm,a feasible and efficient model of membrane computing is provided by combining the rules of membrane structure design,which provides a new idea for parallel implementation of immune algorithm.Combining the flow of immune algorithm with the design of rules in the membrane,a feasible and effective membrane computing model is proposed,which provides a new method for parallel implementation of immune algorithm.