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)