Search This Blog

Loading...

7 Aug 2013

Python Day 12: CA based SOM-GA: fitness by clusters


The structure of the algorithm:
1. Genetic Algorithm produces a generation based on the model generated by Cellular Automata:



2. Each individual in this generation represents a teaching neuron or input on the Self-Organising map and trains the other neurons on the map to acquire similar parameters or vectors to those of the teaching neurons. Vectors of the neurons are represented in the same way as the decoded chromosome genes of the individuals. 

For visualisation purposes each individual has its own colour and the same colour has individual's best match on the neural map . Every neuron on the map changes its colour to match the colour of the closest input or teaching neuron (marked with the circle around it). This way the self-organising map displays colour-coded clusters. Note: each list of the cluster's individuals contains the corresponding original individual from the current population.


3. As soon as the map is trained all neurons are converted to Individuals and become part of the current generation

4. The multi-objective fitness is assessed based on the idea that each component of the fitness criteria must be above certain threshold in order for all parts of individual's fitness to grow simultaneously. Each cluster gives a couple of future parents chosen by one of three available selection methods. 

6. Then the processes of crossover and mutation are applied to all selected individuals. At the crossover the off-springs inherit their parents' averages of R and G colour indexes spliced in a randomly chosen proportion. B is constant for all individuals and their offsprings to keep the colours readable. Therefore colour of the clusters evolves with generations in parallel with the shape of the models.

7. The siblings compose the next generation. The same process performed again for a certain number of generations or until the desired individual has evolved. Note: each generation can contain different number of individuals.

The example of the population evolved over three generations:




2 Aug 2013

Python Day 11: CA based SOM-GA. Exploring the SOM's clustering of the search space



So far all experiments were based mostly on the one advantage SOM gave to GA: the expanded search space. Now the another quality of SOM enhanced GA needs to be looked at: the structuring and clustering of the search space. Is there way to recognise the patterns on the neural map and adapt the algorithm so it works out the fitness criteria of the formed clusters ? The datamining process can be used that recognises different clusters the SOM and figures out the suitable candidate to become a parent.This way the SOM-expanded search space of the GA can be explored, managed and used in evolutionary algorithm even better. 

So far, neurons' vector parameters were 100% geometrical. That gave the map very well-defined visual clustering. As more implicit types of paramenters are programmed into the vector (or chromosome values) and also into the Fitness Factor the more diverse will be the appearance of search space.

After that the third, artificial selection method can be tested on both algorithms.

Application: The algorithm that explores clustering can be used in developing designs which fitness depends mostly on geometry or has an external embryogeny. As there is no point looking at all the individuals in all clusters, because they would be very similar. Another SOM-GA that assesses the fitness based on the Fitness Components Threshold to be used with an implied embyogeny inbuilt processes as it produces the greater diversity of the appearances of the models across generations and their neural maps.

Coding: The illustration below shows the neural maps in clusters. The colour of each cluster represents the colour of the corresponding training individual of the current generation. Each neuron acquires the colour of the closest to it winner (a neuron closest to the training individual of the current generation). When the parents are chosen their offsprings inherit their averages of R and G colour indexes spliced in a randomly chosen proportion. B is constant for all individuals and their offsprings to keep the colours readable. Therefore colour of the clusters evolves with generations in parallel with the shape of the models. Selection method at this point is not essential and will be looked at in more detail in the next stage.



31 Jul 2013

Python Day 9: SOM-GA: Next generation from the couples chosen randomly out ofthe fittest

As the selection of individuals is already programmed into fitness, the assumption is that there is no point to even use Goldberg roulette as a selection method. A random coupling can be performed and their off-springs can compose the next generation. The experiments showed that if there are more couples than the number of individuals in each generation and the fitness threshold is not set very high, than the evolution dies out. At best the fitness remains exactly the same throughout generations, without even giving much of a form divercity. That is due to a vast variety of cetrain level fitness values, so it fluctuates from generation to generation without steadily going up.

Python Day 10: CA based SOM-GA: Expanding Generations



Concept of the current algorithm:





Every new generation is composed by the off-springs of ALL randomly mated individuals (or artificially picked certain number of couples) that have any fitness. Whilst fitness is only given to the individuals if they have ALL fitness components over the certain value.


+

Co-evloving Fitness Components threshold. It keeps growing with the generations thus promoting evolution and keeping the size of the generations down.



Results: The fitness grows so fast from generation to generation even with the co-evolving fitness threshold that it is necessary to introduce a fitness assessment function to determine the reasonable threshold level for each generation. The sizes of the SOMaps are getting enormous. The dark and light orange coloured individuals represent the parents of the next generation:



