Space layout plan is a time consuming complex task yet for experienced professionals. There are many strategies to face this challenge: Define the corridors first and distribute the spaces around them. Define big surface areas to subdivide in the spaces later. No matter, which approach is taken, all methods will deal with surface areas and the space hierarchization.
Stablish space priority is important, because determine capital costs, building operations, maintenance, HVAC energy consumption, etc. For this work a genetic algorithm was implemented to evolve space layout plans to achieve target areas constrained by the building limits and a spatial hierarchization expressed in weights.
The genetic algorithm use the Voronoi diagram as a base for the spatial subdivision and distribution. Voronoi diagrams are often used to analyze space distribution problems and therefore this work could be extrapolated to other problems like, radio emission antennas distribution or restaurant chains distribution.
This is complex for at least these two reasons:
- It's a weight problem, because each space needs different requirements, i.e. orientation, ventilation, square meters, etc.
- It's a multi-objective optimization problem, because all the spaces (rooms) are in a constant fight to find the right position, needed area, view, ventilation, etc. It is not possible to privilege one space with out to decrease the others.
Video: Evolutionary Optimization in Space Floor Layout Plans
GENETIC ALGORITHM ARCHITECTURE
Genetic Algorithm parameters
- Fitness function: Area Difference (subtraction)
- Chromosome: Jagged array type, points and polygons area
- Problem type: Multi-Objective optimization
- Number of generations: 50
- Size of population: 20
- Natural selection: Tournament selection, adjustable pressure (climbing selection)
- Crossover: Single point
- Mutation: Multiply a coordinate by random value, 0.1%
The chromosome is composed by the list of points that represents each space in the planning layout. Each point also controls the different cells in the Voronoi diagram. The complexity emerges since all cells are intrinsically related each other. For example the room A reach the position and area required. The point next to the room A make and adjustment and affect directly the room A properties (position and area), in fact each point affect directly all tangents area. Therefore a good solution is close to a bad one, because is 5 areas reach the right position and target area, then move a point to intend to fit another area, the progress achieved before will be lost and loose the aptitude reached.
The directly affected areas if the red point change position. On the right, the chromosome representation
The fitness function evaluate each cell area (room) against the area objectives table. If the room area minus the objective area is less than the wight specified, then the chromosome is awarded by 1 otherwise 0. The sum of all 1s is divided by 10 to obtain a decimal precision value used as the fitness. As a general rule is not good idea to have integers as fitness values, because the algorithm tends to generalize the problem and the convergence is delayed.
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
tournament selection, with a pressure of 8. For this work a roulette wheel was tested before but without consistent results. A tournament selection with a climbing selection implementation are able to control the pressure during the optimization and keep the diversity in the population, because is a noisy space search. This technique is also very useful when the difference between high and lower ranked individuals is minimum.
Single point crossover was the implemented algorithms. Nevertheless the uniform crossover was also tested but the results were not satisfactory.
offSpring = SinglePtCrossOver(cleanRW(indexDad),cleanRW(indexMom))
The mutation consisted into move a point in the chromosome in a random direction. The step move is very small to keep parents inherited information.
For this work, several plan layouts were optimized through the genetic algorithm, although for this report 3 (with out particular order) examples are shown.
Floor plan 1:
The table shows in the first column the initial room areas. In the second column the objective areas are listed and in the third column the weight per each room. The bigger the number, the less hierarchy. The fourth column shows the final areas after the genetic algorithm optimization. The filled salmon color table cells are the areas that satisfy the required space. The same structure is applied to the other 2 cases. On the right the optimization curve. Floor plans before and after the evolutionary optimization.
Floor plan 5:
The optimization curves show some similarities between the cases: All curves shows a step incremental progression, similar to a staircase section. Also, the curves tendency is close to a straight line. This is a consequence of a noise space search. Floor plans before and after the evolutionary optimization.
Floor plan 6:
The initial and the objective areas, not necessary sum the same amount. This is because in the real world the brief specify the objective areas without consider the building premises. For this particular case, the initial areas sum ~741.5 sqm and the target area 700 sqm. The GA was able to "fit" all areas except the third one for a difference of 40 sqm. Floor plans before and after the evolutionary optimization.