http://burakkanber.com/blog/machine-learning-genetic-algorithms-part-1-javascript/
Interesting article above. Stired an idead that has been bubbling around for ages.
The issue I see is that the chromosome of the GA and the fitness function are seperated. The choromosome is mutated, mated and selected, while the fitness function is static. This treats the "chromosome" simply as "data" while the fitness function, mutation function, mating function and selection function act as immutable "code".
I feel like I have been in this conversation before, but I want some way to load all the functions into the chromosome and allow both the "code" and the "data" to mutate and be mixed up at the same time.
For this to happen, there has to be a simple generic machine to parse the data in the chromosome and interpret some of it as "payload", some as fitness function, some as mating function, some as selection function and some as mutation function.
Chances are that this model will cause catastrophic failure in most scenarios... but its a fun idea.
By allowing all these functions to mutate and become part of the GA, it should make for a more flexible system, that does not encode any of the assumptions of the designers into it. It should allow the system to evolve without any unknown constraints.
What will this need?
A set of abstract mechanisms to iplement the various functions (Fitness, mutation, selection, mating) at a population level along with a chromosome of "data".
The simplest place to start is halfway.... Start with a library of fitness functions and use a simple flag in the data chromosome to pick which one to use on the GA. (Theoretically, this will pick the fitness function which gives the highest "score" for different families of GA's.
Ditto for mutation, selection and mating functions... just sit around and come up with every weird and amusing function possible, then let evoluation selecte the winners.
Showing posts with label Genetic Algorithm. Show all posts
Showing posts with label Genetic Algorithm. Show all posts
Monday, October 29, 2012
Tuesday, November 22, 2011
Genetic Algorithms for non-intuitive solutions
Thinking about evolutionary algorithms and "superstreets" which to me falls into the category of a non-intuitive optimisation. (In that some actors individually loose while the majority win giving an aggregate win for the system)
This, in my mind is a revolutionary design that would not be developed if the rules were to make the solution "fair" for all the actors in the scenario. You could probably get a GA to produce it if you had it in mind before you started and tweaked the algo until it was able to do it.
Anyway, my thought was how to give an evolutionary algorithm the ability to not only generate these kinds of non-intuitive solutions but to identify partial solutions that may be worth preserving in the population even though they are not an optimal solution... much like the problem of making a NN explain itself, this is a case of having some "wildcard" model in the population that maintains diversity. Kind of like the "Island" effect in biology. Diversity is maintained by seperating the population into small groups that interbreed, with only a little "bleed" around the edges of the groups which allows cross-over of locally optimised mutations.
Another possible strategy is to "lock" mutant sections of the DNA that have high impacts on the overall solution, even if the overall solution may be sub-optimal. I think this is a flawed strategy because each strategy needs to be evaluated as a whole...
That said, I think an evaluation matrix is better than a summative score, as this allows individual mutations to spike up... which may be the point to move that part of the population to an island and see what develops.
The question is how to evaluate the solution as in parts... and is this just a different way to arrive at the same flawed solution as above.... trying to "lock" mutations and preserve them artificially.. which defeats the purpose of allowing evolution to act on the population. (Which is all fun as long as its preserving the useful mutations not just plateauing)
Need to run some sims to see what the effect of various strategies might be...
This, in my mind is a revolutionary design that would not be developed if the rules were to make the solution "fair" for all the actors in the scenario. You could probably get a GA to produce it if you had it in mind before you started and tweaked the algo until it was able to do it.
Anyway, my thought was how to give an evolutionary algorithm the ability to not only generate these kinds of non-intuitive solutions but to identify partial solutions that may be worth preserving in the population even though they are not an optimal solution... much like the problem of making a NN explain itself, this is a case of having some "wildcard" model in the population that maintains diversity. Kind of like the "Island" effect in biology. Diversity is maintained by seperating the population into small groups that interbreed, with only a little "bleed" around the edges of the groups which allows cross-over of locally optimised mutations.
Another possible strategy is to "lock" mutant sections of the DNA that have high impacts on the overall solution, even if the overall solution may be sub-optimal. I think this is a flawed strategy because each strategy needs to be evaluated as a whole...
That said, I think an evaluation matrix is better than a summative score, as this allows individual mutations to spike up... which may be the point to move that part of the population to an island and see what develops.
The question is how to evaluate the solution as in parts... and is this just a different way to arrive at the same flawed solution as above.... trying to "lock" mutations and preserve them artificially.. which defeats the purpose of allowing evolution to act on the population. (Which is all fun as long as its preserving the useful mutations not just plateauing)
Need to run some sims to see what the effect of various strategies might be...
Thursday, October 6, 2011
Evolutionary vs Revolutionary Algorithms
http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/
This is a nice little post on building a simple evolutionary algorithm. I have not thought of applying it to string mutation but its a nice little application.
A couple of thoughts occur to me.
The first being that "evolution" is strongly encoded in the mutation algorithm which single-steps one of the characters in the string a single position ( plus or minus). Which produces a slightly random systematic search strategy. A "revolutionary" approach would be to randomly replace a character in the string with another character.
If this approach was taken, then it would introduce much greater possible degree of individual mutation. This is detrimental for a population of one but would be much more valuable if there is a larger population using cross-over and cull based on fitness. Beneficial mutations would be quickly reinforced. In a population of one, there is no chance to move toward beneficial or away from detrimental mutations. You just keep randomly mutating until you exactly hit the target.
Either way, this is still essentially a search strategy toward a known target. As long as the fitness function and the mutation function can play together to move the solution toward the target, it will eventually get there.
The more interesting application is moving toward an unknown target, which means the fitness function needs to have some method of either encoding the properties of a desirable solution ( beware of assumptions) or have some way to brute force test each possible solution in some fashion and collect some metrics from the test to measure fitness.
The mutation function can then either take an evolutionary or revolutionary approach to seeking new solutions.
The next level of subtlty is to introduce a more complex fitness function that evaluates both the overall fitness and "sections" of fitness. In the example above, it would be beneficial to evaluate the overall closeness of the string and the closeness of the first and second halves. This way, its possible to introduce multiple mutations in each generation, rather than a single mutation per step.
What is the benefit of this? Its the same process just running in parallel. Parallel evolution anyone?
You could add random cross overs along with culling based on part and whole fitness values. (So a solution with a high fitness in one half would not be culled even though its overall fitness may be low. )
This allows the solution to evolve at different rates in different parts of its DNA. Again evolutionary rather than revolutionary.
The next stage of fun being to randomly add or remove modules from the solution string and do some sort of fitness evaluation on different parts of the solution string, for different parts of the target. This allows a valuable mutation to may occur in one section to migrate to a different location in the target string, even though it was useless in the position it occurred in initially.
We will call this a matrix of fitness functions. More dimensions can be added to the fitness matrix, depending on how bored you are.
The choice really comes down to the type of mutation function, is it evolutionary (incremental steps) or revolutionary ( random jumps). The first can get trapped on plateaus while the second wanders much more wildly. We need a mix of both. The question is the influence of either in the mutation algorithm. Next trick would be to vary that based on the fitness value. Need to figure out a continuum effect for the mutation algorithm while still keeping it blind to the eventual target state.
Endless fun...
This is a nice little post on building a simple evolutionary algorithm. I have not thought of applying it to string mutation but its a nice little application.
A couple of thoughts occur to me.
The first being that "evolution" is strongly encoded in the mutation algorithm which single-steps one of the characters in the string a single position ( plus or minus). Which produces a slightly random systematic search strategy. A "revolutionary" approach would be to randomly replace a character in the string with another character.
If this approach was taken, then it would introduce much greater possible degree of individual mutation. This is detrimental for a population of one but would be much more valuable if there is a larger population using cross-over and cull based on fitness. Beneficial mutations would be quickly reinforced. In a population of one, there is no chance to move toward beneficial or away from detrimental mutations. You just keep randomly mutating until you exactly hit the target.
Either way, this is still essentially a search strategy toward a known target. As long as the fitness function and the mutation function can play together to move the solution toward the target, it will eventually get there.
The more interesting application is moving toward an unknown target, which means the fitness function needs to have some method of either encoding the properties of a desirable solution ( beware of assumptions) or have some way to brute force test each possible solution in some fashion and collect some metrics from the test to measure fitness.
The mutation function can then either take an evolutionary or revolutionary approach to seeking new solutions.
The next level of subtlty is to introduce a more complex fitness function that evaluates both the overall fitness and "sections" of fitness. In the example above, it would be beneficial to evaluate the overall closeness of the string and the closeness of the first and second halves. This way, its possible to introduce multiple mutations in each generation, rather than a single mutation per step.
What is the benefit of this? Its the same process just running in parallel. Parallel evolution anyone?
You could add random cross overs along with culling based on part and whole fitness values. (So a solution with a high fitness in one half would not be culled even though its overall fitness may be low. )
This allows the solution to evolve at different rates in different parts of its DNA. Again evolutionary rather than revolutionary.
The next stage of fun being to randomly add or remove modules from the solution string and do some sort of fitness evaluation on different parts of the solution string, for different parts of the target. This allows a valuable mutation to may occur in one section to migrate to a different location in the target string, even though it was useless in the position it occurred in initially.
We will call this a matrix of fitness functions. More dimensions can be added to the fitness matrix, depending on how bored you are.
The choice really comes down to the type of mutation function, is it evolutionary (incremental steps) or revolutionary ( random jumps). The first can get trapped on plateaus while the second wanders much more wildly. We need a mix of both. The question is the influence of either in the mutation algorithm. Next trick would be to vary that based on the fitness value. Need to figure out a continuum effect for the mutation algorithm while still keeping it blind to the eventual target state.
Endless fun...
Subscribe to:
Posts (Atom)