problem solving using genetic algorithm

When & How to Solve Problems with Genetic Algorithms

Article summary

Basic steps, when to use genetic algorithms.

• For Example...

Genetic algorithms are a class of algorithms designed to explore a large search space and find optimal solutions by mimicking evolution and natural selection. Potential solutions are randomly found, evaluated, and bred with one another in hopes of producing better solutions.

The process of using genetic algorithms goes like this:

• Determine the problem and goal
• Break down the solution to bite-sized properties (genomes)
• Build a population by randomizing said properties
• Evaluate each unit in the population
• Selectively breed (pick genomes from each parent)
• Rinse and repeat

GAs are not good for all kinds of problems. They’re best for problems where there is a clear way to evaluate fitness. If your search space is not well constrained or your evaluation process is computationally expensive, GAs may not find solutions in a sane amount of time. In my experience, they’re most helpful when there is a decent algorithm in place, but the “knobs” just need to be tweaked.

For Example…

On a recent project, we had an algorithm that we knew would work, but we needed to find the best possible settings for the tune-able parameters.

We were using pressure data from inside a testing lung to parse out breath waves and calculate derived values such as breath rate, tidal volumes, and peak pressures. We had many recordings of pressure data and knew the expected results. The goal was simple: find the set of variables that would get us as close as possible to the expected results. Our properties were a handful of settings for our existing algorithm: low/high thresholds, smoothing factors, averaging window sizes, etc.

A simpler illustration

To walk through how it works, let’s use something a little simpler: a cannon.

Like the old Cannon Fodder game, we have a cannon that has two variables: powder and elevation. Our goal is to shoot as far as possible. (Let’s pretend we don’t know about physics and don’t know that 45 degrees is the answer.)

Our goal : max distance Our genomes : powder (0-100) P and elevation (-90-90 degrees) E

Initial population

We start by generating a sample population and evaluating its members. Normally, this sample would be much larger, but for our example, we’ll keep it small:

Given these results, we can use an elitist strategy to select the top X percent of the population to “reproduce.” Once selected, we use crossover/recombination to blend the best of the population.

Crossover and mutation

Our “Elites” include:

You may use more than two “parents,” but to keep things simple, I’ll just use two. We mix and match values from the parents (just like in biology). We also mutate a percentage of the values to introduce some randomness into our genomes.

The amount of mutation can greatly affect your results and should be tweaked based on your domain and the problem you are trying to solve. To keep our gene pool from becoming too focused, we’ll also include a couple of non-elites from the previous generation.

After crossover:

With non-elites for diversity:

After mutation:

Keeping the non-elites and mutating some of the values will keep us from reaching local optima.

Are we done yet?

Now, we just repeat this process until we’re done. But, how do we know we’re done? GAs are usually terminated by:

• Fixed number of generations
• Fixed amount of processing time
• Optimal/good enough solution is found
• Good ol’ manual killing

For our example here, the algorithm will trend toward a full powder shot at 45 degrees, and we’ll have our clear winner.

Depending on runtime, problem, and domain, any of these terminators are acceptable. For our breath parsing from pressure samples, we used a manual intervention. If possible, I recommend saving off your populations so you can resume long-running simulations.

In the end, using a GA helped us get our algorithm within tolerances fairly quickly. When algorithms changed or new genomes were discovered, we simply added the genome and started over again with a few of our saved elite values. GAs aren’t a perfect fit for a lot of problems, but they’re definitely a fun and interesting tool to have in the toolbox.

Related Posts

Embracing mainline development: beyond feature branches, chatgpt and the value of a computer science education, inspired by nature: an introduction to genetic algorithms, keep up with our latest posts..

We’ll send our latest tips, learnings, and case studies from the Atomic braintrust on a monthly basis.

Tell Us About Your Project

We’d love to talk with you about your next great software project. Fill out this form and we’ll get back to you within two business days.

• Analysis of Algorithms
• Backtracking
• Dynamic Programming
• Divide and Conquer
• Geometric Algorithms
• Mathematical Algorithms
• Pattern Searching
• Bitwise Algorithms
• Branch & Bound
• Randomized Algorithms

Genetic Algorithms

Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random searches provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality solutions for optimization problems and search problems.

Genetic algorithms simulate the process of natural selection which means those species that can adapt to changes in their environment can survive and reproduce and go to the next generation. In simple words, they simulate “survival of the fittest” among individuals of consecutive generations to solve a problem. Each generation consists of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome.

Foundation of Genetic Algorithms

Genetic algorithms are based on an analogy with the genetic structure and behavior of chromosomes of the population. Following is the foundation of GAs based on this analogy –  

• Individuals in the population compete for resources and mate
• Those individuals who are successful (fittest) then mate to create more offspring than others
• Genes from the “fittest” parent propagate throughout the generation, that is sometimes parents create offspring which is better than either parent.
• Thus each successive generation is more suited for their environment.

Search space

The population of individuals are maintained within search space. Each individual represents a solution in search space for given problem. Each individual is coded as a finite length vector (analogous to chromosome) of components. These variable components are analogous to Genes. Thus a chromosome (individual) is composed of several genes (variable components). 

Fitness Score

A Fitness Score is given to each individual which shows the ability of an individual to “compete” . The individual having optimal fitness score (or near optimal) are sought. 

The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores.The individuals having better fitness scores are given more chance to reproduce than others. The individuals with better fitness scores are selected who mate and produce better offspring by combining chromosomes of parents. The population size is static so the room has to be created for new arrivals. So, some individuals die and get replaced by new arrivals eventually creating new generation when all the mating opportunity of the old population is exhausted. It is hoped that over successive generations better solutions will arrive while least fit die. 

Each new generation has on average more “better genes” than the individual (solution) of previous generations. Thus each new generations have better “partial solutions” than previous generations. Once the offspring produced having no significant difference from offspring produced by previous populations, the population is converged. The algorithm is said to be converged to a set of solutions for the problem.

Operators of Genetic Algorithms

Once the initial generation is created, the algorithm evolves the generation using following operators –  1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass their genes to successive generations.  2) Crossover Operator: This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example – 

3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in the population to avoid premature convergence. For example –   

The whole algorithm can be summarized as –  

Example problem and solution using Genetic Algorithms

Given a target string, the goal is to produce target string starting from a random string of the same length. In the following implementation, following analogies are made – 

• Characters A-Z, a-z, 0-9, and other special symbols are considered as genes
• A string generated by these characters is considered as chromosome/solution/Individual

Fitness score is the number of characters which differ from characters in target string at a particular index. So individual having lower fitness value is given more preference.  

Note: Every-time algorithm start with random strings, so output may differ

As we can see from the output, our algorithm sometimes stuck at a local optimum solution, this can be further improved by updating fitness score calculation algorithm or by tweaking mutation and crossover operators.

Why use Genetic Algorithms  

• They are Robust
• Provide optimisation over large space state.
• Unlike traditional AI, they do not break on slight change in input or presence of noise

Application of Genetic Algorithms

Genetic algorithms have many applications, some of them are – 

• Recurrent Neural Network
• Mutation testing
• Code breaking
• Filtering and signal processing
• Learning fuzzy rule base etc

Please Login to comment...

Similar reads.

• How to Watch NFL Games Live Streams Free
• OpenAI o1 AI Model Launched: Explore o1-Preview, o1-Mini, Pricing & Comparison
• How to Merge Cells in Google Sheets: Step by Step Guide
• How to Lock Cells in Google Sheets : Step by Step Guide
• #geekstreak2024 – 21 Days POTD Challenge Powered By Deutsche Bank

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Genetic Algorithm – A Powerful Tool for Problem Solving

• Post author By admin-science
• Post date 20.12.2023

Genetic algorithms are an efficient and powerful tool for solving a wide range of optimization problems. They are based on the principles of natural selection and genetics and have been extensively used in various fields, including engineering, economics, and computer science. By imitating the process of biological evolution, genetic algorithms can find optimal solutions to complex problems.

At the core of genetic algorithms is the concept of crossover , which involves combining different solutions to create new ones. This mimics the process of reproduction in nature, where the genetic material of two individuals is combined to produce offspring with favorable traits. In genetic algorithms, crossover allows for the exploration of the solution space by generating diverse and potentially better solutions.

Another important component of genetic algorithms is mutation . This operation introduces small random changes to the solutions in order to explore new areas of the solution space. Mutation helps prevent the algorithm from getting stuck in local optima and allows it to continue searching for the global optimum.

Selection is a key mechanism in genetic algorithms. It determines which solutions are more likely to be chosen for reproduction and which are more likely to be discarded. By assigning a fitness value to each solution, the algorithm can favor those that perform better and increase their chances of being selected. This process emulates the survival of the fittest in nature and drives the algorithm towards better and better solutions over time.

In conclusion, genetic algorithms offer a powerful approach to solving optimization problems. By incorporating principles from genetics and natural selection, these algorithms can efficiently explore solution spaces and find optimal solutions. Their ability to combine solutions through crossover, introduce randomness through mutation, and favor better solutions through selection make them a valuable tool for solving complex problems in various domains.

What are Genetic Algorithms

Genetic algorithms are a type of problem-solving algorithm that is inspired by the process of evolution. These algorithms are used to find the optimal solution to a problem by mimicking the process of natural selection and evolution.

In a genetic algorithm, a population of potential solutions is created, each represented as a set of genes or parameters. These solutions are then evaluated based on a fitness function, which measures how well each solution performs in solving the problem at hand.

During the evolution process, the genetic algorithm applies two key operators: mutation and selection. Mutation introduces small random changes to the genes of the individuals, while selection favors solutions with higher fitness. These operators mimic the processes of genetic variation and survival of the fittest that occur in natural evolution.

Through repeated generations of mutation and selection, the genetic algorithm gradually converges towards the optimal solution. With each generation, the population evolves and the fitness of the individuals improves. Eventually, the algorithm produces a solution that best solves the problem based on the given fitness function.

Key Components of Genetic Algorithms

1. Population: A group of potential solutions to the problem.

2. Genes: The specific variables or parameters that make up each individual solution.

3. Fitness Function: A measurement of how well each solution performs.

4. Mutation: Random changes to the genes of the individuals.

5. Selection: Favoring solutions with higher fitness.

The Applications of Genetic Algorithms

Genetic algorithms have been successfully applied to a wide range of problems, including optimization, scheduling, machine learning, data mining, and many more. These algorithms have the ability to find near-optimal solutions in complex problem spaces and are particularly useful when traditional optimization methods are not feasible or effective.

Overall, genetic algorithms provide a powerful and versatile approach to problem-solving. By leveraging the principles of evolution and genetic variation, these algorithms have proven to be effective in finding solutions to a wide variety of real-world problems.

Basic Principles of Genetic Algorithms

Genetic algorithms are optimization algorithms inspired by the process of natural evolution. They are commonly used for solving complex problems and finding optimal solutions.

The principles of genetic algorithms include:

• Representation : Problems are represented using chromosomes, which consist of genes. Each gene represents a potential solution to the problem.
• Initialization : An initial population of chromosomes is created randomly or using some heuristics.
• Evaluation : Each chromosome in the population is evaluated using a fitness function that quantifies how well it solves the problem.
• Selection : Based on their fitness, chromosomes are selected to form the next generation. Selection can be done using various strategies, such as tournament selection or proportional selection.
• Crossover : Selected chromosomes undergo crossover to create new offspring. Crossover involves exchanging genetic material between chromosomes to create new combinations.
• Mutation : A small percentage of chromosomes undergo random mutation to introduce new genetic material into the population. Mutation helps explore new regions of the solution space.
• Evolution : The new offspring and a portion of the previous generation form the next generation. This process is repeated for a certain number of generations.
• Solving the Problem : Through generations of selection, crossover, and mutation, genetic algorithms converge towards finding optimal solutions to the problem at hand.

By combining elements of selection, crossover, and mutation, genetic algorithms mimic the process of natural evolution to explore and optimize solution spaces. They are particularly suited for solving complex problems where traditional optimization algorithms may struggle.

Problem Solving with Genetic Algorithms

In the field of optimization, solving complex problems can often be a challenging task. Genetic algorithms offer a powerful approach to problem-solving that mimics the principles of biological evolution.

A genetic algorithm is a computational approach that uses the principles of natural selection, mutation, and crossover to create and evolve a population of potential solutions to a given problem. The algorithm iteratively evolves the population by applying genetic operators, such as mutation and crossover, to generate new offspring with potentially improved fitness.

Genetic algorithms start with an initial population of potential solutions. Each solution is represented as a string of binary digits known as a chromosome. The fitness of each chromosome is evaluated using a fitness function that quantifies how well the solution solves the problem.

The evolution process begins with the selection of parents for reproduction. Higher fitness individuals have a higher chance of being selected for reproduction, simulating the principle of natural selection. The selected parents then undergo crossover, where parts of their genetic material are exchanged, potentially producing offspring with a combination of the parents’ traits.

In addition to crossover, genetic algorithms also employ mutation. Mutation randomly alters one or more bits in a chromosome, introducing new genetic material that can lead to novel solutions. Mutation helps in exploring the search space and preventing the algorithm from converging prematurely.

The new offspring, resulting from crossover and mutation, replace less fit individuals in the population. This process continues for multiple generations, allowing the population to evolve towards better solutions over time. Eventually, the genetic algorithm converges to a solution that optimizes the problem at hand.

Genetic algorithms have been successfully applied to a wide range of problem-solving domains, including optimization, scheduling, pattern recognition, and machine learning. Their ability to explore a large search space and converge to optimal or near-optimal solutions makes them a powerful tool in solving complex problems.

In conclusion, genetic algorithms provide a versatile and efficient approach to problem-solving and optimization. By simulating the principles of genetic evolution, these algorithms are capable of solving a wide variety of problems. Whether it is finding the optimal solution to a complex mathematical function or optimizing a scheduling problem, genetic algorithms can offer an effective solution.

Apply Genetic Algorithms to Problem Solving

Genetic algorithms are a powerful optimization technique inspired by the process of natural evolution. They can be used to solve complex problems by mimicking the principles of genetics and evolution. In problem solving, genetic algorithms can be applied to find the best solution or a near-optimal solution when the search space is large and the problem is difficult to solve using traditional methods.

Genetic algorithms work by creating a population of potential solutions, which are represented as individuals in a population. These individuals are then subjected to genetic operations such as crossover and mutation, which mimic the processes of recombination and mutation in nature. Through these operations, new individuals are created, evaluating their fitness based on how well they solve the problem at hand.

The process of evolution in genetic algorithms involves selection, where individuals with higher fitness scores are more likely to be selected for reproduction, passing their genes to the next generation. This mimics the concept of survival of the fittest in natural evolution.

By repeatedly applying these genetic operations and the process of selection, the population evolves over generations, gradually improving the quality of the solutions. Eventually, the genetic algorithm converges towards an optimal or near-optimal solution.

Genetic algorithms can be applied to a wide range of problem types, including optimization problems, machine learning, scheduling problems, and more. They are particularly useful in situations where the problem space is large or complex, and traditional algorithms may be impractical or inefficient.

When applying genetic algorithms to problem solving, it is important to carefully design the representation of individuals, the genetic operations, and the fitness function. These design choices can greatly impact the efficiency and effectiveness of the algorithm.

Overall, genetic algorithms are a valuable tool for problem solving and optimization. They provide a flexible and effective approach to finding solutions in complex problem domains, and can be applied to a wide range of problem types. By leveraging the principles of genetics and evolution, genetic algorithms offer a unique perspective on problem solving.

Advantages and Limitations of Genetic Algorithms for Problem Solving

Genetic algorithms are powerful optimization algorithms that mimic the process of natural evolution. These algorithms are used to solve complex problems by generating a population of potential solutions and iteratively evolving these solutions through mutation and crossover operations. Genetic algorithms have several advantages and limitations when it comes to problem solving.

Advantages:

• Exploration of Solution Space: Genetic algorithms are capable of exploring a large solution space, searching for optimal solutions that may be hidden or difficult to find using traditional methods.
• Efficiency in Optimization: By employing techniques like mutation and crossover, genetic algorithms are able to efficiently converge towards optimal solutions in a relatively short amount of time compared to other optimization algorithms.
• Adaptability to Dynamic Environments: Genetic algorithms can adapt to changing environments by continuously evolving the population over multiple iterations, allowing them to handle complex and dynamic problem domains.
• Parallelism and Scalability: Genetic algorithms can be easily parallelized, enabling them to solve large-scale problems efficiently by distributing the computation across multiple processors or machines.
• Handling Multiple Objectives: Genetic algorithms are well-suited for solving multi-objective optimization problems, where multiple conflicting objectives need to be optimized simultaneously.

Limitations:

