遗传算法的概念最早是由Bagley J.D 于1967年提出的。后来Michigan大学的J.H.Holland教授于1975年开始对遗传算法(Genetic Algorithm, GA)的机理进行系统化的研究。遗传算法是对达尔文生物进化理论的简单模拟，其遵循“适者生存”、“优胜略汰”的原理。遗传算法模拟一个人工种群的进化过程，并且通过选择、杂交以及变异等机制，种群经过若干代以后，总是达到最优(或近最优)的状态。
自从遗传算法被提出以来，其得到了广泛的应用，特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域，遗传算法更是发挥了重大的作用，大大提高了问题求解的效率。遗传算法也是当前“软计算”领域的重要研究课题。
本文首先结合MATLAB对遗传算法实现过程进行详细的分析，然后通过1个实际的函数优化案例对其应用进行探讨。
1. 遗传算法实现过程
现实生活中很多问题都可以转换为函数优化问题，所以本文将以函数优化问题作为背景，对GA的实现过程进行探讨。大部分函数优化问题都可以写成求最大值或者最小值的形式，为了不是一般性，我们可以将所有求最优值的情况都转换成求最大值的形式，例如，求函数f(x)的最大值，
若是求函数f(x)的最小值，可以将其转换成g(x)=-f(x)，然后求g(x)的最大值，
这里x可以是一个变量，也可是是一个由k个变量组成的向量, x=(x1, x2, …, xk)。每个xi, i=1,2,…,k, 其定义域为Di，Di=[ai, bi]。
一般规定f(x)在其定义域内只取正值，若不满足，可以将其转换成以下形式，
其中C是一个正常数。
1.1 编码与解码
要实现遗传算法首先需要弄清楚如何对求解问题进行编码和解码。对于函数优化问题，一般来说，有两种编码方式，一是实数编码，一是二进制编码，两者各有优缺点，二进制编码具有稳定性高、种群多样性大等优点，但是需要的存储空间大，需要解码过程并且难以理解；而实数编码直接用实数表示基因，容易理解并且不要解码过程，但是容易过早收敛，从而陷入局部最优。本文以最常用的二进制编码为例，说明遗传编码的过程。
从遗传算法求解的过程来看，需要处理好两个空间的问题，一个是编码空间，另一个是解空间，如下图所示
从解空间到编码空间的映射过程成为编码过程；从编码空间到解空间的映射过程成为解码过程。下面就以求解一个简单的一维函数f(x) = -(x-1)^2+4, x的取值范围为[-1,3]最大值为例，来说明编码及解码过程。
编码：
在编码之前需要确定求解的精度，在这里，我们设定求解的精度为小数点后四位，即1e-4。这样可以将每个自变量xi的解空间划分为个等分。以上面这个函数为例，即可以将x的解空间划分为(3-(-1))*1e+4=40000个等分。使ni满足，这里ni表示使上式成立的最小整数，即表示自变量xi的基因串的长度。因为215<40000<216，这里ni取16。例如0000110110000101就表示一个解空间中的基因串。表示所有自变量x=(x1, x2, …, xk)的二进制串的总长度称为一个染色体(Chromosome)的长度或者一个个体(Individual)的长度，。编码过程一般在实现遗传算法之前需要指定。
解码：
解码即将编码空间中的基因串翻译成解空间中的自变量的实际值的过程。对于二进制编码而言，每个二进制基因串都可以这样翻译成一个十进制实数值，。例如基因串0000110110000101，可以翻译为，这里二进制基因串转变成十进制是从左至右进行的。
1.2 初始化种群
在开始遗传算法迭代过程之前，需要对种群进行初始化。设种群大小为pop_size，每个染色体或个体的长度为chromo_size，种群的大小决定了种群的多样性，而染色体的长度则是由前述的编码过程决定的。一般随机生成初始种群，但是如果知道种群的实际分布，也可以按照此分布来生成初始种群。假设生成的初始种群为(v1, v2, …, vpop_size)。
1.3 选择操作
选择操作即从前代种群中选择个体到下一代种群的过程。一般根据个体适应度的分布来选择个体。以初始种群(v1, v2, …, vpop_size)为例，假设每个个体的适应度为(fitness(v1), fitness(v2),…, fitness(vpop_size))，一般适应度可以按照解码的过程进行计算。以轮盘赌的方式选择个体，如下图
随机转动一下轮盘，当轮盘停止转动时，若指针指向某个个体，则该个体被选中。很明显，具有较高适应度的个体比具有较低适应度的个体更有机会被选中。但是这种选择具有随机性，在选择的过程中可能会丢失掉比较好的个体，所以可以使用精英机制，将前代最优个体直接选到下一代中。
轮盘赌选择具体算法如下(这里假定种群中个体是按照适应度从小到大进行排列的，如果不是，可以按照某种排序算法对种群个体进行重排)：
Selection Algorithm
var pop, pop_new;/*pop为前代种群，pop_new为下一代种群*/
var fitness_value, fitness_table;/*fitness_value为种群的适应度，fitness_table为种群累积适应度*/
for i=1:pop_size
r = rand*fitness_table(pop_size);/*随机生成一个随机数，在0和总适应度之间，因为fitness_table(pop_size)为最后一个个体的累积适应度，即为总适应度*/
first = 1;
last = pop_size;
mid = round((last+first)/2);
idx = -1;
/*下面按照排中法选择个体*/
while (first <= last) && (idx == -1)
if r > fitness_table(mid)
first = mid;
elseif r < fitness_table(mid)
last = mid;
else
idx = mid;
break;
end if
mid = round((last+first)/2);
if (last - first) == 1
idx = last;
break;
end if
end while
for j=1:chromo_size
pop_new(i,j)=pop(idx,j);
end for
end for
/*是否精英选择*/
if elitism
p = pop_size-1;
else
p = pop_size;
end if
for i=1:p
for j=1:chromo_size
pop(i,j) = pop_new(i,j);/*若是精英选择，则只将pop_new前pop_size-1个个体赋给pop，最后一个为前代最优个体保留*/
end for
end for
1.3 交叉操作
交叉操作是对任意两个个体进行的(在这里我们实现的算法是直接对相邻的两个个体进行的)。随机选择两个个体，如下图所示
然后随机生成一个实数0<=r<=1, 如果r
单点交叉具体算法如下：
Crossover algorithm
for i=1:2:pop_size
if(rand < cross_rate)/*cross_rate为交叉概率*/
cross_pos = round(rand * chromo_size);/*交叉位置*/
if or (cross_pos == 0, cross_pos == 1)
continue;/*若交叉位置为0或1，则不进行交叉*/
end if
for j=cross_pos:chromo_size
pop(i,j)pop(i+1,j);/*交换*/
end for
end if
end for
1.4 变异操作
变异操作是对单个个体进行的。首先生成一个随机实数0<=r<=1, 如果r
如个体需要进行变异操作，首先需要确定变异位置(rand*chromo_size)，若为0则不进行变异，否则则对该位置的二进制数字进行变异：1变成0, 0变成1.(当然也可以选择多点进行变异)
单点变异的具体算法描述如下：
Mutation algorithm
for i=1:pop_size
if rand < mutate_rate/*mutate_rate为变异概率*/
mutate_pos = round(rand*chromo_size);/*变异位置*/
if mutate_pos == 0
continue;/*若变异位置为0，则不进行变异*/
end if
pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/*将变异位置上的数字至反*/
end if
end for
1.5 遗传算法流程
遗传算法计算流程图如下图所示
1.6 MATLAB程序实现
初始化：
%初始化种群
%pop_size: 种群大小
%chromo_size: 染色体长度
function initilize(pop_size, chromo_size)
global pop;
for i=1:pop_size
for j=1:chromo_size
pop(i,j) = round(rand);
end
end
clear i;
clear j;
计算适应度：(该函数应该根据具体问题进行修改，这里优化的函数是前述的一维函数)
%计算种群个体适应度，对不同的优化目标，此处需要改写
%pop_size: 种群大小
%chromo_size: 染色体长度
function fitness(pop_size, chromo_size)
global fitness_value;
global pop;
global G;
for i=1:pop_size
fitness_value(i) = 0.;
end
for i=1:pop_size
for j=1:chromo_size
if pop(i,j) == 1
fitness_value(i) = fitness_value(i)+2^(j-1);
end
end
fitness_value(i) = -1+fitness_value(i)*(3.-(-1.))/(2^chromo_size-1);
fitness_value(i) = -(fitness_value(i)-1).^2+4;
end
clear i;
clear j;
对个体按照适应度大小进行排序：
%对个体按适应度大小进行排序，并且保存最佳个体
%pop_size: 种群大小
%chromo_size: 染色体长度
function rank(pop_size, chromo_size)
global fitness_value;
global fitness_table;
global fitness_avg;
global best_fitness;
global best_individual;
global best_generation;
global pop;
global G;
for i=1:pop_size
fitness_table(i) = 0.;
end
min = 1;
temp = 1;
temp1(chromo_size)=0;
for i=1:pop_size
min = i;
for j = i+1:pop_size
if fitness_value(j)
min = j;
end
end
if min~=i
temp = fitness_value(i);
fitness_value(i) = fitness_value(min);
fitness_value(min) = temp;
for k = 1:chromo_size
temp1(k) = pop(i,k);
pop(i,k) = pop(min,k);
pop(min,k) = temp1(k);
end
end
end
for i=1:pop_size
if i==1
fitness_table(i) = fitness_table(i) + fitness_value(i);
else
fitness_table(i) = fitness_table(i-1) + fitness_value(i);
end
end
fitness_table
fitness_avg(G) = fitness_table(pop_size)/pop_size;
if fitness_value(pop_size) > best_fitness
best_fitness = fitness_value(pop_size);
best_generation = G;
for j=1:chromo_size
best_individual(j) = pop(pop_size,j);
end
end
clear i;
clear j;
clear k;
clear min;
clear temp;
clear temp1;
选择操作：
%轮盘赌选择操作
%pop_size: 种群大小
%chromo_size: 染色体长度
%cross_rate: 是否精英选择
function selection(pop_size, chromo_size, elitism)
global pop;
global fitness_table;
for i=1:pop_size
r = rand * fitness_table(pop_size);
first = 1;
last = pop_size;
mid = round((last+first)/2);
idx = -1;
while (first <= last) && (idx == -1)
if r > fitness_table(mid)
first = mid;
elseif r < fitness_table(mid)
last = mid;
else
idx = mid;
break;
end
mid = round((last+first)/2);
if (last - first) == 1
idx = last;
break;
end
end
for j=1:chromo_size
pop_new(i,j)=pop(idx,j);
end
end
if elitism
p = pop_size-1;
else
p = pop_size;
end
for i=1:p
for j=1:chromo_size
pop(i,j) = pop_new(i,j);
end
end
clear i;
clear j;
clear pop_new;
clear first;
clear last;
clear idx;
clear mid;
交叉操作：
%单点交叉操作
%pop_size: 种群大小
%chromo_size: 染色体长度
%cross_rate: 交叉概率
function crossover(pop_size, chromo_size, cross_rate)
global pop;
for i=1:2:pop_size
if(rand < cross_rate)
cross_pos = round(rand * chromo_size);
if or (cross_pos == 0, cross_pos == 1)
continue;
end
for j=cross_pos:chromo_size
temp = pop(i,j);
pop(i,j) = pop(i+1,j);
pop(i+1,j) = temp;
end
end
end
clear i;
clear j;
clear temp;
clear cross_pos;
变异操作：
%单点变异操作
%pop_size: 种群大小
%chromo_size: 染色体长度
%cross_rate: 变异概率
function mutation(pop_size, chromo_size, mutate_rate)
global pop;
for i=1:pop_size
if rand < mutate_rate
mutate_pos = round(rand*chromo_size);
if mutate_pos == 0
continue;
end
pop(i,mutate_pos) = 1 - pop(i, mutate_pos);
end
end
clear i;
clear mutate_pos;
打印算法迭代过程：
%打印算法迭代过程
%generation_size: 迭代次数
function plotGA(generation_size)
global fitness_avg;
x = 1:1:generation_size;
y = fitness_avg;
plot(x,y)
算法主函数：
%遗传算法主函数
%pop_size: 输入种群大小
%chromo_size: 输入染色体长度
%generation_size: 输入迭代次数
%cross_rate: 输入交叉概率
%cross_rate: 输入变异概率
%elitism: 输入是否精英选择
%m: 输出最佳个体
%n: 输出最佳适应度
%p: 输出最佳个体出现代
%q: 输出最佳个体自变量值
function [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate, elitism)
global G ; %当前代
global fitness_value;%当前代适应度矩阵
global best_fitness;%历代最佳适应值
global fitness_avg;%历代平均适应值矩阵
global best_individual;%历代最佳个体
global best_generation;%最佳个体出现代
fitness_avg = zeros(generation_size,1);
disp "hhee"
fitness_value(pop_size) = 0.;
best_fitness = 0.;
best_generation = 0;
initilize(pop_size, chromo_size);%初始化
for G=1:generation_size
fitness(pop_size, chromo_size);  %计算适应度
rank(pop_size, chromo_size);  %对个体按适应度大小进行排序
selection(pop_size, chromo_size, elitism);%选择操作
crossover(pop_size, chromo_size, cross_rate);%交叉操作
mutation(pop_size, chromo_size, mutate_rate);%变异操作
end
plotGA(generation_size);%打印算法迭代过程
m = best_individual;%获得最佳个体
n = best_fitness;%获得最佳适应度
p = best_generation;%获得最佳个体出现代
%获得最佳个体变量值，对不同的优化目标，此处需要改写
q = 0.;
for j=1:chromo_size
if best_individual(j) == 1
q = q+2^(j-1);
end
end
q = -1+q*(3.-(-1.))/(2^chromo_size-1);
clear i;
clear j;
2.  案例研究
对上一节中的函数进行优化，设置遗传算法相关参数，程序如下
function run_ga()
elitism = true;%选择精英操作
pop_size = 20;%种群大小
chromo_size = 16;%染色体大小
generation_size = 200;%迭代次数
cross_rate = 0.6;%交叉概率
mutate_rate = 0.01;%变异概率
[m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate,elitism);
disp "最优个体"
m
disp "最优适应度"
n
disp "最优个体对应自变量值"
q
disp "得到最优结果的代数"
p
clear;
结果如下：
"最优个体"
m =
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
"最优适应度"
n =
4.0000
"最优个体对应自变量值"
q =
1.0000
"得到最优结果的代数"
p =
74
此结果非常准确。
算法迭代过程图形：
从上图中可以看出，随着迭代次数的增加，算法逐渐收敛。
3. 总结
本文详细的介绍了简单遗传算法的实现过程，并以一个简单的函数优化作为案例说明了其应用。但是由于该测试函数过于简单，在实际的应用过程中，还需要对相关参数进行调整，使其效率得到更大的提高。

