Generative Urban Design through Genetic Algorithms

An urban centre is an open system involved almost an infinite number of parameters looking the right balance. It's no coincidence cities have the same problems: Traffic jams, Pollution, Crime and Terrorism, Resource management, Etc.

Resolve problems in complex systems is not a matter of luck and in most cases, intuition will pick a wrong solution, because a complex system behaves in many ways at the same.

Apply traditional linear solutions to complex systems is not the right answer.

The aging process stop the interaction between some different parts of the city. The land is transformed, the trade is modified and commerce slowly begin to decline with homes and urban infrastructure. Social and economic interactions in urban areas are so complex that intuition or experience will not able to prevent modern city problems.

Cities were planned vertically, which means the use of land and their element relations in the city were determined a priori. Urbanist and planners determined where the most important shopping streets should be, commerce, squares, etc. Nevertheless, these guidelines have not been able to understand the interactions and relationships that occur in the urban area. Therefore, The urban aging process over time have marginalized and declined some areas, ghettos had been created and pollutions problems had been emerged.

The new city planning aims to rescue these areas, modifying urban regulations in order to revitalize and improve quality relationships. However, if the planning is done again with the intuition that was made at the beginning, the new urban areas will expose the aging process again. Because, the new plan will be also surpassed by the emerging behavior that exist between the social and commercial relations.

Jay Wright Forrester and Christopher Alexander propose the use of generative tools in urban planning, rather than applying intuitive designed models.

The design process is divided in 3 steps:

  1. Generative infrastructure (buildings, roads, power supplies, etc.)
  2. Agent simulation on the proposed infrastructure
  3. Evaluate


THE TRAVELLING SALESMAN PROBLEM

This research takes the Travelling Salesman Problem (TSP) as start point to purpose a generative urban design model optimized through genetic algorithms. The model will search for an optimized route to link different areas, purpose building densities and orientations. The buildings volumes is related each other spatially point of view. It is possible to recognize squares, streets hierarchy and open areas such us parks.

The TSP is defined as a combinatorial problem which consist in to find the correct order of points (areas) to achieve the shortest path. The space search is not noisy as other kind of problems, but expose a vast number of possibilities. The space search is defined by the factorial number of points (areas) to analyze:

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

  • With 6 points exist 720 combinations.
  • With 20 points exist 2.432.902.008.176.640.000 combinations.

If each of these combination is tested at one millisecond, it will take: 77.146.816 years to find the best solution, yet a Genetic Algorithm model is a good candidate to tackle this problem.


GENETIC ALGORITHM PARAMETERS
  • Fitness Function: 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)
  • Codification: A list of points
  • Type of problem: combinatorial
  • Number of generations: > 100
  • Population size: 20 individuals
  • Natural selection: Roulette Wheel, scaled by non-polinomic function.
  • Crossover: One-point crossover, 50%.
  • Mutation: Swap bit, 0.01%.


Chromosome Type

Each individual in the population is defined by chromosome with a single list of points:

index: 0 index: 1 index: 2 index: n ...
P1(x, y, z) P2(x, y, z) P3(x, y, z) Pn(x, y, z)


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: index = ([(bestInd / dist) * (pointer / i + 1)] - displace)

The displace parameter controls the pressure in further populations when the difference from the highest ranked individual with the lowest ranked individual is minimum.

The blue curve displace: 5. This means that only the highest 10 ranked individuals have a chance to be selected for crossover and mutation. In the other hand, the green curve displace: 0. All individuals have a chance to be selected for the crossover and mutation.

high pressure (blue curve) in natural selection implies a reduction in the search area, a quick result convergence but with the problem to find only local solutions. In the opposite, a lower pressure (green curve) the search area is bigger and the convergence can take long time and also with the problem to find only local solutions. The correct answer is to find the right balance in the displace parameter.


Crossover

A single point crossover is implemented. It's necessary to check the copied genes to the offspring to avoid repeated data. For example if the Parent A inherits the first half genes, the remaining genes from Parent B are checked.

Crossover diagram


Mutation

The mutation consist in swap two genes in the offspring chromosome.

Mutation diagram



RESULTS



Optimization curve for 300 generations



The model applied on a surface



Examples of generations: Sequence, the difference between generations is minimum when the algorithm is close to global minimum results



close view to results



0 Comments:

Add a comment