# How to do a genetic algorithm's chromosome which controls movements

First I would like to inform you that I'm french and 15 so my english is not very good.

I've read some articles about genetic algorithms (GA) and since I discovered the HTML5's canvas element, I can create an AI with animations, so I've created two little experiments to enjoy seeing robots moving on their own but first I'll present you the second one because it's easier :

The aim of this experiment for the white circles is to touch the red square and instead of using coordinate calculations, like I said, I would like to create an autonomous algorithm which evolves in the time.

I give to the circles their relative coordinates to the red square like so they know exactly where they are and their speed that they will be able to change.

So to do it I need a solution to create a chromosome that contains moving informations but since the x and y positions are randomly assigned to circles and the square, if a member of the population has the good solution, it's only for this particular configuration.

I'm searching how to make them know that if the x coordinate is inferior to 0, they have to go left without creating a function like this if(firstGeneInfo == 2){bot[i].x += redSquare.x - bot[i].x;}.

This is a screenshot of the canvas :

And the jsfiddle link but movements are random for the moment.

http://jsfiddle.net/KLn8r/1/

The other experiment is a sort of "survival game" where the red square has to last, first I created it as a human-AI experience but I prefer to do an AI vs AI game, and so implement a genetic algorithm but in this case it is a lot more complicated because they are multiple enemies, I thought that with informations like enemies's coordinates and speed once again, the red square would developp kind of a strategy. The enemies are controlled by an algorithm and there is no need to do a GA for them.

A screenshot :

and the jsfiddle link : http://jsfiddle.net/f6ghk/

If you've read all this, I already thank you ! I'm not asking for the full working code but just the principle of a chromosome that works in theses cases.

I hope that my english wasn't to horrible to read and that for my problems I don't need a simulated neural network because it seems a bit complicated to me.

• I haven't implemented something like this yet, but I've given it some thought before, and I think to do this well enough you do indeed need neural networks, and the chromosomes would encode the connections/weights between the different neurons. Actually neural networks are not that complicated, google some tutorials and try to power through it, it's worth it. They're quite a nice application of something that can be trained using evolutionary algorithms as well. – TravisG Mar 7 '14 at 3:10
• Is there someone who knows a good class to learn neural networks's basics ? – nathsou Mar 7 '14 at 13:19
• Take a look at this page: ai-junkie.com/ann/evolved/nnt2.html – TravisG Mar 7 '14 at 17:39
• Great ! This tutorial looks very comprehensible. – nathsou Mar 8 '14 at 1:48

How it works in real life is that it is completely random. If the mutation is good, the organism can survive and reproduce. If the mutation is bad, the organism and it's genome will usually die out.

With that in mind, with every generation, add random traits to the offspring and if it is beneficial, allow it to pass it's genes to the next generation with a random chance of mutation.

If you are using sexual reputation, select 2 random ones and randomly select different traits from each other, but give the more effective organisms a higher chance at reproducing.

This would look something like this in the code:
(done in pseudo code)

function onNextGen() {
for (organism in organismArray) {
organism.giveTrait(Math.random());
}
}
}


or for sexual reproduction:

function onNextGen() {
for (organism in maleOrganismArray) {
nextGenOrganismsArray[n] = new Organsim(organism + femaleOrganismArray[Math.random()];
}
}


This is a poor example but I hope it displays my point.

(First, what you're doing is awesome! I love GA.)

I haven't read every line of your code, yet (I intend to), but ain't what you're looking for the fitness function? I mean, it's the fitness function that will tell how valuable are de chromosomes so you can cross then in the next generation... Anyway, really not sure. Hope to understand you problem better soon.

Perhaps Jeff Heaton implementation might help. His stuff is awesome! There is bunch of them at: JavaScript Machine Learning and Neural Networks with Encog

Keep it up and good luck...

• Hi jaywalking101, you will see that my algorithm is yet very stupid but I appreciate that you enjoy it ! Indeed, I plan to do a GA to solve my little problem, I first code some little things to learn it and then I will applicate it to the JSfiddle. Thank you for the link with a very interesting class just like on ai-junkie.com but this time with direct-javascript application. If you want, we can keep in touch I like the idea of speaking with a Bresilian and it can improve my AI knowlegde and my english. – nathsou Apr 24 '14 at 16:02
• Hey, @nathsou, That would be great! I am also using canvas a lot right now and soon I will need to try to do some behavior implementation (like flocking and hunting). And I am sure that between my portuguese and your french that we would practice a lot of english! =P So, how shall we "meet"? =) – slacktracer Apr 25 '14 at 19:07
• I just added you on Google + and maybe have you Skype ? – nathsou Apr 25 '14 at 22:57

I'm not really seeing a question. What is your exact goal? To find the shortest path?

Genetic Algorithm's require you to have fitness function. To define one and to have it be meaningful you need 2 things. 1 a set of possible options and a fitness function that analyzes them. This is often done with a randomizer that randoms a certain option and each time you call the fitness function you attribute a positive or negative bias to specific actions. If done correctly you get a near optimal sequence of data / events. The problem you are have is what is known as the traveling salesman problem. It has no real 'best' solution, but good algorithms like A* exist for solving it.

Without a more refined question it is difficult to say anything because you are showing us stuff without a real concrete question. Do you simply want to try to tackle the traveling salesman problem with a genetic algorithm? Are you placing any line of sight limitations on your actor?

• What he is having isn't called tsp, cause that is a specific solvable problem that afawk requires an algorithm with large complexity n^2*2^n. Plus A* does not solve it. A* helps you get from point A to point B, it does not take into consideration the time it will take to travel to all the points. – AturSams May 11 '14 at 5:20