A Parallel Bioinspired Algorithm for Chinese Postman Problem Based on Molecular Computing
Authors:
Open Access
- 16 January 2021
- journal article
- research article
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2021 (1)
Abstract
The Chinese postman problem is a classic resource allocation and scheduling problem, which has been widely used in practice. As a classical nondeterministic polynomial problem, finding its efficient algorithm has always been the research direction of scholars. In this paper, a new bioinspired algorithm is proposed to solve the Chinese postman problem based on molecular computation, which has the advantages of high computational efficiency, large storage capacity, and strong parallel computing ability. In the calculation, DNA chain is used to properly represent the vertex, edge, and corresponding weight, and then all possible path combinations are effectively generated through biochemical reactions. The feasible solution space is obtained by deleting the nonfeasible solution chains, and the optimal solution is solved by algorithm. Then the computational complexity and feasibility of the DNA algorithm are proved. By comparison, it is found that the computational complexity of the DNA algorithm is significantly better than that of previous algorithms. The correctness of the algorithm is verified by simulation experiments. With the maturity of biological operation technology, this algorithm has a broad application space in solving large‐scale combinatorial optimization problems.Keywords
Funding Information
- National Natural Science Foundation of China (11701363, RC202002)
This publication has 52 references indexed in Scilit:
- A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequencesBioSystems, 2011
- Heuristics for the rural postman problemComputers & Operations Research, 2010
- A polynomial-time DNA computing solution for the Bin-Packing ProblemApplied Mathematics and Computation, 2009
- Parallel DNA arithmetic operation based on n-moduli setApplied Mathematics and Computation, 2009
- DNA approach to solve clustering problem based on a mutual orderBioSystems, 2008
- DNA ternary additionApplied Mathematics and Computation, 2006
- Research on Chinese Postman Problem Decision Process AlgorithmJournal of Computer Research and Development, 2005
- Solution of a 20-Variable 3-SAT Problem on a DNA ComputerScience, 2002
- DNA Solution of Hard Computational ProblemsScience, 1995
- Molecular Computation of Solutions to Combinatorial ProblemsScience, 1994