遗传算法基础练习笔记
概述：
遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型。
遗传算法的主要步骤如下
1、初始化种群：先随机生成一群该问题的可能解，每个解可以看成一条染色体。比如5个物品的01背包问题随机一个解为[1,0,0,1,1]，构成这个解的信息是一串01数据，这就可以看成一条染色体，里面的0或1就是一个基因。一条染色体可以代表某物种的一个个体，随机生成的一堆解就可以看成一个自然生成的种群。01背包的解比较特殊，可以直接当做染色体，因为01数组的数据形式很方便后面阶段将要对染色体进行的交叉和变异操作。很多问题的解的形式比较复杂，这就需要通过编码把解的形式简化再表示染色体，等最后选出最优染色体时再解码成原问题的解的数据格式。编码的方法要具体问题具体分析，这里只需要知道有这个步骤就行。初始化步骤只需进行一次，后面的步骤都需要循环进行多次，即种群迭代多次。
2、计算适应度：生物进化的直接原因是环境改变，我们要想让一个种群按我们需要求解的方向进化，就把求解目标设为一个影响生物生存的环境因素，把生物个体(染色体)中与求解目标相关的值定为该个体的适应度。比如01背包问题的求解目标是装入背包的物品总价值最大化，种群中每个个体的染色体代表一个可能解，一个可能解对应一个装物品的方案，其中包括装入背包的物品编号、数量、重量、价值等信息。跟求解目标相关的是装入背包的物品价值，选其作为适应度就很合适。在复杂一些的问题中适应度可选的值不止一个，选不同的适应度运行效率不一样。遗传算法很多步骤是很灵活的，不同的策略往往能得到一样的结果，但是效率不一样。
3、选择下一代的父母染色体：计算完适应度就按这个标准淘汰不好的染色体(可能解)，淘汰的方法有很多，最常用的是轮盘赌选择法。轮盘赌选择法要先计算每个个体的生存率=个体适应度/所有个体的适应度总和，根据每个个体的生存率画出一个扇形图，在圆心加上一根指针就是一个简易的轮盘。转动轮盘时，每个个体被指针选中的概率等于其生存率。在程序中实现轮盘赌可以把每个个体的生存率排成一列，总长为1，每个个体不重叠地占据0-1中的某个小数区间，比如1,2,3号个体生存率分别为0.1,0.2,0.3，那么对应的区间就是[0,0.1],(0.1,0.3],(0.3,0.6]。随机生成一个0-1的小数，落在哪个个体占据的区间就表示选中哪个个体。每次转动轮盘大概率会选出一个适应度较高的个体作为下一代的父母，为了保证每次迭代后总群数量不变，轮盘转动的次数要等于种群数。适应度低的个体很可能一次都没被选中从而被淘汰，适应度高的个体可能被选中很多次，这意味着优秀基因者能进行多次交配产生多个子代。轮盘赌的效率比较高，但误差较大，优化的方法也有很大，各有利弊，后面再具体介绍。轮盘赌选择是影响种群进化的决定性步骤。
4、繁衍下一代染色体：选出父母染色体后就进行下一代的繁衍，基本规则是一对父母染色体产生两个孩子染色体，然后淘汰父母染色体，这样可以保证每一代的个体数是恒定的。被选出来的父母染色体都是原种群中较为优秀的染色体，繁衍下一代是为了产生更优秀的染色体，模仿大自然的规律，把一对父母染色体随机交换一段基因，生成两个子代染色体，这两个子代可能比父母更优秀也可能更差，差的会在下一次赌轮盘中被淘汰，而好的会脱颖而出。因为优秀的基因总是能获得更多繁衍子代的机会，所以总群的基因总是向好的方向进化。因为交换染色体的结果是随机的，假如所有的父母染色体都进行基因交换，就成了随机算法，结果不可控，有可能交换后的子代染色体普遍比父母代染色体差，那样种群就退化了。因此我们可以保守一点，设一个交叉率，值取0.5-0.9，让父母染色体只有0.5-0.9的概率能交换基因片段(交配)，剩下的就直接把染色体完整遗传(克隆)给下一代，这样即便交配获得的子代染色体都不好，克隆产生的子代还能保持不变，下一次赌轮盘大概率会选克隆的子代，这样种群至少也是保持不变而不会退化。
5、基因变异：生物进化的根本原因是基因突变。遗传算法生成的种群也一样，当某一个较优的染色体(可能解)在种群中占据一定数量优势时，交换染色体只会让更多染色体被它同化，最终同化完以后就不会产生更优的染色体了，所以需要基因突变，小范围改变一些基因也许会产生更优的染色体，这样就会继续进化。
一、0-1背包问题：给定 n 种物品和一背包。物品 i 的重量是wi，其价值为 vi，背包的容量为 c。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
实例：n = 10，c = 20，w =（3,1,4,5,3,6,7,8,9,7），v =（10,6,3,11,12,20,15,8,19,21）
package knapsack.problem;
/**遗传算法的资源类对象
* @author 矜君
* @date 2020/9/21 7:45.
*/
public class GeneticAlgResources01 {
//求解问题的资源：
/**
* 物品数量
*/
public int goodNum;
/**
* 背包容量(隐约束)
*/
public int capacity;
/**
* 各个物品的重量
*/
public int[] weight;
/**
* 各个物品的价值
*/
public int[] value;
//遗传算法的标配资源：
/**
* 染色体的基因数
*/
public int gene;
/**
* 种群的个体数
*/
public int populationNum;
/**
* 种群的染色体的基因序列
*/
public int[][] chromosome;
/**
* 种群适应度
*/
public int[] adaptiveness;
/**
* 种群适应度总和
*/
public int adaptivenessSum;
/**
* 总的演化代数
*/
public int generationNum;
/**
* 当前演化代数
*/
public int currGeneration = 0;
/**
* 生存者编号(有重复，足够优秀的个体可能被选中多次，这意味着它可以有多个孩子)
*/
public int[] parent;
/**
* 交叉概率
*/
public double crossoverRate;
/**
* 变异概率
*/
public double mutationRate;
/**
* 临时记录下一代的染色体
*/
public int[][] childChromosome;
/**
* 最优染色体的适应度(在本题最优适应度=最优值)
*/
public int optimalValue = 0;
/**
* 最优染色体的基因序列(最优解)
*/
public int[] optimalSolution;
/** 构造方法，只需要传入与问题相关的变量和遗传算法的四个主要影响变量
* @param goodNum 物品数量
* @param capacity 背包容量
* @param weight 物品重量
* @param value 物品价值
* @param populationNum 种群数量
* @param generationNum 遗传代数
* @param crossoverRate 交叉率
* @param mutationRate 变异率
*/
public GeneticAlgResources01(int goodNum, int capacity, int[] weight, int[] value,
int populationNum, int generationNum, double crossoverRate, double mutationRate) {
this.goodNum = goodNum;
this.capacity = capacity;
this.weight = weight;
this.value = value;
this.populationNum = populationNum;
this.generationNum = generationNum;
this.crossoverRate = crossoverRate;
this.mutationRate = mutationRate;
}
}
package knapsack.problem;
/**种群初始化
* @author 矜君
* @date 2020/9/21 8:51.
*/
public class GeneticAlgInitialization01 {
/** 初始化资源类数据，生成初代种群。
* @param ga01 资源类对象
*/
public static void initialization(GeneticAlgResources01 ga01){
//初始化资源类数据
ga01.gene=ga01.goodNum;
ga01.chromosome=new int[ga01.populationNum][ga01.gene];
ga01.adaptiveness= new int[ga01.populationNum];
ga01.parent = new int[ga01.populationNum];
ga01.childChromosome=new int[ga01.populationNum][ga01.gene];
ga01.optimalSolution = new int[ga01.gene];
//生成初代种群，直接遍历每条染色体的每个基因位置(数组元素)，随机生成0和1基因。
for (int i = 0; i < ga01.populationNum; i++) {
for (int j = 0; j < ga01.gene; j++) {
double r = Math.random();
ga01.chromosome[i][j]=Math.random()>r?1:0;
}
}
}
}
package knapsack.problem;
/**计算适应度
* @author 矜君
* @date 2020/9/21 11:26.
*/
public class GeneticAlgAdaptiveness01 {
/**计算当前种群每条染色体的适应度
* @param ga01 资源对象
*/
public static void countAdaptiveness(GeneticAlgResources01 ga01){
//适应度总和是直接用+=计算的，所以要先初始化。
ga01.adaptivenessSum=0;
//零时变量，记录当前种群的最优适应度及其编号
int bestAdaptiveness = 0;
int bestAdaptivenessNo = 0;
//遍历种群个体
for (int i = 0; i < ga01.populationNum; i++) {
//记录当前染色体的物品重量和价值
int currW = 0;
int currV = 0;
//遍历基因，计算当前染色体的物品重量和价值
for (int j = 0; j < ga01.gene; j++) {
currW+=ga01.chromosome[i][j]*ga01.weight[j];
if (currW<=ga01.capacity){
currV+=ga01.chromosome[i][j]*ga01.value[j];
}else {
//如果装入物品的重量超出背包重量，则当前染色体适应度为0
currV=0;
break;
}
}
//记录染色体i的适应度
ga01.adaptiveness[i]=currV;
ga01.adaptivenessSum+=currV;
//记录当前种群的最优适应度及其编号
if (currV>bestAdaptiveness){
bestAdaptiveness = currV;
bestAdaptivenessNo = i;
}
}
//如果当前种群的最优适应度大于当前之前每一代种群的最优适应度就更新当前的最优值和最优解
if (bestAdaptiveness > ga01.optimalValue){
ga01.optimalValue = bestAdaptiveness;
ga01.optimalSolution = ga01.chromosome[bestAdaptivenessNo].clone();
}
}
}
package knapsack.problem;
/**选择父母染色体
* @author 矜君
* @date 2020/9/21 13:09.
*/
public class GeneticOperatorSelection01 {
/**从当前种群中选择较优的染色作为下一代的父母
* @param ga01 资源对象
*/
public static void rouletteWheelSelect(GeneticAlgResources01 ga01){
int n = ga01.populationNum;
//计算每个个体的生存区间(用一维数组的区间对应轮盘的扇形面积)
double[] survivalRate = new double[n];
for (int i = 0; i < n; i++) {
double temp=(double) ga01.adaptiveness[i]/ga01.adaptivenessSum;
survivalRate[i]=i==0?temp:temp+survivalRate[i-1];
}
//转动次数=种群个体数
for (int i = 0; i < n; i++) {
//用随机数代表轮盘上的指针
double temp = Math.random();
//寻找被指针选中的个体编号
for (int j = 0; j < n; j++) {
if (temp<survivalRate[j]){
//被选中个体拥有繁衍后代的权力，放入父母数组，
ga01.parent[i]=j;
break;
}
}
}
}
}
package knapsack.problem;
/**染色体交叉
* @author 矜君
* @date 2020/9/21 16:48.
*/
public class GeneticOperatorCrossover01 {
/**父母染色体交叉或复制繁衍子代
* @param ga01 资源对象
*/
public static void crossover(GeneticAlgResources01 ga01){
//遍历父母染色体
for (int i = 0; i < ga01.populationNum; i++) {
//如果随机数小于交叉率就对i和i+1这对染色体进行交叉，产生的子代复制到临时记录子代染色体的数组。
if (i+1<ga01.populationNum && Math.random()<ga01.crossoverRate){
//单点交叉，随机生成交叉点，交叉点分割的后半段基因交换
int temp = (int)(Math.random()*ga01.gene);
System.arraycopy(ga01.chromosome[ga01.parent[i]],temp+1,ga01.childChromosome[i],temp+1,ga01.gene-temp-1);
System.arraycopy(ga01.chromosome[ga01.parent[i+1]],0,ga01.childChromosome[i],0,temp);
System.arraycopy(ga01.chromosome[ga01.parent[i]],0,ga01.childChromosome[i+1],0,temp);
System.arraycopy(ga01.chromosome[ga01.parent[i+1]],temp+1,ga01.childChromosome[i+1],temp+1,ga01.gene-temp-1);
i++;
}else {
//如果随机数大于交叉率就直接复制产生子代
ga01.childChromosome[i]=ga01.chromosome[ga01.parent[i]].clone();
}
}
}
}
package knapsack.problem;
/**染色体变异
* @author 矜君
* @date 2020/9/21 18:53.
*/
public class GeneticOperatorMutation01 {
/**子代染色体变异
* @param ga01 资源类
*/
public static void mutation(GeneticAlgResources01 ga01){
//遍历子代每个染色体的每个基因
for (int i = 0; i < ga01.populationNum; i++) {
for (int j = 0; j < ga01.gene; j++) {
//如果随机数小于变异率就把当前基因进行01转换
if (Math.random()<ga01.mutationRate){
ga01.childChromosome[i][j]=1-ga01.childChromosome[i][j];
}
}
}
//变异完后子代染色体就完成了，子代染色体替换父代，准备下一次迭代
for (int i = 0; i < ga01.populationNum; i++) {
ga01.chromosome[i]=ga01.childChromosome[i].clone();
}
}
}
package knapsack.problem;
import java.util.Arrays;
/**遗传算法主线程
* @author 矜君
* @date 2020/9/21 20:09.
*/
public class GeneticAlgDemo01 {
public static void main(String[] args) {
//物品数量
int goodNum = 10;
//背包容量(隐约束)
int capacity = 20;
//各个物品的重量
int[] weight = {3,1,4,5,3,6,7,8,9,7};
//各个物品的价值
int[] value = {10,6,3,11,12,20,15,8,19,21};
//种群个体数
int populationNum = 50;
//繁衍代数
int generationNum = 50;
//交叉率
double crossoverRate = 0.6;
//变异率
double mutationRate = 0.01;
//创建遗传算法的资源对象
GeneticAlgResources01 ga01 = new GeneticAlgResources01(goodNum,capacity,weight,value,populationNum,generationNum,crossoverRate,mutationRate);
//计算开始时间
long s = System.currentTimeMillis();
//初始化种群数据
GeneticAlgInitialization01.initialization(ga01);
//计算初代种群适应度
GeneticAlgAdaptiveness01.countAdaptiveness(ga01);
//繁衍迭代
for (int i = 0; i < generationNum; i++) {
//从i代中选择第i+1代的父母染色体
GeneticOperatorSelection01.rouletteWheelSelect(ga01);
//父母染色体交叉或复制繁衍子代
GeneticOperatorCrossover01.crossover(ga01);
//子代染色体变异并替换父代染色体
GeneticOperatorMutation01.mutation(ga01);
//计算i+1代的适应度
GeneticAlgAdaptiveness01.countAdaptiveness(ga01);
}
//计算结束时间
long e = System.currentTimeMillis();
System.out.println("最优值为：" + ga01.optimalValue);
System.out.println("最优解为：" + Arrays.toString(ga01.parent));
System.out.println("计算时间为："+(e-s)+"毫秒。");
}
}
二、旅行售货员问题：某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。
package travelling.salesman.problem;
import java.util.ArrayList;
import java.util.Arrays;
/**
* @author 矜君
* @date 2020/9/24 23:39.
*/
public class GA01 {
/**
* 城市数量
*/
private int n;
/**
* 出发城市
*/
private int startCity;
/**
* 城市的邻接矩阵
*/
private double[][] map;
/**
* 基因数
*/
private int gene;
/**
* 初代种群数量
*/
private int populationNum;
/**
* 初代种群的染色体的基因序列
*/
private int[][] chromosome;
/**
* 初代种群适应度
*/
private double[] adaptiveness;
/**
* 种群适应度总和
*/
private double adaptivenessSum;
/**
* 总的演化代数
*/
private int generationNum;
/**
* 当前演化代数
*/
private int currGeneration = 0;
/**
* 生存率
*/
private double[] survivalRate;
/**
* 生存者编号(有重复，足够优秀的个体可能被选中多次，这意味着它可以有多个孩子)
*/
private int[] parent;
/**
* 交叉概率
*/
private double matingRate;
/**
* 变异概率
*/
private double variationRate;
/**
* 初代种群的染色体的基因序列
*/
private int[][] childChromosome;
/**
* 最优染色体的适应度
*/
private double optimalValue = Double.MAX_VALUE;
/**
* 最优染色体的基因序列
*/
private int[] optimalSolution;
public GA01(int n, int startCity, double[][] map, int populationNum, int generationNum, double matingRate, double variationRate) {
this.n = n;
this.startCity = startCity;
this.map = map;
this.populationNum = populationNum;
this.generationNum = generationNum;
this.matingRate = matingRate;
this.variationRate = variationRate;
}
/**
* 生成初始种群
*/
private void initialization(){
if (currGeneration==0){
gene=n;
chromosome=new int[populationNum][gene];
adaptiveness= new double[populationNum];
survivalRate = new double[populationNum];
parent = new int[populationNum];
childChromosome=new int[populationNum][gene];
for (int i = 0; i < populationNum; i++) {
/*确保每个城市只出现一遍*/
boolean[] b = new boolean[gene];
chromosome[i][0] = startCity;
b[0] = true;
int j = gene;
while (j>0){
if (j==startCity){
j--;
continue;
}
int r = (int)(Math.random()*(gene-1))+1;
if (!b[r]){
chromosome[i][r]=j;
j--;
b[r]=true;
}
}
}
countAdaptiveness();
/*rouletteWheelSelect();
mating();*/
}
}
/**
* 计算适应度
*/
private void countAdaptiveness(){
/* System.out.print("种群：");
for (int[] ints : chromosome) {
System.out.print(Arrays.toString(ints)+" ");
}
System.out.println(" ");*/
adaptivenessSum=0;
double bestAdaptiveness = Double.MAX_VALUE;
int bestAdaptivenessNo = 0;
for (int i = 0; i < populationNum; i++) {
int previousCity = startCity;
double currCost = 0;
for (int j = 1; j < gene; j++) {
int currCity = chromosome[i][j];
if (map[previousCity][currCity]!=0){
currCost+=map[previousCity][currCity];
}else {
currCost=Double.MAX_VALUE;
break;
}
if (j==gene-1 ){
if (map[currCity][startCity]!=0){
currCost+=map[currCity][startCity];
}else {
currCost=Double.MAX_VALUE;
break;
}
}
previousCity = currCity;
}
/* if (currCost==22){
System.out.println("出问题的代数："+currGeneration);
}*/
if (currCost<bestAdaptiveness){
bestAdaptiveness = currCost;
bestAdaptivenessNo = i;
}
if (currCost<Double.MAX_VALUE){
adaptiveness[i] = (1.0/currCost);
adaptivenessSum += adaptiveness[i];
}
}
//averageAdaptiveness = (bestAdaptiveness+worstAdaptiveness)/2;
if (bestAdaptiveness < optimalValue){
optimalValue = bestAdaptiveness;
optimalSolution = chromosome[bestAdaptivenessNo].clone();
}
/*System.out.print("适应力：");
for (int i = 0; i < populationNum; i++) {
System.out.print(1.0/adaptiveness[i]+" ");
}*/
}
/**
* 轮盘赌选择
*/
private void rouletteWheelSelect(){
//计算适应度区间,路程越远，适应度越差，但是路程必须记录，所以在求生存率时再取倒数
for (int i = 0; i < populationNum; i++) {
double temp= adaptiveness[i]/adaptivenessSum;
survivalRate[i]=i==0?temp:temp+survivalRate[i-1];
}
/* System.out.print("生存率：");
System.out.println(Arrays.toString(survivalRate));
System.out.print("指针：[");*/
/* int number = 0;
while (number<populationNum){
double temp = Math.random();
for (int j = 0; j < populationNum; j++) {
if (temp<survivalRate[j] && adaptiveness[j]>=averageAdaptiveness){
parent[number]=j;
number++;
break;
}
}
}*/
for (int i = 0; i < populationNum; i++) {
double temp = Math.random();
// System.out.print(temp+",");
for (int j = 0; j < populationNum; j++) {
if (temp<survivalRate[j]){
// System.out.print(j+"