Pyevolve | Terra Incognita

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.

25/03/2009 by Christian S. Perone

Genetic Algorithms, genetic programming, News, Pyevolve, Python, Time Waste

Genetic Algorithms on cellphones ! Pyevolve on Nokia N73 (Symbian + PyS60)

Hello ! This is the 2nd post related to the Pyevolve on portable devices, the first was in the Sony PSP here and the PoC of Pyevolve solving the TSP problem with a graphical output of best individuals on the Sony PSP screen. Now, it’s time to go further and run Pyevolve into the most portable device used by us, the cellphone.

Using the new version of the PyS60, the release 1.9.1, which comes with the new amazing 2.5.1 Python core, I’ve executed the Pyevolve with no problem, and I was very surprised by the performance of the GA on the Nokia N73, the GA I’ve ran is the minimization of one of the De Jogn’s test suite functions, the Sphere function, the function is very simple and I’ve used 5 real variables between the interval of [-5.12, 5.12], the Gaussian Real Mutator and the Single Point Crossover of the Pyevolve framework. Also I’ve set a population size of 80 individuals and the mutation rate of 2% and crossover rate of 90%.

After 18 generations (about 8 seconds), the GA ended with the best score of 0.0, representing the optimal minimization of the De Jong’s Sphere function.

Follow some screenshots of the adventure (click on the pictures to enlarge):

How to install Pyevolve on the PyS60 ?

1) First, you need to install the PyS60 for your Symbian platform. Here is the installation manual. The order of the installation is: Python Runtime for S60, Python Script Shell and PIPS Library.

2) Then, you must create a directory on your Memory Card, inside the “Python” directory, named “Lib”, and inside this directory, you copy the “pyevolve” folder. The absolute folder structure will be like this:

MemoryCard:\Python\Lib\pyevolve

Some features of the framework will not work, like the some DB Adapters, however, the GA core is working really good. I’ve used the Pyevolve subversion release r157, but it should works with the 0.5 release too. I’ve not finished the documentation of the new release, I’m working on some features yet.

Here is the source code I’ve used to minimize the De Jong’s Sphere function:

import e32
print "Loading Pyevolve modules...",
e32.ao_yield()

from pyevolve import G1DList, GSimpleGA
from pyevolve import Initializators, Mutators, Consts

print " done !"
e32.ao_yield()

def sphere(xlist):
   n = len(xlist)
   total = 0
   for i in range(n):
      total += (xlist[i]**2)
   return total

def ga_callback(ga_engine):
   gen = ga_engine.getCurrentGeneration()
   best = ga.bestIndividual()
   print "Generation %d - Best Score: %.2f" % (gen, best.score)
   e32.ao_yield()

   return False

if __name__ == "__main__":

   genome = G1DList.G1DList(5)
   genome.setParams(rangemin=-5.12, rangemax=5.13, bestRawScore=0.00, roundDecimal=2)
   genome.initializator.set(Initializators.G1DListInitializatorReal)
   genome.mutator.set(Mutators.G1DListMutatorRealGaussian)

   genome.evaluator.set(sphere)

   ga = GSimpleGA.GSimpleGA(genome)
   ga.setMinimax(Consts.minimaxType["minimize"])
   ga.setGenerations(100)
   ga.setMutationRate(0.02)
   ga.terminationCriteria.set(GSimpleGA.RawScoreCriteria)
   ga.stepCallback.set(ga_callback)

   ga.evolve()

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

You can note the use of the module “e32” of the PyS60, this is used to process pending events, so we can follow the statistics of current generation while it evolves.

I hope you enjoyed this work, the next step is to port the TSP problem to cellphone =)

Some time ago I’ve asked Guido van Rossum on the Google Moderator about the future of Python for mobile phones (aka PyS60), and here is the full answer from him:

I’m hopeful, but concerned that Java has cornered this market. For example, the Android development kit is extremely slick but only supports Java at the moment. There’s no doubt about which is the dominant app development language on most mobile platforms, including S60 and anything Symbian-based. In the long run I expect Python to just happen on mobile devices, as increases in disk space will allow the set of pre-installed tools to grow. In the mean time I see a bigger role for Python server-side, for example there are iPhone apps backed by services written in Python running on App Engine (and probably also apps backed by Python running on other server platforms).

Guido van Rossum, San Francisco Bay Area

Well, I think that with this new version of PyS60, with the 2.5.1 core, the Python on mobiles can be very useful and productive. Recently, Nokia have signed a loan agreement with the European Investment Bank (EIB) to the tune of €500 million ($623.9 million). According to Reuters, the five-year loan will be used in part to “finance software research and development (R&D) projects Nokia is undertaking during 2009-2011 to make Symbian-based smartphones more competitive.” So I’m with great expectations with this new investment on Symbian smartphones and with the future possibilities of the PyS60.

21/03/2009 by Christian S. Perone

Genetic Algorithms, News, Pyevolve, Time Waste

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()

10/03/2009 by Christian S. Perone

Genetic Algorithms, Pyevolve, Python

Rosenbrock’s banana function and friends

This post is a report of an optimization test suite applied to Pyevolve GA Core.

