An Introduction to Genetic Algorithms

Genetic algorithms are a program that seeks the best solution to the problem by simulating natural evolutionary processes such as "survival of the fittest", chromosome crossing and mutation. This article will briefly introduce the writing methods of genetic algorithms, discuss some important factors that need to be considered when writing your own algorithms, and provide some examples of practical applications of genetic algorithms.

Key Points

• Genetic algorithms simulate evolutionary processes such as "survival of the fittest", and use mechanisms such as selection, crossover and mutation to find the optimal solutions to complex problems.
• In genetic algorithms, the potential solution is expressed as chromosomes, and its applicability is evaluated by a fitness function that determines the probability of it being selected for reproduction.
• The crossover process combines features from a pair of parental solutions to create new offspring, while variation introduces random changes in the offspring, thus maintaining genetic diversity and potentially discovering new solutions.
• Because genetic algorithms can effectively explore large and complex solution spaces, they are very effective for problems that are difficult to solve in traditional search and optimization methods.
• The practical applications of genetic algorithms range from designing antennas with enhanced performance characteristics to optimizing web design, which illustrates their versatility and power in solving practical problems.

Cracking unknown information

The time is 2369 years, and humans have spread all over the sea of ​​stars. You are a young and intelligent doctor stationed in a busy deep-sky star base, bustling with interstellar travelers, merchants, and occasional outlaws. Shortly after you arrived, a shopkeeper at the base became interested in you. He claims he is just a simple tailor, but rumors say he is a secret agent working for a particularly evil regime.

