In this tutorial, we’ll first define some fundamental properties of genetic algorithms. Secondly, we’ll review how they are constructed. Then we’ll discuss how they work. Lastly, we’ll review some real-life applications of genetic algorithms.
Genetic algorithms are mostly applicable in optimization problems. This is because they are designed to search for solutions in a search space until an optimal solution is found. In particular, genetic algorithms are capable of iteratively making improvements on solutions generated until optimal solutions are generated.
Now let’s look at the formal definition of genetic algorithms.
Genetic algorithms are heuristic algorithms inspired by the natural process of evolution. This theory of evolution was first proposed by Charles Darwin in the mid 19th century. Evolution describes the change in the biological characteristics of species over a generation through natural selection.
Consequently, genetic algorithms are based on natural selection. Where only the fittest individuals in a population are selected to reproduce and generate offspring.
3. How Do They Work?
Genetic algorithms follow the natural process of evolution, and are described as follows:
Now let’s look at the steps in a basic genetic algorithm.
The first step is to initialize the population. In the case of problem-solving, a set of solutions to the problem at hand is the initial population. Secondly, we evaluate the optimality of the population using a fitness function. The fitness function is an objective function that evaluates the quality of the solutions.
The ultimate goal is to find the maxima or minima of this function . Take, for instance, a fitness function that assigns a score to the solutions in the population. Then, our goal here is to reach a global maximum for the function, .
If the solutions from the population are satisfactory, we usually stop the algorithm and crown these as the best individuals. Now, if the solutions are not satisfactory, we perform the process of selection and pick the fittest individuals to reproduce and generate new solutions. This is done iteratively.
Next, after selection, the fittest individuals reproduce through crossover, to generate offspring. The word offspring here refers to a new generation of solutions. During crossover, values are exchanged to generate new individuals.
Then, certain offspring produced will undergo mutation. This is a process of randomly changing the values or characteristics in the offspring to introduce diversity. Specifically, an iterative application of the mutation operation will allow the algorithm to get out of a local minimum during the search.
It is important to note that crossover and mutation are the two main methods used to generate offspring in genetic algorithms. Lastly, if the solutions or offsprings are satisfactory and there are no better offsprings to produce, the algorithm terminates and presents the best individuals as the optimal solutions.
Genetic algorithms are one of the most fundamental algorithms in computer science. Consequently, they have found many applications in the real world in different industries and for different tasks. However, we’ll only discuss a few in this article.
Robotics encompasses the design, construction, and operation of autonomous robots. In robotics, genetic algorithms are used to provide insight into the decisions a robot has to make. For instance, given an environment, suppose a robot has to get to a specific position using the least amount of resources. Genetic algorithms are used to generate optimal routes the robot could use to get to the desired position.
Economics is the science of the use of resources in the production, distribution, and overall consumption of goods and services. In economics, genetic algorithms are used to create models of supply and demand over periods of time. Additionally, genetic models are also used to derive game theory and asset pricing, models.
4.3. Automated Design
Automated design constitutes the design and production of automobiles such as cars. In particular, a car manufacturing company may have specifications on how a car should operate. As an example, minimum fuel consumption is a desirable specification in the design of vehicles. As a result, genetic algorithms are used to derive designs of automobiles that satisfy constraints such as low fuel consumption.
4.4. Scheduling Tasks
Suppose, we have a task to schedule the timetable for a university. The goal of a scheduling task is to find an optimal solution that satisfies certain constraints. Genetic algorithms are used in this aspect to derive optimal schedules considering the courses, number of students, and lecture rooms that the university has.
4.5. Vehicle Routing
In most logistics companies, one main task is vehicle routing. Here, we have to figure out how to route and transport goods to different clients using a fleet of vehicles. Consequently, genetic algorithms are used to derive cost-effective routes to transport these goods to the rightful client at the right time.
In marketing, the main idea is to promote goods and services in such a way that it will gain a lot of customers or clients. Genetic algorithms are used here to derive the best combinations of product specifications and attributes that will attract the most customers.
In medicine and bioinformatics, genetic algorithms have been used to identify benign and malignant tumours in ultrasounds and mammograms.
In this article, we first defined evolution, then genetic algorithms. We’ve discussed the basic components and how they work. Lastly, we reviewed some real-life applications of these algorithms.