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

Question

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.

Thank you for your answers !

Answer 1

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) {
        organism.addTrait(Math.random());
        nextGenOrganismsArray[n] = new Organsim(organism + femaleOrganismArray[Math.random()];
    }
}

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

Answer 2

(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...

Answer 3

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?