Melanie Mitchell described these properties:
1_ Complex collective behavior: Complex systems consist of a large networks of individual components, each following relatively simple rules with no central control. It is the collective actions of vast numbers of components that give rise to the complex, hard to predict in some cases.
2_ Signaling and information processing: All the systems produce and use information and signals from both their internal and external environment.
3_ Adaptation: The system adapt, change their behavior to improve their chances of survival or success, trough learning or evolutionary processes.

Considering the third point, adaptation plays a large role in complex systems, differentiation between complex adaptive systems such as ant colonies and the neuronal nets or Genetic Algorithms. And non-adaptive complex systems, such as huricanes, waves, dunes, etc. Systems organized behaviour are usually called self-organizing. The macroscopic behavior sometimes are called emergent systems which is a characteristic of the system. The main thing here is how the emergent self-organized behaviours comes about.

This is my first attempt to create a complex system based in very simple rules.
How is works:
the applet will generate 500 particles. This particles will try too keep the same distance among each, which is impossible because the size of the field (500px x 600px) will not allow.
clicking on the field you can create attractors and repellors to initiate different behaviours in the flock.
Use the first slider to set the visualization of the cells.
Use the second slider to set the attraction-repellor distance influence.
Use the third slider to set the strenght of the attractor-repellor, by default is in zero so it will not produce any influence in the flock. Use positive values to create attractors and negative for repellors.
In order to use, define the influence area (second slider) then, the strength (third slider) then click on the field.
To liberate the forces applied in the flock, hit:
b to remove the last attractor-repellor.
e to remove any force.
a to see the particles.

// Click on any picture to launch the applet. //
I hop you enjoy.

Video

Introduction
Genetic Algorithms (GAs) were proposed and developed by John Holland in 1960s (Mitchell, 1996). A GAs is a programming technique which imitates the biological evolution as a strategy to resolve problems and/or search design that fits certain conditions. This paper explain in deep how can GAs can be applied to design optimized architecture. There are many books and literature about Genetic Algorithms and Evolutionary Computation. For further information please visit: [1 – 5].

Definition of the problem
Nowadays, one of the main problems in architecture is the HVAC consumption in the buildings. The problem to face up in this work consists in reducing the heating and air conditioning modifying the geometry and the windows’ positions and sizes. This problem is considered a multi-objective problem because both parameters are related and we cannot minimize one of it without increasing the other.

For example, if we have a big window, in summer the sun will heat all the pieces of furniture hence it will increase the temperature in the room and therefore, we will have to turn on the air conditioning to keep the room at 20ºC. The good news is that we can take advantage of the natural light for more time, and we can also refresh the house at night releasing the heat trapped on the walls by radiation during the day. In winter, the same window will capture the heat, but unfortunately all the heat will be lost very quickly because it will escape through the same window where it enters. Therefore, we will have to turn on the heating quickly and the worst is that all the heating produced will continue escaping trough the window increasing the heating consumptions.

If we reduce the window to the minimum possible size, what will happen during the summer is that we will not be able to release the heat trapped on the walls, so we will have to keep the air conditioning switched on for more time to cool the room and logically we will not be able to take advantage of natural light as much as when we have the big window. Besides, as we have a small window he will have to turn on the light earlier and since the artificial light heats, we will have to release this heating of the room too. In winter, the same small window will not heat the interior of the room and we will have to turn on the heating almost all the day and probably the night. In addition, we will have to turn on the light because the sunlight within the building will not be enough because winter is darker than summer.

To sum up, a large window performs well in summer and presents a very bad behaviour in winter. On the contrary, a small window will be a complete nuisance in summer, but it will have a better performance in winter. Therefore, the problem is not to enlarge or reduce the window to achieve a single parameter, but to find the optimum that balances both behaviours.

There is an extra help for this problem such as the possibility of modifying the geometry of the building which will allow us to search and explore creative solutions and to obtain better performances that will be out of reach if we only change the windows’ position and size.

This research pretends to be a seed in the contribution to the pursuit of sustainable development proposing an architectural design’s system to reduce the air conditioning and heating consumption by searching the best possible shape applying a Genetic Algorithm. The solution of the problem consists in answering the following question: Which is the best building’s geometry and windows’ configuration to keep the temperature at 20º during the hottest and coldest day of the year in order to consume less energy?.

