Machine learning: Introduction to Genetic Algorithms

Translator: haoming

The original link

I like to start my machine learning classes with genetic algorithms (sometimes abbreviated to “”GA””). Genetic algorithm (ga) is probably the most impractical I contact algorithm, but I like to think it as a start, because the algorithm is very attractive, and by this algorithm can learn “” cost function” “or” “” “error function and the concept of global optimal and local optimal, these concepts are common in all machine learning algorithms and is very important.

Introduction to “Machine Learning in Javascript” this blog post provides a good Introduction and context for this blog and the others in this series.

Genetic algorithms are inspired by nature and evolution, which sounds pretty cool to me. Not surprisingly, artificial neural networks (“”NN””) are also modeled from biology, evolution is the best general-purpose learning algorithm we’ve ever seen, and the human brain is the best general-purpose problem solver we know of. Genetic and neural networks are two very important parts of biological survival, and also two rapidly developing fields of artificial intelligence and machine learning research. While I’d love to talk about the difference between the terms GA”” learning algorithm “” and NN”” problem solver “that I studied, for now we’re going to cut out the whole NNs and concentrate on GAs.

I used the very important term “generic” above. For any given computational problem, you can probably find an algorithm that solves it more efficiently than GA. But solving specific computational problems is not the focus of this exercise, nor of GAs. You use GA not because you have a complex problem, but because you have a complex problem with multiple problems. Or, you can use GA when you have a complex but unrelated set of parameters.

One application that COMES to mind is bipedal robot walking. Making a robot walk on two legs is very difficult. Hard-coding a walking program is almost certain to fail. Even if you succeed in making one robot walk, the next different robot may have a slightly different balance center, and the algorithm you enslave will no longer work. To avoid the inevitable heartbreak, you should use GA to “teach a robot to walk” rather than simply “teach a robot to walk”.

Let’s implement GA in JavaScript.

The problem

Build a genetic algorithm program in JavaScript that produces the text “Hello, World!” “.

Naturally, everything starts from “Hello, World!” “Start, so it’s appropriate to build a GA program that produces this phrase. Note that this is a very contrived question. At one point we even used the phrase “Hello, World!” “In the source code! If you know what you want, why write an algorithm in the first place? It seems silly. The answer is simple, it’s an exercise for learning. The next GA exercise (which will be based on PHP) will be less contrived, but we’ll start somewhere else.

Fundamentals of Genetic Algorithms

The basic approach to GAs is to generate a group of “candidate solutions” and then use some feedback to calculate how close the candidate solution is to the optimal solution. Candidate solutions that are far from optimal literally die and are never seen again. The near-optimal candidate solutions combine with each other and may vary slightly; This is an attempt to adjust the candidate from time to time and see if the candidate is closer or farther from the optimal solution.

These “candidate solutions” are called ** gene chromosomes **. (Note: I am using the term gene incorrectly. Genes are technically individual characters of candidate solutions, while the whole is called a chromosome. Semantics matter!)

Chromosomes pair up to produce offspring and then mutate. They either died due to the law of survival of the fittest or were allowed to produce offspring with more desirable traits adapted to natural selection.

This might be a strange way to think about solving “”Hello, World! “Problems, but hang in there. This example is not the only problem that GAs can solve.

chromosome

The chromosome is the model for the solution, and in our case, the chromosome itself is a string. Let’s assume that all chromosomes are 13 characters long (and “Hello, World! “The same length). Here are some possible chromosomes that could be candidate solutions to the problem:

• Gekmo+ xosmd!
• Gekln, worle””
• Fello, wosld!
• Gello, wprld!
• Hello, world!

It is clear that the last one is the correct (or globally optimal) chromosome. But how do we evaluate the optimality of chromosomes?

The cost function

The cost function (or error function, or relative fitness function) is a measure of chromosomal optimality. If we call it the adaptive function then we’re looking for the high value, and if we use the cost function then we’re looking for the low value.

In this case, we can define a cost function as follows:

For each character in the string, calculate the difference between the candidate character and the target character in the ASCII representation, then square the difference such that the “” cost “” is always positive.

For example, if we have an uppercase “”A””(ASCII 65) but it is assumed to be A uppercase “”C””(ASCII 67), then our cost on this character is 4(67-65 = 2, 2^2 = 4).

Again, the reason we use the difference squared is because we don’t have negative costs. You can just use absolute values if you want. Experiment with different methods – this is how you learn!

Using the above rules as a cost function, we can calculate the cost of the above 5 example chromosomes (in parentheses):

• Gekmo+ xosmd! (7)
• Gekln, worle”” (5)
• Fello, wosld! (5)
• Gello, wprld! (2)
• Hello, world! (0)

In this case, because the problem is simple and artificial, we know that we’re looking for a result that costs zero, and we end the algorithm. Sometimes that’s not the case. Sometimes you’re just looking for the lowest cost you can find, and you need to think of different ways to end the calculation. Other times, you’re looking for the highest “fit” of __ that you can find, and again you need to come up with some other criteria to terminate the operation.

