人工智能优化算法

人工智能优化算法曹金龙2011年9月26日优化问题的分类单目标优化和多目标优化优化目标的个数约束优化和非约束优化有无约束条件连续优化和离散优化优化的变量多目标优化目标

通常而言，这k个目标函数是相互冲突矛盾的，即不能同时达到最大值或者最小值，这需要寻找一个折衷的解。通常称这些解为Pareto最优解。

有些文章中采取，Y=a*U+b*V,a+b=1，但个人认为这是没有任何理论依据的。多目标优化问题是优化理论研究的热点。f2f1ParetofrontsolutiondominatedsolutionTheParetoFrontforaTwo-ObjectiveOptimizationProblems约束优化问题处理方法：罚函数方法经典的算法遗传算法(GA)量子遗传算法(GQA)粒子群算法(PSO)人工蜂群算法(ABC)量子粒子群算法(QPSO)膜优化理论多目标优化算法遗传算法(GeneticAlgorithm)遗传算法(GeneticAlgorithm，GA)是建立在自然选择和群体遗传学基础上的搜索方法，是由美国Michigan大学的Holland教授首先提出并发展起来的。核心思想：初始种群产生之后，按照“适者生存”和“优胜劣汰”的原理，逐代演化产生出越来越好的近似解。现在的研究方向多为遗传算法与其它智能优化算法结合以及小生境遗传算法。交叉和变异算子

单点交叉

随机变异

(BoundaryMutation):crossingpointatkthposition父代子代mutatingpointatkthposition父代子代交叉算子交叉

(单点交叉)这里应用单点交叉，这也是在遗传算法中应用最广泛的交叉方式，另外还有双点交叉，多点交叉，均匀交叉等。将父代交叉点后的基因交换位置，从而产生子代的基因。交叉点是随机产生的，图示为产生的在交叉点为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

endendfort=1:mifU(0,1)<Pmendendend

执行精英保留策略end

量子遗传算法量子遗传算法是量子计算和遗传算法相结合的产物，其关键步骤包括染色体编码、种群测量、种群更新等。在QGA中，染色体编码采用量子位来实现。量子位与经典位的不同之处在于它可以落在和之外的线性组合态，其状态通常表示为：设一个染色体包含位量子位，则其编码形式为量子旋转门的更新操作如下所示测量过程如下：

量子旋转门的选取

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(t<MAX-GEN)dot=t+1makeP(t)byobservingQ(t-1)statesrepairP(t)evaluateP(t)updateQ(t)storethebestsolutionbamongP(t)end粒子群

ParticleSwarmOptimization群体智能是由大量简单个体相互交流和协作涌现出的智能行为。PSO源于对鸟群和鱼群等觅食和迁徙等行为的模拟，是群体智能的重要代表。PSO的提出者RussellEberhartJamesKennedy粒子群算法(PSO)PSO迭代公式惯性项认知项社会项w:

惯性权重

c1,c2

:学习因子

r1,r2

:[0,1]区间内随机数

P

：个体最优位置；g

：全局最优位置PSO求解Schwefel函数粒子群收敛过程示意图求解结果迭代次数种群最优解0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771真实解837.9658PSO的优点模型简单计算简单全局优化能力强具有高维多目标优化能力伪代码创建并初始化一个M维的粒子群Repeat

for每个粒子i=1~N

If

//设置个体的最佳位置

endIf

//设置全局的最佳位置

endendfor每个粒子i=1~N

更新粒子的速度更新粒子的位置

