Evolutionary Algorithms and Design

Jonathan Byrne

Natural Computing Research and Applications Group

University College Dublin

Ireland

Infinite Monkey Theorem

"If an infinite number of monkeys randomly hit keys on a typewriter for an infinite amount of time then they would almost surely write the complete works of Shakespeare"

Although theoretically true, the internet has so far shown otherwise.

Brute Force Approach

"To be or not to be that is the question"
  • Probability of typing 't': 1/27
  • Probability of typing 'to' (1/27 * 1/27): 1 in 729
  • Probability of typing entire phrase (1/27 ^ 39): 1 in 66,555,937,033,867,822,607,895,549,241,096,482,953,017,615,834,735,226,163

How Long?

If a computer processed a million combinations a second:

2,110,474,918,628,482,452,051,482,408,710,568,333,111,923 years

Estimated age of the universe: 13,750,000,000 years

Evolutionary Algorithms (EA)

  • Heuristic Optimiser
  • Inspired by biological evolution

The Algorithm:

Generate an initial random population then:

  1. Evaluate (fitness function)
  2. Select (fitness pressure)
  3. Crossover (heredity)
  4. Mutate (variation)
  5. Repeat

Evaluate

Target phrase: that

Population:

  • town (1)
  • flat (2)
  • pond (0)
  • this (2)

Selection

Tournament Selection:

Crossover

Mutation

  • "town" -> "toan"

Example

The Nature of Code by Daniel Schiffman

Link to code

Applications

NP complete problems:

Easy to check an answer but too many possible solutions

  • Large scale optimisation algorithms
  • Transport and routing
  • Scheduling
  • Bioinformatics
Since design problems defy comprehensive description and offer an inexhaustible number of solutions the design process cannot have a finite and identifiable end. The designer’s job is never really done and it is probably always possible to do better.

B. Lawson.

Evolving a Vehicle

Car GA

Electricity Pylon Design

RIBA Competition

  • Royal Institute of British Architects design competition
  • Pre-specified loading conditions
  • Use structural analysis as fitness function

Loading Constraints

Example Loading

Wind Loading

Ice Loading

Wind and Ice Loading

Multi-objective Optimisation

  • Conflicting Objectives
  • Requires a trade off

Lift vs Drag

Initial Generation

Evolving the Pareto Front

Final Generation

Optimised Blended Wing Body Designs

Optimised Cessna 182 Designs

Optimised MiG 21 Designs

Applications

Shinkansen

Shinkansen

NASA Antenna

Fibre Optics

Questions?