Self-Crossover Based Genetic Algorithm for Performance Augmentation of the Traveling Salesman Problem
Nicholas D. Ernest, Kelly De Oliveira Cohen · Infotech@Aerospace 2011 · 2011
A genetic algorithm (GA) based approach to the path representation of the Traveling Salesman Problem (TSP) will be presented towards potential application to co-operative control of a group of UAVs. The scenario involves a random distribution of cities on a two dimensional grid or a pre-defined set of targets, and determines the optimal path solution of the TSP by means of an iterative algorithm. Similar codes based on genetic algorithms are in existence; however, a unique set of modifications are utilized in this study. Generally speaking, when applying a GA to the TSP, traditional crossover is not permitted, as a city could be visited twice using this method. To circumvent this issue and optimize algorithm efficiency, we introduce a concept referred to as SCROOGE (Self CROssover Optimal GEnetic algorithm). This algorithm will be utilizing a combination of self-crossover and mutation of the strings making up the population. Through selfcrossover, a single string is chosen for breeding, and has a chance to produce an offspring based off of its own genetic material, much as a starfish or many other animals would in nature. Additionally, SCROOGE’s parameters morph with time, becoming more focused on avoiding local minima as iterations progress.