题目：
定义一个二元函数，
 。用遗传算法求全局最大值；
遗传算法简单介绍与MATLAB实现(二)
引入题目一
上一篇文章中我们简单的介绍了一了一下遗传算法，其中提到了多元函数f=f(x,y)f=f(x,y)，所以在这里我们就定义一个二元函数，作为第一个练手的程序。
遗传算法MATLAB程序
设定参数
首先我们要确定一系列参数
N = 100;  %种群内个体数目
N_chrom = 2; %染色体节点数
iter = 2000; %迭代次数
mut = 0.2;  %突变概率
acr = 0.2; %交叉概率
其中突变概率指的是某个个体的染色体发生突变的概率。因为实际中并不可能每一个个体都会发生突变，而是存在一定的概率，因此我们在这里定义每一个个体突变发生的概率为0.2。
同理，交叉概率指的就是某个个体与另一个个体发生染色体交叉的概率。
迭代次数指的是整个种群迭代2000多次。
一般来说，并不是突变概率、交叉概率越小或者越大越好。比如说突变概率特别高的话，会让整个种群的最优适应度飘忽不定。如果特别小的话，会让种群迭代的速度特别慢，很难找到最优适应度。这里取0.2是我经过多次试验以后，觉得0.2是一个比较稳定不会乱飘且适应度收敛也不错的一个值。
迭代次数也同理，如果一个特别简单的模型去求最优解，可能五六次迭代就求出来了，那么2000次迭代纯属浪费时间。但是如果是一个特别复杂的模型，那么2000次迭代就有可能不够。具体迭代次数可以自己灵活决定。
chrom_range = [-10 -10; 10 10];%每个节点的值的区间
chrom = zeros(N, N_chrom);%存放染色体的矩阵
fitness = zeros(N, 1);%存放染色体的适应度
fitness_ave = zeros(1, iter);%存放每一代的平均适应度
fitness_best = zeros(1, iter);%存放每一代的最优适应度
chrom_best = zeros(1, N_chrom+1);%存放当前代的最优染色体与适应度
其中的chrom_range指的是每个节点值的区间。在我们的这个模型中，x∈[−10,10],y∈[−10,10]x∈[−10,10],y∈[−10,10]。第一行放的是两个变量的区间下限，第二行放的是区间上限。
chrom和fitness两个矩阵你们可以自己理解一下为什么这样子写。
fitness_ave用来存放每一代的平均适应度，主要是用来最后画图，观察种群在每一次迭代中适应度的变化情况。fitness_best同理。
chrom_best用来存放最优适应度对应的最优染色体与适应度，可以回想一下上一章染色体变异中需要最优适应度，优胜劣汰中需要最优染色体，这个矩阵作用就是如此。
初始化种群
接下来开始初始化参数
chrom = Initialize(N, N_chrom, chrom_range); %初始化染色体
fitness = CalFitness(chrom, N, N_chrom); %计算适应度
chrom_best = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
fitness_best(1) = chrom_best(end); %将当前最优存入矩阵当中
fitness_ave(1) = CalAveFitness(fitness); %将当前平均适应度存入矩阵当中
Initialize函数是我自定义的一个函数，用于初始化染色体。具体操作就是用一个for循环对每个个体的染色体进行随机赋值，并利用chrom_range将其限定在变量规定的区间之内。function chrom_new = Initialize(N, N_chrom, chrom_range)
chrom_new = rand(N, N_chrom);
for i = 1:N_chrom %每一列乘上范围
chrom_new(:, i) = chrom_new(:, i)*(chrom_range(2, i)-chrom_range(1, i))+chrom_range(1, i);
end
CalFitness函数则是计算chrom内每个个体的适应度，并将其保存在fitness中。这个函数很重要，请着重理解这个函数的用法。function fitness = CalFitness(chrom, N, N_chrom)
fitness = zeros(N, 1);
%开始计算适应度
for i = 1:N
x = chrom(i, 1);
y = chrom(i, 2);
fitness(i) = sin(x)+cos(y)+0.1*x+0.1*y;
end
FindBest函数寻找出当前种群中的最优染色体，并将其保存在chrom_best。
function chrom_best = FindBest(chrom, fitness, N_chrom)
chrom_best = zeros(1, N_chrom+1);
[maxNum, maxCorr] = max(fitness);
chrom_best(1:N_chrom) =chrom(maxCorr, :);
chrom_best(end) = maxNum;
CalAveFitness函数用于计算当前种群中的平均适应度。
function fitness_ave = CalAveFitness(fitness)
[N ,~] = size(fitness);
fitness_ave = sum(fitness)/N;
迭代开始
初始化完以后就开始迭代，为了保证迭代次数和iter一致，这里我们就直接令t从2开始迭代。
再一次迭代过程中，一个种群执行操作顺序为：染色体变异，染色体交叉，计算适应度，寻找最优染色体，替换当前存储的最优染色体，优胜劣汰。
需要注意的是这里替换当前最优染色体。因为我们将这个种群的个个个体的染色体重新变异、交叉过了，所以最优染色体也会变化。但是这一代的最优染色体不一定比上一次迭代的最优染色体好，所以需要判定是否将最优染色体这个位置给换掉。
因此迭代过程中的代码为for t = 2:iter
chrom = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter); %变异
chrom = AcrChrom(chrom, acr, N, N_chrom); %交叉
fitness = CalFitness(chrom, N, N_chrom); %计算适应度
chrom_best_temp = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
if chrom_best_temp(end)>chrom_best(end) %替换掉当前储存的最优
chrom_best = chrom_best_tem
其中MutChrom函数用来对种群进行染色体变异操作。这里面的操作比较多，主要可以分为三步：
判断某节点是否变异；
判断变异是增加还是减少；
判断变异后的值是否越界。
用流程图表示为下图所示。
下面代码表示为
function chrom_new = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter)
for i = 1:N
for j = 1:N_chrom
mut_rand = rand; %是否变异
if mut_rand <=mut
mut_pm = rand; %增加还是减少
mut_num = rand*(1-t/iter)^2;
if mut_pm<=0.5
chrom(i, j)= chrom(i, j)*(1-mut_num);
else
chrom(i, j)= chrom(i, j)*(1+mut_num);
end
chrom(i, j) = IfOut(chrom(i, j), chrom_range(:, j)); %检验是否越界
end
end
end
chrom_new = chrom;
越界函数IfOut函数我们看它是左越界还是右越界，如果是左越界，则让节点值等于区间下限；如果是右越界，则让节点值等于区间上限。
function c_new = IfOut(c, range)
if crange(2)
if abs(c-range(1))
c_new = range(1);
else
c_new = range(2);
end
else
c_new = c;
end
AcrChrom函数是染色体交叉函数。逻辑相较染色体变异来说比较简单，大致可以分为以下几点
判断该节点是否交叉；
随机寻找一个与其交叉的节点；
对两个节点进行交叉。function chrom_new = AcrChrom(chrom, acr, N, N_chrom)
for i = 1:N
acr_rand = rand;
if acr_rand
acr_chrom = floor((N-1)*rand+1); %要交叉的染色体
acr_node = floor((N_chrom-1)*rand+1); %要交叉的节点
%交叉开始
temp = chrom(i, acr_node);
chrom(i, acr_node) = chrom(acr_chrom, acr_node);
chrom(acr_chrom, acr_node) = temp;
end
end
chrom_new = chrom;
ReplaceWorse函数则是优胜劣汰这个过程，将种群中的最劣染色体替换掉。这里是直接用最优染色体替换，并且替换掉的是最后几个染色体，目的是加快收敛速度，但可能会陷入局部最优解。
function [chrom_new, fitness_new] = ReplaceWorse(chrom, chrom_best, fitness)
max_num = max(fitness);
min_num = min(fitness);
limit = (max_num-min_num)*0.2+min_num;
replace_corr = fitness
replace_num = sum(replace_corr);
chrom(replace_corr, :) = ones(replace_num, 1)*chrom_best(1:end-1);
fitness(replace_corr) = ones(replace_num, 1)*chrom_best(end);
chrom_new = chrom;
fitness_new = fitness;
end
输出遗传算法迭代图
在这里我们只输出一个标准图为迭代过程中种群的平均适应度与最优适应度。
在之前我们已经得到了每一代的平均适应度fitness_ave与最优适应度fitness_best，所以可以直接输出图像
figure(1)
plot(1:iter, fitness_ave, 'r', 1:iter, fitness_best, 'b')
grid on
legend('平均适应度', '最优适应度')
之后我们还想要看得出的点在实际图像中哪个位置，所以我们可以增加一个用来作图的函数PlotModel
function y = PlotModel(chrom)
x = chrom(1);
y = chrom(2);
z = chrom(3);
figure(2)
scatter3(x, y, z, 'ko')
hold on
[X, Y] = meshgrid(-10:0.1:10);
Z =sin(X)+cos(Y)+0.1*X+0.1*Y;
mesh(X, Y, Z)
y=1;
遗传算法主程序
上面就是所有程序片段，因此把主程序的代码联立起来为
clc, clear, close all
%%基础参数
N = 100;  %种群内个体数目
N_chrom = 2; %染色体节点数
iter = 2000; %迭代次数
mut = 0.2;  %突变概率
acr = 0.2; %交叉概率
best = 1;
chrom_range = [-10 -10;10 10];%每个节点的值的区间
chrom = zeros(N, N_chrom);%存放染色体的矩阵
fitness = zeros(N, 1);%存放染色体的适应度
fitness_ave = zeros(1, iter);%存放每一代的平均适应度
fitness_best = zeros(1, iter);%存放每一代的最优适应度
chrom_best = zeros(1, N_chrom+1);%存放当前代的最优染色体与适应度
%%初始化
chrom = Initialize(N, N_chrom, chrom_range); %初始化染色体
fitness = CalFitness(chrom, N, N_chrom); %计算适应度
chrom_best = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
fitness_best(1) = chrom_best(end); %将当前最优存入矩阵当中
fitness_ave(1) = CalAveFitness(fitness); %将当前平均适应度存入矩阵当中
for t = 2:iter
chrom = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter); %变异
chrom = AcrChrom(chrom, acr, N, N_chrom); %交叉
fitness = CalFitness(chrom, N, N_chrom); %计算适应度
chrom_best_temp = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
if chrom_best_temp(end)>chrom_best(end) %替换掉当前储存的最优
chrom_best = chrom_best_temp;
end
%%替换掉最劣
[chrom, fitness] = ReplaceWorse(chrom, chrom_best, fitness);
fitness_best(t) = chrom_best(end); %将当前最优存入矩阵当中
fitness_ave(t) = CalAveFitness(fitness); %将当前平均适应度存入矩阵当中
end
%%作图
figure(1)
plot(1:iter, fitness_ave, 'r', 1:iter, fitness_best, 'b')
grid on
legend('平均适应度', '最优适应度')
e = PlotModel(chrom_best)
%%输出结果
disp(['最优染色体为', num2str(chrom_best(1:end-1))])
disp(['最优适应度为', num2str(chrom_best(end))])
输出结果
我们运行一下， 可以得到最大点为(7.9541,6.3834)(7.9541,6.3834)，最大值为3.4237。
可以做出最大值点在空间中的位置如图所示。证明我们的结论比较正确，起码没有落到周围的极大值的峰上。
读者想要更加详细理解遗传算法可以看看这个：炫云：遗传算法的实现过程炫云：遗传算法(附Python实现)​zhuanlan.zhihu.com炫云：遗传算法(附Python实现)​zhuanlan.zhihu.com