Contributors and previous work
Many Scientists, engineers and architects have been working and experimenting with evolutionary techniques in the form finding of architecture. For further information please visit: [5 – 8]. Nevertheless This work is based on the paper “Architectural Constraints in a Generative Design System: Interpreting Energy Consumption Levels” by Luisa Caldas and Leslie Norford at the Seventh International IBSA conference in Rio de Janeiro, Brazil in 2001[9].

In that paper, the researchers encoded one of the buildings of the School of Architecture in Oporto-designed by Alvaro Siza- to apply a Genetic Algorithm to optimize daylight and energy consumed to heat and to cool the building. They used this building as test bed and its windows’ geometry as a framework to modify and explore different configurations during the iterations of the algorithm. To evaluate the HVAC consumptions they use DOE-2.1E which is a building simulation program and a Micro-Genetic Algorithm (Micro-GA), which is not described in depth.

This work is based on a parametric model to constrain some relations of the building, to avoid failures in reports during the process of evaluation and to encode in a simple way the parameters of the building. A Micro-GA is used to search and optimize the geometry, although it presents some variations in comparison to the traditional way to build this algorithm. Other aspects to comment on are that the population is very small -5 individuals per generation- and not more than 15 generations are used to obtain the results. This work is programmed basically in C# in two different levels. The top level corresponds to GCScript, which is applied to control the geometry and manage the different classes to compose the GA and transactions files between GC <-> E+. And the bottom level, which is pure C# directly written in visual Studio 2008 and embedded into GC through a series of functions. The programming language C# is used to perform the hard tasks such as gaining speed during the process, developing the whole GA and carrying out all the transaction files between the programs. Finally, the evaluation of the building is performed by Energy Plus, which is the evolution of the software used by Caldas and Norford.

Method
This section consists of the explanation of how the whole process works, which is divided into the description of the parametric model into GC, the explanation of the thermal model into E+ and the description of the classes and how they are related to create the GA.

Parametric Model
The model is a perpendicular box to the north, composed by 6 flat surfaces and two windows. One of the windows faces east and the other west. The measures of the box are 12 meters in the X direction (east – west), 10 meters in the Y direction (north – south) and 4 meters high.

The first step of the construction consists in 4 parameters called coordXSrfWest, coordYSrfWest, coordXSrfEast and coordYSrfEast. These parameters are used to control the geometry of the box. The second step is to define 3 points. The first point lives in the center of the box (point01) and the others two are defined by the previous parameters and are named ptWest and ptEast. The Z coordinate of the three points is a fixed value that keeps the surfaces flat, otherwise E+ will not perform a correct analysis.

Two vectors (ByOriginDirectionPoint()), are defined from point01 to the points ptEast and ptWest. These vectors are used to host also two planes (ByDirectionAndDistanceFromOrigin()), one for the east side and the other for the west side. These planes host two coordinate systems (OnPlane()) at their bases and two polygons are created through a GCScript code . The windows are also generated by GCScript and their size depends on the flat surface dimensions (It cannot be bigger than the flat surface that contains it) and coordinate systems as origin. The rest four polygons are defined by the vertices of the original polygons.

Parametrizing a model needs a double effort, on one side you have to know exactly what you need to avoid extra steps in the generation and lose speed. On the other side, you must know which of these parameters constraints are and which of them are flexible. Once the model was parametrized it is tested under much iteration to observe the behaviour and detect possible bugs.

Figure 1 (The model with the geometric elements to build the shape.)

Figure 2 (Testing model after 200 iterations in which is possible to observe the different geometries that are able to support.)

Thermal Model
The thermal model corresponds to the other information that we need to describe the building. This data is necessary because it sets the physical characteristics such as where the building is located, the type of weather, which material the walls have, if the windows are double or simple and etc. This information and much more are defined in the E+ file.

The important part in this model is that the geometry (behavior) is defined and manipulated into GC and the physical characteristics (properties) are defined into E+. The correspondence between the two files must always be the same. For example, if in the IDF (EnergyPlus file) appears 6 flat surfaces the model must return always 6 flat surfaces.

The principal characteristics of the model into E+
Building location: Country terrain, Chicago IL.
Windows: Double Panel window with an interior camera of 3 mm.
Walls: Wood siding outside, fiberglass quilt in the middle, and plasterboard in the interior.
Roof: Roof deck outside, fiberglass quilt, in the middle and plasterboard in the interior.
The floor is defined by: Thickness(m): 0.10, Conductivity(W/m-K): 1.7296, Density(kg/m3): 2243.0, Thermal Absorptance: 0.9, Solar Absorptance: 0.65, Visible Absorptance: 0.65
The HVAC system used is a standard configuration: Heating Supply Air Temperature(C): 50, Cooling Supply Air Temperature(C): 13, Heating Supply Air Humidity Ratio(kg-H2O/kg-air): 0.015, Cooling Supply Air Humidity Ratio(kg-H2O/kg-air): 0.01
The output variables are defined into E+. In this case, the report corresponds to the consumption of heating and cooling during the hottest and coldest day of a year.

