Design Through Evolution

Evolutionary Algorithms:

Evolutionary Algorithms are a branch of computational design focused on optimization of design through 'fitness' functions.
In general they are based on the main Evolutionary theory by Charles Darwin.
Its implementation in computation varies tremendously between different applications and there are of course a plethora of applications for evolutionary algorithms in optimization.

Genetic Algorithms:

When looked at the travelling salesman problem.
TSP or as scientist call the NP-Problem.
Where 1 salesman goes through 4 cities located close to each other, he must find the optimal path to travel the least distance.

Simple solution (Brute force method)

 1) Consider city 1 as the starting and ending point.

 2) Generate all (n-1)! Permutations of cities.

 3) Calculate cost of every permutation and keep track of minimum cost permutation.

 4) Return the permutation with minimum cost.

 Time Complexity = Θ(n!)

 This problem through brute force becomes simple to solve with only 4 cities.

 As you have only 4!/2 solutions --- ((4*3*2*1)/2) = 12 solutions.

However when considering more cites for example 10. This problem has then 180,000 permutations to try.
With 30 cities it becomes immeasurably difficult to solve with brute force which requires a approach to test each permutation to find the best outcome.

‍
GA solution

Possibly the most popular type of an evolutionary algorithm is the genetic algorithm.
GA defines a problem and through steps of varied parental population, fitness evaluation, selection process (crossbreeding or mutation) and generating new population through successful candidates tries to solve the given problem.
As such when looked at TSP we consider the fact that from an initial dataset of 100 solutions, it scores the outcomes through a fitness function which in this scenario is least distance travelled.
Then through a selection process (the top successful subset of initial population) it cross breeds the values (genes) to create a new population of 100.
In regards to having enough population variation, there also needs to be mutation involved where random values of the new population will mutate to include more variations.

Through this process, and after (x)number of variations we can then much more quickly find the most optimized pathway for the travelling salesman.

‍

Personal Method of learning:

Though my efforts in learning how to implement an Evolutionary optimization method in design does not try and solve TSP.
Rather, it creates a simple relationship which is explored through the GA method stated above.
In order to understand and create my own variation of GA I used the program Side FX Houdini 18 and the software language VEX (High performance expression language used throughout Houdini).
Through Vex I was able to run the code multi-threaded and simulate 1000s of generations with initial dataset of 50-100 within minutes.
I tested the GA through 4 case studies.

 1) Starting from a rectangle - Keep the area of 1 meter squared while reducing the perimeter.

 2) Starting from a box - Keep the volume of 1 meter cubed while reducing the total surface area.

 3) Starting from basic building formation - reach an optimum volume regardless of surface area.

 4) For an uneven shape - reach the smallest bounding box volume through x, y, z rotations.  

There were few precedents for the Second case study however non for the others as such my GA implementation took longer than expected.

‍

Steps of GA design:

 The steps for creating a GA algorithm with different goals is more or less the same.

 1) Create a population of given amount (for my case it was between 10-100) with varied properties.

 2) For each element of the population create a fitness score.

   a. In regards to Case study 1 - the closer the area to 1 and perimeter of 3.14(PI).

   b. In regards to Case study 2 - the closer the volume to 1 and surface area to 3.14(PI).

   c. In regards to Case study 3 - the closer the volume to 1.

   d. In regards to Case study 4 - the smaller the volume of the bounding box in relation to rotation values of x, y, z.

 3) Using 'argsort' sort the population from best to worst or from fittest to not.

 4) taking the top (50% in my case) and randomly selecting 50 percent of the Genes (point locations, xyz rotations) and crossbreeding or exchanging the values to the other randomly selected 50% of the genes.

 5) This gives me a new population from which I take a mutation rate of 5% of the population and mutate their values randomly within a given range.
(Its important to note that mutation if left too high will basically break the GA system as it will never truly evolve towards the fitness goal.)

 6) Finally using this new dataset return the most successful candidate to view with its fitness score (out of 1000).

 7) Repeat the steps for (x) generation amount.

‍

Results:

Case Study 1:

As expected - Mutation plays a large role in finding the optimal design outcome.
However due to the fact that it was already understood that a circle will have the smallest perimeter when compared to its area the fitness function has an ideal perimeter or PI from the beginning.

‍

Case Study 2:

Case Study 3:

For case study 3 I found it interesting that rather than keeping its form its slowly increasing in height to meet the volume required. I believe there to be a coding error but an interesting accident nevertheless.

‍

Case Study 4:

In this instance I had to rework the entire code to focus on parameter space rather than exchanging point attributes. For this to work it was important for me to store the rotational values in each axes on each element.
Then rather than evaluating the fitness model of the rotational values I was only calculating the score for the volume of the bounding box.
Once sorted I could simply take 2 or the 3 rotational values with the highest score and generate my new population.

Interesting note, as sometimes while going through the generations there are one or two moments when the system actually returns the most ideal score or 1000.
However in this occasion I think there needs to be a if statement to stop the generation at this point and to simply return the best canditate rather than use the perfect score candidate and continue generating a new population.
Though I can understand that rather than 1 ideal outcome sometimes the requirement is to generate a family of close ideals.

‍

Reference Links:

 https://natureofcode.com/book/chapter-9-the-evolution-of-code/

 Daniel Shiffman - The nature of Code

 I highly recommend buying his book (its free or with donation) as he covers all you need to know when learning to code initially.

‍

 https://www.youtube.com/watch?v=8-7UIMwA3f8

 Junichiro Horikawa - Implemented Daniel Shiffman's code through python. In general also a great source for coding procedural designs.

‍

 https://forums.odforce.net/topic/43233-genetic-algorithms-in-houdini/

 Niels Provos - Implemented a variation of GA through PDG and Houdini whereas he looks into the second case study.

‍