Parameterized analysis of bio-inspired computation and the traveling salesperson problem.

Abstract

Bio-inspired algorithms such as evolutionary algorithms (EA) and ant colony optimization (ACO) have become very popular in recent years to solve a wide range of complex real world problems. However, the understanding about the conditions under which these algorithms perform well is still limited. Classical computational complexity analysis often taking a worst case perspective, hardly captures what is happening during the actual algorithm run and, lacks implications for guiding algorithm design. This issue is more significant on the problems such as the traveling salesperson problem (TSP) where the problem is hard in a theoretical sense and has a lot of real world applications. Thus, more practical perspectives of algorithm analysis and design are essential to bridge the gap between the theory and the practice in bio-inspired computation specially with respect to the hard problems such as the TSP. We introduce “parameterized analysis” of bio-inspired computation by linking together several emerging methods of algorithm analysis and design with the aim of explaining the relationship between various problem and algorithm parameters and their effects on the algorithm performance. Moreover, we gain novel insights into bio-inspired computation and the TSP through parameterized analysis.