Classes
Two types of classes are written in C# in this research, one kind of classes is used for technical tasks, such as reading and writing files, calculating the distance between points and lines, exporting to excel, saving files, executing a program, sleeping the program and etc. The other type of classes performs the GA, in those we found the traditional genetic operators such as mutation, crossover, fitness function, selection and replace.

Technical Classes
The main technical classes into the GA are GCScriptFuncVerticesToIdf.cs, GCScriptFuncSleep.cs and GCScriptFuncReadSolution.cs. The class GCScriptFuncVerticesToIdf.cs transforms the polygons’ vertices in a list of strings, then extracts the information of the IDF file and replaces the old vertices for the new ones saving the file with the new data loaded. After this and through the class System.Diagnostic.Process, E+ is called to perform the thermal analysis with the new loaded geometry. This class is embedded into GC as a function called runSimulation().

The class GCScriptFuncSleep.cs sleeps the application for a couple of seconds meanwhile the analysis is performed and the new files are created.The class GCScriptFuncReadSolution.cs extracts the report analysis of the E+ and calculates the average of the consumptions, which is divided in three different values: the average heating consumption, the average cooling consumption and the average of the temperature in the building. Those values are returned into an array. This class is embedded into GC as a function called readDataSolution(). Its results are very important because these values are used as the fitness functions into the GA. The aim is to reduce these values as much as possible. Once the data is returned to GC another average is calculated to obtain a single value instead of the three original ones.

Genetic operator’s classes
Once the first series of classes is performed in order to create the first population, it is time to jump over the genetic operators. The first operator called in the code is CSChromosome.cs. This class takes the ptEast, ptWest, the two windows and its HVAC consumption (fitness) and decomposes the data in an array of 31 elements. At the end of the class the chromosome presents this structure as it is shown in Figure 4. The chromosome is saved in the population array and the fitness is printed in the console script. This class is embedded into GC as a function called genrChromosome().

Figure 3 (The chromosome is constituted by a list of doubles. From 0 to 14, the data on the list belongs to the east side and from the 15 to 29 to the west side. The last value (30) is the fitness which represents the HVAC consumption.)

After the population is created, the next operator that is applied is the CsnaturalSelection.cs. This operator is in charge of sorting the different chromosomes in the population from the best to the worst. Since we are working with very small population: Only 5 candidates per generation, the Roulette-wheel or other types of natural selection are not performed. What this class returns is the same population sorted from the “best” (the lowest HVAC consumption) to the “worst” solutions (the highest HVAC consumption). This class is embedded into GC as a function called pfrmElitism().

The next step produced into the GA is the crossover in which the best two solutions exchange part of their chromosome to constitute a new possible solution which inherits the properties of their parents. Since we are working with a small population this operator presents some differences in comparison with other traditional crossover systems. Several tests were made creating the crossover. For example, if we split the chromosome in two stripes and recombine them to produce two offsprings, this type operators will produce a rapidly convergence to a local minimum and stop the optimization at the second iteration. However, this kind of operator is very useful in other types of problems. Therefore, it is only necessary to create a new possible solution with the position of ptEast and ptWestpoints and the windows’ polygons which are related to the geometry that is generated randomly in order to avoid local minimum. Since we are working with only 5 generations it is necessary to explore all the possible solutions during this small period of time in which the GA runs.

At the end, the offspring is the coordinates of ptEastand ptWestpoints. This class is embedded into GC function under the name pfrmCrossOver(). The offspring and the best solution in the previous population are conserved for the next generation; nevertheless the offspring incorporates a very small mutation in its X and Y coordinates.

The class in charge of performing this mutation is CSMutation.cs. The mutation depends on a factor called MutationPercent and the best results in consumption set this value around 0.5. What it is done to perform the mutation is to calculate a random value between 0 and 1 (double r = Random.NextDouble()). Then, the MutationPercent is added and subtracted from the coordinate of a point to find a maximum and a minimum value:

double high = offspring [i] + percent, double low = offspring [i] – percent (1)

