-
Notifications
You must be signed in to change notification settings - Fork 0
/
Ant_Colony_Nakljucne_utezi.py
100 lines (91 loc) · 3.82 KB
/
Ant_Colony_Nakljucne_utezi.py
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from random import *
import time
start = time.time()
def izberi_pot(ant,vozlisce,neobiskana,pher,verjetnosti,razdalja,seznam,n,a,b,q0):
vsota = 0
for i in range(n):
if neobiskana[ant][i] == 1:
verjetnosti[i] = (pher[vozlisce][i]**a)*((1/razdalja[vozlisce][i])**b)
vsota += (pher[vozlisce][i]**a)*(razdalja[vozlisce][i]**b)
else:
verjetnosti[i] = 0
for i in range(n):
if verjetnosti[i]/vsota > q0:
return [i]
return choices(seznam,verjetnosti)
def main():
a = 1 # pomen razdalje
b = 2.5 # pomen pher
c = 1 # zacetni pher
s = 0.1 # odstranitev slabih poti
p = 0.1 # dodatek k opt poti
q0 = 0.9 # pozresnost
m = 10 # stevilo mravelj
q = 100 # kolicina pher, ki ga izloci ena mravlja
n = 10 #int(input()) #stevilo_mest
zgornja_utez = 999 # Zgornja meja za utez
razdalja = [[0]*n for i in range(n)]
pher = [[c]*n for i in range(n)]
verjetnosti = [0]*n
seznam = [i for i in range(n)]
lokacija = [0]*m # lokacija na kateri se nahaja i-ta mravlja
dolzina_poti = [0]*m # razdalja, ki jo je na svoji poti opravila i-ta mravlja
pher_dodan = [[0]*n for i in range(n)]
min_dolzina = 999999
opt_pot = []
for i in range(n):
for j in range(n):
razdalja[i][j] = randint(1,zgornja_utez)
korak = 0
global inp
inp = time.time()
while korak < 1000:
korak += 1
pot = [[] for i in range(m)] # pot za vsako mravljo
neobiskana = [[1]*n for i in range(m)] # mnozica neobiskanih vozlisc za vsako mravljo (morda bolj smiselno sete za boljso casovno zahtebnost)
pher_dodan = [[0]*n for i in range(n)] # kolicina pheranoma dodanega zaradi mravljine poti
dolzina_poti = [0]*m
for i in range(m):
lokacija[i] = randint(0,n-1)
neobiskana[i][lokacija[i]] = 2
for i in range(n): # tukaj simuliramo pot
for j in range(m):
if i == n-1:
for k in range(n):
if neobiskana[j][k] == 2:
f = k
dolzina_poti[j] += razdalja[lokacija[j]][f]
pot[j].append((lokacija[j],f))
else:
f = izberi_pot(j,lokacija[j],neobiskana,pher,verjetnosti,razdalja,seznam,n,a,b,q0)[0]
dolzina_poti[j] += razdalja[lokacija[j]][f]
pot[j].append((lokacija[j],f))
lokacija[j] = f
neobiskana[j][f] = 0
pher[pot[j][i][0]][pot[j][i][1]] = (1-s)*pher[pot[j][i][0]][pot[j][i][1]] + s*c
pher[pot[j][i][1]][pot[j][i][0]] = pher[pot[j][i][0]][pot[j][i][1]]
for i in range(m):
if dolzina_poti[i] == min(dolzina_poti):
if (dolzina_poti[i] < min_dolzina):
min_dolzina = dolzina_poti[i]
opt_pot = pot[i]
for i in range(n-1):
pher_dodan[opt_pot[i][0]][opt_pot[i][1]] = p*(q/min_dolzina)
pher_dodan[opt_pot[i][1]][opt_pot[i][0]] = pher[opt_pot[i][0]][opt_pot[i][1]]
for i in range(n):
for j in range(n):
pher[i][j] = (1-p)*pher[i][j] + pher_dodan[i][j]
for i in range(n-1):
pher_dodan[opt_pot[i][0]][opt_pot[i][1]] = 0
pher_dodan[opt_pot[i][1]][opt_pot[i][0]] = 0
#print(dolzina_poti) # dolzina poti v zadnji iteraciji
#print(opt_pot) # optimalna pot
print(min_dolzina) # dolzina opt poti (to nas zanima!)
#print(pher) # kolicina pher ob koncu
global tj
tj= time.time()
print("Ant Colony " + str(tj-inp))
for i in range(10):
main()
t = time.time()
print("skupni " + str(t - start))