Genetic Algorithms

Genetic Algorithms, News, Science

Meanwhile, at the Hall of Justice!

UPDATE 05/10: there is an article in the Physorg too.

Sometimes we face new applications for EC, but for this I was not expecting, from Eurekalert:

WASHINGTON, Oct. 5 — Criminals are having a harder time hiding their faces, thanks to new software that helps witnesses recreate and recognize suspects using principles borrowed from the fields of optics and genetics.

(…)

His software generates its own faces that progressively evolve to match the witness’ memories. The witness starts with a general description such as “I remember a young white male with dark hair.” Nine different computer-generated faces that roughly fit the description are generated, and the witness identifies the best and worst matches. The software uses the best fit as a template to automatically generate nine new faces with slightly tweaked features, based on what it learned from the rejected faces.

“Over a number of generations, the computer can learn what face you’re looking for,” says Solomon.

Read the full article here.

by Christian S. Perone
Genetic Algorithms, Pyevolve, Python

n-queens problem using Pyevolve

Last night I’ve read a post on Reddit written by Matthew Rollings showing a code in Python to solve Eight Queens puzzle using EA. So I decided to implement it in Python again but this time using Pyevolve, here is the code:

from pyevolve import *
from random import shuffle

BOARD_SIZE = 64

def queens_eval(genome):
   collisions = 0
   for i in xrange(0, BOARD_SIZE):
      if i not in genome: return 0
   for i in xrange(0, BOARD_SIZE):
      col = False
      for j in xrange(0, BOARD_SIZE):
         if (i != j) and (abs(i-j) == abs(genome[j]-genome[i])):
            col = True
      if col == True: collisions +=1
   return BOARD_SIZE-collisions

def queens_init(genome, **args):
   genome.genomeList = range(0, BOARD_SIZE)
   shuffle(genome.genomeList)

def run_main():
   genome = G1DList.G1DList(BOARD_SIZE)
   genome.setParams(bestrawscore=BOARD_SIZE, rounddecimal=2)
   genome.initializator.set(queens_init)
   genome.mutator.set(Mutators.G1DListMutatorSwap)
   genome.crossover.set(Crossovers.G1DListCrossoverCutCrossfill)
   genome.evaluator.set(queens_eval)

   ga = GSimpleGA.GSimpleGA(genome)
   ga.terminationCriteria.set(GSimpleGA.RawScoreCriteria)
   ga.setMinimax(Consts.minimaxType["maximize"])

   ga.setPopulationSize(100)
   ga.setGenerations(5000)
   ga.setMutationRate(0.02)
   ga.setCrossoverRate(1.0)

   # This DBAdapter is to create graphs later, it'll store statistics in
   # a SQLite db file
   sqlite_adapter = DBAdapters.DBSQLite(identify="queens")
   ga.setDBAdapter(sqlite_adapter)

   ga.evolve(freq_stats=10)

   best = ga.bestIndividual()
   print best
   print "\nBest individual score: %.2f\n" % (best.score,)

if __name__ == "__main__":
   run_main()

It tooks 49 generations to solve a 64×64 (4.096 chess squares) chessboard, here is the output:

Gen. 0 (0.00%): Max/Min/Avg Fitness(Raw) [20.83(27.00)/13.63(7.00)/17.36(17.36)]
Gen. 10 (0.20%): Max/Min/Avg Fitness(Raw) [55.10(50.00)/39.35(43.00)/45.92(45.92)]
Gen. 20 (0.40%): Max/Min/Avg Fitness(Raw) [52.51(55.00)/28.37(24.00)/43.76(43.76)]
Gen. 30 (0.60%): Max/Min/Avg Fitness(Raw) [67.45(62.00)/51.92(54.00)/56.21(56.21)]
Gen. 40 (0.80%): Max/Min/Avg Fitness(Raw) [65.50(62.00)/19.89(31.00)/54.58(54.58)]

        Evolution stopped by Termination Criteria function !

Gen. 49 (0.98%): Max/Min/Avg Fitness(Raw) [69.67(64.00)/54.03(56.00)/58.06(58.06)]
Total time elapsed: 39.141 seconds.

And here is the plots generated by the Graph Plot Tool of Pyevolve:

fig1

fig3

fig5

fig8

by Christian S. Perone
Genetic Algorithms, Time Waste

The Darwin’s cake experiment

Suppose that you are the owner of a famous bakery, and you have a recipe of a really delicious cake which is well known and desired by many of your clients. Is in this scene that enters the Darwin’s cake experiment.

Suppose that you also have nearly 1.000 clients (you are very famous hehe) that you can send new cakes done by you with different amounts of ingredients and these same clients will return to you how much they liked the new cake recipe in a rating between 1 and 10 in a way to know what is the most popular desired taste.

