Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
ACO solution in Uncategorized category for Express Delivery by Zanzacar
import random
'''
This solution is not that most efficient. It also doesn't claim to be. I was mainly looking into
Ant Colony Optimization, Classes, and also coming up with an interesting alternative solution.
Please also note the solution doesn't work every single time, I have worked it to a point now
that it works majority of the time rather then a minority.
I have left some of the thing intact such as printing the earth so you can see the pheromones in action etc.
These are the first classes I have ever made so if you have any suggestion I would love to hear them.
Notes:
#1. B is for putting in the box, P is for taking out
#2. I found that after about 10,000 or maybe 100,000 ants
there isn't much reason to continue. That is why I run
multiple waves through.
#3. I think the pheromone decomposition, and pheromone laying could be optomized.
I tried a lot of different pheromone schemes throughout this process. It was hard
trying to find a solution to meet all the needs of all the mazes.
#4. Enjoy.
'''
class earth:
'''
Used to define/contain all the enviromental elements.
'''
def __init__(self,data):
self.endLocation = (len(data)-1,len(data[0])-1)
self.field_map = self.mapSetup(data)
self.default_map = self.field_map[:]
def curMoves(self,curLocation):
return self.field_map[curLocation[0]][curLocation[1]][1]
def decomposePheromone(self):
'''Decomposes the weighted moves'''
for row in self.field_map:
for cell in row:
if cell[1][0]>10:cell[1][0]-=7
if cell[1][1]>10:cell[1][1]-=7
if cell[1][2]>10:cell[1][2]-=7
if cell[1][3]>10:cell[1][3]-=7
if cell[1][4]>10:cell[1][4]-=7
if cell[1][5]>10:cell[1][5]-=7
def mapSetup(self,matrix):
'''setups initial state of map... all available moves [cell value,[weighted moves]]'''
matrix = [list(map(list,row)) for row in matrix]
for row in range(len(matrix)):
for col in range(len(matrix[0])):
moves = []
if matrix[row][col][0]=='B':
moves.extend([100,100])
else:
moves.extend([0,0])
if row-1>=0 and matrix[row-1][col][0]!='W':
moves.append(1)
else:
moves.append(0)
if row+1=0 and matrix[row][col-1][0]!='W':
moves.append(1)
else:
moves.append(0)
if col+12*self.bestTime:
self.curTime=10000
break
if self.curTime0 and possibleMoves<5 and moveValue==oppositeDict[self.curRoute[-1]]:
#insure no u-turns moves
moveValue = self.antBrain(self.motherEarth.curMoves(self.curLocation))
if moveValue=='B':
if self.hasCargo==True:
self.curRoute+=moveValue
self.hasCargo = False
self.curTime+=1
moveValue = self.antBrain(self.motherEarth.curMoves(self.curLocation)[2:])
elif moveValue=='P':
if self.hasCargo==False:
self.curRoute+='B'
self.hasCargo = True
self.curTime+=1
moveValue = self.antBrain(self.motherEarth.curMoves(self.curLocation)[2:])
self.curRoute+=moveValue
self.curLocation = tuple(sum(x) for x in zip(self.curLocation, moveDict[moveValue]))
if self.hasCargo:
self.curTime+=2
else:
self.curTime+=1
def antBrain(self,weightedMoves):
'''Ant Logic on move selection'''
rnd = random.random() * sum(weightedMoves)
for index, weightValue in enumerate(weightedMoves):
rnd -= weightValue
if rnd < 0:
if len(weightedMoves)>4:
return self.COMMAND_LIST[index]
else:
return self.MOVE_LIST[index]
def placePheromone(self,pheromoneAmount):
'''changes weighted possible moves positive values add, -1 creates new route via pheromone'''
ghostPosition = (0,0)
moveDict = {'U': (-1,0),'D': (1,0),'R': (0,1),'L': (0,-1),'B':(0,0),'P':(0,0)}
for step in self.bestRoute:
if pheromoneAmount<1:
self.motherEarth.curMoves(ghostPosition)[self.COMMAND_LIST.index(step)]+=max(self.motherEarth.curMoves(ghostPosition))
else:
self.motherEarth.curMoves(ghostPosition)[self.COMMAND_LIST.index(step)]+=pheromoneAmount
ghostPosition = tuple(sum(x) for x in zip(ghostPosition, moveDict[step]))
def getRoute(self): return self.bestRoute
def getTime(self): return self.bestTime
def printMap(self):
self.motherEarth.printEarth()
#main function
def checkio(data):
runAnts = ant(data)
runAnts.run(len(data)*len(data[0]),len(data[0])*1000) #This could potentially be optimized based off the map.
return runAnts.getRoute()
Jan. 14, 2014
