關于遺傳算法的詳細原理以及具體的定義這里就不多介紹，想了解的可以自行百度，下面就簡單介紹下自己對遺傳算法的理解，本文對基因的編碼采用二進制規則。
算法思想：
遺傳算法參照達爾文的進化論，認為物種都是向好的方向去發展（適者生存），因此可以認為到足夠的代數之后，得到的最值可實際的最值很接近。
算法步驟：
- 1）隨機產生一個種群；
- 2）計算種群的適應度、最好適應度、最差適應度、平均適應度等指標；
- 3）驗證種群代數是否達到自己設置的閾值，如果達到結束計算，否則繼續下一步計算；
- 4）采用轉盤賭法選擇可以產生下一代的父代，產生下一代種群（種群中個體數量不變）；
- 5）種群發生基因突變；
- 6）重復2、3、4、5步。
算法實現-基因部分
1、種群個體（這里認為是染色體），在個體中，我們為這個個體添加兩個屬性，個體的基因和基因對應的適應度（函數值）。
|
1
2
3
4
|
public class Chromosome { private boolean[] gene;//基因序列 private double score;//對應的函數得分 } |
2、隨機生成基因序列，基因的每一個位置是0還是1，這里采用完全隨機的方式實現。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public Chromosome(int size) { if (size <= 0) { return; } initGeneSize(size); for (int i = 0; i < size; i++) { gene[i] = Math.random() >= 0.5; } } private void initGeneSize(int size) { if (size <= 0) { return; } gene = new boolean[size]; } |
3、把基因轉化為對應的值，比如101對應的數字是5，這里采用位運算來實現。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public int getNum() { if (gene == null) { return 0; } int num = 0; for (boolean bool : gene) { num <<= 1; if (bool) { num += 1; } } return num; } |
4、基因發生變異，對于變異的位置這里完全采取隨機的方式實現，變異原則是由1變為0，0變為1。
|
1
2
3
4
5
6
7
8
9
10
11
|
public void mutation(int num) { //允許變異 int size = gene.length; for (int i = 0; i < num; i++) { //尋找變異位置 int at = ((int) (Math.random() * size)) % size; //變異后的值 boolean bool = !gene[at]; gene[at] = bool; } } |
5、克隆基因，用于產生下一代，這一步就是將已存在的基因copy一份。
|
1
2
3
4
5
6
7
8
9
10
11
|
public static Chromosome clone(final Chromosome c) { if (c == null || c.gene == null) { return null; } Chromosome copy = new Chromosome(); copy.initGeneSize(c.gene.length); for (int i = 0; i < c.gene.length; i++) { copy.gene[i] = c.gene[i]; } return copy; } |
6、父母雙方產生下一代，這里兩個個體產生兩個個體子代，具體哪段基因差生交叉，完全隨機。
|
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
|
public static List<Chromosome> genetic(Chromosome p1, Chromosome p2) { if (p1 == null || p2 == null) { //染色體有一個為空，不產生下一代 return null; } if (p1.gene == null || p2.gene == null) { //染色體有一個沒有基因序列，不產生下一代 return null; } if (p1.gene.length != p2.gene.length) { //染色體基因序列長度不同，不產生下一代 return null; } Chromosome c1 = clone(p1); Chromosome c2 = clone(p2); //隨機產生交叉互換位置 int size = c1.gene.length; int a = ((int) (Math.random() * size)) % size; int b = ((int) (Math.random() * size)) % size; int min = a > b ? b : a; int max = a > b ? a : b; //對位置上的基因進行交叉互換 for (int i = min; i <= max; i++) { boolean t = c1.gene[i]; c1.gene[i] = c2.gene[i]; c2.gene[i] = t; } List<Chromosome> list = new ArrayList<Chromosome>(); list.add(c1); list.add(c2); return list; } |
算法實現-遺傳算法
1、對于遺傳算法，我們需要有對應的種群以及我們需要設置的一些常量：種群數量、基因長度、基因突變個數、基因突變率等，具體參照如下代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public abstract class GeneticAlgorithm { private List<Chromosome> population = new ArrayList<Chromosome>();//種群 private int popSize = 100;//種群數量 private int geneSize;//基因最大長度 private int maxIterNum = 500;//最大迭代次數 private double mutationRate = 0.01;//基因變異的概率 private int maxMutationNum = 3;//最大變異步長 private int generation = 1;//當前遺傳到第幾代 private double bestScore;//最好得分 private double worstScore;//最壞得分 private double totalScore;//總得分 private double averageScore;//平均得分 private double x; //記錄歷史種群中最好的X值 private double y; //記錄歷史種群中最好的Y值 private int geneI;//x y所在代數 } |
2、初始化種群，在遺傳算法開始時，我們需要初始化一個原始種群，這就是原始的第一代。
|
1
2
3
4
5
6
7
8
|
private void init() { for (int i = 0; i < popSize; i++) { population = new ArrayList<Chromosome>(); Chromosome chro = new Chromosome(geneSize); population.add(chro); } caculteScore(); } |
3、在初始種群存在后，我們需要計算種群的適應度以及最好適應度、最壞適應度和平均適應度等。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
private void caculteScore() { setChromosomeScore(population.get(0)); bestScore = population.get(0).getScore(); worstScore = population.get(0).getScore(); totalScore = 0; for (Chromosome chro : population) { setChromosomeScore(chro); if (chro.getScore() > bestScore) { //設置最好基因值 bestScore = chro.getScore(); if (y < bestScore) { x = changeX(chro); y = bestScore; geneI = generation; } } if (chro.getScore() < worstScore) { //設置最壞基因值 worstScore = chro.getScore(); } totalScore += chro.getScore(); } averageScore = totalScore / popSize; //因為精度問題導致的平均值大于最好值，將平均值設置成最好值 averageScore = averageScore > bestScore ? bestScore : averageScore; } |
4、在計算個體適應度的時候，我們需要根據基因計算對應的Y值，這里我們設置兩個抽象方法，具體實現由類的實現去實現。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
private void setChromosomeScore(Chromosome chro) { if (chro == null) { return; } double x = changeX(chro); double y = caculateY(x); chro.setScore(y); } /** * @param chro * @return * @Description: 將二進制轉化為對應的X */public abstract double changeX(Chromosome chro); /** * @param x * @return * @Description: 根據X計算Y值 Y=F(X) */public abstract double caculateY(double x); |
5、在計算完種群適應度之后，我們需要使用轉盤賭法選取可以產生下一代的個體，這里有個條件就是只有個人的適應度不小于平均適應度才會長生下一代（適者生存）。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
private Chromosome getParentChromosome (){ double slice = Math.random() * totalScore; double sum = 0; for (Chromosome chro : population) { sum += chro.getScore(); //轉到對應的位置并且適應度不小于平均適應度 if (sum > slice && chro.getScore() >= averageScore) { return chro; } } return null; } |
6、選擇可以產生下一代的個體之后，就要交配產生下一代。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
private void evolve() { List<Chromosome> childPopulation = new ArrayList<Chromosome>(); //生成下一代種群 while (childPopulation.size() < popSize) { Chromosome p1 = getParentChromosome(); Chromosome p2 = getParentChromosome(); List<Chromosome> children = Chromosome.genetic(p1, p2); if (children != null) { for (Chromosome chro : children) { childPopulation.add(chro); } } } //新種群替換舊種群 List<Chromosome> t = population; population = childPopulation; t.clear(); t = null; //基因突變 mutation(); //計算新種群的適應度 caculteScore(); } |
7、在產生下一代的過程中，可能會發生基因變異。
|
1
2
3
4
5
6
7
8
|
private void mutation() { for (Chromosome chro : population) { if (Math.random() < mutationRate) { //發生基因突變 int mutationNum = (int) (Math.random() * maxMutationNum); chro.mutation(mutationNum); } } } |
8、將上述步驟一代一代的重復執行。
|
1
2
3
4
5
6
7
8
9
10
11
|
public void caculte() { //初始化種群 generation = 1; init(); while (generation < maxIterNum) { //種群遺傳 evolve(); print(); generation++; } } |
編寫實現類
由于上述遺傳算法的類是一個抽象類，因此我們需要針對特定的事例編寫實現類，假設我們計算 Y=100-log(X)在[6,106]上的最值。
1、我們假設基因的長度為24（基因的長度由要求結果的有效長度確定），因此對應的二進制最大值為 1<< 24，我們做如下設置
|
1
2
3
4
5
6
7
8
|
public class GeneticAlgorithmTest extends GeneticAlgorithm{ public static final int NUM = 1 << 24; public GeneticAlgorithmTest() { super(24); } } |
2、對X值的抽象方法進行實現
|
1
2
3
4
5
|
@Overridepublic double changeX(Chromosome chro) { // TODO Auto-generated method stub return ((1.0 * chro.getNum() / NUM) * 100) + 6; } |
3、對Y的抽象方法進行實現
|
1
2
3
4
5
|
@Overridepublic double caculateY(double x) { // TODO Auto-generated method stub return 100 - Math.log(x); } |
運行結果
遺傳算法思考
自己看了很多遺傳算法的介紹，上面提到的最優解都是最后一代的最值，自己就有一個疑問了，為什么我知道前面所有帶中的最值，也就是程序中的X Y值，為什么不能用X Y值做遺傳算法最后的結果值呢？
完整代碼
1、Chromosome類
|
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
|
/** *@Description: 基因遺傳染色體 */package com.lulei.genetic.algorithm; import java.util.ArrayList; import java.util.List; public class Chromosome { private boolean[] gene;//基因序列 private double score;//對應的函數得分 public double getScore() { return score; } public void setScore(double score) { this.score = score; } /** * @param size * 隨機生成基因序列 */ public Chromosome(int size) { if (size <= 0) { return; } initGeneSize(size); for (int i = 0; i < size; i++) { gene[i] = Math.random() >= 0.5; } } /** * 生成一個新基因 */ public Chromosome() { } /** * @param c * @return * @Description: 克隆基因 */ public static Chromosome clone(final Chromosome c) { if (c == null || c.gene == null) { return null; } Chromosome copy = new Chromosome(); copy.initGeneSize(c.gene.length); for (int i = 0; i < c.gene.length; i++) { copy.gene[i] = c.gene[i]; } return copy; } /** * @param size * @Description: 初始化基因長度 */ private void initGeneSize(int size) { if (size <= 0) { return; } gene = new boolean[size]; } /** * @param c1 * @param c2 * @Description: 遺傳產生下一代 */ public static List<Chromosome> genetic(Chromosome p1, Chromosome p2) { if (p1 == null || p2 == null) { //染色體有一個為空，不產生下一代 return null; } if (p1.gene == null || p2.gene == null) { //染色體有一個沒有基因序列，不產生下一代 return null; } if (p1.gene.length != p2.gene.length) { //染色體基因序列長度不同，不產生下一代 return null; } Chromosome c1 = clone(p1); Chromosome c2 = clone(p2); //隨機產生交叉互換位置 int size = c1.gene.length; int a = ((int) (Math.random() * size)) % size; int b = ((int) (Math.random() * size)) % size; int min = a > b ? b : a; int max = a > b ? a : b; //對位置上的基因進行交叉互換 for (int i = min; i <= max; i++) { boolean t = c1.gene[i]; c1.gene[i] = c2.gene[i]; c2.gene[i] = t; } List<Chromosome> list = new ArrayList<Chromosome>(); list.add(c1); list.add(c2); return list; } /** * @param num * @Description: 基因num個位置發生變異 */ public void mutation(int num) { //允許變異 int size = gene.length; for (int i = 0; i < num; i++) { //尋找變異位置 int at = ((int) (Math.random() * size)) % size; //變異后的值 boolean bool = !gene[at]; gene[at] = bool; } } /** * @return * @Description: 將基因轉化為對應的數字 */ public int getNum() { if (gene == null) { return 0; } int num = 0; for (boolean bool : gene) { num <<= 1; if (bool) { num += 1; } } return num; } } |
2、GeneticAlgorithm類
|
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
|
/** *@Description: */package com.lulei.genetic.algorithm; import java.util.ArrayList; import java.util.List; public abstract class GeneticAlgorithm { private List<Chromosome> population = new ArrayList<Chromosome>(); private int popSize = 100;//種群數量 private int geneSize;//基因最大長度 private int maxIterNum = 500;//最大迭代次數 private double mutationRate = 0.01;//基因變異的概率 private int maxMutationNum = 3;//最大變異步長 private int generation = 1;//當前遺傳到第幾代 private double bestScore;//最好得分 private double worstScore;//最壞得分 private double totalScore;//總得分 private double averageScore;//平均得分 private double x; //記錄歷史種群中最好的X值 private double y; //記錄歷史種群中最好的Y值 private int geneI;//x y所在代數 public GeneticAlgorithm(int geneSize) { this.geneSize = geneSize; } public void caculte() { //初始化種群 generation = 1; init(); while (generation < maxIterNum) { //種群遺傳 evolve(); print(); generation++; } } /** * @Description: 輸出結果 */ private void print() { System.out.println("--------------------------------"); System.out.println("the generation is:" + generation); System.out.println("the best y is:" + bestScore); System.out.println("the worst fitness is:" + worstScore); System.out.println("the average fitness is:" + averageScore); System.out.println("the total fitness is:" + totalScore); System.out.println("geneI:" + geneI + "\tx:" + x + "\ty:" + y); } /** * @Description: 初始化種群 */ private void init() { for (int i = 0; i < popSize; i++) { population = new ArrayList<Chromosome>(); Chromosome chro = new Chromosome(geneSize); population.add(chro); } caculteScore(); } /** * @Author:lulei * @Description:種群進行遺傳 */ private void evolve() { List<Chromosome> childPopulation = new ArrayList<Chromosome>(); //生成下一代種群 while (childPopulation.size() < popSize) { Chromosome p1 = getParentChromosome(); Chromosome p2 = getParentChromosome(); List<Chromosome> children = Chromosome.genetic(p1, p2); if (children != null) { for (Chromosome chro : children) { childPopulation.add(chro); } } } //新種群替換舊種群 List<Chromosome> t = population; population = childPopulation; t.clear(); t = null; //基因突變 mutation(); //計算新種群的適應度 caculteScore(); } /** * @return * @Description: 輪盤賭法選擇可以遺傳下一代的染色體 */ private Chromosome getParentChromosome (){ double slice = Math.random() * totalScore; double sum = 0; for (Chromosome chro : population) { sum += chro.getScore(); if (sum > slice && chro.getScore() >= averageScore) { return chro; } } return null; } /** * @Description: 計算種群適應度 */ private void caculteScore() { setChromosomeScore(population.get(0)); bestScore = population.get(0).getScore(); worstScore = population.get(0).getScore(); totalScore = 0; for (Chromosome chro : population) { setChromosomeScore(chro); if (chro.getScore() > bestScore) { //設置最好基因值 bestScore = chro.getScore(); if (y < bestScore) { x = changeX(chro); y = bestScore; geneI = generation; } } if (chro.getScore() < worstScore) { //設置最壞基因值 worstScore = chro.getScore(); } totalScore += chro.getScore(); } averageScore = totalScore / popSize; //因為精度問題導致的平均值大于最好值，將平均值設置成最好值 averageScore = averageScore > bestScore ? bestScore : averageScore; } /** * 基因突變 */ private void mutation() { for (Chromosome chro : population) { if (Math.random() < mutationRate) { //發生基因突變 int mutationNum = (int) (Math.random() * maxMutationNum); chro.mutation(mutationNum); } } } /** * @param chro * @Description: 設置染色體得分 */ private void setChromosomeScore(Chromosome chro) { if (chro == null) { return; } double x = changeX(chro); double y = caculateY(x); chro.setScore(y); } /** * @param chro * @return * @Description: 將二進制轉化為對應的X */ public abstract double changeX(Chromosome chro); /** * @param x * @return * @Description: 根據X計算Y值 Y=F(X) */ public abstract double caculateY(double x); public void setPopulation(List<Chromosome> population) { this.population = population; } public void setPopSize(int popSize) { this.popSize = popSize; } public void setGeneSize(int geneSize) { this.geneSize = geneSize; } public void setMaxIterNum(int maxIterNum) { this.maxIterNum = maxIterNum; } public void setMutationRate(double mutationRate) { this.mutationRate = mutationRate; } public void setMaxMutationNum(int maxMutationNum) { this.maxMutationNum = maxMutationNum; } public double getBestScore() { return bestScore; } public double getWorstScore() { return worstScore; } public double getTotalScore() { return totalScore; } public double getAverageScore() { return averageScore; } public double getX() { return x; } public double getY() { return y; } } |
3、GeneticAlgorithmTest類
|
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
|
/** *@Description: */package com.lulei.genetic.algorithm; public class GeneticAlgorithmTest extends GeneticAlgorithm{ public static final int NUM = 1 << 24; public GeneticAlgorithmTest() { super(24); } @Override public double changeX(Chromosome chro) { // TODO Auto-generated method stub return ((1.0 * chro.getNum() / NUM) * 100) + 6; } @Override public double caculateY(double x) { // TODO Auto-generated method stub return 100 - Math.log(x); } public static void main(String[] args) { GeneticAlgorithmTest test = new GeneticAlgorithmTest(); test.caculte(); } } |
以上就是關于Java遺傳算法的詳細介紹，希望對大家學習Java遺傳算法有所幫助。
