精华内容
下载资源
问答
  • 寻优算法结构
    2022-03-15 11:24:46

    【蚁群优化算法、粒子群优化算法、细菌觅食算法、萤火虫算法、人工鱼群算法】

    计算机技术不断发展,算法技术也在不断更新。群体智能 (Swarm Intelligent,SI) 算法始于 20 世纪 90 年代初,主要是受自然界生物群体智能现象的启发,通过模仿社会性动物的行为,而提出的一种随机优化算法。群体智能是基于种群行为对给定的目标进行寻优的启发式搜索算法,其的核心是由众多简单个体组成的群体能够通过相互之间的简单合作来实现某一较复杂的功能。所以群体智能可以在没有集中控制并且缺少全局信息和模型的前提下,为寻找复杂的分布式问题的解决方案提供了基础。

    作为计算智能的一个重要的学科分支,群体智能优化算法是一类通过模仿生物界的遗传进化机理和群体协作行为而提出的仿生类随机搜索算法。该算法以其高效的寻优速度,无需考虑问题的过多初始信息等特点而受到人们的普遍关注。

    群体智能优化算法是一类基于概率的随机搜索进化算法,各个算法之间存在结构、研究内容、计算方法等具有较大的相似性。因此,群体智能优化算法可以建立一个基本的理论框架模式:

    Step1:设置参数,初始化种群;

    Step2:生成一组解,计算其适应值;

    Step3:由个体最有适应着,通过比较得到群体最优适应值;

    Step4:判断终止条件示否满足?如果满足,结束迭代;否则,转向Step2;

    各个群体智能算法之间最大不同在于算法更新规则上,有基于模拟群居生物运动步长更新的(如PSO,AFSA与SFLA),也有根据某种算法机理设置更新规则(如ACO)。

    统一框架下的群体智能优化算法,可以根据优化对象的特性只能地选择适合的更新规则,进行运算得到理想的优化结果。

    蚁群算法(Ant Colony, ACO):是模拟真实的蚁群秘觅食过程寻求最短路径的原理,由意大利学者Dorigo等在20世纪90年代首先提出。最初的蚁群算法成为蚂蚁系统,对于旅行商问题(TSP)及二次分配问题(QAP)等取得了较好效果,经过改进后成为蚂蚁算法或蚁群算法。蚁群算法吸收了蚂蚁群体行为的典型特征:一是能觉察小范围区域内情况,并能判断出是否有食物或其他同类的信息素轨迹;而是释放自己的信息素;三是所遗留的信息素会随时间而逐步减小。蚁群算法通过候选解组织群体的过程来寻求最优解,这个过程包括适应阶段和协作阶段。在适应阶段,各候选解根据积累的信息不断调整自身的结构;在协作阶段各候选解间通过信息交流,以便产生系能更好的解。

    1991 年意大利学者 Dorigo M 等受到自然界中蚁群觅食行为启发而提出了蚁群算法(AntColony Optimization,ACO)。蚁群算法的基本理念是蚁群生物性的利用最短路径的根据局部信息调整路径上的信息素找寻的特征,这个算法的优势非常的明显,而且具有较为突出的应用性,在这个过程中蚂蚁可以逐步地构造问题的可行解,在解的构造期间,每只蚂蚁可以使用概率方式向下一个节点跳转,而且由于这个节点是具有较强信息素和较高启发式因子的方向,直至无法进一步移动。此时,蚂蚁所走路径对应于待求解问题的一个可行解。蚁群算法目前已成功地用于解决旅行商 TSP 问题、数据挖掘、二次指派问题、网络路由优化、机器人路径规划、图着色、物流配送车辆调度、PID 控制参数优化及无线传感器网络等问题。

    1. 蚁群算法的优点:
    1. 蚁群算法与其他启发式算法相比,在求解性能上,具有很强的鲁棒性(对基本蚁群算法模型稍加修改,便可以应用于其他问题)和搜索较好解的能力。
    2. 蚁群算法是一种基于种群的进化算法,具有本质并行性,易于并行实现。
    3. 蚁群算法很容易与多种启发式算法结合,以改善算法性能。
    1. 蚁群算法存在的问题:

    TSP问题是一类经典的组合优化问题,即在给定城市个数和各城市之间距离的条件下,找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果,但是也存在一些不足:

    1. 如果参数设置不当,导致求解速度很慢且所得解的质量特别差。
    2. 基本蚁群算法计算量大,求解所需时间较长。
    3. 基本蚁群算法中理论上要求所有的蚂蚁选择同一路线,该线路即为所求的最优线路;但在实际计算中,在给定一定循环数的条件下很难达到这种情况。

    另一方面,在其它的实际应用中,如图像处理中寻求最优模板问题,我们并不要求所有的蚂蚁都找到最优模板,而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板,反而影响了计算效率。

    蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。

    蚁群算法一般需要较长的搜索时间,其复杂度可以反映这一点;而且该方法容易出现停滞现象,即搜索进行到一定程度后,所有个体发现的解完全一致,不能对解空间进一步进行搜索,不利于发现更好的解。

    粒子群优化算法(Particles warm optimization algorithm, PSO):最早是在1995年由Kennedy和Eberhart提出的一种基于智能启发的全局优化技术演化计算方法,起源于生物学家对鸟群觅食过程行为的观察研究,具有易理解、易实现、全局搜索能力强等特点备受科学工程领域的极大关注。 设想这样一个场景:一群鸟在随机搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是他们当前的位置离食物还有多元。那么找到食物的最优策略是什么呢,最简单有效的搜索目前离食物最近的鸟的周围区域。PSO算法中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为“微粒”,所有的微粒都有一个被优化的函数决定的适应值,每个微粒海有一个速度决定他们飞翔的方向和距离,然后微粒们就追随当前最优微粒在解空间中搜索。PSO算法初始化为一群随机微粒(随机解),然后通过迭代找到最优解,在每次迭代中,微粒通过跟踪两个“极值“来更新自己。第一个就是微粒本身所找到的最优解,这个解成为个体极值;另一个极值是整个种群目前找到的最优解,这个极值是全局极值。

    粒子群算法的优点:

    1. PSO算法没有交叉和变异运算,依靠粒子速度完成搜索,并且在迭代进化中只有最优的粒子把信息传递给其它粒子,搜索速度快;
    2. PSO算法具有记忆性,粒子群体的历史最好位置可以记忆并传递给其它粒子;
    3. 需调整的参数较少,结构简单,易于工程实现;
    4. 采用实数编码,直接由问题的解决定,问题解的变量数直接作为粒子的维数。

    粒子群算法的缺点:

    1. 缺乏速度的动态调节,容易陷入局部最优,导致收敛精度低和不易收敛;
    2. 不能有效解决离散及组合优化问题;
    3. 不能有效求解一些非直角坐标系描述问题,如有关能量场或场内粒子运动规律的求解问题(这些求解空间的边界大部分是基于极坐标、球坐标或柱坐标);
    4. 参数控制,对于不同的问题,如何选择合适的参数来达到最优效果

    细菌觅食算法(BFO)是模拟大肠杆菌在人体肠道内觅食时所表现出来的智能行为而提出的一类智能优化算法,由K.M.Passino于2002年提出。它具有三个典型的行为模式,即趋化行为、复制行为和驱散行为。

    趋化行为指细菌向食物丰富的区域聚集的行为,包括翻转和前进两种模式。前者指细菌朝任意的方向移动一定距离;后者通过判断翻转后细菌的适应度函数值是否得到改善,来决定细菌是否要沿当前方向继续移动。通过这一行为,细菌可获得连续局部寻优的能力。

    复制行为是根据细菌的适应度函数值,选择让较差的细菌继承较好细菌的位置及步长。通过该行为可加快细菌的寻优速度。

    驱散行为是让细菌以一定概率被驱散到搜索空间中的任意位置,通过该行为可以避免细菌陷人局部极值。

    整个菌群通过不断重复这三种行为,形成高效快速的寻优模式。

    从细菌觅食优化算法提出来至今,已经有不少学者对其进行了深入地研究及改进,将其应用到实际工程中。随着研究的不断深入,BFO算法的一-些缺点和问题也随之暴露出来。其中主要集中在算法进行过程中参数的调整方面,包括细菌菌群的大小、细菌趋化的步长、细菌进行中的趋化操作、复制操作和迁移操作的上限次数,用BFO算法优化不同类型的问题时,其参数不具备自适应性,很难保:证求解的精度及收敛速度,因而算法不具备普遍性。

    萤火虫算法(Glowworm Swarn Optimization, GSO) 是2005 年由印度学者 Krishnanand 和 Ghose 提出的通过模拟萤火虫在觅食、求偶和警戒等生活习性中产生的因光而吸引并移动的行为来进行寻优的。萤火虫算法的基本原理是 :用搜索空间中的点模拟自然界中的萤火虫个体,将搜索和优化过程模拟成萤火虫个体的吸引和移动过程,将求解问题的目标函数度量成萤火虫个体所处位置的优劣,将萤火虫个体的优胜略汰过程类比为求解问题目标函数的搜索和优化过程中用好的解取代较差的解的迭代过程。

    萤火虫算法在问题空间随机分布N只萤火虫,这些萤火虫都带有一定的荧光,每个萤火虫都具有自己的感知范围Rdi (0<Rdi <Rs),而RS是最大感知半径。萤火虫实现寻优时,在其感知范围内寻找荧光素值较高的萤火虫,并且会朝着这个方向移动。萤火虫移动之后,其感知半径要进行更新,最后大部分的萤火虫都会聚集在一个或多个极值上。

    1. 优点:萤火虫算法不仅可以优化单峰函数和多峰函数,而且该算法具有较强的局部搜索能力可以在一个娇小的区域内找到该区域的最优解。操作方便、实现简单、参数较少、而且参数对算法的影响较小。
    2. 缺点:萤火虫算法必须要求感知范围内有优秀个体向其提供信息,否则个体将停止搜索,这种搜索方法对优秀个体的依赖程度太高,从而降低了收敛速度;而且,当个体距离峰值非常近时,由于步长可能大于该距离,将导致个体在峰值附近发生震荡现象。

    人工鱼群算法(Artificial Fish-Swarm Algorithm,AFSA):是由李晓磊等在2002年提出的,源于对鱼群运动行为的研究,是一种新型的智能仿生优化算法.在基本的AFSA算法中,主要是利用了鱼群的觅食、聚群和追尾行为,从构造单条鱼的底层行为坐骑,通过鱼群中各个体的局部寻优,达到全局最优值在群体中突显出来的目的。它具有较强的鲁棒性、优良的分布式计算机制、易于和其他方法结合等优点.目前对该算法的研究、应用已经渗透到多个应用领域,并由解决一维静态优化问题发展到解决多维动态组合优化问题。

    2002 年由我国的李晓磊等受鱼群运动行为的启发而提出了人工鱼群算法(Artifi cialFish-Swarm Algorithm,AFSA)。人工鱼群算法的思想主要是利用鱼个体的四种行为(觅食、聚群、追尾和随机)的特征,通过技术应用将人工鱼随机地分布于解空间中,解空间中包含着若干局部最优值和一个全局最优值。在进行应用时,可以有效的利用相关特点进行,特别是应用的寻优期间,每次迭代执行完,人工鱼都将对比自身状态和公告板状态,如自身具有优势,则更新公告板状态,确保公告板为最优状态。 人工鱼群算法已在参数估计、组合优化、前向神经网络优化、电力系统无功优化、输电网规划、边坡稳定、非线性方程求解等方面得到应用,且取得了较好的效果。

    人工鱼群算法的特点:

    1. 只需比较目标函数值,对目标函数的性质要求不高;
    2. 对初值的要求不高,随机产生或设置为固定值均可,鲁棒性强;
    3. 对参数设定的要求不高,容许范围大;
    4. 收敛速度较慢,但是具备并行处理能力;具备较好的全局寻优能力,能快速跳出局部最优点;
    5. 对于一些精读要求不高的场合,可以用它快速得到一个可行解;
    6. 不需要问题的严格机理模型,甚至不需要问题的精确描述,这使得它的应用范围得以延伸。

    发展趋势及展望:蚂蚁优化算法、粒子优化算法等为解决一类优化问题提供了新的思路,众多研究者纷纷给予改进,使之得到了扩展和完善,在解决某些问题方面表现出了比传统优化算法更好的性能,但是单纯对优化算法的研究很难再有其他大的突破。然而,生物群体拥有巨大的潜力供人们研究,目前还没有形成系统的理论,许多问题有待回答。以下几个方面将是研究的热点:刺激产生新的算法的生物群体的行为模型;各种算法的完善和结合在实际问题上的应用;群体机器人的研究;群体智能系统的底层机制的研究;系统的建模、仿真以及实际应用。//生物的奥秘是无穷的,从生物学甚至社会学的角度出发,新的有益的行为模式有待去发现和提炼。

    更多相关内容
  • 函数寻优超参数调节-知乎.zip,函数寻优超参数调节-知乎,PSO-2参数-无约束,RunPSO.m,find_Schaffer.m,yan.m,111,target.m,PSO.gif,PSO.m
  • 麻雀搜索算法(Sparrow Search Algorithm, SSA)是...相比传统算法,麻雀搜索算法结构简单、易于实现,且控制参数较少,局部搜索能力较强。该算法在单峰、多峰等基准函数上的表现优于粒子群算法、蚁群算法等传统算法
  • 基于猎人猎物优化算法的函数寻优算法

    千次阅读 热门讨论 2022-01-25 11:56:57
    文章目录一、理论基础1、猎人猎物优化算法2、HPO算法流程图二、仿真实验...所有优化算法的总体结构基本相同。首先,将初始总体随机设置为(x→)={x→1,x→2,⋯ ,x→n}(\overrightarrow x)=\{\overrightarrow x_1,\over

    一、理论基础

    1、猎人猎物优化算法

    本文提出了一种新的基于种群的优化算法—猎人猎物优化算法(Hunter–prey optimizer, HPO)。该算法的灵感来源于狮子、豹子和狼等食肉动物,以及鹿和羚羊等猎物的行为。
    所有优化算法的总体结构基本相同。首先,将初始总体随机设置为 ( x → ) = { x → 1 , x → 2 , ⋯   , x → n } (\overrightarrow x)=\{\overrightarrow x_1,\overrightarrow x_2,\cdots,\overrightarrow x_n\} (x )={x 1,x 2,,x n},然后将种群总体所有成员的目标函数计算为 ( O → ) = { O 1 , O 2 , ⋯   , O n } (\overrightarrow O)=\{O_1,O_2,\cdots,O_n\} (O )={O1,O2,,On}。受该算法启发,通过一系列规则和策略在搜索空间中控制和引导种群。重复此过程,直到算法停止。 在每次迭代中,根据该算法的规则更新群体中每个成员的位置,并用目标函数评估新位置,这个过程会使解决方案随着每次迭代而优化。初始群体中每个成员的位置由式(1)在搜索空间中随机生成。 x i = r a n d ( 1 , d ) . ∗ ( u b − l b ) + l b (1) x_i=rand(1,d).*(ub-lb)+lb\tag{1} xi=rand(1,d).(ublb)+lb(1)其中, x i x_i xi是猎人或猎物的位置, l b lb lb是问题变量的最小值(下界), u b ub ub是问题变量的最大值(上界), d d d是问题变量的数量(维度)。式(2)定义了搜索空间的下界和上界。需要注意的是,一个问题的所有变量的上下限可能相同或不同。 l b = [ l b 1 , l b 2 , ⋯   , l b d ] ,    u b = [ u b 1 , u b 2 , ⋯   , u b d ] (2) lb=[lb_1,lb_2,\cdots,lb_d],\,\,ub=[ub_1,ub_2,\cdots,ub_d]\tag{2} lb=[lb1,lb2,,lbd],ub=[ub1,ub2,,ubd](2)生成初始总体并确定每个代理的位置后,使用目标函数 O i = f ( x → ) O_i=f(\overrightarrow x) Oi=f(x )计算每个解的适应度值。 F ( x ) F(x) F(x)可以是最大值(效率、性能等)或最小值(成本、时间等)。搜索机制通常包括两个步骤:探索和开发。探索是指算法倾向于高度随机的行为,因此解决方案会发生显著变化。解决方案的重大变化促使猎人进一步探索搜索空间,并发现其有希望的领域。在发现有希望的区域后,必须减少随机行为,以便算法能够在有希望的区域周围搜索,这就是开发。
    对于猎人的搜索机制,式(3)给出了其数学模型: x i , j ( t + 1 ) = x i , j ( t ) + 0.5 [ ( 2 C Z P p o s ( j ) − x i , j ( t ) ) + ( 2 ( 1 − C ) Z μ ( j ) − x i , j ( t ) ) ] (3) x_{i,j}(t+1)=x_{i,j}(t)+0.5\left[(2CZP_{pos(j)}-x_{i,j}(t))+(2(1-C)Z{\mu(j)}-x_{i,j}(t))\right]\tag{3} xi,j(t+1)=xi,j(t)+0.5[(2CZPpos(j)xi,j(t))+(2(1C)Zμ(j)xi,j(t))](3)其中, x ( t ) x(t) x(t)是当前猎人位置, x ( t + 1 ) x(t+1) x(t+1)是猎人的下一次迭代位置, P p o s P_{pos} Ppos是猎物的位置, μ \mu μ是所有位置的平均值, Z Z Z是由式(4)计算的自适应参数: P = R → 1 < C ;    I D X = ( P = = 0 ) ; Z = R 2 ⊗ I D X + R → 3 ⊗ ( ∼ I D X ) (4) \begin{array}{l}P=\overrightarrow R_1<C;\,\,IDX=(P==0);\\Z=R_2\otimes IDX+\overrightarrow R_3\otimes(\sim IDX)\end{array}\tag{4} P=R 1<C;IDX=(P==0);Z=R2IDX+R 3(IDX)(4)其中, R → 1 \overrightarrow R_1 R 1 R → 3 \overrightarrow R_3 R 3 [ 0 , 1 ] [0,1] [0,1]内的随机向量, P P P R → 1 < C \overrightarrow R_1<C R 1<C的索引值, R 2 R_2 R2 [ 0 , 1 ] [0,1] [0,1]内的随机数, I D X IDX IDX是满足条件( P = = 0 P==0 P==0)的向量 R → 1 \overrightarrow R_1 R 1的索引值, C C C是探索和开发之间的平衡参数,其值在迭代过程中从1减小到0.02,计算如下: C = 1 − i t ( 0.98 M a x I t ) (5) C=1-it\left(\frac{0.98}{MaxIt}\right)\tag{5} C=1it(MaxIt0.98)(5)其中, i t it it是当前迭代次数, M a x I t MaxIt MaxIt是最大迭代次数。计算猎物的位置( P p o s P_{pos} Ppos),以便首先根据式(6)计算所有位置的平均值( μ \mu μ),然后计算每个搜索代理与该平均位置的距离。 μ = 1 n ∑ i = 1 n x → i (6) \mu=\frac1n\sum_{i=1}^n\overrightarrow x_i\tag{6} μ=n1i=1nx i(6)根据式(7)计算欧几里得距离: D e u c ( i ) = ( ∑ j = 1 d ( x i , j − μ j ) 2 ) 1 2 (7) D_{euc(i)}=\left(\sum_{j=1}^d(x_{i,j}-\mu_j)^2\right)^{\frac12}\tag{7} Deuc(i)=(j=1d(xi,jμj)2)21(7)根据式(8),距离位置平均值最大的搜索代理被视为猎物( P p o s P_{pos} Ppos): P → p o s = x → i ∣ i    i s    i n d e x    o f    M a x ( e n d )    s o r t ( D e u c ) (8) \overrightarrow P_{pos}=\overrightarrow x_i|i\,\,is\,\,index\,\,of\,\,Max(end)\,\,sort(D_{euc})\tag{8} P pos=x iiisindexofMax(end)sort(Deuc)(8)如果每次迭代都考虑到搜索代理与平均位置( μ \mu μ)之间的最大距离,则该算法将具有延迟收敛性。根据狩猎场景,当猎人捕获猎物时,猎物会死亡,而下一次,猎人会移动到新的猎物位置。为了解决这个问题,考虑一种递减机制,如式(9)所示: k b e s t = r o u n d ( C × N ) (9) kbest=round(C\times N)\tag{9} kbest=round(C×N)(9)其中 N N N是搜索代理的数量。
    改变式(8),将猎物的位置计算为式(10): P → p o s = x → i ∣ i    i s    s o r t e d    D e u c ( k b e s t ) (10) \overrightarrow P_{pos}=\overrightarrow x_i|i\,\,is\,\,sorted\,\,D_{euc}(kbest)\tag{10} P pos=x iiissortedDeuc(kbest)(10)在算法开始时, k b e s t kbest kbest的值等于 N N N。因此,最后一个距离搜索代理的平均位置( μ \mu μ)最远的搜索代理被选择为猎物,并被猎人捕获。
    假设最佳安全位置是最佳全局位置,因为这将使猎物有更好的生存机会,猎人可能会选择另一个猎物。式(11)用于更新猎物位置: x i , j ( t + 1 ) = T p o s ( j ) + C Z cos ⁡ ( 2 π R 4 ) × ( T p o s ( j ) − x i , j ( t ) ) (11) x_{i,j}(t+1)=T_{pos(j)}+CZ\cos(2\pi R_4)\times(T_{pos(j)}-x_{i,j}(t))\tag{11} xi,j(t+1)=Tpos(j)+CZcos(2πR4)×(Tpos(j)xi,j(t))(11)其中, x ( t ) x(t) x(t)是猎物的当前位置; x ( t + 1 ) x(t+1) x(t+1)是猎物的下一次迭代位置; T p o s T_{pos} Tpos是全局最优位置; Z Z Z是由式(4)计算的自适应参数; R 4 R_4 R4是范围 [ − 1 , 1 ] [-1,1] [1,1]内的随机数; C C C是探索和开发之间的平衡参数,其值在算法的迭代过程中减小,并由式(5)计算; cos ⁡ \cos cos函数及其输入参数允许下一个猎物位置在不同半径和角度的全局最优位置,并提高开发阶段的性能。
    为了选择猎人和猎物,结合式(3)和(11)提出了式(12): x i ( t + 1 ) = { x i ( t ) + 0.5 [ ( 2 C Z P p o s ( j ) − x i ( t ) ) + ( 2 ( 1 − C ) Z μ ( j ) − x i ( t ) ) ] i f    R 5 < β ( 12 a ) T p o s + C Z cos ⁡ ( 2 π R 4 ) × ( T p o s − x i ( t ) ) e l s e ( 12 b ) (12) x_i(t+1)=\begin{dcases}x_i(t)+0.5\left[(2CZP_{pos(j)}-x_{i}(t))+(2(1-C)Z{\mu(j)}-x_{i}(t))\right]\quad if \,\,R_5<\beta(12a)\\T_{pos}+CZ\cos(2\pi R_4)\times(T_{pos}-x_{i}(t))\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad else(12b)\end{dcases}\tag{12} xi(t+1)={xi(t)+0.5[(2CZPpos(j)xi(t))+(2(1C)Zμ(j)xi(t))]ifR5<β(12a)Tpos+CZcos(2πR4)×(Tposxi(t))else(12b)(12)其中, R 5 R_5 R5 [ 0 , 1 ] [0,1] [0,1]范围内的随机数, β \beta β是一个调节参数,在本文中的值设置为0.1。如果 R 5 R_5 R5值小于 β \beta β,搜索代理将被视为猎人,搜索代理的下一个位置将用式(12a)更新;如果 R 5 R_5 R5值大于 β \beta β,搜索代理将被视为猎物,搜索代理的下一个位置将用式(12b)更新。

    2、HPO算法流程图

    所提出算法的流程图如图1所示。
    在这里插入图片描述

    图1 HPO算法流程图

    二、仿真实验与结果分析

    将HPO与PSO、TSA、LFD、HHO和WOA进行对比,实验设置种群规模为30,最大迭代次数为500,每种算法独立运行30次,以文献[1]中30维的F3、F4、F5(单峰函数)、F10、F11、F12(多峰函数)为例,结果显示如下:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    函数:F3
    PSO:最差值: 1655.3088, 最优值: 144.4169, 平均值: 705.5008, 标准差: 374.0712, 秩和检验: 3.0199e-11
    TSA:最差值: 0.0014177, 最优值: 6.3681e-09, 平均值: 0.00010689, 标准差: 0.00027107, 秩和检验: 3.0199e-11
    LFD:最差值: 2.7324e-05, 最优值: 1.609e-06, 平均值: 1.0413e-05, 标准差: 6.5274e-06, 秩和检验: 3.0199e-11
    HHO:最差值: 1.9747e-73, 最优值: 7.5816e-97, 平均值: 7.3121e-75, 标准差: 3.6064e-74, 秩和检验: 3.0199e-11
    WOA:最差值: 77911.2649, 最优值: 22160.2961, 平均值: 49304.8815, 标准差: 13888.0351, 秩和检验: 3.0199e-11
    HPO:最差值: 2.125e-144, 最优值: 4.8337e-159, 平均值: 7.0978e-146, 标准差: 3.8795e-145, 秩和检验: 1
    函数:F4
    PSO:最差值: 9.2222, 最优值: 2.6354, 平均值: 5.5985, 标准差: 1.7375, 秩和检验: 3.0199e-11
    TSA:最差值: 1.5538, 最优值: 0.018393, 平均值: 0.3713, 标准差: 0.3628, 秩和检验: 3.0199e-11
    LFD:最差值: 0.0011982, 最优值: 0.00037569, 平均值: 0.00076243, 标准差: 0.00022244, 秩和检验: 3.0199e-11
    HHO:最差值: 4.1015e-48, 最优值: 2.2482e-64, 平均值: 2.8774e-49, 标准差: 8.865e-49, 秩和检验: 3.0199e-11
    WOA:最差值: 90.8896, 最优值: 0.63375, 平均值: 48.1807, 标准差: 25.9539, 秩和检验: 3.0199e-11
    HPO:最差值: 1.9138e-76, 最优值: 4.679e-83, 平均值: 2.0117e-77, 标准差: 5.0094e-77, 秩和检验: 1
    函数:F5
    PSO:最差值: 3265.9273, 最优值: 395.2169, 平均值: 1310.819, 标准差: 709.752, 秩和检验: 3.0199e-11
    TSA:最差值: 32.6867, 最优值: 26.4304, 平均值: 28.5989, 标准差: 0.98266, 秩和检验: 3.0199e-11
    LFD:最差值: 28.2876, 最优值: 27.6816, 平均值: 28.0259, 标准差: 0.1791, 秩和检验: 3.0199e-11
    HHO:最差值: 0.046694, 最优值: 2.1425e-05, 平均值: 0.011778, 标准差: 0.013516, 秩和检验: 3.0199e-11
    WOA:最差值: 28.7441, 最优值: 27.1566, 平均值: 27.9145, 标准差: 0.45396, 秩和检验: 3.0199e-11
    HPO:最差值: 26.0057, 最优值: 23.1074, 平均值: 23.6597, 标准差: 0.56852, 秩和检验: 1
    函数:F10
    PSO:最差值: 8.7096, 最优值: 3.4325, 平均值: 5.3647, 标准差: 1.0923, 秩和检验: 1.2118e-12
    TSA:最差值: 3.4079, 最优值: 1.8519e-12, 平均值: 1.8109, 标准差: 1.5196, 秩和检验: 1.2118e-12
    LFD:最差值: 0.00036925, 最优值: 0.00017272, 平均值: 0.00026293, 标准差: 5.3357e-05, 秩和检验: 1.2118e-12
    HHO:最差值: 8.8818e-16, 最优值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0, 秩和检验: NaN
    WOA:最差值: 7.9936e-15, 最优值: 8.8818e-16, 平均值: 4.7962e-15, 标准差: 2.8529e-15, 秩和检验: 1.2954e-08
    HPO:最差值: 8.8818e-16, 最优值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0, 秩和检验: NaN
    函数:F11
    PSO:最差值: 24.4352, 最优值: 4.6305, 平均值: 12.1824, 标准差: 4.3481, 秩和检验: 1.2118e-12
    TSA:最差值: 0.028988, 最优值: 0, 平均值: 0.0084913, 标准差: 0.0095626, 秩和检验: 5.375e-06
    LFD:最差值: 8.1923e-08, 最优值: 4.2355e-09, 平均值: 2.0162e-08, 标准差: 1.828e-08, 秩和检验: 1.2118e-12
    HHO:最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0, 秩和检验: NaN
    WOA:最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0, 秩和检验: NaN
    HPO:最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0, 秩和检验: NaN
    函数:F12
    PSO:最差值: 11.6649, 最优值: 1.0804, 平均值: 4.175, 标准差: 2.1919, 秩和检验: 3.0199e-11
    TSA:最差值: 13.0908, 最优值: 0.67667, 平均值: 7.3373, 标准差: 3.9204, 秩和检验: 3.0199e-11
    LFD:最差值: 0.12132, 最优值: 0.0007559, 平均值: 0.012568, 标准差: 0.028406, 秩和检验: 3.0199e-11
    HHO:最差值: 2.7599e-05, 最优值: 3.2155e-09, 平均值: 6.3657e-06, 标准差: 7.7866e-06, 秩和检验: 4.9752e-11
    WOA:最差值: 0.065805, 最优值: 0.0065428, 平均值: 0.023731, 标准差: 0.015485, 秩和检验: 3.0199e-11
    HPO:最差值: 1.9617e-07, 最优值: 3.1496e-11, 平均值: 6.9024e-09, 标准差: 3.5754e-08, 秩和检验: 1
    

    实验结果表明:所提出的HPO算法对解决单峰和多峰问题具有足够的探索和开发能力,与其他优化算法相比,HPO算法的性能更优越。

    三、参考文献

    [1] Naruei, I., Keynia, F., Sabbagh Molahosseini, A. Hunter-prey optimization: algorithm and applications[J]. Soft Computing, 2022, 26: 1279-1314.

    展开全文
  • 适应性粒子群寻优算法.pdf
  • 神经网络遗传算法函数极值寻优——非线性函数极值寻优
  • 协方差矩阵自适应进化策略(Covariance matrix adaptive evolution strategy, CMA-ES)是Nikolaus Hansen等人提出的一种新的无约束优化算法,已成功应用于全局优化、多峰优化、多目标优化、大规模优化和结构工程等领域...
  • 为了在多粒度空间中寻找一个合适的粒度空间来对不确定性目标概念进行近似描述,使误分类代价与测试代价之和尽可能小,给出属性代价贡献率的定义,并提出一种代价敏感的粒度寻优算法.实验结果表明,所提出算法能适用于...
  • 遗传算法与模拟退火法寻优能力综述.pdf
  • 文章目录一、理论基础1、晶体结构算法2、CryStAl伪代码二、仿真实验与结果分析三、参考文献 一、理论基础 1、晶体结构算法 晶体结构算法(Crystal Structure Algorithm, CryStAl)由伊朗的Siamak Talatahari等人于2021...

    一、理论基础

    1、晶体结构算法

    晶体结构算法(Crystal Structure Algorithm, CryStAl)由伊朗的Siamak Talatahari等人于2021年提出,该算法的主要灵感来源于从点阵点添加基形成晶体结构的基本原理。
    在该模型中,优化算法的每个候选解都被视为空间中的一个单晶。为了进行迭代优化,首先随机确定一些晶体进行初始化。 C r = [ C r 1 C r 2 ⋮ C r i ⋮ C r n ] = [ x 1 1 x 1 2 ⋯ x 1 j ⋯ x 1 d x 2 1 x 2 2 ⋯ x 2 j ⋯ x 2 d ⋮ ⋮ ⋮ ⋱ ⋮ x i 1 x i 2 ⋯ x i j ⋯ x i d ⋮ ⋮ ⋮ ⋱ ⋮ x n 1 x n 2 ⋯ x n j ⋯ x n d ] ,    { i = 1 , 2 , ⋯   , n j = 1 , 2 , ⋯   , d (1) Cr=\begin{bmatrix}Cr_1\\Cr_2\\\vdots\\Cr_i\\\vdots\\Cr_n\end{bmatrix}=\begin{bmatrix} x_1^1 & x_1^2 & \cdots & x_1^j & \cdots & x_1^d \\x_2^1 & x_2^2 & \cdots & x_2^j & \cdots & x_2^d \\\vdots & \vdots & & \vdots & \ddots & \vdots \\x_i^1 & x_i^2 & \cdots & x_i^j & \cdots & x_i^d \\ \vdots & \vdots & & \vdots & \ddots & \vdots \\ x_n^1 & x_n^2 & \cdots & x_n^j & \cdots & x_n^d \end{bmatrix},\,\,\begin{dcases}i=1,2,\cdots,n\\j=1,2,\cdots,d\end{dcases}\tag{1} Cr=Cr1Cr2CriCrn=x11x21xi1xn1x12x22xi2xn2x1jx2jxijxnjx1dx2dxidxnd,{i=1,2,,nj=1,2,,d(1)其中, n n n是晶体(候选解)的数量, d d d是问题的维度。这些晶体的初始位置在搜索空间中随机确定,如下所示: x i j ( 0 ) = x i , min ⁡ j + ξ ( x i , max ⁡ j − x i , min ⁡ j ) ,    { i = 1 , 2 , ⋯   , n j = 1 , 2 , ⋯   , d (2) x_i^j(0)=x_{i,\min}^j+\xi(x_{i,\max}^j-x_{i,\min}^j),\,\,\begin{dcases}i=1,2,\cdots,n\\j=1,2,\cdots,d\end{dcases}\tag{2} xij(0)=xi,minj+ξ(xi,maxjxi,minj),{i=1,2,,nj=1,2,,d(2)其中, x i j ( 0 ) x_i^j(0) xij(0)确定晶体的初始位置; x i , min ⁡ j x_{i,\min}^j xi,minj x i , max ⁡ j x_{i,\max}^j xi,maxj分别是第 i i i个候选解的第 j j j个决策变量的最小和最大允许值; ξ \xi ξ是一个 [ 0 , 1 ] [0,1] [0,1]区间内的随机数。
    根据晶体学中的“基”概念,角上的所有晶体都被视为主晶体 C r m a i n Cr_{main} Crmain,通过考虑初始生成的晶体(候选解)随机确定。应该注意的是,每个步骤的随机选择过程是通过省略当前 C r Cr Cr来确定的。具有最佳配置的晶体被确定为 C r b Cr_b Crb,而随机选择的晶体的平均值用 F c F_c Fc表示。
    为了更新候选解在搜索空间中的位置,考虑了基本格原理,其中确定了以下四种更新过程:

    1. 简易隔室: C r n e w = C r o l d + r C r m a i n (3) Cr_{new}=Cr_{old}+rCr_{main}\tag{3} Crnew=Crold+rCrmain(3)
    2. 包含最优晶体的隔室: C r n e w = C r o l d + r 1 C r m a i n + r 2 C r b (4) Cr_{new}=Cr_{old}+r_1Cr_{main}+r_2Cr_b\tag{4} Crnew=Crold+r1Crmain+r2Crb(4)
    3. 包含平均晶体的隔室: C r n e w = C r o l d + r 1 C r m a i n + r 2 F c (5) Cr_{new}=Cr_{old}+r_1Cr_{main}+r_2F_c\tag{5} Crnew=Crold+r1Crmain+r2Fc(5)
    4. 包含最优晶体和平均晶体的隔室: C r n e w = C r o l d + r 1 C r m a i n + r 2 C r b + r 3 F c (6) Cr_{new}=Cr_{old}+r_1Cr_{main}+r_2Cr_b+r_3F_c\tag{6} Crnew=Crold+r1Crmain+r2Crb+r3Fc(6)其中,在上述四个等式中, C r n e w Cr_{new} Crnew是新位置, C r o l d Cr_{old} Crold是旧位置, r r r r 1 r_1 r1 r 2 r_2 r2 r 3 r_3 r3均为 [ − 1 , 1 ] [-1,1] [1,1]的随机数。

    值得一提的是,作为元启发式算法的两个关键特征,探索和开发在该算法中得到了保证,通过式(4)到式(7)同时进行局部和全局搜索。为了处理违反变量边界条件的解变量 x i j x_i^j xij,定义了一个flag,其中对于变量范围外的 x i j x_i^j xij,flag命令违反变量的边界改变。终止标准是基于最大迭代次数考虑的,其中优化过程在固定的迭代次数后终止。

    2、CryStAl伪代码

    CryStAl伪代码如图1所示。
    在这里插入图片描述

    图1 CryStAl算法伪代码

    二、仿真实验与结果分析

    将CryStAl与SSA、MFO、MVO和SCA进行对比,以常用23个测试函数的F1、F2(单峰函数/30维)、F9、F10(多峰函数/30维)、F18、F19(固定维度多峰函数/2维、3维)为例,实验设置种群规模为50,最大迭代次数为1000,每种算法独立运算30次,结果显示如下:
    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

    函数:F1
    SSA:最差值: 1.1521e-08,最优值:6.5816e-09,平均值:9.1439e-09,标准差:1.5234e-09,秩和检验:3.0199e-11
    MFO:最差值: 10000,最优值:3.4669e-06,平均值:2333.3334,标准差:4301.8307,秩和检验:3.0199e-11
    MVO:最差值: 0.30711,最优值:0.088964,平均值:0.19896,标准差:0.051538,秩和检验:3.0199e-11
    SCA:最差值: 0.020153,最优值:9.1494e-09,平均值:0.0022384,标准差:0.0045475,秩和检验:3.0199e-11
    CryStAl:最差值: 1.4154e-21,最优值:3.9076e-33,平均值:8.1479e-23,标准差:2.6898e-22,秩和检验:1
    函数:F2
    SSA:最差值: 2.2252,最优值:0.00024429,平均值:0.429,标准差:0.56186,秩和检验:3.0199e-11
    MFO:最差值: 80,最优值:7.2456e-05,平均值:30.0001,标准差:21.9717,秩和检验:3.0199e-11
    MVO:最差值: 0.88101,最优值:0.15069,平均值:0.29942,标准差:0.13562,秩和检验:3.0199e-11
    SCA:最差值: 2.0238e-05,最优值:8.236e-09,平均值:3.2206e-06,标准差:5.6825e-06,秩和检验:3.0199e-11
    CryStAl:最差值: 7.5549e-11,最优值:1.2467e-17,平均值:1.4583e-11,标准差:2.2825e-11,秩和检验:1
    函数:F9
    SSA:最差值: 98.5006,最优值:13.9294,平均值:53.4955,标准差:17.3332,秩和检验:1.2118e-12
    MFO:最差值: 251.1547,最优值:77.6065,平均值:158.1764,标准差:36.4213,秩和检验:1.2118e-12
    MVO:最差值: 226.9633,最优值:64.7372,平均值:126.9481,标准差:40.9522,秩和检验:1.2118e-12
    SCA:最差值: 52.3055,最优值:1.2428e-06,平均值:8.1638,标准差:16.7671,秩和检验:1.2118e-12
    CryStAl:最差值: 0,最优值:0,平均值:0,标准差:0,秩和检验:NaN
    函数:F10
    SSA:最差值: 3.9825,最优值:2.1058e-05,平均值:1.7234,标准差:0.93524,秩和检验:2.9991e-11
    MFO:最差值: 19.963,最优值:0.0014421,平均值:13.294,标准差:8.2212,秩和检验:2.9991e-11
    MVO:最差值: 1.9301,最优值:0.11851,平均值:0.74551,标准差:0.63754,秩和检验:2.9991e-11
    SCA:最差值: 20.2654,最优值:6.6981e-06,平均值:14.0588,标准差:8.8633,秩和检验:2.9991e-11
    CryStAl:最差值: 1.2563e-11,最优值:8.8818e-16,平均值:8.7047e-13,标准差:2.3078e-12,秩和检验:1
    函数:F18
    SSA:最差值: 3,最优值:3,平均值:3,标准差:1.0603e-13,秩和检验:3.0142e-11
    MFO:最差值: 3,最优值:3,平均值:3,标准差:1.4019e-15,秩和检验:2.5046e-11
    MVO:最差值: 3,最优值:3,平均值:3,标准差:3.7556e-07,秩和检验:3.0199e-11
    SCA:最差值: 3,最优值:3,平均值:3,标准差:7.9049e-06,秩和检验:6.2828e-06
    CryStAl:最差值: 3.0002,最优值:3,平均值:3,标准差:4.2419e-05,秩和检验:1
    函数:F19
    SSA:最差值: -3.8628,最优值:-3.8628,平均值:-3.8628,标准差:8.4614e-15,秩和检验:3.0029e-11
    MFO:最差值: -3.8628,最优值:-3.8628,平均值:-3.8628,标准差:2.7101e-15,秩和检验:1.2118e-12
    MVO:最差值: -3.8628,最优值:-3.8628,平均值:-3.8628,标准差:3.7259e-07,秩和检验:3.0199e-11
    SCA:最差值: -3.8531,最优值:-3.8622,平均值:-3.8558,标准差:0.002796,秩和检验:3.0199e-11
    CryStAl:最差值: -3.8625,最优值:-3.8628,平均值:-3.8627,标准差:6.4015e-05,秩和检验:1
    

    实验结果表明:CryStAl算法在大多数情况下优于其他元启发式算法。

    三、参考文献

    [1] S. Talatahari, M. Azizi, M. Tolouei, et al. Crystal Structure Algorithm (CryStAl): A Metaheuristic Optimization Method[J]. IEEE Access, 2021, 9: 71244-71261.

    展开全文
  • 本文首先详细的介绍了遗传算法。之后通过对比基于遗传算法和非线性寻优算法相结合和普通的遗传算法在寻优上的差异。得出了基于遗传算法和非线性寻优算法相结合寻优能力更强的结论。并给出了MATLAB代码实现......

    一、理论基础

    1、非线性规划

      非线性规划是20世纪50年代形成的一门新兴学科。1951年库恩和塔克发表的关于最优性条件(后来称为库恩·塔克条件)的论文是非线性规划诞生的标志。非线性规划研究一 n n n元实函数在一组等式或不等式的约束条件下的极值问题,非线性规划的理论来源于1951年库恩·塔克建立的最优条件。20世纪50年代,非线性规划的研究主要注重对梯度法和牛顿法的研究,以Davidon(1959)、Fletcher和Powell(1963)提出的DFP方法为代表。20世纪60年代侧重于对牛顿方法和共轭梯度法的研究,其中以由Broyden、Fletcher,Goldfarb 和Shanno从不同角度共同提出的BFGS方法为代表。20世纪70年代是非线性规划飞速发展时期,约束变尺度(SQP)方法(Han和Powell为代表)和Lagrange乘子法(代表人物是Powell和Hestenes)为这一时期的主要研究成果。20世纪80年代以来,随着计算机技术的快速发展,非线性规划方法取得了长足进步,在信赖域法、稀疏拟牛顿法、并行计算、内点法和有限储存法等领域取得了丰硕的研究成果。

    2、非线性规划函数

      函数fmincon是MATLAB最优化工具箱中求解非线性规划问题的函数,它从一个预估
    值出发,搜索约束条件下非线性多元函数的最小值。
      函数fmincon的约束条件为

    min ⁡ f ( x ) = { c ( x ) ≤ 0 c e q ( x ) = 0 A ⋅ x ≤ b A e q ⋅ x = b e q l b ≤ x ≤ u b (2-1) \min f(x) = \begin{cases} c(x) \leq 0 \\ ceq(x) = 0 \\ A·x \leq b \\ Aeq·x = beq \\ lb \leq x \leq ub \\ \end{cases}\tag{2-1} minf(x)= c(x)0ceq(x)=0AxbAeqx=beqlbxub(2-1)
       其中, x 、 b 、 b e q 、 I b 和 u b 是矢量; A 和 A e q 为矩阵; c ( x ) 和 c e q ( x ) 返回矢量的函数; f ( x ) 、 c ( x ) 和 c e q ( x ) 是非线性函数。 其中,x、b、beq、Ib和ub是矢量;A和Aeq为矩阵;c(x)和ceq(x)返回矢量的函数;f(x)、c(x)和ceq(x)是非线性函数。 其中,xbbeqIbub是矢量;AAeq为矩阵;c(x)ceq(x)返回矢量的函数;f(x)c(x)ceq(x)是非线性函数。
    函数fmincon的基本用法为
    x = f m i n c o n ( f u n , x 0 , A , b ) x= fmincon(fun,x0,A,b) x=fmincon(fun,x0,A,b)
    x = f m i n c o n ( f u n , x 0 , A , b , A e q , b e q ) x = fmincon(fun, x0, A,b, Aeq, beq) x=fmincon(fun,x0,A,b,Aeq,beq)
    x = f m i n c o n ( f u n , x 0 , A , b , A e q , b e q , l b , u b ) x = fmincon(fun, x0, A,b, Aeq, beq, lb, ub) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)
    x = f m i n c o n ( f u n , x o , A , b , A e q , b e q , l b , u b , n o n l c o n ) x= fmincon(fun, xo,A, b, Aeq, beq, lb, ub, nonlcon) x=fmincon(fun,xo,A,b,Aeq,beq,lb,ub,nonlcon)
    x = f m i n c o n ( f u n , x o , A , b , A e q , b e q , l b , u b , n o n l c o n , o p t i o n s ) x = fmincon(fun, xo, A,b, Aeq, beq, lb, ub, nonlcon, options) x=fmincon(fun,xo,A,b,Aeq,beq,lb,ub,nonlcon,options)
    其中, n o n l c o n nonlcon nonlcon为非线性约束条件; I b Ib Ib u b ub ub分别为 x x x的下界和上界。当函数输人参数不包括 A 、 b 、 A e q 、 b e q 时 , 默认 A = 0 、 b = 0 , A e q = [ ] 、 b e q = [ ] A、b、Aeq、beq时,默认A=0、b=0,Aeq=[]、beq=[] AbAeqbeq,默认A=0b=0,Aeq=[]beq=[] x 0 x0 x0 x x x的初设值。

    3、遗传算法基本思想

    1)、算法介绍

      一些介绍可以不看
      遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索算法难以解决的复杂和非线性优化问题。目前,遗传算法已被广泛应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域,并在这些领域中取得了良好的成果。与传统搜索算法不同,遗传算法从随机产生的初始解开始搜索,通过一定的选择、交叉、变异操作逐步迭代以产生新的解。群体中的每个个体代表问题的一个解,称为染色体,染色体的好坏用适应度值来衡量,根据适应度的好坏从上一代中选择一定数量的优秀个体,通过交叉、变异形成下一代群体。经过若干代的进化之后,算法收敛于最好的染色体,它即是问题的最优解或次优解。
      遗传算法提供了求解非线性规划的通用框架,它不依赖于问题的具体领域。遗传算法的优点是将问题参数编码成染色体后进行优化,而不针对参数本身,从而不受函数约束条件的限制;搜索过程从问题解的一个集合开始,而不是单个个体,具有隐含并行搜索特性,可大大减少陷人局部最小的可能性。而且优化计算时算法不依赖于梯度信息,且不要求目标函数连续及可导,使其适于求解传统搜索方法难以解决的大规模、非线性组合优化问题。

    2)、算法执行过程

      遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体
      染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码。
      初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群
      这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解
      遗传算法过程图解

    Created with Raphaël 2.3.0 种群初始化 计算各个体的适应度 选择操作 交叉操作 变异操作 是否达到迭代次数 结束 yes no

    3)、 相关生物学术语

      为了大家更好了解遗传算法,在此之前先简单介绍一下相关生物学术语,大家了解一下即可。

    生物遗传概念遗传算法中的作用
    适者生存算法停止时,最优目标值的可行解有最大的可能被留住
    个体可行解
    染色体可行解的编码
    基因可行解中每一分量的特征
    适应性适应度函数值
    种群根据适应度函数值选取的一组可行解
    优胜劣汰从种群中选择若干个个体。是一种基于适应度的优胜劣汰的过程。(选择)
    交配通过交配原则产生一组新可行解的过程(交叉)
    变异编码的某一分量发生变化的过程

    4) 、实现流程

      遗传算法中每一条染色体,对应着遗传算法的一个解决方案,一般我们用适应性函数(fitness function)来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。遗传算法的实现过程实际上就像自然界的进化过程那样。
      下面我们用袋鼠跳中的步骤一一对应解释,以方便大家理解:

    • 首先寻找一种对问题潜在解进行"数字化"编码的方案。(建立表现型和基因型的映射关系)
    • 随机初始化一个种群(那么第一批袋鼠就被随意地分散在山脉上),种群里面的个体就是这些数字化的编码。
    • 接下来,通过适当的解码过程之后(得到袋鼠的位置坐标)。
    • 用适应度函数对每一个基因个体作一次适应度评估(袋鼠爬得越高当然就越好,所以适应度相应越高)
    • 用选择函数按照某种规定择优选择(每隔一段时间,射杀一些所在海拔较低的袋鼠,以保证袋鼠总体数目持平)。
    • 让个体基因变异(让袋鼠随机地跳一跳)。
    • 然后产生子代(希望存活下来的袋鼠是多产的,并在那里生儿育女)。
        遗传算法并不保证你能获得问题的最优解,但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找"最优解。(你不必去指导袋鼠向那边跳,跳多远)。而只要简单的“否定"一些表现不好的个体就行了。(把那些总是爱走下坡路的袋鼠射杀,这就是遗传算法的精粹!)
        由此我们可以得出遗传算法的一般步骤:
    • 随机产生种群。
    • 根据策略判断个体的适应度,是否符合优化准则,若符合,输出最佳个体及其最优解,结束。否则,进行下一步。
    • 依据适应度选择父母,适应度高的个体被选中的概率高,适应度低的个体被淘汰。
    • 用父母的染色体按照一定的方法进行交叉,生成子代。
    • 对子代染色体进行变异。
    • 由交叉和变异产生新一代种群,返回步骤2,直到最优解产生。

    5)、 实现细节

    5.1、编码

      编码是应用遗传算法时要解决的首要问题,也是设计遗传算法时的一个关键步骤。编码方法影响到交叉算子、变异算子等遗传算子的运算方法,很大程度上决定了遗传进化的效率。迄今为止人们已经提出了许多种不同的编码方法。总的来说,这些编码方法可以分为三大类:二进制编码法、浮点编码法、符号编码法。下面分别进行介绍。

    5.1.1、二进制编码

      就像人类的基因有AGCT4种碱基序列一样。不过在这里我们只用了0和1两种碱基,然后将它们串成一条链形成染色体。一个位能表示出2种状态的信息量,因此足够长的二进制染色体便能表示所有的特征。这便是二进制编码。如下:
      

    1110001010111

      它由二进制符号0和1所组成的二值符号集。它有以下一些优点:

    • 编码、解码操作简单易行
    • 交叉、变异等遗传操作便于实现
    • 符合最小字符集编码原则

      二进制编码的缺点是:对于一些连续函数的优化问题,由于其随机性使得其局部搜索能力较差,如对于一些高精度的问题,当解迫近于最优解后,由于其变异后表现型变化很大,不连续,所以会远离最优解,达不到稳定例如:63和64对应的二进制分别为0111111和1000000。对应的7位数值均不同,因此该编码方式会导致变异后可能会出现远离最优解的情况,表现型不稳定

    5.1.2、浮点数编码

      二进制编码虽然简单直观,一目了然。但是存在着连续函数离散化时的映射误差。个体长度较短时,可能达不到精度要求,而个体编码长度较长时,虽然能提高精度,但增加了解码的难度,使遗传算法的搜索空间急剧扩大。
      所谓浮点法,是指个体的每个基因值用某一范围内的一个浮点数来表示。在浮点数编码方法中,必须保证基因值在给定的区间限制范围内,遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个休的基因值也在这个区间限制范围内。如下所示:
      

    1.2—3.1—4.3—6.5—1

      它有以下一些优点:

    • 精度高,是用于连续性问题。避免了汉明悬崖问题
    • 适用于表示范围比较大的数值,适合空间较大的遗传搜索
    • 降低了计算的复杂度,提高了效率
    • 便于遗传算法与经典优化算法的混合使用
    • 便于设计针对问题的专门知识的知识型遗传算子
    • 便于处理复杂的决策变量约束条件,适用于组合优化问题。

      举例展示:
      如果有5个变量,其取值范围分别为[1,5]、[2,8]、[6,15]、[8,21]、[9,26]([]中前面的数表示该变量的最小值,后面的数表示该变量的最大值)。其编码方式为:
    b o u n d = [ 1 5 2 8 6 15 8 21 9 26 ] bound = \left[ \begin{matrix} 1&5 \\ 2&8 \\ 6&15 \\ 8&21 \\ 9&26 \\ \end{matrix} \right] bound= 1268958152126
    r e t = b o u n d ( : , 1 ) ′ + ( b o u n d ( : , 2 ) − b o u n d ( : , 1 ) ) ′ . ∗ p i c k ; ret=bound(:,1)'+(bound(:,2)-bound(:,1))'.*pick; ret=bound(:,1)+(bound(:,2)bound(:,1)).pick;
      此处采用了线性插值的方法,其中 b o u n d bound bound是数据范围矩阵, b o u n d ( : , 1 ) bound(:,1) bound(:,1)表示第一列的所有行,后面解释相同。 b o u n d ( : , 1 ) ′ bound(:,1)' bound(:,1)表示对其进行转置,后面解释相同。 p i c k pick pick表示一个 1 × n 1 \times n 1×n的矩阵(n为变量长度,此例便为5),矩阵中的每一个值均在0-1之间。 r e t ret ret便为该问题的一个染色体编码。
      对应的MATLAB代码如下:

    pick=rand(1,length(lenchrom));%lenchrom为基因个数,即变量个数
    ret=bound(:,1)'+(bound(:,2)-bound(:,1))'.*pick; %bound是数据范围矩阵线性插值,
    %编码结果以实数向量存入ret中
    

    5.2、评价个体的适应度

      通过我们刚才的编码,将编码值反解,得出对应变量的值,将其带入适应度函数中(求目标函数最大值和最小值有所不同,求最大值时,一般适应度函数为目标函数;求最小值时,一般可以把目标函数取倒数当成其的适应度函数),适应度函数的值便为该个体的适应度。

    5.3、选择(selection)

      选择操作也叫复制操作,从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说,选择将使适应度高的个体繁殖下一代的数目较多,而适应度较小的个体,繁殖下一代的数目较少,甚至被淘汰。下面介绍常用法的选择算子:

    1. 轮盘赌选择(Roulette Wheel Selection):是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。(最常用,下面将用此方法进行说明)

    2. 随机竞争选择(Stochastic Tournament):每次按轮盘赌选择一对个体,然后让这两个个体进行竞争,适应度高的被选中,如此反复,直到选满为止。

    3. 最佳保留选择:首先按轮盘赌选择方法执行遗传算法的选择操作,然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。

    4. 无回放随机选择(也叫期望值选择Excepted Value Selection):根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下:
      (1) 计算群体中每个个体在下一代群体中的生存期望数目N。
      (2) 若某一个体被选中参与交叉运算,则它在下一代中的生存期望数目减去 0.5,若某一个体未被选中参与交叉运算,则它在下一代中的生存期望数目减去1.0。
      (3) 随着选择过程的进行,若某一个体的生存期望数目小于0时,则该个体就不再有机会被选中。

    5. 确定式选择:按照一种确定的方式来进行选择操作。具体操作过程如下:
      (1)计算群体中各个个体在下一代群体中的期望生存数目N。
      (2)用N的整数部分确定各个对应个体在下一代群体中的生存数目。
      (3)用N的小数部分对个体进行降序排列,顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中M个个体。

    6. 无回放余数随机选择:可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中,因而选择误差比较小。

    7. 均匀排序:对群体中的所有个体按期适应度大小进行排序,基于这个排序来分配各个个体被选中的概率。

    8. 最佳保存策略:当前群体中适应度最高的个体不参与交叉运算和变异运算,而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。

    9. 随机联赛选择:每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。

    10. 排挤选择:新生成的子代将代替或排挤相似的旧父代个体,提高群体的多样性。
        最通常的实现方法是轮盘赌(roulette wheel)模型。(其他选择算子大家可以自行上网找资料查看。)令 ∑ f i \sum f_i fi表示群体的适应度值之总和, f i f_i fi表示种群中第 i i i个染色体的适应度值,它被选择的概率正好为其适应度值所占份额 f i f_i fi ∑ f i \sum f_i fi
      P i = f i / ∑ i = 1 n f i P_i = f_i/\sum^{n}_{i=1}f_i Pi=fi/i=1nfi
      如果适应度为 存在负数的话,我们可以采用下面的公式:
      f i ′ = f i − min ⁡ f i max ⁡ f i − min ⁡ f i f'_i = \frac {f_i-\min f_i}{\max f_i-\min f_i} fi=maxfiminfifiminfi
      再计算概率和累计概率。
        设想群体全部个体的适应性分数分别由一张饼图代表,如下所示:
      请添加图片描述
        群体中每一染色体指定饼图中一个小块。块的大小与染色体的适应性分数成比例,适应性分数愈高,它在饼图中对应的小块所占面积也愈大。为了选取一个染色体,要做的就是旋转这个轮子,直到轮盘停止时,看指针停止在哪一块上,就选中与它对应的那个染色体。例如:

    个体1234567891011
    适应度21.81.61.41.21.00.81.60.40.20.1
    选择概率0.180.160.150.130.110.090.070.060.030.020.009
    累计概率0.180.340.190.620.730.820.890.950.980.9911

      若产生的随机数为0.88,0.82<0.88<0.89,则7号个体被选中
      由表格可以看到:“11号个体选中概率最小,但却因为其编号最大导致其累积概率为1,那么会有人疑惑是否11号个体会被选中的事件较大概率出现呢?为了验证结果,在Matlab中进行实验。进行1000次模拟,并记录每次模拟的结果,得到结果如下表所示:

    个体1234567891011
    选中次数1831681511311128169573396
    选中概率0.1830.1680.1510.1310.1120.0810.0690.0570.0330.0090.006

      从这里可以看出适应度大的选中次数多,选中概率大。适应度小的则相反。说明轮盘赌选择法是切实可行的。

    5.4、交叉(crossover)

      交叉算子将被选中的两个个体的基因链按一定概率pc进行交叉,从而生成两个新的个体,交叉位置pc是随机的。其中pc是一个系统参数。根据问题的不同,交叉又分为了单点交叉算子(Single Point Crossover)、双点交叉算子(Two Point Crossover)、均匀交叉算子 (Uniform Crossover),在此我们只讨论单点交叉的情况。
    单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体,将两者的部分基因码值进行交换。下面我们分别以二进制编码和浮点数数编码为例:
      二进制编码:
      假设如下两个8位的个体:

      S1:1000 1111

      S2:1110 1100

      产生一个在1到7之间的随机数c,假如现在产生的是2,将S1和S2的低二位交换,后代P1为1100 1111,P2为10101100。在这里高二位与低二位是按从左到右的顺序还是从右到左的顺序,自我感觉效果是一样的,在这篇文章中我们定义为从左到右的。
      浮点数编码(不同于上面,这里采用了单点交换(实数交叉法)):
      假设有两个染色体 a k , a j a_k,a_j ak,aj,随机产生一个交叉位置 k k k,则交叉法则如下:
    { a k j = a i j ( 1 − b ) + a i j b a i j = a k j ( 1 − b ) + a k j b \begin{cases} a_{kj} = a_{ij}(1-b) + a_{ij}b \\ a_{ij} = a_{kj}(1-b) + a_{kj}b \\ \end{cases} {akj=aij(1b)+aijbaij=akj(1b)+akjb
    其中 b b b时0-1之间的随机数。

    5.5、变异(Mutation)

      这是在选中的个体中,将新个体的基因链的各位按概率pm进行异向转化,最简单方式是改变串上某个位置数值。对二进制编码来说将0与1互换:0变异为1,1变异为0。
      以下变异算子适用于二进制编码和浮点数编码的个体:

    1. 基本位变异(Simple Mutation):对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。
    2. 均匀变异(Uniform Mutation):分别用符合某一范围内均匀分布的随机数,以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。(特别适用于在算法的初级运行阶段)
    3. 边界变异(Boundary Mutation):随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。
    4. 非均匀变异:对原有的基因值做一随机扰动,以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后,相当于整个解向量在解空间中作了一次轻微的变动。
    5. 高斯近似变异:进行变异操作时用符号均值为P的平均值,方差为P**2的正态分布的一个随机数来替换原有的基因值。

      下面我们分别以二进制编码和浮点数数编码为例用基本位变异:
      二进制编码:
      如下8位二进制编码:
      1 1 1 0 1 1 0 0
      随机产生一个1至8之间的数i,假如现在k=6,对从左往右的第6位进行变异操作,将原来的1变为0,得到如下串:
      1 1 1 0 1 0 0 0
      浮点数编码:
      第 i i i个染色体的第 j j j个基因 a i j a_{ij} aij变异法则如下:
    a i j = { a i j + ( a i j − a m a x ) ∗ f ( g ) r ≥ 0.5 a i j + ( a m i n − a i j ) ∗ f ( g ) r < 0.5 a_ij = \begin{cases} a_{ij} + (a_{ij}-a_{max})*f(g) & r \geq 0.5 \\ a_{ij} + (a_{min}-a_{ij})*f(g) & r < 0.5 \\ \end{cases} aij={aij+(aijamax)f(g)aij+(aminaij)f(g)r0.5r<0.5
    其中 a m a x a_{max} amax时基因 a i j a_{ij} aij的上界; a m i n a_{min} amin时基因 a i j a_{ij} aij的下界; f ( g ) = r 2 ( 1 − g / G m a x ) 2 f(g) = r_2(1-g/G{max})^2 f(g)=r2(1g/Gmax)2, r 2 r_2 r2是一个0-1之间的随机数, g g g时当前的迭代次数, G m a x G_{max} Gmax时最大进化次数, r r r是0-1之间的随机数。

    5.6、精英主义(Elitism)

      仅仅从产生的子代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。也就是说当利用交叉和变异产生新的一代时,我们有很大的可能把在某个中间步骤中得到的最优解丢失。在此我们使用精英主义(Elitism)方法,在每一次产生新的一代时,我们首先把当前最优解原封不动的复制到新的一代中,其他步骤不变。这样任何时刻产生的一个最优解都可以存活到遗传算法结束。

    4、算法结合

      经典非线性规划算法大多采用梯度下降的方法求解,局部搜索能力较强,但是全局搜素能力较弱。遗传算法采用选择、交叉和变异算子进行搜索,全局搜索能力较强,但是局部搜索能力较弱,一般只能得到问题的次优解,而不足最优解。因此,本文结合了两种算法的优点,一方面采用遗传算法进行全局搜索,一方面采用非线性规划算法进行局部搜索,以得到问题的全局最优解。

    二、举例说明

    😂😂😂前面花了很多功夫介绍了一下遗传算法,现在终于到了本文的主要内容了。都看到这里了,希望小伙伴们能给个赞鼓励一下😘😘

    1、问题描述

      采用遗传算法和非线性规划的方法求解如下函数的最小值。
    f ( x ) = − 5 s i n x 1 s i n x 2 s i n x 3 s i n x 4 s i n x 5 − s i n 5 x 1 s i n 5 x 2 s i n 5 x 3 s i n 5 x 4 s i n 5 x 5 + 8 f(x) = -5sinx_1sinx_2sinx_3sinx_4sinx_5-sin5x_1sin5x_2sin5x_3sin5x_4sin5x_5+8 f(x)=5sinx1sinx2sinx3sinx4sinx5sin5x1sin5x2sin5x3sin5x4sin5x5+8
    其中 x 1 、 x 2 、 x 3 、 x 4 、 x 5 x_1、x_2、x_3、x_4、x_5 x1x2x3x4x5是0~0.9 π \pi π之间的实数
      容易看出该问题的解为( π \pi π/2, π \pi π/2, π \pi π/2, π \pi π/2, π \pi π/2),最小值为2。
    下面通过算法求解答案。

    2、算法流程

      非线性规划遗传算法流程图如下图所示:
    在这里插入图片描述
      其中,种群初始化模块根据求解问题初始化种群,适应度值计算模块根据适应度函数计算种群中染色体的适应度值,选择、交叉和变异为遗传算法的搜索算子,N 为固定值,当进化次数为 N 的倍数时,则采用非线性寻优的方法加快进化,非线性寻优利用当前染色体值采用函数 fmincon 寻找问题的局部最优值。

    三、MATLAB程序实现

    1、编码方式

      采用浮点数编码

    function ret=Code(lenchrom,bound)
    %本函数将变量编码成染色体,用于随机初始化一个种群
    % lenchrom   input : 染色体长度
    % bound      input : 变量的取值范围
    % ret        output: 染色体的编码值
    
    flag=0;
    while flag==0
        pick=rand(1,length(lenchrom));
        ret=bound(:,1)'+(bound(:,2)-bound(:,1))'.*pick; %线性插值
        flag=test(lenchrom,bound,ret);             %检验染色体的可行性
    

    2、适应度函数

      本例是求解最小值,因此我们将目标函数当作我们的适应度函数,而个体适应度为适应度函数的倒数。

    function y = fun(x)
    y=-5*sin(x(1))*sin(x(2))*sin(x(3))*sin(x(4))*sin(x(5))-sin(5*x(1))*sin(5*x(2))*sin(5*x(3))*sin(5*x(4))*sin(5*x(5))+8;
    
    

    3、选择操作

      选择操作采用轮盘赌的方法从种群中选择适应度好的个体组成新种群。

    function ret=Select(individuals,sizepop)
    % 本函数对每一代种群中的染色体进行选择,以进行后面的交叉和变异
    % individuals input  : 种群信息
    % sizepop     input  : 种群规模
    % opts        input  : 选择方法的选择
    % ret         output : 经过选择后的种群
    
    individuals.fitness= 1./(individuals.fitness);
    sumfitness=sum(individuals.fitness);
    sumf=individuals.fitness./sumfitness;
    index=[];
    for i=1:sizepop   %转sizepop次轮盘
        pick=rand;
        while pick==0
            pick=rand;
        end
        for j=1:sizepop
            pick=pick-sumf(j);
            if pick<0
                index=[index j];
                break;  %寻找落入的区间,此次转轮盘选中了染色体i,注意:在转sizepop次轮盘的过程中,有可能会重复选择某些染色体
            end
        end
    end
    individuals.chrom=individuals.chrom(index,:);
    individuals.fitness=individuals.fitness(index);
    ret=individuals;
    

    4、交叉操作

      交叉操作是从种群中选取两个个体,按一定概率交叉得到新个体。

    function ret=Cross(pcross,lenchrom,chrom,sizepop,bound)
    %本函数完成交叉操作
    % pcorss                input  : 交叉概率
    % lenchrom              input  : 染色体的长度
    % chrom                 input  : 染色体群
    % sizepop               input  : 种群规模
    % ret                   output : 交叉后的染色体
    
    for i=1:sizepop 
        
        % 随机选择两个染色体进行交叉
        pick=rand(1,2);
        while prod(pick)==0
            pick=rand(1,2);
        end
        index=ceil(pick.*sizepop);
        % 交叉概率决定是否进行交叉
        pick=rand;
        while pick==0
            pick=rand;
        end
        if pick>pcross
            continue;
        end
        flag=0;
        while flag==0
            % 随机选择交叉位置
            pick=rand;
            while pick==0
                pick=rand;
            end
            pos=ceil(pick.*sum(lenchrom)); %随机选择进行交叉的位置,即选择第几个变量进行交叉,注意:两个染色体交叉的位置相同
            pick=rand; %交叉开始
            v1=chrom(index(1),pos);
            v2=chrom(index(2),pos);
            chrom(index(1),pos)=pick*v2+(1-pick)*v1;
            chrom(index(2),pos)=pick*v1+(1-pick)*v2; %交叉结束
            flag1=test(lenchrom,bound,chrom(index(1),:));  %检验染色体1的可行性
            flag2=test(lenchrom,bound,chrom(index(2),:));  %检验染色体2的可行性
            if   flag1*flag2==0
                flag=0;
            else flag=1;
            end    %如果两个染色体不是都可行,则重新交叉
        end
    end
    ret=chrom;
    
    

    5、变异操作

      变异操作是从种群中选取一个个体,按一定概率变异得到新个体。

    function ret=Mutation(pmutation,lenchrom,chrom,sizepop,pop,bound)
    % 本函数完成变异操作
    % pcorss                input  : 变异概率
    % lenchrom              input  : 染色体长度
    % chrom                 input  : 染色体群
    % sizepop               input  : 种群规模
    % pop                   input  : 当前种群的进化代数和最大的进化代数信息
    % ret                   output : 变异后的染色体
    
    for i=1:sizepop  
        % 随机选择一个染色体进行变异
        pick=rand;
        while pick==0
            pick=rand;
        end
        index=ceil(pick*sizepop);
        % 变异概率决定该轮循环是否进行变异
        pick=rand;
        if pick>pmutation
            continue;
        end
        flag=0;
        while flag==0
            % 变异位置
            pick=rand;
            while pick==0
                pick=rand;
            end
            pos=ceil(pick*sum(lenchrom));  %随机选择了染色体变异的位置,即选择了第pos个变量进行变异
            v=chrom(i,pos);
            v1=v-bound(pos,1);
            v2=bound(pos,2)-v;
            pick=rand; %变异开始
            if pick>0.5
                delta=v2*(1-pick^((1-pop(1)/pop(2))^2));
                chrom(i,pos)=v+delta;
            else
                delta=v1*(1-pick^((1-pop(1)/pop(2))^2));
                chrom(i,pos)=v-delta;
            end   %变异结束
            flag=test(lenchrom,bound,chrom(i,:));     %检验染色体的可行性
        end
    end
    ret=chrom;
    

    5、算法主函数

      遗传算法主函数流程如下:

    1. 随机初始化种群
    2. 计算种群的适应度值,从中选取最有个体
    3. 选择操作
    4. 交叉操作
    5. 变异操作
    6. 非线性寻优
    7. 判断进化是否结束,若否则返回步骤2
    %% 清空环境
    clc
    clear
    warning off
    
    %% 遗传算法参数
    maxgen=30;                         %进化代数
    sizepop=100;                       %种群规模
    pcross=[0.6];                      %交叉概率
    pmutation=[0.01];                  %变异概率
    lenchrom=[1 1 1 1 1];              %变量字串长度
    bound=[0 0.9*pi;0 0.9*pi;0 0.9*pi;0 0.9*pi;0 0.9*pi];  %变量范围
    
    %% 个体初始化
    individuals=struct('fitness',zeros(1,sizepop), 'chrom',[]);  %种群结构体
    avgfitness=[];                                               %种群平均适应度
    bestfitness=[];                                              %种群最佳适应度
    bestchrom=[];                                                %适应度最好染色体
    % 初始化种群
    for i=1:sizepop
        individuals.chrom(i,:)=Code(lenchrom,bound);       %随机产生个体
        x=individuals.chrom(i,:);
        individuals.fitness(i)=fun(x);                     %个体适应度
    end
    
    %找最好的染色体
    [bestfitness bestindex]=min(individuals.fitness);
    bestchrom=individuals.chrom(bestindex,:);  %最好的染色体
    avgfitness=sum(individuals.fitness)/sizepop; %染色体的平均适应度
    % 记录每一代进化中最好的适应度和平均适应度
    trace=[];
    
    %% 进化开始
    for i=1:maxgen
        
        % 选择操作
        individuals=Select(individuals,sizepop);
        avgfitness=sum(individuals.fitness)/sizepop;
        % 交叉操作
        individuals.chrom=Cross(pcross,lenchrom,individuals.chrom,sizepop,bound);
        % 变异操作
        individuals.chrom=Mutation(pmutation,lenchrom,individuals.chrom,sizepop,[i maxgen],bound);
        
        if mod(i,10)==0
            individuals.chrom=nonlinear(individuals.chrom,sizepop);
        end
        
        % 计算适应度
        for j=1:sizepop
            x=individuals.chrom(j,:);
            individuals.fitness(j)=fun(x);
        end
        
        %找到最小和最大适应度的染色体及它们在种群中的位置
        [newbestfitness,newbestindex]=min(individuals.fitness);
        [worestfitness,worestindex]=max(individuals.fitness);
        % 代替上一次进化中最好的染色体
        if bestfitness>newbestfitness
            bestfitness=newbestfitness;
            bestchrom=individuals.chrom(newbestindex,:);
        end
        individuals.chrom(worestindex,:)=bestchrom;
        individuals.fitness(worestindex)=bestfitness;
        
        avgfitness=sum(individuals.fitness)/sizepop;
        
        trace=[trace;avgfitness bestfitness]; %记录每一代进化中最好的适应度和平均适应度
    end
    %进化结束
    
    %% 结果显示
    figure
    [r c]=size(trace);
    plot([1:r]',trace(:,1),'r-',[1:r]',trace(:,2),'b--');
    title(['函数值曲线  ' '终止代数=' num2str(maxgen)],'fontsize',12);
    xlabel('进化代数','fontsize',12);ylabel('函数值','fontsize',12);
    legend('各代平均值','各代最佳值','fontsize',12);
    ylim([1.5 8])
    disp('函数值                   变量');
    % 窗口显示
    disp([bestfitness x]);
    grid on
    
    

    6、非线性寻优

      调用MATLAB工具箱中的fmincon进行非线性求解,代码如下:

    function ret = nonlinear(chrom,sizepop)
    
    for i=1:sizepop
        x=fmincon(inline('-5*sin(x(1))*sin(x(2))*sin(x(3))*sin(x(4))*sin(x(5))-sin(5*x(1))*sin(5*x(2))*sin(5*x(3))*sin(5*x(4))*sin(5*x(5))')...
            ,chrom(i,:)',[],[],[],[],[0 0 0 0 0],[2.8274 2.8274 2.8274 2.8274 2.8274]);
        ret(i,:)=x';
    end
    
    
    

    7、结果分析

      根据遗传算法理论,在MATLAB 软件中编程实现利用基本遗传算法寻找该兩数最优解。遗传算法参数设置为:种群规模 100,进化次数 30,交叉概率为0.6,变异概率为 0.1。
      基本遗传算法优化过程中各代平均两数值和最优个体两数值变化如下图所示:
      当种群进化到30 代时,函数值收敛到2.0174,在 x 1 、 x 2 、 x 3 、 x 4 、 x 5 x_1、x_2、x_3、x_4、x_5 x1x2x3x4x5,分别取1.6225 1.6165 1.5890 1.6089 1.5814时到达。
    在这里插入图片描述
      在MATLAB软件中编程实现基于遗传算法和非线性规划的函数寻优求解该问题。遗传算法参数设置同前,即种群规模 100,进化次数 30,交叉概率为0.6,变异概率为 0.1。
      算法优化过程中各代平均函数值和最优个体函数值变化如下图所示:
      当种群进化到30 代时,函数值收敛到2.0000,在 x 1 、 x 2 、 x 3 、 x 4 、 x 5 x_1、x_2、x_3、x_4、x_5 x1x2x3x4x5,分别取1.5708 1.5708 1.5708 1.5708 1.5708时到达。
    在这里插入图片描述
      比较两图可见,在同等条件下,基于遗传算法和非线性规划的函数寻优算法在收敛速度和求解结果上优于基本的遗传算法。可见,将非线性规划方法同遗传算法相结合,提高了遗传算法的搜索能力。

    四、总结

      本文采用的基本遗传算法和基于遗传算法和非线性规划的函数寻优算法的代码均会在下面给出。其中基本遗传算法只需要根据需求设置适应度函数,变量取值范围以及各个参数便可以用于其他问题。

    链接:https://pan.baidu.com/s/18HlTtFe9ytPHqXq3dkmsFA
    提取码:6666

      
      
      
      

    喜欢的小伙伴麻烦点个赞奥,谢谢啦🙏🙏

    参考:
    MATLAB智能算法30案例分析(第二版)
    https://www.jianshu.com/p/b0e08ca9a529

    展开全文
  • 基于蚁群节点寻优的贝叶斯网络结构算法研究.pdf,K2算法是学习贝叶斯网络结构的经典算法。针对K2算法依赖最大父节点数和节点序的不足,以及蚁群算法搜索空间庞大的问题,提出了一种新的贝叶斯结构学习算法 MWST ACO ...
  • ABC-RNDS方案采用双层网络拓扑结构,首先使用最小生成树法构建骨干网络,再使用人工蜂群优化算法通过网络参数优和限制中继节点总数的方法实现网络寿命的延长。实验验证分析表明,在成本和连通性受约束的条件下,...
  • 寻优算法之遗传算法

    千次阅读 2018-04-24 07:58:22
    简单的遗传算法 导言 研究生研究的领域就是用启发算法来解决超多目标优化问题,所谓的超多目标就是要同时优化目标维数超过3维且目标之间具有一定矛盾性的问题。例如从深圳到北京的交通路线,我们若只考虑时间与价格...
  • 伺服控制系统常用参数寻优算法

    千次阅读 2018-01-26 10:04:14
    参数寻优——转自mishidemudong  参数寻优背景  参数寻优问题随处可见,举几个例子。   1. 小明假期结束回校,可以坐火车,可以坐汽车,可以坐飞机,还可以走着,小明从哪条路去学校更好呢?   2. ...
  • 各种群体寻优算法的比较(半原创)

    万次阅读 多人点赞 2019-01-10 16:31:20
    【蚁群优化算法、粒子群优化算法、细菌觅食算法、萤火虫算法、人工鱼群算法】 计算机技术不断发展,...群体智能是基于种群行为对给定的目标进行寻优的启发式搜索算法,其的核心是由众多简单个体组成的群体能够通...
  • 基于麻雀搜索算法的函数寻优算法

    千次阅读 多人点赞 2021-05-28 10:54:38
    文章目录一、理论基础1、发现者位置更新2、跟随者位置更新3、警戒者位置更新4、SSA算法伪代码二、仿真...相比传统算法,麻雀搜索算法结构简单、易于实现,且控制参数较少,局部搜索能力较强。该算法在单峰、多峰等基
  • 相对退火法,遗传算法更有可能跳出局部最解,得到全局最解 遗传算法核心思想(代码的核心四个部分) 遗传算法是仿照了达尔文的生物进化概念:“物竞天择,适者生存” 选择:选择更适合生存者,淘汰劣势者。...
  • 完整代码已上传我的资源:【优化算法】动态粒子群算法的动态环境寻优算法【含Matlab源码 1125期】 点击上面蓝色字体,直接付费下载,即可。获取代码方式2: 付费专栏优化求解(Matlab)备注: 点击上面蓝色字体付费...
  • 联供系统在线寻优的遗传算法软件实现.pdf
  • 基于类中心与边界自寻优的聚类算法.pdf
  • 野马优化算法主要包括以下5个步骤:所有优化算法的种群结构基本相同。将初始种群随机设置为(x→)={x→1,x→2,⋯ ,x→n}(\overrightarrow x)=\{\overrightarrow x_1,\overrightarrow x_2,\cdots,\overrightarrow x_n...
  • 基于模拟退火的粒子群算法寻优.pdf
  • 基于入侵杂草算法的函数寻优算法

    千次阅读 2021-01-20 12:23:16
    文章目录一、理论基础1、算法简介2、杂草特性二、案例背景1、问题描述2、解题思路及步骤(1) 初始化种群(2) 繁殖(3) 空间分布三、MATLAB程序实现1、清空环境变量2、初始化参数3、构建解空间4、迭代寻优5、结果...
  • 基于粒子群算法的PID参数寻优.pdf
  • 基于混合粒子群算法的PID参数寻优.pdf
  • 基于混沌粒子群算法的复杂模型寻优.pdf
  • 寻优能力增强型越界免疫粒子群算法.pdf
  • 基于遗传算法的船体主甲板外展程度寻优.pdf
  • 基于多智能体局部寻优的粒子群优化算法.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,619
精华内容 3,047
热门标签
关键字:

寻优算法结构