3

I have been going over genetic algorithms. My aim is to implement simple simulation where the player (uncontrolled by external human players) avoids obstacles and goes towards the rewards.

I understand that genetic algorithms fall into Evolutionary Algorithms, which is great for this scenario because I don't have to provide training data then. It will learn by itself.

These introductions I have been reading talk about populations which are encoded as binary strings (I think), I don't see how populations and refining populations to produce new generations has anything to do with this problem domain.

Can someone please explain

1
  • Adeeb, it's already been pointed out that they do not fall into reinforcement learning. Genetic algorithms fall into the category of evolutionary algorithms. If you wanted something that used "reinforcement", look into neural networks. Sep 25, 2013 at 20:32

2 Answers 2

4

Put simply, you will use your genetic algorithm to generate the rules determining the AI's behaviour. Exactly how these rules are encoded and interpreted depends on what you want to achieve.

Maybe you'd like the genetic algorithm to generate weights for the connections of a neural network that in turn handles the player's behaviour. In that case you will encode the weights as a binary string.

Another example would be to interpret the binary string as a decision tree

When you have your representation coded, your genetic algorithm will generate individuals with different genes or binary strings. These individuals will then be assigned a fitness value according to how well it performs and the GA will, hopefully, over time find a good AI (according to your fitness function and representation).

EDIT: Say you have the network below with three connections and you've chose to encode each weight with four bits. Then your binary string could, in it's simplest encoding, be these 3 weights concatenated.

enter image description here

4
  • Since the encoding depends on what I want to achieve, is there an algorithm or a straight forward way of choosing the encoding? All I want is to make the player collect the rewards, I have already used a neural network for avoiding collisions with obstacles.
    – Adeeb
    Sep 25, 2013 at 20:49
  • Then you would encode information about your neural network such as nodes, layers and weights in a binary string. Perhaps you could start with a static topology and only encode the connection weights in the binary string.
    – PureW
    Sep 25, 2013 at 21:14
  • I get what you're saying now, my ANN has 3 layers so can I just add the other weights?
    – Adeeb
    Sep 25, 2013 at 21:56
  • Yes, you encode whatever you want to optimize in the binary string. In your case you can add all the network's weights together into the binary string. Just remember that longer strings will require more time to optimize for the GA.
    – PureW
    Sep 25, 2013 at 22:07
0

Check out Dan Ashlock's Tartarus papers.

Not the answer you're looking for? Browse other questions tagged or ask your own question.