（一）問題
遺傳算法求解正方形拼圖游戲
（二）代碼
|
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): ''' 定義顏色的類，這個(gè)類包含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): ''' 生成隨機(jī)數(shù)，判斷是否需要變異 ''' return True if rate > r.random() else False class Triangle(object): ''' 定義三角形的類 屬性： ax,ay,bx,by,cx,cy：表示每個(gè)三角形三個(gè)頂點(diǎn)的坐標(biāo) 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: 目標(biāo)圖片像素值 方法： add_triangles(self, num=1) : 在圖片類中生成num個(gè)三角形 mutate_from_parent(self, parent): 從父代圖片對象進(jìn)行變異 calc_match_rate(self) : 計(jì)算環(huán)境適應(yīng)度 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通道三個(gè)矩陣分別與目標(biāo)圖片相應(yīng)通道作差取平方加和評估相似度 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())] # 生成一系列的圖片作為父本，選擇其中最好的一個(gè)進(jìn)行遺傳 parentList = [] for i in range(20): print('正在生成第%d個(gè)初代個(gè)體' % (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() # 進(jìn)入遺傳算法的循環(huán) i = 0 while i < 30000: childList = [] # 每一代從父代中變異出10個(gè)個(gè)體 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] # 選擇其中適應(yīng)度最好的一個(gè)個(gè)體 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 # 如果子代比父代更適應(yīng)環(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('.') # 取當(dāng)前路徑PATH = os.path.join(PATH,'results')TARGET = NAME # 源圖片文件名TRIANGLE_NUM = 256 # 三角形個(gè)數(shù) if __name__ == '__main__': #print('開始進(jìn)行遺傳算法') main() |
（三）運(yùn)行結(jié)果
（四）結(jié)果描述
代碼是在遺傳算法求解三角形火狐拼圖改進(jìn)而來，遺傳算法求解正方形拼圖游戲只需隨機(jī)生成一個(gè)坐標(biāo)和一個(gè)常數(shù)值（作為正方形的邊長），通過正方形的性質(zhì)，可以寫出正方形其他三個(gè)點(diǎn)的坐標(biāo)，確定了四個(gè)點(diǎn)的坐標(biāo)之后，進(jìn)行遺傳和變異。
到此這篇關(guān)于Python實(shí)現(xiàn)遺傳算法(虛擬機(jī)中運(yùn)行)的文章就介紹到這了,更多相關(guān)Python 遺傳算法內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/qq_52137561/article/details/121492555
