The basic idea is that you don't need to implement complex physical reality simulation (air drag, turbulence etc.), but only relatively simple genetic algorithm.
To test the idea I devised following experimental setup - each "individual" is sheet of paper (37x194 mm), which is divided in fourteen folding lines:
Each folding line can be left untouched or folded inwards or outwards, thus there are 3^14=4'782'969 variants (actually some foldings which cancel each other are forbidden, so there are little bit less variants). Here are some examples:
The goal (fitness funcion) of each paper sheet is to fly as far as possible. It is measured by throwing each paper sheet from fixed height (around 2.20 m) and measuring horizontal distance to landing point:
Each sheet is thrown 3 times and average distance is calculated. Sheet is always thrown by holding it in fixed position (upper side of the sheet).
Genome encodes specific foldings as binary string, for example, binary string 10101110111110011111100 encodes following folding sequence: Out None None None In Out None Out None None Out Out In None. First bit determines, whether folding place #1 or #2 is folded at all (1=yes, 0=no), second bit determines, which of folding places is folded (in this case - first), third bit encodes folding direction (inwards or outwards) and so on...
Thus in this case genotype of each organism equals it's phenotype (appearance).
Then comes genetic algoritm, which has fairly standard steps:
1) generate initial random population
2) determine fitness function for each individual
3) create intermediate population by selecting best individuals (by using Stochastic universal sampling)
4) perform crossover by randomly choosing two individuals and exchaning their genome sequences at random point
5) perform mutations by randomly flipping bit (0=>1, 1=>0)
6) fold paper sheets, throw them from fixed height, measure distance and calculate fitness function value for each individual
7) repeat the procedure again and again for each generation
At first I tried setup with population size of 10 individuals and mutation rate p=0.01. Either because of small population size or incorrecty applied crossover procedure after 5 generations population was stuck in some local maximum and also folding sequences started to resemble each other too much.
Here is summary of results:
Generation 1 - max 66.5 cm - average 35.7 cm
Generation 2 - max 62.0 cm - average 36.5 cm
Generation 3 - max 71.5 cm - average 37.8 cm
Generation 4 - max 52.5 cm - average 37.1 cm
Generation 5 - max 53.0 cm - average 39.1 cm
Second try included population of 20 individuals and mutation rate p=0.02. Results were more promising:
Generation 1 - max 73.7 cm - average 27.2 cm
Generation 2 - max 119.7 cm - average 39.3 cm
Generation 3 - max 97.7 cm - average 51.8 cm
Generation 4 - max 123.3 cm - average 46.1 cm
Best far-flying individual (#161) with his "parents" above (#148 and #149) is shown here:
As we can see, winning design is quite simple - just fold the paper sheet diagonaly in middle and it will fly ~2-3 times further than most other sheets with elaborate designs.
Conclusions so far:
* Artificial evolution can find interesting designs, but probably the same result could be achieved by using different optimisation techiques.
* Have to test other methods for comparision.
* Good designs are not always retained after crossover and mutation (probably need to increase proportion of best individual in next generation).
* Folding many paper sheets "by hand" can be quite boring (some kind of semi-automated "embriology" should be considered in futher research).
* Foldings are not always perfect (different phenotypes resulting from equal genotypes).
* All of operations were performed "by hand" using Excel - no need for programming, but quite cumbersome. More automated approach should be considered in future.
* Variability of distances for each individual was not very large (standard deviation/average = ~0.77) meaning that designs really play role in flight distance. In other words, bad designs consistently had low-distance flight, while good designs consistently had high-distance flight in each of 3 trials.
* Larger population size is better (reduced tendency to local maximum), but probably 10 or 20 individuals are still not enough to get real power of artificial evolution and also number of generations might be larger.
* Mutation rate p=0.01 seemed too small, probably p=0.02 is more appropriate.
* No practical use so far (but it was interesting...).
* Lack of theoretical background (e.g. best mutation rates, population size etc.), but, of course, this is just proof-of-concept and doesn't pretend to prove anything...
No comments:
Post a Comment