def runAntColonyOptimization():
# constants
# NUM_RUNS = 50
# NUM_ANTS = 250
# NUM_BEST_ANTS = 5
# PHEROMON_UPDATE = 0.025
NUM_ANTS = iNumPlayers
NUM_BEST_ANTS = int(iNumPlayers / 10)
NUM_RUNS = iNumPlayers * 25
PHEROMON_UPDATE = 0.34 / iNumPlayers
# the best ant (permutation, error) we know
TheBestAnt = (None, 'inf')
# uniformly distributed pheromon at the beginning
fPheromonMatrix = SquareMatrix(iNumPlayers, 1 / iNumPlayers)
# the actual ACO:
for iRun in xrange(NUM_RUNS):
ants = {}
# get some random ants:
for i in xrange(NUM_ANTS):
permutation = randomList(iPlayersList, fPheromonMatrix)
error = evaluatePermutation(permutation)
ants[error] = permutation
bestants = []
[B]# get the x best ants (smallest error):
sortedkeys = ants.keys()
sortedkeys.sort()
for error in sortedkeys[:NUM_BEST_ANTS]:
ant = (ants[error], error)
bestants.append(ant)[/B]
# check if we have a new TheBestAnt:
if bestants[0][1] < TheBestAnt[1]:
TheBestAnt = bestants[0]
print "%s %.8f (%d)" % (TheBestAnt[0], TheBestAnt[1], iRun)
# let the x best ants update the pheromon matrix:
for i, pos in enumerate(fPheromonMatrix):
for ant in bestants:
value = ant[0][i]
fPheromonMatrix[i][value] = pos[value] + PHEROMON_UPDATE
# total probability for each pos has to be one:
fPheromonMatrix[i] = ScaleList(fPheromonMatrix[i])
return TheBestAnt