A Parallel Bioinspired Algorithm for Chinese Postman Problem Based on Molecular Computing

被引:9
作者
Wang, Zhaocai [1 ]
Bao, Xiaoguang [1 ]
Wu, Tunhua [2 ]
机构
[1] Shanghai Ocean Univ, Coll Informat, Shanghai 201306, Peoples R China
[2] Wenzhou Business Coll, Sch Informat Engn, Wenzhou 325035, Peoples R China
基金
中国国家自然科学基金;
关键词
POLYNOMIAL-TIME; OPTIMIZATION ALGORITHM; DNA ALGORITHM; SOLVE; COEXISTENCE; SYSTEM;
D O I
10.1155/2021/8814947
中图分类号
Q [生物科学];
学科分类号
07 ; 0710 ; 09 ;
摘要
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.
引用
收藏
页数:13
相关论文
共 50 条
  • [41] Parallel tempered genetic algorithm guided by deep neural networks for inverse molecular design
    Nigam, AkshatKumar
    Pollice, Robert
    Aspuru-Guzik, Alan
    [J]. DIGITAL DISCOVERY, 2022, 1 (04): : 390 - 404
  • [42] Reservoir Computing Based on Two Parallel Reservoirs Under Identical Electrical Message Injection
    Yue, Dian-Zuo
    Wu, Zheng-Mao
    Hou, Yu-Shuang
    Hu, Chun-Xia
    Jiang, Zai-Fu
    Xia, Guang-Qiong
    [J]. IEEE PHOTONICS JOURNAL, 2021, 13 (01):
  • [43] Near real-time digital holographic microscope based on GPU parallel computing
    Zhu, Gang
    Zhao, Zhixiong
    Wang, Huarui
    Yang, Yan
    [J]. 2017 INTERNATIONAL CONFERENCE ON OPTICAL INSTRUMENTS AND TECHNOLOGY: OPTICAL SYSTEMS AND MODERN OPTOELECTRONIC INSTRUMENTS, 2017, 10616
  • [44] Scalable photonic reservoir computing based on pulse propagation in parallel passive dispersive links
    Cai, Xinyi
    Yang, Shuna
    Yang, Bo
    Zhai, Yanrong
    Jin, Tao
    Chi, Hao
    [J]. APPLIED OPTICS, 2024, 63 (22) : 5785 - 5791
  • [45] A meta-heuristic based on the Imperialist Competitive Algorithm (ICA) for solving Hybrid Flow Shop (HFS) scheduling problem with unrelated parallel machines
    Garavito-Hernandez, Edwin
    Pena-Tibaduiza, Eliana
    Perez-Figueredo, Luis E.
    Moratto-Chimenty, Eslendis
    [J]. JOURNAL OF INDUSTRIAL AND PRODUCTION ENGINEERING, 2019, 36 (06) : 362 - 370
  • [46] Multi Operators-based Partial Connected Parallel Evolutionary Algorithm
    Laili, Yuanjun
    Tao, Fet
    Zhang, Lin
    [J]. 2016 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2016, : 4289 - 4296
  • [47] Scheduling Strategy of Space-based Satellite Based on Fireworks Algorithm under Cloud Computing
    Tian, Guilin
    Liu, Changyun
    Jiang, Haobo
    [J]. ICBDC 2019: PROCEEDINGS OF 2019 4TH INTERNATIONAL CONFERENCE ON BIG DATA AND COMPUTING, 2019, : 91 - 96
  • [48] Discussion on Knapsack Problem Optimization Algorithm Based on Complex Network
    Xiao Meng
    Zhou Yunyao
    [J]. MECHATRONICS ENGINEERING, COMPUTING AND INFORMATION TECHNOLOGY, 2014, 556-562 : 3354 - +
  • [49] A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem
    Rahmati, Seyed Habib A.
    Hajipour, Vahid
    Niaki, Seyed Taghi Akhavan
    [J]. APPLIED SOFT COMPUTING, 2013, 13 (04) : 1728 - 1740
  • [50] A GA-based algorithm meets the fair ranking problem
    Tahery, Saedeh
    Aftabi, Seyyede Zahra
    Farzi, Saeed
    [J]. INFORMATION PROCESSING & MANAGEMENT, 2021, 58 (06)