什么是遗传算法？
遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
我们都用它来做什么？
一是基于遗传算法的机器学习，这一研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的机器学习算法。
二是遗传算法和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。
三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。
四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用。
五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。
当然，本人才疏学浅，只会用其自动组个卷。
遗传算法基本运算过程
a) 初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b) 个体评价：计算群体P(t)中各个个体的适应度。
c) 选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d) 交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
e) 变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值做变动，群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
f) 终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
实例分析
试题实体类：本试题实体针对大学英语四级设计，包含写作、听力、词汇理解、长阅读、仔细阅读两篇、翻译7个大题。并且含有遗传算法相关属性及方法。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
273package com.cet.pojo;
import java.util.List;
import java.util.Random;
import com.cet.service.ObjectService;
import com.cet.tool.Algorithm;
/**
* Test entity.
*/
public class Test implements java.io.Serializable {
/**
* 试题
*/
private static final long serialVersionUID = 1L;
// Fields
private Integer id;
private String name;
private BaseWriting baseWriting;
private BaseListening baseListening;
private BaseWordunderstand baseWordunderstand;
private BaseLongreading baseLongreading;
private BaseCarereading baseCarereading1;
private BaseCarereading baseCarereading2;
private BaseTranslate baseTranslate;
private int ismeta;
// 遗传算法相关属性
private float difficulty = 0;// 试卷难度
private double Fitness = 0;// 试卷适应度
public int genes[] = new int[7];// 试卷基因序列
/** default constructor */
public Test() {}
// 遗传算法相关方法
/**
* 计算试卷个体难度系数 计算公式： 每题难度*分数求和除总分
*
* @return
*/
public float getDifficulty() {
if (difficulty == 0) {
float _difficulty = (baseWriting.getDifficulty() * (float) 106.5
+ baseListening.getDifficulty() * (float) 248.5
+ baseTranslate.getDifficulty() * (float) 106.5
+ baseWordunderstand.getDifficulty() * (float) 36
+ baseLongreading.getDifficulty() * (float) 71
+ baseCarereading1.getDifficulty() * (float) 71 + baseCarereading2
.getDifficulty()
* (float) 71);
difficulty = (_difficulty / (float) 710.5);
}
return difficulty;
}
/**
* 计算个体适应度 公式为：f=1-|EP-P| 其中EP为期望难度系数，P为种群个体难度系数
*
* @param difficulty
* 期望难度系数
*/
public double getFitness(double EP) {
if (Fitness == 0) {
Fitness = 1 - Math.abs(EP - getDifficulty());
}
return Fitness;
}
/**
* 功能：避免重复题型
* 检查生成的Test的所有题型是否数据库已经存在，只要Test里有种题型和数据库的某个Test一样，就更换该题型为数据库所有Test里都没有的。
*
* @param test
* @return
*/
public boolean checkTest() {
ObjectService objectService = Algorithm.objectService;
Random random = new Random();
List<?> notInList = objectService.getObjectNotIn("BaseWriting");
if (notInList.size() < 1) {
return false;
}
baseWriting = (BaseWriting) notInList.get(random.nextInt(notInList
.size()));
notInList = objectService.getObjectNotIn("BaseListening");
if (notInList.size() < 1) {
return false;
}
baseListening = (BaseListening) notInList.get(random.nextInt(notInList
.size()));
notInList = objectService.getObjectNotIn("BaseWordunderstand");
if (notInList.size() < 1) {
return false;
}
baseWordunderstand = (BaseWordunderstand) notInList.get(random
.nextInt(notInList.size()));
notInList = objectService.getObjectNotIn("BaseLongreading");
if (notInList.size() < 1) {
return false;
}
baseLongreading = (BaseLongreading) notInList.get(random
.nextInt(notInList.size()));
notInList = objectService.getObjectNotIn("BaseCarereading");
if (notInList.size() < 2) {
return false;
}
int ran = random.nextInt(notInList.size());
baseCarereading1 = (BaseCarereading) notInList.get(ran);
notInList.remove(ran);
baseCarereading2 = (BaseCarereading) notInList.get(random
.nextInt(notInList.size()));
notInList = objectService.getObjectNotIn("BaseTranslate");
if (notInList.size() < 1) {
return false;
}
baseTranslate = (BaseTranslate) notInList.get(random.nextInt(notInList
.size()));
return true;
}
/**
* 功能：随机生成一套试卷
*
* @return
*/
public void getRandomTest() {
BaseWriting baseWriting = (BaseWriting) getRandomObject(
BaseWriting.class, "BaseWriting");
setBaseWriting(baseWriting);
genes[0] = baseWriting.getId();
BaseListening baseListening = (BaseListening) getRandomObject(
BaseListening.class, "BaseListening");
setBaseListening(baseListening);
genes[1] = baseListening.getId();
BaseWordunderstand baseWordunderstand = (BaseWordunderstand) getRandomObject(
BaseWordunderstand.class, "BaseWordunderstand");
setBaseWordunderstand(baseWordunderstand);
genes[2] = baseWordunderstand.getId();
BaseLongreading baseLongreading = (BaseLongreading) getRandomObject(
BaseLongreading.class, "BaseLongreading");
setBaseLongreading(baseLongreading);
genes[3] = baseLongreading.getId();
BaseCarereading baseCarereading1 = (BaseCarereading) getRandomObject(
BaseCarereading.class, "BaseCarereading");
setBaseCarereading1(baseCarereading1);
genes[4] = baseCarereading1.getId();
BaseCarereading baseCarereading2;
do {
baseCarereading2 = (BaseCarereading) getRandomObject(
BaseCarereading.class, "BaseCarereading");
} while (baseCarereading2.getId() == baseCarereading1.getId());
setBaseCarereading2(baseCarereading2);
genes[5] = baseCarereading2.getId();
BaseTranslate baseTranslate = (BaseTranslate) getRandomObject(
BaseTranslate.class, "BaseTranslate");
setBaseTranslate(baseTranslate);
genes[6] = baseTranslate.getId();
}
/**
* 功能：随机获取一个题型对象
*
* @param clas
* @param table
* @return
*/
public Object getRandomObject(Class<?> clas, String table) {
ObjectService objectService = Algorithm.objectService;
Random random = new Random();
Object obj = objectService.getObjectById(clas, random
.nextInt(objectService.getMaxID(table)) + 1);
return obj;
}
// Property accessors
public Integer getId() {
return this.id;
}
public void setId(Integer id) {
this.id = id;
}
public BaseLongreading getBaseLongreading() {
return this.baseLongreading;
}
public void setBaseLongreading(BaseLongreading baseLongreading) {
this.baseLongreading = baseLongreading;
}
public BaseTranslate getBaseTranslate() {
return this.baseTranslate;
}
public void setBaseTranslate(BaseTranslate baseTranslate) {
this.baseTranslate = baseTranslate;
}
public BaseListening getBaseListening() {
return this.baseListening;
}
public void setBaseListening(BaseListening baseListening) {
this.baseListening = baseListening;
}
public BaseCarereading getBaseCarereading1() {
return this.baseCarereading1;
}
public void setBaseCarereading1(BaseCarereading baseCarereading1) {
this.baseCarereading1 = baseCarereading1;
}
public BaseWordunderstand getBaseWordunderstand() {
return this.baseWordunderstand;
}
public void setBaseWordunderstand(BaseWordunderstand baseWordunderstand) {
this.baseWordunderstand = baseWordunderstand;
}
public BaseWriting getBaseWriting() {
return this.baseWriting;
}
public void setBaseWriting(BaseWriting baseWriting) {
this.baseWriting = baseWriting;
}
public BaseCarereading getBaseCarereading2() {
return this.baseCarereading2;
}
public void setBaseCarereading2(BaseCarereading baseCarereading2) {
this.baseCarereading2 = baseCarereading2;
}
public String getName() {
return this.name;
}
public void setName(String name) {
this.name = name;
}
public void setIsmeta(int ismeta) {
this.ismeta = ismeta;
}
public int getIsmeta() {
return ismeta;
}
}
种群类 遗传算法种群类，负责存放试卷个体，并且包含相关方法。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
52package com.cet.tool;
import com.cet.pojo.Test;
/**
* 功能：遗传算法种群类
*
* @author alin
*
*/
public class Population {
Test[] Tests;// 个体集合
// 创建一个种群,初始化时initialise=true
public Population(int populationSize, boolean initialise) {
Tests = new Test[populationSize];
// 初始化种群
if (initialise) {
for (int i = 0; i < size(); i++) {
Test newTest = new Test();
newTest.getRandomTest();
saveTest(i, newTest);
}
}
}
public Test getTest(int index) {
return Tests[index];
}
// 获取种群适应度最高的个体
public Test getFittest() {
Test fittest = Tests[0];
for (int i = 0; i < size(); i++) {
if (fittest.getFitness(Algorithm.ep) <= getTest(i).getFitness(
Algorithm.ep)) {
fittest = getTest(i);
}
}
return fittest;
}
// 获取种群大小
public int size() {
return Tests.length;
}
// 保存试卷到种群
public void saveTest(int index, Test indiv) {
Tests[index] = indiv;
}
}
操作类 遗传算法操作类，包含对试卷个体的交叉变异等操作1
2
3
4
5
6
7
8
9
10
11public String GA_Test(){
Test test = new AutoGATest().getGATest(objectService, difficulty,
0.8, 0.1, 5, 80, true);// 遗传算法自动组卷并返回试卷
if (test == null) {// 题型数量已经不够用了，无法生成新的不重复的试卷
message = "<script>alert('Error,题库相关难度的题型不足或者题型数量已经不够用，无法生成新的不重复的试卷');</script>";
return "error";
}
test.setName(examname);//设置试题名称
objectService.save(test);//保存试题
return "success";
}
试题主类 通过传入参数生成试题 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
103package com.cet.tool;
import com.cet.pojo.Test;
import com.cet.service.ObjectService;
/**
* 功能：遗传算法主类
*
* @author alin
*
*/
public class AutoGATest {
/**
* 功能：遗传算法生成试卷主方法
*
* @param objectService
* @param difficulty
* 试卷难度
* @param ep
* 期望难度
* @param uniformRate
* 交叉概率
* @param mutationRate
* 变异概率
* @param tournamentSize
* 淘汰数组大小
* @param popSize
* 种群大小
* @param isCheck
* 每次交叉或变异生成的个体是否需要检查重合，考试时检查，练习时不需检查
* @return
*/
public Test getGATest(ObjectService objectService, float ep,
double uniformRate, double mutationRate, int tournamentSize,
int popSize, boolean isCheck) {
// 设置遗传算法相关参数
Algorithm.ep = ep;// 设置期望难度
Algorithm.uniformRate = uniformRate;// 设置交叉概率
Algorithm.mutationRate = mutationRate;// 设置变异概率
Algorithm.tournamentSize = tournamentSize;// 设置淘汰数组大小
boolean isFirst = true;// 第一次进化，不进行精英主义，因为如果进行，是将初始的种群的精英放入新种群，而不会让它进行任何交叉变异，而有可能它是与数据库某Test重合的
Algorithm.objectService = objectService;
Population myPop = new Population(popSize, true);// 初始化一个种群
// 不断迭代，进行进化操作。 直到找到期望的基因序列,默认都要进化一次，因为这样，进化后的种群个体都是经过交叉变异来的，
// 交叉变异过程中，我进行了重复检查，如果个体和数据库的Test数据重合，则重新赋值一个不重复的。这样避免了
// 未进化种群就找到了最优个体，而该最优个体与数据库Test数据重合的问题
int generationCount = 0;
long begin = System.currentTimeMillis();
int Count = isCheck == true ? 10 : 100;
do {
if (myPop.getFittest().getFitness(Algorithm.ep) < 0.90// 种群中最好的个体适应度都低于0.9，则加大交叉概率
&& Algorithm.uniformRate < 0.97) {
System.out.print(" 加大交叉概率 ");
Algorithm.uniformRate += 0.07;
}
if (myPop.getFittest().getFitness(Algorithm.ep) < 0.90// 种群中最好的个体适应度都低于0.9，则加大变异概率
&& Algorithm.mutationRate < 0.25) {
System.out.println(" 加大变异概率 ");
Algorithm.mutationRate += 0.03;
}
if (myPop.getFittest().getFitness(Algorithm.ep) > 0.90// 种群中最好的个体适应度高于0.9，则减小交叉概率
&& Algorithm.uniformRate > 0.90) {
System.out.print(" 减小交叉概率 ");
Algorithm.uniformRate -= 0.07;
}
if (myPop.getFittest().getFitness(Algorithm.ep) > 0.90// 种群中最好的个体适应度高于0.9，则减小变异概率
&& Algorithm.mutationRate > 0.15) {
System.out.println(" 减小变异概率 ");
Algorithm.mutationRate -= 0.03;
}
myPop = Algorithm.evolvePopulation(myPop, isFirst, isCheck);
if (myPop == null) // 题型数量已经不够用了，无法生成新的不重复的试卷
return null;
isFirst = false;
generationCount++;
System.out.println("第" + generationCount + "次进化， 适应度为: "
+ myPop.getFittest().getFitness(Algorithm.ep) * 100 + "%");
} while (myPop.getFittest().getFitness(Algorithm.ep) < 0.98
&& generationCount <= Count);
System.out.println("用时:" + (System.currentTimeMillis() - begin)
/ 1000.0 + "秒");
if (generationCount > Count) {
System.err.println("题库相关难度的题型不足，无法生成新的试卷\n");
return null;
}
System.out.println("进化完成!");
System.out.println("进化总次数:" + generationCount + "，最终个体适应度:"
+ myPop.getFittest().getFitness(Algorithm.ep) * 100 + "%"
+ "，期望难度:" + ep + ",试卷难度:" + myPop.getFittest().getDifficulty()
+ "\n");
return myPop.getFittest();
}
}
引用类 只放一个Action方法引用1
2
3
4
5
6
7
8
9
10
11public String GA_Test(){
Test test = new AutoGATest().getGATest(objectService, difficulty,
0.8, 0.1, 5, 80, true);// 遗传算法自动组卷并返回试卷
if (test == null) {// 题型数量已经不够用了，无法生成新的不重复的试卷
message = "<script>alert('Error,题库相关难度的题型不足或者题型数量已经不够用，无法生成新的不重复的试卷');</script>";
return "error";
}
test.setName(examname);//设置试题名称
objectService.save(test);//保存试题
return "success";
}
注：大二时写的代码，比较渣，意思到位就行了。
更多文章，请关注：开猿笔记