So I filtered the potential parents leaving only those with the fitness of greater than half of the best one of the current lot. It was done in order to minimise the size of the further generations and their neural self-organising maps. As a result the algorithm evolves the fitter generation from the expanded search space extremely fast. However the biggest drawback is that it has to run many times before it can create the first generation where the components of the fitness criteria are at the right balance. If it doesn't happen than the code just terminates with the message informing that the fitness of all individuals is of value zero. In a way its not a bad thing as it stops the user from wasting a lot of computational time and evolving the wrong generations. However, even algorithm works perfectly well, something can be done in order to produce more appropriate first generation as at the moment it is created randomly. Alternatively, the fitness components threshold can be more intelligent and be set depending on the fitness values of each component of current generation. The second option is more realistic to program. The same goal was achieved by simply lowering the Fitness Components Threshold and increasing the min fitness level for the parents selection. Also the maximum size for the neural maps was set to keep the computing time to realistic limits as sometimes the map can be so large that it concentrates too long on one generation without any benefit for the evolution process.

The resulting maps showed well-defined clustering, displayong the concentration of the fittest models on the maps. It occurred because the fitness is geometry dependent:


28 Jul 2013

Python Day 8. SOM-GA: Co-evolving Threshold of the Fitness FactorComponents

Co-evolving Threshold of the Fitness Factor Components for Each Individual and Neuron:

In order to gain some fitness an individual (or a neuron) must have the components of the fitness factor defined accepted level. If one of the Fitness Factor constituents is below the defined threshold, its total fitness is written down to zero. This is introduced for two reasons. Firstly, so individuals evolve their fitness evenly across all its components. The individuals whose fitness is zero are not participating in the selection process at all. Secondly, to manage the problem of expanded choice and structure the the search space by narrowing it down and eliminating the individuals that are not fit across all the components of the fitness factor. In addition all siblings are forming the next generation. Also the computational time is saved as the neurons with fitness zero, do not go through the laborious process of encoding their values to binary chromosome code. 

25 Jul 2013

Python Day 6: Encoding of a GA chromosome list. CA based GA-SOM

Going forward and evolving the algorithm of the  Day5Day 3Day 2 and Day 1 to produce an algorithm described in the Thesis Abstract with the description of the Main Stages

It was quite a straightforward task to turn Neurons to Individuals of GA in order to check their fitness, cross parents over and mutate few. The tricky bit was to create a self.chromosome list from the decoded self.values list. 


















24 Jul 2013

Python Day 5: Self-Organising Maps expand and rstructure Genetic Algoritjm's search space (2D Cellular Automata model)

Going forward and evolving the algorithm of the  Day 3Day 2 and Day 1 to produce an algorithm described in the Thesis Abstract with the description of the Main Stages


Each Self-Organising Map trains its neurons to become a close match to every individual of each generation. The neurons highlighted in RED are the best match of an individual of the generation, which search space they were expanding.  Thus SOMs expand and structure the entire search space of the Genetic Algorithm. The fitness of the neurons within the map is not checked therefore they cannot become parents. That's the task for tomorrow.

The experiments will follow in the next posts to determine advantages and disadvantages of incorporation SOM into GA, what it means for the process of the evolution of an architectural model and how it can be parametrised to deliver designs of high aesthetic levels.



21 Jul 2013

Python Day 4: Dilemma

The next step: rationalise fitness externally, explicitly and implicitly to add both functional and aesthetic values to the model (more in the post)

or

should I forget about fitness for now, concentrate straight away on Self-Organising Maps. At the end of the day, SOM is the main subject, simplify whats not relevant and instead manage the choice and selection process by:

- seting up the minimum amount of parameters, only with those essential ones that needs to be worked with or customised
- defining multiple constrains and applying the elimination criteria- applying artificial selection

