Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
2. Bio-Inspired Machine Learning Algorithm: Genetic Algorithm
verfasst von : Khaled Salah Mohamed
Erschienen in: Machine Learning for Model Order Reduction
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Genetic algorithms (GA) are the heuristic (experience-based) search and time-efficient learning and optimization techniques that mimic the process of natural evolution based on Darwinian Paradigm as depicted in Fig. 2.1. Thus genetic algorithms implement the optimization strategies by simulating evolution of species through natural selection. The nature to computer mapping is shown in Table 2.1, where each cell of a living thing contains chromosomes (strings of DNA), each chromosome contains a set of genes (blocks of DNA), and each gene determines some aspect of the organism (like eye color). In other words, parameters of the solution (genes) are concatenated to form a string (chromosome). In a chromosome, each gene controls a particular characteristic of the individual. The population evolves toward the optimal solution as depicted in Fig. 2.2. Evolution based on “survival of the fittest.” Genetic algorithms are well suited for hard problems where little is known about the underlying search space. So, it is considered a robust search and optimization mechanism. The genetic algorithm used in this work consists of the following steps or operations, [1–11], and can be seen in Fig. 2.3:
1.
Initialization and encoding:
The GA starts with the creation of random strings, which represent each member in the population.
2.
Evaluation (Fitness):
The fitness used as a measure to reflect the degree of goodness of the individual is calculated for each individual in the population.
3.
Selection:
In the selection process, individuals are chosen from the current population to enter a mating pool devoted to the creation of new individuals for the next generation such that the chance of a given individual to be selected to mate is proportional to its relative fitness. This means that best individuals receive more copies in subsequent generations so that their desirable traits may be passed onto their offspring. This step ensures that the overall quality of the population increases from one generation to the next.
The different techniques used in selection process for introducing new individuals for the next generation are:
-
Elitism selection: It is simply selecting the fitted individuals crated from the current population and passing them to the next population. This method guarantees a high probability of getting closer to the most optimum solution due to passing of the fittest chromosomes to the crossover operator producing fitter individuals.
-
Roulette Wheel Selection: In this kind of selection the parenthood probability is directly proportional to the fitness of the individuals. Every individual is given a weight proportional to its fitness having a higher probability to be chosen in the next generation. There is a notable disadvantage in this method of selection which is if some individuals have a higher fitness than others, there is a probability that they will be chosen as parents for every individual in the next generation. The wheel rotating can be realized by generating a random number and comparing it to random selected individual in the current generation.
-
Tournament selection: It occurs by choosing 4 or 8 or 2 n individuals from the current population and comparing each two of them randomly and so on till having one individual which is the fittest one. This process occurs as many needed time to form the new population.
-
Rank selection: In this kind of selection all individuals in the population are ranked according to their fitness. Each individual is assigned a weight inversely proportional to the rank.
4.
Crossover:
Crossover provides the means by which valuable information is shared among the population. It combines the features of two parent individuals to form two children individuals that may have new patterns compared to those of their parents and plays a central role in Gas. The crossover operator takes two chromosomes and interchanges part of their genetic information to produce two new chromosomes.
The different techniques used in crossover process for introducing new individuals for the next generation are:
-
Simple crossover: It is a process of exchanging some genes of the chromosomes or some chromosomes of the individual depending on the representation creating new individuals of new chromosomes. It depends on crossover rate which is previously identified.
-
Heuristic crossover: Choosing two individuals from the current individual randomly and computing the fitness of each individual and comparing them to each other. The fitter individual is passed to the next population and the other one is not passed and instead a new individual is created.
-
Arithmetic crossover: Arithmetic crossover occurs by choosing two or more individuals randomly from the current generation and multiplying them by one random in the case of the inevitability of the presence of a certain defined domain and more than one random if there is no physical need for a defined search domain.
5.
Mutation:
Mutation is often introduced to guard against premature convergence. Generally, over a period of several generations, the gene pool tends to become more and more homogeneous. The purpose of mutation is to introduce occasional perturbations to the parameters to maintain genetic diversity within the population.
6.
Replacement:
After generating the offspring’s population through the application of the genetic operators to the parents’ population, the parents’ population is totally replaced by the offspring’s population. This is known as no overlapping, generational, replacement. This completes the “life cycle” of the population.
7.
Termination:
The GA is terminated when some convergence criterion is met. Possible convergence criteria are: the fitness of the best individual so far found exceeds a threshold value; the maximum number of generations is reached. An example for the parameter used in GA is shown in Table 2.2.