A Parallel DNA Algorithm for Solving the Quota Traveling Salesman Problem Based on Biocomputing Model

The quota traveling salesman problem (QTSP) is a variant of the traveling salesman problem (TSP), which is a classical optimization problem. In the QTSP, the salesman visits some of the n cities to meet a given sales quota Q while having minimized travel costs. In this paper, we develop a DNA algorithm based on Adleman-Lipton model to solve the quota traveling salesman problem. Its time complexity is O(n²+Q), which is a significant improvement over previous algorithms with exponential complexity. A coding scheme of element information is pointed out, and a reasonable biological algorithm is raised by using limited conditions, whose feasibility is verified by simulation experiments. The innovation of this study is to propose a polynomial time complexity algorithm to solve the QTSP. This advantage will become more obvious as the problem scale increases compared with the algorithm of exponential computational complexity. The proposed DNA algorithm also has the significant advantages of having a large storage capacity and consuming less energy during the operation. With the maturity of DNA manipulation technology, DNA computing, as one of the parallel biological computing methods, has the potential to solve more complex NP-hard problems.

A Hybrid Model for Water Quality Prediction Based on an Artificial Neural Network, Wavelet Transform, and Long Short-Term Memory

Clean water is an indispensable essential resource on which humans and other living beings depend. Therefore, the establishment of a water quality prediction model to predict future water quality conditions has a significant social and economic value. In this study, a model based on an artificial neural network (ANN), discrete wavelet transform (DWT), and long short-term memory (LSTM) was constructed to predict the water quality of the Jinjiang River. Firstly, a multi-layer perceptron neural network was used to process the missing values based on the time series in the water quality dataset used in this research. Secondly, the Daubechies 5 (Db5) wavelet was used to divide the water quality data into low-frequency signals and high-frequency signals. Then, the signals were used as the input of LSTM, and LSTM was used for training, testing, and prediction. Finally, the prediction results were compared with the nonlinear auto regression (NAR) neural network model, the ANN-LSTM model, the ARIMA model, multi-layer perceptron neural networks, the LSTM model, and the CNN-LSTM model. The outcome indicated that the ANN-WT-LSTM model proposed in this study performed better than previous models in many evaluation indices. Therefore, the research methods of this study can provide technical support and practical reference for water quality monitoring and the management of the Jinjiang River and other basins.

Solving the Family Traveling Salesperson Problem in the Adleman-Lipton model based on DNA computing

The Family Traveling Salesperson Problem (FTSP) is a variant of the Traveling Salesperson Problem (TSP), in which all vertices are divided into several different families, and the goal of the problem is to find a loop that concatenates a specified number of vertices with minimal loop overhead. As a Non-deterministic Polynomial Complete (NP-complete) problem, it is difficult to deal with it by the traditional computing. On the contrary, as a computer with strong parallel ability, the DNA computer has incomparable advantages over digital computers when dealing with NP problems. Based on this, a DNA algorithm is proposed to deal with FTSP based on the Adleman-Lipton model. In the algorithm, the solution of the problem can be obtained by executing several basic biological manipulations on DNA molecules with O(N2) computing complexity (N is the number of vertices in the problem without the origin). Through the simulation experiments on some benchmark instances, the results show that the parallel DNA algorithm has better performance than traditional computing. The effectiveness of the algorithm is verified by deducing the algorithm process in detail. Furthermore, the algorithm further proves that DNA computing, as one of the parallel computing methods, has the potential to solve more complex big data problems.