题目：
定义一个二元函数， 
 。用遗传算法求全局最大值；
遗传算法简单介绍与MATLAB实现（二）
引入题目一
上一篇文章中我们简单的介绍了一了一下遗传算法，其中提到了多元函数f=f(x,y)f=f(x,y)，所以在这里我们就定义一个二元函数，作为第一个练手的程序。
遗传算法MATLAB程序
设定参数
首先我们要确定一系列参数
N = 100;  %种群内个体数目
N_chrom = 2; %染色体节点数
iter = 2000; %迭代次数
mut = 0.2;  %突变概率
acr = 0.2; %交叉概率
其中突变概率指的是某个个体的染色体发生突变的概率。因为实际中并不可能每一个个体都会发生突变，而是存在一定的概率，因此我们在这里定义每一个个体突变发生的概率为0.2。
同理，交叉概率指的就是某个个体与另一个个体发生染色体交叉的概率。
迭代次数指的是整个种群迭代2000多次。
一般来说，并不是突变概率、交叉概率越小或者越大越好。比如说突变概率特别高的话，会让整个种群的最优适应度飘忽不定。如果特别小的话，会让种群迭代的速度特别慢，很难找到最优适应度。这里取0.2是我经过多次试验以后，觉得0.2是一个比较稳定不会乱飘且适应度收敛也不错的一个值。
迭代次数也同理，如果一个特别简单的模型去求最优解，可能五六次迭代就求出来了，那么2000次迭代纯属浪费时间。但是如果是一个特别复杂的模型，那么2000次迭代就有可能不够。具体迭代次数可以自己灵活决定。
chrom_range = [-10 -10; 10 10];%每个节点的值的区间
chrom = zeros(N, N_chrom);%存放染色体的矩阵
fitness = zeros(N, 1);%存放染色体的适应度
fitness_ave = zeros(1, iter);%存放每一代的平均适应度
fitness_best = zeros(1, iter);%存放每一代的最优适应度
chrom_best = zeros(1, N_chrom+1);%存放当前代的最优染色体与适应度
其中的chrom_range指的是每个节点值的区间。在我们的这个模型中，x∈[−10,10],y∈[−10,10]x∈[−10,10],y∈[−10,10]。第一行放的是两个变量的区间下限，第二行放的是区间上限。
chrom和fitness两个矩阵你们可以自己理解一下为什么这样子写。
fitness_ave用来存放每一代的平均适应度，主要是用来最后画图，观察种群在每一次迭代中适应度的变化情况。fitness_best同理。
chrom_best用来存放最优适应度对应的最优染色体与适应度，可以回想一下上一章染色体变异中需要最优适应度，优胜劣汰中需要最优染色体，这个矩阵作用就是如此。
初始化种群
接下来开始初始化参数
chrom = Initialize(N, N_chrom, chrom_range); %初始化染色体
fitness = CalFitness(chrom, N, N_chrom); %计算适应度
chrom_best = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
fitness_best(1) = chrom_best(end); %将当前最优存入矩阵当中
fitness_ave(1) = CalAveFitness(fitness); %将当前平均适应度存入矩阵当中
Initialize函数是我自定义的一个函数，用于初始化染色体。具体操作就是用一个for循环对每个个体的染色体进行随机赋值，并利用chrom_range将其限定在变量规定的区间之内。
function chrom_new = Initialize(N, N_chrom, chrom_range)
chrom_new = rand(N, N_chrom);
for i = 1:N_chrom %每一列乘上范围
    chrom_new(:, i) = chrom_new(:, i)*(chrom_range(2, i)-chrom_range(1, i))+chrom_range(1, i);
