The Interactive Robotic Painting Machine !

I’m glad to announce a project created by Benjamin Grosser called “Interactive Robotic Painting Machine“. The machine uses Python and Pyevolve as it’s Genetic Algorithm core, the concept is very interesting:

What I’ve built to consider these questions is an interactive robotic painting machine that uses artificial intelligence to paint its own body of work and to make its own decisions. While doing so, it listens to its environment and considers what it hears as input into the painting process. In the absence of someone or something else making sound in its presence, the machine, like many artists, listens to itself. But when it does hear others, it changes what it does just as we subtly (or not so subtly) are influenced by what others tell us.

Read more about the project in the Benjamin Grosser website.

 

News: Using genetic algorithms to optimise current and future health planning

From a publication of 28/10/2010, of the authors Saoshi Sasaki, Alexis J Comber, Hiroshi Suzuki and Chris Brunsdon:

Background

Ambulance response time is a crucial factor in patient survival. The number of emergency cases (EMS cases) requiring an ambulance is increasing due to changes in population demographics. This is decreasing ambulance response times to the emergency scene. This paper predicts EMS cases for 5-year intervals from 2020, to 2050 by correlating current EMS cases with demographic factors at the level of the census area and predicted population changes. It then applies a modified grouping genetic algorithm to compare current and future optimal locations and numbers of ambulances. Sets of potential locations were evaluated in terms of the (current and predicted) EMS case distances to those locations.

Results

Future EMS demands were predicted to increase by 2030 using the model (R2=0.71). The optimal locations of ambulances based on future EMS cases were compared with current locations and with optimal locations modelled on current EMS case data. Optimising the location of ambulance stations locations reduced the average response times by 57 seconds. Current and predicted future EMS demand at modelled locations were calculated and compared.

Conclusions

The reallocation of ambulances to optimal locations improved response times and could contribute to higher survival rates from life-threatening medical events. Modelling EMS case ‘demand’ over census areas allows the data to be correlated to population characteristics and optimal ‘supply’ locations to be identified. Comparing current and future optimal scenarios allows more nuanced planning decisions to be made. This is a generic methodology that could be used to provide evidence in support of public health planning and decision making.

Read the original paper here.

Evolutionary Computation

There is a portuguese version of this post.

Evolutionary computing (EC) has been widely used in recent years, and every year there are new applications for the techniques developed, despite being a relatively new area, few people are giving attention to that (at least in my vision and I will explain why) probably will have a promising and revolutionary future in relation to how we can generate innovation and even learn from it, especially as it relates to Evolutionary Algorithms (EAs).

Read More

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.

Travelling Salesman on Sony PSP using Stackless Python + Pyevolve

This is my first PoC of the Travelling Salesman Problem on PSP, since I’ve installed the Pyevolve on the Sony PSP,  I can optimize any problem while using the graphical interface of PSP (in that problem I’m using the 2D functions to plot the cities and the path) to show results in real-time. Here is the video, the quality is very low, I’ve used my cellphone 🙂

Here is the source code I’ve used, the Pyevolve version of this example is the development version r166, which in the future will be the 0.6 final release (I’m working on many new features yet, so it will take time to release), however, this PoC should work on 0.5 release too:

import psp2d, pspos

WHITE_COLOR = psp2d.Color(255,255,255)
CLEAR_COLOR = psp2d.Color(0,0,0,255)
RED_COLOR   = psp2d.Color(255, 0, 0)

cm     = []
coords = []
CITIES = 20

pspos.setclocks(333,166)
psp_scr  = psp2d.Screen()
psp_font = psp2d.Font('font.png')
psp_scr.clear(CLEAR_COLOR)
psp_font.drawText(psp_scr, 0, 5, "Loading Pyevolve modules...")
psp_scr.swap()

from pyevolve import G1DList
from pyevolve import GSimpleGA
from pyevolve import GAllele
from pyevolve import Mutators
from pyevolve import Crossovers
from pyevolve import Consts

from random import shuffle as rand_shuffle, randint as rand_randint
from math import sqrt

def cartesian_matrix(coords):
   """ A distance matrix """
   matrix={}
   for i,(x1,y1) in enumerate(coords):
      for j,(x2,y2) in enumerate(coords):
         dx, dy = x1-x2, y1-y2
         dist=sqrt(dx*dx + dy*dy)
         matrix[i,j] = dist
   return matrix

def tour_length(matrix, tour):
   """ Returns the total length of the tour """
   total = 0
   for i in range(CITIES):
      j      = (i+1)%CITIES
      total += matrix[tour[i], tour[j]]
   return total

def write_tour_to_img(coords, tour):
   """ The function to plot the graph """
   psp_scr.clear(CLEAR_COLOR)
   for i in range(CITIES):
      j      = (i+1)%CITIES
      city_i = tour[i]
      city_j = tour[j]
      x1, y1 = coords[city_i]
      x2, y2 = coords[city_j]
      psp_scr.drawLine(int(x1), int(y1), int(x2), int(y2), WHITE_COLOR)
      psp_font.drawText(psp_scr, int(x1)+7, int(y1)-5, str(i))
      psp_scr.fillRect(int(x1), int(y1), 6, 6, RED_COLOR)

   psp_scr.swap()

def G1DListTSPInitializator(genome, **args):
   """ The initializator for the TSP """
   lst = [i for i in xrange(genome.getListSize())]
   rand_shuffle(lst)
   genome.genomeList = lst

def evolve_callback(ga_engine):
   """ Callback called every generation by Pyevolve """
   write_tour_to_img(coords, ga_engine.bestIndividual())
   return False

def main_run():
   global cm, coords

   width, height = psp_scr.size
   coords = [(rand_randint(0, width),rand_randint(0, height))
                 for i in xrange(CITIES)]
   cm     = cartesian_matrix(coords)

   setOfAlleles = GAllele.GAlleles(homogeneous=True)
   range_allele = GAllele.GAlleleRange(0, len(coords)-1)
   setOfAlleles.add(range_allele)

   genome = G1DList.G1DList(len(coords))
   genome.setParams(allele=setOfAlleles)

   genome.evaluator.set(lambda chromosome: tour_length(cm, chromosome))
   genome.mutator.set(Mutators.G1DListMutatorSwap)
   genome.crossover.set(Crossovers.G1DListCrossoverOX)
   genome.initializator.set(G1DListTSPInitializator)

   ga = GSimpleGA.GSimpleGA(genome)
   ga.setMinimax(Consts.minimaxType["minimize"])
   ga.setGenerations(300)
   ga.setPopulationSize(200)
   ga.setCrossoverRate(1.0)
   ga.setMutationRate(0.1)
   ga.stepCallback.set(evolve_callback)

   ga.evolve()

if __name__ == "__main__":
   main_run()

Pyevolve: work on the distributed Genetic Algorithm support

I’m currently working on the distributed GA support for the Pyevolve framework, the approach I’m using to network communication (individuals migration) is the hightweigh and unreliable UDP protocol, due it’s performance (for lan/wan) and broadcasting compatibility.

The distributed GA will have options to create the logical migration topology for the connected nodes (islands of evolution), migration schemes, migration rates and other parameters.