Travelling Salesman on Sony PSP using Stackless Python + Pyevolve

这是我第一次PoC的Travelling Salesman Problemon 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 the2D functions城市和阴谋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 thedevelopment versionr166, 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:

进口psp2d pspos WHITE_COLOR = psp2d.Color (255255,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 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 byCarlos 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 theInteractive 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 theSphere 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 theEBOOT.PBPand thepython.zipfiles 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 somebasic usageof PSP Stackless Python port. I’ve used thepsp2dmodule to show the information on screen. When I got more time, I’ll port the visualization of the TSP problem to use thepsp2d, it will be nice to seeTraveling Salesperson Problemrunning with real-time visualization on PSP =)

Related Links

Google Code Project of PSP Stackless Python