end
CalFitness函数则是计算chrom内每个个体的适应度，并将其保存在fitness中。这个函数很重要，请着重理解这个函数的用法。
function fitness = CalFitness(chrom, N, N_chrom)
fitness = zeros(N, 1);
%开始计算适应度
for i = 1:N
    x = chrom(i, 1);
    y = chrom(i, 2);
    fitness(i) = sin(x)+cos(y)+0.1*x+0.1*y;
end
FindBest函数寻找出当前种群中的最优染色体，并将其保存在chrom_best。
function chrom_best = FindBest(chrom, fitness, N_chrom)
chrom_best = zeros(1, N_chrom+1);
[maxNum, maxCorr] = max(fitness);
chrom_best(1:N_chrom) =chrom(maxCorr, :);
chrom_best(end) = maxNum;
CalAveFitness函数用于计算当前种群中的平均适应度。
function fitness_ave = CalAveFitness(fitness)
[N ,~] = size(fitness);
fitness_ave = sum(fitness)/N;
迭代开始
初始化完以后就开始迭代，为了保证迭代次数和iter一致，这里我们就直接令t从2开始迭代。
再一次迭代过程中，一个种群执行操作顺序为：染色体变异，染色体交叉，计算适应度，寻找最优染色体，替换当前存储的最优染色体，优胜劣汰。
需要注意的是这里替换当前最优染色体。因为我们将这个种群的个个个体的染色体重新变异、交叉过了，所以最优染色体也会变化。但是这一代的最优染色体不一定比上一次迭代的最优染色体好，所以需要判定是否将最优染色体这个位置给换掉。
因此迭代过程中的代码为
for t = 2:iter
    chrom = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter); %变异
    chrom = AcrChrom(chrom, acr, N, N_chrom); %交叉
    fitness = CalFitness(chrom, N, N_chrom); %计算适应度
    chrom_best_temp = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
    if chrom_best_temp(end)>chrom_best(end) %替换掉当前储存的最优
        chrom_best = chrom_best_tem