• Difficulty in Problem Representation: Choosing an appropriate representation scheme for the problem at hand can be a challenge, as different representations may have varying effects on the performance of the algorithm.
• Lack of Guarantee for Global Optima: Genetic algorithms may converge to local optima instead of global optima, especially in complex and multimodal problem domains. Additional techniques, such as hybrid algorithms or multiple runs, may be needed to mitigate this limitation.
• Intensive Computation: Genetic algorithms require a substantial amount of computational resources, especially when solving large-scale problems with a high number of variables or constraints.
• Tuning of Parameters: Genetic algorithms often involve several parameters that need to be carefully tuned to achieve optimal performance. Selecting appropriate parameter values can be time-consuming and subjective.
• Lack of Problem Understanding: Genetic algorithms are generally considered as black-box optimization techniques, meaning that they provide solutions without providing insights into the underlying problem structure. This may limit the interpretability of the results.

Despite their limitations, genetic algorithms have proven to be versatile problem-solving algorithms that can find solutions to a wide range of complex optimization problems in various domains.

Components of Genetic Algorithms

Genetic algorithms are a type of evolutionary algorithm used for solving complex problems. They are inspired by the process of natural evolution and use methods such as mutation, crossover, and selection to find optimal solutions.

Mutation is a process in genetic algorithms where random changes are introduced into the genetic material. This introduces diversity into the population and helps explore different solution possibilities. Mutation can occur at various stages during the algorithm’s evolution.

Crossover combines genetic material from two parent solutions to create new offspring. This process mimics reproduction in nature and helps combine beneficial traits from different solutions. It promotes convergence towards better solutions as the algorithm progresses.

Selection is the process of choosing parent solutions for crossover and determining which solutions survive and reproduce. Selection methods favor solutions that are well-suited to solving the problem and have higher fitness scores. This encourages the evolution of solutions towards optimal outcomes.

Genetic algorithms follow an iterative process of evolution and selection. They start with an initial population of random solutions and gradually improve them over multiple generations. Each generation is evaluated based on a fitness function, which measures how well a solution solves the problem at hand.

Algorithm parameters such as population size, mutation rate, and selection criteria can be tuned to achieve better performance for specific problems. Finding the right balance between exploration (mutation) and exploitation (crossover) is crucial for the algorithm’s success.

Genetic algorithms are widely used for solving optimization problems in various fields, including engineering, finance, and artificial intelligence. Their ability to explore large solution spaces and find near-optimal solutions makes them valuable tools for solving complex problems.

In conclusion, genetic algorithms are a powerful approach to problem-solving that harnesses the principles of evolution. By incorporating mutation, crossover, and selection, these algorithms can efficiently explore and converge towards optimal solutions in diverse problem domains.

Representation in Genetic Algorithms

In order to solve a problem using genetic algorithms, it is important to define a suitable representation for the problem at hand. The representation determines how the solution space is explored during the evolution process.

A genetic algorithm operates on a population of individuals, each representing a potential solution to the problem. The individuals are typically encoded as strings of bits, where each bit represents a different attribute or characteristic of the solution.

Selection is a key component of genetic algorithms, where individuals with higher fitness are more likely to be selected for reproduction. The fitness of an individual is a measure of its quality or suitability as a solution to the problem. The selection process ensures that the best solutions have a higher chance of being passed on to the next generation.

In order to generate a new population of individuals, genetic algorithms use two main genetic operators: mutation and crossover. Mutation introduces random changes to the genetic material of an individual, allowing for exploration of new regions of the solution space. Crossover combines the genetic material of two individuals to create offspring that inherit traits from both parents.

The genetic algorithm iteratively applies selection, mutation, and crossover to evolve the population towards better solutions. By iteratively improving the population, genetic algorithms are able to find optimal or near-optimal solutions to a wide range of problems.

Selection in Genetic Algorithms

Selection is a crucial step in the evolution of a genetic algorithm. It plays a vital role in determining which individuals will be selected for reproducing and passing their genetic information to the next generation. The main goal of selection is to mimic the principles of natural selection and promote the survival of the fittest individuals for solving a given problem.

Evolution and Genetic Algorithms

In the context of genetic algorithms, evolution refers to the iterative process of generating new populations of individuals through genetic operations such as crossover and mutation. Each population represents a possible solution to a given problem, and with each iteration, the genetic algorithm aims to improve the quality of these solutions.

Selection Algorithm

The selection algorithm is responsible for determining which individuals will have the opportunity to reproduce. It involves selecting individuals based on their fitness value, which is a measure of how well they solve the problem at hand. Typically, the higher the fitness value, the more likely an individual is to be selected for reproduction.

One commonly used selection method is tournament selection. In this method, a fixed number of individuals are randomly selected from the population to compete in a tournament. The individual with the highest fitness value wins the tournament and is selected for reproduction.

Another popular selection method is roulette wheel selection, also known as fitness proportionate selection. In this method, each individual is assigned a segment on a roulette wheel that is proportional to their fitness value. A random spin of the wheel determines which individuals are selected for reproduction. The higher an individual’s fitness value, the larger their segment on the wheel, and the higher their chances of being selected.

Advantages of Selection in Genetic Algorithms

The selection step in genetic algorithms contributes to the optimization process by promoting the survival of individuals with higher fitness. It helps to maintain diversity within the population, as it allows a variety of individuals with different genetic information to reproduce.

This diversity is important because it ensures that the genetic algorithm explores a wide range of possible solutions to the problem. Additionally, selection helps to prevent premature convergence to sub-optimal solutions by preserving genetic diversity and allowing potentially better solutions to emerge in later generations.

• Selection is a fundamental component of genetic algorithms.
• It simulates the principles of natural selection to solve problems through evolution.
• Common selection methods include tournament selection and roulette wheel selection.
• Selection promotes the survival of individuals with higher fitness and maintains genetic diversity.
• It prevents premature convergence to sub-optimal solutions and allows for the emergence of potentially better solutions in later generations.

Crossover in Genetic Algorithms

In genetic algorithms, crossover is a key operation for creating new offspring solutions from parent solutions. It is an essential step in the evolutionary process of solving problems through optimization. Crossover involves combining genetic information from two parent solutions to create a new solution that inherits traits from both parents.

During the selection process, individuals with better fitness scores are more likely to be chosen as parents for crossover. This is because the goal of genetic algorithms is to improve the overall fitness of the population over successive generations.

The crossover operation begins by selecting a random point in the genetic code, which determines the location where the genetic material of the parents is exchanged. The genetic code can be represented as binary strings or any other appropriate encoding scheme depending on the problem being solved.

There are various types of crossover techniques used in genetic algorithms, including one-point crossover, two-point crossover, and uniform crossover. These techniques differ in how they select the crossover point(s) and exchange genetic material between the parent solutions.

In one-point crossover, a single crossover point is selected, and the genetic material after this point is swapped between the parents. This creates two new offspring solutions, each with a combination of genetic traits from both parents.

Two-point crossover is similar to one-point crossover, but it involves selecting two crossover points. The genetic material between these two points is exchanged between the parents, creating two new offspring solutions with a different combination of genetic traits.

Uniform crossover is a more flexible technique that allows for the exchange of genetic material at every position in the genetic code. This means that each bit or trait has an equal chance of being swapped between the parents, resulting in a more diverse set of offspring solutions.

Crossover plays a crucial role in the evolution of solutions in genetic algorithms. By combining genetic information from different parents, it helps to explore the solution space more effectively and find better solutions to the problem at hand.

Overall, crossover is an essential component of the genetic algorithm solving process. It facilitates the exploration of different solution combinations and increases the diversity of the population, leading to an improved chance of finding optimal solutions through an iterative process of evolution.

Mutation in Genetic Algorithms

In the process of solving problems using genetic algorithms, mutation plays a significant role in introducing variability and exploring new regions in the search space. It is a crucial operator that helps in maintaining diversity and preventing premature convergence.

Mutation is a genetic operator that makes small, random alterations in the genetic material (i.e., the chromosomes) of individuals in a population. These alterations can be beneficial by introducing new traits or characteristics that were not present in the original population.

The process of mutation starts by selecting individuals from the population, usually based on a predefined mutation rate. The selected individuals undergo random changes in their genetic information, typically achieved by flipping bits, swapping values, or introducing random adjustments to the values of specific genes.

Mutation adds an element of randomness to the evolutionary process of genetic algorithms, allowing the algorithm to explore new regions of the search space that may lead to better solutions. It provides a mechanism to escape local optima, as it can introduce novel solutions that were not present in the initial population.

However, mutation alone is not sufficient for effective problem solving using genetic algorithms. It needs to be complemented by other essential operators like selection and crossover. Selection helps in identifying the fittest individuals from the population, while crossover combines the genetic information of selected individuals to create new offspring.

Together, mutation, selection, and crossover form the basis of the genetic algorithm. By iteratively applying these operators, the algorithm gradually evolves a population of individuals that are increasingly better at solving the problem at hand.

In conclusion, mutation in genetic algorithms is a critical mechanism that introduces variability and promotes exploration of new solutions. It adds randomness to the algorithm’s evolution and complements other operators in solving complex problems effectively.

Fitness Function in Genetic Algorithms

In the process of solving a problem using genetic algorithms, the fitness function plays a crucial role. It is a fundamental component of the algorithm that guides the evolution and optimization process.

The fitness function determines how well each individual in a population solves the problem at hand. It assigns a numerical value, known as the fitness score, to each individual based on their ability to satisfy the given problem’s criteria or objectives. The goal is to maximize the fitness score, as individuals with higher scores are considered more fit in terms of solving the problem.

The fitness function evaluates the individuals based on specific criteria relevant to the problem being solved. These criteria can be defined by the problem statement, requirements, or the objectives that need to be optimized. For example, in a genetic algorithm used to optimize a scheduling problem, the fitness function may consider criteria such as minimizing task overlap, minimizing resource utilization, and maximizing overall efficiency.

To determine the fitness score, the algorithm evaluates each individual in the population by applying the fitness function. The function takes the individual’s genetic representation, or chromosome, as input and produces a numerical output that represents its fitness. This evaluation is performed for each individual, and the resulting fitness scores are used in the subsequent selection and evolution steps of the algorithm.

The fitness function is typically designed in a way that reflects the problem’s objectives and constraints. It should be able to differentiate between good and bad individuals, rewarding the ones that are more likely to lead to a better solution. However, finding the appropriate fitness function can be challenging, as it requires a deep understanding of the problem domain and the desired optimization goals.

Selection and Evolution based on Fitness Scores

The fitness scores assigned to individuals play a crucial role in the selection and evolution steps of genetic algorithms. Individuals with higher fitness scores are more likely to be selected for reproduction and crossover, while those with lower scores have lower chances of passing their genetic material to the next generation.

The selection process is usually based on the concept of “survival of the fittest,” where individuals with higher fitness scores have a higher probability of being selected for reproduction. This process mimics the natural evolution process, as individuals that are better adapted to their environment have a higher chance of passing their genes to the next generation.

In addition to selection, the fitness scores also influence the evolution process through mutation and crossover. Mutation introduces random changes in the genetic material of individuals, while crossover combines the genetic material of two selected individuals to create new ones. The fitness scores guide these processes, ensuring that the genetic material of individuals with higher fitness is more likely to be preserved and passed on to the next generation.

In summary, the fitness function is a crucial component of genetic algorithms as it evaluates and scores individuals based on their ability to solve the problem. It determines the individuals’ fitness and guides the selection and evolution processes, ensuring the algorithm converges towards better solutions over time.

Steps to Solve Problems Using Genetic Algorithms

Genetic algorithms are a powerful solution approach that can be used to solve a wide range of optimization problems. These algorithms are inspired by the principles of evolution and genetics, and they mimic the natural selection process to find the most optimal solution to a problem.

Here are the steps involved in solving problems using genetic algorithms:

• Define the problem: Clearly define the problem you want to solve. This could be an optimization problem, where you are trying to find the best solution from a large set of possible solutions.
• Encode the solutions: Represent each potential solution as a set of genes or chromosomes. These genes represent different variables or parameters that need to be optimized.
• Initialize the population: Create an initial population of potential solutions. This population should be large enough to cover a wide range of possible solutions.
• Evaluate the fitness: Evaluate the fitness of each individual in the population. The fitness function determines how well each solution performs in solving the problem.
• Select parents: Select individuals from the population to serve as parents for the next generation. The selection process is usually based on the fitness of each individual, with fitter individuals having a higher probability of being selected.
• Apply genetic operators: Apply genetic operators such as mutation and crossover to the selected parents to create new offspring. Mutation introduces random changes in the genes, while crossover combines the genes of two parents to create new solutions.
• Replace the population: Replace the old population with the new offspring. This ensures that the next generation of solutions is based on the most fit individuals.
• Repeat the process: Repeat steps 4 to 7 for a certain number of generations or until a stopping criterion is met. This allows the algorithm to iteratively refine the solutions and converge towards the optimal solution.
• Output the best solution: Once the algorithm has finished running, output the best solution found. This solution represents the most optimal solution to the problem.

By following these steps, genetic algorithms can efficiently solve complex problems by exploiting the principles of evolution and genetic variation. They can be applied to a wide range of problems in various fields, such as engineering, finance, and biology.

Define the Problem

To solve a problem using genetic algorithms, it is important to clearly define the problem statement. This step is crucial as it sets the stage for the optimization process.

Problem Statement

The problem statement should clearly outline the specific task or objective that needs to be accomplished. It should also define any constraints or limitations that need to be considered during the optimization process. This helps in identifying the appropriate fitness function and evaluating the effectiveness of the genetic algorithm.

For example, if the problem is to find the shortest path between multiple locations, the problem statement should specify the starting and ending locations, as well as any intermediate points that need to be visited. It should also mention any roadblocks or restrictions that may affect the path selection.

Adapting the Problem to Genetic Algorithm

Once the problem is defined, it is important to consider how to adapt it to be solved using a genetic algorithm. This involves identifying the variables or parameters that need to be optimized, as well as the potential solutions or genomes.

The crossover and mutation operators are then defined based on the problem characteristics. The selection operator is also determined based on the desired traits or characteristics that need to be preserved or improved during the evolution process.

Overall, a clear problem definition helps in designing an effective genetic algorithm that can efficiently search and optimize the solution space.

Define the Genetic Representation

In genetic algorithms, the first step in solving a problem is to define a suitable genetic representation for the problem. This representation determines how the problem will be encoded as a set of genes, which can then be manipulated by the genetic algorithm.

The genetic representation is crucial in determining the search space of the genetic algorithm. The search space is the set of all possible solutions to the problem, and a good genetic representation should ensure that all feasible solutions can be represented.

In many cases, the genetic representation consists of a binary string, where each gene represents a bit in the string. For example, if we are solving a binary optimization problem, each gene in the genetic representation could represent a decision variable, with a value of 0 or 1.

Encoding Other Types of Problems

However, genetic algorithms can also be used to solve problems with more complex representations. For example, if we are solving a problem that involves a sequence of elements, such as the traveling salesman problem, each gene could represent a city in the sequence.

Another approach is to use a real-valued representation, where each gene represents a real number. This can be useful for solving optimization problems where the solution space is continuous.

Crossover and Mutation

The genetic representation also determines how crossover and mutation operations are applied. Crossover involves taking two parent solutions and combining their genes to create a new offspring solution. The specific crossover operator used depends on the genetic representation.

Mutation involves randomly changing the value of one or more genes in a solution. Again, the mutation operator used will depend on the genetic representation.

By defining a suitable genetic representation for a problem, we can ensure that the genetic algorithm has the potential to find good solutions. However, the success of the algorithm also depends on the selection and fitness evaluation mechanisms, which will be discussed in later sections.

Define the Fitness Function

One of the key components of a genetic algorithm is the fitness function. The fitness function is a mathematical function that measures how well a particular solution performs in solving the problem at hand.

When using genetic algorithms for problem solving and optimization, the fitness function is crucial in determining which solutions are better suited for survival and reproduction, and which solutions should be discarded.

Why is the Fitness Function Important?

The fitness function allows the genetic algorithm to evaluate potential solutions and determine their fitness or suitability for solving the given problem. It provides a quantitative measure of how well a solution addresses the problem objectives.

A well-defined fitness function is essential as it guides the genetic algorithm in its exploration of the solution space. By assigning a fitness score to each solution, the algorithm can prioritize solutions that are more likely to lead to an optimal solution.

Designing the Fitness Function

Designing an effective fitness function involves careful consideration of the problem objectives and constraints. The fitness function should capture the essence of what is desired in a solution, whether it is maximizing a desired outcome or minimizing a cost or error.

The fitness function should be able to quantify how well a solution performs relative to other solutions. This can be achieved by assigning a numerical fitness score based on specific criteria or evaluating the solution against a target value.

It is important to strike a balance when designing the fitness function. It should be sensitive enough to discriminate between good and bad solutions but should also avoid being too strict or too lenient.

In some cases, the fitness function may need to be adapted or updated as the genetic algorithm progresses. This can involve refining the criteria for evaluating solutions or adjusting the fitness scoring scheme based on the algorithm’s performance.

