Parallel DNA Algorithms of Generalized Traveling Salesman Problem-Based Bioinspired Computing Model

Authors

Xiaomin Ren¹, Xiaoming Wang¹, Zhaocai Wang^{1, *,} , Tunhua Wu^{2, *}

¹College of Information, Shanghai Ocean University, Shanghai, 201306, P. R. China

²School of Information Engineering, Wenzhou Business College, Wenzhou, 325035, P. R. China

^*Corresponding authors. Email: zcwang1028@163.com; appll188@163.com

DOI

10.2991/ijcis.d.201127.001How to use a DOI?

Keywords

DNA computing; Adleman–Lipton model; Generalized traveling salesman problem; NP-hard problem

Abstract

Generalized traveling salesman problem (GTSP) is a classical combinatorial optimization problem, in which the optimization goal is the minimum route combination. Since the GTSP is a more complex problem than the traveling salesman problem (TSP), the GTSP can be considered an extension of the TSP. At present, compared with TSP, GTSP has been widely used in practice. In GTSP, n nodes are divided into m clusters, and the problem is divided into two categories according to different constraints. According to the second kind of the GTSP, we propose a parallel biochemical algorithm to solve it. We use deoxyribonucleic acid (DNA) biological strands to represent different vertices, point groups and weights, and get the optimal solutions to a series of different biochemical reaction combinations of DNA sequences. Compared with other algorithms, our algorithm reduces the time complexity to O(n2), and proves the feasibility.

Copyright

© 2021 The Authors. Published by Atlantis Press B.V.

Open Access

This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)
View full text (HTML)

TY  - JOUR
AU  - Xiaomin Ren
AU  - Xiaoming Wang
AU  - Zhaocai Wang
AU  - Tunhua Wu
PY  - 2020
DA  - 2020/12/03
TI  - Parallel DNA Algorithms of Generalized Traveling Salesman Problem-Based Bioinspired Computing Model
JO  - International Journal of Computational Intelligence Systems
SP  - 228
EP  - 237
VL  - 14
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.d.201127.001
DO  - 10.2991/ijcis.d.201127.001
ID  - Ren2020
ER  -