How the genetic algorithm works
How the genetic algorithm works
ABDUL STTAR ISMAIL WDAA
Genetic algorithms are a method of optimization and research. This method can be classified as one of the methods of evolutionary algorithms that depend on imitating the work of nature from a Darwinian perspective ..Genetic algorithm: It is a search technique used to find exact or approximate solutions that optimize. Genetic algorithms are classified as global search heuristics, and it is also a specific class of evolutionary algorithms also known as evolutionary computation that uses technology inspired by evolutionary biology. (Evolutionary biology) such as heredity, mutation, selection and crossover. Genetic algorithms are considered one of the important techniques in the search for the optimal option from a set of solutions available for a particular design, and adopt Darwin's principle of selection, where this genetic treatment passes the optimal advantages through successive reproductive processes, and strengthens these traits, and these traits have the greatest ability to enter the reproductive process , producing optimal offspring and by repeating the genetic cycle, the quality of the offspring gradually improves
Methodology
Genetic algorithms are implemented as a computer simulation, where chromosomes are used as individuals in the processes that they perform to find separate solutions, in general solutions are represented by a binary system of 0 and 1, and other symbols can also be used..The process of evolution usually begins with random selection of chromosomes (population) and this happens in other generations. In each generation, the fitness function is calculated for all chromosomes individually, and the best chromosomes are selected based on the best optimal function and then cross-breeding ( merge) and also make a mutation, this algorithm stops when we reach the largest number of generations produced or reach the best achievement through the optimization function, if the stop is due to the largest number of generations, the optimal solution is not achieved. Genetic algorithms are found in bioinformatics , computer science, engineering, economics, chemistry, manufacturing, mathematics, physics, and other fields.
Steps of the genetic algorithm
1- Initialization: Initially many individual solutions are randomly generated on the initial form of chromosomes. The size of the chromosomes depends on the nature of the problem, but there are usually several hundred or thousands of possible solutions. Traditionally, chromosomes are generated randomly, covering the full range of possible search spaces. Sometimes, this solution may be "classified" in the event of an optimal solution.
2- Selection: During all successive generations, a proportion of the current chromosomes are selected to produce a new generation. These chromosomes are chosen based on the optimal function, where the percentage of selection is in preference to the optimal function, and there is another way by choosing a random set of chromosomes, but this process may take a very long time.
3- Reproduction: It is a process to generate a second generation of chromosomes that have been selected through the selection process and then crossover and mutation to produce offspring.
Hybridization process
Through the parents selected from the selection process, every two parents are mated to produce two new children, and this process continues until a new set of chromosomes is found in addition to the set of parents. There are several techniques that are used in the crossbreeding process:
Hybridization point: This process eventually produces the next generation of chromosomal populations that differ from the first generation; all data are arranged depending on the point where the metamorphosis of the data occurs provided that no duplication occurs.
Two point’s hybridization: This process eventually produces the next generation of chromosomal populations that differ from the first generation; all data are arranged depending on these two points where a process of metamorphosis of the data occurs provided that no repetition occurs.
Cutting and connecting: This process cuts data from a region different from the region of the second chromosome, which leads to a difference in the length of the chromosome.
Mutation: is a sudden change in offspring resulting from the cross-breeding process so that it is a change in the shape of the chromosome by changing one of the components of the chromosome (bit change). This process is not the result of the parents.
The cloning process eventually leads to the production of new chromosomes, and the optimization function is applied to them to produce new offspring.
4- Termination: The process of creating a new generation continues until one of the causes of termination occurs, namely:
1- Getting to the best solution.
2- Reaching the required number of generations.
3- Access to a specific value (budget) such as (time/money) account.
4- Connecting to the (local minimum) and not being able to get out of it.
5- Guesswork.
6- Using a combination of the above reasons.
5- The pseudo -code of the algorithm.
1- Choosing a chromosomal data set.
2- Calculate the optimal function for each chromosome.
3- Re
4- Choosing the best parents for the process of producing offspring.
5- Generation of new generation using hybridization and mutation.
6- Evaluate the new son based on the optimization function.
7- Making changes to the original chromosomes depending on the values ??of the offspring.