In summary, the fitness function plays a crucial role in genetic algorithms as it guides the algorithm in selecting and evolving solutions. A well-designed fitness function is essential for effectively solving optimization problems using genetic algorithms.

Initialize the Population

When using genetic algorithms for problem solving and optimization, the first step is to initialize the population. The population consists of a set of individuals, each representing a potential solution to the problem at hand.

The individuals in the population are typically represented as strings of binary digits, also known as chromosomes. These chromosomes are encoded in such a way that each gene represents a different aspect or parameter of the problem being solved.

To create the initial population, we randomly generate a set of chromosomes. This randomization helps to ensure diversity and allows for exploration of different potential solutions. The size of the population is an important parameter, as it affects both the exploration and exploitation capabilities of the genetic algorithm.

After initialization, the genetic algorithm enters a loop where it iteratively improves the population. One of the key steps in this process is selection.

Selection involves choosing a subset of individuals from the current population to serve as parents for the next generation. This selection is typically done based on the fitness of each individual, which is a measure of how well they perform in solving the problem.

There are various selection strategies that can be used, such as tournament selection or roulette wheel selection. These strategies aim to strike a balance between preserving good individuals and allowing for exploration of new potential solutions.

Mutation and Crossover

Once the parents are selected, the genetic algorithm applies mutation and crossover operators to create the offspring for the next generation.

Mutation involves making random changes to individual genes in the chromosomes. This helps to introduce diversity into the population and allows for exploration of different potential solutions. The mutation rate is an important parameter, as it affects the balance between exploration and exploitation.

Crossover, on the other hand, involves combining the genes of two parents to create offspring with a combination of their characteristics. This helps to exploit good solutions found by the parents and potentially create even better solutions.

By iteratively repeating the steps of selection, mutation, and crossover, the genetic algorithm evolves the population towards better and better solutions to the problem. Over time, the population converges towards a set of optimal solutions, representing the best possible solutions for the given problem.

Apply Selection, Crossover, and Mutation

Genetic algorithms are a powerful technique for solving optimization problems that mimic the process of evolution. In order to find the optimal solution to a problem, genetic algorithms apply selection, crossover, and mutation operations.

Selection is the process of choosing individuals from a population for reproduction, based on their fitness or ability to solve the problem. The more fit an individual is, the higher their chances of being selected for reproduction. This mimics the natural selection process, where individuals with advantageous traits are more likely to survive and reproduce.

Crossover is the process of combining the genetic material of two selected individuals to create new individuals. This mimics the biological process of sexual reproduction, where genetic material from two parents is combined to create offspring with a combination of traits from both parents. In the context of genetic algorithms, crossover helps explore different parts of the solution space and combines the beneficial traits of different individuals.

Mutation is a random alteration of the genetic material, usually with a low probability. It introduces genetic diversity into the population and helps explore new areas of the solution space. While selection and crossover focus on exploring the existing population, mutation introduces random changes that could potentially lead to better solutions. Mutation helps to avoid getting stuck in local optima and promotes the exploration of the entire solution space.

By applying selection, crossover, and mutation iteratively, genetic algorithms can gradually evolve a population of individuals that are increasingly better at solving the problem at hand. This process of evolution mimics the natural process of adaptation and can be a powerful approach for optimization problems.

Evaluate the Fitness of the Offspring

Once the offspring is created through the crossover and mutation operators, the next step in the genetic algorithm is to evaluate the fitness of the offspring. Fitness evaluation is a crucial component of the algorithm as it determines the quality of the solutions and guides the evolution towards an optimal solution.

The fitness of an individual in the population is a measure of how well it solves the problem at hand. In an optimization problem, the fitness can be defined as the objective function value, which represents the quality of the solution. The objective function evaluates a candidate solution and assigns a fitness score based on how well it satisfies the problem constraints and objectives.

The fitness evaluation process involves running the problem-specific evaluation function on each individual in the population, including the offspring. This function calculates the fitness score and assigns it to the individual. The evaluation function may involve complex calculations or simulations, depending on the problem being solved.

Selection operators such as tournament selection or roulette wheel selection can then be used to select the fittest individuals for reproduction in the next generation. The selection process is biased towards individuals with higher fitness scores, increasing the chance that their genetic material will be passed on to future generations.

By evaluating the fitness of the offspring and selecting the best individuals for reproduction, the genetic algorithm iteratively improves the population over multiple generations. Through the combination of crossover, mutation, and selection, the algorithm converges towards better solutions to the problem at hand.

It is important to note that the fitness evaluation process is problem-specific and needs to be designed and implemented based on the characteristics of the problem being solved. The evaluation function should accurately represent the problem constraints and objectives to guide the evolution towards optimal solutions.

In conclusion, the evaluation of the fitness of the offspring is a critical step in the genetic algorithm for problem solving and optimization. It ensures that the algorithm’s evolution is guided towards solutions that satisfy the problem constraints and objectives. By combining crossover, mutation, and selection with fitness evaluation, the genetic algorithm can efficiently explore the solution space and converge towards optimal solutions.

Repeat until Termination Criteria is Met

Once a genetic algorithm is set up for solving a problem, it needs to iterate through multiple generations in order to evolve and optimize the solution. This process involves repeating the steps of selection, crossover, and mutation until a termination criteria is met.

During selection, the individuals in the current generation are evaluated based on their fitness, which represents how well they solve the problem. The fittest individuals are then selected to be parents for the next generation.

Crossover is the process of combining the genetic material of two parent individuals to create offspring. This is done by selecting a crossover point and swapping the genetic information before and after that point between the parents.

Mutation introduces small random changes into the genetic material of the offspring. This helps introduce new variations into the population and prevents stagnation in the evolution process.

Following the crossover and mutation steps, the newly created offspring are added to the population. The individuals in the population are then evaluated again, and the cycle of selection, crossover, and mutation is repeated.

The termination criteria determine when the genetic algorithm should stop iterating through generations. This can be based on factors such as the maximum number of iterations, reaching a certain fitness threshold, or a combination of different criteria.

By repeating the steps of selection, crossover, and mutation until the termination criteria is met, the genetic algorithm gradually improves the population and converges towards an optimal solution for the problem.

Examples of Problem Solving Using Genetic Algorithms

Genetic algorithms have been successfully applied to solve a wide range of problems in various fields. These algorithms are a form of evolutionary computation that mimics the process of natural selection in order to find optimized solutions.

One of the most common problems that genetic algorithms are used to solve is the optimization problem. For example, in the field of engineering, these algorithms can be used to find the optimal design of a structure by evolving a population of potential solutions over multiple generations.

Another example is in the field of scheduling, where genetic algorithms can be used to optimize the allocation of resources or the sequencing of tasks to minimize costs or maximize efficiency. This can be applied to various domains such as project management, production planning, or transportation logistics.

In the field of machine learning, genetic algorithms can be used for feature selection or parameter optimization in models. By evolving a population of potential solutions, these algorithms can find the best combination of variables or parameters to achieve the desired performance.

Furthermore, genetic algorithms can also be applied to solve complex mathematical problems such as the traveling salesman problem or the knapsack problem. These problems involve finding the optimal solution among a vast number of possibilities, and genetic algorithms provide a powerful approach for exploring the solution space.

The process of solving a problem using genetic algorithms involves several key steps. These include population initialization, selection of fitter individuals based on an evaluation function, genetic operators such as mutation and crossover to create new solutions, and termination criteria based on the predefined stopping condition.

In conclusion, genetic algorithms are a versatile and powerful tool for problem solving and optimization. Their ability to mimic the process of evolution makes them well-suited for finding optimized solutions in various domains. By applying these algorithms, researchers and practitioners can tackle complex problems and find efficient solutions.

Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is a classic problem in the field of optimization and computer science. It involves finding the shortest possible route that a salesman can take to visit a number of cities and return to his starting point.

Genetic algorithms have been successfully applied to solve the Travelling Salesman Problem. These algorithms are inspired by the process of natural evolution and mimic the survival of the fittest. They involve the creation of a population of potential solutions, and then applying genetic operators such as selection, crossover, and mutation to generate new offspring.

Genetic Algorithms and the TSP

In the context of the TSP, a genetic algorithm starts by randomly generating an initial population of solutions, each representing a possible route for the salesman. The fitness of each solution is then evaluated based on the total distance of the route. The goal is to minimize this distance, as it represents the overall cost or time the salesman would spend.

Selection is the process of choosing which solutions will be selected for reproduction. Solutions with higher fitness are more likely to be selected, but there is also a chance for less fit solutions to be chosen in order to maintain genetic diversity.

Crossover is the process of combining genetic material from two parent solutions to create offspring solutions. In the context of the TSP, crossover involves selecting a subset of cities from each parent and creating a new route that visits all these cities.

Mutation is the process of randomly altering some characteristics of a solution. In the TSP, mutation can involve swapping the order of a subset of cities in a route, or randomly selecting a city and inserting it at a different position.

Solving the TSP with Genetic Algorithms

The process of solving the TSP using genetic algorithms involves repeatedly applying selection, crossover, and mutation until a satisfactory solution is found. This process is typically repeated for a number of generations, allowing the population to evolve and improve over time.

Through the iterative process of genetic evolution, genetic algorithms are able to explore a large solution space and converge to a near-optimal or optimal solution to the TSP. Although it is not guaranteed to find the absolute optimal solution, genetic algorithms are efficient and scalable, making them a popular choice for solving complex optimization problems like the Travelling Salesman Problem.

Knapsack Problem

The knapsack problem is a classic optimization problem in computer science and mathematics. It involves finding the most valuable combination of items to fit into a knapsack with a capacity constraint.

In the knapsack problem, each item has a weight and a value. The goal is to select a subset of items that maximizes the total value while keeping the total weight within the capacity of the knapsack. This problem is often used to illustrate the principles of optimization and solving problems using genetic algorithms.

Genetic algorithms can be used to solve the knapsack problem by using an evolutionary approach. The algorithm starts with a population of potential solutions, which are represented as binary strings. Each bit in the string represents whether a particular item is included in the knapsack or not.

The algorithm evolves the population over multiple generations, using genetic operators such as selection, crossover, and mutation. Selection involves choosing the fittest individuals from the population to be parents for the next generation. Crossover combines the genetic material of the parents to create offspring with a mix of their characteristics. Mutation randomly alters some bits in the offspring to introduce new genetic material.

Through this process of evolution, the algorithm searches for the optimal combination of items that maximizes the total value while staying within the capacity constraint of the knapsack. The algorithm continues to iterate until it reaches a termination condition, such as a maximum number of generations or a satisfactory solution.

The knapsack problem is a challenging problem in the field of optimization, and genetic algorithms provide an effective approach for solving it. By using a combination of selection, crossover, and mutation, genetic algorithms can explore the space of possible solutions and converge towards an optimal solution to the knapsack problem.

Job Scheduling Problem

The job scheduling problem is an optimization problem that involves scheduling a set of tasks to be executed on a set of resources, subject to certain constraints. The goal is to find an optimal schedule that minimizes the overall completion time or maximizes resource utilization.

In the context of genetic algorithms, the job scheduling problem can be solved using an evolutionary algorithm approach. The genetic algorithm is a search and optimization algorithm inspired by the process of natural evolution. It iteratively generates a population of potential solutions, uses a selection process to choose the best individuals, applies genetic operators such as mutation and crossover to create new individuals, and evaluates their fitness based on the problem constraints and objectives.

Selection is a crucial component of the genetic algorithm. It determines which individuals are selected to reproduce and create the next generation. In the context of the job scheduling problem, selection can be based on the fitness of individuals, which is usually calculated based on the objective function. The objective function could be the total completion time or the resource utilization, depending on the problem requirements.

Mutation is an essential operator in the genetic algorithm that introduces small random changes to individuals in the population. In the context of the job scheduling problem, mutation can be applied to change the order of tasks within a schedule or to swap tasks between different schedules. This introduces diversity into the population and allows exploration of different search spaces.

In summary, the job scheduling problem can be effectively solved using genetic algorithms. The algorithm maintains a population of potential schedules, applies selection and mutation operators to create new generations, and evaluates the fitness of each individual. Through evolution, the algorithm converges towards an optimal solution that minimizes the overall completion time or maximizes resource utilization.

Genetic Algorithms Optimization Techniques

Genetic algorithms are powerful optimization techniques that leverage principles of genetics and evolution to solve complex problems. They mimic the process of natural selection, mutation, and crossover to drive the search for an optimal solution.

Optimization

Optimization is the process of finding the best solution for a given problem within a set of possible solutions. In the context of genetic algorithms, optimization involves evolving a population of candidate solutions over generations to improve their fitness and converge on the optimal solution.

Selection is a key operation in genetic algorithms that determines which individuals from the population will contribute to the next generation. In this process, individuals with higher fitness are more likely to be selected, as they have a higher chance of passing their genetic information to the next generation.

There are various selection techniques used in genetic algorithms, such as tournament selection, roulette wheel selection, and rank-based selection. Each technique has its own advantages and trade-offs, and the choice depends on the problem being solved.

Mutation introduces random changes in the genetic information of individuals, helping to explore new areas of the solution space. It helps to maintain diversity in the population and prevents premature convergence to a suboptimal solution.

Different mutation operators can be applied, such as swapping, inversion, and insertion, depending on the problem and the representation of the solutions. The mutation rate determines the probability of a gene being mutated, and it should be carefully tuned to balance exploration and exploitation.

Crossover is the process of combining genetic information from two parents to create offspring. It simulates the genetic recombination that occurs in sexual reproduction. By exchanging genetic material, crossover creates new individuals that inherit traits from both parents.

Various crossover techniques exist, including one-point crossover, two-point crossover, and uniform crossover. The choice of crossover technique can significantly impact the exploration and exploitation capabilities of the algorithm, and it is often problem-dependent.

By utilizing optimization techniques like selection, mutation, and crossover, genetic algorithms are able to efficiently solve complex problems by iteratively evolving a population of candidate solutions. This enables the algorithm to navigate the search space and converge towards a near-optimal or optimal solution.

Parameter Tuning in Genetic Algorithms

Genetic algorithms (GA) are a powerful optimization technique inspired by the process of natural evolution. They mimic the mechanics of natural selection, crossover, and mutation to find the optimal solution to a problem. However, to achieve the best results, it is crucial to fine-tune the parameters of the GA algorithm.

One of the key parameters to consider is the mutation rate. Mutation introduces genetic diversity into the population by randomly modifying a small portion of the solution. A high mutation rate may cause excessive exploration of the search space, leading to slow convergence and a high risk of getting stuck in sub-optimal solutions. On the other hand, a low mutation rate may result in insufficient exploration, limiting the algorithm’s ability to escape local optima. Finding the right balance is necessary to strike a good trade-off between exploration and exploitation.

Another important parameter is the selection mechanism. The selection process determines which individuals are chosen as parents for generating the next generation. Several selection strategies, such as tournament selection and roulette wheel selection, are available. The choice of the selection mechanism impacts the diversity of the population and the convergence rate. It is essential to select a selection strategy that suits the problem at hand and balances diversity and convergence.

Additionally, the crossover rate is another critical parameter. Crossover involves combining genetic material from two parents to create offspring solutions. A high crossover rate ensures a significant exchange of genetic material, leading to greater exploration of the solution space. Conversely, a low crossover rate may limit the exchange of genetic information, resulting in a slower convergence rate and a reduced ability to find optimal solutions. Again, finding the right balance is crucial to achieving good results.

Importance of Parameter Tuning

The optimal parameter values for a genetic algorithm depend on the specific problem being solved and the characteristics of the search space. Different problems may require different settings to achieve the best performance. By tuning the parameters, practitioners can adapt the genetic algorithm to the problem at hand and improve its effectiveness.

Parameter tuning in genetic algorithms plays a crucial role in achieving optimal results. The mutation rate, selection mechanism, and crossover rate significantly impact the algorithm’s ability to find optimal solutions and the convergence speed. Finding the right balance between exploitation and exploration is essential for successful problem solving using genetic algorithms. Thus, practitioners should carefully tune these parameters to adapt the algorithm to the problem and maximize its performance.

Elitism in Genetic Algorithms

In the context of genetic algorithms, selection plays a crucial role in the evolution of a population towards an optimal solution for a given problem. One commonly used selection strategy is elitism. Elitism aims to preserve the best individuals from one generation to the next, ensuring their continued presence in the population.

What is Elitism?

Elitism is a strategy in genetic algorithms that selects the best individuals, based on their fitness, and carries them over to the next generation. It ensures that the most fit individuals are given a chance to reproduce and pass on their favorable traits to future generations. This strategy helps prevent the loss of valuable genetic information and accelerates the convergence of the population towards an optimal solution.

During the selection process, the individuals with the highest fitness values are identified and marked as elite. These elite individuals are automatically carried over to the next generation without any modification.

How Does Elitism Work?

