Facebook
From Funky Capybara, 1 Year ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 102
  1. import random as rd
  2. import numpy as np
  3.  
  4.  
  5. def suma_kolejnych(x):
  6.     w = 0
  7.     for i in range(1, x+1):
  8.         w += x
  9.     return w
  10.  
  11. def losuj_gen(color_no):
  12.     return rd.randint(0, color_no-1)
  13.  
  14. def losuj_populacje_startowa(l_osobnikow, n, color_no):
  15.     populacja = np.zeros((l_osobnikow, n))
  16.     for i in range(l_osobnikow):
  17.         for j in range(n):
  18.             populacja[i][j] = losuj_gen(color_no)
  19.     return populacja
  20.  
  21. def f_oceny(osobnik, M, n):
  22.     fail_no = 0
  23.     for i in range(len(osobnik)):
  24.         for j in range(n):
  25.             if M[i][j] != 0:
  26.                 if osobnik[i] == osobnik[j]:
  27.                     fail_no += 1
  28.     return fail_no
  29.  
  30. def selekcja_metoda_ranking(populacja, f_oceny, M, n, l_osobnikow):
  31.     osobnik_pom = []
  32.     for i in range(populacja.shape[0]):
  33.         osobnik_pom.append([populacja[i], f_oceny(populacja[i], M, n)])
  34.     sorted(osobnik_pom, key= lambda osobnik_pom: osobnik_pom[1], reverse=True)
  35.  
  36.     new_populacja = losuj_populacje_startowa(l_osobnikow, n, 1)
  37.     maks_los = suma_kolejnych(populacja.shape[0])
  38.     for i in range(populacja.shape[0]):
  39.         los = rd.randint(0, maks_los-1)
  40.         x = 0
  41.         while los < suma_kolejnych(x):
  42.             x += 1
  43.         for j in range(populacja.shape[1]):
  44.             new_populacja[i][j] = osobnik_pom[0][x][j]
  45.     return new_populacja
  46.  
  47. def krzyzowanie(populacja, war_krzyzowania, n):
  48.     for i in range(0, populacja.shape[0], 2):
  49.         krzyzuj = rd.random()
  50.         if krzyzuj < war_krzyzowania:
  51.             cross_point = rd.randint(1, n-1)
  52.             rodzic1 = populacja[i]
  53.             rodzic2 = populacja[i+1]
  54.             for j in range(n):
  55.                 if j <= cross_point:
  56.                     populacja[i][j] = rodzic2[j]
  57.                     populacja[i+1][j] = rodzic1[j]
  58.     return populacja
  59.  
  60. def mutacja(populacja, war_mutacji, color_no):
  61.     for i in range(0, populacja.shape[0]):
  62.         mutuj = rd.random()
  63.         if mutuj < war_mutacji:
  64.             for j in range(populacja.shape[1]):
  65.                 mutuj_gen = rd.random()
  66.                 if mutuj_gen < war_mutacji:
  67.                     populacja[i][j] = losuj_gen(color_no)
  68.     return populacja
  69.  
  70. def najlepszy(populacja, f_oceny, M, n, best, best_f):
  71.     best_grade = 99999999999
  72.     for osobnik in populacja:
  73.         grade = f_oceny(osobnik, M, n)
  74.         if grade < best_grade:
  75.             best_grade = grade
  76.             if grade < best_f:
  77.                 best_f = grade
  78.                 best = osobnik
  79.     return best, best_f
  80.  
  81. def kolorowanie_genetyczne(color_no, M, n, max_iter, l_osobnikow, war_stop, war_krzyzowania, war_mutacji):
  82.     iter_no = 0
  83.     best_f = 99999999
  84.     populacja = losuj_populacje_startowa(l_osobnikow, n, color_no)
  85.     best = populacja[0]
  86.     rd.seed()
  87.  
  88.     while iter_no < max_iter and best_f > war_stop:
  89.         #selekcja
  90.         populacja = selekcja_metoda_ranking(populacja, f_oceny, M, n, l_osobnikow)
  91.         #krzyzowanie
  92.         populacja = krzyzowanie(populacja, war_krzyzowania, n)
  93.         #mutacja
  94.         populacja = mutacja(populacja, war_mutacji, color_no)
  95.         #spr wyniku
  96.         best, best_f = najlepszy(populacja, f_oceny, M, n, best, best_f)
  97.         iter_no += 1
  98.  
  99.     best_f /= 2
  100.     if best_f <= war_stop:
  101.         return True, best_f
  102.     else:
  103.         return False, best_f
  104.  
  105.  
  106. file = open("C:/my_pc/Code/moje/Algosy/kolorowanie grafow/q6x6.txt", 'r')
  107. n = int(file.readline())
  108. M = np.zeros((n,n))
  109. for line in file:
  110.     pom = line.split()
  111.     M[int(pom[0])-1][int(pom[1])-1] = 1
  112. file.close()
  113.  
  114. czy, best_f = kolorowanie_genetyczne(10, M, n, 5000, 10, 5, 0.3, 0.8)
  115. print(czy, best_f)