Hossain, Md. Sabir and Tanim, Ahsan Sadee and Choudhury, Sadman Sakib and Hayat, S. M. Afif Ibne and M. Nomani, Kabir and Islam, Mohammad Mainul (2019) An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator. EMITTER International Journal of Engineering Technology, 7 (2). pp. 480-493. ISSN 2355-391X. (Published)
|
Pdf
An Efficient Solution to Travelling Salesman Problem.pdf Available under License Creative Commons Attribution Non-commercial Share Alike. Download (574kB) | Preview |
Abstract
The traveling salesman problem (TSP) is a famous NP-hard problem in the area of combinatorial optimization. It is utilized to locate the shortest possible route that visits every city precisely once and comes back to the beginning point from a given set of cities and distance. This paper proposes an efficient and effective solution for solving such a query. A modified crossover method using Minimal Weight Variable, Order Selection Crossover operator, a modified mutation using local optimization and a modified selection method using KMST is proposed. The crossover operator (MWVOSX) chooses a particular order from multiple orders which have the minimum cost and takes the remaining from the other parent in backward and forward order. Then it creates two new offspring. Further, it selects the least weight new offspring from those two offspring. The efficiency of the proposed algorithm is compared to the classical genetic algorithm. Comparisons show that our proposed algorithm provides much efficient results than the existing classical genetic algorithm.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Traveling Salesman Problem, Crossover Operator, Minimal Weight Variable, Genetic Algorithm, |
| Subjects: | Q Science > QA Mathematics > QA76 Computer software |
| Faculty/Division: | Faculty of Computer System And Software Engineering |
| Depositing User: | Dr. Muhammad Nomani Kabir |
| Date Deposited: | 30 Mar 2020 00:07 |
| Last Modified: | 30 Mar 2020 00:07 |
| URI: | http://umpir.ump.edu.my/id/eprint/27534 |
| Download Statistic: | View Download Statistics |
Actions (login required)
 |
View Item |