Elitism works by selecting a fixed number of elite individuals, typically the top performers, from the current population. These selected individuals are then directly copied to the next generation, without undergoing any genetic crossover or mutation.

The remaining individuals in the population undergo genetic crossover and mutation, just like in a typical genetic algorithm. This allows for the exploration of new genetic combinations and the potential discovery of even better solutions to the problem at hand.

By incorporating elitism in the selection process, genetic algorithms can strike a balance between exploration and exploitation. The elites ensure that the best solutions are preserved and not lost in the evolutionary process, while the rest of the population continues to evolve and explore the problem space.

Elitism can greatly improve the performance of genetic algorithms, especially in cases where the search space is vast or the problem at hand is highly complex. It helps in avoiding premature convergence to suboptimal solutions by maintaining a diverse population and promoting the continual improvement of fitness over generations.

In conclusion, elitism is a powerful technique in genetic algorithms that prioritizes the retention of the best individuals in the population. It enhances the efficiency and effectiveness of the evolutionary process, leading to improved problem optimization and successful evolution towards the desired solution.

Hybridization with other Algorithms

In genetic algorithms, crossover and mutation operators are used to explore the search space and generate new solutions. However, these operators have limitations and may not always be sufficient to solve complex optimization problems. In such cases, hybridization with other algorithms can be a powerful approach to improve the performance of genetic algorithms.

Hybrid algorithms combine genetic algorithms with other optimization techniques to take advantage of their strengths and overcome their limitations. This approach allows for a more efficient and effective solution to problem-solving.

Crossover and Selection

In genetic algorithms, crossover is the process of combining genetic material from two solutions to create new offspring. It helps explore different regions of the search space and promotes the preservation of good solutions. However, in some cases, crossover alone may not be enough to find the global optimal solution due to the limitations of the genetic representation or the nature of the problem.

By combining genetic algorithms with other algorithms that use different crossover mechanisms, such as simulated annealing or particle swarm optimization, it is possible to enhance the exploration of the search space and improve the diversity of solutions. This hybridization approach can lead to better convergence and more accurate solutions.

Mutation and Other Optimization Algorithms

Mutation is an important operator in genetic algorithms as it introduces random changes to the genetic material. It helps escape from local optima and introduces diversity to the population. However, in some cases, mutation alone may not be enough to overcome the problem’s constraints or find the optimal solution.

Hybridization with other optimization algorithms, such as gradient-based algorithms or pattern search methods, can complement the mutation operator in genetic algorithms. By combining the strengths of both approaches, it is possible to improve the efficiency of the search and find better solutions.

In conclusion, hybridization with other algorithms is a valuable technique to enhance the performance of genetic algorithms in solving complex optimization problems. By combining the strengths of different algorithms, such as crossover and selection mechanisms, with other optimization techniques, it is possible to improve the exploration of the search space and find more accurate and efficient solutions to the problem at hand.

Real-world Applications of Genetic Algorithms

Genetic algorithms have been applied to various real-world problems, offering effective solutions by mimicking the process of natural evolution.

Optimization Problems

One of the most common applications of genetic algorithms is in solving optimization problems. These algorithms are used to find the best solution among a large set of possible solutions. The genetic algorithm applies the concepts of mutation and crossover to create new solutions and evolve towards the optimal solution over generations.

For example, in manufacturing processes, genetic algorithms can be used to optimize production schedules, minimizing cost and maximizing efficiency. By evaluating different combinations of machines, resources, and order sequences, genetic algorithms can find the most optimal arrangement to meet production goals.

Data Mining

Another important application of genetic algorithms is in data mining, where they can be used to discover patterns and relationships within large datasets. Genetic algorithms can analyze and optimize the parameters of machine learning models, allowing them to adapt and improve over time.

In finance, genetic algorithms can be used to predict stock prices and optimize investment portfolios. By evolving and selecting trading strategies based on historical data, genetic algorithms can identify profitable patterns and make informed investment decisions.

Routing and Scheduling

Genetic algorithms have also been applied to solve routing and scheduling problems in various domains. In transportation, genetic algorithms can optimize routes and scheduling for delivery vehicles, minimizing travel time and cost. In telecommunications, these algorithms can optimize the allocation of network resources and improve network efficiency.

Additionally, genetic algorithms have been used in urban planning to optimize traffic signal timing, reducing congestion and improving traffic flow. By evolving and evaluating different signal timing sequences, genetic algorithms can find the most effective solution to minimize delays and improve overall transportation efficiency.

In conclusion, genetic algorithms have found widespread use in solving real-world problems across various industries. By applying the concepts of genetic evolution, these algorithms offer effective and efficient solutions to optimization, data mining, routing, and scheduling problems.

What are genetic algorithms and how do they work?

Genetic algorithms are a type of evolutionary algorithm that is inspired by natural selection and genetics. They work by creating a population of candidate solutions to a problem, and then applying genetic operators such as selection, crossover, and mutation to evolve the population towards better solutions over generations.

What types of problems can be solved using genetic algorithms?

Genetic algorithms can be used to solve a wide range of problems, including optimization, machine learning, scheduling, and routing problems. They are particularly well-suited for problems with a large search space and where finding the optimal solution using traditional methods is difficult or time-consuming.

How do genetic algorithms ensure diversity within the population?

Genetic algorithms use selection mechanisms that give preference to individuals with higher fitness, but they also incorporate mechanisms to maintain diversity within the population. This can be done through the use of genetic operators such as crossover and mutation, which introduce new genetic material and prevent the population from converging prematurely.

What are the advantages of using genetic algorithms?

There are several advantages to using genetic algorithms. They are able to simultaneously explore multiple parts of the search space, which increases the likelihood of finding the global optimum. They are also able to handle complex, non-linear problems with multiple objectives. Additionally, genetic algorithms are flexible and can be easily customized to specific problem domains.

Are there any limitations of using genetic algorithms?

Yes, there are some limitations to using genetic algorithms. They can be computationally expensive, especially for large problem instances or when the fitness function is expensive to evaluate. Genetic algorithms also rely heavily on the quality of the initial population, and may get stuck in local optima if the search space is highly deceptive. Additionally, they may not be suitable for problems with constraints that are difficult to handle.

Genetic algorithms are a type of optimization algorithm inspired by the process of natural selection. They work by evolving a population of potential solutions to a problem through a process of selection, crossover, and mutation.

Related posts:

• Discover the Benefits of Genetic Algorithm for Efficient Problem Solving and Optimization
• Unleashing the Power of Genetic Algorithm in Machine Learning – A Revolutionary Approach to Solving Complex Problems
• Python Genetic Algorithm – An In-depth Guide to Optimization and Machine Learning
• Why genetic algorithm is the go-to approach for optimization
• A comprehensive guide to implementing a Genetic Algorithm in MATLAB for optimization problems
• Is Genetic Algorithm AI? Exploring the Relationship Between Genetic Algorithms and Artificial Intelligence
• Common Challenges Encountered in Implementing Genetic Algorithm Solutions
• Implementing a Genetic Algorithm to Solve Complex Optimization Problems
• Comparison of Genetic Algorithm and Bayesian Optimization Algorithms for Optimization Problems
• Comparing Genetic Algorithms and Evolutionary Algorithms – Unveiling the Differences and Applications

Real-World Uses for Genetic Algorithms

Last updated: June 11, 2023

• Deep Learning
• Machine Learning
• Metaheuristics

Baeldung Pro comes with both absolutely No-Ads as well as finally with Dark Mode , for a clean learning experience:

>> Explore a clean Baeldung

Once the early-adopter seats are all used, the price will go up and stay at $33/year.

1. Introduction

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.

2. Definitions

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.

3.1. Algorithm

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.

4. Applications

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.

4.1. Robotics

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.

4.2. Economics

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.

4.6. Marketing

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.

4.7. Medicine

In medicine and bioinformatics, genetic algorithms have been used to identify benign and malignant tumours in ultrasounds and mammograms.

5. Conclusions

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.

Advertisement

Genetic algorithms: theory, genetic operators, solutions, and applications

• Review Article
• Published: 03 February 2023
• Volume 17 , pages 1245–1256, ( 2024 )

Cite this article

• Bushra Alhijawi   ORCID: orcid.org/0000-0003-0806-102X 1 &
• Arafat Awajan 1 , 2  

4919 Accesses

44 Citations

Explore all metrics

A genetic algorithm (GA) is an evolutionary algorithm inspired by the natural selection and biological processes of reproduction of the fittest individual. GA is one of the most popular optimization algorithms that is currently employed in a wide range of real applications. Initially, the GA fills the population with random candidate solutions and develops the optimal solution from one generation to the next. The GA applies a set of genetic operators during the search process: selection, crossover, and mutation. This article aims to review and summarize the recent contributions to the GA research field. In addition, the definitions of the GA essential concepts are reviewed. Furthermore, the article surveys the real-life applications and roles of GA. Finally, future directions are provided to develop the field.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Genetic Algorithms

Genetic Programming

Explore related subjects

• Artificial Intelligence

BoussaïD I, Lepagnot J, Siarry P (2013) A survey on optimization metaheuristics. Inf Sci 237:82–117

MathSciNet   Google Scholar  

Agushaka JO, Ezugwu AE, Abualigah L (2022) Dwarf mongoose optimization algorithm. Comput Methods Appl Mech Eng 391:114570

Ezugwu AE, Agushaka JO, Abualigah L, Mirjalili S, Gandomi AH (2022) Prairie dog optimization algorithm. Neural Comput Appl 34(22):20017–20065

Google Scholar  

Abualigah L, Abd Elaziz M, Sumari P, Geem ZW, Gandomi AH (2022) Reptile search algorithm (RSA): a nature-inspired meta-heuristic optimizer. Expert Syst Appl 191:116158

Oyelade ON, Ezugwu AE-S, Mohamed TI, Abualigah L (2022) Ebola optimization search algorithm: a new nature-inspired metaheuristic optimization algorithm. IEEE Access 10:16150–16177

Holland J, Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Massachusetts

Mattfeld DC (2013) Evolutionary search and the job shop: investigations on genetic algorithms for production scheduling

Arabali A, Ghofrani M, Etezadi-Amoli M, Fadali MS, Baghzouz Y (2013) Genetic-algorithm-based optimization approach for energy management. IEEE Trans Power Deliv 28(1):162–170

Koza JR (1994) Genetic programming as a means for programming computers by natural selection. Stat Comput 4(2):87–112

Kim J-H, Myung H (1997) Evolutionary programming techniques for constrained optimization problems. IEEE Trans Evol Comput 1(2):129–140

Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359

Rechenberg I (1973) Evolution strategy: optimization of technical systems by means of biological evolution. Fromman Holzboog Stuttgart 104:15–16

Holland JH (1975) Adaptation in natural and artificial systems. In: An introductory analysis with application to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press, pp 439–444

Man K-F, Tang K-S, Kwong S (1996) Genetic algorithms: concepts and applications [in engineering design]. IEEE Trans Ind Electron 43(5):519–534

Mitchell M (1998) An introduction to genetic algorithms

Sudholt D (2018) The benefits of population diversity in evolutionary algorithms: a survey of rigorous runtime analyses. arXiv preprint arXiv:1801.10087

Kazimipour B, Li X, Qin AK (2014) A review of population initialization techniques for evolutionary algorithms. In: 2014 IEEE congress on evolutionary computation (CEC), IEEE, pp 2585–2592

Whitley D (1994) A genetic algorithm tutorial. Stat Comput 4(2):65–85

Mukhopadhyay A, Maulik U, Bandyopadhyay S, Coello CAC (2014) A survey of multiobjective evolutionary algorithms for data mining: part i. IEEE Trans Evol Comput 18(1):4–19

Bodenhofer U (2003) Genetic algorithms: theory and applications. Lecture notes, Fuzzy logic laboratorium Linz-Hagenberg, Winter

Sastry K, Goldberg DE, Kendall G (2014) Genetic algorithms. In: Search methodologies, pp 93–117

Goldberg DE, Holland JH (1988) Genetic algorithms and machine learning. Mach Learn 3(2):95–99

Baker JE (1987) Reducing bias and inefficiency in the selection algorithm. In: Proceedings of the second international conference on genetic algorithms, pp 14–21

Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. Found Genetic Algorithms 1:69–93

Schlierkamp-Voosen D, Mühlenbein H (1993) Predictive models for the breeder genetic algorithm. Evol Comput 1(1):25–49

Spears WM, De Jong KD (1995) On the virtues of parameterized uniform crossover. Technical report, Naval Research Lab Washington DC

Sivrikaya-Şerifoğlu F (1997) A new uniform order-based crossover operator for genetic algorithm applications to multi-component combinatorial optimization problems. Unpublished PhD dissertation, Boğaziçi University, Istanbul

Paul PV, Ramalingam A, Baskaran R, Dhavachelvan P, Vivekanandan K, Subramanian R (2014) A new population seeding technique for permutation-coded genetic algorithm: service transfer approach. J Comput Sci 5(2):277–297

Deng Y, Liu Y, Zhou D (2015) An improved genetic algorithm with initial population strategy for symmetric TSP. In: Mathematical problems in engineering

Hassanat AB, Prasath V, Abbadi MA, Abu-Qdari SA, Faris H (2018) An improved genetic algorithm with a new initialization mechanism based on regression techniques. Information 9(7):167

Kaya M (2011) The effects of two new crossover operators on genetic algorithm performance. Appl Soft Comput 11(1):881–890

Rafsanjani MK, Eskandari S (2011) A new combinational selection operator in genetic algorithm. AIP Conf Proc 1389:1082–1085 ( AIP )

Rafsanjani MK, Eskandari S (2012) The effect of a new generation based sequential selection operator on the performance of genetic algorithm. Indian J Sci Technol 5(12):3758–3761

Hussain A, Muhammad YS (2020) Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator. Complex Intell Syst 6(1):1–14

Kaya Y, Uyar M, Tekın R (2011) A novel crossover operator for genetic algorithms: ring crossover. arXiv preprint arXiv:1105.0355

Semenkin E, Semenkina M (2012) Self-configuring genetic algorithm with modified uniform crossover operator. In: International conference in swarm intelligence, Springer, pp 414–421

Thakur M (2014) A new genetic algorithm for global optimization of multimodal continuous functions. J Comput Sci 5(2):298–311

Elsayed SM, Sarker RA, Essam DL (2014) A new genetic algorithm for solving optimization problems. Eng Appl Artif Intell 27:57–69

Osaba E, Onieva E, Carballedo R, Diaz F, Perallos A (2014) An adaptive multi-crossover population algorithm for solving routing problems. In: Nature inspired cooperative strategies for optimization (NICSO 2013), pp 113–124

Jin C, Li F, Tsang EC, Bulysheva L, Kataev MY (2017) A new compound arithmetic crossover-based genetic algorithm for constrained optimisation in enterprise systems. Enterpr Inf Syst 11(1):122–136

Demirci H, Ozcerit A, Ekiz H, Kutlu A (2015) Chaotic crossover operator on genetic algorithm. In: Proceedings of 2nd international conference on information technology

Alkafaween E (2018) Novel methods for enhancing the performance of genetic algorithms. CoRR https://arxiv.org/abs/1801.02827

Hassanat AB, Alkafaween E (2017) On enhancing genetic algorithms using new crossovers. Int J Comput Appl Technol 55(3):202–212

Xue Y, Zhu H, Liang J, Słowik A (2021) Adaptive crossover operator based multi-objective binary genetic algorithm for feature selection in classification. Knowl Based Syst 227:107218

Koohestani B (2020) A crossover operator for improving the efficiency of permutation-based genetic algorithms. Expert Syst Appl 151:113381

Manzoni L, Mariot L, Tuba E (2020) Balanced crossover operators in genetic algorithms. Swarm Evol Comput 54:100646

Viana MS, Morandin Junior O, Contreras RC (2020) A modified genetic algorithm with local search strategies and multi-crossover operator for job shop scheduling problem. Sensors 20(18):5440

Albayrak M, Allahverdi N (2011) Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. Expert Syst Appl 38(3):1313–1320

Marung U, Theera-Umpon N, Auephanwiriyakul S (2016) Top-n recommender systems using genetic algorithm-based visual-clustering methods. Symmetry 8(7):54

Yuan Y, Wang W, Pang W (2021) A genetic algorithm with tree-structured mutation for hyperparameter optimisation of graph neural networks. In: 2021 IEEE congress on evolutionary computation (CEC), IEEE, pp 482–489

Haghrah A, Nekoui M, Nazari-Heris M, Mohammadi-ivatloo B (2021) An improved real-coded genetic algorithm with random walk based mutation for solving combined heat and power economic dispatch. J Ambient Intell Humaniz Comput 12(8):8561–8584

Alhijawi B, Kilani Y (2020) A collaborative filtering recommender system using genetic algorithm. Inf Process Manag 57(6):102310

