Meta-heuristic methods are capable of finding solutions in less time, and one such method is the genetic algorithm - an adaptive and re-iterative algorithm that resembles the natural process of evolution, to solve a wide category of optimization problems. The genetic Algorithm belongs to the class of stochastic optimization algorithms which generally finds good enough (near-optimal) solutions in a short period and hence it is the most commonly used algorithm in various real-life applications. Genetic algorithms address all types of engineering problems in discrete optimization.
Genetic Algorithms are most effective to find solutions when the population is large, when dealing with problems of multi-constraints, solving a problem when the time or resources are limited, or finding an approximate answer. The main advantage genetic algorithms have over other meta-heuristic methods is that they scale linearly with the growing size of the problem. The parameters of the Genetic Algorithm can be tuned by using clustering methods, based on the characteristics of the data available. The mechanism for fine-tuning our developed metaheuristics is to use the k-means clustering algorithm, an unsupervised Machine learning technique. Different clusters can be identified which have a remarkable impact on improving the performance of the genetic algorithm. The research study identifies x and y coordinates as input for clustering the data by using the competitive neural network, also considering the distance between the two coordinates. The model then predicts the clusters of the unlabelled coordinate pairs. The study by Phiboonbanakit is based on applying a clustering geolocation technique to the obtained regions of delivery, make the model learn and adapt to the changing conditions in routing, and further transfer the knowledge for constructing a new route, optimizing the traveling distance and cost in a better way. Another approach for clustering the data from the nearest neighbor which has a minimum distance between two points in the same group is by using a density-based method.
The Genetic Algorithm performs random search and optimization based on the principles of natural evolution, i.e. genetic processes of biological organisms. Darwin originally described the natural process with three basic principles: reproduction, natural selection and the diversity of individuals. Each individual in the population, represented with the properties of chromosome and genotype, represents a particular solution to our problem. Each individual is evaluated with a fitness function, based on the genotype. This fitness function calculates the scores of our individual to solve the given search problem, which can be a problem of minimization or maximization. The strength of the individual is derived from the fitness function, which plays a prime role in the selection process. Similar to our nature, the population in our GA evolves over time. Surrogate information drastically reduces the user effort and hence many researchers have tried to improve the algorithms through the use of surrogate information, e.g. Particle swarm optimization algorithm and genetic algorithm.
One example would be - Vehicle routing problems, which are generally modeled with the assumption that entire information is known well in advance while planning the routes, and hence it’s not supposed to change in real-time. However, most of the routing applications have to consider dynamic information that gets updated regularly, in contrast to static information, which does not change with time. Therefore, most problems need re-planning, i.e. the routes need to be changed and updated consistently so that dynamic information can be integrated into the planning phase. Phiboonbanakit (2018) describes the routing optimization process using a genetic algorithm in the following way: Encoding the solution of the problem to chromosomes, evaluating the quality and fitness of each chromosome, and finally selecting the population for mutation. This process is repeated until the population producing the least cost is selected. The distance between the two points is the Euclidean distance used for calculations.
Genetic algorithms have tons of applications and some of them are:
This theorem states that if a monkey hits keyboard keys at random for an indefinite amount of time (infinite time), then he will most probably type a given text, such as the unfinished works of Leonardo Da Vinci. In fact, the monkey would surely type every possible finite text for an infinite number of times. However, the probability of the occurrence of this event is so small that it would require far more time than the estimated age of the whole universe, but the chances of this event’s occurrence are not zero.
Fitness function is the heart of all genetic algorithms. This function takes any individual and determines the best way it fulfills the criteria that the algorithm is optimizing for. If we are writing a genetic algorithm that simulates a jumping frog, then the fitness function can be the height of the jump, given the weight of the frog, leg size of the frog, and energy constraints of the frog. This fitness function is applied to each individual of the population separately for determining whether they should be allowed to reproduce or not. The fitness function may return a fitness score or a boolean score when any individual passes a defined threshold for reproduction.
This function takes into consideration - the overall population and the results of the fitness function for determining the individual that should reproduce. If the fitness function has a defined threshold for reproduction and if it returns a boolean, then this selection function simply filters out the population by that returned value. However, if our fitness function returns raw scores, then the selection function will calculate a threshold from those returned scores. For example, it may calculate the average score of the individual and decide to keep only the bottom half of the population. It then passes the selected population to the reproduction function and simultaneously deletes the rejected individuals (like Thanos snapping his finger and wiping out half of the population).
This function determines the expansion of the population based on the existing individuals. However, modifying the behavior of individuals and parameters of the reproduction function is complex and impacts the parts of the genetic algorithm creation (as this function determines how the population changes over a period of time. One of the simplest reproduction methods is the mutation method, where new members are selected based on single individuals. If we want to double the population by mutation, then a new individual is created with similar characteristics but modified by a random factor. Crossover is one of the complex methods of reproduction, where each new individual is created based on a combination of the existing individuals. These approaches simulate asexual and sexual reproduction and include random factors for advancing the overall population. The reproduction function, however, returns the new population - which can be the same/different size than the original population size.
Once the desired iterations of functions have occurred, the termination function then checks the ending population & returns the best individuals depending on the fitness score. The role of this function depends entirely on the application of the function.
Develop your Bot-Building skills with 2 months of FREE Bot-Building on the Engati Platform. No credit card required; start now!