Genetic Algorithms



Genetic Algorithms

Introduction

The genetic algorithm (GA) belongs to the class of non-deterministic optimizing algorithms (Holland, 1975; De Jong, 1975). One of the GA application problems is that it may be too slow or too fast in terms of its convergence (Baker, 1985; Goldberg and Richardson, 1987; Tanese, 1989), leading to reaching a local optimum by the GA. To solve the above problem different modifications of GAs have appeared (Davis, 1985; Schaffer and Morishima, 1987; Schaffer et al., 1989; Michalewicz, 1992).

The way convergence is reached is influenced to a major degree by the proper selection of control parameters. The aim of determining these values is to reach a compromise, typical for a GA, between the necessity of searching the whole domain (exploration) and that of perfecting the existing solution (exploitation). The optimal control parameter values depend on the concrete problem being solved at the given moment by the algorithm and it requires long and laborious experiments to set these values properly (Schaffer et al., 1989). In order to accelerate and improve the GA performance (with mutation probability being a GA control parameter), a method of defining mutation probability in a dynamic way has been proposed in this paper. The method consists in mutation probability modification when the GA is being generated; it is based on transitory test results and it leads to reaching an optimal mutation probability in a short span.

Genetic algorithms

The idea of genetic algorithms is derived from and inspired by natural processes of the selection of individuals and the evolution of species as well as reproduction mechanisms and the genetic transmission of characteristics. As a result of natural mechanisms new species are originated ousting those that are not adjusted to their environment as well as themselves. Genetic algorithms have to adjust themselves to certain requirements, i.e. to find a global function extremum. They are algorithms that, starting from the initial set of probable solutions to a problem, generate a better and better solution set. New solutions are generated with the use of genetic operators simulating natural reproduction processes. Each element of the domain of solutions (populations) whose number is constant is called a chromosome; its constituent parts are called genes, while genetic operators bear the names of selection, crossover, mutation. It is the searching of the domain by the GA that generates proposed solutions (i.e. the individuals) that are later evaluated by the environment. The role of genetic algorithm environment is played by the so-called "fitness function" defined in all points of the domain which is being searched at a given moment. The function also measures the degree to which a given chromosome is adjusted to the requirements of the problem. The aim of a GA is to improve in a constant way the adjustment function value until a global extremum is reached by that function. In order to construct a GA it is indispensable to define its five component elements: (1) a genetic representation of solutions to a given problem, (2) a method of a generating an ...