Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100755 447 lines (333 sloc) 10.954 kb
134d944 Importing code into GIT
Tomasz bla Fortuna authored
1 #! /usr/bin/env python
2
3 """
4 Alternative implementation of travelling salesman problem
5 that displays solutions in a graphical window, using the
6 pyFLTK widgets (http://pyfltk.sourceforge.net)
7 """
8
77f64f3 Small fixes.
Tomasz bla Fortuna authored
9 try:
10 from fltk import *
11 except ImportError:
12 print "This demo requires fltk installed in order to work!"
13 import sys
14 sys.exit(1)
134d944 Importing code into GIT
Tomasz bla Fortuna authored
15
4b91610 Issue1: Remove psyco / fix fltk (font)
Tomasz bla Fortuna authored
16 try:
17 import psyco
18 except ImportError:
19 psyco = None
134d944 Importing code into GIT
Tomasz bla Fortuna authored
20
21 from threading import Lock
22 from thread import start_new_thread
23 from time import sleep
24
25 from random import random
26 from math import sqrt
27
28 from pygene.gene import FloatGene, FloatGeneMax, FloatGeneRandom
29 from pygene.organism import Organism, MendelOrganism
30 from pygene.population import Population
31
32 width = 500
33 height = 500
34
35 # set the number of cities in our tour
36 numCities = 30
37
38 # tweak these to gen varying levels of performance
39
40 geneRandMin = 0.0
41 geneRandMax = 10.0
42 geneMutProb = 0.1
43 geneMutAmt = .5 # only if not using FloatGeneRandom
44
45 popInitSize = 10
46 popChildCull = 20
47 popChildCount = 100
48 popIncest = 10 # number of best parents to add to children
49 popNumMutants = 0.7 # proportion of mutants each generation
50 popNumRandomOrganisms = 0 # number of random organisms per generation
51
52 mutateOneOnly = False
53
54 BaseGeneClass = FloatGene
55 BaseGeneClass = FloatGeneMax
56 #BaseGeneClass = FloatGeneRandom
57
58 OrganismClass = MendelOrganism
59 #OrganismClass = Organism
60
61 mutateAfterMating = True
62
63 crossoverRate = 0.05
64
65 class CityPriorityGene(BaseGeneClass):
66 """
67 Each gene in the TSP solver represents the priority
68 of travel to the corresponding city
69 """
70 randMin = geneRandMin
71 randMax = geneRandMax
72
73 mutProb = geneMutProb
74 mutAmt = geneMutAmt
75
76 class City:
77 """
78 represents a city by name and location,
79 and calculates distance from another city
80 """
81 def __init__(self, name, x=None, y=None):
82 """
83 Create city by name, randomly generating
84 its co-ordinates if none given
85 """
86 self.name = name
87
88 # constrain city coords so they're no closer than 50 pixels
89 # to any edge, so the city names show up ok in the gui version
90 if x == None:
91 x = random() * (width - 100) + 50
92 if y == None:
93 y = random() * (height - 100) + 50
94
95 self.x = x
96 self.y = y
97
98 def __sub__(self, other):
99 """
100 compute distance between this and another city
101 """
102 dx = self.x - other.x
103 dy = self.y - other.y
104 return sqrt(dx * dx + dy * dy)
105
106 def __repr__(self):
107 return "<City %s at (%.2f, %.2f)>" % (self.name, self.x, self.y)
108
109 if 0:
110 cities = [
111 City("Sydney"),
112 City("Melbourne"),
113 City("Brisbane"),
114 City("Armidale"),
115 City("Woolongong"),
116 City("Newcastle"),
117 City("Cairns"),
118 City("Darwin"),
119 City("Perth"),
120 City("Townsville"),
121 City("Bourke"),
122 City("Gosford"),
123 City("Coffs Harbour"),
124 City("Tamworth"),
125 ]
126
127 if 1:
128 cities = []
129 for i in xrange(numCities):
130 cities.append(City("%s" % i))
131
132 cityNames = [city.name for city in cities]
133
134 cityCount = len(cities)
135
136 cityDict = {}
137 for city in cities:
138 cityDict[city.name] = city
139
140 priInterval = (geneRandMax - geneRandMin) / cityCount
141 priNormal = []
142 for i in xrange(cityCount):
143 priNormal.append(((i+0.25)*priInterval, (i+0.75)*priInterval))
144
145 genome = {}
146 for name in cityNames:
147 genome[name] = CityPriorityGene
148
149 class TSPSolution(OrganismClass):
150 """
151 Organism which represents a solution to
152 the TSP
153 """
154 genome = genome
155
156 mutateOneOnly = mutateOneOnly
157
158 crossoverRate = crossoverRate
159
160 numMutants = 0.3
161
162 def fitness(self):
163 """
164 return the journey distance
165 """
166 distance = 0.0
167
168 # get the city objects in order of priority
169 sortedCities = self.getCitiesInOrder()
170
171 # start at first city, compute distances to last
172 for i in xrange(cityCount - 1):
173 distance += sortedCities[i] - sortedCities[i+1]
174
175 # and add in the return trip
176 distance += sortedCities[0] - sortedCities[-1]
177
178 # done
179 return distance
180
181 def getCitiesInOrder(self):
182 """
183 return a list of the cities, sorted in order
184 of the respective priority values in this
185 organism's genotype
186 """
187 # create a sortable list of (priority, city) tuples
188 # (note that 'self[name]' extracts the city gene's phenotype,
189 # being the 'priority' of that city
190 sorter = [(self[name], cityDict[name]) for name in cityNames]
191
192 # now sort them, the priority elem will determine order
193 sorter.sort()
194
195 # now extract the city objects
196 sortedCities = [tup[1] for tup in sorter]
197
198 # done
199 return sortedCities
200
201 def normalise(self):
202 """
203 modifies the genes to a reasonably even spacing
204 """
205 genes = self.genes
206 for i in xrange(2):
207 sorter = [(genes[name][i], name) for name in cityNames]
208 sorter.sort()
209 sortedGenes = [tup[1] for tup in sorter]
210
211
212
213
214 class TSPSolutionPopulation(Population):
215
216 initPopulation = popInitSize
217 species = TSPSolution
218
219 # cull to this many children after each generation
220 childCull = popChildCull
221
222 # number of children to create after each generation
223 childCount = popChildCount
224
225 # number of best parents to add in with next gen
226 incest = popIncest
227
228 mutants = popNumMutants
229
230 numNewOrganisms = popNumRandomOrganisms
231
232 mutateAfterMating = mutateAfterMating
233
234 class TSPCanvas(Fl_Box):
235 """
236 Implements a custom version of box that draws the
237 cities and journey
238 """
239 def __init__(self, gui, x, y, w, h):
240
241 Fl_Box.__init__(self, x, y, w, h)
242
243 # style the widget
244 self.box(FL_DOWN_BOX)
245 self.color(FL_WHITE)
246
247 # save needed attribs
248 self.gui = gui
249 self.pop = gui.pop
250
251 # best fitness so far
252 self.bestSoFar = 10000000000000000000
253
254 def draw(self):
255
256 Fl_Box.draw(self)
257
258 # now, show the cities and plot their journey
259 self.showJourney()
260
261 def showJourney(self, *ev):
262 """
263 Periodically display the best solution
264 """
265 self.gui.lock.acquire()
266
267 # get the best
268 best = self.gui.best
269
270 fitness = self.gui.fitness
271
272 # get the cities in order
273 order = best.getCitiesInOrder()
274
275 print "best=%s" % fitness
276
277 # draw the city names
278 fl_color(FL_BLACK)
4b91610 Issue1: Remove psyco / fix fltk (font)
Tomasz bla Fortuna authored
279 fl_font(FL_HELVETICA, 16)
134d944 Importing code into GIT
Tomasz bla Fortuna authored
280 for city in order:
281 fl_draw(city.name, int(city.x), int(city.y))
282
283 # choose a colour according to whether we're improving, staying the same,
284 # or getting worse
285 if fitness < self.bestSoFar:
286 fl_color(FL_GREEN)
287 self.bestSoFar = fitness
288 elif fitness == self.bestSoFar:
289 # equal best - plot in blue
290 fl_color(FL_BLUE)
291 else:
292 # worse - plot in red
293 fl_color(FL_RED)
294
295 # now draw the journey
296 for i in xrange(len(order)-1):
297 city0, city1 = order[i:i+2]
298 fl_line(int(city0.x), int(city0.y), int(city1.x), int(city1.y))
299
300 # and don't forget the journey back home
301 fl_line(int(order[0].x), int(order[0].y), int(order[-1].x), int(order[-1].y))
302
303 self.gui.lock.release()
304
305
306 class TSPGui:
307 """
308 displays solutions graphically as we go
309 """
310 x = 100
311 y = 100
312 w = width + 10
313 h = height + 50
314
315 updatePeriod = 0.1
316
317 def __init__(self):
318 """
319 Creates the graphical interface
320 """
321 # initial empty population
322 self.pop = TSPSolutionPopulation()
323 self.best = self.pop.best()
324 self.updated = True
325
326 # lock for drawing
327 self.lock = Lock()
328
329 # build the gui
330 self.win = Fl_Window(
331 self.x, self.y,
332 self.w, self.h,
333 "pygene Travelling Salesman solver")
4b91610 Issue1: Remove psyco / fix fltk (font)
Tomasz bla Fortuna authored
334
134d944 Importing code into GIT
Tomasz bla Fortuna authored
335 self.xdraw = 5
336 self.ydraw = 5
337 self.wdraw = self.w - 10
338 self.hdraw = self.h - 90
339
340 # bring in our custom canvas
341 self.draw_canvas = TSPCanvas(
342 self,
343 self.xdraw, self.ydraw,
344 self.wdraw, self.hdraw,
345 )
346
347 # add in some fields
348 self.fld_numgen = Fl_Output(120, self.h-84, 50, 20, "Generations: ")
349 self.fld_numimp = Fl_Output(320, self.h-84, 50, 20, "Improvements: ")
350
351 # add a chart widget
352 self.chart = Fl_Chart(5, self.h - 60, self.w - 10, 60)
353 self.chart.color(FL_WHITE)
354 self.chart.type(FL_LINE_CHART)
355 self.win.end()
356
357 # this flag allows for original generation to be displayed
358 self.firsttime = True
359 self.fitness = self.pop.best().fitness()
360
361 self.ngens = 0
362 self.nimp = 0
363 self.bestFitness = 9999999999999999999
4b91610 Issue1: Remove psyco / fix fltk (font)
Tomasz bla Fortuna authored
364
134d944 Importing code into GIT
Tomasz bla Fortuna authored
365 def run(self):
366 """
367 Runs the population
368 """
369 # put up the window
370 self.win.show()
371
372 # start the background thread
373 start_new_thread(self.threadUpdate, ())
374
375 # schedule periodical updates
376 Fl.add_idle(self.update)
377
378 # hit the event loop
379 Fl.run()
380
381 def update(self, *args):
382 """
383 checks for updates
384 """
385 # and let the thread run
386 sleep(0.0001)
387
388 if self.updated:
389
390 self.lock.acquire()
391
392 # now draw the current state
393 self.draw_canvas.redraw()
394
395 # plot progress on graph
396 self.chart.add(self.fitness)
397
398 # update status fields
399 self.ngens += 1
400 self.fld_numgen.value(str(self.ngens))
401
402 if self.fitness < self.bestFitness:
403 self.nimp += 1
404 self.fld_numimp.value(str(self.nimp))
405 self.bestFitness = self.fitness
406
407 self.updated = False
408
409 self.lock.release()
410
411 def threadUpdate(self):
412 """
413 create and display generation
414 """
415 print "threadUpdate starting"
416
417 while True:
418
419 self.pop.gen()
420
421 #print "generated"
422
423 self.lock.acquire()
424
425 self.best = self.pop.best()
426 self.fitness = self.best.fitness()
427 self.updated = True
428
429 self.lock.release()
430
431
432 def main():
433
434 # build and run the gui
435 gui = TSPGui()
436
4b91610 Issue1: Remove psyco / fix fltk (font)
Tomasz bla Fortuna authored
437 if psyco:
438 print "Starting psyco"
439 psyco.full()
134d944 Importing code into GIT
Tomasz bla Fortuna authored
440
441 gui.run()
442
443 if __name__ == '__main__':
444 main()
445
446
Something went wrong with that request. Please try again.