遗传算法原理及算法实例

遗传算法原理解析

遗传算法，作为进化算法家族中的一员，是一种基于自然选择的元启发式过程。它主要通过借鉴生物进化中的变异、交叉和选择等启发式算子，来构建针对优化和搜索问题的有效解决方案。

参考生物进化的原理，遗传算法将问题比作一个生物的进化历程，通过遗传、杂交、变异以及自然选择等步骤来生成新的解决方案，同时不断淘汰那些适应度低的解，并提升那些适应度高的解。经过如此循环进化N次之后，很可能会培育出具有极高适应度值的个体。

与遗传算法紧密相连的生物学术语包括：染色体，即生物细胞中的遗传物质载体。

生物由细胞构成，每个细胞内都含有相同的染色体组。这些染色体由众多基因构成，每个基因负责调控一种特定蛋白质的合成，进而影响生物的特定性状。所有这些染色体的总和被称为基因组，它全面决定了生物个体的特性。该个体在微观层面，其基因构成被称为基因型，而在宏观层面，其外在特征则表现为显型。在遗传算法的简单模型中，基因组内的数条染色体被视为一条单一的染色体。

（2） 个体复制

在复制过程中，父母的遗传物质会通过交叉互换的方式形成子女的遗传信息。此外，染色体还可能在极小的几率下发生变异。

遗传算法本质上是一种搜索算法，搜索算法的共同特征为：

首先组成一组候选解

依据某些适应性条件测算这些候选解的适应度

根据适应度保留某些候选解，放弃其他候选解

对保留的候选解进行某些操作，生成新的候选解

交叉现象，即两条染色体相互交换部分遗传信息，以此为基础开yun体育app入口登录，生成下一代的两条全新染色体。

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

染色体交叉是以一定的概率发生的，这个概率记为Pc 。

变异现象：在生物繁殖的过程中，新形成的染色体上携带的基因有可能以某种几率出现错误，这种现象被称为变异。这种变异发生的几率可以用符号Pm来表示。

变异前：

000001110000000010000

变异后：

000001110000100010000

适应度函数，它是用来衡量一个染色体的适应能力的，通常用f(x)来表示。在特定情况下，我们还需区分染色体的适应度函数和问题的目标函数。比如，在0-1背包问题中，目标函数是所选取物品的总价值，但将物品价值作为染色体的适应度函数，可能并不完全恰当。适应度函数与目标函数之间存在着正向关系，我们可以通过对方程进行适当的调整，从而得到适应度函数。

遗传算法伪代码

基本遗传算法伪代码
/*
* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
* G：终止进化的代数
若进化过程中产生的任一单独个体的适应度函数值超出Tf，进化流程即可宣告结束。
*/
对Pm、Pc、M、G、Tf等参数进行初始化，同时随机生成第一代种群Pop。
 
