Skip to content

Commit 9a241ab

Browse files
author
linyiqun
committed
GA遗传算法的实现
GA遗传算法的实现
1 parent a06548e commit 9a241ab

File tree

2 files changed

+376
-0
lines changed

2 files changed

+376
-0
lines changed

‎Others/DataMining_GA/Client.java

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package GA;
2+
3+
/**
4+
* Genetic遗传算法测试类
5+
* @author lyq
6+
*
7+
*/
8+
public class Client {
9+
public static void main(String[] args){
10+
//变量最小值和最大值
11+
int minNum = 1;
12+
int maxNum = 7;
13+
//初始群体规模
14+
int initSetsNum = 4;
15+
16+
GATool tool = new GATool(minNum, maxNum, initSetsNum);
17+
tool.geneticCal();
18+
}
19+
}

‎Others/DataMining_GA/GATool.java

Lines changed: 357 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,357 @@
1+
package GA;
2+
3+
import java.util.ArrayList;
4+
import java.util.Random;
5+
6+
/**
7+
* 遗传算法工具类
8+
*
9+
* @author lyq
10+
*
11+
*/
12+
public class GATool {
13+
// 变量最小值
14+
private int minNum;
15+
// 变量最大值
16+
private int maxNum;
17+
// 单个变量的编码位数
18+
private int codeNum;
19+
// 初始种群的数量
20+
private int initSetsNum;
21+
// 随机数生成器
22+
private Random random;
23+
// 初始群体
24+
private ArrayList<int[]> initSets;
25+
26+
public GATool(int minNum, int maxNum, int initSetsNum) {
27+
this.minNum = minNum;
28+
this.maxNum = maxNum;
29+
this.initSetsNum = initSetsNum;
30+
31+
this.random = new Random();
32+
produceInitSets();
33+
}
34+
35+
/**
36+
* 产生初始化群体
37+
*/
38+
private void produceInitSets() {
39+
this.codeNum = 0;
40+
int num = maxNum;
41+
int[] array;
42+
43+
initSets = new ArrayList<>();
44+
45+
// 确定编码位数
46+
while (num != 0) {
47+
codeNum++;
48+
num /= 2;
49+
}
50+
51+
for (int i = 0; i < initSetsNum; i++) {
52+
array = produceInitCode();
53+
initSets.add(array);
54+
}
55+
}
56+
57+
/**
58+
* 产生初始个体的编码
59+
*
60+
* @return
61+
*/
62+
private int[] produceInitCode() {
63+
int num = 0;
64+
int num2 = 0;
65+
int[] tempArray;
66+
int[] array1;
67+
int[] array2;
68+
69+
tempArray = new int[2 * codeNum];
70+
array1 = new int[codeNum];
71+
array2 = new int[codeNum];
72+
73+
num = 0;
74+
while (num < minNum || num > maxNum) {
75+
num = random.nextInt(maxNum) + 1;
76+
}
77+
numToBinaryArray(array1, num);
78+
79+
while (num2 < minNum || num2 > maxNum) {
80+
num2 = random.nextInt(maxNum) + 1;
81+
}
82+
numToBinaryArray(array2, num2);
83+
84+
// 组成总的编码
85+
for (int i = 0, k = 0; i < tempArray.length; i++, k++) {
86+
if (k < codeNum) {
87+
tempArray[i] = array1[k];
88+
} else {
89+
tempArray[i] = array2[k - codeNum];
90+
}
91+
}
92+
93+
return tempArray;
94+
}
95+
96+
/**
97+
* 选择操作，把适值较高的个体优先遗传到下一代
98+
*
99+
* @param initCodes
100+
* 初始个体编码
101+
* @return
102+
*/
103+
private ArrayList<int[]> selectOperate(ArrayList<int[]> initCodes) {
104+
double randomNum = 0;
105+
double sumAdaptiveValue = 0;
106+
ArrayList<int[]> resultCodes = new ArrayList<>();
107+
double[] adaptiveValue = new double[initSetsNum];
108+
109+
for (int i = 0; i < initSetsNum; i++) {
110+
adaptiveValue[i] = calCodeAdaptiveValue(initCodes.get(i));
111+
sumAdaptiveValue += adaptiveValue[i];
112+
}
113+
114+
// 转成概率的形式，做归一化操作
115+
for (int i = 0; i < initSetsNum; i++) {
116+
adaptiveValue[i] = adaptiveValue[i] / sumAdaptiveValue;
117+
}
118+
119+
for (int i = 0; i < initSetsNum; i++) {
120+
randomNum = random.nextInt(100) + 1;
121+
randomNum = randomNum / 100;
122+
123+
sumAdaptiveValue = 0;
124+
// 确定区间
125+
for (int j = 0; j < initSetsNum; j++) {
126+
if (randomNum > sumAdaptiveValue
127+
&& randomNum <= sumAdaptiveValue + adaptiveValue[j]) {
128+
//采用拷贝的方式避免引用重复
129+
resultCodes.add(initCodes.get(j).clone());
130+
break;
131+
} else {
132+
sumAdaptiveValue += adaptiveValue[j];
133+
}
134+
}
135+
}
136+
137+
return resultCodes;
138+
}
139+
140+
/**
141+
* 交叉运算
142+
*
143+
* @param selectedCodes
144+
* 上步骤的选择后的编码
145+
* @return
146+
*/
147+
private ArrayList<int[]> crossOperate(ArrayList<int[]> selectedCodes) {
148+
int randomNum = 0;
149+
// 交叉点
150+
int crossPoint = 0;
151+
ArrayList<int[]> resultCodes = new ArrayList<>();
152+
// 随机编码队列，进行随机交叉配对
153+
ArrayList<int[]> randomCodeSeqs = new ArrayList<>();
154+
155+
// 进行随机排序
156+
while (selectedCodes.size() > 0) {
157+
randomNum = random.nextInt(selectedCodes.size());
158+
159+
randomCodeSeqs.add(selectedCodes.get(randomNum));
160+
selectedCodes.remove(randomNum);
161+
}
162+
163+
int temp = 0;
164+
int[] array1;
165+
int[] array2;
166+
// 进行两两交叉运算
167+
for (int i = 1; i < randomCodeSeqs.size(); i++) {
168+
if (i % 2 == 1) {
169+
array1 = randomCodeSeqs.get(i - 1);
170+
array2 = randomCodeSeqs.get(i);
171+
crossPoint = random.nextInt(2 * codeNum - 1) + 1;
172+
173+
// 进行交叉点位置后的编码调换
174+
for (int j = 0; j < 2 * codeNum; j++) {
175+
if (j >= crossPoint) {
176+
temp = array1[j];
177+
array1[j] = array2[j];
178+
array2[j] = temp;
179+
}
180+
}
181+
182+
// 加入到交叉运算结果中
183+
resultCodes.add(array1);
184+
resultCodes.add(array2);
185+
}
186+
}
187+
188+
return resultCodes;
189+
}
190+
191+
/**
192+
* 变异操作
193+
*
194+
* @param crossCodes
195+
* 交叉运算后的结果
196+
* @return
197+
*/
198+
private ArrayList<int[]> variationOperate(ArrayList<int[]> crossCodes) {
199+
// 变异点
200+
int variationPoint = 0;
201+
ArrayList<int[]> resultCodes = new ArrayList<>();
202+
203+
for (int[] array : crossCodes) {
204+
variationPoint = random.nextInt(codeNum * 2);
205+
206+
for (int i = 0; i < array.length; i++) {
207+
// 变异点进行变异
208+
if (i == variationPoint) {
209+
array[i] = (array[i] == 0 ? 1 : 0);
210+
break;
211+
}
212+
}
213+
214+
resultCodes.add(array);
215+
}
216+
217+
return resultCodes;
218+
}
219+
220+
/**
221+
* 数字转为二进制形式
222+
*
223+
* @param binaryArray
224+
* 转化后的二进制数组形式
225+
* @param num
226+
* 待转化数字
227+
*/
228+
private void numToBinaryArray(int[] binaryArray, int num) {
229+
int index = 0;
230+
int temp = 0;
231+
while (num != 0) {
232+
binaryArray[index] = num % 2;
233+
index++;
234+
num /= 2;
235+
}
236+
237+
//进行数组前和尾部的调换
238+
for(int i=0; i<binaryArray.length/2; i++){
239+
temp = binaryArray[i];
240+
binaryArray[i] = binaryArray[binaryArray.length - 1 - i];
241+
binaryArray[binaryArray.length - 1 - i] = temp;
242+
}
243+
}
244+
245+
/**
246+
* 二进制数组转化为数字
247+
*
248+
* @param binaryArray
249+
* 待转化二进制数组
250+
*/
251+
private int binaryArrayToNum(int[] binaryArray) {
252+
int result = 0;
253+
254+
for (int i = binaryArray.length-1, k=0; i >=0 ; i--, k++) {
255+
if (binaryArray[i] == 1) {
256+
result += Math.pow(2, k);
257+
}
258+
}
259+
260+
return result;
261+
}
262+
263+
/**
264+
* 计算个体编码的适值
265+
*
266+
* @param codeArray
267+
*/
268+
private int calCodeAdaptiveValue(int[] codeArray) {
269+
int result = 0;
270+
int x1 = 0;
271+
int x2 = 0;
272+
int[] array1 = new int[codeNum];
273+
int[] array2 = new int[codeNum];
274+
275+
for (int i = 0, k = 0; i < codeArray.length; i++, k++) {
276+
if (k < codeNum) {
277+
array1[k] = codeArray[i];
278+
} else {
279+
array2[k - codeNum] = codeArray[i];
280+
}
281+
}
282+
283+
// 进行适值的叠加
284+
x1 = binaryArrayToNum(array1);
285+
x2 = binaryArrayToNum(array2);
286+
result = x1 * x1 + x2 * x2;
287+
288+
return result;
289+
}
290+
291+
/**
292+
* 进行遗传算法计算
293+
*/
294+
public void geneticCal() {
295+
// 最大适值
296+
int maxFitness;
297+
//迭代遗传次数
298+
int loopCount = 0;
299+
boolean canExit = false;
300+
ArrayList<int[]> initCodes;
301+
ArrayList<int[]> selectedCodes;
302+
ArrayList<int[]> crossedCodes;
303+
ArrayList<int[]> variationCodes;
304+
305+
int[] maxCode = new int[2*codeNum];
306+
//计算最大适值
307+
for(int i=0; i<2*codeNum; i++){
308+
maxCode[i] = 1;
309+
}
310+
maxFitness = calCodeAdaptiveValue(maxCode);
311+
312+
initCodes = initSets;
313+
while (true) {
314+
for (int[] array : initCodes) {
315+
// 遗传迭代的终止条件为存在编码达到最大适值
316+
if (maxFitness == calCodeAdaptiveValue(array)) {
317+
canExit = true;
318+
break;
319+
}
320+
}
321+
322+
if (canExit) {
323+
break;
324+
}
325+
326+
selectedCodes = selectOperate(initCodes);
327+
crossedCodes = crossOperate(selectedCodes);
328+
variationCodes = variationOperate(crossedCodes);
329+
initCodes = variationCodes;
330+
331+
loopCount++;
332+
}
333+
334+
System.out.println("总共遗传进化了" + loopCount +"次" );
335+
printFinalCodes(initCodes);
336+
}
337+
338+
/**
339+
* 输出最后的编码集
340+
*
341+
* @param finalCodes
342+
* 最后的结果编码
343+
*/
344+
private void printFinalCodes(ArrayList<int[]> finalCodes) {
345+
int j = 0;
346+
347+
for (int[] array : finalCodes) {
348+
System.out.print("个体" + (j + 1) + ":");
349+
for (int i = 0; i < array.length; i++) {
350+
System.out.print(array[i]);
351+
}
352+
System.out.println();
353+
j++;
354+
}
355+
}
356+
357+
}

0 commit comments

Comments
 (0)