Travelling salesman problem as a generative model urban, macro scale

Bookmark and Share

A Genetic Algorithm to solve the problem Travelling Sales Problem (TSP) is adapted to find the shortest path from a list of buildings, offering volume and direction of the nearest line on the road. For each of the points where the route passes, there is a volume that represents a building, which is scaled depending on the distance between buildings and focuses depending on the direction of the route. The outcome is a series of volumes related to each other spatially, that creates spaces, which can be recognized as squares, roads, more open and more protected areas.

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 descendant.

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 the result.

For further  information, please visit A.I. IN DESIGN section.

Leave a Reply