Genetski algoritam

import random
import itertools
import datetime

br_gradova = 10
gradovi = [(random.random()*10, random.random()*10) for i in range(br_gradova)]

udaljenosti = []

for p in itertools.permutations(gradovi):
    udaljenost = 0
    for i in range(len(p)-1):
        udaljenost += (p[i][0]-p[i+1][0])**2 + (p[i][1]-p[i+1][1])**2

    udaljenost += (p[0][0]-p[len(p)-1][0])**2 + (p[0][1]-p[len(p)-1][1])**2
    udaljenosti.append(udaljenost)

udaljenosti.sort()
print(datetime.datetime.now())
print("Najkraca putanja je : ",udaljenosti[0])


class Jedinka:
    def __init__(self):
        self.hromozom = []

    def inicijalizuj(self, duzina_hromozoma):
        self.hromozom = list(range(duzina_hromozoma))
        random.shuffle(self.hromozom)


    def fitness(self,gradovi):
        indeksi = list(self.hromozom)
        indeksi.append(indeksi[0])
        udaljenost = 0
        for i in range(len(indeksi)-1):
            udaljenost += (gradovi[indeksi[i]][0] - gradovi[indeksi[i+1]][0])**2 + (gradovi[indeksi[i]][1] - gradovi[indeksi[i+1]][1])**2
        return udaljenost

    def mutiraj(self):
        if random.random() > 0.8:
            prvi = random.randrange(len(self.hromozom))
            drugi = random.randrange(len(self.hromozom))

        self.hromozom[prvi], self.hromozom[drugi] = self.hromozom[drugi], self.hromozom[prvi]

    def ukrstanje(self, druga):
        pocetak = random.randrange(0, len(self.hromozom)-1)
        kraj = random.randrange(pocetak, len(self.hromozom))

        nova1 = Jedinka()

        nova1.hromozom = list(druga.hromozom)
        nova1.hromozom[pocetak:kraj] = self.hromozom[pocetak:kraj]

        nedozvoljeni = set(self.hromozom[pocetak:kraj])

        j=kraj
        for i in range(kraj, len(nova1.hromozom)):
            while(druga.hromozom[j%len(druga.hromozom)] in nedozvoljeni):
                j += 1

            nova1.hromozom[i] = druga.hromozom[j%len(druga.hromozom)]
            j += 1

        for i in range(0, pocetak):
            while(druga.hromozom[j%len(druga.hromozom)] in nedozvoljeni):
                j += 1

            nova1.hromozom[i] = druga.hromozom[j%len(druga.hromozom)]
            j += 1



        nova2 = Jedinka()

        nova2.hromozom = list(self.hromozom)
        nova2.hromozom[pocetak:kraj] = druga.hromozom[pocetak:kraj]
        nedozvoljeni = set(druga.hromozom[pocetak:kraj])

                #--------------------------------------Za Novu2 jedinku-------------------------------------------


        j=kraj
        for i in range(kraj, len(nova2.hromozom)):
            while(self.hromozom[j%len(self.hromozom)] in nedozvoljeni):
                j += 1

            nova2.hromozom[i] = self.hromozom[j%len(self.hromozom)]
            j += 1

        for i in range(0, pocetak):
            while(self.hromozom[j%len(self.hromozom)] in nedozvoljeni):
                j += 1

            nova2.hromozom[i] = self.hromozom[j%len(self.hromozom)]
            j += 1
        #-------------------------------------------------------------------------------------------

        return [nova1, nova2]

    def __repr__(self):
        return str(self.hromozom)


class Populacija:
    def __init__(self,gradovi,broj_jedinki=100):
        self.gradovi = gradovi
        self.broj_jedinki = broj_jedinki
        self.jedinke = []
        for i in range(broj_jedinki):
            j = Jedinka()
            j.inicijalizuj(len(self.gradovi))
            self.jedinke.append(j)

    def fit(self, broj_iteracija=100):
        for _ in range(broj_iteracija):
            sample_a = random.sample(self.jedinke, 20)
            sample_b = random.sample(self.jedinke, 20)
            for i, j in enumerate(sample_a):
                self.jedinke.extend(j.ukrstanje(sample_b[i]))

            self.jedinke.sort(key=lambda j: j.fitness(self.gradovi))
            self.jedinke = self.jedinke[:self.broj_jedinki]



# test_jedinka = Jedinka()
# test_jedinka.inicijalizuj(len(gradovi))
# print(test_jedinka)
# print(test_jedinka.fitness(gradovi))
# test_jedinka.mutiraj() Ispraviti mutiranje
# print(test_jedinka)

# test_jedinka2 = Jedinka()
# test_jedinka2.inicijalizuj(len(gradovi))

# rezultat = test_jedinka.ukrstanje(test_jedinka2)
# print(rezultat)
# print(sorted(rezultat[0].hromozom), sorted(rezultat[1].hromozom))

print("Genetski algoritam")
populacija = Populacija(gradovi, 100)
populacija.fit(1000)
print(populacija.jedinke[0].fitness(gradovi))
print(populacija.jedinke[0])
print(datetime.datetime.now())