Using Genetic Algorithm with Combinational Crossover to solve Travelling Salesman Problem

Abstract

This paper proposes a new solution for Traveling Salesman Problem (TSP) using genetic algorithm. A combinational crossover technique is employed in the search for optimal or near-optimal TSP solutions. It is based upon chromosomes that utilise the concept of heritable building blocks. Moreover, generation of a single offspring, rather than two, per pair of parents, allows the system to generate high performance chromosomes. This solution is compared with the well performing Ordered Crossover (OX). Experimental results demonstrate that, due to the well structured crossover technique, has enhanced performance.