Armagan A, Dunson DB, Lee J (2013) Generalized double pareto shrinkage. Stat Sin 23(1):119

Kumar M, Husian M, Upreti N, Gupta D (2010) Genetic algorithm: review and application. Int J Inf Technol Knowl Manag 2(2):451–454

Paulinas M, Ušinskas A (2007) A survey of genetic algorithms applications for image enhancement and segmentation. Inf Technol Control 36:3

Połap D (2020) An adaptive genetic algorithm as a supporting mechanism for microscopy image analysis in a cascade of convolution neural networks. Appl Soft Comput 97:106824

Sun Y, Xue B, Zhang M, Yen GG, Lv J (2020) Automatically designing CNN architectures using the genetic algorithm for image classification. IEEE Trans Cybern 50(9):3840–3854

Chen R, Yang B, Li S, Wang S (2020) A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Comput Ind Eng 149:106778

Zhou Z, Li F, Zhu H, Xie H, Abawajy JH, Chowdhury MU (2020) An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments. Neural Comput Appl 32(6):1531–1541

Maulik U, Bandyopadhyay S (2000) Genetic algorithm-based clustering technique. Pattern Recogn 33(9):1455–1465

Sheikh RH, Raghuwanshi MM, Jaiswal AN (2008) Genetic algorithm based clustering: a survey. In: 2008. ICETET’08. First international conference on emerging trends in engineering and technology, IEEE, pp 314–319

Mohammadrezapour O, Kisi O, Pourahmad F (2020) Fuzzy c-means and k-means clustering with genetic algorithm for identification of homogeneous regions of groundwater quality. Neural Comput Appl 32(8):3763–3775

Harman M, McMinn P, De Souza JT, Yoo S (2012) Search based software engineering: techniques, taxonomy, tutorial. In: Empirical software engineering and verification, pp 1–59

Srivastava PR, Kim T (2009) Application of genetic algorithm in software testing. Int J Softw Eng Appl 3(4):87–96

Harman M (2007) The current state and future of search based software engineering. In: 2007 Future of software engineering, IEEE Computer Society, pp 342–357

Ramkumar R, Mala G (2021) Non functional requirement based software architecture scheme with security requirement using hybrid group search optimization and genetic algorithm. J Ambient Intell Humaniz Comput 12(5):4863–4876

Alhijawi B, Awajan A (2021) Novel textual entailment technique for the Arabic language using genetic algorithm. Comput Speech Lang 68:101194

Iqbal F, Hashmi JM, Fung BC, Batool R, Khattak AM, Aleem S, Hung PC (2019) A hybrid framework for sentiment analysis using genetic algorithm based feature reduction. IEEE Access 7:14637–14652

Ar Y, Bostanci E (2016) A genetic algorithm solution to the collaborative filtering problem. Expert Syst Appl 61:122–128

Dwivedi P, Kant V, Bharadwaj KK (2018) Learning path recommendation based on modified variable length genetic algorithm. Educ Inf Technol 23(2):819–836

Hashemi S, Kiani S, Noroozi N, Moghaddam ME (2010) An image contrast enhancement method based on genetic algorithm. Pattern Recogn Lett 31(13):1816–1824

Daniel E, Anitha J (2015) Optimum green plane masking for the contrast enhancement of retinal images using enhanced genetic algorithm. Optik Int J Light Electron Opt 126(18):1726–1730

Deborah H, Arymurthy AM (2010) Image enhancement and image restoration for old document image using genetic algorithm. In: 2010 Second international conference on advances in computing, control and telecommunication technologies (ACT), IEEE, pp 108–112

Guo F, Peng H, Tang J (2016) Genetic algorithm-based parameter selection approach to single image defogging. Inf Process Lett 116(10):595–602

Wijayaningrum VN, Mahmudy WF (2016) Optimization of ship’s route scheduling using genetic algorithm. Indones J Electr Eng Comput Sci 2(1):180–186

Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287

Faghihi V, Reinschmidt KF, Kang JH (2014) Construction scheduling using genetic algorithm based on building information model. Expert Syst Appl 41(16):7565–7578

Konar D, Bhattacharyya S, Sharma K, Sharma S, Pradhan SR (2017) An improved hybrid quantum-inspired genetic algorithm (Hqiga) for scheduling of real-time task in multiprocessor system. Appl Soft Comput 53:296–307

Keshanchi B, Souri A, Navimipour NJ (2017) An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. J Syst Softw 124:1–21

Soundarya V, Kanimozhi U, Manjula D (2017) Recommendation system for criminal behavioral analysis on social network using genetic weighted k-means clustering. JCP 12(3):212–220

Wang Z, Yu X, Feng N, Wang Z (2014) An improved collaborative movie recommendation system using computational intelligence. J Vis Lang Comput 25(6):667–675

Georgiou O, Tsapatsoulis N (2010) Improving the scalability of recommender systems by clustering using genetic algorithms. In: International conference on artificial neural networks, Springer, pp 442–449

El-Samak AF, Ashour W (2015) Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm. J Artif Intell Soft Comput Res 5(4):239–245

Rahman MA, Islam MZ (2014) A hybrid clustering technique combining a novel genetic algorithm with k-means. Knowl Based Syst 71:345–365

Shaw MKE (2015) K-means clustering with automatic determination of k using a multiobjective genetic algorithm with applications to microarray gene expression data. PhD thesis, San Diego State University

Lahari K, Murty MR, Satapathy SC (2015) Partition based clustering using genetic algorithm and teaching learning based optimization: performance analysis. In: Emerging ICT for bridging the future-proceedings of the 49th annual convention of the computer society of India CSI, vol 2, Springer, pp 191–200

Ahmed MA, Hermadi I (2008) Ga-based multiple paths test data generator. Comput Oper Res 35(10):3107–3124

Rao KK, Raju G, Nagaraj S (2012) Optimizing the software testing efficiency using genetic algorithm-implementation methodology. Softw Eng Technol 4(10):432–439

Räihä O (2010) A survey on search-based software design. Comput Sci Rev 4(4):203–249

Bhatia N (2016) A cluster adaptive genetic model for improving the recommender system. Imp J Interdiscip Res 2:8

Gupta A, Shivhare H, Sharma S (2015) Recommender system using fuzzy c-means clustering and genetic algorithm based weighted similarity measure. In: International conference on computer, communication and control (IC4), IEEE

Alahmadi DH, Zeng X-J (2015) Twitter-based recommender system to address cold-start: a genetic algorithm based trust modelling and probabilistic sentiment analysis. In: IEEE 27th international conference on tools with artificial intelligence (ICTAI), IEEE, pp 1045–1052

Verma A, Virk HK (2015) A hybrid recommender system using genetic algorithm and KNN approach. Int J Comput Sci Trends Technol (IJCST) 6(3):131–134

Verma A, Virk H (2015) A hybrid genre-based recommender system for movies using genetic algorithm and KNN approach. Int J Innov Eng Technol 5(4):48–55

Alhijawi B, Kilani Y (2016) Using genetic algorithms for measuring the similarity values between users in collaborative filtering recommender systems. In: 2016 IEEE/ACIS 15th international conference on computer and information science (ICIS), IEEE, pp 1–6

Xiao J, Luo M, Chen J-M, Li J-J (2015) An item based collaborative filtering system combined with genetic algorithms using rating behavior. In: International conference on intelligent computing, Springer, pp 453–460

Alhijawi B, Kilani Y, Alsarhan A (2020) Improving recommendation quality and performance of genetic-based recommender system. Int J Adv Intell Paradig (IJAIP) 10:1

Fong S, Ho Y, Hang Y (2008) Using genetic algorithm for hybrid modes of collaborative filtering in online recommenders. In: Eighth international conference on hybrid intelligent systems, HIS’08, IEEE, pp 174–179

Salehi M (2014) Latent feature based recommender system for learning materials using genetic algorithm. Inf Syst Telecommun 137

Athani M, Pathak N, Khan AU (2014) Dynamic music recommender system using genetic algorithm. Int J Eng Adv Technol 3(4):230–232

Zhang F, Chang H-y (2006) A collaborative filtering algorithm employing genetic clustering to ameliorate the scalability issue, IEEE, pp 331–338

Download references

Author information

Authors and affiliations.

Princess Sumaya University for Technology, Amman, Jordan

Bushra Alhijawi & Arafat Awajan

Mutah University, Al-Karak, Jordan

Arafat Awajan

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Bushra Alhijawi .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Alhijawi, B., Awajan, A. Genetic algorithms: theory, genetic operators, solutions, and applications. Evol. Intel. 17 , 1245–1256 (2024). https://doi.org/10.1007/s12065-023-00822-6

Download citation

Received : 24 July 2022

Revised : 02 December 2022

Accepted : 31 December 2022

Published : 03 February 2023

Issue Date : June 2024

DOI : https://doi.org/10.1007/s12065-023-00822-6

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Genetic algorithms
• Evolutionary algorithm
• Genetic operators
• Optimization
• Find a journal
• Publish with us
• Track your research

Help Center Help Center

• Help Center
• Trial Software
• Product Updates
• Documentation

What Is the Genetic Algorithm?

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming , where some components are restricted to be integer-valued.

This flow chart outlines the main algorithmic steps. For details, see How the Genetic Algorithm Works .

The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

Selection rules select the individuals, called parents , that contribute to the population at the next generation. The selection is generally stochastic, and can depend on the individuals' scores.

Crossover rules combine two parents to form children for the next generation.

Mutation rules apply random changes to individual parents to form children.

The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table:

Related Topics

• Genetic Algorithm Terminology
• How the Genetic Algorithm Works
• Nonlinear Constraint Solver Algorithms for Genetic Algorithm
• Local vs. Global Optima

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

• Switzerland (English)
• Switzerland (Deutsch)
• Switzerland (Français)
• 中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)

Contact your local office

Augmenting genetic algorithms with machine learning for inverse molecular design

First published on 11th September 2024

Evolutionary and machine learning methods have been successfully applied to the generation of molecules and materials exhibiting desired properties. The combination of these two paradigms in inverse design tasks can yield powerful methods that explore massive chemical spaces more efficiently, improving the quality of the generated compounds. However, such synergistic approaches are still an incipient area of research and appear underexplored in the literature. This perspective covers different ways of incorporating machine learning approaches into evolutionary learning frameworks, with the overall goal of increasing the optimization efficiency of genetic algorithms. In particular, machine learning surrogate models for faster fitness function evaluation, discriminator models to control population diversity on-the-fly, machine learning based crossover operations, and evolution in latent space are discussed. The further potential of these synergistic approaches in generative tasks is also assessed, outlining promising directions for future developments.

Introduction

Given the success of both evolutionary and machine learning in materials science, it is natural to investigate the combination of both approaches. While being an incipient area of research still in its infancy, efforts have been made to explore the synergies and some very promising advances have already been achieved.

In this perspective we will first give a brief introduction to evolutionary learning (EL) and in particular genetic algorithms (GAs). Next, we will review a series of studies on materials optimization using hybrid approaches that utilize techniques from evolutionary and machine learning. Finally, we conclude with a short summary and discuss opportunities for further developments and applications.

GAs, first popularized by Holland in the 1970s, 47 are one of many different types of EL algorithms and are commonly used in materials science for the de novo design of materials and molecules. 48 Like all other types of EL approaches, they are generic and heuristic optimization algorithms that make no prior assumptions about the solution domain. GAs are inspired by Darwinian evolution and draw concepts from evolutionary biology such as mutation, recombination, and selection. The underlying key idea of GAs is that evolution is dictated by two competing forces: variation, which pushes the population towards novelty, and selection, which pushes the population towards quality. Combining both forces in an iterative optimization scheme leads to an efficient search strategy that balances exploration and exploitation in solution space. The efficiency of GAs is due to the heuristic nature of selection and recombination operations, that leverage the best partial solutions to construct better solutions. This makes them ideal for exploring chemical spaces that are usually large and diverse. On the flip side however, this also means that GAs are non-deterministic, meaning that they are not guaranteed to converge to the global optimum.

In the following, the basic building blocks of GAs are briefly described. The literature provides comprehensive overviews and discussions on the essential building blocks of GAs 49 and their applications to chemistry and materials science. 48

GAs operate on a set of solutions called the population, that is iteratively optimized to yield higher quality solutions over the course of multiple generations. Following the language of evolutionary biology, the solutions are also called individuals, which in chemistry and related fields usually represent molecules or materials. 48 In each generation, new offspring solutions are created by applying genetic operations that combine information of the currently best performing solutions (exploitation) and introduce random mutations (exploration). The newly generated offspring solutions then compete against the solutions of the previous population, and only the best performing solutions are carried over to the next generation. This process is repeated until some sort of convergence criterion is met (often times simply a maximal number of iterations). 49,50 There are four main building blocks to any GA that can be adapted in order to modify the evolution behavior in terms of the search space, optimization target, selection pressure, and diversity control:

• Chromosome: defines the representation of the solutions.

• Fitness: measures the quality of the solutions.

• Genetic operations: create new solutions from existing ones.

• Selection: selects individuals of the population based on their fitness.

This modular nature makes GAs ideal for applications in chemistry and materials science where optimization tasks are usually problem specific and diverse. 48 All solutions in a GA share a common, underlying structure that completely defines their traits. In technical terms, this is represented as an array where each cell corresponds to a different property of the solution. These cells are referred to as the genes, which in the array, form the chromosome, expressing properties of a problem-dependent nature. The chromosome usually has a fixed length and its cell values can be of different data types ( e.g. boolean, integer or float). During evolution, new offspring solutions will be created by applying genetic operations to the chromosome. Therefore, all chromosome values are usually constrained to be of the same data type so that meaningful recombination operations between them can be defined. 49,50 In applications to chemistry and material science the chromosome is the molecular representation. 48 Most commonly used are line notations such as SMILES 51 that represent molecules using a single cell of data type string.

The quality of a solution is measured in terms of a so-called fitness that reflects how well it satisfies a specified set of requirements. Thereby, it essentially defines the optimization objective and is determined by the specific problem to be solved. The fitness is a real valued function of the chromosome that can be thought of as a hyper-surface on which the GA tries to find (local) optima. In multi-objective optimization settings 52–61 it is a vector, where each dimension corresponds to a different property of interest. Calculation of the fitness is usually the computational bottleneck of GAs and since it is evaluated multiple times per generation, its choice has significant implications on the overall computational cost and performance. 49,50

Genetic operations are used to generate new offspring solutions in each generation and push the population towards novelty. They can be subdivided into two groups, crossover and mutation, which are usually performed in sequence. First, the genomes of two parent solutions are recombined in a crossover operation to form an offspring solution that then is further modified by a random mutation. However, there also exist variations to this process in which either crossover or mutation operations alone are used in order to obtain offspring solutions. 49,50 The crossover propagates characteristics of the parent solutions to the offspring. Together with parent selection, it ensures that genetic information of well performing solutions is carried over to the next generations. There exist different implementations, such as the single point crossover in which the two parent chromosomes are split at a random position and then exchange genes. 49,50 Mutations, on the other hand, usually introduce completely new genetic information in a random fashion, which ensures diversity in the explored solutions. There are many different implementations for such mutation operations, one example is the single point mutation that randomly changes a single gene in a solution's chromosome. Mutations can also be defined according to a predefined rule, for example the swap mutation switches the values of two genes. 49,50

Selection pushes the population towards quality by discarding badly performing solutions. Selection is performed twice in each generation, once to determine which solutions are recombined to create new offspring (parent selection), and once to determine which solutions proceed to the next generation (survivor selection). The selection rules are usually stochastic and dependent on the solutions fitnesses so that the fittest are more likely to be selected. This ensures that the population evolves towards better performing solutions while maintaining some level of diversity. 49,50

In chemistry and materials science, GAs are known to be efficient optimization tools, aiding the exploration of large chemical spaces of diverse nature. 57,62–66 An important contribution to the field is the graph-based GA (GB-GA) 67 that utilizes the graph representations of molecules to define crossover and mutation operations offering an alternative to the more common string based SMILES representation. 51 Recent advances include the PL-MOGA 61 that facilitates the directed, multi-objective optimization of transition metal complexes, and GAMaterial 68 which enables the machine learning (ML) accelerated optimization of materials and others. 34,55,69–71 Furthermore, GAs have been used for the optimization of molecular structures and conformer search. For example in the automated interaction site screening (aISS) 72 approach, that finds accurate aggregate geometries, such as dimers, at low computational cost.

Surrogate fitness functions

