An Artificial Ecosystem Algorithm applied to static and Dynamic Travelling Salesman Problems

摘要

An ecosystem inspired algorithm that aims to take advantage of highly distributed computer architectures is proposed. The motivation behind this work is to grasp the phenomenal properties of ecosystems and use them for large-scale real-world problems. Just as an ecosystem comprises many separate components that adapt together to form a single synergistic whole, the Artificial Ecosystem Algorithm (AEA) solves a problem by adapting subcomponents of a problem such that they fit together and form a single optimal solution. AEA uses populations of solution components that are solved individually such that they combine to form the candidate solution, unlike typical biology inspired algorithms like GA, PSO, BCO, and ACO that regard each individual in a population as a candidate solution. Like species in an ecosystem, the AEA may have species of components representing sub-parts of the solution that evolve together and cooperate with the other species. Three versions of this algorithm are illustrated: the basic AEA algorithm, and two AEA with Species. These algorithms are evaluated through a series of experiments on symmetric and dynamic Travelling Salesman Problems that show very promising results compared to existing approaches. Experiments also show very promising results for the Dynamic TSP making this method potentially useful for handling dynamic routing problems.