启发式遗传算法

2022-11-17 97阅读

温馨提示:这篇文章已超过506天没有更新,请注意相关的内容是否还可用!

启发式遗传算法

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

启发式遗传算法

启发式遗传算法概念

启发式算法下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。而启发式遗传算法是将遗传算法应用于启发式算法中,用来解决最优化问题的一种算法。

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

启发式遗传算法遗传算法

与其他启发式搜索方法一样,遗传算法在形式上是一种迭代方法,它从一组解出发,模拟生物体的进化机制,采用复制、交叉、变异等遗传操作,在继承原有优良基因的基础上,生成具有更好性能指标的下一代解的群体,不断迭代,直到搜索到最优解或满意解为止。用遗传算法解决组合优化问题的一般步骤:Step1: 确定群体规模i及遗传操作的代数。初试代数k = 1,使用随机方法或其他方法产生i个可能解组成初始解群。Step2:对于群体中每一个个体,计算其适应度。Step3:while对于群体中每一个体,计算其生存概率;根据生存概率,在群体中选择父体执行遗传操作,包括复制、交叉、变异,得到一个新的解群体,此时k = k + 1,转第二步。Step4:满足条件,结束操作。

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

遗传算法是John Holland教授和他的学生们发展建立的 。早期的算法是简单遗传算法,效率很低。因此人们在应用遗传算法时,常常对简单遗传算法进行修改,加入新技术,保留简单遗传算法的主要特点,同时又与之有所不同。无约束优化问题非常适合遗传算法,比方说求函数,极大值问题。首先利用传统数值解法提供初始群体;再用遗传算法法则得到启发式遗传算法。启发式遗传算法的算法步骤:Step1:编码表示。对于q维实向量,每一个分量都用一个二进制串表示,依照搜索空闻确定串长l ,这样每一点的编码由q个二进制串构成。Step2:选择一个正整数n作为群体的规模参数,然后利用传统数值解法生成n个近似最优点(i=1,2…,n),这些点构成初始群体,完成初始化。Step3:给定一个很小的数M ,取适应值函数:计算第t代群体P(f)的每个个体的适应值。Step4:对每个个体计算其生存概率:然后根据随机选择策略,使得每个个体被选择进行演化。Step5:对从群体P(t)中选择复制的个体采用杂交算子和变异算子作用形成下一代新的个体,杂交是以概率交换两个父代个体间对应的分量。杂交完成后,再以最小概率作用变异算子。变异算子是改变串中的等位基因。Step6:循环执行第三、四、五步直到满足停止准则,停止准则设置成最大代数或得到容许解时终止。算法第三步中适应值函数的选取数M 是为了使适应值非负,这样便于计算演化概率,显然适应值越大目标函数越大,因而个体越优;反之,适应值越小的个体越差。适应值大的个体有更多的机会在下一代中再生。对于极小化问题可采取下面方法定义适应函数

启发式遗传算法启发式遗传算法的优势

在科学实践、工程技术和日常生活中, 人们常常会遇到大量的、各式各样的最优化问题。最优化方法在近几十年里获得了巨大的发展,但很多方法不同程度上还存在着一些不足之处,尤其是最终所求得的大多为局部最优解,并不是全局最优解。而近年来得到蓬勃发展的遗传算法其本质是一种求解问题的高效并行全局搜索方法。它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最优解。遗传算法对目标函数或约束条件, 既不要求连续,又不要求可微, 只要问题是可计算的就行。尽管遗传算法是一种全局随机优化方法, 但它也存在缺点,主要是:完全依赖概率随机地进行寻优操作虽然可以避免陷入局部极小, 但受寻优条件的限制, 一般只能得到全局范围内的次优解,很难得到最优解;通过参数的二进制编码字符串间接运算, 人为地将连续空间离散化, 导致计算精度与字符串长度、运算量之间的矛盾;由于遗传算法采用随机优化技术,所以要花费大量的时间;遗传算法虽然具有很强的全局搜索能力,但其局部搜索能力较弱。针对以上存在的问题,将遗传算法与梯度寻优技术结合起来,并采用原始变量来构成染色体,设计出启发式遗传算法,可以成功解决上述问题。

启发式遗传算法应用

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

启发式遗传算法Camel函数的最优化问题

Camel函数:这是一个处处可导的函数, 存在有6 个局部极小点。最优点是和,最优解=-1.031628,其图像如下:将常规变异操作和启发式遗传算法中的变异操作两种方式用于Camel函数的最优化问题,并比较和分析优化结果。表1 给出了对于10 个不同的初始解群,取不同值并分别迭代200代时所达到的平均值,其中=0 代表常规变异操作:由表1可见,在相同迭代次数下变异操作可以优化结果,但当>=0.6时不如遗传算法。

启发式遗传算法banana函数的最优化问题

由Rosenbrock设计的Banana函数是一个极难优化的函数,理论分析与数值计算表明,Banana函数对于最速下降法是不成功的,甚至在合理的时间内完全不收敛。Banana函数定义为:最优解是X*=,=0,函数曲面和等高线图如图:通过实例计算表明,在远离X*=点的区域内任意选取10个初始解群,经过启发式遗传算法的搜索,都能收敛到最小值点,平均值为:从计算情况可知,在相同精度条件下,启发式遗传算法所用时间大概是遗传算法的四分之一。zhua曲子白渡白颗

目录[+]