Modified Genetic Algorithm to Traveling Salesman Problem for Large Input Datasets
DOI:
https://doi.org/10.11145/bmc.2016.06.157Abstract
The use of graphs is widely applied in modeling and solving problems in the field of computer science and bioinformatics.
Therefore, it is essential to develop and improve algorithms reducing their computational complexity andВ increasing the precision of the solutions generated by them as well as the size of the input data.
In this study two well-known algorithms for solving the problem for finding a minimum Hamiltonian cycle in weighted, undirected and complete graph (also known as Travelling Salesman Problem - TSP) are analyzed.
The first algorithm is based on the backtracking method and it always finds the optimal solution, while with the second one, the genetic algorithm (GA), finding the optimal solution is not always guaranteed.
The aims of the study are to determine: (1)which of the algorithms can be used so that the resulting solution is optimal or near-optimal and the execution time be reasonable depending on the size of the input data; (2)the influence of GA parameter values on the quality of the resulting solutions for large size of the input data. The parameters determine the number of solutions in each population and the number of all generations.
The analysis of the results revealed that:(1) the algorithm that finds all possible solutions can be used for graphs with a small number of vertices (not more than 20), whereas GA can be used for graphs with a large number of vertices; (2) in graphs with a small number of vertices: n<20 (and n*(n-1)/2 edges) GA always finds the optimal solution as long asВ enoughВ solution space is set. However, the number of all Hamiltonian cycles in a complete graph with n vertices ((n-1)!/2) is bigger than the solution space; (3) all input datasets showed that with the number increase of vertices in the graph it is necessary to increase the number of the current solutions in the population. In this way GA reaches a certain rate of convergence faster, i.e.,В a generation after which the space of solutions contains only optimal solutions or near optimal ones.
Acknowledgments: This work is partially supported by the project of the Bulgarian National Science Fund, entitled: Bioinformatics research: protein folding, docking and prediction of biological activity, NSF I02/16, 12.12.14.
Downloads
Published
Issue
Section
License
The journal Biomath Communications is an open access journal. All published articles are immeditely available online and the respective DOI link activated. All articles can be access for free and no reader registration of any sort is required. No fees are charged to authors for article submission or processing. Online publications are funded through volunteer work, donations and grants.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
