I have been considering a problem that was posed to myself a few weeks back. A programmer wants to create a program that attempts to replicate a painted image using a genetic algorithm. For example, a tree.
As he builds his genetic algorithm, each generation is given a score based on its closeness to the original image. As the program runs, subsequent generations slowly build up until you get an image which somewhat resembles the tree. However, this is a slow and tedious process, depending on the complexity of the algorithm designed (and I watched one slowly attempt to get a good tree), the length of time and the closeness to the original image that is desired.
Surely there would be a way to optimize the program a bit more!
What if, rather than allowing the whole population to interbreed, instead we allow only certain areas of a population to interbreed. Let’s pretend there were a series of different habitats, a desert, an ocean, a forest, and a tundra. Different genomes would be more adept at surviving for in each one. As the population adapts to its own environment it moves towards a more suitable form.
However, we would not want to completely segregate the parts. If we do this we decrease the genetic diversity of our total population and could end up missing our most optimal solution… also, once one part reaches an optimal solution, it stagnates and can’t move.
But what if we do allow movement between the four (what I shall call) competition pools? If we stumble upon a better solution for pool 1 in pool 4, we should include the facility to move that genome to pool 1. If we simply move it, then we would lose it from the original competition pool, so instead, we could do an a-sexual reproduction. The genome replicates itself into the other pool. If the genome is weaker than the other strong genomes in pool 1 it will die out, but if it survives it may bring about a more optimal solution…
In fact, segregating our population in this fashion increases the likelihood that we will end up with the most optimal solution.
Why? Well, when are have a single population, the survivors of that population begin to lose genetic diversity and merge towards what they deem is the most optimal solution that they can… but this might be a local minima.
(think of a wavey line, a dip could be a local minima, if our algorithm finds that minima, it may get stuck in it because it does not want to shift to the left or the right because the line’s level rises – assuming, of course, that that the lowest point is the most optimal).
If, however, there is another population which is attempting to optimize something else, it may chance upon a better minima for a different pool. This genome then is transfered to the other competition pool to see whether it in fact is better. If it survives then that pool will continue it’s optimization, if it dies then there was no harm done to our most optimal solution anyway.
In fact, one might suggest creating a small population around that newly found minima so as to allow a chance for the population to survive. - this is something I am considering quite closely, as to its the benefit, and how it would be done in order to allow it optimize itself before being put into full competition
Going back to our tree example, we could segregate the image into four parts. Each generation is a complete tree, however, in terms of construction of the tree, each genome may only be fighting against opponents in one quarter of the total genetic pool. Once Alleles start to disappear we can begin to see our tree take some obvious shape and characteristics. Once our optimals have been reached, we can create a new competition pool, taking a portion of genetic code from a genome in each pool, corresponding to the portion that was successful, merging the pools and allowing them to optimize into the best possible looking tree.
Some food for thought! Hopefully in the not-so far future I shall have the opportunity to use this technique on some actual AI (probably in a game of some descript) to see the benefit that it brings about.
But for now, I better continue working on my assignment – an AI with 4 dimensions of inputs, requiring two dimensions of optimized outputs in order to solve a problem. I have two giant sheets of paper which I am slowly colouring in as to my settings at each possibility.
- Owen
Probably not
Care to elaborate?