遗传算法（GA）

Posted on

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

设置种群参数

1
2
3
4
5
6
7
private int ChrNum = 10; // 染色体数量
private String[] ipop = new String[ChrNum]; // 一个种群中染色体总数
private int generation = 0; // 染色体代号
public static final int GENE = 46; // 基因数
private double bestfitness = Double.MAX_VALUE; // 函数最优解
private int bestgenerations; // 所有子代与父代中最好的染色体
private String beststr; // 最优解的染色体的二进制码

初始化种群中的每一个染色体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private String initChr() {
  String res = "";
  for (int i = 0; i < GENE; i++) {
    if (Math.random() > 0.5) {
      res += "0";
    } else {
      res += "1";
    }
  }
  return res;
}
private String[] initPop() {
		String[] ipop = new String[ChrNum];
		for (int i = 0; i < ChrNum; i++) {
			ipop[i] = initChr();
		}
		return ipop;
	}

基因编码

染色体的基因编码与变量的值转换,以目标函数fitness作为每个染色体的适应度值

1
2
3
4
5
6
7
8
9
10
11
private double[] calculatefitnessvalue(String str) {
  // 二进制数前23位为x的二进制字符串，后23位为y的二进制字符串
  int a = Integer.parseInt(str.substring(0, 23), 2);
  int b = Integer.parseInt(str.substring(23, 46), 2);
  double x = a * (6.0 - 0.0) / (Math.pow(2, 23) - 1); // x的基因
  double y = b * (6.0 - 0.0) / (Math.pow(2, 23) - 1); // y的基因
  double fitness = 3 - Math.sin(2 * x) * Math.sin(2 * x) - Math.sin(2 * y) * Math.sin(2 * y);
  double[] returns = { x, y, fitness };
  return returns;

}

选择

计算群体上每个个体的适应度值，按由个体适应度值所决定的某个规则选择将进入下一代的个体,同时记录下该种群中的最优解

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
private void select() {
  double evals[] = new double[ChrNum]; // 所有染色体适应值
  double p[] = new double[ChrNum]; // 各染色体选择概率
  double q[] = new double[ChrNum]; // 累计概率
  double F = 0; // 累计适应值总和
  for (int i = 0; i < ChrNum; i++) {
    evals[i] = calculatefitnessvalue(ipop[i])[2];
    if (evals[i] < bestfitness) {
      bestfitness = evals[i];
      bestgenerations = generation;
      beststr = ipop[i];
    }

    F = F + evals[i]; // 所有染色体适应值总和
  }

  for (int i = 0; i < ChrNum; i++) {
    p[i] = evals[i] / F;
    if (i == 0)
      q[i] = p[i];
    else {
      q[i] = q[i - 1] + p[i];
    }
  }
  for (int i = 0; i < ChrNum; i++) {
    double r = Math.random();
    if (r <= q[0]) {
      ipop[i] = ipop[0];
    } else {
      for (int j = 1; j < ChrNum; j++) {
        if (r < q[j]) {
          ipop[i] = ipop[j];
        }
      }
    }
  }
}

交叉

交叉率为60%，平均为60%的染色体进行交叉

1
2
3
4
5
6
7
8
9
10
11
12
private void cross() {
  String temp1, temp2;
  for (int i = 0; i < ChrNum; i++) {
    if (Math.random() < 0.60) {
      int pos = (int) (Math.random() * GENE) + 1;
      temp1 = ipop[i].substring(0, pos) + ipop[(i + 1) % ChrNum].substring(pos);
      temp2 = ipop[(i + 1) % ChrNum].substring(0, pos) + ipop[i].substring(pos);
      ipop[i] = temp1;
      ipop[(i + 1) / ChrNum] = temp2;
    }
  }
}

变异

基因突变具有不定向性，不能保证解的绝对优化，但可以防止陷入局部最优解，这里选取1%的基因进行变异操作

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
private void mutation() {
  for (int i = 0; i < 4; i++) {
    int num = (int) (Math.random() * GENE * ChrNum + 1);
    int chromosomeNum = (int) (num / GENE) + 1; // 染色体号

    int mutationNum = num - (chromosomeNum - 1) * GENE; // 基因号
    if (mutationNum == 0)
      mutationNum = 1;
    chromosomeNum = chromosomeNum - 1;
    if (chromosomeNum >= ChrNum)
      chromosomeNum = 9;
    String temp;
    String a; // 记录变异位点变异后的编码
    if (ipop[chromosomeNum].charAt(mutationNum - 1) == '0') { // 当变异位点为0时
      a = "1";
    } else {
      a = "0";
    }
    // 当变异位点在首、中段和尾时的突变情况
    if (mutationNum == 1) {
      temp = a + ipop[chromosomeNum].substring(mutationNum);
    } else {
      if (mutationNum != GENE) {
        temp = ipop[chromosomeNum].substring(0, mutationNum - 1) + a
            + ipop[chromosomeNum].substring(mutationNum);
      } else {
        temp = ipop[chromosomeNum].substring(0, mutationNum - 1) + a;
      }
    }
    // 记录下变异后的染色体
    ipop[chromosomeNum] = temp;
  }
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String args[]) {
  GA Tryer = new GA();
  Tryer.ipop = Tryer.initPop(); // 产生初始种群
  String str = "";
  // 迭代次数
  for (int i = 0; i < 100000; i++) {
    Tryer.select();
    Tryer.cross();
    Tryer.mutation();
    Tryer.generation = i;
  }
  double[] x = Tryer.calculatefitnessvalue(Tryer.beststr);
  str = "最小值" + Tryer.bestfitness + '\n' + "第" + Tryer.bestgenerations + "个染色体:<" + Tryer.beststr + ">" + '\n'
      + "x=" + x[0] + '\n' + "y=" + x[1];
  System.out.println(str);
}

运行结果

1
2
3
4
最小值1.0000297643275602
第88578个染色体:<0010000101100111011001110100111100000010010010>
x=0.7829040030126575
y=3.925886145339745