Computational Creativity and Evolutionary 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

Multiple Runs

Crossover

Applications

NP complete problems:

Easy to check an answer but too many possible solutions

  • Large scale optimisation algorithms
  • Transport and routing
  • Scheduling
  • Bioinformatics

Defining Creativity

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

Evolving Circuits

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



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
download link

Applications

  • Robotics
  • Animation
  • Computer games
  • In silico biology

Evolutionary Art

  • Evolve music, images or animation
  • Aesthetic fitness

GENR8

Electric Sheep

Issues

  • Do objectives capture aesthetics?
  • How to quantify preference
  • Assumptions of convergence
  • Collective mediocrity
  • Algorithmic art

The Painting Fool

The Painting Fool

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.

Evolved Designs

Shinkansen

Shinkansen

NASA Antenna

Fibre Optics

The Importance of Mapping

Issues with Direct Mappings

  • Shape not smooth or contains small holes
  • Scales poorly
  • Parents being valid doesn't guarantee valid children

Direct Mapping (Voxels)

Buildable Objects by Pollack and Funes (1999)

Qualities of a Good Mapping:

  • Hierarchy, modularity and regularity
  • Generates valid designs
  • High locality

Parametric Design

  • Rapid prototyping technique
  • Define the relationships between components
  • Originally in Sketchpad

Why Parametric?

  • 3D printing
  • Adoption in Aeronautics and Architecture
  • Programmers get it for free
  • Easy to evolve

Grasshopper

Turning Torso (Calatrava)

Messe Halle (Herzog & De Meuron)

Messe Halle (Herzog & De Meuron)

Rolex Learning Center (SANAA)

Open-Vehicle Sketch Pad (openVSP)



link

OpenVSP

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

Conclusions

  • If no exact optimiser solves your problem then use an EA
  • EAs capable of creative design solutions
  • Parametric models are easily evolved
  • EAs capable of active design