I'm very interested in techniques to develop algorithms. I'm currently exploring genetic algorithms.
From what I understand, they are usually implanted with fixed genome size, say 40 bits. And crucial to the genetic algorithm working is the fitness function being able to assess partial fitness.
I'm struggling on a couple of aspects:
Say I create algorithms that generate a variable length genome that translates to an arbitrary algorithm of an individual. The individual might consist of variable assignments, computations, loops and so on, of some arbitrary depth and size. I'd have GA mechanisms to implement crossovers, mutations and selections. I'd expect this to involve representing an individual's algorithm/phenotype as a tree, for xample a while loop at the base of the tree, and branches being the conditions for the while loop and operations performed in the whole loop. Crossovers for example might swap random sections of the individual's tree with another's. But what I'm stuck on is the fitness evaluation of an algorith:
Say we randomly generate an algorithm. Chances are, it won't do what we want. At all. In fact, if we have a task we want an algorithm to perform, there's very little chance that it would output what we want. I can't think of an effective way of appraising fitness such that in most cases it won't be zero. Even, if say an individual's algorithm contains within it part of what could be part of a successful algorithm, chances are the junk within that individual's algorithm would prevent that individual from achieving a fitness other than zero.
How can this problem be overcome?
I thought of one option which might help to some extent but is not a full solution: each step of the algorithm could be tested for a value to see if it matches expected output for given input. But chances are that the algorithm is only accidentally achieving this value, not as the result of an effective algorithm.
I wonder if it's even possible to do what we want here. Nature, with its selection of the fittest has a great advantage: numbers. Trillions of individual over billions of years. That's 1021. I just have one computer over say a year. That's an enormous difference. Are genetic algorithms really practical? Anyway, I digress.
If I want to create algorithms with GA, I feel we need to at least optimise aspects for generating and selecting fit individuals. Algorithms should only be able to be created that do not have redundant or dead code. So I need mutation and crossover operations that intelligently alter an algorithm? This could get really complicated?
I'm also wondering if we could evaluate fitness of part of an algorithm some how, and prioritise propagation of that part?
I just don't see how to create arbitrary algorithms without having to cover an enormous search space. I think the biggest problem is evaluating the fitness of algorithms (ignoring that nature has the advantage of greater space and time). In nature, fitness seems to be possible for anything from simple single-celled organisms all the way up to complex human beings, enabling progressive development. But my vision of GAs is different; fitness would be evaluated as how close the output of an algorithm matches what I want out of a completed algorithm. Chances are fitness will be zero for the vast majority of cases, so it would have to develop blindly, not being coerced by a fitness slope, so facing the full solution search space with only brute force to help it. And even if fitness does not evaluate to zero, the chances of a non-zero fitness being evaluate could be achieved by a largely unfit algorithm, only fitting perhaps one or two input/output data points, and not having any elements of what could be considered an effective algorithm.
Please could someone shine light on these aspects? I'm relatively new to AI in general, I've never managed to implement anything and am quite early in the learning stage. I don't know if I'm on the right track at all. Have I got the wrong end of the stick? I feel like I've hit a dead end. Have I misunderstood the application of genetic algorithms?
Thanks
[link] [comments]