Figure 4 (Parent1 and Parent2 involved in the class crossover are split to create a new offspring. Random choices are made to define which types of offspring are returned. Windows data and HVAC consumption are discarded in this operator.)

After that, a simple equation is performed in order to save in the chromosome the new coordinates’ values:

offspringMutate[i] = low + r * (low – high) (2)

After the mutation is performed, the mutated offspring and the best solution are stored into the new population and 3 more possible candidates are generated randomly in order to complete the size of the population. The process is repeated N times or a stop condition can be defined by a consumption threshold.

Results
For this research, the GA system was tested 14 times with the same data environment and the same number of generations -5 in total-. Our results were that in 6 tries the GA optimized in all 5 generations, in other 6 the system was unable to optimize in one and finally in the other two, the algorithms were unable to optimize.

The average consumption at the beginning of the generations in the12 successful tries was: 1139.0286 w/h. The average consumption after the optimization was: 970.7155 w/h. The reduction represents the 17.21% less of consumption during the hottest and coldest day of a year. The best individual in all tests was: 840.4193.

Geometry
In relation to the geometry, the best results have some similarities. For example, the parameter coordXSrfEast was always around 10 in the best solutions, and the coordYSrfEast was always low, less than five. Something similar happened with the west side, coordXSrfWest was always within -5 and -12 and the coordYSrfWest was represented with low values between around 5 and -1, but only two times the values rose to 6 and 7.

Figure 5 (The figure shows the 12 successful tests where the optimization was performed. It shows the initial and final consumptions.)

Discussion
The results show that the system performed in most cases very good results decreasing the consumptions of HVAC levels around 17%. Before the GA performed, the coordXSrfEast parameters were higher than ten in all the cases and the coordXSrfWest parameters were low. This means that a big space will logically need more consumption to keep the temperature at 20ºC than a small one. For the coordYSrfEast and coordYSrfWest parameters, the values are in general high, which means in geometry that the two surfaces facing east and south receive the sun directly in the morning and in the afternoon. This type of geometry will increase the cooling consumption in the hottest day, and if the windows are big the consumption will be a complete disaster for the coldest day too.

The best solutions in general have low values in the coordYSrfEast and coordYSrfWest coordinates which means that the shape is folded to reduce the area exposed to the east and west. The Y values control the orientation of the building determining how much of the area is exposed to the sun. These small values indicate that the east and the west surfaces are facing south direction.

For the coordXSrfEast, the values are around 10 and for the coordXSrfWest are around -6 and only in one of test -12. The X values basically determine the size of the building such as the length of the building that pulls in both surfaces’ directions to face east and west. A big value to the east and small value to the west mean a large building. These parameters affect directly the total volume of the building and as a consequence it influences the performance of the HVAC consumption.

Figure 6(Perspectives of the 12 tests where the optimization was successfully performed.)

Since this experiment was focused on the manipulation of the geometry, the windows were always left at random sizes and positions. However, it is possible to observe some similarities among the windows in the different tests. For example, in all the cases the GA preferred small windows located near the edges of the surfaces instead of a center big window as the architects prefer. Another special feature was the disposition of the windows. The east windows were always disposed on the right side of the surface and in the west it occurred exactly the same. Nevertheless, if we look at the building from the east to the west directions, the building has the east windows on the right side and the west windows on the left side in the best test. The GA in almost all the cases proposed for the east side bigger windows than for the west side. Besides, the east windows in almost all the cases are vertical meanwhile the west are horizontal. The GA disposed 10 times the west window near the roof and proposed high and horizontal windows, but the east windows were left more freely generating windows near the floor and in only 4 cases near the roof. When this type of windows’ configuration occurs the GA reduces the consumption by decreasing the total volume of the building.

The GA in all the cases tried to reduce the total volume of the building and fold their geometry facing the east and west surfaces to the south (10 times) or to the north (twice). It never faced the east or west surfaces directly. The GA tried to capture more energy from the east than from the west proposing bigger windows for the east side 9 times. In general, the system left the east side with big windows at medium height and the west side with small horizontal windows near the roof.

Conclusion
The GA was able to generate out of 14 tests 12 possible solutions with low energy consumption levels. This makes the building more sustainable which is an issue that concerns the architectural discipline. Small consumptions are reflected in the budget of the building monthly, which is related to the cost that is, another issue that concerns the architectural discipline.

