サラリーマンが、セールスマンと蟻で遊んだ

ant.py

# coding utf-8
import copy
import random
from math import *
import matplotlib.pyplot as plt


class Agent():
    def __init__(self, towns, roads, start, pheromone):
        # value
        self.current = start
        self.alpha = 1
        self.beta = 3
        self.Q = 100

        # list
        self.whole = copy.deepcopy(towns)
        self.notVisited = copy.deepcopy(towns)
        self.notVisited.remove(start)
        self.visited = [towns[start]]

        # dict
        self.roads = roads
        self.pheromone = copy.deepcopy(pheromone)
        self.way = {}
        for i in towns:
            for j in towns:
                if i is j:
                    continue
                self.way[(i,j)] = False

    def assessment(self, j):
        numerator = (self.pheromone[(self.current, j)]**self.alpha) * ((1/self.roads[(self.current, j)])**self.beta)
        denominator = sum([(self.pheromone[(self.current,l)]**self.alpha) * ((1/self.roads[(self.current, l)])**self.beta) for l in self.notVisited])
        assess = numerator / denominator
        return assess

    def probability(self):
        p = {}
        for m in self.notVisited:
            mAsses = self.assessment(m)
            sumAsses = sum([self.assessment(n) for n in self.notVisited])
            p[m] = mAsses / sumAsses
        return p

    def agentwalk(self):
        for i in self.whole:
            prob = self.probability()
            sprob = prob.items()
            #sprob = sorted(prob.items(), key=lambda x: x[0])
            choice = random.random()
            for i in sprob:
                choice = choice - i[1]
                if choice < 0:
                    nextT = i
                    break
            self.way[(self.current, nextT[0])] = True
            self.current = nextT[0]
            self.visited.append(nextT[0])
            self.notVisited.remove(nextT[0])
            if len(self.notVisited) == 0:
                return self.visited
        return self.visited

    def get_deltaphero(self):
        sumoflen = self.get_length()
        deltaPheromone = {}
        for i in self.pheromone:
            if self.way[i]:
                deltaPheromone[i] = self.Q/sumoflen
            else:
                deltaPheromone[i] = 0
        return deltaPheromone

    def get_phero(self,startpheromone, pheromones, ro):
        for i in startpheromone:
            startpheromone[i] = ro * startpheromone[i] + (1-ro) * sum([k[i] for k in pheromones])
        return startpheromone

    def get_length(self):
        sumoflen = 0
        for i in range(1,len(self.visited)):
            sumoflen += roads[(self.visited[i-1],self.visited[i])]
        return sumoflen

    def get_way(self):
        return self.visited

figureCount = 0
def anthistorySave(len, way, delt, pheromone, title=""):
    global figureCount
    phrange = max(pheromone.values()) - min(pheromone.values()) + 1
    for i in pheromone:
        pheromone[i] = pheromone[i]/phrange

    fig, ax = plt.subplots()
    plt.title(title + " length=" + str(len))
    plt.scatter([i[0] for i in positions], [i[1] for i in positions])
    for i, town in enumerate(way):
        plt.annotate(i, (positions[town][0]+1, positions[town][1]-3), color='r')
        plt.annotate(town, (positions[town][0]+1, positions[town][1]+1), color='g')
    for i in pheromone:
        plt.plot([positions[i[0]][0], positions[i[1]][0]],
                 [positions[i[0]][1], positions[i[1]][1]], 'r', alpha=pheromone[i])
        if delt[i] > 0:
            plt.plot([positions[i[0]][0], positions[i[1]][0]],
                     [positions[i[0]][1], positions[i[1]][1]], 'b')
    plt.grid()
    plt.savefig("hist/" + title + "anthistory_"+"{0:05d}".format(figureCount)+".png")
    plt.close('all')
    figureCount += 1


if __name__ == "__main__":
    NumOfTown = 30
    NumOfAgent = 20
    NumOfSolve = 500
    ro = 0.4
    random.seed(2)

    towns = [i for i in range(NumOfTown)]
    positions = [(random.randint(1,100), random.randint(1,100)) for i in range(NumOfTown)]

    roads = {}
    pheromone = {}
    for i in towns:
        for j in towns:
            if i is j:
                continue
            roads[(i,j)] = sqrt((positions[i][0] - positions[j][0])**2 +
                            (positions[i][1] - positions[j][1])**2)
            pheromone[(i,j)] = random.random()

    minlength = None
    bestAgent = None
    lastPheno = 0
    for i in range(NumOfSolve):
        pheros = []
        topAgent = None
        for m in range(NumOfAgent):
            k = Agent(towns=towns, start=0, roads=roads, pheromone=pheromone)
            k.agentwalk()
            length = k.get_length()
            pheros.append(k.get_deltaphero())
            if (topAgent is None) or (topAgent.get_length() > length):
                topAgent = copy.deepcopy(k)
            if (minlength is None) or (minlength > length):
                minlength = length
                bestAgent = copy.deepcopy(k)
            anthistorySave(k.get_length(), k.get_way(), k.get_deltaphero(), k.pheromone)
        #anthistorySave(topAgent.get_length(), topAgent.get_way(), topAgent.get_deltaphero(), topAgent.pheromone)
        print("今" + str(i) + "番目のありんこたちが仕事をしました。")
        pheromone = k.get_phero(pheromone, pheros, ro)

        if round(sum(pheromone.values()),4) == round(lastPheno,4):
            pheromone = {}
            for i in towns:
                for j in towns:
                    if i is j:
                        continue
                    pheromone[(i,j)] = random.random()
        lastPheno = sum(pheromone.values())

    print(bestAgent.get_way())
    anthistorySave(bestAgent.get_length(), bestAgent.get_way(), bestAgent.get_deltaphero(), bestAgent.pheromone)