71 lines
2.1 KiB
Python
71 lines
2.1 KiB
Python
|
import random
|
||
|
|
||
|
table_coords = [(12, 2), (16, 11), (4, 4), (15, 4), (2, 9), (15, 15), (12, 12), (7, 8), (4, 15)]
|
||
|
|
||
|
def krzyzowanie(rodzic1, rodzic2, pnkt):
|
||
|
dzieciak1 = rodzic1[:]
|
||
|
for i in range(pnkt):
|
||
|
tempInd = dzieciak1.index(rodzic2[i])
|
||
|
dzieciak1[tempInd] = dzieciak1[i]
|
||
|
dzieciak1[i] = rodzic2[i]
|
||
|
|
||
|
dzieciak2 = rodzic2[:]
|
||
|
for i in range(pnkt):
|
||
|
tempInd = dzieciak2.index(rodzic1[i])
|
||
|
dzieciak2[tempInd] = dzieciak2[i]
|
||
|
dzieciak2[i] = rodzic1[i]
|
||
|
|
||
|
return dzieciak1, dzieciak2
|
||
|
|
||
|
def stworzOsobnika():
|
||
|
return random.sample(table_coords, len(table_coords))
|
||
|
|
||
|
def rankuj(populacja):
|
||
|
return sorted(populacja, key=lambda x: funkcjaCelu(x))
|
||
|
def funkcjaCelu(osobnik):
|
||
|
sum = 0
|
||
|
for i in range(len(osobnik)):
|
||
|
j = i + 1
|
||
|
if i == len(osobnik) - 1:
|
||
|
j = 0
|
||
|
sum += abs(osobnik[i][0] - osobnik[j][0]) + abs(osobnik[i][1] - osobnik[j][1])
|
||
|
|
||
|
sum += abs(5 - osobnik[0][0]) + abs(5 - osobnik[0][1]) #dodawanie odległości od punktu (5,5), spawn agenta
|
||
|
return sum
|
||
|
|
||
|
def mutacja(osobnik):
|
||
|
|
||
|
if random.random() < 0.01:
|
||
|
ind1 = random.randint(0, len(osobnik)-1)
|
||
|
ind2 = random.randint(0, len(osobnik)-1)
|
||
|
osobnik[ind1], osobnik[ind2] = osobnik[ind2], osobnik[ind1]
|
||
|
return osobnik
|
||
|
|
||
|
def genetyk(liczebnosc, iteracje):
|
||
|
populacja = [stworzOsobnika() for _ in range(liczebnosc)]
|
||
|
|
||
|
for i in range(iteracje):
|
||
|
rankingowaPopulacja = rankuj(populacja)
|
||
|
populacja = rankingowaPopulacja[:liczebnosc]
|
||
|
nowePokolenie = []
|
||
|
|
||
|
for j in range(0, liczebnosc, 2):
|
||
|
rodzic1 = rankingowaPopulacja[j]
|
||
|
rodzic2 = rankingowaPopulacja[j+1]
|
||
|
punktKrzyzowania = random.randint(0, 7)
|
||
|
|
||
|
dzeciak1, dzieciak2 = krzyzowanie(rodzic1, rodzic2, punktKrzyzowania)
|
||
|
|
||
|
dzeciak1 = mutacja(dzeciak1)
|
||
|
dzieciak2 = mutacja(dzieciak2)
|
||
|
|
||
|
nowePokolenie.extend([dzeciak1, dzieciak2])
|
||
|
|
||
|
populacja.extend(nowePokolenie)
|
||
|
|
||
|
najlepszy = rankuj(populacja)[0]
|
||
|
return najlepszy
|
||
|
|
||
|
data = genetyk(50, 30)
|
||
|
print(funkcjaCelu(data))
|
||
|
print(data)
|