do
{ 
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
　　do
　　{
　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
　　　　if ( random ( 0 , 1 ) < Pm )
　　　　{
　　　　　　对2个个体按变异概率Pm执行变异操作
　　　　}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )

遗传算法优化方法：

精英主义策略，作为基本遗传算法的一种优化手段，旨在确保在进化过程中形成的最佳解不会因交叉和变异而受损。为此，我们采取的措施是将每一代中的最优解完整地保留并复制至下一代。

在三个基础操作的基础上，我们可以引入一个新增的插入步骤。这一步骤会将染色体上的某个随机片段，移动至另一个随机指定的位置。

遗传算法实例

这里选用参考3中的实例：计算函数

的最小值开yunapp体育官网入口下载手机版，其中每个变量的取值区间都是。

首先，确定适应度的函数：

定义函数y，其值为my_fitness函数对种群population的处理结果。
该随机数矩阵的百分比值位于[0,1]区间内，接下来的处理步骤将对数值进行调整，使其落在[-1,1]的范围内。
人口数量等于两倍于（人口数量减去0.5）。

遗传算法实现：

执行函数my_ga(...)后，得到最佳适应度值、精英个体、当前代数以及上一代数。
变量数量，……，表示求解问题所需的参数数目。
自定义适应度函数的名称为fitness_function，……
种群规模，即每一代中个体数量的多少，……
父本数量，……，表示在每一代中保持恒定的数量（不包括发生变异的部分）。
变异比率，……         百分比
最大演化代数设定，……，表示程序运行过程中能够达到的最大迭代次数。
以最低成本为目标……，这一目标值（函数值越低，其适应度越佳）。
)
% 累加概率
% 假设 parent_number = 10
分子parent_number，其取值范围从-1至1，被用来构建一个数值序列。
分母部分，即sum(parent_number:-1:1)，它代表了一个累加的结果，即一个数值。
分子数值依次递减，分别为10、9、8、7、6、5、4、3、2、1。
% 分母 10+9+...+1=55
相除结果分别为：0.1818、0.1636、0.1455、0.1273、0.1091、0.0909、0.0727、0.0545、0.0364、0.0182。
累加值分别为0.1818，0.3455，0.4909，0.6182，0.7273，0.8182，0.8909，0.9455，0.9818，以及1.0000。
通过%运算得出的结果显示，该累加概率函数呈现出从0至1逐渐增长，但增长速度逐渐减慢的趋势。
记录下每一代的最大适应度值，并将其初始化为1，记作best_fitness。
记录下每一代的最优解，并将其初始化为0，具体操作为：将最大代数与变量数量中的较大值作为参数，赋值给elite。
子女的总数等于种群的整体数目减去那些在每一代中保持不变的个体，即父母们的数量。
每一代的子女数量等于总人口数减去父母数量。
个体数量等于种群规模，而对应矩阵的行数即代表个体数，每行数据描绘了一个具体的个体。
矩阵的列数与%number_of_variables相对应，这一列数等同于参数的数目，而这些参数则代表了个体的特征。
种群数量等于从指定大小和变量数量中随机生成的种群；%完成种群的初始化
当代数等于1时，若最大代数除以演化循环的余数不为零，则演化循环启动。
    
将数据输入至预先设定的函数句柄，进行计算处理。
将人口矩阵输入至fitness_function函数进行计算。
执行计算后，得到个体适应度值（构成一个population_size行1列的矩阵），具体过程为：通过调用fitness_function函数对种群（population）进行评估。
    % index记录排序后每个值原来的行数
对cost数组进行排序，得到的结果是cost和index，排序方式为从小到大。
    % index(1:parent_number) 
种群中排在前面，数量达到parent_number的这些个体，它们的cost值相对较低，这些个体的行数被限制在一定的范围内。
从这批个体中挑选出parent_number个作为繁殖对象，实际上，这parent_number个个体所对应的交配概率是……
对种群进行筛选，保留其中排名靠前的个体，具体操作为：采用索引方式选取前parent_number个个体，并将这些个体组成新的种群。
    % population矩阵是不断变化的
经过前述的sort排序操作，矩阵的排列顺序已变为递增形式，且其中的%cost值也随之发生了变化。
    % cost(1)即为本代的最佳适应度
记录当前代的最高适应度值为1；best_fitness(当前代)等于cost(1)；表示本代的最佳适应度状况。
在%population矩阵中，第一行所展示的是当前代的最优解，即所谓的精英解。
精英（代数，：）等于种群（第一代，：）；%记录当前代的最优解（精英群体）
    % 若本代的最优解已足够好，则停止演化
若当前代最佳适应度函数值< minimal_cost; 
        last_generation = generation;
        break; 
    end
    
    % 交叉变异产生新的种群，染色体交叉开始
    for child = 1:2:child_number % 步长为2是因为每一次交叉会产生2个孩子
        
        % cumulative_probabilities 长度为 parent_number
        % 从中随机选择2个父母出来  (child+parent_number)
        mother = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的母亲
父亲的选择基于累积概率，若随机数大于该概率，则确定其为较优秀的父亲。
        
        % ceil：向上取整
        % rand 生成一个随机数
        % 即随机选择了一列，这一列的值交换
随机选取一个染色体交叉点，其值等于向上取整后的随机数与变量总数相乘的结果。
        
若交叉点值为3，变量总数为5，
mask1的值被设定为1，接着是1，再是1，然后是0，最后是0。
mask2的值被设定为全零，除了最后一位是1，再接下来又是1。
mask1等于一个由1组成的长度为1的向量，后面跟着一个由0组成的长度为number_of_variables减去crossover_point的向量。
        mask2 = not(mask1);
        
        % 获取分开的4段染色体
