How do I make my genetic algorithm more efficient?

1
votes

I've created a game (basically an Agar.io clone), where a human player is placed against AI controlled bots powered by a genetic algorithm and neural networks.

The problem is that I think that my algorithm isn't efficient. I have 10 bots ranked by their fitness function, which is time survived. Their gene consists of real numbers between -1 and 1.

From lowest to highest fitness, I take n bots up to 5 bots and take the current weight value and add it by a Gaussian number multiplied by (10^-n). I had trouble performing crossover with floating point numbers, thus I only did mutation like this.

Obviously, my AI isn't very intelligent.

How could I improve my algorithm?

Here is where most of the source code resides if needed: https://github.com/jadenyjw/evo/blob/master/core/src/com/evo/game/stages/GameStage.java

3
artificial-intelligencegenetic-algorithmevolutionary-algorithm
This is off topic for SO. Maybe try codereview.stackexchange.com - httpNick
@httpNick Thanks will try that out. - Jaden Wang
I'm voting to close this question as off-topic because it is asking for peer review of working code (which is not included in the post). It may be more suited for Code Review, but they're going to expect the code in the post itself as we would here. Code in an off-site location has zero value to future readers if that off-site location is unavailable for some reason (off-line, moved, deleted, etc). - Ken White
My code should be fine, I just want to know a smarter way to implement this algorithm. Maybe what I'm asking for can be considered pseudocode. Then I can actually translate it to real code. - Jaden Wang
@KenWhite, I think the question is valid and subject to an easy improvement. I think the OP should post a piece of (pseudo)code that implements your genetic crossover function, and then we car reason over it. I am assuming this is single a narrow part that you Jaden want answers on. - kkm

3 Answers

0
votes

Agar.io is comparable to other Artificial Intelligence Competitions like Mario AI. The problem is, that many different problemsolving techniques are allowed and that neuroevolution, genetic programming and maschine learning are very easy to implement for beginners. Unfortunately it is not possible to scale these bots up to be more intelligent than a certain level. Thats because genetic programming itself is the wrong way to go. Better solution is Scripting AI which is not only scalable up to every level of intelligence but also uses less cpu-power as so called "evolutional AI".

Lets take a deeper look into the sourcecode. According to the import statements at the beginning the "Encog Framework" was used. That is a prominent Machine Learning Library which supports GPU Computing and is a similar to pybrain. Even with best parametertuning Encog will never be able to generate from scratch an agent which is ready to win against human player. But it is good way to proove that these kind optimizing algorithm are not suited for real problems.

0
votes

Having vectors of real numbers you could try Differential Evolution.

As GA it's part of the evolutionary algorithms family. DE performs well exploring the high value areas of the solution space effectively (but it has the usual problem of getting stuck in local minima).

Contrary to your approach DE exchanges information among solutions and so it could perform better.

Last but not least, changing from your approach to DE is relatively simple: you only have to code the specific mutation/crossover operator.

0
votes

You can perform a cross between two bots, conserving the values of the genes, by randomly selecting the half of the genes of a bot, and the opposite half of the genes of another bot.

For example, with n genes:

For i from 0 to n-1
  r = random interger number
  If(r modulo 2 == 0)
    gene[i] of new bot = gene[i] of bot number 1
  Else
    gene[i] of new bot = gene[i] of bot number 2
  EndIf
EndFor

You also can "cross" the genes themselves by computing the middle value of the two real numbers:

gene[i] of new bot = ((gene[i] of bot 1) + (gene[i] of bot 2)) / 2

The population may be too small, maybe you'll get better results with a population of 100 bots or more, instead of 10. But maybe your game don't allow that, and so you'll probably need to run the genetic algorithm for more generations of bots.

About mutations, you are doing small mutations, you can introduce a second mutation type, that create a totally new gene with a totally new random real number, that is not influenced by the previous value of the gene, so it is a huge mutation, controlled by an independent mutation rate.

Some algorithms have a variable mutation rate, controlled by a gene that also can mutate. So you can test it by introducing 2 genes that control the mutation rate for small and huge mutations. But I don't know if it can have efficient results on small populations.

About the neural network, you can test others layouts, because may be it has too much, or hasn't enough neurons, to efficiently control the bots. It is the same problem about the number of hidden layers.