I’m writing a paper about Pyevolve and I’ve done some tests on the GA quality of Pyevolve with must common optimization test functions: Schaffer, Rastringin, Sphere, Ackley and the absolute GA-hard Rosenbrock. Follows in the end of the post, the results of the trials, I’ve exported the latex formulae as images.

The only function that the GA had some trouble (it failed to find the global minima in 3 of 10 trials, the “fail” term means that it had not found an optimal solution for 5.000 generations) was the Rosenbrock’s function with 20 variables, also known as Rosenbrock’s banana function due the dinstinctive shape of the contour lines, here is the 3D plot with 2 variables.

As Wikipedia says,

This function is often used to test performance of optimization algorithms. The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial, however to converge to the global minimum is difficult.

However, this behavior was not unexpected, since we can note the same on the research of [1], [2], [3] and [4], among other many papers.

I think this trial results brings more reliability to the framework, when the Pyevolve paper was published, I’ll post it here.

[1] Seredynski, Franciszek, et. al. (2003). “Function Optimization with Coevolutionary Algorithms”, in International Intelligent Information Processing and Web Mining Conference.

[2] Hiroyasu, Tomoyuki, et. al. (1999). “Distributed Genetic Algorithms with Randomized Migration Rate”, IEEE Proceedings of Systems, Man and Cybernetics Conference SMC’99, Vol. 1, pp. 689-694.

[3] Bouvry, Pascal, et. al. (1997). “Distributed evolutionary optimization in Manifold: the Rosenbrock’s function case study”, Duke University.

[4] Panait, Liviu (2002). “A comparison of two competitive fitness functions”, in GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference.

06/03/2009 by Christian S. Perone

Genetic Algorithms, Pyevolve, Python

Pyevolve on Sony PSP ! (genetic algorithms on PSP)

Sony PSP can be more interesting than funny sometimes. Few people know about the potential of the PSP port of Stackless Python 2.5.2. This great port of python was done by Carlos E. and you can find more information about the progress of the port on his blog.

Well, I’ve tested the Pyevolve GA framework on the Stackless Python for PSP and for my surprise, it worked without changing one single line of code on the framework due the fact of Pyevolve has been written in pure Python (except the platform specific issue like the Interactive Mode, but this issue is automaticly disabled on unsupported platforms).

So now, we have Genetic Algorithms on PSP.

Follow some screenshots (click to enlarge):

The GA running on the PSP screenshot is the minimization of the Sphere function.

Here is the steps to install Pyevolve on PSP:

PSP Stackless Python Installation

1) First, create a directory called “python” on your PSP under the “/PSP/GAME” and the directory structure “/python/site-packages/” on the root of your memory stick (this last directory will be used to put Pyevolve later).
2) Copy the EBOOT.PBP and the python.zip files to this created directory;

Pyevolve Installation

3) Download the Pyevolve source and copy the directory called “pyevolve” to the created directory “/python/site-packages/”, the final directory structure will be: “/python/site-packages/pyevolve”

Ready ! Now you can import Pyevolve modules inside scripts on your PSP, of course you can’t use the graphical plotting tool or some DB Adapters of Pyevolve, but the GA Core it’s working very well.

Here is some basic usage of PSP Stackless Python port. I’ve used the psp2d module to show the information on screen. When I got more time, I’ll port the visualization of the TSP problem to use the psp2d, it will be nice to see Traveling Salesperson Problem running with real-time visualization on PSP =)

Pyevolve: the effect of Linear Scaling

There’s an interesting graph in Pyevolve which is a heat-like graph of the population raw and fitness scores. In this graph you can note the effect of Linear Scaling over the scores, the raw scores graph is in left and the fitness scaled scores is in the right, this plot uses the Gaussian interpolation method.

This graph feature is very interesting to study the effects of selections and scaling schemes and even to see the propagation of best individuals on the population while evolving, I think this graph should be more explored.

02/03/2009 by Christian S. Perone

Pyevolve, Python

Good news: IronPython and Jython compatibility !

Good news, I’ve tested Pyevolve 0.5 with the IronPython 2.0.1 and Jython 2.5b1, and the framework is working perfect (besides the performance loss when comparing with CPython 2.5 and 2.6). The only feature that do not worked is the dump of statistics with the sqlite3, sine there is no sqlite3 on the default install of Jython and IronPython. To Pyevolve work on IronPython, you must install the zlib module for IronPython and import your Python modules like this:

import sys
sys.path.append(r"c:\python25\lib")

With this compatibility issue, you can use Pyevolve on your .NET platform or in your Java applications.

16/02/2009 by Christian S. Perone

Pyevolve, Python

Pyevolve profiling dot graph

I’ve created a profiling dot graph of the pyevolve_example15_rosenbrock.py with the Gprof2Dot, this Pyevolve example is the minimization of the Rosenbrock function with 20 variables.

I’ve created that graph to show the call structure of Pyevolve, as you can see, the accumulation in FunctionSlot applyFunctions method is the effect of the use of FunctionSlot use in many operations like scaling, selection, evaluation, crossover and mutation.

14/02/2009 by Christian S. Perone

Terra Incognita

Tag: Pyevolve