基于Java实现的遗传进化算法说明与使用

目录
一、 概述： 2
二、 编码方式 2
三、 选择操作 4

1. 轮盘赌选择法 4
2. 随机遍历抽样法 4
3. 锦标赛选择法 4
   四、 交叉操作 5
4. 部分匹配法（Partially Matching Crossover，PMX） 5
5. 循环交叉法（Cycle Crossover，CX） 5
6. 次序交叉法1（Order Crossover，OX1） 6
7. 次序交叉法2（Order Crossover，OX2） 6
8. 基于位置的交叉法（Position Based Crossover，POS） 7
9. 交替位置交叉法（Alternating Position Crossover，APX） 7
   五、 变异操作 8
10. 替换变异（Displacement Mutation，DM） 8
11. 交换变异（Exchange Mutation，EM） 8
12. 插入变异（Insertion Mutation，IM） 8
13. 简单倒位变异（Simple Inversion Mutation，SIM） 8
14. 倒位变异（Inversion Mutation，IVM） 9
15. 争夺变异（Scramble Mutation，SM） 9
    六、 进化算法pdf内容 10
    3.2 遗传算法 10
    3.3 遗传规划 11
    3.4 进化策略 13
    3.5 差异进化 14
    3.6 进化规划 15
    3.7 语法进化 16
    3.8 基因表达规划 17
    3.9 学习分类系统 18
    3.10 非支配排序遗传算法 20
    3.11 强帕累托进化算法 20
    七、 问题代码实现 22
    2.1 TSP问题求解 22
    2.2 多元单目标函数问题求解 22
    2.3 多元多目标函数问题求解 22
    2.4 虚拟网络映射问题求解 23
    一、概述：
    遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
    其他详细的介绍与资料，可以到网上搜索，这里不再作进一步的介绍。概括地讲，遗传算法主要解决四个方面的问题，即编码操作，选择操作，交叉操作以及变异操作。以下几个章节简单介绍一下遗传算子操作。
    二、编码方式
    TSP问题编码一般有五种不同的方式：
    基于二进制的编码。比较传统的编码方式，但是这种方式的编码，在经过遗传操作以后很难保证后代还是一个可行解，还需要另外的修正操作；
    基于矩阵的编码。比较复杂，并且需要占用大量的内存，应用的不是很广泛；
    基于邻接的编码。同上；
    基于索引的编码。同上；
    基于路径的编码。 目前最普遍用的编码方式。因为它最直观最容易理解，操作起来也比较方便。
    显然，对于二进制编码来说，其遗传操作是比较容易实现，这里不再详细解释。以下将主要介绍基于路径的编码方式以及相关的遗传操作，作为今后的资料索引。
    本文转载自：http://www.biyezuopin.vip/onews.asp?id=16534

package functionExtremum;public class GA {private int ChrNum = 50; // 染色体数量public static final int GENE = 46; // 基因数（染色体长度）private String[] ipop = new String[ChrNum]; // 一个种群中染色体总数private int generation = 0; // 染色体代号private double crossover = 0.90;  // 交叉概率最优解private double mutation = 0.01;  // 变异概率最优解private double bestfitness = Double.MAX_VALUE; // 函数最优解private int bestgenerations; // 所有子代与父代中最好的染色体private String beststr; // 最优解的染色体的二进制码// 初始化一条染色体（用二进制字符串表示）private String initChr() {String res = "";for (int i = 0; i < GENE; i++) {if (Math.random() > 0.5) {res += "0";} else {res += "1";}}return res;}// 初始化一个种群(10条染色体)private String[] initPop() {String[] ipop = new String[ChrNum];for (int i = 0; i < ChrNum; i++) {ipop[i] = initChr();}return ipop;}// 将染色体转换成x,y变量的值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) / (Math.pow(2, 23) - 1); // x的基因double y = b * (6.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;}// 轮盘选择 计算群体上每个个体的适应度值; 按由个体适应度值所决定的某个规则选择将进入下一代的个体;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] = (F - (ChrNum - 1) * evals[i]) / F;if (i == 0)q[i] = p[i];else {q[i] = q[i - 1] + p[i];}}String[] ipopnew = new String[ChrNum];for (int i = 0; i < ChrNum; i++) {double r = Math.random();for (int j = 0; j < ChrNum; j++) {if (r < q[j]) {ipopnew[i] = ipop[j];}}}ipop = ipopnew;}// 交叉操作private void cross() {String temp1, temp2;for (int i = 0; i < ChrNum; i++) {if (Math.random() < crossover) {int pos = (int) (Math.random() * GENE) + 1; // pos位点前后二进制串交叉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;}}}// 基因突变操作private void mutation() {for (int i = 0; i < (int)(ChrNum*mutation); i++) {int chromosomeNum = (int) (Math.random() * ChrNum);// 染色体号：在数组中，对应的数字少一位，所以不用+1int mutationNum = (int) (Math.random() * GENE); // 基因号String temp;String a; // 记录变异位点变异后的编码if (ipop[chromosomeNum].charAt(mutationNum) == '0') { // 当变异位点为0时a = "1";} else {a = "0";}// 当变异位点在首、中段和尾时的突变情况if (mutationNum == 0) {temp = a + ipop[chromosomeNum].substring(mutationNum);} else {if (mutationNum != GENE - 1) {temp = ipop[chromosomeNum].substring(0, mutationNum) + a+ ipop[chromosomeNum].substring(mutationNum);} else {temp = ipop[chromosomeNum].substring(0, mutationNum) + a;}}// 记录下变异后的染色体ipop[chromosomeNum] = temp;}}public void solve() {ipop = initPop(); // 产生初始种群String str = "";// 迭代次数for (int i = 0; i < 100000; i++) {select();cross();mutation();generation = i;}double[] x = calculatefitnessvalue(beststr);str = "最小值" + bestfitness + '\n' + "第" + bestgenerations + "个染色体:<" + beststr + ">" + '\n' + "x=" + x[0] + '\n'+ "y=" + x[1];System.out.println(str);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！