You start having lunch together every week, discussing topics from politics to poetry. Even after a few months, you are still not sure whether he is expressing romantic feelings or taking secrets (you certainly don't have any secrets). Maybe both.

One day at lunch, he challenged you: "I have a message to tell you, dear doctor! I certainly can't tell you what it is. But I tell you, it's 12 characters long. These Characters can be any letter, space or punctuation. I will tell you how far your guess is from the actual answer. You are smart; do you think you can untie it? ”

You returned to the office in the medical cabin, still thinking about what he just said. Suddenly, a gene sequencing simulation experiment you had previously run on a nearby computer gave you an idea. You are not a password decryption expert, but maybe you can use your expertise in genetics to decipher his information!

Some theories

As I mentioned at the beginning, a genetic algorithm is a program that uses operations that drive evolution to search for solutions. After many iterations, the algorithm selects the best candidates (guess) from a set of possible solutions, recombines them, and checks which combinations make it closer to the solution. Poor candidates will be discarded.

In the above scene, any character in the secret message can be A-Z, space or basic punctuation. Suppose this gives us the following 32 characters "alphabet": ABCDEFGHIJKLMNOPQRSTUVWXYZ -.,!? This means there are 32¹² (approximately 1.15×10¹⁸) possible information , but only one of them is correct. It takes too long to check each possibility. Instead, the genetic algorithm will randomly select 12 characters and ask the tailor/spy to rate how close the result is to his information. This is more effective than brute force searches, because scores allow us to fine-tune future candidates. Feedback allows us to measure the fitness of each guess and hopefully avoid wasting time in a dead end.

Suppose we made three guesses: HOMLK?WSRZDJ, BGK KA!QTPXC and XELPOCV.XLF!. The first candidate scored 248.2, the second was 632.5, and the third was 219.5. The way scores are calculated depends on the situation, which we will discuss later, but now let's assume it is based on the deviation between the candidate and the target information: the perfect score is 0 (i.e. no deviation; the candidate and the target are the same), A higher score means greater deviation. The guesses with scores of 248.2 and 219.5 are closer to the content of the secret information than the guess with scores of 635.5.

The future guess is made through the combination of best attempts. There are many ways to combine candidates, but now we consider a simple crossover approach: each character in the new guess has a 50-50 probability copied from the first or second parent candidate. If we take the two guesses of HOMLK?WSRZDJ and XELPOCV.XLF!, then the first character of our descendant candidate has a 50% probability of H, a 50% probability of X, and the second character will be O or E , and so on. The offspring may be HELLO?W.RLD!.

Generate new candidates by crossover

However, if we only use the values ​​of the parent candidate, there may be a problem in multiple iterations: lack of diversity. If we have one candidate consists of all A and the other consists of all B, then any descendants generated by crossover will consist only of A and B. If the solution includes C, we would be unfortunate.

To mitigate this risk and maintain diversity while still narrowing the scope of solutions, we can introduce slight changes. Rather than doing a 50-50 segmentation directly, we allow a small probability to replace any value in the alphabet. Through this mutation, the offspring may become HELLO WORLD!.

Mutation keeps things fresh!

According to expectations, genetic algorithms borrow a large number of genetic science vocabulary. So, before we discuss further, let's refine some terms:

• Alleles: A member of the genetic alphabet. The definition of alleles depends on the algorithm. For example, 0 and 1 may be alleles of genetic algorithms used to process binary data, and algorithms used to process codes can use function pointers, etc. In our secret information scenario, alleles are letters, spaces, and various punctuation marks in the alphabet.
• Chromosome: a given allele sequence; a candidate solution; "guess". In our scenario, HOMLK?WSRZDJ, XELPOCV.XLF! and HELLO WORLD! are all chromosomes.
• Gene: Alleles at specific locations in chromosomes. For chromosome HOMLK?WSRZDJ, the first gene is H, the second gene is O, the third gene is M, and so on.
• Population: A collection of one or more candidate chromosomes proposed as a solution to the problem.
• Generations: Population during algorithm specific iterations. Candidates in one generation provide genes to produce the next generation of populations.
• Fitness: A measure of how close a candidate is to the desired solution. Adaptive chromosomes are more likely to pass their genes to future candidates, while less adaptive chromosomes are more likely to be discarded.
• Select: The process of selecting some candidates for reproduction (used to create new candidate chromosomes) and discarding other candidates. There are a variety of selection strategies that vary in tolerance for selecting weaker candidates.
• Reproduction: The process of combining the genes of one or more candidates to produce new candidates. The donor chromosome is called the father, and the produced chromosome is called the offspring.
• Mutation: Randomly introduced abnormal genes in offspring to prevent loss of genetic diversity in many generations.

Show me some code!

I suspect that given the advanced overview and the term list, you might be tempted to see some code right now. So let's look at some JavaScript code that solves our secret information problem. During the reading process, I invite you to think about which methods may be considered "boilerplate code" and which implementations are more closely related to the problem we are trying to solve:

// ... (Candidate class and GeneticAlgorithm class code as provided in the original text) ...

We first define a Candidate data object, just to pair chromosomes with their fitness scores. For convenience, a static sorting method is also attached; it comes in handy when we need to find or output the most suitable chromosome.

Next, we have a GeneticAlgorithm class that implements the genetic algorithm itself.

The constructor uses objects that solve various parameters required for simulation. It provides a way to specify genetic alphabet, target messages, and other parameters that define the constraints under which the simulation will run. In the example above, we expect a population of 100 candidates per generation. From this, only 40 chromosomes will be selected for reproduction. We have a 3% chance of introducing a mutation, and when it occurs, we will change up to two genes. The maxGenerations value is used as a protection measure; if we don't converge to a solution after 1 million generations, we will terminate the script anyway.

It is worth mentioning that the population, selection size and maximum number of ages provided when running the algorithm are quite small. More complex problems may require larger search space, which in turn increases the memory usage of the algorithm and the time it takes to run. However, it is highly recommended to use smaller variant parameters. If they get too big, we lose any benefit of breeding candidates based on fitness, and the simulation starts to become a random search.

Methods like randomInt(), init(), and run() may be considered boilerplate. But just because there is a boilerplate doesn't mean it won't have a practical impact on the simulation. For example, genetic algorithms use randomness heavily. While the built-in Math.random() function is suitable for our purposes, for other issues you need a more precise random generator. Crypto.getRandomValues() provides stronger cryptographic random values.

Performance is also a consideration. I strive to be clear and easy to understand in this article, but remember that the operation will be repeated. You may find yourself needing to micro-optimize the code in a loop, use more efficient memory data structures, and inline the code instead of separating it into functions/methods, all without regard to your implementation language.

The implementation of calcFitness(), select(), reproduce() and even stop() methods is specific to the problem we are trying to solve.

calcFitness() returns a value that measures the fitness of a chromosome based on certain expected criteria—in our case, it is how well it matches a secret message. Calculation of fitness is almost always situation-specific; our implementation calculates mean square error using the ASCII value of each gene, but other indicators may be more appropriate. For example, I can calculate the Hamming distance or Levinstein distance between two values, and even combine multiple measurements. Ultimately, it is important that the fitness function returns useful measurements based on the problem at hand, not just boolean "fit"/"not fit".

select() method demonstrates an elite selection strategy—only the most suitable candidates in the entire population are selected for breeding. As I mentioned earlier, there are other strategies, such as tournament selection, which selects the most appropriate candidate from the set of individual candidates in the population, and Boltzmann selection, which imposes increasingly larger and larger candidates on the selection of candidates pressure. The purpose of these different methods is to ensure that chromosomes have the opportunity to deliver genes that may prove beneficial later, even if it may not be immediately apparent. In-depth descriptions of these and other selection strategies, as well as example implementations, are easily found online.

Describing various selection strategies

There are many methods to combine genes. Our code creates offspring using uniform crossover where each gene has the same probability to choose from a parent. Other strategies may tend toward one parent's gene rather than another. Another popular strategy is k-point crossing, where chromosomes are divided at k points, resulting in 1 fragments that combine to produce offspring . The intersections can be fixed or randomly selected.

Description of k-point crossing strategy

We are not limited to two parent chromosomes; we can combine genes from three or more candidates, and can even be constructed based on a single candidate. Consider an algorithm that evolves images by drawing random polygons. In this case, our chromosomes are implemented as image data. In each generation, the most suitable image is selected from the population as the parent, and all child candidates are generated by drawing their own polygons onto the parent copy. Parent chromosomes/images are the unique variations/drawings of the parent.

Practical Application of Genetic Algorithm

Genetic algorithms can be used for both entertainment and profitability. Perhaps the two most popular examples of practical application of genetic algorithms are the X-band antennas evolved by BoxCar 2D and NASA.

BoxCar 2D is a simulation that uses genetic algorithms to evolve the best "cars" that can travel through simulated terrain. The car consists of eight random vectors, and connects the wheels to the random points. The project's website can be found on boxcar2d.com, which briefly introduces the algorithm on its About page and provides a ranking list showing some of the best designs. Unfortunately, the site uses Flash and may now be inaccessible to many people – in this case, various screen recordings can be found on YouTube if you are curious. You may also want to check out a similar (excellent) simulation written by Rafael Matsunaga using HTML5 technology, which can be found on rednuht.org/genetic_cars_2.

Cars evolved in BoxCar 2D, pictures from BoxCar 2D rankings

In 2006, NASA's Space Technology 5 mission tested various new technologies in space. One of these technologies is a new type of antenna designed using genetic algorithms. Designing new antennas can be a very expensive and time-consuming process. It requires special expertise and often setbacks occur when demand changes or prototypes fail to perform as expected. Evolved antenna creation time is shorter, with higher gain and lower power consumption. The full text of the paper discussing the design process is available for free online (automated antenna design using evolutionary algorithms). Genetic algorithms have also been used to optimize existing antenna designs for higher performance.

The best evolutionary antennas in their category, pictures are from automated antenna design papers

Genetic algorithms have even been used in web design! An advanced project by Elijah Mensch (optimizing website design by applying interactive genetic algorithms) uses them to optimize news article carousels by manipulating CSS rules and rating fitness using A/B tests.

The best layout for the first and ninth generations, the picture comes from the paper on optimized website design

Conclusion

So far, you should have a basic understanding of what genetic algorithms are and be familiar enough with their vocabulary to interpret any resources you may encounter in your own research. However, understanding theories and terms is only half the work. If you plan to write your own genetic algorithm, you must also understand your specific problem. Before you start, here are some important questions to ask yourself:

• How do I represent my problem as a chromosome? What is my valid allele?
• Do I know what the goal is? That is, what am I looking for? Is it a specific value or any solution with fitness exceeding a certain threshold?
• How do I quantify candidate fitness?
• How do I combine and mutate candidates to generate new candidate solutions?

I hope I also help you understand how programs draw inspiration from nature—not only in form, but also in process and function. Feel free to share your own thoughts in the forum.

Frequently Asked Questions about Genetic Algorithms

• What is a genetic algorithm (GA)? Genetic algorithms are a heuristic search and optimization technique inspired by the natural selection process. It is used to find approximate solutions to optimization and search problems through the principles of simulation evolution.
• How does genetic algorithms work? Genetic algorithms work by evolving populations of candidate solutions over successive generations. The process includes selection, crossover (recombination), mutation and evaluating individuals in the population, aiming to iteratively improve the quality of the solution.
• What types of problems are genetic algorithms suitable for? Genetic algorithms are widely used and can be applied to a variety of optimization and search problems, including but not limited to scheduling, routing, machine learning, and function optimization.
• How to select parameters for genetic algorithms? Parameters such as population size, variability and crossover rate depend on the characteristics of the specific problem and solution space. Experiment and tuning are common practices to find the best parameter values ​​for a given problem.
• What is the role of fitness function in genetic algorithms? The fitness function quantifies how individual solutions perform in a given problem. It guides the selection process and facilitates solutions that contribute positively to optimization goals.

The above is the detailed content of An Introduction to Genetic Algorithms. For more information, please follow other related articles on the PHP Chinese website!