3142人阅读
智能信息处理（3）
一、实验目的
1.掌握遗传算法的基本原理和步骤。
2.&复习VB、VC的基本概念、基本语法和编程方法，并熟练使用VB或VC编写遗传算法程序。
二、实验内容
1.&上机编写程序，解决以下函数优化问题：
2.&调试程序。
3.&根据实验结果，撰写实验报告。
三、实验原理
遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。
标准遗传算法流程图如下图所示，主要步骤可描述如下：
①&随机产生一组初始个体构成初始种群。
②&计算每一个体的适配值（，也称为适应度）。适应度值是对染色体个体进行评价的一种指标，是进行优化所用的主要信息，它与个体的目标值存在一种对应关系。
③&判断算法收敛准则是否满足，若满足，则输出搜索结果；否则执行以下步骤。
④&根据适应度值大小以一定方式执行复制操作（也称为选择操作）。
⑤&按交叉概率pc执行交叉操作。
⑥&按变异概率pm执行变异操作。
⑦&返回步骤②。
图1.1&标准遗传算法流程图
代码实现：：：：：：
#include &stdio.h&
#include &math.h&
#include &stdlib.h&
#include&time.h&
#define byte unsigned char
#define step 200 //步长
#define MAX 50
#define N 10 //随机数个数
#define Pc 0.74
//被选择到下一代的概率,个数=Pc*N，小于N
下一代数=上一代，不用处理
#define Pt 0.25
//交叉的概率,个数=Pt*N 舍，小于N
0~(n2+1)随机数，之后部分开始交叉
#define Pm 0.01
//变异的概率,个数=Pm*N*n2 入，小于N
0~(N*(n2+1))随机数/(n2+1)=个体,0~(N*(n2+1))随机数%(n2+1)=该个体基因位置
#define n2 15//2的15次方,共16位
#define next_t (int)(Pt*N)//交叉个数
#define next_m (int)(Pm*N+1)//变异个数
向后约等于
#define e 0.001//次数限制阈值
int N=10; //随机数个数
float Pc=0.74;
//被选择到下一代的概率,个数=Pc*N，小于N
下一代数=上一代，不用处理
float Pt=0.25;
//交叉的概率,个数=Pt*N 舍，小于N
0~(n2+1)随机数，之后部分开始交叉
float Pm=0.01;
//变异的概率,个数=Pm*N*n2 入，小于N
0~(N*(n2+1))随机数/(n2+1)=个体,0~(N*(n2+1))随机数%(n2+1)=该个体基因位置
bitary[N][n2+1],bitary0[N][n2+1];//二进制
int src1[N];
float ShowType(int a);//表现型
void BinNum(int a);//二进制位数n2
float fit_func(float a);//适应度
void DecToBin (int src,int num);//十进制转二进制
void BinToDec (void);//十进制转二进制
int selectT(float a,float b[10]);//选择交叉个体
int selectM(float a,float b[10]);//选择变异个体
void main(void)
//范围是[-100,100]***************************
src[N],i=0,j=0,k=0,count=0;//十进制
float show[N];//表现型
float fit[N],sumfit=0;//适应度
float pcopy[N];//优胜劣汰，遗传到下一代的概率fit[i]/总和(fit[i])
float pacc[N];//pcopy[i]累加概率值
float prand[N];//随机产生N个0~1的下一代概率
//根据概率选择到的个体序号
int new_select[N];//根据概率选择到的个体
int new_T[next_t],new_M[next_m];
float min,min1;
printf(&随机数(原始母体),表现型, 适配值\n&);
srand( (unsigned)time(NULL) );
for(i=0;i&N;i++)
src[i]=rand()%32768; //rand()%201-100===&-100~100的十进制随机数 随时间递增
show[i]=ShowType(src[i]);//转化成表现型
fit[i]=fit_func(show[i]);//计算各个适配值(适应度)
sumfit=sumfit+fit[i];
//种群的适应度总和
printf(&%5d,
%f\n&,src[i],show[i],fit[i]);
printf(&\n第%d代适配总值\n%f\n&,count,sumfit);//第0代
printf(&\n遗传到下一代的概率\n&);
for(i=0;i&N;i++)
pcopy[i]=fit[i]/
printf(&%f, &,pcopy[i]);
// 求选择(被复制)的累加概率,用于轮盘赌产生随机数区域，选择下一代个体
printf(&\n遗传到下一代的累加概率\n&);
pacc[0]=pcopy[0];
for(i=1;i&N;i++)
pacc[i]=pacc[i-1]+pcopy[i];
printf(&%f, &,pacc[i]);
//每个src[N]都随机取其中一个pcopy，取得的值pcopy[i]跟pcopy概率大小有关
//模拟轮盘赌方式选择新一代
printf(&\n\n新产生的第%d代,表现型, 适配值\n&,count);
srand( (unsigned)time(NULL) );
for(i=0;i&N;i++)
prand[i]=(float)( (rand()%101)*0.01 );//0~1的十进制小数 ，精确到0.01
iselect=selectT(prand[i],pacc);
new_select[i]=src[iselect];//产生的新一代,十进制
show[i]=ShowType(new_select[i]);//转化成表现型
fit[i]=fit_func(show[i]);
DecToBin (new_select[i],i);
sumfit=sumfit+fit[i];
//种群的适应度总和
printf(& %d
%f\n&,new_select[i],show[i],fit[i]);
printf(&\n第%d代适配总值\n%f\n&,count,sumfit);//第1代
if (min&sumfit)
while(fabs(min-min1)&e&&count&MAX)
//从新一代选择个体交叉
printf(&\n随机产生交叉个体号
srand( (unsigned)time(NULL) );
for(i=0;i&2;i++)
//简单起见交叉数设为2
new_T[i]=rand()%N;//0~10的十进制数 产生的交叉个体
if (i&0)//两个不同个体交叉
while(new_T[i]==new_T[i-1])
new_T[i]=rand()%N;
printf(&%d,
&,new_T[i]);
srand( (unsigned)time(NULL) );//随机产生交叉位置
k=rand()%n2;//0~14的十进制数
printf(&\n随机产生交叉位置
printf(&\n原编码\n&);
for(j=n2;j&=0;j--)
printf(&%c&,bitary[new_T[0]][j]);
printf(&\n&);
for(j=n2;j&=0;j--)
printf(&%c&,bitary[new_T[1]][j]);
printf(&\n位置%d后交叉编码\n&,k);
for(i=k+1;i&n2+1;i++)//交叉
temp=bitary[new_T[0]][i];
bitary[new_T[0]][i]=bitary[new_T[1]][i];
bitary[new_T[1]][i]=
for(j=n2;j&=0;j--)
printf(&%c&,bitary[new_T[0]][j]);
printf(&\n&);
for(j=n2;j&=0;j--)
printf(&%c&,bitary[new_T[1]][j]);
//从新一代选择个体变异
printf(&\n随机产生变异个体号
srand( (unsigned)time(NULL) );
for(i=0;i&1;i++)
//简单起见变异数设为1个
new_M[i]=rand()%N;//0~9的十进制数 产生的变异个体
k=rand()%(n2+1);//0~15的十进制数
printf(&%d\n编码位置
%d\n原编码\n&,new_M[i],k);
for(j=n2;j&=0;j--)
printf(&%c&,bitary[new_M[i]][j]);
if (bitary[new_M[i]][k]=='0')//变异取反
bitary[new_M[i]][k]='1';
else bitary[new_M[i]][k]='0';
printf(&\n位置%d变异后编码\n&,k);
for(j=n2;j&=0;j--)
printf(&%c&,bitary[new_M[i]][j]);
printf(&\n&);
//新的bitary即产生第二代
printf(&\n新产生的第%d代\n&,count);
for(i=0;i&N;i++)
for(j=n2;j&=0;j--)
printf(&%c&,bitary[i][j]);
printf(&\n&);
BinToDec ();//二进制转十进制
for(i=0;i&N;i++)
new_select[i]=src1[i];
show[i]=ShowType(src[i]);//转化成表现型
fit[i]=fit_func(show[i]);//计算各个适配值(适应度)
sumfit=sumfit+fit[i];
//种群的适应度总和
printf(&%5d,
%f\n&,src1[i],show[i],fit[i]);
printf(&\n第%d代适配总值\n%f\n&,count,sumfit);
if (sumfit&min)
printf(&\n\n\n*****************\n
\n*****************\n&,sumfit);
//////////////////////////子函数////////////////
float ShowType(int a)
temp=(float)(a*200.0/);//(2的15次方减1)=32767
float fit_func(float a)
void DecToBin (int src,int num)
//注意负数的补码
if (src&0)
src=(int)pow(2,16)-abs(src);
for (i=0;i&=n2;i++)
bitary[num][i]='0';
bitary0[num][i]='0';
bitary[num][i]=(src%2)+48;
bitary0[num][i]=(src%2)+48;
src=(int)(src/2);
void BinToDec (void)
for(i=0;i&N;i++)
src1[i]=0;
for(j=0;j&n2+1;j++)
src1[i]=src1[i]+(bitary[i][j]-48)*(int)pow(2,j);
int selectT(float a,float b[10])
for(i=0;i&N;i++)
if (a&b[i])
return -1;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：41352次
排名：千里之外
原创：21篇
转载：11篇
(4)(1)(1)(3)(5)(11)(1)(6)遗传算法在函数优化中的应用_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
遗传算法在函数优化中的应用
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩16页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢遗传算法求解函数优化问题的Matlab实现_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
遗传算法求解函数优化问题的Matlab实现
上传于|0|0|文档简介
&&关于MATLAB的 ,对数模有帮助
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩1页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢遗传算法求解函数优化问题的比较_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
遗传算法求解函数优化问题的比较
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用3下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩8页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢最优化问题求解之：遗传算法
遗传算法的手工模拟计算示例
为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各
个主要执行步骤。
例：求下述二元函数的最大值：
(1) 个体编码
&&&&&&&&&&
遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种
符号串。本题中，用无符号二进制整数来表示。
&&&&&&&&&&
因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它
们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可
&&&&&&&&&&
例如，基因型 X＝101110 所对应的表现型是：x＝[ 5，6 ]。
&&&&&&&&&&
个体的表现型x和基因型X之间可通过编码和解码程序相互转换。
(2) 初始群体的产生
遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始
群体数据。
本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机
方法产生。
如：，111001
&(3) 适应度汁算
遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传
机会的大小。
本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接
利用目标函数值作为个体的适应度。
选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代
群体中。&&&&&&&&&&&&&&&&&&&
本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中
的数量。其具体操作过程是：
&& 先计算出群体中所有个体的适应度的总和&
fi& ( i=1.2,…,M );
&& 其次计算出每个个体的相对适应度的大小 fi / fi ，它即为每个个体被遗传
&&&&&&&&&&&&
到下一代群体中的概率，
&& 每个概率值组成一个区域，全部概率值之和为1；
&& 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区
&&&&&&&&&&&&
域内来确定各个个体被选中的次数。
交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某
两个个体之间的部分染色体。
本例采用单点交叉的方法，其具体操作过程是：
& 先对群体进行随机配对；
& 其次随机设置交叉点位置；
& 最后再相互交换配对染色体之间的部分基因。
变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进
行改变，它也是产生新个体的一种操作方法。
本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：
& 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，
其中的数字表示变异点设置在该基因座处；
& 然后依照某一概率将变异点的原有基因值取反。
对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。
从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得
到了明显的改进。事实上，这里已经找到了最佳个体“111111”。&&&&&&&
[注意]&&&&&&
需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，
我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中
&& 有可能需要一定的循环次数才能达到这个最优结果。
----------------------------------------------------------------------------
遗传算法属于进化算法( Evolutionary
Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解.
遗传算法有三个基本算子:选择、交叉和变异.
。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。
生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法（GA）。算法中称遗传的生物体为个体（individual），个体对环境的适应程度用适应值（fitness）表示。适应值取决于个体的染色体（chromosome），在算法中染色体常用一串数字表示，数字串中的一位对应一个基因（gene）。一定数量的个体组成一个群体（population）。对所有个体进行选择、交叉和变异等操作，生成新的群体，称为新一代（new
generation）。
遗传算法计算程序的流程可以表示如下[3]：
第一步 准备工作
（1）选择合适的编码方案，将变量（特征）转换为染色体（数字串，串长为m）。通常用二进制编码。
（2）选择合适的参数，包括群体大小（个体数M）、交叉概率PC和变异概率Pm。
（3）确定适应值函数f（x）。f（x）应为正值。
形成一个初始群体（含M个个体）。在边坡滑裂面搜索问题中，取已分析的可能滑裂面组作为初始群体。
第三步 对每一染色体（串）计算其适应值fi，同时计算群体的总适应值
第四步 选择
计算每一串的选择概率Pi=fi/F及累计概率。选择一般通过模拟旋转滚花轮（roulette，其上按Pi大小分成大小不等的扇形区）的算法进行。旋转M次即可选出M个串来。在计算机上实现的步骤是：产生[0，1]间随机数r，若r
第五步 交叉
（1）对每串产生[0，1]间随机数，若r&pc，则该串参加交叉操作，如此选出参加交叉的一组后，随机配对。
对每一对，产生[1，m]间的随机数以确定交叉的位置。
第六步 变异
如变异概率为Pm，则可能变异的位数的期望值为Pm
&m&M，每一位以等概率变异。具体为对每一串中的每一位产生[0，1]间的随机数r，若r
如新个体数达到M个，则已形成一个新群体，转向第三步；否则转向第四步继续遗传操作。直到找到使适应值最大的个体或达到最大进化代数为止。
由于选择概率是由适应值决定的，即适应值大的染色体入选概率也较大，使选择起到"择优汰劣"的作用。交叉使染色体交换信息，结合选择规则，使优秀信息得以保存，不良信息被遗弃。变异是基因中得某一位发生突变，以达到产生确实有实质性差异的新品种。遗传算法虽是一种随机算法，但它是有导向的，它所使用的"按概率随机选择"方法是在有方向的搜索方法中的一种工具。正是这种独特的搜索方法，使遗传算法自然地避开了其它最优化算法常遇到的局部最小陷阱。
遗传算法与传统的优化方法（枚举，启发式等）相比较，以生物进化为原型，具有很好的收敛性，在计算精度要求时，计算时间少，鲁棒性高等都是它的优点。
遗传算法的优点：
1. 与问题领域无关切快速随机的搜索能力。
搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，robust.
3. 搜索使用评价函数启发，过程简单
4. 使用概率机制进行迭代，具有随机性。
5. 具有可扩展性，容易与其他算法结合。
遗传算法的缺点：&
&1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,
&2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.
3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精确的解需要较多的训练时间。
4、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。
5、算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。
在现在的工作中，遗传算法（1972年提出）已经不能很好的解决大规模计算量问题，它很容易陷入“早熟”。常用混合遗传算法，合作型协同进化算法等来替代，这些算法都是GA的衍生算法。
遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索出，而不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以方便地进行分布式计算，加快求解速度。但是遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低。在实际应用中，遗传算法容易产生早熟收敛的问题。采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。
模拟退火算法虽具有摆脱局部最优解的能力，能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。但是，由于模拟退火算法对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，使得模拟退火算法的运算效率不高。模拟退火算法对参数（如初始温度）的依赖性较强，且进化速度慢。
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。