60 .metadata/.plugins/org.eclipse.core.resources/.history/92/80e39bd408eb001516d9bdbed1014b85
View file

This file was deleted.

60 .metadata/.plugins/org.eclipse.core.resources/.history/9d/7094640109eb001516d9bdbed1014b85
View file

This file was deleted.

60 .metadata/.plugins/org.eclipse.core.resources/.history/b/30e560c708eb001516d9bdbed1014b85
View file

This file was deleted.

49 .metadata/.plugins/org.eclipse.core.resources/.history/b3/303b7b21cfeb0015175da7c32f7494c7
View file

This file was deleted.

60 .metadata/.plugins/org.eclipse.core.resources/.history/c6/c0a5b70609eb001516d9bdbed1014b85
View file

This file was deleted.

49 .metadata/.plugins/org.eclipse.core.resources/.history/d9/201ce51dcfeb0015175da7c32f7494c7
View file

This file was deleted.

49 .metadata/.plugins/org.eclipse.core.resources/.history/dd/300ef718cfeb0015175da7c32f7494c7
View file

This file was deleted.

60 .metadata/.plugins/org.eclipse.core.resources/.history/f5/b06db4c508eb001516d9bdbed1014b85
View file

This file was deleted.

49 .metadata/.plugins/org.eclipse.core.resources/.history/fd/90407decceeb0015175da7c32f7494c7
View file

This file was deleted.

50 .metadata/.plugins/org.eclipse.core.resources/.history/fd/f0d60617cfeb0015175da7c32f7494c7
View file

This file was deleted.

49 .metadata/.plugins/org.eclipse.core.resources/.history/fe/f05c82e3ceeb0015175da7c32f7494c7
View file

This file was deleted.

BIN +24 Bytes (100%) .../.plugins/org.eclipse.core.resources/.projects/Ant_Based_Searching/.indexes/history.index
View file
Binary file not shown.
94 .../Ant_Based_Searching/com.python.pydev.analysis/AdditionalProjectInterpreterInfo.pydevinfo
View file
@@ -1,57 +1,63 @@
-- VERSION_4
-- START DISKCACHE_2
C:\EclipseWorkspaces\csse453\.metadata\.plugins\org.eclipse.core.resources\.projects\Ant_Based_Searching\com.python.pydev.analysis\v2_indexcache
mapMaker|1458170726005394000|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\mapMaker.py
City|1458170890414394000|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\City.py
AS_Ant|1458172062943394000|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\AS_Ant.py
main|1458172381075601000|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\main.py
mapMaker|1458535671758651000|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\mapMaker.py
AS_Ant|1458534792828279000|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\AS_Ant.py
City|1458531352213094000|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\City.py
-- END DISKCACHE
-- START DICTIONARY
10
4=mapMaker
5=path
8=AS_Ant.travel
7=AS_Ant.__init__
10=city.__init__
9=path.__init__
3=City
2=AS_Ant
6=city
1=main
3=mapMaker
4=path
10=path.decay
7=AS_Ant.travel
6=AS_Ant.__init__
9=city.__init__
8=path.__init__
2=City
1=AS_Ant
5=city
-- END DICTIONARY
-- START TREE 1
13
Q|1|Q!11@
alp|1|alpha!11@
ant|1|ants!11@
as_|1|AS_Ant!17@
bes|2|bestPath!11@bestLength!11@
bet|1|beta!11@
cit|1|city!25@
num|2|numIterations!11@numAnts!11@
pat|1|path!25@
rea|1|readMap!34@
rho|1|rho!11@
sta|1|start_city!11@
20
Q|0|
alp|0|
ant|0|
as_|1|AS_Ant!9@
bes|0|
bet|0|
cit|1|city!17@
e|0|
ite|0|
mak|1|makeMap!26@
num|0|
pat|1|path!17@
per|0|
pre|0|
rea|1|readMap!26@
rho|0|
sam|0|
sta|0|
t0|0|
upd|1|updatePaths!10@
-- END TREE
-- START TREE 2
17
__i|3|__init__!5&26@__init__!6&26@__init__!2&18@
add|1|addNeighbor!6&26@
alp|1|alpha!7&19@
bet|1|beta!7&19@
cit|2|city!8&19@city!7&19@
com|2|complete!8&19@complete!7&19@
dec|2|decay!5&26@decayRate!9&27@
dis|1|dist!9&27@
fin|1|finalCity!7&19@
isc|1|isComplete!2&18@
len|1|length!7&19@
nam|1|name!10&27@
nee|1|needToVist!7&19@
nei|1|neighbors!10&27@
pat|1|path!7&19@
phe|1|pher!9&27@
tra|1|travel!2&18@
__i|3|__init__!1&10@__init__!4&18@__init__!5&18@
add|1|addNeighbor!5&18@
alp|1|alpha!6&11@
bet|1|beta!6&11@
cit|2|city!7&11@city!6&11@
com|2|complete!7&11@complete!6&11@
dec|2|decay!4&18@decayRate!8&19@
dis|1|dist!8&19@
fin|1|finalCity!6&11@
isc|1|isComplete!1&10@
len|1|length!6&11@
nam|1|name!9&19@
nee|1|needToVist!6&11@
nei|1|neighbors!9&19@
pat|1|path!6&11@
phe|2|pher!10&19@pher!8&19@
tra|1|travel!1&10@
-- END TREE
2 ...s/org.eclipse.core.resources/.projects/Ant_Based_Searching/org.python.pydev/1.v1_astdelta
View file
@@ -1 +1 @@
INSmapMaker|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\mapMaker.py
INSmain|C:\EclipseWorkspaces\csse453\Ant_Based_Searching\main.py
BIN +3.42 KB (450%) .metadata/.plugins/org.eclipse.core.resources/.safetable/org.eclipse.core.resources
View file
Binary file not shown.
3,562 .metadata/.plugins/org.eclipse.e4.workbench/workbench.xmi
View file

