Introduction to Optimization with Genetic Algorithm (2023)

Selecting the optimal parameters for machine learning tasks is challenging. Some results may be bad not because the data is noisy or because the learning algorithm used is weak, but because of poor selection of parameter values. This article provides a brief introduction to Evolutionary Algorithms (EAs) and describes the Genetic Algorithm (GA), which is one of the simplest Random EAs.

Suppose a data scientist has an image dataset divided into several classes and an image classifier needs to be created. After the data scientist has investigated the data set, K-Nearest Neighbor (KNN) seems to be a good fit. To use the KNN algorithm, there is one important parameter to use, which is K. Suppose an initial value of 3 is selected. The scientist starts the learning process of the KNN algorithm with K=3 selected. The generated trained model achieved a classification accuracy of 85%. Is this percentage acceptable? If not, can we achieve better classification accuracy than we currently have? We cannot say that 85% is the best precision that can be achieved by performing different experiments. But to do another experiment, we definitely need to change something in the experiment, like changing the K value used in the KNN algorithm. We cannot definitively say that 3 is the best value to use in this experiment unless we try applying different values ​​for K and observe how the classification accuracy varies. The question is "how to find the best value for K that maximizes the classification performance?" This is what is called optimization.

In optimization, we start with some sort of initial value for the variables used in the experiment. Since these values ​​may not be the best to use, we need to change them until we get the best ones. In some cases, these values ​​are generated by complex functions that we cannot easily solve manually. But it is very important to do optimization because a classifier can produce a bad classification precision not because, for example, the data is noisy or the learning algorithm used is weak, but because of the bad selection of the initial learning values. parameters As a result, there are different optimization techniques suggested by Operations Research (OP) researchers to make this optimization work. According to [1], optimization techniques are classified into four main categories:

1. constrained optimization
2. Multimodal optimization
3. Multi-objective optimization
4. Combinatorial Optimization

By looking at various natural species, we can see how they evolve and adapt to their environments. We can take advantage of such existing natural systems and their natural evolution to create our own artificial systems doing the same job. This is called bionics. For example, the airplane is based on how birds fly, the radar is based on bats, the submarine is invented on the basis of fish, etc. As a result, the principles of some optimization algorithms come from nature. For example, the Genetic Algorithm (GA) takes its central idea from Charles Darwin's theory of natural evolution, "survival of the fittest."

Before going into the details of how GA works, we can have a general idea about Evolutionary Algorithms (EAs).

We can say that the optimization is done by evolutionary algorithms (EA). The difference between traditional algorithms and EAs is that EAs are not static but dynamic as they can evolve over time.

Evolutionary algorithms have three main characteristics:

1. population based: Evolutionary algorithms are to optimize a process in which the current solutions are bad to generate new better solutions. The set of current solutions from which new solutions will be generated is called the population.
2. fitness oriented: If there are several solutions, how can you say that one solution is better than another? There is a fitness value associated with each individual solution calculated from a fitness function. Such a fitness value reflects how good the solution is.
3. driven by variation: If there is no acceptable solution in the current population according to the calculated fitness function of each individual, we must do something to generate new, better solutions. As a result, the individual solutions will undergo a series of variations to generate new solutions.

We will move to GA and apply these terms.

The genetic algorithm is a classical evolutionary algorithm with a random basis. By random here we mean that, to find a solution using GA, random changes are applied to current solutions to generate new ones. Please note that GA may be called Simple GA (SGA) due to its simplicity compared to other EAs.

GA is based on Darwin's theory of evolution. It is a slow and gradual process that goes from making changes to making light and slow changes. Also, GA slowly makes small changes to its solutions until it gets the best solution.

Here is the description of how GA works:

GA works with a population consisting of some solutions where the population size (popsize) is the number of solutions. Each solution is called individual. Each individual solution has a chromosome. The chromosome is represented as a set of parameters (characteristics) that define the individual. Each chromosome has a set of genes. Each gene is represented in some way, as a sequence of 0's and 1's, as shown in figure 1.

See Also

The Importance of Probability in Data Science - KDnuggets

Furthermore, each individual has a fitness value. To select the best individuals, a fitness function is used. The result of the fitness function is the fitness value that represents the quality of the solution. The higher the fitness value, the higher the quality of the solution. Selection of the best individuals based on their quality is applied to generate what is called a mating pool, where the highest quality individual is most likely to be selected in the mating pool.

