三种启发式算法介绍以及实现

时间：2024-03-01 08:53:20

启发式算法

什么是启发式算法？

启发式算法，就一个基于直观或经验构造的算法，可以在可接受的花费下给出待解决优化问题的一个可行解。

说白了，启发式算法就是根据我们在实际生活中的经验，构造的一个可以解决优化问题的算法。

什么是可接受的花费?

比如说我们要解决一个问题，这个问题求解需要成百上千甚至上亿年，这显然是我们不可能接受的时间，又或者我们根本无法接受求解所需要的空间。

什么是优化问题？

工程设计中的最优化问题，是指在一定约束条件下，求解一个目标函数的最大值或最小值问题。实际上就等同于规划问题

什么是可行解？

得到的这个解在我们接受的范围之内，不是必须要最优解。

常见的启发式算法：粒子群算法，模拟退火算法，遗传算法，蚁群算法，禁忌搜索算法，本次我们介绍前三个算法。

引入

我们举一个最简单的例子

我们如何找到这个函数的最大值？

我首先想到最简单的办法就是去尝试，这就需要引入一个概念，盲目搜索。

盲目搜索分为两类，一类是我们最熟悉的穷举法，穷举法就是随机的连续取值。还有一种是蒙特卡洛模拟，那么什么是蒙特卡洛模拟？

实际上，枚举法和蒙特卡洛模拟是完全不同的两种盲目搜索方法。

这样的盲目搜索很容易陷入计算时间的无穷黑洞中，所以我们需要启发式算法来解决更困难，更复杂的问题。这里给出盲目搜索和启发式搜索更多的解释。

粒子群算法

1995年，美国学者Kennedy和Eberhart共同提出了粒子群算法，其基本思想源于对鸟类群体行为进行建模与仿真的研究结果的启发。

它的核心思想是利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的可行解

问题引入

首先，离食物最近的鸟会对其他的鸟说：兄弟们，你们快往我这个方向来，我这离食物最近；
与此同时，每只鸟在搜索食物的过程中，它们的位置也在不停变化，因此每只鸟也知道自己离食物最近的位置，这也是它们的一个参考；最后，鸟在飞行中还需要考虑一个惯性。

这样，就是三个方向加上自己的当前位置

我们对这一幅图，赋予更多的数学意义，引入个体学习因子，社会学习因子的概念，以及对应的权重系数，得到：

粒子群算法中的基本概念

粒子：优化问题的候选解
位置：候选解所在的位置
速度：候选解移动的速度
适应度：评价粒子优劣的值，一般设置为目标函数值
个体最佳位置：单个粒子迄今为止找到的最佳位置
群体最佳位置：所有粒子迄今为止找到的最佳位置

粒子群算法的核心表达式

粒子群算法流程图

粒子群算法的代码实现

clc;clear;close all;
%% 初始化种群
f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式
figure(1);ezplot(f,[0,0.01,20]);
N = 50;                         % 初始种群个数
d = 1;                          % 空间维数
ger = 100;                      % 最大迭代次数     
limit = [0, 20];                % 设置位置参数限制
vlimit = [-1, 1];               % 设置速度限制
w = 0.8;                        % 惯性权重
c1 = 0.5;                       % 自我学习因子
c2 = 0.5;                       % 群体学习因子 
for i = 1:d
    x = limit(i, 1) + (limit(i, 2) - limit(i, 1)) * rand(N, d);%初始种群的位置