其中MutChrom函数用来对种群进行染色体变异操作。这里面的操作比较多，主要可以分为三步：
判断某节点是否变异；
判断变异是增加还是减少；
判断变异后的值是否越界。
用流程图表示为下图所示。
下面代码表示为
function chrom_new = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter)
for i = 1:N
    for j = 1:N_chrom
        mut_rand = rand; %是否变异
        if mut_rand <=mut
            mut_pm = rand; %增加还是减少
            mut_num = rand*(1-t/iter)^2;
            if mut_pm<=0.5
                chrom(i, j)= chrom(i, j)*(1-mut_num);
            else
                chrom(i, j)= chrom(i, j)*(1+mut_num);
            end
            chrom(i, j) = IfOut(chrom(i, j), chrom_range(:, j)); %检验是否越界
        end
    end
end
chrom_new = chrom;
越界函数IfOut函数我们看它是左越界还是右越界，如果是左越界，则让节点值等于区间下限；如果是右越界，则让节点值等于区间上限。
function c_new = IfOut(c, range)
if c<range(1) || c>range(2)
    if abs(c-range(1))<abs(c-range(2))
        c_new = range(1);
    else
        c_new = range(2);
    end
else
    c_new = c;
end
AcrChrom函数是染色体交叉函数。逻辑相较染色体变异来说比较简单，大致可以分为以下几点
判断该节点是否交叉；
随机寻找一个与其交叉的节点；
对两个节点进行交叉。
function chrom_new = AcrChrom(chrom, acr, N, N_chrom)
for i = 1:N
    acr_rand = rand;
    if acr_rand<acr %如果交叉
        acr_chrom = floor((N-1)*rand+1); %要交叉的染色体
        acr_node = floor((N_chrom-1)*rand+1); %要交叉的节点
        %交叉开始
        temp = chrom(i, acr_node);
        chrom(i, acr_node) = chrom(acr_chrom, acr_node); 
        chrom(acr_chrom, acr_node) = temp;
    end
