人工智能——遗传算法
姓名：杨晶晶 学号：21011210420 学院：通信工程学院
转载自：https://blog.csdn.net/ritterliu/article/details/54821300
【嵌牛导读】遗传算法，核心是达尔文优胜劣汰适者生存的进化理论的思想。我们都知道一个种群，通过长时间的繁衍，种群的基因会向着更适应环境的趋势进化，优良的基因会被保留，后代越来越多，适应能力低个体的基因被淘汰，后代越来越少。经过几代的繁衍进化，留下来的少数个体，就是相对能力最强的个体了。那么在解决一些问题的时候，我们能不能学习这样的思想。
【嵌牛鼻子】遗传算法的基本概念；遗传算法代码。
【嵌牛提问】什么是遗传算法？利用C语言设计相关代码进行验证。
【嵌牛正文】
遗传算法介绍
遗传算法是一种模拟生命进化机制的搜索和优化方法，是把自然遗传学和计算机科学结合起来的优化方程，有很强的解决问题的能力和广泛的适应性。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索合适的假设从若干初始假设的群体集合开始。当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。每一步，根据给定的适应度评估当前群体的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子。
遗传算法的几个基本概念
（1）染色体（Chromosome）：在使用遗传算法时，需要把问题的解编成一个适合的码子。这种具有固定结构的符号串既是染色体，符号串的每一位代表一个基因。符号串的总位数成为染色体的长度，一个染色体就代表问题的一个解，每个染色体也被称为一个个体。
（2）群体（Population）：每代所产生的染色体总数成为群体，一个群体包含了该问题在这一代的一些解的集合。
（3）适应度（Fitness）：对群体中每个染色体进行编码后，每个个体对应一个具体问题的解，而每个解对应于一个函数值。该函数值即适应函数，就是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数
基本的遗传操作
（1）选择（Select）：按一定的概率从上代群体中选择M对个体作为双亲，直接拷贝到下一代，染色体不发生变化。
（2）交叉（Crossover）：对于选中进行繁殖的两个染色体X，Y，以X，Y为双亲作交叉操作，从而产生两个后代X1，Y1.
（3）变异（Mutation）：对于选中的群体中的个体（染色体），随机选取某一位进行取反运算，即将该染色体码翻转。
用遗传算法求解的过程是根据待解决问题的参数集进行编码，随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。如果满足收敛条件，此种群为最好个体，否则，对产生的新一代群体重新进行选择、交叉、变异操作，循环往复直到满足条件。
TSP问题
所谓TSP问题（旅行商问题）即最短路径问题就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。用遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。
TSP问题的遗传算法设计与实现
（１）编码问题：由于这是一个离散型的问题，我们采用整数编码的方式，用1－ｎ来表示n个城市，1－n的任意一个排列就构成了问题的一个解。可以知道，对于n个城市的TSP问题，一共有n!种不同的路线。
（２）种群初始化：对于N个个体的种群，随机给出N个问题的解（相当于是染色体）作为初始种群。这里具体采用的方法是：1,2，…,n作为第一个个体，然后2,3，…n分别与1交换位置得到n-1个解，从2开始，3,4,…,n分别与2交换位置得到n-2个解，依次类推。（如果这样还不够初始种群的数量，可以再考虑n,n-1,…,1这个序列，然后再按照相同的方法生成，等等）
（３）适应度函数：设一个解遍历初始行走的总距离为D，则适应度fitness=1/D.即总距离越高，适应度越低，总距离越低（解越好），适应度越高。
（４）选择操作：个体被选中的概率与适应度成正比，适应度越高，个体被选中的概率越大。这里仍然采用轮盘赌法。选择作为交叉的双亲，是根据前代染色体的适应函数值所确定的，质量好的个体，即从起点到终点路径长度短的个体被选中的概率较大。交叉率不可选择过小，否则，延缓获得最优解的过程，本程序选择 =0.85。
（５）交叉操作：交叉操作是遗传算法最重要的操作，是产生新个体的主要来源，直接关系到算法的全局寻优能力，这里采用部分映射交叉。比如对于n = 10的情况，对于两个路径:
1 2 4 5 6 3 9 0 8 7
3 9 7 6 8 0 5 1 2 4
随机产生两个[1,10]之间的随机数r1，r2，代表选择交叉的位置，比如r1 = 2，r2 = 4,如上图划线的位置，将第一个个体r1到r2之间的基因(即城市序号)与第二个个体r1到r2之间的基因交换，交换之后变为:
1 9 7 6 6 3 9 0 8 7
3 2 4 5 8 0 5 1 2 4
划线部分表示交叉过来的基因，这个时候会发现可能交叉过来的基因与原来其他位置上的基因有重复，容易直到，第一个个体重复基因的数目与第二个个体重复基因的数目是相同的（这里都是3个），只需要把第一个个体重复的基因与第二个个体重复的基因做交换，即可以消除冲突。消除冲突之后的解如下:
1 9 7 6 5 3 2 0 8 4
3 2 4 5 8 0 6 1 9 7
（６）变异操作:变异操作采取对于一个染色体(即个体)随机选取两个基因进行交换的策略。比如对于染色体:
2 4 6 0 3 1 9 7 8 5
随机选取了两个位置p1=3,p2=8,交换这两个位置的基因，得到新的染色体为:
2 4 7 0 3 1 9 6 8 5
变异率的选择对规模大的优化问题影响很大，本程序选 0.1。为了使算法尽可能快地获得更好的解，改善遗传算法的收敛性。在变异操作时，增加了个体求优的自学习过程，即在某位基因变异后.计算新产生的染色体的适应函数值，若适应函数值更小，即获得的路径更短，则保留;否则，保持原来的解不变。
流程图
效果图
个人观点：
（１）还是那句话，程序 = 数据结构 + 算法，所以实现遗传算法，预先设计一个简单有效的数据结构至关重要，一个好的数据结构，会让我们在编码过程当中，更容易理解和处理程序流程。
（２）遗传算法并没有想象的那么复杂和困难，在完成编码以后，深刻认识到遗传算法其实就是一种在大量数据中的搜索方法，同时，具有除去不理想状态结点的功能，这无疑是遗传算法的要害之处，极大的增加了程序的收敛性，通过无数次的迭代，不断从一组数据当中选出当前组当中最好的数据，然后再形成一组数据，这些数据在经过某些调整（选择、交叉和变异），有可能会产生更理想的数据 。依照此法，不断迭代生成新的数据，选出较为理想的数据，随着迭代次数的增加，所产生的数据就会不断靠近，甚至等于问题的最优解。
完整源代码：
//population 种群
//Chromosome 染色体
//survival 存活
//crossover rate 交叉率
//mutation rate 突变率
//probability 概率
#include "stdio.h"
#include "stdlib.h"
#include "windows.h"
#include "time.h"
#define cityNum 10 //城市数量（基因数量）（染色体长度）
#define popSize 10 //种群大小（尺寸）
#define croRate 0.85 //交叉概率
#define mutRate 0.1 //变异概率
#define MAX 999 //进化代数
//定义染色体的结构
struct Chrom
{
int cityArr[cityNum]; //染色体的基因编码
char name; //染色体的名称
float adapt; //染色体的适应度
int dis; //染色体的路径长度
};
struct Chrom genes[popSize]; //定义基因库（结构体数组）
struct Chrom genesNew[popSize]; //重新建立一个新的种群
struct Chrom temp; //定义临时公用结点
char names[cityNum] = {'A','B','C','D','E','F','G','H','I','J'}; //城市名称
int distance[cityNum][cityNum] = {{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, //城市距离矩阵
{ 1, 0, 1, 2, 3, 4, 5, 6, 7, 8 },
{ 2, 1, 0, 1, 2, 3, 4, 5, 6, 7 },
{ 3, 2, 1, 0, 1, 2, 3, 4, 5, 6 },
{ 4, 3, 2, 1, 0, 1, 2, 3, 4, 5 },
{ 5, 4, 3, 2, 1, 0, 1, 2, 3, 4 },
{ 6, 5, 4, 3, 2, 1, 0, 1, 2, 3 },
{ 7, 6, 5, 4, 3, 2, 1, 0, 1, 2 },
{ 8, 7, 6, 5, 4, 3, 2, 1, 0, 1 },
{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }}; //最优解为18
void initGroup()
{
//初始化基因库
int i,j,k;
int t = 0;
int flag = 0;
srand(time(NULL));//初始化随机种子,防止随机数每次重复，常常使用系统时间来初始化,当srand()的参数值固定的时候，rand()获得的数也是固定的
for(i = 0; i < popSize; i ++)
{
//使用临时结点开始赋值
temp.name = names[i];
temp.adapt = 0.0f;
temp.dis = 0;
//产生10个不相同的数字
for(j = 0; j < cityNum;)
{
t = rand()%cityNum; //随机产生0-9的数
flag = 1;
for(k = 0; k < j; k ++)
{
if(genes[i].cityArr[k] == t)
{
flag = 0;
break;
}
}
if(flag)
{
temp.cityArr[j] = t;
genes[i] = temp;//存入结构体数组，产生一个个体
j++;
}
}
}
}
//计算种群所有染色体的个体适应度
void popFitness()
{
int i,n1,n2;
for(i = 0; i < popSize; i ++)
{
genes[i].dis = 0;
for(int j = 1;j < cityNum; j ++)
{
n1 = genes[i].cityArr[j-1];
n2 = genes[i].cityArr[j];
genes[i].dis += distance[n1][n2];
}
genes[i].dis += distance[genes[i].cityArr[0]][genes[i].cityArr[cityNum-1]];
genes[i].adapt = (float)1/genes[i].dis; //每条染色体的路径总和(个体适应度)
}
}
//返回最优秀的一条染色体
int chooseBest()
{
int choose = 0;
float best = 0.0f;
best = genes[0].adapt;
for(int i = 0; i < popSize; i ++)
{
if(genes[i].adapt < best)
{
best = genes[i].adapt;
choose = i;
}
}
return choose;
}
// 选择操作
void select()
{
float biggestSum = 0.0f;
float adapt_pro[popSize];
float pick = 0.0f;
int i;
for(i = 0; i < popSize; i ++)
{
biggestSum += genes[i].adapt; // 总概率
}
for(i = 0; i < popSize; i ++)
{
adapt_pro[i] = genes[i].adapt / biggestSum; // 概率数组
}
// 轮盘赌
for(i = 0;i < popSize; i ++)
{
pick = (float)rand()/RAND_MAX; // 0到1之间的随机数
for(int j = 0; j < popSize; j ++)
{
pick = pick - adapt_pro[j];
if(pick <= 0)
{
genesNew[i] = genes[j];
break;
}
}
}
for(i = 0;i < popSize; i++)
{
genes[i] = genesNew[i];
}
}
// 交叉操作
void cross()
{
float pick;
int choice1,choice2;
int pos1,pos2;
int temp;
int conflict1[popSize]; // 冲突位置
int conflict2[popSize];
int num1;
int num2;
int index1,index2;
int move = 0; // 当前移动的位置
while(move < popSize-1)
{
pick = (float)rand()/RAND_MAX; // 用于决定是否进行交叉操作
if(pick > croRate) //两条染色体是否相爱
{
move += 2;
continue; // 本次不进行交叉
}
// 采用部分映射杂交
choice1 = move; // 用于选取杂交的两个父代
choice2 = move+1; // 注意避免下标越界
pos1 = rand()%popSize;
pos2 = rand()%popSize;
while(pos1 > popSize -2 || pos1 < 1)//如果位置在开头或结尾(因为全部交换无意义)
{
pos1 = rand()%popSize;
}
while(pos2 > popSize -2 || pos2 < 1)
{
pos2 = rand()%popSize;
}
if(pos1 > pos2)
{
temp = pos1;
pos1 = pos2;
pos2 = temp; // 交换pos1和pos2的位置
}
for(int j = pos1;j <= pos2; j++)// 逐个交换顺序
{
temp = genes[choice1].cityArr[j];
genes[choice1].cityArr[j] = genes[choice2].cityArr[j];
genes[choice2].cityArr[j] = temp;
}
num1 = 0;
num2 = 0;
if(pos1 > 0 && pos2 < popSize - 1)//分三段
{
for(int j =0;j < pos1;j++)
{
for(int k = pos1; k <= pos2; k++)
{
if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k])
{
conflict1[num1] = j;
num1 ++;
}
if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k])
{
conflict2[num2] = j;
num2 ++;
}
}
}
for(j = pos2 + 1;j < popSize;j++)
{
for(int k = pos1; k <= pos2; k ++)
{
if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k])
{
conflict1[num1] = j;
num1 ++;
}
if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k])
{
conflict2[num2] = j;
num2 ++;
}
}
}
}
if((num1 == num2) && num1 > 0)
{
for(int j = 0;j < num1; j ++)
{
index1 = conflict1[j];
index2 = conflict2[j];
temp = genes[choice1].cityArr[index1]; // 交换冲突的位置
genes[choice1].cityArr[index1] = genes[choice2].cityArr[index2];
genes[choice2].cityArr[index2] = temp;
}
}
move += 2;
}
}
//变异操作
void mutation()
{
double pick;
int pos1,pos2,temp;
for(int i = 0;i < popSize; i ++)
{
pick = (float)rand()/RAND_MAX; // 用于判断是否进行变异操作
if(pick > mutRate)
{
continue;
}
pos1 = rand()%popSize;
pos2 = rand()%popSize;
while(pos1 > popSize - 1)
{
pos1 = rand()%popSize;
}
while(pos2 > popSize - 1)
{
pos2 = rand()%popSize;
}
int a = genes[i].dis;
temp = genes[i].cityArr[pos1];
genes[i].cityArr[pos1] = genes[i].cityArr[pos2];
genes[i].cityArr[pos2] = temp;
popFitness();//更新数据
//此步骤的作用在于检查是否变异后得到的个体比变异前更优秀了，如若往坏的方向变化了，那还不如不变异了
//（强制返回，虽然有点违背事物的客观发展规律，但为了增强程序的收敛性，该操作还是有必要的）（偷笑）
if(genes[i].dis > a)
{
temp = genes[i].cityArr[pos1];
genes[i].cityArr[pos1] = genes[i].cityArr[pos2];
genes[i].cityArr[pos2] = temp;
}
}
}
int main()
{
char c = 0;
printf("\n\t\t******************************** 遗传算法求解TSP(旅行商)问题 *********************************\n");
initGroup(); //初始化
popFitness(); //更新数据
//输出配置信息
printf("\n\t\t基因长度:%d",cityNum);
printf("\t种群大小:%d",popSize);
printf("\t交叉概率:%.2f",croRate);
printf("\t变异概率:%.2f",mutRate);
printf("\t进化代数:%d",MAX);
printf("\t预设最优解：18");
printf("\n\n\t\t**********************************************************************************************\n");
//输出距离矩阵
printf("\n\t\t--------- 城市距离矩阵 ---------\n");
printf("\t\t");
int i,j;
for(i = 0; i < cityNum; i ++)
{
for(j = 0;j < cityNum; j ++)
{
printf(" %d",distance[i][j]);
}
printf("\n\t\t");
}
printf("--------------------------------");
//输出路径信息
printf("\n\t\t-------- 初始种群基因库 --------\n");
printf("\t\t ");
for(i = 0; i < cityNum; i ++)
{
printf(" %c",genes[i].name);
}
printf("\n\t\t");
for(i = 0;i < cityNum; i ++)
{
printf("%c",genes[i].name);
for(j = 0; j < cityNum; j ++)
{
printf(" %d",genes[i].cityArr[j]);
}
printf("\n\t\t");
}
printf("--------------------------------\n");
do
{
printf("\n\t\t寻求最优解中：");
//通过不断进化，直到达到定义的进化代数
for(i = 0; i < MAX; i ++)
{
select();
cross();
mutation();
popFitness();//更新数据
int temp = (int)MAX/20;
if( i % temp == 0)
{
printf("▊");
Sleep(200);
}
}
printf("完成");
printf("\n\n\t\t最优路径：");
for(i = 0; i < cityNum ; i++)
{
printf("%d-->",genes[chooseBest()].cityArr[i]);
}
printf("%d",genes[chooseBest()].cityArr[0]);
printf("\n\n\t\t路径长度:%d",genes[chooseBest()].dis);
printf("\n\n\t\t是否再试一次?(Y/y) 是/(N/n) 否：");
fflush(stdin);
c = getchar();
fflush(stdin);
if(c=='N'||c=='n')
{
break;
}
}while(1);
printf("\n\t\t");
return 0;
}
