遗传算法实验报告
专业：自动化 姓名：** 学号：**
摘要：遗传算法，是基于达尔文进化理论发展起来的一种应用广泛、高效的随机搜索与优化方法。本实验利用遗传算法来实现求函数最大值的优化问题，其中的步骤包括初始化群体、个体评价、选择运算、交叉运算、变异运算、终止条件判断。该算法具有覆盖面大、减少进入局部最优解的风险、自主性等特点。此外，遗传算法不是采用确定性原则而是采用概率的变迁规则来指导搜索方向，具有动态自适应的优点。
关键词：串集 最优化评估 迭代 变异
一：实验目的
熟悉和掌握遗传算法的运行机制和求解的基本方法。
遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下：
（1）随机产生一个确定长度的特征字符串组成的初始种群。。
（2）对该字符春种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止：
a计算种群中每个个体字符串的适应值；
b应用复制、交叉和变异等遗传算子产生下一代种群。
（3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一
个解。
二：实验要求
已知函数y=f（x1,x2,x3,x4）=1/(x12+x22+x32+x42+1),其中-5≤x1,x2,x3,x4≤5,用遗传算法求y的最大值。
三：实验环境
操作系统：Microsoft Windows 7
软件：Microsoft Visual studio 2010
四：实验原理与步骤
1、遗传算法的思想
生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。
2、算法实现步骤
①、产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合；
②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值f，i=1,2,…,n,f越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度f为群体进化提供了依据；
③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中。此处选用轮盘算法，也就是比例选择算法，个体被选择的概率与其适应度成正比。
④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；此处采取生成随机数决定交叉的个体与交叉的位置。
⑤变异：以一定的概率Pm从群体P（t+1）中随机选择若干个个体，对于选中的个体随机选择某个位置，进行变异；
⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。
五：实验结果
实验结果的显示取决于判断算法终止的条件，这里可以有两种选择：1、在程序中设定迭代的次数；2在程序中设定适应值。本实验是在程序中实验者输入需要迭代的次数来判断程序终结的。
六：实验小结
在实验过程中，我觉得发现算子的选择对实验结果有一定程度的影响，所以除了采用PPT上的算子选取外，也同样尝试了其他的算子选择方法。
1、选择算子
①、排序选择方法。基于个体按适应度大小的排序来分配个体被选中的概率，这种算法与轮盘算法的思路差不多。
②、保存最佳个体策略。由于选择、交配、变异等操作的随机性，当代最优秀的个体可能会被破坏，所以可以采用保存当代最优秀的个体，参与到下一代的选择过程中。
不过总的来说，轮盘算法还是选取选择算子最有效、最常用的算法。
2、交叉算子
①、单点交叉。是指在个体编码串中随机设置一个交叉点，在该店交换配对的两条染色体上的基因。
②、两点交叉与多点交叉。在选择交叉算子的过程中，单点交叉是最简单的方法，又称简单交叉，两点甚至多点交叉，是交配两点之间的染色体，比单点交叉的适应性更高，不过程序略复杂。
本实验采用的是均匀交叉，在选定位置后每一位基因都以相同的概率进行交叉。
附上实验代码（visual studio 2010环境下运行）
#include＜iostream＞
#include＜ctime＞
#include＜iomanip＞
#include ＜algorithm＞
using namespace std;
int main()
{
srand(time(0));
double arr[5][4]; //初始化
cout＜＜"初始化："＜＜endl;
for(int i=0;i＜5;i++)
{
cout＜＜"C"＜＜i＜＜" ";
for(int j=0;j＜4;j++)
{
arr[i][j]=((-5000+rand()%100000)*0.0001);
cout＜＜setiosflags(ios::left)＜＜setw(8)＜＜arr[i][j]＜＜" ";
}
cout＜＜endl;
}
double result[5];double best_result; double result1[5]; //适应值计算
for(int i=0;i＜5;i++)
{
double sum=0;
for(int j=0;j＜4;j++)
sum+=arr[i][j]*arr[i][j];
result[i]=1/(sum+1);
}
for(int i=0;i＜5;i++)
result1[i]=result[i];
sort(result1,result1+5);
best_result=result1[4];cout＜＜"初始化后进行适应值计算，最大值best_result："＜＜best_result＜＜endl;
int n;cout＜＜"请输入需要迭代的次数：";cin＞＞n;int test_num=1;double test_result;
while(test_num＜=n)
{
cout＜＜"第"＜＜test_num＜＜"次迭代："＜＜endl;
double sum_result=0;double pecentage[5]; //选择
for(int i=0;i＜5;i++)
sum_result+=result[i];
for(int i=0;i＜5;i++)
{
pecentage[i]=result[i]/sum_result;
}
double a;double arr1[5][4];
for(int i=0;i＜5;i++)
for(int j=0;j＜5;j++)
arr1[i][j]=arr[i][j];
for(int i=0;i＜5;i++)
{
a=(rand()%100)*0.01;
if(a＜=pecentage[0])
for(int j=0;j＜4;j++)
arr[i][j]=arr1[0][j];
if(a＞pecentage[0]&&a＜=(pecentage[0]+pecentage[1]))
for(int j=0;j＜4;j++)
arr[i][j]=arr1[1][j];
if(a＞(pecentage[0]+pecentage[1])&&a＜=(pecentage[0]+pecentage[1]+pecentage[2]))
for(int j=0;j＜4;j++)
arr[i][j]=arr1[2][j];
if(a＞(pecentage[0]+pecentage[1]+pecentage[2])&&a＜=(pecentage[0]+pecentage[1]+pecentage[2]+pecentage[3]))
for(int j=0;j＜4;j++)
arr[i][j]=arr1[3][j];
if(a＞(pecentage[0]+pecentage[1]+pecentage[2]+pecentage[3])&&a＜=(pecentage[0]+pecentage[1]+pecentage[2]+pecentage[3]+pecentage[4]))
for(int j=0;j＜4;j++)
arr[i][j]=arr1[4][j];
}
double mating_pecentage=0.88;double mating[5];int num;double tend[4]={0}; //交配
for(int i=0;i＜5;i++)
{
mating[i]=(rand()%100)*0.01;
}
for(int i=0;i＜5;i++)
{
if(mating[i]＜=0.88)
{
for(int k=i+1;k＜5;k++)
{
if(mating[k]＜=0.88&&arr[i][0]!=arr[k][0])
{
num=rand()%3;
for(int l=num+1;l＜4;l++)
tend[l]=arr[i][l];
for(int m=num+1;m＜4;m++)
{
arr[i][m]=arr[k][m];
arr[k][m]=tend[m];
}
}
mating[k]=1;
break;
}
}
}
double variation[5][4]; //变异
for(int i=0;i＜5;i++)
{
for(int j=0;j＜4;j++)
variation[i][j]=(rand()%100)*0.01;
}
for(int i=0;i＜5;i++)
for(int j=0;j＜4;j++)
if(variation[i][j]＜0.1)
arr[i][j]=(-5000+rand()%10000)*0.0001;
cout＜＜"新群体："＜＜endl;
for(int i=0;i＜5;i++)
{
for(int j=0;j＜4;j++)
cout＜＜setiosflags(ios::left)＜＜setw(8)＜＜arr[i][j]＜＜" ";
cout＜＜endl;
}
for(int i=0;i＜5;i++) //重新评价
{
double sum=0;
for(int j=0;j＜4;j++)
sum+=arr[i][j]*arr[i][j];
result[i]=1/(sum+1);
}
for(int i=0;i＜5;i++)
result1[i]=result[i];
sort(result1,result1+5);
test_result=result1[4];if(test_result＞best_result)best_result=test_result;
cout＜＜"适应值计算，更新best_result："＜＜best_result＜＜endl;
test_num++;
}
system("pause");
return 0;
}