遗传算法
超详细遗传算法（图文并茂）
一.前言
- 遗传算法（GA）主要用来解决TSP问题和复杂多项式求解问题。先从最简单的经典的遗传算法开始，再逐渐延伸（自适应交叉，自适应变异，退火式变异）。
- 本人现为大三在校生，能力有限，文章中肯定存在很多不足之处。可以留言讨论。或者联系作者邮箱：zi.bo@qq.com。
- 实验环境：windows 10 vs2017
- 实验题目取自 https://www.cnblogs.com/lyrichu/p/6152928.html
代码全部编译通过，并且得出理想结果。
二.什么是遗传算法？
- 遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
- 我自己理解的意思为：先随机构造一个种群，然后根据适应度选择优秀的个体。让这些优秀个体繁衍出后代，为了不使种群陷入恶性循环还需要对部分个体变异。（为了加快进化速度还可以对染色体进行逆转等等）
三.遗传算法的一般步骤
假设有一名商人想去 济南市、德州市、聊城市、菏泽市、泰安市、莱芜市、济宁市、枣庄市、临沂市、日照市、青岛市、威海市、烟台市、潍坊市，商人目前正在济南市。
要求：
- 所走路程最近；
- 每个城市只能访问一次；
- 从某城市出发，最后回到该城市
根据要求，求解一条路径。
-
编码
在本问题来看，我们需要求解出的是一条路径。换个角度说：对这些城市进行排序，看看哪种顺序最符合我们的三个要求。而一个城市就对应大自然中的一个 基因 。而本题目中的14个城市一次排序就构成了一条路。这一条路对应自然中的一条染色体 。根据染色体计算出的路径总长度即是 适应度。N条染色体可以构成一个种群（种群的大小是人为规定的)。 -
选择
选择操作就是根据染色体的适应度选择符合要求的染色体。在本问题中我们选择染色体的概率和适应度成正比，路径越短，染色体的适应度越大，被选到的概率越高。所以我们采用轮盘赌算法来选择优秀个体。
3.交叉
交叉是产生新个体的主要操作。这里我们采用PMX交叉算法。让被选择的两个优秀基因根据交叉算法产生的新的个体。 -
变异
程序再具体执行时，有概率会产生一个值（染色体），这个值并不是我们想要的，但又因为规则的不完善或者其他情况，后代总是围绕着这个值变化。这个现象我们成为“早熟”。为了避免这个现象我们随机产生一个值（染色体），用来打破当前这个局面。
四.具体做法
需要的变量
- 定义一个全局变量
const int evolution_Pop用来存储进化次数 - 定义一个全局变量
const int lenght用来保存城市的个数 - 定义一个全局变量
const int pop_Size用来保存种群大小（规模） - 定义一个二维数组
int city_Pos[lenght][2]用来保存城市的坐标（坐标稍后在程序中给出） - 定义一个二维数组
int population[pop_Size][lenght]用来保存解集 - 定义一个一维数组
pop_Fitness[pop_Size]用来保存染色体的适应度
以上变量都是 全局变量
程序开始
- 程序开始先初始化种群：
void init_Pop()。在这里我把种群规模设定为300。即初始化300条染色体。我们先把种群数组population[pop_Size][lenght]都赋值｛0，1，2，3，4。。。｝0即代表济南，1代表德州，2代表聊城，以此类推。为了加快收敛速度，基因的排序越混乱越好。所以接下来我们把每条染色体打乱。在这里因为种群数和城市数量较少。所以采用了这样的思想： - 先让0排在最前边
- 随后0与1交换，0与2交换，0与3交换。。一直到0与最后一个元素交换完。
- 当0全部交换完毕后，让1与右边的数值依次交换。
- 1也交换完毕后向右，依次用2交换。这样全部交换完成后一共有(N-1)!条染色体（排列）。如果染色体数目不够，可以将popluation数组倒序排列｛13，12，11，10。。｝然后再按照以上步骤排列。
代码实现
void init() //初始化种群
{
int pop_num = 1; //染色体数量
for (int i = 0; i < pop_Size; i++)
{
for (int j = 0; j < lenght; j++)
{
population[i][j] = j; //初始化种群
}
}
start:for (int i = 0; i < lenght - 1; i++) //构造种群
{
for (int j = 1; (i + j) < lenght; j++) //将第一个数值 与第1，2，3，4。。。。。互换位置构造成新的解集
{
int temp = population[pop_num][i];
population[pop_num][i] = population[pop_num][i + j];
population[pop_num][i + j] = temp;
if (pop_num >= pop_Size)
{
goto end;
}
pop_num++;
}
}
for (int i = pop_num; i < pop_Size; i++) //逆转值再次构造
{
for (int j = 0; j < lenght; j++)
{
population[i][j] = lenght - j - 1;
}
}
goto start;
end:pop_num++;
}
再提供一种办法，用于超大规模的种群构造
/*void permutation(int levels, int lenght, int a[])
{
//递归到底层
int pop_num = 1;//染色体数量
if (levels == lenght - 1)
{
for (int j = 0; j < lenght; j++)
population[pop_num][j] = a[j];
pop_num++;
}
else
{
for (int i = levels; i < lenght; i++)
{
int temp = a[levels];
a[levels] = a[i];
a[i] = temp;
//交换后递归下一层
permutation(levels + 1, lenght, a);
//保证每一层递归后保持上一层的顺序
temp = a[levels];
a[levels] = a[i];
a[i] = temp;
}
}
}*/
- 种群构造完成后，计算每条染色体的适应度存储到
pop_Fitness数组中。这里分成了两个函数:void path_Pop(int *arr)和double *distance(double x,double y)。其中path_Pop函数接收一条染色体。然后将染色体第1 和2 ，2和3， 3和4个元素，一直到12和13两两一组传递给distance函数，distance接收到两个值后，找到city_Pos对应的坐标，计算出两个城市间的距离返回给path_Pop函数，path_Pop函数将距离加在一起就是整条路径的距离（也是染色体的适应度）。
代码实现：
double distance(double* x, double* y) //两个城市之间的距离
{
double x1 = *x;
double y1 = *(x + 1);
double x2 = *y;
double y2 = *(y + 1);
double distances = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)); //勾股定理求两个点之间的距离
return distances;
}
double path_Pop(int *arr) //染色体总距离
{
double path_Pop_Dis = 0.0; //存储距离
double path_Sum_Dis = 0.0;
int first_Pos = *arr; //存储第一个点得位置
for (int i = 0; i < lenght-1; i++)
{
int x1 = *(arr+i);
int x2 = *(arr + i+1);
path_Pop_Dis = distance(city_Pos[x1], city_Pos[x2]);
path_Sum_Dis += path_Pop_Dis;
}
int last_Pos = *(arr + 13);
path_Sum_Dis += distance(city_Pos[first_Pos], city_Pos[last_Pos]); //总距离包括最后一个点回到第一个点的距离
return path_Sum_Dis;
}
- 种群初始化完成后就是evolution_Pop次选择 ,交叉 , 遗传 。
- 选择 操作
- 选择操作是根据染色体适应度大小实现。本质上来说就是一个轮盘赌算法。
- 首先求出种群适应度的值（也就是全部染色体适应度的和）。
- 在用每条染色体的适应度除以适应度的总和，这样可以将染色体适应度映射为一条区间[0,1]的线段。
- 给出一个[0,1)的随机值pick。从
i = 0开始,执行到i = pop_Size每次执行pick-=(pop_Fitness[i]/sum_Fitness)如果pick<=0则选中这个区间所在位置对应的染色体。 - 执行pop_Size次。
- 选择操作代码
void select()
{
double pop_Fintess_Avg = 0; //适应度平均值
double pop_Fitness_Sum = 0.0; //适应度和
double pop_Fitness_Rec[pop_Size]; //适应度倒数
double pop_Fitness_Rec_Sum = 0.0; //适应度平均值的和
for (int i = 0; i < pop_Size; i++)
{
pop_Fitness_Rec_Sum += 1 / pop_Fitness[i]; //倒数和
}
int postion[pop_Size][lenght];
for (int i = 0; i < pop_Size; i++) //轮盘赌法
{
double pick = ((double)rand()) / RAND_MAX;
while(pick>=1)
pick = ((double)rand()) / RAND_MAX;
double prob = pick;
for (int j = 0; j < pop_Size; j++)
{
pick = pick - ((1 / pop_Fitness[j])/ pop_Fitness_Rec_Sum);
if (pick <= 0)
{
for (int m = 0; m < lenght; m++)
{
postion[i][m] = population[j][m];
}
break;
}
}
}
for (int i = 0; i <pop_Size; i++)
{
for (int j = 0; j < lenght; j++)
{
population[i][j] = postion[i][j];
}
}
for (int i = 0; i < pop_Size; i++)//更新每条染色体的适应度
{
pop_Fitness[i] = path_Pop(population[i]);
}
}
- 交叉操作
- 首先从种群的第一条染色体开始，给出一个[0,1]随机数如果，随机数>0.6则开始交叉，否则跳过这条染色体。以此类推。(有时间再写一篇关于这个交叉概率的文章)。这里先记住交叉概率0.6.
- 在染色体上随机选取一段基因，与另一条染色体交换选取的基因。
- 由上图可以看出，交叉后的基因有冲突。所以交叉后要解决冲突。第一步要检测并记录冲突。检测的元素不能是交叉过的基因，假设第一条染色体为A,第二条染色体为B。从A[0] 开始，先检查A[0]是否是交叉过的元素，不是取A[1]与A[0]比较，如果相等则将A[0]的位置记录到二维数组repeat_Pop[2][lenght]中（repeat_Pop[0]记录A的位置，repeat_Pop[1]记录染色体B的位置），如果不相等取A[2]与A[0]比较，取A[3]，取A[4]。。。A[0]比较完成后。再拿A[1]，检查是否是交叉过的元素，然后依次与整个数组内的其它元素比较。
- 检查完染色体A后，再以同样的方法检查染色体B。
- 两个染色体都检查完成后，将染色体A第一个冲突位置repeat_Pop[0][0]与染色体B的第一个冲突位置repeat_Pop[1][0]互换值。以此类推互换全部冲突位置的值。（下图红色虚线是冲突位置，灰色虚线是交叉位置）
- 最后所有染色体交叉完成后，更新染色体的适应度
- 代码实现
void cross() //交叉操作
{
int temp; //交叉缓存
int repeat_Pop[2][lenght]; //记录重复位置
int number = 0; //记录冲突基因个数
int pick; //交叉长度
for (int i = 0; i < pop_Size - 1; i++) //交叉开始
{
double cross_Prob = ((double)rand()) / RAND_MAX;
if (cross_Prob > 0.6)
continue;
int pos = Rand(0, lenght - 1); //选择一个位置
pick = (0, lenght - pos - 1); //交叉区间
for (int j = 0; j < pick; j++) //PMX基因交叉法
{
temp = population[i][pos + j];
population[i][pos + j] = population[i + 1][pos + j];
population[i + 1][pos + j] = temp;
}
for (int k = 0; k < 2; k++)
{
number = 0;
for (int m = 0; m < lenght; m++)
{
if (m < pos || m>(pos + pick-1))
{
for (int n = 0; n < lenght; n++)
{
if (n != m)
{
if (k == 0)
{
if (population[i][m] == population[i][n])
{
repeat_Pop[k][number++] = m;//记录冲突基因所在位置
break;
}
}
else
{
if(population[i+1][m] == population[i+1][n])
{
repeat_Pop[k][number++] = m;//记录冲突基因所在位置
break;
}
}
}
else
{
continue;
}
}
}
else
{
continue;
}
}
}
for (int k = 0; k <number;k++)//解决冲突
{
int temp = population[i][repeat_Pop[0][k]];
population[i][repeat_Pop[0][k]] = population[i + 1][repeat_Pop[1][k]];
population[i + 1][repeat_Pop[1][k]] = temp;
}
}
for (int i = 0; i < pop_Size; i++) //更新每条染色体的适应度
{
pop_Fitness[i] = path_Pop(population[i]);
}
}
5.变异操作
变异操作估摸着是整个算法中最简单的一部分了，但深入研究后也会发现许多东西，比如一般变异率设定为0.1。(和交叉概率意思相同),如果变异概率数值过大，此算法变成一个随机算法。如果变异概率过小,又不能打破“早熟”局面。所以还有一个更优秀的自适应变异概率(有机会个自适应交叉一块写出来)。
- 同交叉一样，先从种群的第一条染色体开始，给一个[0,1]的随机数，如果随机数>0.1则跳过这条染色体，否则进入变异操作。
- 随机在染色体上选择两个位置，交换这两个位置的值。
- 全部执行完成后，更新染色体适应度。
- 代码实现
for (int i = 0; i < pop_Size; i++)
{
double variation_Prob = ((double)rand()) / RAND_MAX;
if (variation_Prob > 0.1)
continue;
int pos_One = Rand(0, lenght - 1); //选择一个位置
int pos_Two = Rand(0, lenght - 1); //再选择一个位置
int temp = population[i][pos_One]; //交换这两个位置的基因
population[i][pos_One] = population[i][pos_Two];
population[i][pos_Two] = temp;
}
for (int i = 0; i < pop_Size; i++) //更新每条染色体的适应度
{
pop_Fitness[i] = path_Pop(population[i]);
}
五. 后记
- 在代码中有一个rand()函数。在当时写这个算法的时候，这个rand()着实给我带来了不小问题。所以重写了rand()函数的部分功能。
- 关于轮盘赌算法中随机数取值问题：作者当时随机数的取值为[0,1]，当随机数为1的时候。程序会直接bug。关于这里直到现在也没弄清楚为什么不能取1.(猜想是IDE在处理double类型数据会丢失部分小数，所以达不到1)
六. 全部代码
#include<iostream>
#include<cmath>
#include<ctime>
#include<stdlib.h>
using namespace std;
const int lenght = 14; //城市个数也是染色体长度
const int pop_Size = 100; //种群规模
double city_Pos[lenght][2]= { {16.47,96.10},{16.47,94.44},{20.09,92.54},{22.39,93.37},{25.23,97.24},{22.00,96.05},{20.47,97.02},
{17.20,96.29},{16.30,97.38},{14.05,98.12},{16.53,97.38},{21.52,95.59},{19.41,97.13},{20.09,92.55} }; //城市坐标
int population[pop_Size][lenght]; //存放解集
double pop_Fitness[pop_Size]; //染色体适应度
double distance(double * x, double *y); //两个城市之间的距离
double path_Pop(int*arr); //染色体总距离 即求染色体适应度
void permutation(int levels, int n, int a[]); //递归构造解集，种群规模超过1W时可以考虑用这个函数
void init(); //初始化一条染色体
int Rand(int upper,int lower); //随机一个 lower <= 整数 <= upper
void select(); //操作
void cross(); //交叉操作
void variation(); //变异操作
void reverse_Variariation(); //逆转加速进化操作
double * Min()
{
double temp =100;
double sum[2] = { 0 };
double avg = 0;
double * arr = sum;
for (int i = 0; i < pop_Size; i++)
{
if (temp > pop_Fitness[i])
{
temp = pop_Fitness[i];
}
sum[0] += pop_Fitness[i];
}
sum[1] = sum[0] / pop_Size;
sum[0] = temp;
return arr;
}
int main()
{
srand((unsigned)time(NULL) );
time_t start, finish;
init();
start = clock();
for (int i = 0; i < 1000; i++)
{
select();
cross();
variation();
}
finish = clock();
double times = ((double)(finish - start)) / CLOCKS_PER_SEC;
double *arr = Min();
cout << "最短路径 " << *arr << " 平均值：" << *(arr+1);
}
int Rand(int upper, int lower)
{
if (upper < lower) //分好上下界
{
int temp = upper;
upper = lower;
lower = temp;
}
if (upper >= 0&&lower >= 0) //两个正整数
{
restart: int randoms_Plus = (int)rand() % (upper - lower + 1) + lower;
if (randoms_Plus<lower || randoms_Plus>upper) //检查结果
{
goto restart;
}
return randoms_Plus;
}
else if(upper>=0&&lower <= 0) //一正一负
{
restart1: int randoms_Plus = (int)rand() % (upper)+1; //先随机出 1<= randoms <= upper的一个正整数
int randoms_Neg = -(int)rand() % (abs(lower) + 1); //再随机出 abs(lower)<= randoms <=0的一个负整数
// randoms_Neg = -randoms_Neg;//将正整数变成负整数
if (((double)rand() / RAND_MAX)<= ((double)upper / (1+upper + abs(lower)))) //轮盘赌法确定正负出现概率
{
if (randoms_Plus<lower || randoms_Plus>upper) //检查结果
{
goto restart1;
}
return randoms_Plus;
}
else
{
if (randoms_Neg<lower || randoms_Neg>upper) //检查结果
{
goto restart1;
}
return randoms_Neg;
}
}
else //两个负数
{
restart2: int randoms_Plus = (int)rand() % (abs(lower) - abs(upper) + 1) + abs(upper);
if ((-randoms_Plus) < lower || (-randoms_Plus) > upper) //检查结果
{
goto restart2;
}
return -randoms_Plus;
}
}
double distance(double* x, double* y) //两个城市之间的距离
{
double x1 = *x;
double y1 = *(x + 1);
double x2 = *y;
double y2 = *(y + 1);
double distances = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)); //勾股定理求两个点之间的距离
return distances;
}
double path_Pop(int *arr) //染色体总距离
{
double path_Pop_Dis = 0.0; //存储距离
double path_Sum_Dis = 0.0;
int first_Pos = *arr; //存储第一个点得位置
for (int i = 0; i < lenght-1; i++)
{
int x1 = *(arr+i);
int x2 = *(arr + i+1);
path_Pop_Dis = distance(city_Pos[x1], city_Pos[x2]);
path_Sum_Dis += path_Pop_Dis;
}
int last_Pos = *(arr + 13);
path_Sum_Dis += distance(city_Pos[first_Pos], city_Pos[last_Pos]); //总距离包括最后一个点回到第一个点的距离
return path_Sum_Dis;
}
/*void permutation(int levels, int lenght, int a[])
{
//递归到底层
int pop_num = 1;//染色体数量
if (levels == lenght - 1)
{
for (int j = 0; j < lenght; j++)
population[pop_num][j] = a[j];
pop_num++;
}
else
{
for (int i = levels; i < lenght; i++)
{
int temp = a[levels];
a[levels] = a[i];
a[i] = temp;
//交换后递归下一层
permutation(levels + 1, lenght, a);
//保证每一层递归后保持上一层的顺序
temp = a[levels];
a[levels] = a[i];
a[i] = temp;
}
}
}*/
void init() //这个办法有点蠢 下次优化改进
{
int pop_num = 1; //染色体数量
for (int i = 0; i < pop_Size; i++)
{
for (int j = 0; j < lenght; j++)
{
population[i][j] = j; //初始化种群
}
}
start:for (int i = 0; i < lenght - 1; i++) //构造种群
{
for (int j = 1; (i + j) < lenght; j++) //将第一个数值 与第1，2，3，4。。。。。互换位置构造成新的解集
{
int temp = population[pop_num][i];
population[pop_num][i] = population[pop_num][i + j];
population[pop_num][i + j] = temp;
if (pop_num >= pop_Size)
{
goto end;
}
pop_num++;
}
}
for (int i = pop_num; i < pop_Size; i++) //逆转值再次构造
{
for (int j = 0; j < lenght; j++)
{
population[i][j] = lenght - j - 1;
}
}
goto start;
end:pop_num++;
}
void select()
{
double pop_Fintess_Avg = 0;//适应度平均值
double pop_Fitness_Sum = 0.0;//适应度和
double pop_Fitness_Rec[pop_Size];//适应度倒数
double pop_Fitness_Rec_Sum = 0.0;//适应度平均值的和
for (int i = 0; i < pop_Size; i++)//更新每条染色体的适应度
{
pop_Fitness[i] = path_Pop(population[i]);
}
for (int i = 0; i < pop_Size; i++)
{
pop_Fitness_Rec[i] = 1 / pop_Fitness[i];//染色体的倒数
}
for (int i = 0; i < pop_Size; i++)
{
pop_Fitness_Rec_Sum += 1 / pop_Fitness[i]; //倒数和
}
int postion[pop_Size][lenght];
for (int i = 0; i < pop_Size; i++)//轮盘赌法
{
double pick = ((double)rand()) / RAND_MAX;
while(pick>=1)
pick = ((double)rand()) / RAND_MAX;
double prob = pick;
for (int j = 0; j < pop_Size; j++)
{
pick = pick - ((1 / pop_Fitness[j])/ pop_Fitness_Rec_Sum);
if (pick <= 0)
{
for (int m = 0; m < lenght; m++)
{
postion[i][m] = population[j][m];
}
break;
}
}
}
for (int i = 0; i <pop_Size; i++)
{
for (int j = 0; j < lenght; j++)
{
population[i][j] = postion[i][j];
}
}
for (int i = 0; i < pop_Size; i++)//更新每条染色体的适应度
{
pop_Fitness[i] = path_Pop(population[i]);
}
}
void cross() //交叉操作
{
int temp; //交叉缓存
int repeat_Pop[2][lenght]; //记录重复位置
int number = 0; //记录冲突基因个数
int pick; //交叉长度
for (int i = 0; i < pop_Size - 1; i++) //交叉开始
{
double cross_Prob = ((double)rand()) / RAND_MAX;
if (cross_Prob > 0.6)
continue;
int pos = Rand(0, lenght - 1); //选择一个位置
pick = (0, lenght - pos - 1); //交叉区间
for (int j = 0; j < pick; j++) //PMX基因交叉法
{
temp = population[i][pos + j];
population[i][pos + j] = population[i + 1][pos + j];
population[i + 1][pos + j] = temp;
}
for (int k = 0; k < 2; k++)
{
number = 0;
for (int m = 0; m < lenght; m++)
{
if (m < pos || m>(pos + pick-1))
{
for (int n = 0; n < lenght; n++)
{
if (n != m)
{
if (k == 0)
{
if (population[i][m] == population[i][n])
{
repeat_Pop[k][number++] = m;//记录冲突基因所在位置
break;
}
}
else
{
if(population[i+1][m] == population[i+1][n])
{
repeat_Pop[k][number++] = m;//记录冲突基因所在位置
break;
}
}
}
else
{
continue;
}
}
}
else
{
continue;
}
}
}
for (int k = 0; k <number;k++)//解决冲突
{
int temp = population[i][repeat_Pop[0][k]];
population[i][repeat_Pop[0][k]] = population[i + 1][repeat_Pop[1][k]];
population[i + 1][repeat_Pop[1][k]] = temp;
}
}
for (int i = 0; i < pop_Size; i++) //更新每条染色体的适应度
{
pop_Fitness[i] = path_Pop(population[i]);
}
}
void variation() //变异操作
{
for (int i = 0; i < pop_Size; i++)
{
double variation_Prob = ((double)rand()) / RAND_MAX;
if (variation_Prob > 0.1)
continue;
int pos_One = Rand(0, lenght - 1); //选择一个位置
int pos_Two = Rand(0, lenght - 1); //再选择一个位置
int temp = population[i][pos_One]; //交换这两个位置的基因
population[i][pos_One] = population[i][pos_Two];
population[i][pos_Two] = temp;
}
for (int i = 0; i < pop_Size; i++) //更新每条染色体的适应度
{
pop_Fitness[i] = path_Pop(population[i]);
}
}