end
v = rand(N, d);                  % 初始种群的速度
xm = x;                          % 每个个体的历史最佳位置
ym = zeros(1, d);                % 种群的历史最佳位置
fxm = zeros(N, 1);               % 每个个体的历史最佳适应度
fym = -inf;                      % 种群历史最佳适应度
hold on
plot(xm, f(xm), \'ro\');title(\'初始状态图\');
figure(2)
%% 群体更新
iter = 1;
record = zeros(ger, 1);          % 记录器
while iter <= ger
     fx = f(x) ; % 个体当前适应度   
     for i = 1:N      
        if fxm(i) < fx(i)
            fxm(i) = fx(i);     % 更新个体历史最佳适应度
            xm(i,:) = x(i,:);   % 更新个体历史最佳位置
        end 
     end
if fym < max(fxm)
        [fym, nmax] = max(fxm);   % 更新群体历史最佳适应度
        ym = xm(nmax, :);      % 更新群体历史最佳位置
 end
    v = v * w + c1 * rand * (xm - x) + c2 * rand * (repmat(ym, N, 1) - x);% 速度更新
    % 边界速度处理
    v(v > vlimit(2)) = vlimit(2);
    v(v < vlimit(1)) = vlimit(1);
    x = x + v;% 位置更新
    % 边界位置处理
    x(x > limit(2)) = limit(2);
    x(x < limit(1)) = limit(1);
    record(iter) = fym;%最大值记录
%     x0 = 0 : 0.01 : 20;
%     plot(x0, f(x0), \'b-\', x, f(x), \'ro\');title(\'状态位置变化\')
%     pause(0.1)
    iter = iter+1;
end
figure(3);plot(record);title(\'收敛过程\')
x0 = 0 : 0.01 : 20;![](https://img2020.cnblogs.com/blog/2478564/202108/2478564-20210807205959209-1752240276.png)


figure(4);plot(x0, f(x0), \'b-\', x, f(x), \'ro\');title(\'最终状态位置\')
disp([\'最大值：\',num2str(fym)]);
disp([\'变量取值：\',num2str(ym)]);

遗传算法

问题引入

遗传算法是仿照了达尔文的生物进化概念：“物竞天择，适者生存”

遗传算法中的基本概念

谢菲尔德大学遗传算法工具箱

安装以及使用见：MATLAB安装谢菲尔德（Sheffield）遗传算法工具箱的安装（文件名已小写）_东风难破的博客-****博客

工具箱函数表

遗传算法基本步骤

编码与种群生成

遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串，最常用的方法是将十进制数转换为二进制数。我们可以使用遗传算法工具箱直接生成一个随机的二进制矩阵代替。

进制转换函数

适应度函数

遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。

选择函数

选择函数把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。

一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。

交叉函数

交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。
单点交叉的具体操作过程是：
• 先对群体进行随机配对；
• 其次随机设置交叉点位置；
• 最后再相互交换配对染色体之间的部分基因

变异函数

变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。

OldChrom为当前种群，Pm为变异概率（默认为0.7）,BaseV指明染色体个体元素的变异的基本字符（默认二进制编码）

重插入函数

对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。

遗传算法应用实例

问题引入

参数设置

代码
clc
clear all
close all
%% 画出函数图
figure(1);
hold on;
lb=1;ub=2; %函数自变量范围【1,2】
ezplot(\'sin(10*pi*X)/X\',[lb,ub]);   %画出函数曲线
xlabel(\'自变量/X\')
ylabel(\'函数值/Y\')
%% 定义遗传算法参数
NIND=40;        %个体数目
MAXGEN=20;      %最大遗传代数
PRECI=20;       %变量的二进制位数
GGAP=0.95;      %代沟
px=0.7;         %交叉概率
pm=0.01;        %变异概率
trace=zeros(2,MAXGEN);                        %寻优结果的初始值
FieldD=[PRECI;lb;ub;1;0;1;1];                      %区域描述器
Chrom=crtbp(NIND,PRECI);                      %初始种群
%% 优化
gen=0;                                  %代计数器
X=bs2rv(Chrom,FieldD);                 %计算初始种群的十进制转换
ObjV=sin(10*pi*X)./X;        %计算目标函数值
while gen<MAXGEN
   FitnV=ranking(ObjV);                               %分配适应度值
   SelCh=select(\'sus\',Chrom,FitnV,GGAP);              %选择
   SelCh=recombin(\'xovsp\',SelCh,px);                  %重组
   SelCh=mut(SelCh,pm);                               %变异
   X=bs2rv(SelCh,FieldD);               %子代个体的十进制转换
   ObjVSel=sin(10*pi*X)./X;             %计算子代的目标函数值
   [Chrom,ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群
   X=bs2rv(Chrom,FieldD);
   gen=gen+1;                                             %代计数器增加
   %获取每代的最优解及其序号，Y为最优解,I为个体的序号
   [Y,I]=min(ObjV);
   trace(1,gen)=X(I);                            %记下每代的最优值
   trace(2,gen)=Y;                               %记下每代的最优值
end
plot(trace(1,:),trace(2,:),\'bo\');                            %画出每代的最优点
grid on;
plot(X,ObjV,\'b*\');   %画出最后一代的种群
hold off
%% 画进化图
figure(2);
plot(1:MAXGEN,trace(2,:));
grid on
xlabel(\'遗传代数\')
ylabel(\'解的变化\')
title(\'进化过程\')
bestY=trace(2,end);
bestX=trace(1,end);
fprintf([\'最优解:\nX=\',num2str(bestX),\'\nY=\',num2str(bestY),\'\n\'])

模拟退火算法

爬山算法

在学习模拟退火算法之前，我们首先来学习一个同样是启发式算法的例子，爬山算法。

篇幅有限，我在这里就不啰嗦爬山算法了，这个算法比较简单，建议大家直接看我贴出的链接即可快速掌握

爬山算法_百度百科 (baidu.com)

简而言之，爬山算法是对深度优先搜索的改进，目的是寻找出局部最优解，然而当我们在寻找全局最优解时，很容易就会出现问题。这时，我们就需要我们的模拟退火算法来解决这个问题。

模拟退火算法引入

那么模拟退火算法到底是怎么克服这个缺点的呢？

举例来说明：

求函数\(11sinx+7cos(5x)\)在\([-3,3]\)内的最大值

旧的解： \(

相关文章