The cost function is a very important aspect of GAs, because if you are smart enough, you can use it to reconcile _ completely unrelated parameters._ in our case, we just look at letters. But if you’re building a driving navigation app and you need to measure tolls versus traffic lights versus bad neighborhoods versus Bridges how do you do that? These are completely unrelated parameters, but you can reduce them to a neat cost function by applying different weights to each parameter.

Pairing and death

Pairing is the essence of life, and we use it a lot in GAs. Pairing is a magical moment when two loving chromosomes share each other. The technical term for pairing is “” crossover, “” but I’ll keep calling it “” pairing “” here, because pairing paints a more intuitive picture.

We haven’t talked about “population” in GAs yet (we’ll talk about it later) but for now I’m just saying that when you run a GA you don’t just see one chromosome at a time. Your entire population could be 20 or 100 or 5,000 at a time. Just like evolution, you might be inclined to have the best and strongest chromosomes in the population interbreed with each other in the hope that the offspring will be healthier than either parent.

Pairing strings, like in our “”Hello, World! “Is very simple. You can select two candidates (two strings, two chromosomes) and then select a dot in the middle of the string. If you want, this point could be orthocentric or random. Experiment! Select the center point (called the pivot point), and then create two new chromosomes by combining the front half of the first and the back half of the other.

Use these two strings as an example:

• Hello, wprld! (1)
• Iello, world! (1)

Cut them down the middle and interacted half to produce the following two new “children “:

• Iello, wprld! (2)
• Hello, world! (0)

As you can see, offspring include an illegitimate child that bears the worst characteristics of two parents, but also an angelic child that bears the best characteristics of two parents.

Pairing is a way of passing genes on to the next generation.

mutation

There is just one problem with pairing: breeding. If all you do is pair your candidates from one generation to the next, you get into a “local optimal” dilemma: one answer is good but not necessarily “global optimal “(you’re expecting the best).

(I was recently told that the paragraph above is a bit misleading. Some readers get the impression that the most important aspect of chromosome evolution is pairing, and that in practice a GA without pairing and mutation will achieve little. Mutations help us discover more optimal solutions from previously good solutions (many solutions to problems, like our Hello World example, can be divided into optimal sub-solutions, like “”Hello”” and “”World””), but only mutations can advance the search for solutions in new directions.

Imagine a world in which genes live as physical Settings. It is full of hills and all kinds of strange peaks and valleys. There is one of the lowest valleys in it, but there are many others — and though these valleys are lower than the land directly round them, they are still above sea level. Searching for a solution is like _ randomly _ placing a bunch of balls on a hill. You make the balls move, and they roll down the hill. Eventually, the balls will fall into valleys — but most will fall into random lowest valleys that are still much higher than the hills (locally optimal). Your job is to make sure that at least one of the balls falls at the lowest point on the map: global optimal. Because these balls start at random places, it’s hard to be globally optimal at the beginning, and it’s impossible to predict which balls will get stuck where. What you can do, however, is look at some random balls and kick them. A kick may or may not help – but the idea here is to shake the system to make sure it doesn’t get stuck in local optima for too long.

This is called a mutation. It’s a completely random process in which you target an unsuspecting chromosome and blast it with enough radiation to make one of the letters randomly change.

Here we use an example to illustrate. Let’s say we have these two chromosomes:

• Hfllp, worlb!
• Hfllp, worlb!

Again, a contrived example, but it happens. Your two chromosomes are the same. This means that their children, like their parents, will not progress. But if one of the 100 chromosomes has a random mutation of one character, chromosome #2 becomes “Ifllp, world!” “It’s just a matter of time. And then evolution will continue, because children will end up being different from their parents again. Mutation drives evolution forward.

It’s up to you to decide how and when. Again, do the research. The code I’ll show you later has a very high mutation rate (50%), but this is really just for show. You can make it a little bit lower, like 1%. My code makes unique _ a letter _ move _ an ASCII code _ but you can make your code a little more radical. Experiment, test, and learn. It’s the only way.

Chromosome: Summary

Chromosomes are the expression of candidate solutions to problems. They consist of expressing itself (in our case, a 13-character string), a cost or fitness function, the ability to pair (“” cross “”), and the ability to mutate.

I like to think of these things in OOP terms. The “chromosome” class therefore has the following properties:

Properties:

• The genetic code
• Cost value/adaptation value

Methods:

• pairing
• mutation
• Calculated fitness

We now look at how genes interact in the final part of the GA puzzle :” population “.

population

A population is a set of chromosomes. Populations generally remain the same size, but the average cost of a population generally evolves better over time.

You can choose your own population size. I chose 20 for the next program, but you can choose 10 or 100 or 10,000 if you want. They have advantages and disadvantages, but as I’ve said many times now: Do the experiment and learn it!

The population goes through “generations”. A typical generation might consist of these:

• Cost/fitness scores were calculated for each chromosome
• Order chromosomes by cost/fitness fraction
• Kill a certain number of the weakest members – the number of chromosomes you choose to die
• Match a certain number of strongest members – again, what do you choose to do
• Random mutation member
• Some kind of integrity testing — for example, how do you determine when the issue is considered “” resolved “”?

Start and finish

Initializing a population is easy. You just fill it with completely random chromosomes. In our case, the cost score for a completely random string is terrible. Our code starts with an average cost of 30,000. But that’s okay — that’s what evolution is for. That’s why we’re here.

Knowing when to stop species evolution is a bit tricky. Today’s example is very simple: the cost stops when you get 0. But it wasn’t always that way. Sometimes you don’t know the minimum available cost value. Or, if you are using adaptive values instead of cost values, you may not know the maximum possible adaptive values.

In those cases, you need to specify a completion guideline. It can be anything you want, but here’s a tip to get you started:

Stop the algorithm if the best score hasn’t changed for 1000 generations, then use it as the answer.

Criteria like this may mean that you don’t get global optimality, but there are many cases where you don’t need to get global optimality. Sometimes “close enough” really is good enough.

I will soon write another article on GAs(this time in PHP) with a slightly different problem, which will have a similar completion rule to the one above. It may be a little difficult to swallow the “close enough is good enough” argument right now, but I hope you’ll believe me once you see actual examples.

code

At last! I like OOP methods, but I also like rough and simple code, so I’m going to write this code as straightforward as possible even though it might be a little rough around the edges.

(Note that although I changed the “term” from “gene” to “chromosome” above, the following code still uses the incorrect “gene” term. This is a difference between semantics and pedants, but where can we avoid semantic pedants?)

var Gene = function(code) { if (code) this.code = code; this.cost = 9999; }; Gene.prototype.code = ''; Gene.prototype.random = function(length) { while (length--) { this.code += String.fromCharCode(Math.floor(Math.random()*255)); }};Copy the code

Simple. It’s just a class where the constructor takes a string and sets the cost, and there’s an auxiliary function to make a new random chromosome.

Gene.prototype.calcCost = function(compareTo) {  
        var total = 0;
        for(i = 0; i < this.code.length; i++) {
                total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i));
        }
        this.cost = total;
}; 
Copy the code