(more in the post....and thats already plenty!

or

have a drink on the beach



20 Jul 2013

Python Day 3: Adding Golden Ratio to the Fitness Criteria of the Genetic Algorithm (from day 2)

Today's exercises is not essential, but I just couldn't resist the temptation to test my GA (algorithm of the Day 2) with my long-term area of interest of Golden Ratios and mathematics in Nature. I added an (arguable) aesthetic factor to the model's Fitness Criteria.  Now the proportions of the width and length of the boxes are encouraged to be close to Golden Ratio (Fibonacci) 1.618:

14 Jul 2013

Python Day 1: GA with min intersection of solids

The simplest body-plan of intersecting boxes and a cylinder was chosen to start. The main body is a cylinder and the two boxes are floating around. Roulette selection depending on a fitness criteria of min intersection of the boxes with the cylinder and no intersection of the boxes with each other. Red models are the fittest in each generation:


12 Jul 2013

Stage 3: 1st Generation

From the final model create a set of the individuals with the paramenters of the extreme ends and run SOM to provide the search space for the formation of the 1st generation. Investigate how the possibility space within the GA can be structured with help of SOM of artificial neural networks, based on association of classifications

Stage 2: Final Body-Plan

Find the ways to parametrise the defined functional zones so they can b moulded together in one connected space & let user choose the method.
Mold the spatially allocated masses from the stage 1 together by combining all the objects with different sets of parameters to form one (with the sum of the characteristics of all the separate parts). 

Notes: Parameters do not need to represent geometry. Qualities can be both extensive and intensive. Resulting variation models from the stage 1 compose the 1st generation for the GA

Stage 1: Cellular Automata Creates a Blueprint for the Body-Plan

The conditions of the existing site and results of the performed assembly of local spatial concordances into global morphologies are given. Arrange the functional spaces accordingly in the 3D space with the help of CA algorithm
How: define masses and run 3D CA to arrange the parts of a future individual before crossing them together, not forgetting their integration with the "complexity of the given". User to be given options in choosing the ways to parametrise the first generation in order to avoid the trap of using "computational techniques of close-packing and providing full convergence of solutions before allowing the user to inspect the results". 

References:

Derix_2010_ Mediating Spatial Phenomena through Computational Heuristics (pdf)

MDeLanda "Philosophy & Simulation"

Kalay_Architectures New Media pp.259 (Spatial organisation)

Stage 5: SOM Training of the Following Generations

From the final model create a set of the individuals with the  parameters of the extreme ends and run SOM to provide the search space for the formation of the 1st generation

The first grid is made of randomly parametrised individuals. After the training they are filtered according to a simply functional fitness criteria. Artificial selection is performed among the x even number of individuals that are paired to be mated. After a pair mates, they are replaced by their offspring in the same spatial location, so the genetic material remains spatially local. The rest of the grid remains unchanged but trained to achieve close parametrisation of the newly created generation.

This way the clusters of entirely different spices evolve.


Example in Kalay's "Architectures New Media" pp287 onwards

Stage 4: Selection, Cross-Over and Mutation Experiments

Management of the Expanded Choice:

Read post "On The Paradox of Choice"
Read post "Solving "the Paradox" of the expanded choice in the proposed algorithm"

Selection options:

  • Artificial
Artificial selection is performed among the x even number of individuals that are paired to be mated. After a pair mates, they are replaced by their offspring in the same spatial location, so the genetic material remains spatially local.

  • Natural

  • Co-evolution

Daniel Hillis co-evolved sorting networks 
Karl Sims co-evolved virtual creatures. 

Hill's co-evolution of parasites
There are two independent gene pools whose evolution rates are naturally comparable, one representing "prey" and another"parasites". Each of the populations evolve according to GA's selection /mutation/ recombination sequence. Both gene pools evolve on the same grid and their interaction is through their fitness functions. The prey is scores according the failure of parasites at the same grid location. The parasites are scored based on how well they find flaws in prey's fitness. The fitness functions of the prey and the parasites are complementary in the sense that a success of one represents a failure of another and vice versa.


Benefit of using co-evolution instead of the fixed fitness criteria is that it prevents large portions of the population become stuck in local optima.

Cross-Over Options

Once the next generation is determined the following ways of coupling can be tested:
1. use a mating program with some type of spatial locality. This increases the average inbreeding coefficient and allows the population to divide into locally mating demes  (Hills 1991). Only the closest neighbors are mated. In a long run it promotes the diversity of the phenotypes. 

2. random or selected number of randomly created couples are mated
3.



Mutation options



References

- Daniel Hillis 1991 Co-Evolving Parasites SFI Artificial Life II (pdf)

Reading Room: Agency/Agents


Pickering  A_The Mangle of Practice: Agency and Emergence in the Sociology of Science  (pdf)


Thacker  E_Networks, Swarms, Multitudes part I (pdf)


Thacker  E_Networks, Swarms, Multitudes part II (pdf)


Thacker  E_Pulse Demons (pdf)


Reading Room: Self-Organisation

Coates P_Topological Approximations for Spatial Representation (pdf)

Reading Room: Synchronisation

Steven Strogatz: How things in nature tend to sync up

Reading Room: Artificial Life

Autonomy and Artificiality by Margaret Boden  (pdf)

Reading Room: Evolution

Frazer J_Evolutionary Architecture (pdf)

Reading Room: Evolutionary Computation

Derix_2010_ Mediating Spatial Phenomena through Computational Heuristics (pdf)

Reading Room: Genetic Programming

Coates  P_1999_Exploring 3D design worlds using Lindenmeyer systems and Genetic Programming.EDUC pp 323 (pdf)

Coates P_Genetic Programming and Spatial Morphogenesis (pdf)


Coates P_The use of Genetic programing in Exploring 3D Design Worlds (pdf)


Coates P_The use of Genetic Programming for applications in the field of spatial composition (pdf)