遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。它能解決很多問題，比如數學方程的最大最小值，背包問題，裝箱問題等。在游戲開發中遺傳算法的應用也十分頻繁，不少的游戲 AI 都利用遺傳算法進行編碼。
就個人理解，遺傳算法是模擬神奇的大自然中生物“優勝劣汰”原則指導下的進化過程，好的基因有更多的機會得到繁衍，這樣一來，隨著繁衍的進行，生物種群會朝著一個趨勢收斂。而生物繁衍過程中的基因雜交和變異會給種群提供更好的基因序列，這樣種群的繁衍趨勢將會是“長江后浪推前浪，一代更比一代強”，而不會是只受限于祖先的最好基因。而程序可以通過模擬這種過程來獲得問題的最優解（但不一定能得到）。要利用該過程來解決問題，受限需要構造初始的基因組，并為對每個基因進行適應性分數（衡量該基因的好壞程度）初始化，接著從初始的基因組中選出兩個父基因（根據適應性分數，采用輪盤算法進行選擇）進行繁衍，基于一定的雜交率（父基因進行雜交的概率）和變異率（子基因變異的概率），這兩個父基因會生成兩個子基因，然后將這兩個基因放入種群中，到這里繁衍一代完成，重復繁衍的過程直到種群收斂或適應性分數達到最大。
接下來我們就看看用遺傳算法沖出迷宮的實例。
代碼如下：
java" id="highlighter_94077">
|
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
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
|
import java.awt.Color;import java.awt.Graphics;import java.awt.GridLayout;import java.util.ArrayList;import java.util.List;import java.util.Random;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;@SuppressWarnings("serial")public class MazeProblem extends JFrame{ //當前基因組 private static List<Gene> geneGroup = new ArrayList<>(); private static Random random = new Random(); private static int startX = 2; private static int startY = 0; private static int endX = 7; private static int endY = 14; //雜交率 private static final double CROSSOVER_RATE = 0.7; //變異率 private static final double MUTATION_RATE = 0.0001; //基因組初始個數 private static final int POP_SIZE = 140; //基因長度 private static final int CHROMO_LENGTH = 70; //最大適應性分數的基因 private static Gene maxGene = new Gene(CHROMO_LENGTH); //迷宮地圖 private static int[][] map = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1,1,0,0,0,1}, {5,0,0,0,0,0,0,0,1,1,1,0,0,0,1}, {1,0,0,0,1,1,1,0,0,1,0,0,0,0,1}, {1,0,0,0,1,1,1,0,0,0,0,0,1,0,1}, {1,1,0,0,1,1,1,0,0,0,0,0,1,0,1}, {1,0,0,0,0,1,0,0,0,0,1,1,1,0,1}, {1,0,1,1,0,0,0,1,0,0,0,0,0,0,8}, {1,0,1,1,0,0,0,1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}; private static int MAP_WIDTH = 15; private static int MAP_HEIGHT = 10; private List<JLabel> labels = new ArrayList<>(); public MazeProblem(){ // 初始化 setSize(700, 700); setDefaultCloseOperation(DISPOSE_ON_CLOSE); setResizable(false); getContentPane().setLayout(null); JPanel panel = new JPanel(); panel.setLayout(new GridLayout(MAP_HEIGHT,MAP_WIDTH)); panel.setBounds(10, 10, MAP_WIDTH*40, MAP_HEIGHT*40); getContentPane().add(panel); for(int i=0;i<MAP_HEIGHT;i++){ for(int j=0;j<MAP_WIDTH;j++){ JLabel label = new JLabel(); Color color = null; if(map[i][j] == 1){ color = Color.black; } if(map[i][j] == 0){ color = Color.GRAY; } if(map[i][j] == 5 || map[i][j] ==8){ color = Color.red; } label.setBackground(color); label.setOpaque(true); panel.add(label); labels.add(label); } } } @Override public void paint(Graphics g) { super.paint(g); //畫出路徑 int[] gene = maxGene.getGene(); int curX = startX; int curY = startY; for(int i=0;i<gene.length;i+=2){ //上 if(gene[i] == 0 && gene[i+1] == 0){ if(curX >=1 && map[curX-1][curY] == 0){ curX --; } } //下 else if(gene[i] == 0 && gene[i+1] == 1){ if(curX <=MAP_HEIGHT-1 && map[curX+1][curY] == 0){ curX ++; } } //左 else if(gene[i] == 1 && gene[i+1] == 0){ if(curY >=1 && map[curX][curY-1] == 0){ curY --; } } //右 else{ if(curY <= MAP_WIDTH-1 && map[curX][curY+1] == 0){ curY ++; } } labels.get(curX*MAP_WIDTH+curY).setBackground(Color.BLUE); } } public static void main(String[] args) { //初始化基因組 init(); while(maxGene.getScore() < 1){ //選擇進行交配的兩個基因 int p1 = getParent(geneGroup); int p2 = getParent(geneGroup); //用輪盤轉動法選擇兩個基因進行交配,雜交和變異 mate(p1,p2); } new MazeProblem().setVisible(true); } /** * 根據路徑獲得適應性分數 * @param path * @return */ private static double getScore(int[] gene){ double result = 0; int curX = startX; int curY = startY; for(int i=0;i<gene.length;i+=2){ //上 if(gene[i] == 0 && gene[i+1] == 0){ if(curX >=1 && map[curX-1][curY] == 0){ curX --; } } //下 else if(gene[i] == 0 && gene[i+1] == 1){ if(curX <=MAP_HEIGHT-1 && map[curX+1][curY] == 0){ curX ++; } } //左 else if(gene[i] == 1 && gene[i+1] == 0){ if(curY >=1 && map[curX][curY-1] == 0){ curY --; } } //右 else{ if(curY <= MAP_WIDTH-1 && map[curX][curY+1] == 0){ curY ++; } } } double x = Math.abs(curX - endX); double y = Math.abs(curY - endY); //如果和終點只有一格距離則返回1 if((x == 1&& y==0) || (x==0&&y==1)){ return 1; } //計算適應性分數 result = 1/(x+y+1); return result; } /** * 基因初始化 */ private static void init(){ for(int i=0;i<POP_SIZE;i++){ Gene gene = new Gene(CHROMO_LENGTH); double score = getScore(gene.getGene()); if(score > maxGene.getScore()){ maxGene = gene; } gene.setScore(score); geneGroup.add(gene); } } /** * 根據適應性分數隨機獲得進行交配的父類基因下標 * @param list * @return */ private static int getParent(List<Gene> list){ int result = 0; double r = random.nextDouble(); double score; double sum = 0; double totalScores = getTotalScores(geneGroup); for(int i=0;i<list.size();i++){ Gene gene = list.get(i); score = gene.getScore(); sum += score/totalScores; if(sum >= r){ result = i; return result; } } return result; } /** * 獲得全部基因組的適應性分數總和 * @param list * @return */ private static double getTotalScores(List<Gene> list){ double result = 0; for(int i=0;i<list.size();i++){ result += list.get(i).getScore(); } return result; } /** * 兩個基因進行交配 * @param p1 * @param p2 */ private static void mate(int n1,int n2){ Gene p1 = geneGroup.get(n1); Gene p2 = geneGroup.get(n2); Gene c1 = new Gene(CHROMO_LENGTH); Gene c2 = new Gene(CHROMO_LENGTH); int[] gene1 = new int[CHROMO_LENGTH]; int[] gene2 = new int[CHROMO_LENGTH]; for(int i=0;i<CHROMO_LENGTH;i++){ gene1[i] = p1.getGene()[i]; gene2[i] = p2.getGene()[i]; } //先根據雜交率決定是否進行雜交 double r = random.nextDouble(); if(r >= CROSSOVER_RATE){ //決定雜交起點 int n = random.nextInt(CHROMO_LENGTH); for(int i=n;i<CHROMO_LENGTH;i++){ int tmp = gene1[i]; gene1[i] = gene2[i]; gene2[i] = tmp; } } //根據變異率決定是否 r = random.nextDouble(); if(r >= MUTATION_RATE){ //選擇變異位置 int n = random.nextInt(CHROMO_LENGTH); if(gene1[n] == 0){ gene1[n] = 1; } else{ gene1[n] = 0; } if(gene2[n] == 0){ gene2[n] = 1; } else{ gene2[n] = 0; } } c1.setGene(gene1); c2.setGene(gene2); double score1 = getScore(c1.getGene()); double score2 = getScore(c2.getGene()); if(score1 >maxGene.getScore()){ maxGene = c1; } if(score2 >maxGene.getScore()){ maxGene = c2; } c1.setScore(score1); c2.setScore(score2); geneGroup.add(c1); geneGroup.add(c2); }}/** * 基因 * @author ZZF * */class Gene{ //染色體長度 private int len; //基因數組 private int[] gene; //適應性分數 private double score; public Gene(int len){ this.len = len; gene = new int[len]; Random random = new Random(); //隨機生成一個基因序列 for(int i=0;i<len;i++){ gene[i] = random.nextInt(2); } //適應性分數設置為0 this.score = 0; } public int getLen() { return len; } public void setLen(int len) { this.len = len; } public int[] getGene() { return gene; } public void setGene(int[] gene) { this.gene = gene; } public double getScore() { return score; } public void setScore(double score) { this.score = score; } public void print(){ StringBuilder sb = new StringBuilder(); for(int i=0;i<gene.length;i+=2){ if(gene[i] == 0 && gene[i+1] == 0){ sb.append("上"); } //下 else if(gene[i] == 0 && gene[i+1] == 1){ sb.append("下"); } //左 else if(gene[i] == 1 && gene[i+1] == 0){ sb.append("左"); } //右 else{ sb.append("右"); } } System.out.println(sb.toString()); }} |
以上就是本文關于遺傳算法沖出迷宮方法實例解析，希望對大家有所幫助。
原文鏈接：https://www.2cto.com/kf/201706/649186.html