end
chrom_new = chrom;
ReplaceWorse函数则是优胜劣汰这个过程，将种群中的最劣染色体替换掉。这里是直接用最优染色体替换，并且替换掉的是最后几个染色体，目的是加快收敛速度，但可能会陷入局部最优解。
function [chrom_new, fitness_new] = ReplaceWorse(chrom, chrom_best, fitness)
max_num = max(fitness);
min_num = min(fitness);
limit = (max_num-min_num)*0.2+min_num;
replace_corr = fitness<limit;
replace_num = sum(replace_corr);
chrom(replace_corr, :) = ones(replace_num, 1)*chrom_best(1:end-1);
fitness(replace_corr) = ones(replace_num, 1)*chrom_best(end);
chrom_new = chrom;
fitness_new = fitness;
end
输出遗传算法迭代图
在这里我们只输出一个标准图为迭代过程中种群的平均适应度与最优适应度。
在之前我们已经得到了每一代的平均适应度fitness_ave与最优适应度fitness_best，所以可以直接输出图像
figure(1)
plot(1:iter, fitness_ave, 'r', 1:iter, fitness_best, 'b')
grid on
legend('平均适应度', '最优适应度')
之后我们还想要看得出的点在实际图像中哪个位置，所以我们可以增加一个用来作图的函数PlotModel
function y = PlotModel(chrom)
x = chrom(1);
y = chrom(2);
z = chrom(3);
figure(2)
scatter3(x, y, z, 'ko')
hold on
[X, Y] = meshgrid(-10:0.1:10);
Z =sin(X)+cos(Y)+0.1*X+0.1*Y;
mesh(X, Y, Z)
y=1;
遗传算法主程序
上面就是所有程序片段，因此把主程序的代码联立起来为
clc, clear, close all
%%基础参数
N = 100;  %种群内个体数目
N_chrom = 2; %染色体节点数
iter = 2000; %迭代次数
mut = 0.2;  %突变概率
acr = 0.2; %交叉概率
best = 1;
chrom_range = [-10 -10;10 10];%每个节点的值的区间
chrom = zeros(N, N_chrom);%存放染色体的矩阵
fitness = zeros(N, 1);%存放染色体的适应度
fitness_ave = zeros(1, iter);%存放每一代的平均适应度
fitness_best = zeros(1, iter);%存放每一代的最优适应度
chrom_best = zeros(1, N_chrom+1);%存放当前代的最优染色体与适应度
%%初始化
chrom = Initialize(N, N_chrom, chrom_range); %初始化染色体
fitness = CalFitness(chrom, N, N_chrom); %计算适应度
chrom_best = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
fitness_best(1) = chrom_best(end); %将当前最优存入矩阵当中
fitness_ave(1) = CalAveFitness(fitness); %将当前平均适应度存入矩阵当中
for t = 2:iter
    chrom = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter); %变异
    chrom = AcrChrom(chrom, acr, N, N_chrom); %交叉
    fitness = CalFitness(chrom, N, N_chrom); %计算适应度
    chrom_best_temp = FindBest(chrom, fitness, N_chrom); %寻找最优染色体
    if chrom_best_temp(end)>chrom_best(end) %替换掉当前储存的最优
        chrom_best = chrom_best_temp;
    end
    %%替换掉最劣
    [chrom, fitness] = ReplaceWorse(chrom, chrom_best, fitness);
    fitness_best(t) = chrom_best(end); %将当前最优存入矩阵当中
    fitness_ave(t) = CalAveFitness(fitness); %将当前平均适应度存入矩阵当中