The authors further proposed two additions to this standard GA framework: a diversity control mechanism to prevent evolutionary stagnation and a distance penalty to account for low prediction confidence of the ANN for data points very different from the training data. Their proposed diversity control mechanism increases the mutation probability to 0.5 if the ratio of unique complexes in the current generation falls below 25%. The increased mutation rate pushes the GA to explore new regions in the chemical space and thereby prevents the GA from getting stuck in a local optimum. The distance penalty is motivated by the observation that ML prediction results tend to become unreliable for data points very different from the training data. In a GA where the fitness is based on surrogate predictions, poor predictive performance can hinder evolution and lead to poor final results. Therefore, using model uncertainty to estimate the surrogate accuracy can be useful to avoid basing evolution on overconfident fitness predictions. 77 In previous work, 75 the authors showed that a large distance in feature space is a potent indicator of model accuracy ( Fig. 1 ) and successfully used it with a set of features that emphasizes metal-proximal properties.

They benchmarked four different variants of the GA: (1) the standard GA, (2) GA with diversity control, (3) GA with distance penalty, and (4) GA with both diversity control and distance penalty. In all cases, the GA was initialized with a random selection of 20 complexes and run for a total of 21 generations. The standard GA quickly converged due to a single candidate completely dominating the solution. The GA with diversity control exhibited a slightly higher diversity in the final population while approaching fitness values to those of the standard GA. However, both the standard GA and the diversity-controlled GA converged towards candidates with on average large distances to the training data and therefore low prediction confidence. Introducing the distance penalty term in the fitness function lead to candidates with 50% lower mean distances to the training data at the cost of a 25% reduction of the mean population fitness. With this approach, the authors could achieve both higher diversity in the final candidates as well as fairly small mean distances to the training data. With ∼50 repeats of the GA, roughly half of the design space could be sampled using the standard and diversity-controlled approach. With the combined control strategy, 80% of the lead compounds could be identified, which constitutes an increase of ∼30% compared to the standard GA. The majority of missed lead compounds had large distances to the training data, indicating that the distance penalty term works as intended and discourages exploration in areas of low confidence, which nonetheless contain a small proportion of the leads.

In order to estimate the robustness of the ANN-based fitness, the authors determined the accuracy of the surrogate model for a subset of lead compounds identified by the GA. Relative to DFT, they obtained an average test error of 4.5 kcal mol −1 , which is moderately higher than the model baseline error of 3.0 kcal mol −1 . For complexes that were very similar to the training data, the observed mean error was 1.5 kcal mol −1 . Furthermore, two thirds of the ANN lead compounds could be validated by DFT optimization, though including solvent effects and thermodynamic corrections reduced this ratio to one half. According to the authors, these findings demonstrated sufficient predictive performance of the ANN fitness for its use in evolutionary design applications.

In their conclusion, the authors emphasized the massive gains in terms of computational efficiency compared to a traditional GA with a DFT-based fitness function that would require up to 30 days of computing walltime. However, the computational cost associated with acquiring the training data (here roughly 50% of the investigated space) remains a significant contribution. They furthermore noted that the observed ANN errors in the final populations could be reduced by decreasing d opt and discussed options for leveraging low-confidence candidates to retrain the surrogate model on-the-fly, in order to improve the predictive accuracy of the model in subsequent generations.

Forrest and co-worker 79 made use of similar concepts for the evolutionary optimization of alloy compositions with respect to their glass forming ability. Instead of a single ANN, they used an ensemble of ANNs as a surrogate fitness function in order to facilitate predictions of relevant properties such as the temperature of the crystallization onset. Further, Kwon and co-workers 80 utilized a surrogate model in an evolutionary approach to optimize the maximum light-absorbing wavelengths in organic molecules. Since their evolutionary algorithm operated directly on bit-string fingerprint vectors 81 they furthermore used a separate RNN to decode them into chemically valid molecular structures.

Bayesian surrogate models

In their 2019 study, 87 Jennings and co-workers showcased such a model by investigating the atom ordering of a 147-atom Mackay icosahedral structure. 88 They considered all possible compositions Pt x Au 147− x for all x ∈ [1, 146]. The optimization goal was to locate the hull of minimum excess energy configurations for all compositions as calculated by the Effective Medium Potential (EMT) potential, 89 which served as the fitness. The authors defined a traditional GA that operates on the configuration of Pt and Au atoms. Cut and splice crossover functions 90 as well as random permutation and swapping mutations were used to create new offspring configurations. The crossover and mutation operations were set up to be mutually exclusive, meaning that offspring was created using either one or the other method. Parents were selected with a roulette wheel selection scheme based on the fitness values. In order to ensure that all compositions were searched, the authors furthermore employed a niching scheme in which solutions are grouped according to their composition. Their fitness was then determined per niche and the best configurations per composition niche were given equal fitness.

Finally, the authors replaced the EMT potential with a more accurate DFT calculation and repeated the experiments in order to prove that the obtained results were not an artifact of the EMT potential. The results showed that a performance similar to that observed with the EMT potential could be achieved, requiring ∼700 DFT evaluations.

Overall, this work demonstrated a significant speed-up with their ML accelerated GA and motivated further improvements by proposing a way of including geometry optimization with additional genetic operators acting on the atomic coordinates.

Ensuring population diversity

The discriminator D (·) is a dense ANN with ReLU activations and a sigmoid output layer that distinguishes molecules generated by the GA from molecules of a reference dataset. In each generation it is trained for 10 epochs on the molecules of the current population and an equal amount of molecules randomly drawn from the reference dataset, using chemical and geometrical properties as features. In the next generation, this model is then used to assign novelty scores to the newly generated molecules. Molecules that are similar to the molecules of the previous generation will receive low scores, whereas molecules that are more similar to structures of the reference dataset will receive high scores. Because the discriminator score enters the fitness function, the novelty of proposed molecules directly influences their chance of survival. This effect is illustrated in Fig. 3 displaying the workflow of the discriminator ANN. A nice property of this approach is that the discriminator ANN will become very good at identifying long-surviving molecules, assigning low novelty scores, and therefore making it less likely that they will proceed to the next generation. This discourages the survival of already explored solutions and forces the GA to explore regions of the chemical space that are similar to the reference dataset. The authors confirmed this in an investigative study showing that the higher the value of β , the more similar to the reference dataset are the proposed molecules.

The authors further refined their approach with an adaptive discriminator scheme that introduces a time-dependence for the β parameter. In this setting, β is set to zero and only if the optimization stagnates its value is increased to 1000, in order to encourage exploration. Once stagnation is overcome, β will be set to zero again.

The authors concluded by highlighting the domain independence of their approach, making it interesting also for applications outside the field of chemistry and discussed possible improvements using another ANN for fitness evaluation.

Balancing exploration and exploitation

To that end, Nigam and co-workers improved on their previous ANN-augmented GA 92 by proposing JANUS, 99 a parallel GA guided by ANNs. JANUS maintains two distinct and independent, fixed size populations as they are separately evolved. With this two-pronged approach, one population is responsible for exploration while the other takes care of exploitation. At the beginning of each generation, the populations can furthermore exchange individuals in order to combine the benefits of both approaches. A schematic description of the JANUS architecture is shown in Fig. 4 .

Analogous to their previous work, JANUS operates directly on SELFIES strings that represent molecules and, as in any other GA, the quality of an individual is measured using a fitness function. Selection of survivors is performed deterministically, meaning that only the best solutions proceed to the next generation. The genetic operators employed differ for the two different populations in order to promote either exploration or exploitation. The exploitative population uses the same insertion and replacement mutations excluding crossovers, as in their previous work, 92 and applies them to the n currently best solutions. In addition to these mutations, the explorative population uses an interpolation crossover that generates paths between two parents through matching and replacing characters until both are equal. For all intermediates along these paths, the joint similarity 100 to both parents in terms of the Tanimoto score is calculated and the molecule with the highest score is selected as the final offspring resulting from crossover. Parents are selected according to a simulated annealing strategy that allows badly performing individuals to be selected with low probabilities which allows the population to escape local optima.

Additional selection pressure is applied to filter the offspring individuals before survivor selection. In the exploitative population only molecules that are similar to the parents are propagated further. In the explorative population an ANN is used to predict fitness values and, based on its predictions, the highest scoring individuals are added to the population. Alternatively, a classifier ANN can be used which directly sorts the offspring individuals into either “good” or “bad”, only allowing “good” molecules to enter the population. Either approach effectively constitutes a pre-selection of the most promising solutions at a low computational cost. The ANN is trained in each generation with all molecules for which the fitness is known. This implies that the ANNs predictive accuracy becomes better over the course of multiple generations as more data is added to the training set. For the classifier ANN, a %-threshold is used to identify which molecules belong to the “good” and “bad” classes. In their study, the authors experimented with the top 50% and 20%.

JANUS was furthermore tested on two more molecular benchmarks: the imitated protein inhibition task, 102 in which the objective is to generate 5000 molecules that inhibit two different proteins (either one or both) while exhibiting high drug-likeness as measured by the QED score 97 and low synthetic accessibility penalty as measured by the SA score, 93 and a docking task 103 considering four different protein targets with the goal of finding molecules that minimize the respective docking scores. In both benchmarks the authors found JANUS to outperform other approaches from the literature and achieve state-of-the-art results in terms of the fitness objective. The diversity of generated molecules however was reduced compared to results from the literature. The authors proposed that the incorporation of a discriminator 92 may promote population diversity and alleviate this shortcoming.

The authors concluded their work by discussing the low synthetic accessibility of most of the generated compounds in all investigated benchmarks and proposed ways of directly accounting for synthesizability in the molecular design process, either during structure generation or fitness evaluation, and using multi-objective GAs 104 that do not make use of the naive weighted sum approach. In this regard, there are now powerful alternatives like stability filters 34 and the PL-MOGA, 61 respectively. The authors furthermore discussed plans for incorporating their previously developed discriminator for population diversity 92 into the JANUS framework in order to improve the GAs ability to escape local optima.

Modifying crossover

Alternatively, Pareto-based multi-objective optimization techniques can be employed to incorporate the constraints as separate optimization goals. By using appropriate methods to guide the search 61 effective cutoffs for the constraints can be implemented. However, if there are many constraints to encode or other optimization objectives to consider, optimization efficiency and convergence speed will suffer drastically due to the curse of dimensionality.

An entirely different approach is to modify the genetic operators so that the generated offspring solutions satisfy the desired constraints. In this way, the fitness function remains completely independent from the specific constraints while ensuring that all generated solutions satisfy them intrinsically. Naively, this can be implemented by preselecting proposed offspring solutions based on threshold values for the constraints to be considered.

By introducing ChemistGA ( Fig. 5 ), 105 Wang and co-workers demonstrated the use of an ANN-based crossover operation to account for synthetic accessibility during offspring generation in the evolutionary de novo design of drug-like compounds. The optimization goals were, in different combinations, protein activities for DRD2, JNK3, and GSK3β, drug-likeness as measured by the QED score, 97 and synthetic accessibility as measured by the SA score. 93 All molecules were represented as SMILES strings.

The authors furthermore propose an alternative architecture, R-ChemistGA, that utilizes a random forest surrogate model for molecular property prediction in order to reduce computational cost during fitness evaluation. Every fifth generation the molecular properties are calculated using the true fitness function, and the obtained values are used to retrain the random forest in order to improve the models predictive accuracy. While the resulting model adds noise to the evolutionary process, it is also much more appropriate for a real world application in which property predictions are expensive and may not necessarily be carried out freely.

In a first benchmark experiment, the authors tested their model against GB-GA 67 on a task aimed at maximizing activity for protein targets JNK3 and GSK3β, as well as the QED and SA scores. Almost 50% of molecules generated by ChemistGA had high activities for both proteins, whereas GB-GA was not able to generate any. Looking at the different optimization goals individually, ChemistGA outperformed GB-GA with respect to all but the SA score, for which the two models performed similarly. Further investigations revealed that ChemistGAs crossover approach facilitated a more reasonable inheritance of molecular patterns due to the MT preserving the parents substructures more accurately.

Next, they investigated performance in terms of synthesizability, novelty, diversity, and the quantity of unique molecular skeleton types based on the Murcko scaffold 109 for 5000 generated molecules. Two different optimization tasks were assessed: (1) one with only DRD2 and (2) one with JNK3 and GSK3β as protein activity targets in addition to the QED and SA scores. They benchmarked their results against GB-GA and REINVENT. 110 In both tasks, ChemistGA outperformed the other models in terms of novelty and diversity of generated molecules while achieving similar synthesizability. In terms of the number of generated molecular scaffolds, ChemistGA slightly outperformed REINVENT but was inferior to GB-GA in task (1). In task (2) however, ChemistGA generated more than four times as many distinct scaffolds compared to REINVENT. Overall, the proposed architecture seemed to exhibit higher capabilities of exploring the chemical search space compared to the benchmark models.

Finally, the authors turned their attention to their alternative proposed architecture R-ChemistGA, which uses a random forest surrogate to predict fitness values and ran it on the same two tasks. Compared to their baseline model, ChemistGA, the number of generated molecules with R-ChemistGA exhibiting desired properties was twice as high per evaluation of the true fitness function. This indicates that a GA utilizing a noisy surrogate model is still able to guide the optimization into favorable directions. In terms of synthesizability, diversity, and number of scaffolds, R-ChemistGA performed slightly worse compared to the baseline, though the novelty of generated molecules was the highest of all investigated models. Using a t-SNE 111 plot of the best synthesizable molecules, the authors furthermore showed that R-ChemistGA explores larger regions of chemical space and asserted that their architecture produced more reasonable molecules with higher synthesizability.

Evolution in latent space

In closing, the authors discussed the scalability and general applicability of their method and proposed the integration of geometric deep learning models to better represent molecules in terms of their 3D structures.

Abouchekeir and co-workers 129 adapted this approach by replacing the VAE with an adversarial autoencoder (AAE) 130 that aims at decoding latent space vectors into molecular structures indistinguishable from the training data distribution. Benchmarked on the same datasets and optimization goals, their method produced better candidates in the final population and explored a larger hypervolume in chemical space compared to the original DEL approach. The authors attributed this to the more organized latent space produced by the AAE.

Summary and outlook

Besides the fitness function, other uses of ML methods in EL seem to be less explored in the literature. However, the works reviewed here for maintaining population diversity 92 and facilitating constrained crossovers 105 showed promising results. The proposed models outperformed the GAs that were not augmented with ML, indicating their superior efficiency compared to traditional methods. However, their behavior needs to be further explored on more diverse benchmarks and improved architectures should be derived based on the findings of these investigations. Another interesting perspective can be the use of generative models to produce the molecular fragments used as genes by genetic algorithms.

Most works discussed here only consider single-objective optimization problems or employ some sort of weighted sum approach to condense different optimization goals into one objective. Research on multi-objective GAs that make use of ML surrogate fitness functions seems to be largely unexplored. However, multi-objective evolutionary optimization in chemistry and materials science has many interesting applications with the common goal of efficiently sampling the Pareto front spanned by multiple properties. 61 Being able to employ surrogate fitness functions in multi-objective settings will also be crucial for enabling the ML accelerated study of these problems. A fundamental question therein is to define the way predictions are facilitated: using a single surrogate model for all objectives or using separate surrogate models, one for each objective. The comprehensive benchmarking of their respective performance in terms of prediction quality and computational cost will contribute to advancing the field, providing researchers with guidelines for choosing the most effective approach to their specific applications.

Another open challenge in this fast evolving field is the comprehensive and unbiased benchmarking of proposed methods across diverse domains. Many of the works reviewed here report promising performances of their proposed ML-augmented GA architectures but only partially tested against classical alternatives. For example, the discriminator ANNs for ensuring population diversity introduced by Nigam and co-workers 92 was only benchmarked against a standard GA architecture but not one employing classical techniques for maintaining diversity such as niching. 124,134 Similarly, ChemistGA 105 was only benchmarked against a very narrow set of classical GAs not taking into account a wider range of heuristic crossover operations and using suboptimal parameters. Future work should put emphasis on fair and informative benchmarking comparisons against relevant baselines. Especially when comparing the computational efficiencies of classical and ML-augmented GAs, care should be exercised to also take potential training and evaluation costs of ANNs into account. Furthermore problematic is the fact that some of the commonly employed benchmarks such as GuacaMol 98 and MOSES 128 have become outdated since modern EL methods are able to consistently obtain near-perfect scores on them 101,112,135 making it difficult to make substantiated statements about their respective performances. In this regard, Nigam and co-workers developed Tartarus, 32 a suite of realistic benchmarking sets entailing molecular design tasks from chemistry and materials science. In total, the study introduces four novel benchmarks across diverse domains that each include curated reference datasets. The authors encourage employing a resource-constrained training approach limiting the overall runtime and the number of proposed candidates in order to ensure the meaningful comparison of different methods.

In chemistry and materials science, an interesting application for Δ-ML is the prediction of corrections for energies and properties from semiempirical approximations 139–141 such as GFN2-xTB 142 to ab initio methods such as DFT. In evolutionary molecule design, fitness functions based on ab initio calculations are often times associated with prohibitively high computational costs, whereas semiempirical approximations are usually feasible. The use of Δ-ML in EL applications as a cheap yet accurate fitness function can potentially lead to better convergence properties and increase the quality of the solutions evolved.

