# Univerzitet u Novom Sadu, Fakultet tehničkih nauka, Novi Sad, Srbija # Studijski program OAS Informacioni inženjering # Predmet Metode i tehnike nauke o podacima # Pomoćni sadržaj # %% Biblioteke import random # %% Pomoćne klase class Jedinka: def __init__(self, indeksi): self.indeksi = indeksi self.vrednost = None def prebrajanje_indeksa(self): return len(self.indeksi) def formiranje_opisa(self, nazivi): return [nazivi[i - 1] for i in self.indeksi] def __str__(self): return "({}, {})".format(self.indeksi, self.vrednost) class Populacija: def __init__(self, jedinke): self.jedinke = jedinke def dodavanje_jedinke(self, jedinka): self.jedinke.append(jedinka) def sortiranje(self, obrnuto=True): self.jedinke.sort(key=lambda k: k.vrednost, reverse=obrnuto) def __str__(self): return "\n".join([str(jedinka) for jedinka in self.jedinke]) class Prilagođenost: def __init__(self, matrica, početak, kraj): self.matrica = matrica self.početak = početak self.kraj = kraj def evaluiranje(self, jedinka): vrednost = 0 vrednost += self.matrica[self.početak - 1][jedinka.indeksi[0] - 1] vrednost += self.matrica[jedinka.indeksi[-1] - 1][self.kraj - 1] if jedinka.prebrajanje_indeksa() > 1: for i in range(jedinka.prebrajanje_indeksa() - 1): vrednost += (self.matrica[jedinka.indeksi[i] - 1] [jedinka.indeksi[i + 1] - 1]) return vrednost # %% Implementacija genetskog algoritma class GenetskiAlgoritam: def __init__(self, nazivi, matrica, naziv_početka, naziv_kraja, veličina_populacije, broj_evoluiranih_generacija, prag_mutacije): self.nazivi = nazivi self.matrica = matrica self.naziv_početka = naziv_početka self.naziv_kraja = naziv_kraja self.veličina_populacije = veličina_populacije self.broj_evoluiranih_generacija = broj_evoluiranih_generacija self.prag_mutacije = prag_mutacije self.pokrenuto_izvršavanje = False self.rešenje = None def izvršavanje(self, prikaz=True): self.pokrenuto_izvršavanje = True self.rešenje = None dozvoljene_vrednosti = [i + 1 for i in range(len(self.nazivi)) if self.nazivi[i] != self.naziv_početka and self.nazivi[i] != self.naziv_kraja] prilagođenost = Prilagođenost(self.matrica, self.nazivi.index(self.naziv_početka) + 1, self.nazivi.index(self.naziv_kraja) + 1) težine = range(1, self.veličina_populacije + 1) tačke = range(len(dozvoljene_vrednosti)) populacija = Populacija([]) for i in range(self.veličina_populacije): jedinka = Jedinka(random.sample( dozvoljene_vrednosti, len(dozvoljene_vrednosti))) jedinka.vrednost = prilagođenost.evaluiranje(jedinka) populacija.dodavanje_jedinke(jedinka) for i in range(self.broj_evoluiranih_generacija): potomstvo = Populacija([]) populacija.sortiranje() if prikaz: print("Populacija", i) print(populacija) if prikaz: print("Faza selekcije") parovi = [] for p in range(self.veličina_populacije // 2): partner_a = random.choices(populacija.jedinke, weights=težine)[0] partner_b = random.choices(populacija.jedinke, weights=težine)[0] while partner_b is partner_a: partner_b = random.choices(populacija.jedinke, weights=težine)[0] parovi.append((partner_a, partner_b)) if prikaz: print(" Selekcija: {} {}".format(partner_a, partner_b)) if prikaz: print("Faza ukrštanja") for par in parovi: trenutni_indeksi_a = par[0].indeksi trenutni_indeksi_b = par[1].indeksi lokacije = random.sample(tačke, 2) lokacije.sort() prvi_indeks_a = trenutni_indeksi_a[lokacije[0]] drugi_indeks_a = trenutni_indeksi_a[lokacije[1]] prvi_indeks_b = trenutni_indeksi_b[lokacije[0]] drugi_indeks_b = trenutni_indeksi_b[lokacije[1]] novi_indeksi_a = list(trenutni_indeksi_a) novi_indeksi_b = list(trenutni_indeksi_b) if (trenutni_indeksi_b.index(prvi_indeks_a) > trenutni_indeksi_b.index(drugi_indeks_a)): novi_indeksi_a[lokacije[0]] = drugi_indeks_a novi_indeksi_a[lokacije[1]] = prvi_indeks_a if (trenutni_indeksi_a.index(prvi_indeks_b) > trenutni_indeksi_a.index(drugi_indeks_b)): novi_indeksi_b[lokacije[0]] = drugi_indeks_b novi_indeksi_b[lokacije[1]] = prvi_indeks_b jedinka_a = Jedinka(novi_indeksi_a) jedinka_a.vrednost = prilagođenost.evaluiranje(jedinka_a) potomstvo.dodavanje_jedinke(jedinka_a) jedinka_b = Jedinka(novi_indeksi_b) jedinka_b.vrednost = prilagođenost.evaluiranje(jedinka_b) potomstvo.dodavanje_jedinke(jedinka_b) if prikaz: print(" Ukrštanje: {} {} > {} > \n {} {}".format( par[0], par[1], lokacije, jedinka_a, jedinka_b)) if prikaz: print("Faza mutacije") for jedinka in potomstvo.jedinke: if random.randint(1, 100) <= self.prag_mutacije: zatečena_jedinka = Jedinka(jedinka.indeksi) zatečena_jedinka.vrednost = jedinka.vrednost jedinka.indeksi = (zatečena_jedinka.indeksi[1:] + [zatečena_jedinka.indeksi[0]]) jedinka.vrednost = prilagođenost.evaluiranje(jedinka) if prikaz: print(" Mutacija: {} > {}".format( zatečena_jedinka, jedinka)) populacija = potomstvo if prikaz: print("") populacija.sortiranje() if prikaz: print("Populacija", self.broj_evoluiranih_generacija) print(populacija) self.rešenje = populacija.jedinke[-1] def preuzimanje_rešenja(self): return self.rešenje # %% Upotreba genetskog algoritma random.seed(11) mesta = ["ZR", "KI", "KA", "NS", "SU", "SO"] print("Mesta") print(mesta) print("") razdaljine = [ [ 0, 55, 100, 45, 130, 115], [ 55, 0, 55, 90, 85, 115], [100, 55, 0, 105, 40, 95], [ 45, 90, 105, 0, 100, 95], [130, 85, 40, 100, 0, 60], [115, 115, 95, 95, 60, 0] ] print("Razdaljine") for red in razdaljine: print(red) print("") genetski_algoritam = GenetskiAlgoritam( mesta, razdaljine, "SU", "SO", 10, 15, 5) print("Izvršavanje genetskog algoritma") print("") genetski_algoritam.izvršavanje() print("") print("Rešenje") rešenje = genetski_algoritam.preuzimanje_rešenja() print("Sadržaj: {}".format(rešenje if rešenje is not None else "/")) if rešenje is not None: putanja = ([genetski_algoritam.naziv_početka] + rešenje.formiranje_opisa(genetski_algoritam.nazivi) + [genetski_algoritam.naziv_kraja]) print("Putanja: {}".format(putanja))