So I was thinking, this is an optimization problem. Your problem is to find the almost “perfect” amouts of each ingredient of the cake for you most popular clients taste. If we use a Genetic Algorithm to solve this optimization problem, we can imagine some like this:

Create, let’s say, 1.000 cakes (the individuals) with random amounts of ingredients and send them to clients evaluation (fitness function), and then take the rating returned by your clients (the fitness). So you can now create a new generation of cake recipes by applying the genetic operators on the the first generation based on the clients ratings and so on.

This is just a joke, but if a big company decides to make it real, I think it’ll be very funny and they will create the first computer-generated cake !

I was thinking too, if things like this can be done to chemical products; you can do experiments in an automated way, this is a very interesting research field for robotics and AI =)

by Christian S. Perone
Genetic Algorithms, News, Science

Evolving autopilots could boost space slingshots

From the NewScientist article:

COULD space probes use genetic algorithms as autopilots to help them navigate the complexities of the solar system?

Deep-space missions such as NASA’s veteran z Voyager probes often rely on gravity assists. They use a planet’s gravitational field as a slingshot, which allows them to visit other celestial bodies without using up too much fuel. But programming a probe with its trajectory years ahead of time can be a problem, says Ian Carnelli of the European Space Agency in Noordwijk, the Netherlands.

Missed launch windows, unexpected winds and misbehaving rockets mean that probes hardly ever leave Earth in the planned position or velocity, and radiation pressure from solar flares can perturb the craft’s course in deep space. If the probe is out of position when it starts a gravity-assisted manoeuvre, the slingshot will be inefficient.

In the Journal of Guidance, Control and Dynamics (DOI: 10.2514/1.32633), Carnelli and colleagues Bernd Dachwald and Massimiliano Vasile suggest that a probe could navigate for itself using a genetic algorithm (GA).

(…)

Carnelli likens this to hundreds of virtual pilots flying simulated spacecraft, with the GA disposing of those that waste fuel or steer a slow course, while “breeding” the best ones together, a process akin to natural selection. “After hundreds of generations of the GA you obtain a ‘pilot’ that is an extremely good performer – able to fly the assist trajectory that uses the least propellant while reaching the next target planet faster,” he says. Carnelli has run successful simulations of GA-enabled missions to Mercury via Venus, and Pluto via Jupiter.

(…)

Read the full article.

by Christian S. Perone
Genetic Algorithms, News, Science

Digital Archeology Reveals Dinosaur Details using Genetic Algorithms

From the article of LiveScience.com:

The pick and shovel can go only so far in digging up details about dinosaurs. Now supercomputers are revealing knowledge about their anatomy otherwise lost to history.

(…)

For example, if the muscles connected to the thigh bone of a Tyrannosaurus rex were short, that would suggest it was angled vertically as in humans. However, if they were very long, it could have been angled horizontally as in birds.

dino

Initial attempts to randomly decipher which pattern of muscle activation works best result almost always in the animal falling on its face, explained computer paleontologist Peter Falkingham at the University of Manchester. But the scientists employ “genetic algorithms,” or computer programs that can alter themselves and evolve, and so run pattern after pattern until they get improvements.

Eventually, they evolve a pattern of muscle activation with a stable gait and the dinosaur can walk, run, chase or graze, Falkingham said. Assuming natural selection evolves the best possible solution as well, the modeled animal should move similar to its now extinct counterpart. Indeed, they have achieved similar top speeds and gaits with computer versions of humans, emus and ostriches as in reality.

Read the full article.

by Christian S. Perone
Genetic Algorithms, News, Science

Computer Program Self-Discovers Laws of Physics

From the Wired article:

Initially, the equations generated by the program failed to explain the data, but some failures were slightly less wrong than others. Using a genetic algorithm, the program modified the most promising failures, tested them again, chose the best, and repeated the process until a set of equations evolved to describe the systems. Turns out, some of these equations were very familiar: the law of conservation of momentum, and Newton’s second law of motion.

I’m very happy with this news article, I had a similiar idea some time ago, but little different, I’m currently developing it. While in development I always asked myself if it’ll works, but with this good news, maybe it works, but I’ve many work to do yet =)

Read the full article

UPDATE 08/04: you can read the supplemental materials and the report on the Cornell CCSL site.

by Christian S. Perone
Genetic Algorithms, Pyevolve, pys60, Python

TSP on Nokia N73 using PyS60 and Pyevolve

As I promised on the post about Pyevolve on N73, I’ve ported the TSP problem to run on the cellphone. The script will draw the best individual of every generation on the screen using the PyS60 Canvas API. The quality of the video is very low, I’m using another cellphone with VGA only recording.

When I have time, I’ll release the source-code here in the same post. The TSP code is the same used in PSP, but ported to use the Canvas API of PyS60.

I hope you enjoy.

UPDATE 24/04: the source-code can be downloaded here.

by Christian S. Perone