Large diffs are not rendered by default.

1 .metadata/.plugins/org.eclipse.m2e.logback.configuration/0.log
View file
@@ -3,3 +3,4 @@
2016-03-15 16:43:58,097 [Worker-2] INFO c.g.t.t.d.PublishedGradleVersions - Gradle version information cache file is not out-of-date. No remote download required.
2016-03-16 19:25:38,771 [Worker-20] INFO c.g.t.t.d.PublishedGradleVersions - Gradle version information cache file is out-of-date. Remote download required.
2016-03-20 23:21:33,497 [Worker-12] INFO c.g.t.t.d.PublishedGradleVersions - Gradle version information cache file is out-of-date. Remote download required.
2016-03-20 23:48:36,499 [Worker-8] INFO c.g.t.t.d.PublishedGradleVersions - Gradle version information cache file is not out-of-date. No remote download required.
2 .metadata/.plugins/org.python.pydev/dialog_settings.xml
View file
@@ -4,8 +4,8 @@
<section name="DialogBoundsSettings">
<item value="600" key="DIALOG_WIDTH"/>
<item value="8" key="DIALOG_Y_ORIGIN"/>
<item value="100" key="DIALOG_X_ORIGIN"/>
<item value="500" key="DIALOG_HEIGHT"/>
<item value="100" key="DIALOG_X_ORIGIN"/>
<item value="1|Segoe UI|9.0|0|WINDOWS|1|-12|0|0|0|400|0|0|0|1|0|0|0|0|Segoe UI" key="DIALOG_FONT_NAME"/>
</section>
</section>
2 .metadata/.plugins/org.python.pydev/v1_aatwadonc05ihgowuydsrtw4w/1.v1_sys_astdelta
View file
@@ -1 +1 @@
INScopy|C:\Program Files\Python35-32\lib\copy.py
INSnumpy.random.__init__
2 .metadata/version.ini
View file
@@ -1,3 +1,3 @@
#Sun Mar 20 23:17:46 EDT 2016
#Sun Mar 20 23:47:58 EDT 2016
org.eclipse.core.runtime=2
org.eclipse.platform=4.5.2.v20160212-1500
29 Ant_Based_Searching/AS_Ant.py
View file
@@ -6,6 +6,7 @@

from numpy.random import choice
from copy import copy
from _overlapped import NULL

