VectorLinux
September 17, 2014, 07:22:02 pm
 News: Visit our home page for VL info. To search the old message board go to http://vectorlinux.com/forum1. The first VL forum is temporarily offline until we can find a host for it. Thanks for your patience. Now powered by KnowledgeDex.
 Pages: [1]
 Author Topic: eyo I just made a genetic algorithm to solve TSP heuristically  (Read 1170 times)
Triarius Fidelis
Vecteloper
Vectorian

Posts: 2399

Domine, exaudi vocem meam

 « on: May 15, 2010, 08:58:20 pm »

as of now it has found an optimal tour through London, Amsterdam, Hamburg, Copenhagen, Prague, Frankfurt, Brussels, and Paris

Code:
#!/usr/bin/python

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

#ideal tour: London, Amsterdam, Hamburg, Copenhagen, Prague (Praha?), Frankfurt,
#Brussels, Paris, London, length 2,980 km

# Amsterdam - 0
# Brussels - 1
# Copenhagen - 2
# Frankfurt - 3
# Hamburg - 4
# London - 5
# Paris - 6
# Prague - 7

# what is homogeneous?? resolved

# use special initializer
# OX crossover understood

distances = {}

# Amsterdam
distances[0,1] = 176
distances[0,2] = 623
distances[0,3] = 365
distances[0,4] = 366
distances[0,5] = 347
distances[0,6] = 431
distances[0,7] = 710

# Brussels
distances[1,0] = 176
distances[1,2] = 769
distances[1,3] = 319
distances[1,4] = 490
distances[1,5] = 308
distances[1,6] = 263
distances[1,7] = 716

# Copenhagen
distances[2,0] = 623
distances[2,1] = 769
distances[2,3] = 671
distances[2,4] = 289
distances[2,5] = 948
distances[2,6] = 1031
distances[2,7] = 642

# Frankfurt
distances[3,0] = 365
distances[3,1] = 319
distances[3,2] = 671
distances[3,4] = 394
distances[3,5] = 627
distances[3,6] = 481
distances[3,7] = 405

# Hamburg
distances[4,0] = 366
distances[4,1] = 490
distances[4,2] = 289
distances[4,3] = 394
distances[4,5] = 711
distances[4,6] = 747
distances[4,7] = 497

# London
distances[5,0] = 347
distances[5,1] = 308
distances[5,2] = 948
distances[5,3] = 627
distances[5,4] = 711
distances[5,6] = 337
distances[5,7] = 1019

# Paris
distances[6,0] = 431
distances[6,1] = 263
distances[6,2] = 1031
distances[6,3] = 481
distances[6,4] = 747
distances[6,5] = 337
distances[6,7] = 879

# Prague
distances[7,0] = 710
distances[7,1] = 716
distances[7,2] = 642
distances[7,3] = 405
distances[7,4] = 497
distances[7,5] = 1019
distances[7,6] = 879

# Number of cities
NUM_OF_CITIES = 8

def eval_func(chromosome):
total = 0

for i in xrange(NUM_OF_CITIES):
j = (i + 1) % NUM_OF_CITIES
total += distances[chromosome[i],chromosome[j]]

def G1DListTSPInitializator(chromosome, **args):
chromosome.clearList()
lst = [i for i in xrange(chromosome.listSize)]

for i in xrange(chromosome.listSize):
choice = random.choice(lst)
lst.remove(choice)
chromosome.append(choice)

setOfAlleles = GAllele.GAlleles(homogeneous=True)
lst = [ i for i in xrange(NUM_OF_CITIES) ]
a = GAllele.GAlleleList(lst)

genome = G1DList.G1DList(NUM_OF_CITIES)
genome.setParams(allele=setOfAlleles)

genome.evaluator.set(eval_func)
genome.mutator.set(Mutators.G1DListMutatorSwap)
genome.crossover.set(Crossovers.G1DListCrossoverOX)
genome.initializator.set(G1DListTSPInitializator)

ga = GSimpleGA.GSimpleGA(genome)
ga.setGenerations(1000)
ga.setMinimax(Consts.minimaxType["minimize"])
ga.setCrossoverRate(1.0)
ga.setMutationRate(0.03)
ga.setPopulationSize(80)

ga.evolve(freq_stats=100)
best = ga.bestIndividual()
print best

EVOLUTION IS A SATANIC LIE RIGHT

nah just kidding I wouldn't say something dumb like that and mean it

that's only eight cities though

give me like twenty cities

I will find a nearly optimal tour for them

out of 2.5 quintillion possible tours on my craputer I will find a nearly optimal tour

 « Last Edit: May 15, 2010, 09:05:40 pm by Triarius Fidelis » Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
nitehawk
Vectorite

Posts: 155

Just me.

 « Reply #1 on: May 16, 2010, 09:03:26 am »

Wow,..
that sounds great!  I may have gone one better.  I have discovered an "optimal tour"  from my main computer, to the refrigerator (and the other facility) ..and back again to the computer,...that cuts time to the minimum.
 Logged
Triarius Fidelis
Vecteloper
Vectorian

Posts: 2399

Domine, exaudi vocem meam

 « Reply #2 on: May 16, 2010, 12:14:50 pm »

For my part I just have a bedpan on my chair and the number for Domino's posted on the wall
 Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
Triarius Fidelis
Vecteloper
Vectorian

Posts: 2399

Domine, exaudi vocem meam

 « Reply #3 on: May 16, 2010, 11:16:41 pm »

Alright just did a twenty city tour

~61,000 km is the shortest I can get it

Allentown, Amherst, Toronto, Butte, Los Angeles, Port Moresby, Wagga Wagga, Kisumu, Kaliningrad, Stockholm, Uppsala, Oslo, Copenhagen, Ouagadougou, Abidjan, Buenos Aires, Caracas, Port-au-Prince, Pensacola, Camden

It seems counterintuitive that the European and African cities get mixed together

But then I realized that in doing so it makes it shorter, jumping from Abidjan to Buenos Aires rather than from Copenhagen to Buenos Aires

That being said, 61,000 km is the number to beat

EDIT:

Allentown, Camden, Pensacola, Port-au-Prince, Caracas, Buenos Aires, Abidjan, Ouagadougou, Copenhagen, Oslo, Uppsala, Stockholm, Kaliningrad, Kisumu, Wagga Wagga, Port Moresby, Los Angeles, Butte, Toronto, Amherst

what's interesting is that it still splits up the European and African cities counterintuitively
 « Last Edit: May 17, 2010, 04:59:40 pm by Triarius Fidelis » Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
rbistolfi
Packager
Vectorian

Posts: 2283

 « Reply #4 on: June 01, 2010, 06:56:40 am »

Impressive.
 Logged

"There is a concept which corrupts and upsets all others. I refer not to Evil, whose limited realm is that of ethics; I refer to the infinite."
Jorge Luis Borges, Avatars of the Tortoise.

--
Jumalauta!!
Triarius Fidelis
Vecteloper
Vectorian

Posts: 2399

Domine, exaudi vocem meam

 « Reply #5 on: June 03, 2010, 11:34:37 pm »

Next plan is a cellular automaton to model bioluminescence in bacterial colonies
 Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
 Pages: [1]