The minimum size of the windows was not constrained. In some cases, the GA proposed the geometry of the windows with minimum sizes, which can represent an uncomfortable spatial relationship between the interior and the exterior of the building. Therefore, this issue should be revised in the next works.This simple thermal analysis takes a typical laptop about 3.7 seconds to perform. This analysis generates all the documentation necessary to read the solutions and gives the geometry the situation of the HVAC consumption. This time consumption is ideal and a normal GA with a population of 30 individuals and 300 iterations will be the best idea too in contrast to the system proposed in this paper. Nevertheless, the focus of this research points to big scaled projects, where the analysis may take more than1 hour. For example, 5 individuals per 5 generations are at least 25 hours of computing costs. This is the main reason to propose this GA. The system in this stage is still under development, and some features must be checked. For example, when a new population is replaced, goods reports recommend the use of individuals with good fitness that were saved in previous generations instead of generating new ones completely randomly (Zitzler, Kalyanmoy, Thiele and Coello, 2001). In previous stages of development, different genetic operators were tested (mutation, crossover and natural selection) without good results. One of the main problems with small populations is to fall in minimum locals. In other words, the high power of inheritance in a complete crossover (windows and parameters) stops the optimization in the second or third generation falling directly in minimum locals.

References
Mitchell, M., 1996, An Introduction to Genetic Algorithms, Cambridge, Massachusetts,
Zitzler, E., Kalyanmoy, D., Thiele, L. and Coello Coello, C.A. 2001, Evolutionary Multi-Criterion Optimization, Springer-Verlag, Zurich,.
[1]http://www.obitko.com/tutorials/genetic-algorithms/index.php
[2]http://lancet.mit.edu/~mbwall/presentations/IntroToGAs/
[3]http://www.talkorigins.org/faqs/genalg/genalg.html
[4]http://www.genetic-programming.org/
[5]http://www.aaschool.ac.uk/publications/ea/intro.html
[6]ftp://ftp.forum8.co.jp/forum8lib/pdf/VRsymposium/harvard-2-2.pdf
[7]http://projects.csail.mit.edu/emergentDesign/genr8/
[8]http://www.armyofclerks.net/
[9]http://www.inive.org/members_area/medias/pdf/Inive%5CIBPSA%5CUFSC558.pdf

This is a very complex problem to solve. The aim of this experiment consist in use a GA to spatially organize room, depending on their areas and their location within the building perimeter. The process is based on a Voronoi diagram that subdivides the space and the GA fits to set the different areas within the premises plan.

This type of problem is complex for at least two main issues:

1_ Is a problem weight because each area has different requirements in the room spaces. i.e. orientation, ventilation, square meter.
2_ Is a multi-objective optimization, because the complete list of rooms are in some way fighting each other for the best position, the best view, the best ventilation. You can’t privilege one or a set of rooms with out to decrease others.

The problem is based on a Voronoi Diagram (VD). The area of each cell of the VD is used to fit the rooms. Usually VD are used to analyze space problems. There is a lot literature about VD.

Video

Genetic Algorithm parameters
Objective Function -> Diff erence.
Codifi cation -> Jagged array type, points and polygons area.
Type of problem -> Multy-Objective
Number of generations -> 50
Size of population -> 20 ind.
Natural selection -> Tournament selection, adjustable preasure in the selection.
Crossover -> Uniform crossover.
Mutation -> Multiply a coordinate by random value, 0.1%

Genetic Algorithm Structure:

chromosome Type

The chromosome of the individuals consist in the list of VD points. One thing to consider: If the red point is moved (see the picture) in order to fit his cell area, this will affect all the tangents cells area. So if for one side we are trying to achieve the fitness, In the other hand probably we can lost the obtained aptitude .

The chromosome is expressed as a jagged array, in the top list we have points and polygons (Voronoi cells)

Fitness Function
the fitness is expressed by the function in Rhinoscript.  This function evaluate each of the cell area in the VD. If the difference of area minus objective area is less than the width the gen is awarded by 1 else with 0. but we are interesting in generate a fitness with big value so the final result is divided by 10 to obtain decimals and precision in the fitness values. Is not a good idea have integers in a fitness value, because we expect have all the flavours in the optimization process. Lucky for me I never got a 0 division!.

Function fitnessEvaluation(individual, arrAreaGoal, arrPrecision)
Dim i
Dim count : count = 0
Dim area, resta
Dim reward

For i = 0 To UBound(individual)
area = Rhino.CurveArea(individual(i)(1))(0)
resta = Abs(area – arrAreaGoal(i))

