- import random as rd
- import numpy as np
- def suma_kolejnych(x):
- w = 0
- for i in range(1, x+1):
- w += x
- return w
- def losuj_gen(color_no):
- return rd.randint(0, color_no-1)
- def losuj_populacje_startowa(l_osobnikow, n, color_no):
- populacja = np.zeros((l_osobnikow, n))
- for i in range(l_osobnikow):
- for j in range(n):
- populacja[i][j] = losuj_gen(color_no)
- return populacja
- def f_oceny(osobnik, M, n):
- fail_no = 0
- for i in range(len(osobnik)):
- for j in range(n):
- if M[i][j] != 0:
- if osobnik[i] == osobnik[j]:
- fail_no += 1
- return fail_no
- def selekcja_metoda_ranking(populacja, f_oceny, M, n, l_osobnikow):
- osobnik_pom = []
- for i in range(populacja.shape[0]):
- osobnik_pom.append([populacja[i], f_oceny(populacja[i], M, n)])
- sorted(osobnik_pom, key= lambda osobnik_pom: osobnik_pom[1], reverse=True)
- new_populacja = losuj_populacje_startowa(l_osobnikow, n, 1)
- maks_los = suma_kolejnych(populacja.shape[0])
- for i in range(populacja.shape[0]):
- los = rd.randint(0, maks_los-1)
- x = 0
- while los < suma_kolejnych(x):
- x += 1
- for j in range(populacja.shape[1]):
- new_populacja[i][j] = osobnik_pom[0][x][j]
- return new_populacja
- def krzyzowanie(populacja, war_krzyzowania, n):
- for i in range(0, populacja.shape[0], 2):
- krzyzuj = rd.random()
- if krzyzuj < war_krzyzowania:
- cross_point = rd.randint(1, n-1)
- rodzic1 = populacja[i]
- rodzic2 = populacja[i+1]
- for j in range(n):
- if j <= cross_point:
- populacja[i][j] = rodzic2[j]
- populacja[i+1][j] = rodzic1[j]
- return populacja
- def mutacja(populacja, war_mutacji, color_no):
- for i in range(0, populacja.shape[0]):
- mutuj = rd.random()
- if mutuj < war_mutacji:
- for j in range(populacja.shape[1]):
- mutuj_gen = rd.random()
- if mutuj_gen < war_mutacji:
- populacja[i][j] = losuj_gen(color_no)
- return populacja
- def najlepszy(populacja, f_oceny, M, n, best, best_f):
- best_grade = 99999999999
- for osobnik in populacja:
- grade = f_oceny(osobnik, M, n)
- if grade < best_grade:
- best_grade = grade
- if grade < best_f:
- best_f = grade
- best = osobnik
- return best, best_f
- def kolorowanie_genetyczne(color_no, M, n, max_iter, l_osobnikow, war_stop, war_krzyzowania, war_mutacji):
- iter_no = 0
- best_f = 99999999
- populacja = losuj_populacje_startowa(l_osobnikow, n, color_no)
- best = populacja[0]
- rd.seed()
- while iter_no < max_iter and best_f > war_stop:
- #selekcja
- populacja = selekcja_metoda_ranking(populacja, f_oceny, M, n, l_osobnikow)
- #krzyzowanie
- populacja = krzyzowanie(populacja, war_krzyzowania, n)
- #mutacja
- populacja = mutacja(populacja, war_mutacji, color_no)
- #spr wyniku
- best, best_f = najlepszy(populacja, f_oceny, M, n, best, best_f)
- iter_no += 1
- best_f /= 2
- if best_f <= war_stop:
- return True, best_f
- else:
- return False, best_f
- """
- file = open("data/queen6_6.txt", 'r')
- n = int(file.readline())
- M = np.zeros((n,n))
- for line in file:
- pom = line.split()
- M[int(pom[0])-1][int(pom[1])-1] = 1
- file.close()
- czy, best_f = kolorowanie_genetyczne(10, M, n, 5000, 10, 5, 0.3, 0.?
- print(czy, best_f)
- """