（一）問題
遺傳算法求解正方形拼圖游戲
（二）代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
|
#!/usr/bin/env python# -*- coding: utf-8 -*- from PIL import Image, ImageDrawimport osimport gcimport random as rimport minpy.numpy as np class Color(object): ''' 定義顏色的類，這個類包含r,g,b,a表示顏色屬性 ''' def __init__(self): self.r = r.randint(0, 255) self.g = r.randint(0, 255) self.b = r.randint(0, 255) self.a = r.randint(95, 115) def mutate_or_not(rate): ''' 生成隨機數(shù)，判斷是否需要變異 ''' return True if rate > r.random() else False class Triangle(object): ''' 定義三角形的類 屬性： ax,ay,bx,by,cx,cy：表示每個三角形三個頂點的坐標 color : 表示三角形的顏色 img_t : 三角形繪制成的圖，用于合成圖片 方法： mutate_from(self, parent): 從父代三角形變異 draw_it(self, size=(256, 256)): 繪制三角形 ''' max_mutate_rate = 0.08 mid_mutate_rate = 0.3 min_mutate_rate = 0.8 def __init__(self, size=(255, 255)): t = r.randint(0, size[0]) self.ax = r.randint(0, size[0]) self.ay = r.randint(0, size[1]) self.bx = self.ax+t self.by = self.ay self.cx = self.ax+t self.cy = self.ay-t self.dx = self.ax self.dy = self.ay-t self.color = Color() self.img_t = None def mutate_from(self, parent): if mutate_or_not(self.max_mutate_rate): t = r.randint(0, 255) self.ax = r.randint(0, 255) self.ay = r.randint(0, 255) self.bx = self.ax + t self.by = self.ay self.dx = self.ax self.dy = self.ay - t self.cx = self.ax + t self.cy = self.ay - t if mutate_or_not(self.mid_mutate_rate): t = min(max(0, parent.ax + r.randint(-15, 15)), 255) self.ax = min(max(0, parent.ax + r.randint(-15, 15)), 255) self.ay = min(max(0, parent.ay + r.randint(-15, 15)), 255) self.bx = self.ax + t self.by = self.ay self.dx = self.ax self.dy = self.ay - t self.cx = self.ax + t self.cy = self.ay - t if mutate_or_not(self.min_mutate_rate): t = min(max(0, parent.ax + r.randint(-3, 3)), 255) self.ax = min(max(0, parent.ax + r.randint(-3, 3)), 255) self.ay = min(max(0, parent.ay + r.randint(-3, 3)), 255) self.bx = self.ax + t self.by = self.ay self.dx = self.ax self.dy = self.ay - t self.cx = self.ax + t self.cy = self.ay - t # color if mutate_or_not(self.max_mutate_rate): self.color.r = r.randint(0, 255) if mutate_or_not(self.mid_mutate_rate): self.color.r = min(max(0, parent.color.r + r.randint(-30, 30)), 255) if mutate_or_not(self.min_mutate_rate): self.color.r = min(max(0, parent.color.r + r.randint(-10, 10)), 255) if mutate_or_not(self.max_mutate_rate): self.color.g = r.randint(0, 255) if mutate_or_not(self.mid_mutate_rate): self.color.g = min(max(0, parent.color.g + r.randint(-30, 30)), 255) if mutate_or_not(self.min_mutate_rate): self.color.g = min(max(0, parent.color.g + r.randint(-10, 10)), 255) if mutate_or_not(self.max_mutate_rate): self.color.b = r.randint(0, 255) if mutate_or_not(self.mid_mutate_rate): self.color.b = min(max(0, parent.color.b + r.randint(-30, 30)), 255) if mutate_or_not(self.min_mutate_rate): self.color.b = min(max(0, parent.color.b + r.randint(-10, 10)), 255) # alpha if mutate_or_not(self.mid_mutate_rate): self.color.a = r.randint(95, 115) # if mutate_or_not(self.mid_mutate_rate): # self.color.a = min(max(0, parent.color.a + r.randint(-30, 30)), 255) # if mutate_or_not(self.min_mutate_rate): # self.color.a = min(max(0, parent.color.a + r.randint(-10, 10)), 255) def draw_it(self, size=(256, 256)): self.img_t = Image.new('RGBA', size) draw = ImageDraw.Draw(self.img_t) draw.polygon([(self.ax, self.ay), (self.bx, self.by), (self.cx, self.cy), (self.dx, self.dy)], fill=(self.color.r, self.color.g, self.color.b, self.color.a)) return self.img_t class Canvas(object): ''' 定義每一張圖片的類 屬性： mutate_rate : 變異概率 size : 圖片大小 target_pixels: 目標圖片像素值 方法： add_triangles(self, num=1) : 在圖片類中生成num個三角形 mutate_from_parent(self, parent): 從父代圖片對象進行變異 calc_match_rate(self) : 計算環(huán)境適應度 draw_it(self, i) : 保存圖片 ''' mutate_rate = 0.01 size = (256, 256) target_pixels = [] def __init__(self): self.triangles = [] self.match_rate = 0 self.img = None def add_triangles(self, num=1): for i in range(0, num): triangle = Triangle() self.triangles.append(triangle) def mutate_from_parent(self, parent): flag = False for triangle in parent.triangles: t = triangle if mutate_or_not(self.mutate_rate): flag = True a = Triangle() a.mutate_from(t) self.triangles.append(a) continue self.triangles.append(t) if not flag: self.triangles.pop() t = parent.triangles[r.randint(0, len(parent.triangles) - 1)] a = Triangle() a.mutate_from(t) self.triangles.append(a) def calc_match_rate(self): if self.match_rate > 0: return self.match_rate self.match_rate = 0 self.img = Image.new('RGBA', self.size) draw = ImageDraw.Draw(self.img) draw.polygon([(0, 0), (0, 255), (255, 255), (255, 0)], fill=(255, 255, 255, 255)) for triangle in self.triangles: self.img = Image.alpha_composite(self.img, triangle.img_t or triangle.draw_it(self.size)) # 與下方代碼功能相同，此版本便于理解但效率低 # pixels = [self.img.getpixel((x, y)) for x in range(0, self.size[0], 2) for y in range(0, self.size[1], 2)] # for i in range(0, min(len(pixels), len(self.target_pixels))): # delta_red = pixels[i][0] - self.target_pixels[i][0] # delta_green = pixels[i][1] - self.target_pixels[i][1] # delta_blue = pixels[i][2] - self.target_pixels[i][2] # self.match_rate += delta_red * delta_red + \ # delta_green * delta_green + \ # delta_blue * delta_blue arrs = [np.array(x) for x in list(self.img.split())] # 分解為RGBA四通道 for i in range(3): # 對RGB通道三個矩陣分別與目標圖片相應通道作差取平方加和評估相似度 self.match_rate += np.sum(np.square(arrs[i]-self.target_pixels[i]))[0] def draw_it(self, i): #self.img.save(os.path.join(PATH, "%s_%d_%d_%d.png" % (PREFIX, len(self.triangles), i, self.match_rate))) self.img.save(os.path.join(PATH, "%d.png" % (i))) def main(): global LOOP, PREFIX, PATH, TARGET, TRIANGLE_NUM # 聲明全局變量 img = Image.open(TARGET).resize((256, 256)).convert('RGBA') size = (256, 256) Canvas.target_pixels = [np.array(x) for x in list(img.split())] # 生成一系列的圖片作為父本，選擇其中最好的一個進行遺傳 parentList = [] for i in range(20): print('正在生成第%d個初代個體' % (i)) parentList.append(Canvas()) parentList[i].add_triangles(TRIANGLE_NUM) parentList[i].calc_match_rate() parent = sorted(parentList, key=lambda x: x.match_rate)[0] del parentList gc.collect() # 進入遺傳算法的循環(huán) i = 0 while i < 30000: childList = [] # 每一代從父代中變異出10個個體 for j in range(10): childList.append(Canvas()) childList[j].mutate_from_parent(parent) childList[j].calc_match_rate() child = sorted(childList, key=lambda x: x.match_rate)[0] # 選擇其中適應度最好的一個個體 del childList gc.collect() parent.calc_match_rate() if i % LOOP == 0: print ('%10d parent rate %11d \t child1 rate %11d' % (i, parent.match_rate, child.match_rate)) parent = parent if parent.match_rate < child.match_rate else child # 如果子代比父代更適應環(huán)境，那么子代成為新的父代 # 否則保持原樣 child = None if i % LOOP == 0: # 每隔LOOP代保存一次圖片 parent.draw_it(i) #print(parent.match_rate) #print ('%10d parent rate %11d \t child1 rate %11d' % (i, parent.match_rate, child.match_rate)) i += 1 '''定義全局變量，獲取待處理的圖片名'''NAME = input('請輸入原圖片文件名：')LOOP = 100PREFIX = NAME.split('/')[-1].split('.')[0] # 取文件名PATH = os.path.abspath('.') # 取當前路徑PATH = os.path.join(PATH,'results')TARGET = NAME # 源圖片文件名TRIANGLE_NUM = 256 # 三角形個數(shù) if __name__ == '__main__': #print('開始進行遺傳算法') main() |
（三）運行結(jié)果
（四）結(jié)果描述
代碼是在遺傳算法求解三角形火狐拼圖改進而來，遺傳算法求解正方形拼圖游戲只需隨機生成一個坐標和一個常數(shù)值（作為正方形的邊長），通過正方形的性質(zhì)，可以寫出正方形其他三個點的坐標，確定了四個點的坐標之后，進行遺傳和變異。
到此這篇關(guān)于Python實現(xiàn)遺傳算法(虛擬機中運行)的文章就介紹到這了,更多相關(guān)Python 遺傳算法內(nèi)容請搜索服務器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/qq_52137561/article/details/121492555
