遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它能解决很多问题，比如数学方程的最大最小值，背包问题，装箱问题等。在游戏开发中遗传算法的应用也十分频繁，不少的游戏 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
