Ant-Colony/main.py at master · Pussa/Ant-Colony · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
from random import choices
ants = 100000 # Количество муравьев
matrix = list()
matrix.append(list(map(int, input().split()))) # Получение матрицы
for i in range(1, len(matrix[0])):
    matrix.append(list(map(int, input().split())))
cs = len(matrix)
a =0.1
b = 2.5  #Задание значения костант
Q = 1

def sig(cs, t, a, n, b):
    sigma = 0
    for i in range(cs):
        for j in range(cs):
            sigma = sigma + t[i][j] ** a * n[i][j] ** b
    return sigma

def nn(matrix,cs):
    n = [[1 / matrix[i][j] if matrix[i][j] != 0 else 0 for j in range(cs)] for i in range(cs)]
    return n

n = nn(matrix,cs)
t = [[Q for j in range(cs)] for i in range(cs)]     #Ферамон
sigma = sig(cs,t,a,n,b)
p = [[(t[i][j]**a*n[i][j]**b)/sigma for j in range(cs)] for i in range(cs)]      # Расчет начальной матрицы вероятностей

L = 0
LL= 1000000000000000
zapomnit = 0
index_otkuda = 0
count = 0
for ant in range (ants):
    ants_mass = [j for j in range(cs)] #Список посещенных городов
    zxc = ant%cs #Определение первого города
    ants_mass[zxc] = -1
    index_otkuda = zxc
    L = 0
    count = 0
    choice =-1                     #Алгоритм выбора пути
    count2 = 0

    while(count!=cs):
        while(choice==-1):
            choice = choices(ants_mass,weights=p[index_otkuda])[0]
            if (choice>-1) :
                ants_mass[choice] = -1
                count2+=1

            if (count2==cs-2):

                L = L + matrix[index_otkuda][choice]
                index_otkuda =choice
                count2 +=1
                ants_mass[choice] = -1
                for w in range (cs):
                    if ants_mass[w]!=-1:
                        zapomnit =ants_mass[w]

                choice =zapomnit


            if count2 ==cs or count2 ==cs-1:

                break

        L = L+matrix[index_otkuda][choice]

        t[index_otkuda][choice] = t[index_otkuda][choice] + Q / L
        sigma = sigma + t[index_otkuda][choice] ** a * n[index_otkuda][choice] ** b  # Обновление вероятностей после обновления уровня ферамона
        p[index_otkuda][choice] = (t[index_otkuda][choice] ** a * n[index_otkuda][choice] ** b) / sigma
        index_otkuda = choice
        count += 1
        choice =-1
    if L +matrix[index_otkuda][zxc] <LL  :
        LL =L +matrix[index_otkuda][zxc]


print(LL)