母亲_1等于遗传掩码1乘以种群函数（以母亲为参数，冒号表示范围）；这代表了母亲染色体前端的遗传信息。
母亲2的基因序列等于mask2与母亲基因序列中指定部分相乘的结果。
        
父亲1的染色体前部由mask1与种群(father,:)进行运算得到。
父亲二号的染色体后段，通过mask2与种群函数population(father,:)的运算得到。
        
        % 得到下一代
在计算人口数量时，将父代编号加上子代编号的结果作为参数，得到的人口数量等于母亲编号1与父亲编号2的和；这代表了一个新的孩子。
设定人口数(parent_number+child+1)等于母亲2加上父亲1；%表示新增了一个孩子
        
    end % 染色体交叉结束
    
    
    % 染色体变异开始，变异种群
变异种群等于从种群中选取2至种群大小范围内的个体，不包括精英个体进行变异操作。
基因总数等于种群规模减去一后，再乘以变量数量。
变异基因的数量等于对元素总数乘以变异率后向上取整的结果。即，变异基因数目是元素总数与变异率相乘后的向上取整值。
    
经过数乘操作，矩阵中的各个元素揭示了发生变化的基因所在的具体位置，这些位置在矩阵中可通过一维坐标进行标识。
确定变异基因的数量，通过计算元素总数与随机数（范围在1到变异次数之间）的乘积，并向上取整得到mutation_points。
    
    % 被选中的基因都被一个随机数替代，完成变异
对选中的基因执行变异处理，变异点数量由`mutation_population`函数决定，该函数接收`mutation_points`作为参数；变异操作的范围在1至`number_of_mutations`之间随机生成。
种群（2：种群规模，）等于变异后的种群。
    % 染色体变异结束
end % 演化循环结束

函数测试：

clc,clear all,close all;
% 调用 my_ga 进行计算
% 求解问题的参数个数         10
定义一个用于评估适应度的函数，命名为my_fitness。
% 种群规模                  100
每一代中维持恒定的数量为50，这相当于交叉率为0.5。
变异发生的几率是0.1，相当于每十个个体中就有一个会经历变异。
最大演化次数限制为10000次，每代演化次数同样设定为10000次。
设定最小目标值，需达到1.0e-6，确保个体适应度函数值符合这一标准。< 0.000001结束
[best_fitness, elite, generation, last_generation] = my_ga(10, 'my_fitness', 100, 50, 0.1, 10000, 1.0e-6);
% 输出后10行
disp(last_generation); 
i_begin = last_generation - 9;
disp(best_fitness(i_begin:last_generation,:));
% disp(best_fitness(9990:10000,:));
% disp(elite(9990:10000,:))
% 不要写成这样，因为GA常常在中间就跳出循环了
% 将elite值转化为问题范围内
my_elite = elite(i_begin:last_generation,:);
my_elite = 2 * (my_elite - 0.5);
disp(my_elite);
% 最佳适应度的演化情况
figure
loglog(1:generation, best_fitness(1:generation), 'linewidth',2)
xlabel('Generation','fontsize',15);
ylabel('Best Fitness','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);
% 最优解的演化情况
figure
semilogx(1 : generation, 2 * elite(1 : generation, :) - 1)
xlabel('Generation','fontsize',15);
ylabel('Best Solution','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);

参考：

http://blog./110913/

该博客地址为http://blog.csdn.net/dazhong159，其中包含了一篇详细的文章，文章的标题是《7908531》，内容丰富，值得一读。

该网页上明确指出，任何对专有名词的修改都是被严格禁止的，同时也不得在文中穿插任何英文单词。改写结果应仅包含改写后的句子开元ky888棋牌官方版，且需保持原文的风格，避免直接复述原句。

禁止访问该GitHub页面，其中包含谢帅的遗传算法项目。

请访问该链接以获取关于功能最大值问题的遗传算法源代码，具体位置在“artificial-intelligence”文件夹下的“genetic-algorithm-for-functional-maximum-problem”子目录中。