Evolution is a major computing tool. Its effectiveness can be seen in a large variety of problems. A number of evolutionary algorithms exist that differ in the mechanism in which they represent the problem and carry out the evolutionary process. In this chapter, the authors extend the ideas of the previous chapter to look for more evolutionary concepts and algorithms. The first major class includes swarm intelligence algorithms, where they primarily study particle swarm optimization, ant colony optimization, artificial bee colonies, and probability-based incremental learning. In all these algorithms, the basic motive is to use a number of particles that form a complete population, and optimization is carried out by their mutual interaction. The other major algorithm that the authors study in the chapter is Genetic Programming, which forms a major pillar of evolutionary computation. Here, the individual is a program whose execution results in the estimation of fitness denoting the goodness of problem solving. The various operators are modified to enable the representation of the individual to work. A tree-based representation is one of the most commonly used representations. They further study a linear representation of the program, and the underlying technique is known as grammatical evolution. All the algorithms are applied to the problem of motion planning of mobile robots.
TopIntroduction
Evolutionary computing is a very versatile computing paradigm that finds applications in a very large variety of problems. It is an easy endeavor to model the problem and use an evolutionary computing technique for problem solving. Evolutionary techniques are widely used, especially for the purpose of optimization. This computing technique is able to evolve the complete system, with fewer or no difficulties. The evolution may be of a machine design, pattern design, or a robotic path. These algorithms may, however, have large computational times in some occasions. This is especially true when the fitness function that measures the goodness of a solution is time consuming. In such a case, the maximum number of evaluations we may do of the fitness function is limited. This puts a heavy restriction on the maximum number of individuals and generations that the entire system may have. Hence, the task is the generation of effective individuals or solutions to the problem with as few fitness function calls as possible.
The entire paradigm of evolutionary computing may be bifurcated into four major pillars. These are genetic algorithms, genetic programming, evolutionary programming, and evolutionary strategies. We studied the genetic algorithm and the evolutionary strategies in the previous chapter. The Genetic Algorithms had a real representation of the problem. Here, the problem parameters in their phenotypic form were stuffed into a genetic individual, which made its genotypic form. This mechanism of individual representation was used in the entire cycle of evolution. In evolutionary strategies, the basic motive was self-adaptation. Here, the complete individual was stuffed with some extra parameters known as the strategy parameters. These parameters enabled the optimization of the parameters used for the purpose of evolution. These parameters let to the computation of the desired mutation rate. The problem parameters were later mutated using this mutation rate computed by the strategy parameters.
The basic focus of this chapter is to introduce other exciting evolutionary paradigms. Here, we would discuss swarm intelligence and genetic programming. The basic motivation behind the swarm intelligence is to understand the mechanism in which a collective effort of multiple particles or problem solutions can lead to optimization. Here, we take a real representation of the problem. While most of the evolutionary concepts remain similar to the discussions with genetic algorithms in the previous chapter, we take a greater look at the problem solving methodology and the evolutionary operators used in this case. Under this head, a variety of algorithms exist, each one of them inspired from some biological phenomenon.
The other major topic of discussion in the chapter is geneticprogramming that forms one of the major pillars of evolutionary algorithms. Here, the discussion involves the mechanism of representing an evolutionary individual as a program and to use the same for optimization. We discuss the tree-based representation and later advance to the linear representation, which is used in the grammaticalevolution technique.
The basic problem being dealt with is the problem of robot path planning. Here, we are given a robotic map, and need to find a path from the source to the destination for the robot. This path needs to be without collision. Further, the path so evolved needs to be preferably as smooth as possible. The smoothness enables a robotic controller to physically move the robot at high speeds. There is always a limit to the time the planning algorithm may take to generate the trajectory. Taking a large amount of time may change the map, and the output of the planner may not be valid. Ideally, the planning time needs to be as small as possible. However, the plans generated in a short amount of time may not be optimal or complete.
This chapter first presents the basic computing paradigms of particle swarm optimization, genetic programming, and grammatical evolution. A number of swarm techniques have been duly explained, including the particle swarm optimization, ant colony optimization, etc. While the swarm intelligence algorithms have the similar mechanism of problem representation and working as the genetic algorithms, we briefly discuss their mechanism of solving the problem of robot motion planning. The solution with the use of grammatical evolution for the problem is taken explicitly. All these discussions follow in the chapter.