The individuals in the mating group are called parents. Every two parents selected from the mating group will produce two offspring (sons). By mating only high quality individuals, one hopes to get better quality offspring than their parents. This will prevent the bad guys from spawning more bad guys. By continuing to select and breed high-quality individuals, there will be a better chance of keeping only the good properties of the individuals and leaving out the bad ones. Ultimately, this will result in the desired optimal or acceptable solution.

But the offspring currently generated using the selected parents only have the traits of their parents and nothing else unchanged. No new ones are added to it, and therefore the same disadvantages in their parents will exist in the new offspring. To overcome this problem, some changes will be applied to each offspring to create new individuals. The set of all newly generated individuals will be the new population that replaces the old population previously used. Each population created is called a generation. The process of replacing the old population with the new is called substitution. Figure 2 summarizes the GA steps.

There are two questions that need to be answered to get a complete idea about GA:

1. How are the two offspring generated from the two parents?
2. How does each child change slightly to be an individual?

We will answer these questions later.

There are different representations available for the chromosome and the selection of the appropriate representation is problem specific. A good representation is what makes the search space smaller and therefore easier to find.

The available representations for the chromosome, including:

· Tracks: Each chromosome is represented as a string of 0's and 1's.

· Permutation: Useful for ordering problems such as the traveling salesman problem.

· Valor: The actual value is encoded as is.

For example, if we want to encode the number 7 in binary, it might look like Figure 3.

Each part of the chromosome above is called a gene. Each gene has two properties. The first is its value (allele) and the second is the location (locus) within the chromosome, which is the number above its value.

Each chromosome has two representations.

1. genotype: The set of genes that represent the chromosome.
2. phenotype: The actual physical representation of the chromosome.

In the example above, the binary of 0111 is the genotype and 7 is the representation of the phenotype.

After representing each chromosome in the correct way to serve as a search in space, the next step is to calculate the fitness value of each individual. Suppose the fitness function used in our example is:

f(x)=2x+2

where x is the chromosome value

Then the fitness value of the previous chromosome is:

f(7)=2(7)+2=16

The process of calculating the fitness value of a chromosome is called evaluation.

Once you understand how to represent each individual, the next step is to initialize the population by selecting the appropriate number of individuals within it.

Then select a number of individuals from the population in the mating group. Based on the previously calculated fitness value, the best individuals are selected based on a threshold. After this step, we will finish selecting a subset of the population from the mating group.

Based on the individuals selected from the mating group, the parents are selected for mating. The selection of each parent can be done by selecting the parents sequentially (1–2, 3–4, etc.). Another way is the random selection of parents.

For every two parents selected, there are several variation operators to apply, such as:

1. Crossover (recombination)
2. Mutation

Figure 4 gives an example for these operators.

The cross in GA generates a new generation equal to the natural mutation. By mutating the parents of the previous generation, the offspring of the new generation carry genes from both parents. The number of genes each parent carries is random. Remember that GA is a random EA. Sometimes offspring take half their genes from one parent and half from the other parent, and sometimes that percentage changes. For every two parents, crossing over occurs by selecting a random point on the chromosome and swapping genes before and after that point in their parents. The resulting chromosomes are offspring. Therefore, the operator is called a single point crossover.

Keep in mind that mating is important and without it, the offspring will be identical to the parent.

The next variation operator is mutation. For each offspring, select a few genes and change their value. The mutation varies depending on the chromosome representation, but it is up to you to decide how to apply the mutation. If the encoding is binary (that is, the value space of each gene has only two values ​​0 and 1), invert the bit value of one or more genes.

But if the gene value comes from a space of more than two values, such as 1, 2, 3, 4, and 5, the binary mutation is not applicable and we must find another way. One way is to select a random value from such a set of values, as shown in Figure 5.

Note that without a mutation, the offspring will have all the properties of its parents. To add new features to this offspring, a mutation was produced. But since the mutation occurs randomly, it is not recommended to increase the number of genes to be applied to the mutation.

The individual after the mutation is called a mutant.

[1] Eiben, Agoston E., and James E. Smith. Introduction to evolutionary computation. vol. 53. Heidelberg: Springer, 2003.

The original article is available on LinkedIn at this link:https://www.linkedin.com/pulse/introduction-optimization-genetic-algorithm-ahmed-gad

It is also shared on KDnuggets at this link:https://www.kdnuggets.com/2018/03/introduction-optimization-with-genetic-algorithm.html

To contact the author:

Linkedin:https://linkedin.com/in/ahmedfgad

Email: ahmed.f.gad@gmail.com