Hybrid Evolutionary Methods

Abstract

The limitations of single algorithm approaches lead to an attempt to hybridize or fuse multiple algorithms in the hope of removing the underlying limitations. In this chapter, the authors study the evolutionary algorithms for problem solving and try to use them in a unique manner so as to get a better performance. In the first approach, they use an evolutionary algorithm for solving the problem of motion planning in a static environment. An additional factor called momentum is introduced that controls the granularity with which a robotic path is traversed to compute its fitness. By varying the momentum, the map may be treated finer or coarser. The path evolves along the generations, with each generation adding to the maximum possible complexity of the path. Along with complexity (number of turns), the authors optimize the total path length as well as the minimum distance from the obstacle in the robotic path. The requirement of evolutionary parameter individuals as well as the maximum complexity is less at the start and more at the later stages of the algorithm. Momentum is made to decrease as the algorithm proceeds. This makes the exploration vague at the start and detailed at the later stages. As an extension to the same work, in the second approach of the chapter, the authors show the manner in which a hybrid algorithm may be used in place of simple genetic algorithm for solving the problem with momentum. A Hybrid Genetic Algorithm Particle Swarm Optimization (HGAPSO) algorithm, which is a hybrid of a genetic algorithm and particle swarm optimization, is used in the same modeling scenario. In the third and last approach, the authors present a hierarchical evolutionary algorithm that operates in two hierarchies. The coarser hierarchy finds the path in a static environment consisting of the entire robotic map. The resolution of the map is reduced for computational speed. The finer hierarchy takes a section of the map and computes the path for both static and dynamic environments. Both these hierarchies carry optimization as the robot travels in the map. The static environment path gets more and more optimized along with generations. Hence, an extra setup cost is not required like other evolutionary approaches. The finer hierarchy makes the robot easily escape from the moving obstacle, almost following the path shown by the coarser hierarchy. This hierarchy extrapolates the movements of the various objects by assuming them to be moving with same speed and direction.