基于模式搜索的自学习遗传算法

基于模式搜索的自学习遗传算法

0ga的改进方法。在对于遗传算法（ga）是一种基于生物自然选择和遗传机的随机搜索方法，具有很好的优化解决方案，在制定路径问题时具有很强的应用优势。GA存在两个不容忽视的缺陷,分别是未成熟收敛和遗传后期的收敛迟滞,主要原因是:1)为了保证算法的全局收敛性,就要维持种群中个体的多样性和搜索的有效性,避免有效基因的丢失;2)为了加快收敛速度,就要使种群较快地向最优状态转移,这又会降低群体的多样性,容易陷入局部最优。如何较快地找到最优解并防止早熟收敛问题是GA的一个较难权衡的问题。许多学者对GA改进方法进行了研究,主要集中在两个方面:1)对于GA自身过程算子或控制参数的不断完善和改进,如分层遗传、自适应遗传、小生境、并行遗传等;2)引入其他优化思想或智能技术,发挥互补优势。文献将禁忌搜索与遗传算法配合,在利用遗传算法求解配送中心选址问题的同时,设计禁忌搜索规则来解决配送中心选址所涉及的路线安排问题;文献研究了模拟退火算法与遗传算法融合的混合遗传方式,有一定的指导意义,但是在实际应用中还需针对问题具体分析。本文设计了一种基于模式搜索的自学习改进遗传算法,以期提高算法的综合搜索能力,并进一步研究了改进遗传算法在岸基导弹航路规划中的应用问题。1自适应搜索的优化算法GA是受生物进化思想启发而得出的一种全局优化算法,通过对生物遗传和进化过程中选择、交叉、变异机理的模仿,完成对问题最优解的自适应搜索过程。GA主要执行以下步骤。1根据编码公式生成初始群体编码是GA要解决的首要问题,通过编码将解空间的数据表示成基因串数据,按照相应的编码方案随机产生指定种群大小的个体。2适应性分配GA在搜索过程中用适应度来评估个体的优劣,并作为后续遗传操作的依据,个体的适应度越大,则被遗传到下一代的概率就越大。3“上系群体”规则选择操作是根据各个个体的适应度值,按照“适者生存”的规则,从上一代群体中选择出一些优良的个体遗传到下一代群体中。GA进行选择的原则是适应性强的个体为下一代贡献的概率大,则被保留到下一代的概率也大。4新个体组合交叉操作是GA最主要的遗传操作,通过交叉操作可以得到新一代个体,新个体组合了父辈个体的特性。简单的交叉操作是按照交叉概率随机选择若干对染色体并随机选取交叉点实行相应位置的基因交换,得到新的染色体。5群体社会设计变异操作是对于群体中的任一个体,以一定的概率随机改变串结构中某个串的值,即对群体中的个体,以某一概率改变某一个或一些基因座上的基因值。6过基于适应度的再选择机制通过以上遗传环节所生成的子代个体,通过基于适应度的再选择机制被保留并插入父代种群中,同时父代中相应位置的个体被淘汰,从而产生新的参与进化的种群。2基于此模式的自学记录法2.1搜索网格点模式搜索是一种求解优化问题的直接搜索方法,其“爬山”能力强,却不要求任何目标函数梯度的信息。模式搜索算法在每次迭代中依据模式和步长来搜索当前点周围的一系列网格点,寻找使目标函数值得到改善的点,对于求解目标函数不可微、甚至不连续的问题比较实用。定义:模式搜索法是对当前搜索点按固定模式和步长Δk探索移动,以寻求可行下降方向(非最速下降方向)的直接搜索法。迭代过程只要找到相对于当前点的改善点,则步长递增,并从该点开始进入下一次迭代;否则步长递减,在当前点继续搜索。以下为模式搜索算法的主要术语及其实现方式。1搜索点的选取在模式搜索中,模式是若干向量的集合,向量由算法来使用,以确定在每次迭代中要搜索哪些点。例如,如果在某优化问题中存在两个独立变量,则缺省模式由下列向量组成(模式也可自行定义):v1=;v2=;v3=[-1,0];v4=[0,-1]。2数得到改善的点在每一次迭代中,模式搜索算法搜索一组点(称为网格(Mesh)),以寻找使目标函数得到改善的点。该算法形成网格的方法是:①给模式向量乘以一个标量(称为网格尺寸);②把结果向量与当前点相加,当前点是前一步找到的最佳目标函数值的点。需要说明的是,模式搜索中用两个变量来调整网格的扩张和收缩,分别为扩张因子和收缩因子。3模式搜索法sdcs在每一步迭代中,算法通过计算当前生成的网格点的目标函数值,寻找比当前点更能使优化目标得到改善的点来取代当前点,这是一个搜索、计算和判决的过程。此过程由一个完全表决(completepoll,cp)参数来控制判决的彻底性。若cp=1,则判决过程必须搜索、计算并比较每一个当前生成的网格点,寻求其中的最优点替代当前点;若cp=0,则只要判决过程找到一个相对更优的点就停止当前代的判决过程,以此点作为新的当前点进入下一个迭代过程。模式搜索算法在迭代过程中,若找到使目标函数得到改进的点(即判决成功),就将网格尺寸扩大进入下一迭代过程,网格扩大的倍数由扩张因子决定,此为模式搜索的正向机制;同样,若某次迭代中判决不成功,则保留当前点不变,将网格尺寸缩小并进入下一迭代过程,网格缩小的倍数由收缩因子决定,此为模式搜索的负向机制。与其他启发式搜索相比,模式搜索法有以下优点:1)机制简洁,便于实现;2)不需要方向导数或梯度的任何信息;3)具有正反馈特性;4)该算法在局部具有很强的收敛性,可以作为传统方法和某些智能优化算法的辅助。2.2改变自学习遗传的发展方向遗传算法主要存在两种机制:遗传和进化,遗传是必要的,而进化才是优化的目的所在。绝大多数遗传算法的研究集中在对算法自身的改进或相关融合上,主要考虑了生物遗传的客观性和同代种群个体之间的交流,往往忽略了生物遗传的主观能动性和种群进化过程中前后代累积的经验信息,自学习遗传正是基于这一点进行改进。所谓自学习遗传是指在不改变遗传算法主体的前提下,充分利用遗传过程中的主要遗传信息来指导遗传过程下一步的进化方向,实现主动的自我学习和调整。本文提出基于模式搜索的自学习遗传算法,主要是利用每一代遗传中最优个体的变化规律,通过模式搜索的确定型自调整机制,来试探在当前代最优解的附近是否存在进一步优化的空间,并将通过模式学习调整而搜索到的更优解返回当前迭代种群,从而指导遗传算法改善下一步的进化方向,使下一步的个体不断向更优的“先辈”学习。2.3基于模式搜索的自学计算器设计1基于模式搜索的学习机制模式搜索是一种主动、直接、有效的搜索方式,具有很强的局部搜索能力和一定的全局搜索能力。相对而言,遗传算法具有较好的通用性和搜索的全局性。同时,由于遗传算法本身不是确定型搜索机制,这既是优势也使其在遗传过程中存在一定的随机波动;并且在已有的遗传选择域内,交叉和变异的局部收敛性远不及模式搜索;特别是在某些特定情况下(如最优域空间相对狭小),遗传算法存在后期收敛迟滞的问题。因此,在遗传过程后引入模式搜索的学习机制具有很强的可行性。当然,模式搜索作为学习算子也有相应的应用范围。其对具有相对连续或关联意义的优化问题编码有较好的应用价值,能很好地增强遗传算法的局部寻优能力,提高收敛速度,而对于互不关联的平行编码或无前后意义的符号编码类优化问题则效果不明显。22学习子计算的过程文中基于模式搜索的正向机制(即只采取扩张模式)来设计自学习算子,其具体设计的简化流程见图1。2.4自学习遗传算法局部搜索原则的改进建议综上,本文基于模式搜索设计了独立的学习算子,提出了新的自学习遗传算法,其基本遗传设计流程如图2所示。下面对基于模式搜索的自学习遗传算法的流程作简单介绍。1)在本文自学习遗传算法中,初始种群采取实数编码,当然也可采用格雷编码、整数或标准二进制编码。前期对于初始种群的多样性调整对算法的全局收敛性至关重要,对不同的编码方式和优化问题,需要作针对性的调整。2)为便于对算法进行对比和突出算法改进研究的重点,本算法对遗传的主要过程算子未做大的改动。在遗传算法的主要操作上,本文算法中种群适应度取对优化目标值的线性标定值;选择操作采取随机遍历抽样,此方式相对于轮盘赌原则,其选择的多样性要优于后者;变异操作采取离散变异方式,而交叉操作则采用基本的单点交叉模式;在重插入环节,基于适应度和精英保留的重插入可以确保各代中的优良个体顺利地保留下来。3)主要遗传过程结束后,自学习算子将依据模式搜索机制对当代种群的最优个体进行优化调整,并依据返回的调整结果来影响遗传过程下一步的优化方向,这样能很好地提高遗传算法的局部搜索能力。需要说明的是,自学习遗传算法是根据确定的自学习机制,从截止当前的种群进化过程中判断种群优化的可能方向,进而在存在优化空间的方向上对目前种群最优个体进行调整并返回优化结果,此过程独立于遗传操作。这有别于自适应遗传算法中依据种群进化进程动态调整遗传参数的方法。4)基于模式搜索的自学习遗传算法具有很强的局部搜索能力,能够确保只要进入搜索范围的最优解都能得到体现,但是如何确保全局最优解在遗传的最终结果中得以体现呢?同时,基于模式搜索的自学习机制在提高遗传算法的局部寻优能力的情况下,是否会同样存在未成熟收敛的风险呢?为较好地解决以上两种隐患,本文在遗传过程上作了3点适当的改进来扩大遗传搜索的全局性和种群的多样性,确保在历代中体现的最优结果得以保留。分别为:①对初始种群进行分布多样性调整(即划分搜索子空间);②取相对较大的交叉和变异概率,以扩大种群的搜索能力;③采取精英保留的重插入策略,确保最终寻优结果的有效收敛。2.5模拟测试1周期振荡函数对本文改进的ALGA算法的仿真测试采用两个经典函数,分别为一元多极值函数f1和多元多峰函数f2(Shubert函数)。f1∶f(x)=xsin(12πx)+2.0,x∈[-3.5,4](1)f2∶f(x1,x2)=∑i=15icos[(i+1)x1+i]∑i=15icos[(i+1)x2+i]+200,[−10≤x1,x2≤10](2)f2∶f(x1,x2)=∑i=15icos[(i+1)x1+i]∑i=15icos[(i+1)x2+i]+200,[-10≤x1,x2≤10](2)式中:函数f1为周期震荡函数,在当前限定域中,当x=3.9585时取得极小值-1.9584,如图3a所示;函数f2为一个多峰值多极值函数,在其定义域内总共有760个局部最小点,其中有18个是全局最小点,全局最小值为13.2691,如图3b所示。2算法性能测试为了说明改进的ALGA算法的搜索性能,现将改进的ALGA算法与其他一些算法进行仿真测试比较。参与对比测试的算法为基本遗传算法(GA)、自适应遗传算法(AGA)及本文的ALGA算法。遗传操作方式采取单点交叉和基本位变异。GA算法中Pc=0.7,Pm=0.05。AGA算法中自适应概率调整表达式为Pc={Pc1−(Pc1−Pc2)(f′−favg)fmax−favg,Pc1,f′>favgf≤favgPm={Pm1−(Pm1−Pm2)(f−fmax)fmax−favg,Pm1,f>favgf≤favg(3)Ρc={Ρc1-(Ρc1-Ρc2)(f′-favg)fmax-favg,f′>favgΡc1,f≤favgΡm={Ρm1-(Ρm1-Ρm2)(f-fmax)fmax-favg,f>favgΡm1,f≤favg(3)式中:fmax为种群中最大的适应度值;favg为每代种群的平均适应度值;f′为要交叉的两个个体中较小的适应度值;f为要变异个体的适应度值;Pc1=0.85,Pc2=0.5,Pm1=0.06,Pm2=0.03。仿真测试时,各算法的种群规模均为80,每个算法分别在不同的最大迭代代数设置下运行30次。测试的所有数据和结果都在同一计算环境下(即同一台计算机、同一个操作系统和同一段时间内)运算所得。表1表示各算法针对不同的最大迭代代数设置分别运行30次的数据统计结果。由表1可看出:最大迭代代数设置为100、200、300时,无论从平均适应度值、收敛次数,还是收敛到理论最优值的次数,ALGA算法均略优于GA、AGA,表明随着迭代代数的增加,ALGA算法具有更高的收敛精度和收敛率。这说明本文改进的ALGA算法在提高算法的搜索精度和防止陷入局部最优方面具有很好的效果。3为了改善alga在道路规划中的应用3.1陆相岛屿地理障碍威胁我岸基中远程导弹对海上编队目标实施突击,设导弹的发射点为A,敌舰艇编队的目标点为T,我导弹发射点A到编队目标点T的直线距离为1000km。现以发射点A为坐标原点,以A点与T点的连线为横轴建立直角坐标系。则发射点A的坐标为(0,0),目标点T的坐标为(1000,0)。根据战场预警情报,战场规划空间内存在岛屿地理障碍,需要规避绕行;发现友邻方的编队目标,要求导弹突防时,以友邻编队中心位置为圆心,10km为半径的区域内禁止穿越;海区存在恶劣气象区,对岸基导弹突防飞行安全构成威胁,需规避;另外,还发现3个目标协同海上编队,其对空抗击范围取决于编队防空火力的战技性能,要求我岸基导弹在其有效抗击范围以外飞越。具体威胁分布如表2所示。设表2中各威胁源的权重系数依次为k1,k2,…,k6,各威胁源威胁权重分配分别为:恶劣气象威胁权重k1=0.1,友邻兵力目标障碍威胁权重k3=0.1,地理障碍威胁权重k2=0.2,目标防空火力1威胁权重k4=0.2,目标防空火力2威胁权重k4=0.2,目标防空火力3威胁权重k4=0.2。采用改进的ALGA算法进行航路规划,并运用Matlab7.1编程仿真。3.2航迹规划目标函数的确定将遗传算法和待解决问题联系在一起的两种机制是编码和评估。编码是用染色体表示待解决的问题,利用遗传算法进行航路规划,首先是根据该问题所涉及的因素和特点确定基因编码方式。编码方式直接关系到算法的可行性和效率,好的编码方式应该与航路规划具体问题紧密关联。评估是用适应度评价函数来计算染色体的性能和适应性是否接近问题解的最优解,在种群繁殖时利用评估函数来计算染色体的适应性,适应性差的染色体会被淘汰。对于编码,航路规划问题中,航路的主要信息是航路点包含的位置点信息,所以利用基因来表示航路包含的某个位置点,由多个基因组成一个染色体,包含航路上所有位置点的染色体就是一个初始的问题解。这种编码方式合理地表示了航路包含的信息,并且利于计算最优解。本文结合岸基导弹航路规划问题的特点,采取实数制编码方式,具体为:沿着x轴按照一定的长度s将规划区域分为N个航路区,设起始点与目标点间的距离为l,则s=l/N,令航路点序列依次位于各个区域的边界,则航路点的横坐标依次为1s,2s,3s,…,Ns。整条航路可表示为((y0,z0),(y1,z1),(y2,z2),…,(yN-1,zN-1),(yT,zT)),表示的航路为((0