Computational Creativity and Evolutionary Design

Jonathan Byrne

Natural Computing Research and Applications Group

University College Dublin

Ireland

Overview

  • Creativity
  • Evolutionary Algorithms
  • Design Problems
  • Artificial Life and Game A.I.
  • Product Development

Defining Creativity

  • Creativity is subjective
  • "I know it when I see it"

Does not Compute

  • Creativity is a human endeavour
  • A computer only follows the instructions it is given
  • A computer has no insight into design problems

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

Circuit Design

An Evolved Circuit, Intrinsic in Silicon, Entwined with Physics

Adrian Thompson, 1997, Evolvable Systems: From Biology to hardware

Experiment

Used a field-programmable gate array (100 Nodes)

Recognise two distinct inputs

No clock pulse

Result

  • Generation 0-100: nothing
  • Generation 220: recognising input
  • Generation 650: distinguishing input
  • Generation 1400: 50% accuracy
  • Generation 4100:100% accuracy

"A mess of feedback loops"

Redundant Nodes Removed

After Clamping

Applications

  • Adaptive circuitry
  • Generating and breaking existing patents
  • Invention machine- J.R. Koza

Artificial Life

Evolving 3D morphology and behavior by competition

Karl Sims, Artificial Life,Volume 1, 1994

Experiment

Virtual Creatures must survive in a modelled environment

  • Movement tasks and competitive tasks
  • Bodies composed of blocks and springs
  • Sensors for environmental input
  • Different physical environments (water, land)

Results

download link

Game A.I.

Optimising Offensive Moves in Toribash Using a Genetic Algorithm
  • Ragdoll physics engine
  • Turn based game
  • No pre-defined moves

Toribash



link

Basic Attack



link

Single Move Decapitation



link

Tori Gets a Sword



link

Chaining Combo



link

Applications

  • Robotics
  • Animation
  • Computer games
  • In silico biology

Product Design

  • A product can always be optimised
  • Design itself is an evolutionary process
  • E.A. has no preconceptions of a design

Pylon Design

  • Royal Institute of British Architects (RIBA) 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 design objectives
  • Lift versus drag of a wing
  • No perfect solution

Best Lift Maximisation

Best Drag Minimisation

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

Conclusions

  • EAs capable of active design
  • Do not need to be told explicitly what to do
  • Provide multiple design solutions when given vague specifications