In our life, we can develop some algorithms to solve problems we face every day. Some of these problems need a simple algorithm, and some need efficient ones. For instance, if we want to find the best route from one point to another we can use the shortest path algorithm.
Another example, if we want to carry some items in our car and keep the highest valued items first, we may use the knapsack algorithm in which we define the value and weight for each item to keep the highest valued ones within the car capacity.
All of these algorithms are good, but what if our problem holds an enormous number of possibilities, are they still good choices?
In this case we may face a runtime issue in which we need to run our program for a long time to satisfy all the possibilities which is not practical at all. Are there any other solutions?
Before defining what Genetic Algorithms are, let’s know more about other solutions possible. One solution is the dumb solution which is the blind generate and test solution. In this solution we randomly generate a possible solution, then we test this solution to see how good it’s. This process is done until reaching a solution that’s good enough.
We can use this solution in some problems. For example, a problem that has a few possible solutions only and if we have enough time to run.
What’s Genetic Algorithms GA?
The less dumb solution is by using the Genetic Algorithms. They are algorithms in which we generate a number of possible solutions (population), then rank them, remove some bad solutions, and make small changes to them.
The Genetic Algorithms are originally pioneered by John Holland in the 1970s and then got popular in the late 1980s. This solution can help a lot when having a huge number of population and needing the best solutions among them without waiting for a long time.
To understand the Genetic Algorithms more, we can think of them like a search optimization technique to find the best solutions based on Darwin’s Principle of Natural Selection.
To better understand this principle, we can imagine that there are a huge number of giraffes in some environment. As the environment can’t support all of the population to live, some of them will die as they have the less-adaptive traits like short necks.
Another part which has long necks and can get the food from the trees will live as they have more adaptive-traits than the others. As generations come after another, the giraffes with the good traits will reproduce, keeping them into the next generation.
Genetic Algorithm Steps
From the previous paragraphs we can summarize the algorithm into these steps:
1- Generating The Population
In this step we initialize the set of our possible solutions (population) and define each one with its properties.
After generating the population, we define a fitness function to measure each one of the population properties. After that, we rank the whole population according to the result calculated from the fitness function.
3- Duplicate Good Solutions
To ensure that the best ones in the population that have the most fitness value keep reproducing, we duplicate some of them within the population.
4- Apply Crossover
This is the reproducing step in which we can think of it as generating a new population (generation) from the existing one. The new generation will keep the best traits from the previous one.
The last optional step is to apply Mutation on some of the population in which we apply changes on the solution, creating unusual traits.