人工智能优化算法

优化问题的分类单目标优化和多目标优化优化目标的个数约束优化和非约束优化有无约束条件连续优化和离散优化优化的变量多目标优化12(),(),...,()kfxfxfx目标通常而言，这k个目标函数是相互冲突矛盾的，即不能同时达到最大值或者最小值，这需要寻找一个折衷的解。通常称这些解为Pareto最优解。有些文章中采取，Y=a*U+b*V,a+b=1，但个人认为这是没有任何理论依据的。多目标优化问题是优化理论研究的热点。12()[(),(),...,()]kfxfxfxfx21()fxx22()2fxxf2f1ParetofrontsolutiondominatedsolutionTheParetoFrontforaTwo-ObjectiveOptimizationProblems约束优化问题()()()Ffpxxx12()(,,)()0,1,,()0,1,,nggghfxxxgmnhmnnnxxxxmm最小化，使得处理方法：罚函数方法max0,()[1,,]()()()[+1,,+]()mgmmgghgmnphmnnnxxx如果不等式如果等式经典的算法遗传算法(GA)量子遗传算法(GQA)粒子群算法(PSO)人工蜂群算法(ABC)量子粒子群算法(QPSO)膜优化理论多目标优化算法遗传算法(GeneticAlgorithm)遗传算法(GeneticAlgorithm，GA)是建立在自然选择和群体遗传学基础上的搜索方法，是由美国Michigan大学的Holland教授首先提出并发展起来的。核心思想：初始种群产生之后，按照“适者生存”和“优胜劣汰”的原理，逐代演化产生出越来越好的近似解。现在的研究方向多为遗传算法与其它智能优化算法结合以及小生境遗传算法。交叉和变异算子单点交叉随机变异(BoundaryMutation):],...,,,...,,,[],...,,,...,,,[21212121nkkknkkkyyyyyyxxxxxxyxcrossingpointatkthposition父代子代],...,,,...,,,[],...,,,...,,,[21212121nkkknkkkxxxyyyyyyxxxy'x'mutatingpointatkthposition],...,,,...,,,[2121nkkkxxxxxxx父代子代],...,,,...,,,[21'21nkkkxxxxxxx'交叉算子•交叉(单点交叉)–这里应用单点交叉，这也是在遗传算法中应用最广泛的交叉方式，另外还有双点交叉，多点交叉，均匀交叉等。–将父代交叉点后的基因交换位置，从而产生子代的基因。–交叉点是随机产生的，图示为产生的在交叉点为17处的交叉过程。v1=[100110110100101101000000010111001]v2=[001110101110011000000010101001000]c1=[100110110100101100000010101001000]c2=[001110101110011001000000010111001]在17位基因处交叉变异算子•变异–根据变异概率确定基因是否变异。–假设染色体v1的第16位变异，则变异的过程如下。–由于该基因为1，则变异之后变为0。–要注意的是，变异概率相对于交叉概率是很小的。v1=[100110110100101101000000010111001]c1=[100110110100101001000000010111001]在16基因位开始变异选择算子•经典的选择算法：轮盘赌选择–适应度高的个体被选择为后代的概率高，而适应度低的个体被选择为后代的概率低–这也正是体现了达尔文的进化论“优胜劣汰，适者生存”的思想伪代码初始化种群Forgeneration=1:max_generationforind=1:n/2轮盘赌选择个体ifU(0,1)Pc随机产生forp=s~m1212,,,,,,,niiiimXxxxxxxx其中,ijxx[1,2,,]smipjpxxjpipxxendendfort=1:mifU(0,1)Pmendendend执行精英保留策略end~ititxx~jtjtxx量子遗传算法量子遗传算法是量子计算和遗传算法相结合的产物，其关键步骤包括染色体编码、种群测量、种群更新等。在QGA中，染色体编码采用量子位来实现。量子位与经典位的不同之处在于它可以落在和之外的线性组合态，其状态通常表示为：||0|1221设一个染色体包含位量子位，则其编码形式为量子旋转门的更新操作如下所示测量过程如下：1212llq''cossinsincosijijijijijijijij(,)ijijijijs'2'21,()0,()ijijijrxr量子旋转门的选取Han,K.H.andKim,J.H.Geneticquantumalgorithmanditsapplicationtocombinatorialoptimizationproblem[C].Proceedingsofthe2000IEEEInternationalConferenceonEvolutionaryComputation.USA:IEEEPress,2000:1354-1360.伪代码t=0initializeQ(t)makeP(t)byobservingQ(t)statesrepairP(t)evaluateP(t)storethebestsolutionbamongP(t)while(tMAX-GEN)dot=t+1makeP(t)byobservingQ(t-1)statesrepairP(t)evaluateP(t)updateQ(t)storethebestsolutionbamongP(t)end粒子群ParticleSwarmOptimization•群体智能是由大量简单个体相互交流和协作涌现出的智能行为。•PSO源于对鸟群和鱼群等觅食和迁徙等行为的模拟，是群体智能的重要代表。PSO的提出者RussellEberhartJamesKennedy粒子群算法(PSO)PSO迭代公式1122()()(1)(2)VwVcrpxcrgxxxV惯性项认知项社会项w:惯性权重c1,c2:学习因子r1,r2:[0,1]区间内随机数P：个体最优位置；g：全局最优位置PSO求解Schwefel函数1()()sin()500500()=418.9829;=420.9687,i=1:nniiiiifxxxxfxnx最小化问题其中最优解粒子群收敛过程示意图求解结果迭代次数种群最优解0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771真实解837.9658PSO的优点•模型简单•计算简单•全局优化能力强•具有高维多目标优化能力伪代码创建并初始化一个M维的粒子群Repeatfor每个粒子i=1~NIf//设置个体的最佳位置endIf//设置全局的最佳位置endendfor每个粒子i=1~N更新粒子的速度更新粒子的位置endUntil终止条件为真()()iifxfyiiyx()()iifxfyiiyx人工蜂群算法(ABC)人工蜂群算法是模仿蜜蜂行为提出的一种优化方法。主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。Karaboga提出了人工蜂群算法(artificialbeecolonyalgorithm)。食物源的数目＝工蜂的数目＝观察蜂的数目侦察蜂的数目＝1工蜂寻找食物源的位置若则更新食物源的位置否则，食物源的位置保持不变。观察蜂选择工蜂公式实际是轮盘赌选择机制。(1)()()iicccD.Karaboga,B.Basturk,OnThePerformanceOfArtificialBeeColony(ABC)Algorithm,AppliedSoftComputing,Volume8,Issue1,January2008,Pages687-697.B.Basturk,D.Karaboga,Anartificialbeecolony(ABC)algorithmfornumericfunctionoptimization,in:IEEESwarmIntelligenceSymposium2006,May12–14,Indianapolis,IN,USA,2006.()()()ikccc(1)()iiFcFc/21()()iiNkkFcPFc观察蜂根据轮盘赌选择的工蜂的食物源位置，来更新自己的食物源位置。观察蜂的位置更新过程跟工蜂的位置更新过程类似。当工蜂或者观察蜂的食物源位置经过“limit”次后仍然没有更新，则工蜂或者观察蜂变为侦察蜂，随机选择食物源的位置。人工蜂群算法是一种比较有效的算法，这是因为此算法存在侦察蜂，能够在收敛的同时进行适度发散。算法流程InitializeREPEAT■Movetheemployedbeesontotheirfoodsourcesanddeterminetheirnectaramounts.■Movetheonlookersontothefoodsourcesanddeterminetheirnectaramounts.■Movethescoutsforsearchingnewfoodsources.■Memorizethebestfoodsourcefoundsofar.UNTIL(requirementsaremet)人工蜂群算法收敛示意图人工蜂群算法量子粒子群算法HongyuanGAO,JinlongCAO.Asimplequantum-inspiredparticleswarmoptimizationanditsapplication.InternationalJournalofAdvancementinComputingTechnology.Ei源期刊已录用量子粒子的量子位置定义为1212ll112()()tttttidididgdidepxepx2111211(),()abs(cos1()sin),ttttidididgdtidttttididididvpxprcvvv若且其它121121,()0,()tidtidtidrvxrv量子粒子群算法流程•步骤1：初始化量子粒子群，包括随机选择量子粒子的位置,量子粒子的速度和量子粒子的局部最优解。•步骤2：对量子粒子进行适应度评价，从而得到全局最优解。•步骤3：更新量子粒子的量子速度和位置。•步骤4：对于量子粒子的新位置，计算适应度值。•步骤5：更新量子粒子的局部最优解，同时找到全局的最优解作为进化的目标。•步骤6：如果进化并没有终止(通常由预先设定的最大循环次数决定)，返回步骤3,否则，算法终止。Benchmark函数测试试验21111001100cos1,4000600600,1,2nniiiiixfxixix212418.9829sin,500500,1,2niiiifxxxix膜优化理论HongyuanGAO,JinlongCAO,YuningZhao.Membranequantumparticleswarmoptimisationforco