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