If(resta <= arrPrecision(i)) Then
reward = arrPrecision(i)
Else
reward = 1
End If
count = (count + resta) / reward
Next
fitnessEvaluation = 10/count
End Function

Ranking Sort algorithm
Recursive quick sort algorithm, faster and stronger than bubble sort algorithm.

Natural Selection
tournament selection, with a pressure = 8.  I tried the roulette wheel before but the results do not persuade me. So I decide to wrote a tournament selection and the results were much better. With tournament selection is possible to control the pressure during the optimization. this is very useful when de difference of the individuals is minimum. The algorithm operate selecting a group of individuals into the population. The individual with the highest fitness won the competition and it is selected for the next generation (crossover and mutation).

Crossover type
For this GA I implemented two different crossover algorithms: Single point and uniform. the best results were obtained with the single point crossover.
offSpring = SinglePtCrossOver(cleanRW(indexDad),cleanRW(indexMom))
offspring = UniformCrossOver(cleanRW(indexDad),cleanRW(indexMom))

Mutation
The mutation consist in move one point in the chromosome in a random direction. The displacement must be really small because in this type of exercise is really important don not loose the data that came from the parents.

Results:

The table show in the first column the real area of the VD, second column is the objective area, third column: the width and fourth column the final area after the optimization. The white cells means that the GA was no able to fit this areas into the limits.

The plans before and after the optimization.

Optimization curve of the first plant. Each of this experiment were executed only 50 generations.

For further  information, please visit the research part of this blog.

Design a building is a very complex task, in which are involved many variables that must be satisfied. The Architect will decide which of this variables are more important than others and also the building must be satisfy other restrictions such as, budget, laws, clients, technical conditions, materials, fashions, etc.

This experiment use GAs as generative design system to purpose raw shapes trough a series of optimized functions. The goal consist in satisfy all the functions in the fitness, i. e. min = ( f(x1), f(x2, f(x3), f(x4), …, f(x+i) ). The idea consist in find the optimum for a series of functions , but is not possible to makes at least one function better off without making any other function worse off, this definition is knowing as Pareto frontier.

Function list:
The developer’s Manhattan function. → Maximize the volume and minimize the use in the ground floor. (COATES, Paul., Programming.Architecture, Nueva York, Routledge, 2010, p. 97 )
Point Repellor function. → If some part of the building is inside of an influence area the chromosome is punished.
Data type in the chromosome. → The function award the chromosome if some data type is founded inside it.
The model is an imaginary prisma of 20x15x30 units composed by 1x1x1 cubes.

Video

Genetic Algorithm parameter
Objective Function -> Fitness = (fitSequence + Volume) – ( (InsidePts x 2) + footPrint))
Codifi cation -> Bynary string.
Type of problem -> Multy-objective
Number of generations -> 300
Size of population -> 20 ind.
Natural selection -> Roulette Wheel, scaled by non
polinomic function.
Crossover -> Uniform crossover
Mutation -> Bit string mutation, 0.65%

Genetic Algorithm Structure:

Chromosome type
The Chromosome is made by a binary list , 100101010101. 1 represents a cube and 0 empty.
0 1 2 4 5 6 … 9 n+1
1 0 1 0 1 1 … 0 1

Fitness function
If(footPrint > 45) Then footPrint = footPrint * 5
If(Volume > 800) Or (Volume < 700) Then Volume = Volume * 0.5
Fitness = (fitSequence + Volume) – ( (InsidePts x 2) + footPrint))
The test bed to prove the GA.

Ranking Sort algorithm
Recursive quick sort algorithm, faster and stronger than bubble sort algorithm.

Natural Selection
The natural selection used is a roulette wheel scaled by a non-polynomial function and with a variable to manage the factor decay of the curvature. This improvement allows a more detailed selection for the individuals.

the FactorDecay control in accurate way the selection of the individuals to the next generation.

Crossover type
Two types of crossovers where implemented in this GA. A Single point crossover and uniform crossover. The single point crossover works splitting the parents in two stripes in order to create the descendent. The uniform crossover works with a random index which determine if the father o mother will inheritance the gen to the descendent. Both operators produce two descendents.

Single point crossover
uniform crossover

Mutation
The mutation operates swapping a 1 for a 0 or vice versa.

Results, city project: 

Generate a set of buildings, well distributed…This case use a GA to organize the buildings and guaranty the shortest path across the buildings.

After the city is generated, define zone points between buildings to ensure light, ventilation,views, spaces…

Execute the GA to generate volumes according to the functions defined above.