The cost function takes a “mock” string as an argument, finds their difference at the code point and squares it.

Gene.prototype.mate = function(gene) {  
        var pivot = Math.round(this.code.length / 2) - 1;

        var child1 = this.code.substr(0, pivot) + gene.code.substr(pivot);
        var child2 = gene.code.substr(0, pivot) + this.code.substr(pivot);

        return [new Gene(child1), new Gene(child2)];
}; 
Copy the code

The pairing function takes another chromosome as an argument, finds the center of the string, and returns an array of two new children.

Gene.prototype.mutate = function(chance) {  
        if (Math.random() > chance)
                return;

        var index = Math.floor(Math.random()*this.code.length);
        var upOrDown = Math.random() 
Copy the code

The mutant function takes a floating point number as an argument — representing the percentage chance that the chromosome will mutate. If the chromosome is going to mutate, then we randomly decide whether to add or subtract a code point from a randomly selected character code. I was so fast that the progress can’t write a proper String. The prototype. The replaceAt method, so I am here with a simple abbreviations.

var Population = function(goal, size) { this.members = []; this.goal = goal; this.generationNumber = 0; while (size--) { var gene = new Gene(); gene.random(this.goal.length); this.members.push(gene); }};Copy the code

The population-class constructor takes a target string and a population size as arguments, and populates the population with random chromosomes.

Population.prototype.sort = function() {  
        this.members.sort(function(a, b) {
                return a.cost - b.cost;
        });
} 
Copy the code

I define a Population. The prototype. Sort method as an auxiliary function to sort a cost value populations.

Population.prototype.generation = function() { for (var i = 0; i < this.members.length; i++) { this.members[i].calcCost(this.goal); } this.sort(); this.display(); var children = this.members[0].mate(this.members[1]); this.members.splice(this.members.length - 2, 2, children[0], children[1]); for (var i = 0; i < this.members.length; I++) {this. Members [I] mutate (0.5); this.members[i].calcCost(this.goal); if (this.members[i].code == this.goal) { this.sort(); this.display(); return true; } } this.generationNumber++; var scope = this; setTimeout(function() { scope.generation(); }, 20); };Copy the code

The fattest population method is the generation method. There’s no magic here. The display() function (not shown on the page) just renders the output to the page, and I set a temporary rest between generations so the system doesn’t explode.

Notice that in this case I only matched the two strongest chromosomes. Your approach doesn’t have to be this way.

window.onload = function() { var population = new Population(""Hello, world!" "20); population.generation(); };Copy the code

The code above turns the system on; see it in practice.

It’s a bit slow – but it’s not too hard to figure out where the inefficiencies are. Of course you can make it lightning fast if you’re smart enough. As always, I encourage you to fork it yourself and experiment.

Note that there is nothing above that cannot be done in _ other _ programming languages. But you might expect this, too, because this is, after all, “machine learning in all languages.”

Happy study! This series next blog is [ML in JS: k – on – neighbor] (burakkanber.com/blog/machin… “”Machine Learning in JS: k-nearest-neighbor Introduction””).

There is also a [based Algorithms Part 2] (burakkanber.com/blog/machin… “”Machine Learning: Genetic Algorithms in Javascript Part 2”), you should read it if you want to go deeper.