class AS_Ant(object):
'''
@@ -25,16 +26,17 @@ def __init__(self, cities, start_city, alpha, beta):
self.alpha = alpha
self.beta = beta
self.complete = False
self.needToVist.remove(start_city);

def travel(self):


if self.needToVist == []:
for neighbor in self.city.neighbors:
if neighbor[0] == self.finalCity:
for [neighbor, path] in self.city.neighbors:
if neighbor == self.finalCity:
self.path.append(self.finalCity)
self.city = self.finalCity
self.length+=neighbor[1].dist
self.length+=path.dist
self.complete = True
return True
return False
@@ -43,25 +45,21 @@ def travel(self):
choices = []
probabilities = []
total = 0
for neighborTuple in self.city.neighbors:
[neighbor, path] = neighborTuple
for [neighbor, path] in self.city.neighbors:
dist = path.dist
pher = path.pher
if neighbor in self.needToVist:
choices.append(neighbor)
probabilities.append(pher ** self.alpha * (1 / dist) ** self.beta)
total += pher ** self.alpha * (1 / dist) ** self.beta

if total == 0:
return False

p = [prob / total for prob in probabilities]
nextCity = choice(choices, p=p)

for neighborTuple in self.city.neighbors:
[neighbor, path] = neighborTuple
for [neighbor, path] in self.city.neighbors:
dist = path.dist
pher = path.pher
if nextCity == neighbor:
self.length+=dist
break
@@ -77,17 +75,22 @@ def isComplete(self):
return self.complete


def updatePaths(ants,paths,Q):
def updatePaths(ants,paths,Q,bestLength,bestPath,e):
[path.decay() for path in paths]
for ant in ants:
for i in range(0, len(ant.path)-2):
for i in range(0, len(ant.path)-1):
city1 = ant.path[i]
city2 = ant.path[i+1]
for [city, path] in city1.neighbors:
if city == city2:
path.pher += Q/ant.length


lastCity= NULL;
for city in bestPath:
if(lastCity!=NULL):
for [tempCity, path] in city.neighbors:
if tempCity == lastCity:
path.pher += e*Q/bestLength
lastCity = city
return


2 Ant_Based_Searching/City.py
View file
@@ -38,7 +38,7 @@ def __init__(self,dist, pher,rho):


def decay(self):
self.pher *= (1-self.decayRate)
self.pher = self.pher*(1-self.decayRate)



BIN +184 Bytes (110%) Ant_Based_Searching/__pycache__/AS_Ant.cpython-35.pyc
View file
Binary file not shown.
BIN +1 Byte (100%) Ant_Based_Searching/__pycache__/City.cpython-35.pyc
View file
Binary file not shown.
BIN +616 Bytes (170%) Ant_Based_Searching/__pycache__/mapMaker.cpython-35.pyc
View file
Binary file not shown.
77 Ant_Based_Searching/main.py
View file
@@ -5,49 +5,68 @@
'''
import mapMaker
import AS_Ant
import random
import time
from copy import copy




if __name__ == '__main__':
alpha = 1
beta = 5
numAnts = 200
Q = 275
rho = .5
numIterations = 100
t0 = 10**-6

[cities,paths] = mapMaker.readMap('maps/twelve.txt',rho,t0)
start_city = cities[0]
cities.remove(start_city)
def preformTSP(numCities):
[cities,paths] = mapMaker.makeMap(numCities,rho,t0)

bestLength = 99999999999
bestPath = []
iteration = -1
sameResult = 0;

startTime = time.time()

for i in range(0,numIterations):
ants = [AS_Ant.AS_Ant(cities, start_city,alpha,beta) for i in range (1, numAnts)]
ants = [AS_Ant.AS_Ant(cities, random.choice(cities),alpha,beta) for i in range (1, numAnts)]

while [ant for ant in ants if ant.isComplete()] ==[]:
while [ant for ant in ants if ant.isComplete()] ==[] and ants != []:
ants = [ant for ant in ants if ant.travel()]

ants = sorted(ants, key=lambda path:path.length)
if ants[0].length < bestLength:
bestLength = ants[0].length
bestPath = copy(ants[0].path)



print([city.name for city in bestPath])
print(bestLength)
AS_Ant.updatePaths(ants,paths,Q)


if(ants ==[]):
continue
minAnt = min(ants, key=lambda path:path.length)



if abs(minAnt.length - bestLength)<5:
sameResult+=1
elif minAnt.length < bestLength:
bestLength = minAnt.length
bestPath = copy(minAnt.path)
iteration = i
sameResult = 0

if sameResult == 5:
break;

pass

# print([city.name for city in ants[0].path])
# print(ants[0].length)
AS_Ant.updatePaths(ants,paths,Q,bestLength,bestPath,e)
print("number of cities: ",numCities)
print("time: ",time.time()-startTime)
print("best item found on iteration: ",iteration)
print("City path is:")
print([city.name for city in bestPath])
print("Length of path: ",bestLength)



if __name__ == '__main__':
alpha = 2
beta = 2
numAnts = 20
Q = 300
rho = .5
numIterations = 50
t0 = 10**-6
e = 5
for j in range(10,101,10):
preformTSP(j)

pass

18 Ant_Based_Searching/mapMaker.py
View file
@@ -4,6 +4,7 @@
@author: schackma
'''
import City
import random


def readMap(fileName,rho,t0):
@@ -48,3 +49,20 @@ def readMap(fileName,rho,t0):

mapFile.close()
return [cityMap,paths]



def makeMap(numCities,rho,t0):
cities = [City.city(i) for i in range(0,numCities)]
paths = []
random.seed(1)
for i in range(0,numCities):
for j in range(i+1,numCities):
city1 = cities[i]
city2 = cities[j]
newPath = City.path(random.randint(1,100),t0,rho)
paths.append(newPath)
city1.addNeighbor(city2,newPath)
city2.addNeighbor(city1,newPath)

return [cities,paths]