Hybrid Evolutionary Methods

Hybrid Evolutionary Methods

Copyright: © 2013 |Pages: 39
DOI: 10.4018/978-1-4666-2074-2.ch008
OnDemand PDF Download:


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.
Chapter Preview


The attempt to eliminate the limitations of the individual algorithms leads us to the use of hybrid techniques planning. The attempt is to study the limitations of an algorithm of choice, and to later attempt to find a manner or an algorithm that can remove the limitations and enhance the advantages. We have been studying this notion of hybridization of the algorithms to solve the problem of motion planning for mobile robots. The base algorithm that we study in this chapter is evolutionary algorithm. The aim is to make some changes in the conventional problem solving in evolutionary robotics, which was discussed in detail in chapters 4 and 5.

Evolution has always been seen as the future of robotics. Increasing efforts are being made to enable evolutionary algorithms specify complete design of robotics from hardware and/or algorithmic point of view. The ability of evolutionary algorithms to evolve complicated structures is the sole reason behind the same. A number of component designs of robots are current being produced by evolutionary algorithms. Evolutionary algorithms are increasingly used in industry for on-board circuit designs. The control algorithms used in modern robots are further worked over by evolutionary algorithms. These algorithms enable robots do complex tasks as per requirement. All these works can be done off-line, and hence, computational time is not a constraint.

One of the major limitations of the evolutionary algorithm is its time consuming nature. Especially in maps having very large resolution, these algorithms struggle to give decent results within time. This makes these algorithms inefficient. Most robotic problems require the solutions to be real time in nature. For these reasons, it is a requirement for the planning algorithm to work in real time. Hence, in this chapter, we attempt to make the algorithm as time efficient as possible. The various advantages and disadvantages of evolutionary algorithms, that forms the basis of this chapter, are discussed in Table 1.

Table 1.
Advantages and disadvantages of evolutionary algorithms
S. No.AdvantagesDisadvantages
1.Small computation time to generate initial (sub-optimal) solutionsHigh overall computational time for high resolution maps
2.IterativePossibility of immature convergence
4.Probabilistically optimal (not too complex paths)Non-complete in narrow corridors and complex paths
5.Probabilistically complete (not too complex paths)Non-optimal in complex paths

Complete Chapter List

Search this Book: