Machine Learning Based Analysis of Proposed Memetic Algorithm and Its Application in Traveling Salesman Problem

Abstract

Many combinatorial problems exist in the real world, such as real-world routing problems or industrial problems, that the researchers have addressed during the past two decades. The traveling salesman problem (TSP) is investigated by the researchers in last two decades. It is a prevalent problem studied by computer science researchers. It is a combinatorial minimization problem. The current work focuses on the development and analysis of proposed memetic algorithm inspired by a machine learning approach to solve the TSP. Symmetric Traveling salesman problem is considered to evaluate the effectiveness of the proposed memetic algorithm. newlineTSP is mostly considered as benchmark problem to study the novel meta- heuristic algorithms. It represents the broad class of combinatorial problems. It has practical significance and extensive range of applications, including transportation route optimization, job sequencing, and scheduling, computer board wiring, wallpaper cutting, hole punching, etc. Exhaustive search algorithmic approach generally applied to solve this problem, so that solution can be found in polynomial time. But Exhaustive search algorithms fail for the large-scale problem. For this reason, it is essential to develop and improve meta-heuristic algorithms. Once an effective meta-heuristic algorithm is developed and put into practise, it will be applied to solve different types of other NP-Hard problems such as scheduling, sequencing problems. newline newlineIt has been observed by critically analzing and studying the review of literature, relevant to evolutionary algorithmic approach for the TSP. Genetic algorithm (GA) is the first choice of the most researcher to apply on combinatorial problems to solve it. But GA is facing the premature convergence problem. Due to this effect it structs to the local optima. No further improved is seen during the execution of GA. To overcome the premature convergence local search is incorporating in the GA, so that best solution can be found. newline