end
%%作图
figure(1)
plot(1:iter, fitness_ave, 'r', 1:iter, fitness_best, 'b')
grid on
legend('平均适应度', '最优适应度')
e = PlotModel(chrom_best)
%%输出结果
disp(['最优染色体为', num2str(chrom_best(1:end-1))])
disp(['最优适应度为', num2str(chrom_best(end))])
输出结果
我们运行一下， 可以得到最大点为(7.9541,6.3834)(7.9541,6.3834)，最大值为3.4237。
可以做出最大值点在空间中的位置如图所示。证明我们的结论比较正确，起码没有落到周围的极大值的峰上。
原文链接：CSDN-专业IT技术社区-登录
读者想要更加详细理解遗传算法可以看看这个：
炫云：遗传算法的实现过程炫云：遗传算法（附Python实现）​zhuanlan.zhihu.com
炫云：遗传算法（附Python实现）​zhuanlan.zhihu.com

问题:利用遗传算法求法f(x)=x*sin(10*pi*x)+2,-1<=x<=2时的最大值

大概步骤就是：

1.随机生成种群，就是-1到2之间的数，只关注保留了小数点后的4位，本来以为是matlab只保留4位小数然而并不是。（问题不大）

2.通过适应度进行选择，就是适应度越高越容易保留下来。这里通过轮盘赌的方式来确定哪些种群留下来。其实是有些个体增加了一下，有些不要啦。比如开始种群为三个个体：0.1111，1.2222，- 0.1111，经过选择后可能变成了：0.1111，1.2222，1.2222。只是可能变成这样额，还有可能是其他情况额。