Rendering and catmull by Blender.

The aim of the experiment consists in define spatial relations and propose building volumes in relation of the short path founded by the GA. Is a combinatorial problem, because the solution consist in found the correct order of the points (building volumes) trough the path. The problem is combinatorial and the space search is the factorial of number of points in the path.

(n!) = 1 x 2 x 3 x 4 x … x (n – 1) x n

If there are 6 points in the path, we have 720 possible combinations, but if we have 20 points there are 2.432.902.008.176.640.000, possible combinations. This number is so big that if we test each of them, at computer speed (one millisecond), it will take 77.146.816 years to find the best solution. So a good chance to face up the problem will consist use a GA, but also there are good reports using hybrid techniques mixing GAs with Divide and Conquer or ants colonies techniques. Another quite interesting thing of this problem is when the objective is dynamic and the points of the route are moving or the number of points is increasing and decreasing depending of other factors.

Video

Genetic Algorithm parameters:
Objective Function -> length of the path.
Codification -> list of points.
Type of problem -> combinatoria.
Number of generations -> 100.
Size of population -> 20 ind.
Natural selection -> Roulette Wheel, scaled by non-polinomic function.
Crossover -> One-point crossover, 1/2.
Mutation -> Swap bit, 1.

 
Genetic Algorithm Structure:

chromosome Type
Each individual in the population is defined by chromosome with a single list of points.
0                         1                             2                 …                       18                              19
P1(x, y, z)     P2(x, y, z)          P3(x, y, z)          …             P19(x, y, z)             P20(x, y, z)

Fitness function
EuclideanDist = EuclideanDist + Sqr((Path(i)(0) – Path(i + 1)(0)) ^ 2 + (Path(i)(1) – Path(i + 1)(1)) ^ 2 + (Path(i)(2) – Path(i + 1)(2)) ^ 2)

Ranking sort algorithm
Simple bubble sort algorithm.

Natural Selection
The natural selection use a roulette wheel method scaled by a non-polynomial function, expressed by:

 Changing the displace value, the natural selection can be more selective and add pressure in the further populations when the difference from the best individual to the worst is minimum.

The blue curve has a displace = 5 (see the function above), which means that only the best first 10 individuals will have a chance to be selected for crossover and mutation. Have a lot of pressure in the selection inplies search solutions only in a very small  area into the whole space solutions. In some cases can be useful, but in generally the idea is search around the whole space. In the green curve the displace is 0 all the individuals will have a chance to be selected for the crossover and mutation, the inconvenience here is the convergence of the solutions can take quite long time, in the worst of case never find a good solution.

Crossover
A single point crossover is implemented in the GA. But is necessary to check the copied genes to the Son to avoid repeat points or data. For example if the father inherits the first half genes, is necessary to check with genes can contribute the mother to the descendent.

Mutation
The mutation consist in swap two genes,or more, into the chromosome.

 Results:

Curve optimization for a population size of 20 individuals, 20 points and 50 generations.

Curve optimization for a population size of 50 individuals, 50 points  and 300 generations.

Perspective of a result.

For futher information, please visit the Resarch page of this blog. The complete information, for now, is in spanish.

Existen varias maneras de atacar este problema: Ant Colony Optimization.

La idea de este post es hacer una pequeña introducción a los Algoritmos Genéticos AGs y mostrar parte de la lógica que existe detrás de la computación evolutiva. Para esto he programado un simple AGs en RVB y un tutorial donde se explica el tipo de selección, cruce y mutación de este AG en particular.

//TABLA

En esta tabla pueden ver 9 diferentes pruebas del AG con sus resultados. Desde que estamos evaluando la longitud de una ruta, la lista de números que aparece en cada prueba son las longitudes al principio de la optimización (verde) y al final de la optimización (amarillo). Los recuadros de colores representan los diferentes parámetros del AG.

_Initial Population = es el tamaño de la población.

_Natural Selection = especifica cuantas veces el mejor individuo quedará seleccionado en la ruleta (ver tutorial selección natural).

_Crossover Pointer = determina que parte hereda el hijo del padre y la madre. 1/2 significa que heredará la mitad de los genes del padre y la madre (primer el padre).  (ver el tutorial de cruce).

_Mutation Rate = La primera población es aleatoria y este valor determina que tan diferente será. Si pones un valor bajo el algoritmo buscará en un espacio más reducido que si la mutación inicial es total. En principio este valor puede servir para hacer una aproximación al resultado con otro tipo de algoritmo. Por ejemplo generar un individuo que una todos los puntos más cercanos, (esto sería un acercamiento). Luego usar un valor bajo de aleatoriedad para que el AG busqué alrrededor de esta solución.

