《人工智能及其应用大作业（一）》
题 目： 学 号： 姓 名： 基本遗传算法及其在函数优化中的作用
基本遗传算法及其在函数优化中的应用
摘要：
从遗传算法的编码、遗传算子等方面剖析了遗传算法求解无约束函数优化问题的一般步骤, 并以一个实例说明遗传算法能有效地解决函数优化问题。本文利用基本遗传算法求解函数优化问题，选用 f(x)=xsin(10
πx)+2.0，取值范围在[ 1, 2]中，利用基本遗传算法求解两个函数的最优值，遗传算法每次100代，一共
执行10次，根据运算结果分析得到最优解。 关键字：遗传算法 选择 交叉 变异 函数优化
1. 前言
1.1基本概念
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传
机制）演化而来的随机化搜索方法。遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。
选择（Selection ）、交叉（Crossover ）和变异（Mutation ）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（genetic operation），使遗传算法具有了其它传统方法所没有的特性。
1.2 遗传算法的特点
其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。 1.3遗传算法的应用
函数优化，组合优化，机器人智能控制，及组合图像处理和模式识别等。
2. 基本遗传算法
2.1简单遗传算法的求解步骤
Step1：参数设置及种群初始化； Step2：适应度评价； Step3：选择操作； Step4：交叉操作； Step5：变异操作；
Step6：终止条件判断，若未达到终止条件，则转到Step3； Step7：输出结果。
2.2停机准则
（1）完成了预先给定的进化代数则停止；
（2）群体中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。
2.3基本遗传算法框图
3. 实验与结果
本小节采用以下函数： f(x)=xsin(10πx)+2.0，x [-1,2] 3.1编码 表现型：x
基因型：二进制编码（串长取决于求解精度）
按编码原理：假设要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为
3/0.000001=3×106等份。
所以编码的二进制串长应为22位。 3.2产生初始种群 产生的方式：随机
产生的结果：长度为22的二进制串
产生的数量：种群的大小（规模），如30，50，… [***********]1000 [***********]1110 [***********]0100 [***********]1001 [***********]0011 [***********]0000 ... 3.3计算适应度
直接用目标函数作为适应度函数
①解码：将个体s 转化为[-1,2]区间的实数： s= → x=0.637197 ②计算x 的函数值（适应度）： f(x)=xsin(10πx)+2.0=2.586345 3.4遗传操作
选择：比例选择法； 交叉：单点交叉； 变异：小概率变异 3.5模拟结果 设置的参数：
种群大小80；交叉概率0.75；变异概率0.05；最大代数100。 运行结果如下表：
由上表可以分析得出的最优解为x=1.8，最大值为3.85。
4. 结论
遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。
选择的过程很重要，决定着最终结果和收敛速度等。
对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉律和变异律。
遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。
参考文献：
（1）蔡自兴，徐光祐《人工智能及其应用》
（2）马永，贾俊芳. 遗传算法研究综述. 第23卷. 第三期.2007年12月；
附录： 1. 代码
主函数:
clear clc
my_scale=50; %种群规模 gen_len=22; %基因长度 M=100; %迭代次数 pc=0.75; %交叉概率 pm=0.05; %变异概率
new_scale=produscale(my_scale,gen_len); %产生初始种群 fitfit=[]; fittimer=[]; best_f1=[]; best_x1=[]; for i=1:M
my_f=cal_my_f(new_scale); %计算函数值 my_fit=cal_my_fit(my_f); %计算适应度值
next_scale=my_sellect(new_scale,my_fit); %采用赌轮盘法选择 cross_scale=my_cross(next_scale,pc); %按概率交叉 mut_scale=my_mutat(cross_scale,pm); %按概率变异
%寻找每一代中的最优适应度值所对应的个体 best_fit=my_fit(1); [sx,sy]=size(new_scale); for j=2:length(my_fit) if best_fit
best_x=my2to10(new_scale(j,:)); best_x=-2+best_x.*4./(2^sy-1); end end
new_scale=mut_scale;
fitfit=[fitfit,best_fit]; best_f1=[best_f1,best_f]; best_x1=[best_x1,best_x]; fittimer=[fittimer,i]; end
[best_fit,loca]=max(fitfit); best_f=best_f1(loca); best_x=best_x1(loca);
disp('[best_fit,best_f,best_x]=') disp([best_fit,best_f,best_x]) subplot(2,2,1)
plot(fittimer,fitfit) xlabel(' 迭代次数(1)-wxb'); ylabel(' 适应度函数' ) grid on
%子函数：产生初始种群
function initscale=produscale(my_scale,gen_len) initscale=round(rand(my_scale,gen_len)); end
%子函数：计算函数值
function my_f=cal_my_f(new_scale) mychange=my2to10(new_scale); [sx,sy]=size(new_scale);
change_x=-1+mychange.*3./(2^sy-1);
my_f=change_x*sin(10π*change_x)+2;
end
%子函数：计算适应度值
function my_fit=cal_my_fit(my_f) f_min=5;
for i=1:length(my_f) if my_f(i)+f_min
my_fit(i)=my_f(i)+f_min; end end
my_fit=my_fit'; end
%子函数：采用赌轮盘法选择
function next_scale=my_sellect(new_scale,my_fit) sum_of_f=sum(my_fit); accum=my_fit/sum_of_f; accum=cumsum(accum); [sx,sy]=size(new_scale); j=1; while j=a
next_scale(j,:)=new_scale(1,:); else if accum(i)=a next_scale(j,:)=new_scale(i+1,:); j=j+1; end end end end end
%子函数：按概率交叉
function cross_scale=my_cross(new_scale,pc) [sx,sy]=size(new_scale); cross_scale=new_scale; for i=1:2:sx-1 if rand
a=round(rand*sy);
cross_scale(i,:)=[new_scale(i,1:a),new_scale(i+1,a+1:end)]; cross_scale(i+1,:)=[new_scale(i+1,1:a),new_scale(i,a+1:end)]; end end
%子函数：按概率变异
function mut_scale=my_mutat(new_scale,pm) [sx,sy]=size(new_scale); mut_scale=new_scale; for i=1:sx if rand
a=round(rand*sy); if a
a=1; end
if mut_scale(i,a)==0 mut_scale(i,a)=1; else
mut_scale(i,a)=0; end end end
%子函数：2进制转10进制
function mychange=my2to10(new_scale) [sx,sy]=size(new_scale); new_scale1=new_scale; for i=1:sy
new_scale1(:,i)=2.^(sy-i).*new_scale(:,i); end
mychange=sum(new_scale1,2); end
2. 实验结果截图
《人工智能及其应用大作业（一）》
题 目： 学 号： 姓 名： 基本遗传算法及其在函数优化中的作用
基本遗传算法及其在函数优化中的应用
摘要：
从遗传算法的编码、遗传算子等方面剖析了遗传算法求解无约束函数优化问题的一般步骤, 并以一个实例说明遗传算法能有效地解决函数优化问题。本文利用基本遗传算法求解函数优化问题，选用 f(x)=xsin(10
πx)+2.0，取值范围在[ 1, 2]中，利用基本遗传算法求解两个函数的最优值，遗传算法每次100代，一共
执行10次，根据运算结果分析得到最优解。 关键字：遗传算法 选择 交叉 变异 函数优化
1. 前言
1.1基本概念
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传
机制）演化而来的随机化搜索方法。遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。
选择（Selection ）、交叉（Crossover ）和变异（Mutation ）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（genetic operation），使遗传算法具有了其它传统方法所没有的特性。
1.2 遗传算法的特点
其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。 1.3遗传算法的应用
函数优化，组合优化，机器人智能控制，及组合图像处理和模式识别等。
2. 基本遗传算法
2.1简单遗传算法的求解步骤
Step1：参数设置及种群初始化； Step2：适应度评价； Step3：选择操作； Step4：交叉操作； Step5：变异操作；
Step6：终止条件判断，若未达到终止条件，则转到Step3； Step7：输出结果。
2.2停机准则
（1）完成了预先给定的进化代数则停止；
（2）群体中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。
2.3基本遗传算法框图
3. 实验与结果
本小节采用以下函数： f(x)=xsin(10πx)+2.0，x [-1,2] 3.1编码 表现型：x
基因型：二进制编码（串长取决于求解精度）
按编码原理：假设要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为
3/0.000001=3×106等份。
所以编码的二进制串长应为22位。 3.2产生初始种群 产生的方式：随机
产生的结果：长度为22的二进制串
产生的数量：种群的大小（规模），如30，50，… [***********]1000 [***********]1110 [***********]0100 [***********]1001 [***********]0011 [***********]0000 ... 3.3计算适应度
直接用目标函数作为适应度函数
①解码：将个体s 转化为[-1,2]区间的实数： s= → x=0.637197 ②计算x 的函数值（适应度）： f(x)=xsin(10πx)+2.0=2.586345 3.4遗传操作
选择：比例选择法； 交叉：单点交叉； 变异：小概率变异 3.5模拟结果 设置的参数：
种群大小80；交叉概率0.75；变异概率0.05；最大代数100。 运行结果如下表：
由上表可以分析得出的最优解为x=1.8，最大值为3.85。
4. 结论
遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。
选择的过程很重要，决定着最终结果和收敛速度等。
对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉律和变异律。
遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。
参考文献：
（1）蔡自兴，徐光祐《人工智能及其应用》
（2）马永，贾俊芳. 遗传算法研究综述. 第23卷. 第三期.2007年12月；
附录： 1. 代码
主函数:
clear clc
my_scale=50; %种群规模 gen_len=22; %基因长度 M=100; %迭代次数 pc=0.75; %交叉概率 pm=0.05; %变异概率
new_scale=produscale(my_scale,gen_len); %产生初始种群 fitfit=[]; fittimer=[]; best_f1=[]; best_x1=[]; for i=1:M
my_f=cal_my_f(new_scale); %计算函数值 my_fit=cal_my_fit(my_f); %计算适应度值
next_scale=my_sellect(new_scale,my_fit); %采用赌轮盘法选择 cross_scale=my_cross(next_scale,pc); %按概率交叉 mut_scale=my_mutat(cross_scale,pm); %按概率变异
%寻找每一代中的最优适应度值所对应的个体 best_fit=my_fit(1); [sx,sy]=size(new_scale); for j=2:length(my_fit) if best_fit
best_x=my2to10(new_scale(j,:)); best_x=-2+best_x.*4./(2^sy-1); end end
new_scale=mut_scale;
fitfit=[fitfit,best_fit]; best_f1=[best_f1,best_f]; best_x1=[best_x1,best_x]; fittimer=[fittimer,i]; end
[best_fit,loca]=max(fitfit); best_f=best_f1(loca); best_x=best_x1(loca);
disp('[best_fit,best_f,best_x]=') disp([best_fit,best_f,best_x]) subplot(2,2,1)
plot(fittimer,fitfit) xlabel(' 迭代次数(1)-wxb'); ylabel(' 适应度函数' ) grid on
%子函数：产生初始种群
function initscale=produscale(my_scale,gen_len) initscale=round(rand(my_scale,gen_len)); end
%子函数：计算函数值
function my_f=cal_my_f(new_scale) mychange=my2to10(new_scale); [sx,sy]=size(new_scale);
change_x=-1+mychange.*3./(2^sy-1);
my_f=change_x*sin(10π*change_x)+2;
end
%子函数：计算适应度值
function my_fit=cal_my_fit(my_f) f_min=5;
for i=1:length(my_f) if my_f(i)+f_min
my_fit(i)=my_f(i)+f_min; end end
my_fit=my_fit'; end
%子函数：采用赌轮盘法选择
function next_scale=my_sellect(new_scale,my_fit) sum_of_f=sum(my_fit); accum=my_fit/sum_of_f; accum=cumsum(accum); [sx,sy]=size(new_scale); j=1; while j=a
next_scale(j,:)=new_scale(1,:); else if accum(i)=a next_scale(j,:)=new_scale(i+1,:); j=j+1; end end end end end
%子函数：按概率交叉
function cross_scale=my_cross(new_scale,pc) [sx,sy]=size(new_scale); cross_scale=new_scale; for i=1:2:sx-1 if rand
a=round(rand*sy);
cross_scale(i,:)=[new_scale(i,1:a),new_scale(i+1,a+1:end)]; cross_scale(i+1,:)=[new_scale(i+1,1:a),new_scale(i,a+1:end)]; end end
%子函数：按概率变异
function mut_scale=my_mutat(new_scale,pm) [sx,sy]=size(new_scale); mut_scale=new_scale; for i=1:sx if rand
a=round(rand*sy); if a
a=1; end
if mut_scale(i,a)==0 mut_scale(i,a)=1; else
mut_scale(i,a)=0; end end end
%子函数：2进制转10进制
function mychange=my2to10(new_scale) [sx,sy]=size(new_scale); new_scale1=new_scale; for i=1:sy
new_scale1(:,i)=2.^(sy-i).*new_scale(:,i); end
mychange=sum(new_scale1,2); end
2. 实验结果截图