3.交叉，相当于就是两个个体互相交换基因啦。比如有两个个体：0.1111，1.2222；经过交叉后可能变成：0.1211，1.2122。也仅仅其中可能的一种情况额，到底是哪一位进行交叉是随机的，而且交叉也不定一定进行，只是有一定概率进行而已；

4.变异，这个就是只作用与单个个体；比如有个个体：0.1111，变异后：0.1211。这个变异规则应该有好多种，看自己设吧。下面程序中就是让原来的数加上0.0001当作是变异，当然也可以把+0.01当作变异。变异也只是有可能进行额，它也有可能不进行。

5.变异完后，就是所有的个体就组成新的种群了。就又可以重复1.中的操作啦。

遗传算法，直接贴代码啦。

%%%%%%利用遗传算法求法f(x)=x*sin(10*pi*x)+2,-1<=x<=2时的最大值
%程序问题太多啦，说不定x就跑到定义域外去了，还会找到最小值
%如果定义变异时，是加0.1结果就很奇怪，反正还有好多值得改进的地方，但是用来理解GA算法应该足够啦，感觉也可以把十进制变成2进制来进行操作
clc;close all;clear;
a = -1;%求解区间下界
b = 2;%求解区间上界
cAccuracy = 0.01;%计算精度
NP = 100;%种群的个体数，也就是开始随机生成-1到2上的数的个数
NG = 100;%进化的代数generation
Pc = 0.1;%交叉概率
Pm = 0.5;%变异概率

%%  
population = a+(b-a)*rand(1,NP);%随机产生种群，就是-1到2之间的随机数
for generation = 1:NG%大循环，表示经过的代数
    %% 选择
    fitness = population.*sin(10*pi*population)+2;    %适应度函数,因为算出的适应度都是正的，所以可以直接用fx作适应度，但如果有负的，应该就不可以啊
    Pfit = fitness/sum(fitness);
    for i = 1:NP
        disk(i) = sum(Pfit(1:i));   %通过fitness弄出一个(0,1]的轮盘,来进行轮盘赌
    end
       disknum = rand(1,NP) ;
    populationIndex = zeros(1,NP);
    for i = 1:NP
        for j = 1:NP

            if (disknum(i)<=disk(j))           
               populationChosed(i) = population(j);      %通过轮盘赌选择种群population中那些被淘汰，哪些增加啦。可以产生产生新的种群
               break;
            end


        end
    end
    %% 交叉
    for i = 1:NP
        for j = 1:6 %这里因为matlab保留了小数点后4位数，加上个位和符号，所以选择了6，应该可以改成任意位数，
            populationtemp(i,j)=floor(mod((abs(populationChosed(i)))/10^(-j+1),10)); %将populationChosed的个位，10^-1位..分别存到矩阵中好进行交叉变异
            if(populationChosed(i)<0)
               populationtemp(i,6)=-1;%存储符号
            else
                populationtemp(i,6)=1;
            end
        end
    end%%%%上面就是把数的个位，十位（虽然没十位）分别放到数组里用来进行交叉和变异操作
    randindex = randperm(NP);%任意两组组合
    crossbit = ceil(5*rand(1,NP/2));%交叉的位
    for i = 1:2:NP-1
        if(rand()<Pc)%交叉是可能发生也可能不发生，满足一定的概率Pc
            temp = populationtemp(i,crossbit((i+1)/2));
            populationtemp(randindex(i),crossbit((i+1)/2)) = populationtemp(2,crossbit((i+1)/2));%%交叉过程
            populationtemp(randindex(i+1),crossbit((i+1)/2)) = temp;
        end
    end 
    populaitonCrossed=zeros(NP,1);
    for j=1:5
        populaitonCrossed = populationtemp(:,j)*10^(-j+1)+populaitonCrossed;%将交叉后的数组重新变成正常的数
    end
    populaitonCrossed = populaitonCrossed.*populationtemp(:,6);%还要保证正负和交叉以前一样，其实感觉正负也可以当作交叉位的
    %% 变异

    for i = 1:NP
       if(rand()<Pm)%变异发生的概率是Pm
          populationmeta(i) = populaitonCrossed(i)+0.0001;%变异就是加0.0001
       else
           populationmeta(i) = populaitonCrossed(i);       %不变异保持原样
       end
    end
    population=populationmeta;


figure;
x=-1:0.011:2;
fx=x.*sin(10*pi*x)+2;
plot(x,fx);
hold on
fxpop = population.*sin(10*pi*population)+2;
stem(population,fxpop);
hold off
saveas(gca,['figure_',num2str(generation),'.jpg']);
end

再附一张gif图吧