蚁群算法，资源分配

ant-colony.py

#!/usr/bin/env python3

import random
from bisect import bisect
from itertools import accumulate
from collections import Counter
import sys

total = 180
n = 15
if len(sys.argv) > 1:
    try:
        n = int(sys.argv[1])
    except ValueError:
        print("Invalid n. Fallback to default n = 15.", end="\n\n")
else:
    print("Default n = 15.", end="\n\n")
defaultPheromone = 3
pheromoneConstant = 10e5
evaporation = 0.7
alpha = 0.5
beta = 2
ratio = 1

def randomGrids(total, n):
    dividers = sorted(random.sample(range(1, total), n - 1))
    return [b - a for a, b in zip([0] + dividers, dividers + [total])]

def updatePheromone(cost, pheromone, path, minCost):
    l = 0
    cmax = 0
    for i in range(n):
        c = cost.get(tuple(sorted(path[0:i])), None)
        chosen = c.get(path[i], 0)
        l += chosen
        if chosen > cmax:
            cmax = chosen
    if minCost[0] >= cmax:
        minCost[0] = cmax
        minCost[1] = path
    for i in range(n):
        p = pheromone.get(tuple(path[0:i]), None)
        for j in p:
            p[j] *= evaporation
        p[path[i]] += pheromoneConstant / l

def findPath(grids, cost, pheromone, prob, path, minCost):
    if len(path) == n:
        updatePheromone(cost, pheromone, path, minCost)
    else:
        passed = tuple(path)
        left = list((Counter(grids) - Counter(passed)).elements())
        if passed not in prob:
            prob[passed] = {}
            numerator = {}
            denominator = 0
            for i in left:
                if passed not in pheromone:
                    pheromone[passed] = {i: defaultPheromone for i in left}
                p = pheromone[passed][i]
                sortedPassed = tuple(sorted(passed))
                if sortedPassed not in cost:
                    cost[sortedPassed] = {i: (4800 * ratio * (total - sum(passed)) + 3 * ratio * i * i * (total - sum(passed))) / i for i in left}
                c = cost[sortedPassed][i]
                numerator[i] = (p ** alpha) * ((1/c) ** beta)
                denominator += numerator[i]
            for i in left:
                prob[passed][i] = numerator[i] / denominator
        choices = []
        weights = []
        for i in left:
            choices.append(i)
            weights.append(prob[passed][i])
        cumdist = list(accumulate(weights))
        x = random.random() * cumdist[-1]
        choice = choices[bisect(cumdist, x)]
        path.append(choice)
        findPath(grids, cost, pheromone, prob, path, minCost)

minCost = [sys.maxsize, []]
for x in range(100):
    grids = randomGrids(total, n)
    print("Current grids:", grids)
    pheromone = {}
    prob = {}
    cost = {}
    for i in range(100):
        path = []
        findPath(grids, cost, pheromone, prob, path, minCost)
    print("Current minimum cost:", minCost, end='\n\n')
print("Final minimum cost:")
print(minCost)