endUntil终止条件为真人工蜂群算法(ABC)人工蜂群算法是模仿蜜蜂行为提出的一种优化方法。主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。Karaboga提出了人工蜂群算法(artificialbeecolonyalgorithm)。食物源的数目＝工蜂的数目＝观察蜂的数目侦察蜂的数目＝1工蜂寻找食物源的位置若则更新食物源的位置否则，食物源的位置保持不变。观察蜂选择工蜂公式实际是轮盘赌选择机制。

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.观察蜂根据轮盘赌选择的工蜂的食物源位置，来更新自己的食物源位置。观察蜂的位置更新过程跟工蜂的位置更新过程类似。当工蜂或者观察蜂的食物源位置经过“limit”次后仍然没有更新，则工蜂或者观察蜂变为侦察蜂，随机选择食物源的位置。人工蜂群算法是一种比较有效的算法，这是因为此算法存在侦察蜂，能够在收敛的同时进行适度发散。算法流程

Initialize

REPEAT■Movetheemployedbeesontotheirfoodsourcesanddeterminetheirnectaramounts.■Movetheonlookersontothefoodsourcesanddeterminetheirnectaramounts.■Movethescoutsforsearchingnewfoodsources.■Memorizethebestfoodsourcefoundsofar.UNTIL(requirementsaremet)人工蜂群算法收敛示意图人工蜂群算法量子粒子群算法

HongyuanGAO,JinlongCAO.Asimplequantum-inspiredparticleswarmoptimizationanditsapplication.InternationalJournalof

AdvancementinComputingTechnology.Ei源期刊已录用

量子粒子的量子位置定义为

量子粒子群算法流程步骤1：初始化量子粒子群，包括随机选择量子粒子的位置,量子粒子的速度和量子粒子的局部最优解。步骤2：对量子粒子进行适应度评价，从而得到全局最优解。步骤3：更新量子粒子的量子速度和位置。步骤4：对于量子粒子的新位置，计算适应度值。步骤5：更新量子粒子的局部最优解，同时找到全局的最优解作为进化的目标。步骤6：如果进化并没有终止(通常由预先设定的最大循环次数决定)，返回步骤3,否则，算法终止。Benchmark函数测试试验膜优化理论

HongyuanGAO,JinlongCAO,Yuning

Zhao.Membranequantumparticleswarmoptimisationforcognitiveradiospectrumallocation.Int.J.ComputerApplicationsinTechnology.EI源期刊已录用.不同的细胞膜之间采用不同的演进规则，这样克服了某种算法收敛精度不高或者收敛速度过慢的问题，从而得到收敛精度高并且收敛速度快的目标。基于非支配解排序的多目标优化算法

HongyuanGAO,JinlongCAO.Anon-dominatedsortingquantumparticleswarmoptimizationanditsapplicationincognitiveradiospectrumallocation.SCI源期刊已投稿。专利：高洪元，曹金龙，刁鸣，赵宇宁.基于非支配解排序的量子雁群算法的认知无线电多目标频谱分配方法。多目标优化多于最小值多目标优化问题，对于可行解，其中为可行解集合。若对所有的i都成立，且至少有一个严格不等式成立，则成为支配，为非支配解。

Pareto最优解:不存在在各个目标函数下均优于此解的解，对于一个多目标优化问题，所有的Pareto最优解构成Pareto前端(ParetoFront)，也称为Pareto最优解集。f2f1ParetofrontsolutiondominatedsolutionTheParetoFrontforaTwo-ObjectiveOptimizationProblems非支配解排序的过程如下：拥挤度每次计算的过程对每个非支配等级，根据目标函数值由小到大进行排序，目标函数值最大和最小的个体的拥挤度值为。其它的个体的拥挤度为相邻两个个体的拥挤度的差除以最大目标函数和最小目标函数的差值，即进行归一化处理。对所有的目标函数都进行上述计算，最终的拥挤度值就是所有目标函数计算出的拥挤度的总和。基于非支配解排序的量子粒子群算法流程

步骤1：初始化量子粒子的位置和量子速度，并对每个量子粒子进行适应度评价(求解目标函数值)。步骤2：对种群中的个体根据其适应度值进行非支配解排序和拥挤度的计算。步骤3：对非支配解排序等级相同的个体进行拥挤度由大到小进行排序，选择非支配解排序等级为1的解加入精英解集