| 遗传算法（附简单案例及matlab详细代码） | 您所在的位置：网站首页 › 遗传算法tsp问题给路径编码 › 遗传算法（附简单案例及matlab详细代码） |
遗传算法（附简单案例及matlab详细代码）
|
作者：非妃是公主 专栏：《智能优化算法》 博客地址：https://blog.csdn.net/myf_666 个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩 遗传算法也是一种效果很棒的智能优化算法，它主要借鉴了自然界中生物进化的思想，采用优胜劣汰的策略，利用选择、交叉、变异三个过程，对解进行不断的迭代，最终趋向于最优解。 一、生物进化谈到遗传算法，不得不谈生物进化，因为遗传算法就是模仿生物繁殖后代的思想演变而来的，可以说是一种仿生学的算法。 自然选择学说认为，适者生存，生物想要存活下去，就必须进行生存斗争。生存斗争包括种内、种间以及生物和环境之间的斗争三个方面。 在斗争过程中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传递给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也就少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。1 二、遗传算法原理而遗传算法就是借鉴了上述生物进化中的优化策略，对一个目标问题进行优化的。 具体地说，它将问题的解抽象成一个编码，许多个编码构成了一个种群，每个编码都对应得到目标问题的一个解，其中根据可行解的目标函数值的不同，定义这个个体的强弱。越强的个体越容易生存下来（选择），进行后代的繁衍（交叉、变异），越弱的个体就优先被淘汰。 生物进化中的术语遗传算法中的术语群体可行解集个体可行解染色体可行解的编码基因可行解编码中的一位（1个bit）适应度评价函数值（越高，代表解越好）选择选择操作（比如根据概率进行轮盘赌选择可行解）交叉交叉操作（编码的单点交叉、多点交叉）变异变异操作（编码的按位取反） 三、遗传算法的优点 以决策变量的编码作为运算对象。这种编码的方式对于计算机来求解十分方便，具有独特的优越性。遗传算法以目标函数值作为搜索信息，避免了求导。在很多问题中，求导是无法做到的或者很困难做到的。选择、交叉、变异操作包括了很多群体信息。这些信息避免搜索了许多的点，相当于具有一种隐含的并行性。遗传算法基于概率。随着过程的进化，参数对搜索结果的影响很小很小。具有自组织、自适应、自学习等特性。 四、算法具体流程 1. 整体流程 初始化；个体评价；选择运算；交叉运算；变异运算；终止条件判断。流程图如下： no yes 初始化种群 适应度评价 是否结束 选择运算 交叉运算 变异运算 结束 2. 细节处理 Ⅰ. 群体规模 N P NP NP群体规模影响遗传优化的最终结果以及遗传算法的执行效率。一般 NP取10～200。 N P NP NP 太小时，遗传优化效果（相比于最优解准确度）一般不会太好。较大的群体规模可以减小陷入局部最优解的概率，但意味着较大的计算复杂度。 Ⅱ. 交叉概率 P c P_c Pc交叉概率 P c P_c Pc控制着交叉操作的频率，较大的频率可以曾倩遗传算法开辟新的搜索区域的能力。 如果太大，容易生成不好的后代，收敛性差；如果太小，搜索能力差。 Ⅲ. 变异概率 P m P_m Pm保持群体多样性。一般去0.001~0.1 太大，容易陷入随机搜索，导致重要基因丢失。太小，没有效果。 3. 遗传运算终止代数 G G G一般视具体问题而定，取值可在 100~1000 之间。 太大，浪费算力，种群衰退。太小，优化过程没有收敛。 五、仿真实例：求解函数最大值 1. 题目用标准遗传算法求函数 f ( x ) = x + 10 s i n ( 5 x + 7 c o s ( 4 x ) f( x ) =x+10sin(5x +7cos(4x) f(x)=x+10sin(5x+7cos(4x)的最大值，其中的取值范围为 [ 0 ， 10 ] [0，10] [0，10]。 2. 分析通过matlab作图可知，该函数存在多个局部极值，如下图所示： matlab求解代码如下，其中主要思路及较为复杂的点，已在注释中说明。 %%%%%%%%%%%%%%%%%%%%标准遗传算法求函数极值%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%初始化参数%%%%%%%%%%%%%%%%%%%%%%%%%% clear all; %清除所有变量 close all; %清图 clc; %清屏 NP=50; %种群数量 L=20; %二进制数串长度 Pc=0.8; %交叉率 Pm=0.1; %变异率 G=100; %最大遗传代数 Xs=10; %上限 Xx=0; %下限 f=randi([0,1],NP,L); %随机获得初始种群 finalMax=0; finalXBest=0; %%%%%%%%%%%%%%%%%%%%%%%%%遗传算法循环%%%%%%%%%%%%%%%%%%%%%%%% for k=1:G % 跌代的总代数 %%%%%%%%%%%%将二进制解码为定义域范围内十进制%%%%%%%%%%%%%% for i=1:NP % 遍历所有个体 U=f(i,:); % 将第 i 个个体读取出来 m=0; % 存储的二进制对应的十进制数字 for j=1:L % 按位把二进制转化为十进制 m=U(j)*2^(j-1)+m; end x(i)=Xx+m*(Xs-Xx)/(2^L-1); % 把十进制数字m转换到对应的定义域内 Fit(i)= func1(x(i)); % 计算适应度函数 end maxFit=max(Fit); %最大值 minFit=min(Fit); %最小值 rr=find(Fit==maxFit); %找出最优个体的下标索引 fBest=f(rr(1,1),:); %当代最优个体的二进制编码 xBest=x(rr(1,1)); %当代最优个体对应的十进制值 if maxFit>finalMax finalMax=maxFit; finalXBest=xBest; end Fit=(Fit-minFit)/(maxFit-minFit); %归一化适应度值 %%%%%%%%%%%%%%%%%%基于轮盘赌的选择操作%%%%%%%%%%%%%%%%%%% sum_Fit=sum(Fit); %对所有个体的适应度进行一个求和 fitvalue=Fit./sum_Fit; %让所有个体加起来适应度值为1，便于进行概率计算 fitvalue=cumsum(fitvalue); %consum是累加当前索引及以前的索引对应的值，比如[1 2 3]，consume后返回[1 3 6] ms=sort(rand(NP,1)); %生成一个NP * 1的向量，并从小到大排序，轮盘赌的关键操作。（均匀分布） fiti=1; newi=1; while newi |
【本文地址】