什么是启发式遗传算法

liuliuQA2021-04-30 17:16:54阅读(...)

启发式遗传算法是将启发式算法与遗传算法相结合解决最优化问题的一种算法,它继承了启发式算法和遗传算法的优势,并且弥补了部分劣势。启发式遗传算法不仅缩短了搜索时间,还增强了局部搜索的能力。

启发式遗传算法是将启发式算法与遗传算法相结合解决最优化问题的一种算法,它继承了启发式算法和遗传算法的优势,并且弥补了部分劣势。启发式遗传算法不仅缩短了搜索时间,还增强了局部搜索的能力。

什么是启发式遗传算法

概念

启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。

而启发式遗传算法是将遗传算法应用于启发式算法中,用来解决最优化问题的一种算法。

遗传算法与启发式遗传算法

遗传算法

与其他启发式搜索方法一样,遗传算法在形式上是一种迭代方法,它从一组解( 群体)出发,模拟生物体的进化机制,采用复制、交叉、变异等遗传操作,在继承原有优良基因的基础上,生成具有更好性能指标的下一代解的群体,不断迭代,直到搜索到最优解或满意解为止。用遗传算法解决组合优化问题的一般步骤:

Step1: 确定群体规模 i(整数)及遗传操作的代数(整数)。初试代数 k = 1,使用随机方法或其他方法产生 i 个可能解

Step2:对于群体中每一个个体

Step3:while(!结束条件)

对于群体中每一个体

根据生存概率

Step4:满足条件,结束操作。

启发式遗传算法

遗传算法是 John Holland 教授和他的学生们发展建立的 。早期的算法是简单遗传算法,效率很低。因此人们在应用遗传算法时,常常对简单遗传算法进行修改,加入新技术,保留简单遗传算法的主要特点,同时又与之有所不同。

无约束优化问题非常适合遗传算法,比方说求函数,

Step1:编码表示。对于 q 维实向量

Step2:选择一个正整数 n 作为群体的规模参数,然后利用传统数值解法生成 n 个近似最优点

Step3:给定一个很小的数 M ,取适应值函数:

计算第 t 代群体 P(f)的每个个体

Step4:对每个个体

然后根据随机选择策略,使得每个个体

Step5:对从群体 P(t)中选择复制的个体采用杂交算子和变异算子作用形成下一代新的个体,杂交是以概率

Step6:循环执行第三、四、五步直到满足停止准则,停止准则设置成最大代数或得到容许解时终止。

算法第三步中适应值函数的选取数 M 是为了使适应值非负,这样便于计算演化概率,显然适应值越大目标函数越大,因而个体越优;反之,适应值越小的个体越差。适应值大的个体有更多的机会在下一代中再生。对于极小化问题可采取下面方法定义适应函数

启发式遗传算法的优势

在科学实践、工程技术和日常生活中, 人们常常会遇到大量的、各式各样的最优化问题。最优化方法在近几十年里获得了巨大的发展,但很多方法不同程度上还存在着一些不足之处,尤其是最终所求得的大多为局部最优解,并不是全局最优解。而近年来得到蓬勃发展的遗传算法其本质是一种求解问题的高效并行全局搜索方法  。它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最优解。遗传算法对目标函数或约束条件, 既不要求连续,又不要求可微, 只要问题是可计算的就行。尽管遗传算法是一种全局随机优化方法, 但它也存在缺点,主要是:

(1)完全依赖概率随机地进行寻优操作虽然可以避免陷入局部极小, 但受寻优条件的限制, 一般只能得到全局范围内的次优解,很难得到最优解;

(2)通过参数的二进制编码字符串间接运算, 人为地将连续空间离散化, 导致计算精度与字符串长度、运算量之间的矛盾;

(3)由于遗传算法采用随机优化技术,所以要花费大量的时间;

(4)遗传算法虽然具有很强的全局搜索能力,但其局部搜索能力较弱。

针对以上存在的问题,将遗传算法与梯度寻优技术结合起来,并采用原始变量来构成染色体,设计出启发式遗传算法,可以成功解决上述问题。

应用

启发式遗传算法搜索能力很强,下面给出了两个具体应用。

Camel 函数的最优化问题

Camel 函数:

将常规变异操作和启发式遗传算法中的变异操作两种方式用于 Camel 函数的最优化问题,并比较和分析优化结果。表 1 给出了对于 10 个不同的初始解群,

由表 1 可见,在相同迭代次数下变异操作可以优化结果,但当

banana 函数的最优化问题

由 Rosenbrock 设计的 Banana 函数是一个极难优化的函数,理论分析与数值计算表明,Banana 函数对于最速下降法是不成功的,甚至在合理的时间内完全不收敛。

Banana 函数定义为:

最优解是 X*=(1,1),

通过实例计算表明,在远离 X*=(0,0)点的区域内任意选取 10 个初始解群,经过启发式遗传算法的搜索,都能收敛到最小值点,平均值为:

从计算情况可知,在相同精度条件下,启发式遗传算法所用时间大概是遗传算法的四分之一。

收藏0个人收藏
走进科技生活方式

发表评论

本文评论已关闭!