Finally, the complex nature of such synergistic architectures requires users to have extensive knowledge of evolutionary and machine learning, rendering them difficult to use by non-experts. Efforts should go into the development of general frameworks that make these methods more easily accessible by a larger community, in order to enable their application to interesting problems within the fields of chemistry and materials science. For this, a culture of open code and data is crucial in which support for command line usage and comprehensive documentation facilitates the use and adaptation of existing methods. Furthermore, promoting avid exchange between method developers and users, as well as between the theoretical and experimental communities, will help to increase the scientific impact of these methods.

Data availability

Author contributions, conflicts of interest, acknowledgements.

• H. Chen, O. Engkvist, Y. Wang, M. Olivecrona and T. Blaschke, The Rise of Deep Learning in Drug Discovery, Drug Discovery Today , 2018, 23 , 1241–1250  CrossRef   PubMed .
• J. Vamathevan, D. Clark, P. Czodrowski, I. Dunham, E. Ferran, G. Lee, B. Li, A. Madabhushi, P. Shah, M. Spitzer and S. Zhao, Applications of machine learning in drug discovery and development, Nat. Rev. Drug Discovery , 2019, 18 , 463–477  CrossRef   PubMed .
• H. Altae-Tran, B. Ramsundar, A. S. Pappu and V. Pande, Low Data Drug Discovery with One-Shot Learning, ACS Cent. Sci. , 2017, 3 , 283–293  CrossRef   PubMed .
• J. S. Smith, O. Isayev and A. E. Roitberg, ANI-1, A Data Set of 20 Million Calculated Off-Equilibrium Conformations for Organic Molecules, Sci. Data , 2017, 4 , 170193  CrossRef   PubMed .
• J. R. Kitchin, Machine Learning in Catalysis, Nat. Catal. , 2018, 1 , 230–232  CrossRef .
• G. d. P. Gomes, R. Pollice and A. Aspuru-Guzik, Navigating through the Maze of Homogeneous Catalyst Design with Machine Learning, Trends Chem. , 2021, 3 , 96–110  CrossRef .
• B. Meyer, B. Sawatlon, S. Heinen, O. A. von Lilienfeld and C. Corminboeuf, Machine learning meets volcano plots: computational discovery of cross-coupling catalysts, Chem. Sci. , 2018, 9 , 7069–7077  RSC .
• S. Gallarati, R. Fabregat, R. Laplaza, S. Bhattacharjee, M. D. Wodrich and C. Corminboeuf, Reaction-based machine learning representations for predicting the enantioselectivity of organocatalysts, Chem. Sci. , 2021, 12 , 6879–6889  RSC .
• M. Cordova, M. D. Wodrich, B. Meyer, B. Sawatlon and C. Corminboeuf, Data-Driven Advancement of Homogeneous Nickel Catalyst Activity for Aryl Ether Cleavage, ACS Catal. , 2020, 10 , 7021–7031  CrossRef   CAS .
• M. Foscato and V. R. Jensen, Automated in Silico Design of Homogeneous Catalysts, ACS Catal. , 2020, 10 , 2354–2377  CrossRef   CAS .
• S.-H. Shin, S.-H. Yun and S.-H. Moon, A review of current developments in non-aqueous redox flow batteries: characterization of their membranes for design perspective, RSC Adv. , 2013, 3 , 9095–9116  RSC .
• M. Park, J. Ryu, W. Wang and J. Cho, Material design and engineering of next-generation flow-battery technologies, Nat. Rev. Mater. , 2016, 2 , 1–18  CrossRef .
• R. P. Carvalho, C. F. Marchiori, D. Brandell and C. M. Araujo, Artificial intelligence driven in-silico discovery of novel organic lithium-ion battery cathodes, Energy Storage Mater. , 2022, 44 , 313–325  CrossRef .
• D. M. Anstine and O. Isayev, Generative Models as an Emerging Paradigm in the Chemical Sciences, J. Am. Chem. Soc. , 2023, 145 , 8736–8750  CrossRef   PubMed .
• G. Jones, et al. , Genetic and evolutionary algorithms, Encyclopedia of Computational Chemistry , 1998, 2 , 40  Search PubMed .
• V. Venkatasubramanian, K. Chan and J. M. Caruthers, Computer-aided molecular design using genetic algorithms, Comput. Chem. Eng. , 1994, 18 , 833–844  CrossRef .
• D. T. Jones, De novo protein design using pairwise potentials and a genetic algorithm, Protein Sci. , 1994, 3 , 567–574  CrossRef   PubMed .
• V. Venkatasubramanian, K. Chan and J. M. Caruthers, Genetic algorithmic approach for computer-aided molecular design , ACS Publications, 1995  Search PubMed .
• E. J. Bjerrum and R. Threlfall, Molecular generation with recurrent neural networks (RNNs), arXiv , 2017, preprint, arXiv:1705.04612,  DOI: 10.48550/arXiv.1705.04612 .
• A. Gupta, A. T. Müller, B. J. Huisman, J. A. Fuchs, P. Schneider and G. Schneider, Generative recurrent networks for de novo drug design, Mol. Inf. , 2018, 37 , 1700111  CrossRef   PubMed .
• F. Grisoni, M. Moret, R. Lingwood and G. Schneider, Bidirectional molecule generation with recurrent neural networks, J. Chem. Inf. Model. , 2020, 60 , 1175–1183  CrossRef   PubMed .
• O. Dollar, N. Joshi, D. A. Beck and J. Pfaendtner, Attention-based generative models for de novo molecular design, Chem. Sci. , 2021, 12 , 8362–8372  RSC .
• Q. Liu, M. Allamanis, M. Brockschmidt and A. Gaunt, Constrained graph variational autoencoders for molecule design, Advances in Neural Information Processing Systems , 2018, 31 , 7795–7804  Search PubMed .
• W. Jin, R. Barzilay and T. Jaakkola, Junction tree variational autoencoder for molecular graph generation, in International Conference on Machine Learning , 2018, pp. 2323–2332  Search PubMed .
• V. Garcia Satorras, E. Hoogeboom, F. Fuchs, I. Posner and M. Welling, E(n) equivariant normalizing flows, Advances in Neural Information Processing Systems , 2021, 34 , 4181–4192  Search PubMed .
• C. Zang and F. Wang, Moflow: an invertible flow model for generating molecular graphs, in Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining , 2020, pp. 617–626  Search PubMed .
• M. Kuznetsov and D. Polykovskiy, MolGrow: a graph normalizing flow for hierarchical molecular generation, in Proceedings of the AAAI Conference on Artificial Intelligence , 2021, pp. 8226–8234  Search PubMed .
• A. Schneuing, Y. Du, C. Harris, A. Jamasb, I. Igashov, W. Du, T. Blundell, P. Lió, C. Gomes and M. Welling, et al. , Structure-based drug design with equivariant diffusion models, arXiv , 2022, preprint, arXiv:2210.13695,  DOI: 10.48550/arXiv.2210.13695 .
• L. Huang, H. Zhang, T. Xu and K.-C. Wong, Mdm: molecular diffusion model for 3D molecule generation, in Proceedings of the AAAI Conference on Artificial Intelligence , 2023, pp. 5105–5112  Search PubMed .
• E. Hoogeboom, V. G. Satorras, C. Vignac and M. Welling, Equivariant diffusion for molecule generation in 3D, in International conference on machine learning , 2022, pp. 8867–8887  Search PubMed .
• W. Gao and C. W. Coley, The synthesizability of molecules proposed by generative models, J. Chem. Inf. Model. , 2020, 60 , 5714–5723  CrossRef   PubMed .
• A. Nigam, R. Pollice, G. Tom, K. Jorner, J. Willes, L. Thiede, A. Kundaje and A. Aspuru-Guzik, Tartarus: a benchmarking platform for realistic and practical inverse molecular design, Advances in Neural Information Processing Systems , 2023, 36 , 3263–3306  Search PubMed .
• M. Blaschke and F. Pauly, Designing mechanosensitive molecules from molecular building blocks: a genetic algorithm-based approach, J. Chem. Phys. , 2023, 159 , 024126  CrossRef   PubMed .
• A. Nigam, R. Pollice, P. Friederich and A. Aspuru-Guzik, Artificial design of organic emitters via a genetic algorithm enhanced by a deep neural network, Chem. Sci. , 2024, 15 , 2618–2639  RSC .
• C. Kim, R. Batra, L. Chen, H. Tran and R. Ramprasad, Polymer design using genetic algorithm and machine learning, Comput. Mater. Sci. , 2021, 186 , 110067  CrossRef .
• U. Han, H. Kang, H. Lim, J. Han and H. Lee, Development and design optimization of novel polymer heat exchanger using the multi-objective genetic algorithm, Int. J. Heat Mass Transfer , 2019, 144 , 118589  CrossRef .
• K. Mitra, Genetic algorithms in polymeric material production, design, processing and other applications: a review, Int. Mater. Rev. , 2008, 53 , 275–297  CrossRef .
• J.-F. Zhu, Z.-K. Hao, Q. Liu, Y. Yin, C.-Q. Lu, Z.-Y. Huang and E.-H. Chen, Towards Exploring Large Molecular Space: An Efficient Chemical Genetic Algorithm, Journal of Computer Science and Technology , 2022, 37 , 1464–1477  CrossRef   PubMed .
• J. O. Spiegel and J. D. Durrant, AutoGrow4: an open-source genetic algorithm for de novo drug design and lead optimization, J. Cheminf. , 2020, 12 , 1–16  Search PubMed .
• J. Meyers, B. Fabian and N. Brown, De novo molecular design and generative models, Drug Discovery Today , 2021, 26 , 2707–2715  CrossRef   PubMed .
• G. Chalmers, Introducing ligand GA, a genetic algorithm molecular tool for automated protein inhibitor design, Sci. Rep. , 2022, 12 , 20877  CrossRef .
• M. Strandgaard, J. Seumer, B. Benediktsson, A. Bhowmik, T. Vegge and J. H. Jensen, Genetic algorithm-based re-optimization of the Schrock catalyst for dinitrogen fixation, ChemRxiv , 2023, preprint,  DOI: 10.26434/chemrxiv-2023-t73mw .
• M. H. Rasmussen, J. Seumer and J. H. Jensen, Toward De Novo Catalyst Discovery: Fast Identification of New Catalyst Candidates for Alcohol-Mediated Morita-Baylis-Hillman, Angew. Chem., Int. Ed. , 2023, e202310580  Search PubMed .
• J. Seumer, J. Kirschner Solberg Hansen, M. Brøndsted Nielsen and J. H. Jensen, Computational Evolution of New Catalysts for the Morita–Baylis–Hillman Reaction, Angew. Chem., Int. Ed. , 2023, 135 , e202218565  CrossRef .
• R. Laplaza, S. Gallarati and C. Corminboeuf, Genetic optimization of homogeneous catalysts, Chem.: Methods , 2022, 2 , e202100107  Search PubMed .
• S. Gallarati, P. van Gerwen, R. Laplaza, L. Brey, A. Makaveev and C. Corminboeuf, A genetic optimization strategy with generality in asymmetric organocatalysis as a primary target, Chem. Sci. , 2024, 15 , 3640–3660  RSC .
• J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence , MIT Press, 1992  Search PubMed .
• T. C. Le and D. A. Winkler, Discovery and optimization of materials using evolutionary approaches, Chem. Rev. , 2016, 116 , 6107–6132  CrossRef .
• D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning , Addison-Wesley Longman Publishing Co., Inc., USA, 1st edn, 1989  Search PubMed .
• M. Mitchell, An introduction to genetic algorithms , MIT Press, 1998  Search PubMed .
• D. Weininger, SMILES, a chemical language and information system. 1. Introduction to methodology and encoding rules, J. Chem. Inf. Comput. Sci. , 1988, 28 , 31–36  CrossRef .
• F. Dey and A. Caflisch, Fragment-based de novo ligand design by multiobjective evolutionary optimization, J. Chem. Inf. Model. , 2008, 48 , 679–690  CrossRef .
• C. A. Nicolaou, N. Brown and C. S. Pattichis, Molecular optimization using computational multi-objective methods, Curr. Opin. Drug Discovery Dev. , 2007, 10 , 316  Search PubMed .
• C. A. Nicolaou, J. Apostolakis and C. S. Pattichis, De novo drug design using multiobjective evolutionary graphs, J. Chem. Inf. Model. , 2009, 49 , 295–307  CrossRef .
• G. Lamanna, P. Delre, G. Marcou, M. Saviano, A. Varnek, D. Horvath and G. F. Mangiatordi, GENERA: a combined genetic/deep-learning algorithm for multiobjective target-oriented de novo design, J. Chem. Inf. Model. , 2023, 63 , 5107–5119  CrossRef   PubMed .
• R. V. Devi, S. S. Sathya and M. S. Coumar, Multi-objective genetic algorithm for De novo drug design (MoGADdrug), Curr. Comput.-Aided Drug Des. , 2021, 17 , 445–457  CrossRef .
• N. Brown, B. McKay, F. Gilardoni and J. Gasteiger, A graph-based genetic algorithm and its application to the multiobjective evolution of median molecules, J. Chem. Inf. Comput. Sci. , 2004, 44 , 1079–1087  CrossRef .
• D. Scott, S. Manos and P. V. Coveney, Design of electroceramic materials using artificial neural networks and multiobjective evolutionary algorithms, J. Chem. Inf. Model. , 2008, 48 , 262–273  CrossRef   PubMed .
• A. K. Sharma, C. Kulshreshtha and K.-S. Sohn, Discovery of New Green Phosphors and Minimization of Experimental Inconsistency Using a Multi-Objective Genetic Algorithm-Assisted Combinatorial Method, Adv. Funct. Mater. , 2009, 19 , 1705–1712  CrossRef .
• V. J. Gillet, W. Khatib, P. Willett, P. J. Fleming and D. V. Green, Combinatorial library design using a multiobjective genetic algorithm, J. Chem. Inf. Comput. Sci. , 2002, 42 , 375–385  CrossRef .
• H. Kneiding, A. Nova and D. Balcells, Directional multiobjective optimization of metal complexes at the billion-system scale, Nat. Comput. Sci. , 2024, 4 , 263–273  CrossRef .
• R. C. Glen and A. Payne, A genetic algorithm for the automated generation of molecules within constraints, J. Comput.-Aided Mol. Des. , 1995, 9 , 181–202  CrossRef   PubMed .
• J. Devillers, Designing molecules with specific properties from intercommunicating hybrid systems, J. Chem. Inf. Comput. Sci. , 1996, 36 , 1061–1066  CrossRef   PubMed .
• G. K.-M. Goh and J. A. Foster, Evolving molecules for drug design using genetic algorithms via molecular trees, in Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation , 2000, pp. 27–33  Search PubMed .
• S. C.-H. Pegg, J. J. Haresco and I. D. Kuntz, A genetic algorithm for structure-based de novo design, J. Comput.-Aided Mol. Des. , 2001, 15 , 911–933  CrossRef   PubMed .
• A. M. Virshup, J. Contreras-García, P. Wipf, W. Yang and D. N. Beratan, Stochastic voyages into uncharted chemical space produce a representative library of all possible drug-like compounds, J. Am. Chem. Soc. , 2013, 135 , 7296–7303  CrossRef   PubMed .
• J. H. Jensen, A graph-based genetic algorithm and generative model/Monte Carlo tree search for the exploration of chemical space, Chem. Sci. , 2019, 10 , 3567–3572  RSC .
• M. P. Lourenço, J. Hostaš, L. B. Herrera, P. Calaminici, A. M. Köster, A. Tchagang and D. R. Salahub, GAMaterial—a genetic-algorithm software for material design and discovery, J. Comput. Chem. , 2023, 44 , 814–823  CrossRef   PubMed .
• T. Yasuda, S. Ookawara, S. Yoshikawa and H. Matsumoto, Materials processing model-driven discovery framework for porous materials using machine learning and genetic algorithm: a focus on optimization of permeability and filtration efficiency, Chem. Eng. J. , 2023, 453 , 139540  CrossRef .
• B. L. Greenstein and G. R. Hutchison, Screening efficient tandem organic solar cells with machine learning and genetic algorithms, J. Phys. Chem. C , 2023, 127 , 6179–6191  CrossRef .
• T. R. Noviandy, A. Maulana, G. M. Idroes, N. B. Maulydia, M. Patwekar, R. Suhendra and R. Idroes, Integrating Genetic Algorithm and LightGBM for QSAR Modeling of Acetylcholinesterase Inhibitors in Alzheimer's Disease Drug Discovery, Malacca Pharmaceutics , 2023, 1 , 48–54  CrossRef .
• C. Plett and S. Grimme, Automated and efficient generation of general molecular aggregate structures, Angew. Chem., Int. Ed. , 2023, 135 , e202214477  CrossRef .
• Y. Jin, Surrogate-assisted evolutionary computation: recent advances and future challenges, Swarm and Evolutionary Computation , 2011, 1 , 61–70  CrossRef .
• J. P. Janet, L. Chan and H. J. Kulik, Accelerating chemical discovery with machine learning: simulated evolution of spin crossover complexes with an artificial neural network, J. Phys. Chem. Lett. , 2018, 9 , 1064–1071  CrossRef   PubMed .
• J. P. Janet and H. J. Kulik, Predicting electronic structure properties of transition metal complexes with neural networks, Chem. Sci. , 2017, 8 , 5137–5152  RSC .
• Y. Shu and B. G. Levine, Simulated evolution of fluorophores for light emitting diodes, J. Chem. Phys. , 2015, 142 , 104104  CrossRef   PubMed .
• A. Nigam, R. Pollice, M. F. Hurley, R. J. Hickman, M. Aldeghi, N. Yoshikawa, S. Chithrananda, V. A. Voelz and A. Aspuru-Guzik, Assigning confidence to molecular property prediction, Expert Opin. Drug Discovery , 2021, 16 , 1009–1023  CrossRef   PubMed .
• J. P. Janet, C. Duan, T. Yang, A. Nandy and H. J. Kulik, A quantitative uncertainty metric controls error in neural network-driven chemical discovery, Chem. Sci. , 2019, 10 , 7913–7922  RSC .
• R. M. Forrest and A. L. Greer, Evolutionary design of machine-learning-predicted bulk metallic glasses, Digital Discovery , 2023, 2 , 202–218  RSC .
• Y. Kwon, S. Kang, Y.-S. Choi and I. Kim, Evolutionary design of molecules based on deep learning and a genetic algorithm, Sci. Rep. , 2021, 11 , 17304  CrossRef   PubMed .
• D. Rogers and M. Hahn, Extended-connectivity fingerprints, J. Chem. Inf. Model. , 2010, 50 , 742–754  CrossRef   PubMed .
• Y. Zhang, et al. , Bayesian semi-supervised learning for uncertainty-calibrated prediction of molecular properties and active learning, Chem. Sci. , 2019, 10 , 8154–8163  RSC .
• K. Gubaev, E. V. Podryabinkin and A. V. Shapeev, Machine learning of molecular properties: locality and active learning, J. Chem. Phys. , 2018, 148 , 241727  CrossRef   PubMed .
• A. Nandy, C. Duan, C. Goffinet and H. J. Kulik, New strategies for direct methane-to-methanol conversion from active learning exploration of 16 million catalysts, JACS Au , 2022, 2 , 1200–1213  CrossRef   PubMed .
• F. Hase, L. M. Roch, C. Kreisbeck and A. Aspuru-Guzik, Phoenics: a Bayesian optimizer for chemistry, ACS Cent. Sci. , 2018, 4 , 1134–1145  CrossRef   PubMed .
• F. Häse, M. Aldeghi, R. J. Hickman, L. M. Roch and A. Aspuru-Guzik, Gryffin: an algorithm for Bayesian optimization of categorical variables informed by expert knowledge, Applied Physics Reviews , 2021, 8 , 031406  CrossRef .
• P. C. Jennings, S. Lysgaard, J. S. Hummelshøj, T. Vegge and T. Bligaard, Genetic algorithms for computational materials discovery accelerated by machine learning, npj Comput. Mater. , 2019, 5 , 46  CrossRef .
• O. Echt, K. Sattler and E. Recknagel, Magic numbers for sphere packings: experimental verification in free xenon clusters, Phys. Rev. Lett. , 1981, 47 , 1121  CrossRef .
• K. W. Jacobsen, J. Norskov and M. J. Puska, Interatomic interactions in the effective-medium theory, Phys. Rev. B: Condens. Matter Mater. Phys. , 1987, 35 , 7423  CrossRef   PubMed .
• D. M. Deaven and K.-M. Ho, Molecular geometry optimization with a genetic algorithm, Phys. Rev. Lett. , 1995, 75 , 288  CrossRef   PubMed .
• D. R. Jones, M. Schonlau and W. J. Welch, Efficient global optimization of expensive black-box functions, Journal of Global Optimization , 1998, 13 , 455–492  CrossRef .
• A. Nigam, P. Friederich, M. Krenn and A. Aspuru-Guzik, Augmenting genetic algorithms with deep neural networks for exploring the chemical space, arXiv , 2019, preprint, arXiv:1909.11655,  DOI: 10.48550/arXiv.1909.11655 .
• P. Ertl and A. Schuffenhauer, Estimation of synthetic accessibility score of drug-like molecules based on molecular complexity and fragment contributions, J. Cheminf. , 2009, 1 , 1–11  Search PubMed .
• M. Krenn, F. Häse, A. Nigam, P. Friederich and A. Aspuru-Guzik, Self-referencing embedded strings (SELFIES): a 100% robust molecular string representation, Machine Learning: Science and Technology , 2020, 1 , 045024  Search PubMed .
• A. Lo, R. Pollice, A. Nigam, A. D. White, M. Krenn and A. Aspuru-Guzik, Recent advances in the self-referencing embedded strings (SELFIES) library, Digital Discovery , 2023, 2 , 897–908  RSC .
• J. J. Irwin, T. Sterling, M. M. Mysinger, E. S. Bolstad and R. G. Coleman, ZINC: a free tool to discover chemistry for biology, J. Chem. Inf. Model. , 2012, 52 , 1757–1768  CrossRef .
• G. R. Bickerton, G. V. Paolini, J. Besnard, S. Muresan and A. L. Hopkins, Quantifying the chemical beauty of drugs, Nat. Chem. , 2012, 4 , 90–98  CrossRef   PubMed .
• N. Brown, M. Fiscato, M. H. Segler and A. C. Vaucher, GuacaMol: benchmarking models for de novo molecular design, J. Chem. Inf. Model. , 2019, 59 , 1096–1108  CrossRef   PubMed .
• A. Nigam, R. Pollice and A. Aspuru-Guzik, Parallel tempered genetic algorithm guided by deep neural networks for inverse molecular design, Digital Discovery , 2022, 1 , 390–404  RSC .
• A. Nigam, R. Pollice, M. Krenn, G. dos Passos Gomes and A. Aspuru-Guzik, Beyond generative models: superfast traversal, optimization, novelty, exploration and discovery (STONED) algorithm for molecules using SELFIES, Chem. Sci. , 2021, 12 , 7079–7090  RSC .
• S. Ahn, J. Kim, H. Lee and J. Shin, Guiding deep molecular optimization with genetic exploration, Advances in Neural Information Processing Systems , 2020, 33 , 12008–12021  Search PubMed .
• W. Jin, R. Barzilay and T. Jaakkola, Multi-objective molecule generation using interpretable substructures, in International conference on machine learning , 2020, pp. 4849–4859  Search PubMed .
• T. Cieplinski, T. Danel, S. Podlewska and S. Jastrzebski, We should at least be able to design molecules that dock well, arXiv , 2020, preprint, arXiv:2006.16955,  DOI: 10.48550/arXiv.2006.16955 .
• N. Kusanda, G. Tom, R. Hickman, A. Nigam, K. Jorner and A. Aspuru-Guzik, Assessing multi-objective optimization of molecules with genetic algorithms against relevant baselines, in AI for Accelerated Materials Design NeurIPS 2022 Workshop , 2022  Search PubMed .
• J. Wang, X. Wang, H. Sun, M. Wang, Y. Zeng, D. Jiang, Z. Wu, Z. Liu, B. Liao and X. Yao, et al. , ChemistGA: a chemical synthesizable accessible molecular generation algorithm for real-world drug discovery, J. Med. Chem. , 2022, 65 , 12482–12496  CrossRef   PubMed .
• P. Schwaller, T. Laino, T. Gaudin, P. Bolgar, C. A. Hunter, C. Bekas and A. A. Lee, Molecular transformer: a model for uncertainty-calibrated chemical reaction prediction, ACS Cent. Sci. , 2019, 5 , 1572–1583  CrossRef   PubMed .
• A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser and I. Polosukhin, Attention is all you need, Advances in Neural Information Processing Systems , 2017, 30 , 5998–6008  Search PubMed .
• Daylight Chemical Information Systems, I. SMARTS - A Language for Describing Molecular Patterns , 2019, http://www.daylight.com/dayhtml/doc/theory/theory.smarts.html, accessed 2023-11-10  Search PubMed .
• G. W. Bemis and M. A. Murcko, The properties of known drugs. 1. Molecular frameworks, J. Med. Chem. , 1996, 39 , 2887–2893  CrossRef   PubMed .
• J. Guo, V. Fialková, J. D. Arango, C. Margreitter, J. P. Janet, K. Papadopoulos, O. Engkvist and A. Patronov, Improving de novo molecular design with curriculum learning, Nature Machine Intelligence , 2022, 4 , 555–563  CrossRef .
• L. Van der Maaten and G. Hinton, Visualizing data using t-SNE, Journal of Machine Learning Research , 2008, 9 , 2579–2605  Search PubMed .
• Y. Kwon and J. Lee, MolFinder: an evolutionary algorithm for the global optimization of molecular properties and the extensive exploration of chemical space using SMILES, J. Cheminf. , 2021, 13 , 1–14  Search PubMed .
• Y. Chu, W. Heyndrickx, G. Occhipinti, V. R. Jensen and B. K. Alsberg, An evolutionary algorithm for de novo optimization of functional transition metal compounds, J. Am. Chem. Soc. , 2012, 134 , 8885–8895  CrossRef .
• V. Venkatraman, M. Foscato, V. R. Jensen and B. K. Alsberg, Evolutionary de novo design of phenothiazine derivatives for dye-sensitized solar cells, J. Mater. Chem. A , 2015, 3 , 9851–9860  RSC .
• K. Grantham, M. Mukaidaisi, H. K. Ooi, M. S. Ghaemi, A. Tchagang and Y. Li, Deep evolutionary learning for molecular design, IEEE Computational Intelligence Magazine , 2022, 17 , 14–28  Search PubMed .
• D. E. Rumelhart, G. E. Hinton and R. J. Williams, Learning internal representations by error propagation, Biometrika , 1985, 318–362  Search PubMed .
• D. P. Kingma, M. Welling, Auto-encoding variational bayes, arXiv , 2013, preprint arXiv:1312.6114,  DOI: 10.48550/arXiv:1312.6114 .
• D. J. Rezende, S. Mohamed and D. Wierstra, Stochastic backpropagation and approximate inference in deep generative models, in International Conference on Machine Learning , 2014, pp. 1278–1286  Search PubMed .
• M. Podda, D. Bacciu and A. Micheli, A deep generative model for fragment-based molecule generation, in International Conference on Artificial Intelligence and Statistics , 2020, pp. 2240–2250  Search PubMed .
• T. Mikolov, K. Chen, G. Corrado and J. Dean, Efficient estimation of word representations in vector space, arXiv , 2013, preprint, arXiv:1301.3781,  DOI: 10.48550/arXiv.1301.3781 .
• K. Cho, B. Van Merriënboer, D. Bahdanau and Y. Bengio, On the properties of neural machine translation: encoder-decoder approaches, arXiv , 2014, preprint arXiv:1409.1259,  DOI: 10.48550/arXiv:1409.1259 .
• T. Sousa, J. Correia, V. Pereira and M. Rocha, Combining multi-objective evolutionary algorithms with deep generative models towards focused molecular design, in Applications of Evolutionary Computation: 24th International Conference, EvoApplications 2021, Held as Part of EvoStar 2021, Virtual Event, April 7–9, 2021, Proceedings 24 , 2021, pp. 81–96  Search PubMed .
• R. Gómez-Bombarelli, J. N. Wei, D. Duvenaud, J. M. Hernández-Lobato, B. Sánchez-Lengeling, D. Sheberla, J. Aguilera-Iparraguirre, T. D. Hirzel, R. P. Adams and A. Aspuru-Guzik, Automatic chemical design using a data-driven continuous representation of molecules, ACS Cent. Sci. , 2018, 4 , 268–276  CrossRef .
• A. Konak, D. W. Coit and A. E. Smith, Multi-objective optimization using genetic algorithms: a tutorial, Reliability Engineering & System Safety , 2006, 91 , 992–1007  Search PubMed .
• X.-P. Wang and L. Cao, Genetic algorithm: theory, application and software implementation , Xi’an Jiaotong University Press, Xi’an, 2002, pp. 68–69  Search PubMed .
• F. Herrera, M. Lozano and A. M. Sánchez, A taxonomy for the crossover operator for real-coded genetic algorithms: an experimental study, International Journal of Intelligent Systems , 2003, 18 , 309–338  CrossRef .
• Y. Wang, S. H. Bryant, T. Cheng, J. Wang, A. Gindulyte, B. A. Shoemaker, P. A. Thiessen, S. He and J. Zhang, Pubchem bioassay: 2017 update, Nucleic Acids Res. , 2017, 45 , D955–D963  CrossRef   PubMed .
• D. Polykovskiy, A. Zhebrak, B. Sanchez-Lengeling, S. Golovanov, O. Tatanov, S. Belyaev, R. Kurbanov, A. Artamonov, V. Aladinskiy and M. Veselov, et al. , Molecular sets (MOSES): a benchmarking platform for molecular generation models, Front. Pharmacol , 2020, 11 , 565644  CrossRef   PubMed .
• S. Abouchekeir, A. Vu, M. Mukaidaisi, K. Grantham, A. Tchagang and Y. Li, Adversarial deep evolutionary learning for drug design, Biosystems , 2022, 222 , 104790  CrossRef   PubMed .
• A. Makhzani, J. Shlens, N. Jaitly, I. Goodfellow and B. Frey, Adversarial autoencoders, arXiv , 2015, preprint arXiv:1511.05644,  DOI: 10.48550/arXiv:1511.05644 .
• C. Blundell, J. Cornebise, K. Kavukcuoglu and D. Wierstra, Weight uncertainty in neural network, in International Conference on Machine Learning , 2015, pp. 1613–1622  Search PubMed .
• H. Overweg, A.-L. Popkes, A. Ercole, Y. Li, J. M. Hernández-Lobato, Y. Zaykov and C. Zhang, Interpretable outcome prediction with sparse Bayesian neural networks in intensive care, arXiv , 2019, preprint, arXiv:1905.02599,  DOI: 10.48550/arXiv.1905.02599 .
• S. Ryu, Y. Kwon and W. Y. Kim, A Bayesian graph convolutional network for reliable prediction of molecular properties with uncertainty quantification, Chem. Sci. , 2019, 10 , 8438–8446  RSC .
• J. Verhellen and J. Van den Abeele, Illuminating elite patches of chemical space, Chem. Sci. , 2020, 11 , 11485–11491  RSC .
• J. Leguy, T. Cauchy, M. Glavatskikh, B. Duval and B. Da Mota, EvoMol: a flexible and interpretable evolutionary algorithm for unbiased de novo molecular generation, J. Cheminf. , 2020, 12 , 1–19  Search PubMed .
• C. Yang and Y. Zhang, Delta Machine Learning to Improve Scoring-Ranking-Screening Performances of Protein–Ligand Scoring Functions, J. Chem. Inf. Model. , 2022, 62 , 2696–2712  CrossRef .
• M. Ruth, D. Gerbig and P. R. Schreiner, Machine learning of coupled cluster (T)-energy corrections via delta (Δ)-learning, J. Chem. Theory Comput. , 2022, 18 , 4846–4855  CrossRef .
• S. Maier, E. M. Collins and K. Raghavachari, Quantitative Prediction of Vertical Ionization Potentials from DFT via a Graph-Network-Based Delta Machine Learning Model Incorporating Electronic Descriptors, J. Phys. Chem. A , 2023, 127 , 3472–3483  CrossRef   PubMed .
• K. Atz, C. Isert, M. N. Böcker, J. Jiménez-Luna and G. Schneider, Open-source Δ-quantum machine learning for medicinal chemistry, Phys. Chem. Chem. Phys. , 2021, 10775–10783  Search PubMed .
• K. Atz, C. Isert, M. N. Böcker, J. Jiménez-Luna and G. Schneider, Δ-Quantum machine-learning for medicinal chemistry, Phys. Chem. Chem. Phys. , 2022, 24 , 10775–10783  RSC .
• Z. Qiao, A. S. Christensen, M. Welborn, F. R. Manby, A. Anandkumar and T. F. Miller III, Informing geometric deep learning with electronic interactions to accelerate quantum chemistry, Proc. Natl. Acad. Sci. U.S.A. , 2022, 119 , e2205221119  CrossRef   PubMed .
• C. Bannwarth, S. Ehlert and S. Grimme, GFN2-xTB—an accurate and broadly parametrized self-consistent tight-binding quantum chemical method with multipole electrostatics and density-dependent dispersion contributions, J. Chem. Theory Comput. , 2019, 15 , 1652–1671  CrossRef .