Research On The Algorithm Of Constraint Satisfaction Problem Based On Biochemical Reaction

Constraint Satisfaction problem(CSP)extensively exists in scientific research and engineering practice.For example,these problems include human resource allocation problem,crop layout optimization problem,design optimization problem,resource allocation optimization and so on.Usually,it is difficult to solve such complicated engineering problems,in which many constraint conditions must be satisfied simultaneously.However,solving these problems can lead to high social and economic value.As we know,it is proved that CSP is a typical NP-hard problem,so it is difficult to effectively solve these problems by adopting traditional method.Usually,these problems can be reduced to typical CSP,such as minimum vertex covering problem.Therefore,solving the typical CSP can bring new idea and methods for the solution of these problems.How to solve the CSP problem is a key task to these problems,in which it is difficult to obtain the solution of these problems by using traditional computer along with the extending of the problems.In recent years,inspired by biochemical reactions in nature,many intelligent DNA computing algorithms are proposed based on biochemical reactions,which is a non-traditional high performance computing technique.Its merits include highly parallel distributed computing,more parallel operations(more than 1018),and solving NP-hard problem within polynominal time.The experiments indicate that in distribution the chemical reaction optimization algorithm is superior to other heuristic algorithms such as genetic algorithm and tabu search algorithm,owing to its avoiding falling into the local optimal value when solving NP-hard problems.By means of chemical reaction-based DNA computing and chemical reaction optimization algorithm,this paper proposes many relevant algorithms to solve typical constraint satisfaction problems.The experimental results show that the proposed algorithms have good performance and scalability.Main work and innovation points are as follows.1)An algorithm of DNA computing based on divide and conquer to sovle N queens problem is proposed.The N queens problem is a typical CSP problem,and it can be accurately solved by using DNA computing within polynomial time based on sticker model.However,the number of DNA chains involved in chemical reaction is exponential,which can lead to high error rate in solving procedure,so it is difficult to solve a large-scale problem.According to the characteristics of the N queens problem solved by using DNA computing,combining Aldeman-Lipton biochemical operation model and paste model,we propose a new algorithm of DNA computing to solve the N queens problem by introducing traditional divide and conquer strategy.The comparative analysis with existing methods suggest that the proposed algorithm can obviously reduce the time complexity from the exhaustive O(nn)to sub-exponential O(nn/2)number of DNA strands,and the number of the used test tubes from the O(n)to O(1).2)An algorithm of DNA computing to sovle the minimum vertex covering problem based on the DNA assembly model is proposed.Although the N queens problem can be sub-exponentially solved by using the divide and conquer algorithm based on the extended sticker model,the error rate is also very high because the DNA chains involved in chemical reaction are single chain.We propose a DNA computing algorithm based on DNA self-assembly model to solve minimum vertex covering problem.The self-assembly model is a new model of biological molecular computing,and it can reduce the number of biochemical operations and the error rate of solution in the process of biochemical operation.The paper gives the DNA molecule coding scheme and solving method in details,and simulation experiments are performed.The experimental results show that the proposed algorithm can effectively solve the minimum vertex covering problem.Especially,the complexity of biochemical operation is greatly decreased,and the error rate of the biochemical solution is also degraded.The merits of the proposed algorithm include lower complexity of biochemical experiments and better operability.3)A novel DNA computing algorithm is proposed by using molecular junction and self-assembly model to solve the N queens problem.There is only one constraint condition in the minimum vertex covering problem,but in the N queens problem there are many constraint conditions,so we study the CSP problem with more constraint conditions based on DNA self-assembly model by taking solving N queens problem with DNA computing for example.In the N queens problem there are four conditions:no two queens in each row,each column and two diagonal in a board.By skilledly designing junction molecule several conditions can be combined into one condition so that the N queens problem is solved based on DNA self-assembly model.The simulation experiments indicate that the proposed method is effective in performance and has better extendibility.The molecular block tiles population used in the algorithm is O(2n),and the biochemical complexity of operation is O(1),where n is the queen’s number.4)A novel algorithm is proposed to solve the N queens problem based on a hybrid CRO method.Based on DNA computing,although the typical CSP problem can be accurately solved within polynomial time by its great parallel,the number of DNA strands or tile blocks involved in chemical reaction is exponential or sub-exponential.Although many improved methods lowering the error rate of biochemical reaction are proposed,for solving large-scale CSP problem,the error rate of DNA computing is still unacceptable,so the intelligent heuristic optimization algorithm is still a high efficient one in solving CSP problem.Acturally,the chemical reaction optimization algorithm proposed in recent years belongs to an intelligent heuristic algorithm.The algorithm can avoid falling into local optimal search and can improve problem search space.The hybrid CRO algorithm by combining the two algorithms is proposed to solve the N queens problem.Compared with other intelligent heuristic algorithms,the proposed algorithm can effectively avoid local optimum in search,and can effectively expand the search space of the problem.The experimental analysis also shows that the proposed algorithm can greatly improve the efficiency of solving the N queens problem and has the merits of good distribution and quick convergence speed.