_Number of Iterations = número de veces que se ejecutará el AG.

_Child Mutation =está es la mutación del individuo. haz pruebas con valores pequeños y luego con valores grandes >10. verás como la convergencia de resultados es completamente diferente (ver tutorial sobre mutación).

_Displace = Este valor tiene que ver con la “presión” que se le puede asignar a la selección natural. (ver el tutorial de selección natural).

Descargas:

Todos los cursos son en castellano orientados básicamente para estudiantes y profesionales sin la necesidad de tener conocimientos en programación y herramientas digitales. Así que no hay excusas de no aprender consejos, pistas o enriquecer los conocimientos ya aprendidos sobre estas tecnologías.

Este año el seminario sera en Madrid entre los días 30 de Junio y 2 de Julio. El último día lo haremos en Segovia para usar las maquinas de corte.

Todos invitados a darse un vuelta y participar.

más información acá: http://www.algomad.org/

Yo estaré encargado del taller de GC avanzado, donde jugaremos con Algoritmos Genéticos y estaré también participando en el taller de fabricación digital.

//

This is the second year that we launch Algomad 2011. It consist in a seminary of digital tools applied to architecture and engineering. The seminary include basic and advanced courses on Grasshopper and GenerativeComponents plus small workshops on Processing and Rhinoscript.

Also we will have two workshops on digital tools and digital fabrication, this one, provided in GC.

All the courses will be in spanish and oriented to students and profesionals without programming knowledge or digital tools.

No excuses to learn basic and advanced GC tips in spanish.

The key days are in Madrid from  june 30 to july 2.

would be great see you in Algomad.

further info here: http://www.algomad.org/

///////////////////

ALGOMAD 2011, fin, hasta el próximo!

Algomad ha acabado hace una semana, y significa el final de un largo período (años) de trabajo y muy pocas horas de sueño. Pensé que sería luego de mi tesis el 27 de enero, pero la rueda venía cargada y no pude ponerle freno. El seminario fue muy familiar, fue disfrutar de mis amigos y de compartir experiencias, conocimientos, ideas, proyectos (por cierto muy diversos), etc. También me sirvió para tranquilizarme y para pensar en mis futuros proyectos, básicamente despejarme la mente y clarificar mis ideas.

Las imágenes del seminarios, Día Sabado:

 

//

Una de las últimas colaboraciones con IDOM-ACXT, consistió en diseñar una fachada para la nueva sede en Madrid. Para el proyecto desarrollé una serie de patrones con el fin de explorar muchas soluciones de manera rápida y barata. El concepto de diseño consistió en una serie de franjas horizontales con motivos Árabes. Las franjas definían dos densidades diferentes de perforación, una para calentar la chapa de acero perforada (corten) y el otra para crear un flujo de ventilación entre la chapa y el edificio.

Cuando empecé a proponer los modelos, empecé con atractores múltiples para controlar el tamaño de los agujeros. Pero el contrato de la fabricación sólo especificaba 2 diferentes punzones (punzón vertical y cruz). por lo que el código se transformó de un patrón libre a un patrón Arábico muy controlado. Este proyecto me obligó a enfrentar sentencias condicionales anidadas, así como gestionar grandes cantidades de curvas, más de 600.000 perforaciones.

Por desgracia no pude ver el montaje de la fachada, sólo este domingo pode tomar las fotos del edificio. He estado muy sorprendido de ver toda la fachada ydetectar las diferencias entre el modelo digital y la vida real. visitar el edificio fue como una clase magistral.

A very small piece of the process:

Una pequeña parte del proceso:

The real building:

//

A finales del año 2007, gané una beca de investigación en I + D de la Fundación Rafael Escolá. Este premio me dio la oportunidad de participar con empresas, tales como IMAR SA y ACXT IDOM. También mejorar mis habilidades en scripting y aprender muchas cosas acerca de cómo pasan las cosas en las grandes empresas.

Este proyecto es una colaboración con IDOM-ACXT. He desarrollado una estructura tipo diagrama de Voronoi sobre una superficie para cubrir el patio del mercado Encants. El proyecto fue preparado para un concurso, pero desgraciadamente el jurado otorgó el primer premio al diseño más tradicional.
Como de costumbre, el diseño va a morir en el render.