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

Xiaomin Ren; Xiaoming Wang; Zhaocai Wang; Tunhua Wu

doi:10.2991/ijcis.d.201127.001

<Previous Article In Issue

Next Article In Issue>

Volume 14, Issue 1, 2021, Pages 228 - 237

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

Authors

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

¹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

Corresponding Authors

Zhaocai Wang, Tunhua Wu

Received 21 May 2020, Accepted 18 November 2020, Available Online 3 December 2020.

DOI: 10.2991/ijcis.d.201127.001 How 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$ $n$ nodes are divided into $m$ $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 (n^{2})$ $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)

<Previous Article In Issue

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 14 - 1
Pages: 228 - 237
Publication Date: 2020/12/03
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.d.201127.001 How to use a DOI?
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/).

Cite this article

ris enw bib

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  -

download .riscopy to clipboard