# VectorLinux

• May 25, 2018, 07:59:25 am
• Welcome, Guest

### News:

Visit our home page for VL info. For support and documentation, visit the Vector Linux Knowledge Center or search the Knowledge Center and this Forum using the search box above.

Pages: [1]

### AuthorTopic: eyo I just made a genetic algorithm to solve TSP heuristically  (Read 4034 times)

#### Triarius Fidelis

• Vecteloper
• Vectorian
• Posts: 2399
• Domine, exaudi vocem meam
##### eyo I just made a genetic algorithm to solve TSP heuristically
« on: May 15, 2010, 09:58:20 pm »

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

Code: [Select]
`#!/usr/bin/pythonimport randomfrom pyevolve import G1DListfrom pyevolve import GSimpleGAfrom pyevolve import GAllelefrom pyevolve import Mutatorsfrom pyevolve import Crossoversfrom 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 understooddistances = {}# Amsterdamdistances[0,1] = 176distances[0,2] = 623distances[0,3] = 365distances[0,4] = 366distances[0,5] = 347distances[0,6] = 431distances[0,7] = 710# Brusselsdistances[1,0] = 176distances[1,2] = 769distances[1,3] = 319distances[1,4] = 490distances[1,5] = 308distances[1,6] = 263distances[1,7] = 716# Copenhagendistances[2,0] = 623distances[2,1] = 769distances[2,3] = 671distances[2,4] = 289distances[2,5] = 948distances[2,6] = 1031distances[2,7] = 642# Frankfurtdistances[3,0] = 365distances[3,1] = 319distances[3,2] = 671distances[3,4] = 394distances[3,5] = 627distances[3,6] = 481distances[3,7] = 405# Hamburgdistances[4,0] = 366distances[4,1] = 490distances[4,2] = 289distances[4,3] = 394distances[4,5] = 711distances[4,6] = 747distances[4,7] = 497# Londondistances[5,0] = 347distances[5,1] = 308distances[5,2] = 948distances[5,3] = 627distances[5,4] = 711distances[5,6] = 337distances[5,7] = 1019# Parisdistances[6,0] = 431distances[6,1] = 263distances[6,2] = 1031distances[6,3] = 481distances[6,4] = 747distances[6,5] = 337distances[6,7] = 879# Praguedistances[7,0] = 710distances[7,1] = 716distances[7,2] = 642distances[7,3] = 405distances[7,4] = 497distances[7,5] = 1019distances[7,6] = 879# Number of citiesNUM_OF_CITIES = 8def eval_func(chromosome):  total = 0    for i in xrange(NUM_OF_CITIES):      j = (i + 1) % NUM_OF_CITIES      total += distances[chromosome[i],chromosome[j]]  return totaldef 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)setOfAlleles.add(a)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, 10: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: 156
• Just me.
##### Re: eyo I just made a genetic algorithm to solve TSP heuristically
« Reply #1 on: May 16, 2010, 10: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
##### Re: eyo I just made a genetic algorithm to solve TSP heuristically
« Reply #2 on: May 16, 2010, 01: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
##### Re: eyo I just made a genetic algorithm to solve TSP heuristically
« Reply #3 on: May 17, 2010, 12:16:41 am »

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, 05: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: 2383
##### Re: eyo I just made a genetic algorithm to solve TSP heuristically
« Reply #4 on: June 01, 2010, 07: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
##### Re: eyo I just made a genetic algorithm to solve TSP heuristically
« Reply #5 on: June 04, 2010, 12:34:37 am »

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]