人工智能優(yōu)化算法

人工智能優(yōu)化算法曹金龍2011年9月26日優(yōu)化問(wèn)題的分類單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化優(yōu)化目標(biāo)的個(gè)數(shù)約束優(yōu)化和非約束優(yōu)化有無(wú)約束條件連續(xù)優(yōu)化和離散優(yōu)化優(yōu)化的變量多目標(biāo)優(yōu)化目標(biāo)

通常而言，這k個(gè)目標(biāo)函數(shù)是相互沖突矛盾的，即不能同時(shí)達(dá)到最大值或者最小值，這需要尋找一個(gè)折衷的解。通常稱這些解為Pareto最優(yōu)解。

有些文章中采取，Y=a*U+b*V,a+b=1，但個(gè)人認(rèn)為這是沒(méi)有任何理論依據(jù)的。多目標(biāo)優(yōu)化問(wèn)題是優(yōu)化理論研究的熱點(diǎn)。f2f1ParetofrontsolutiondominatedsolutionTheParetoFrontforaTwo-ObjectiveOptimizationProblems約束優(yōu)化問(wèn)題處理方法：罰函數(shù)方法經(jīng)典的算法遺傳算法(GA)量子遺傳算法(GQA)粒子群算法(PSO)人工蜂群算法(ABC)量子粒子群算法(QPSO)膜優(yōu)化理論多目標(biāo)優(yōu)化算法遺傳算法(GeneticAlgorithm)遺傳算法(GeneticAlgorithm，GA)是建立在自然選擇和群體遺傳學(xué)基礎(chǔ)上的搜索方法，是由美國(guó)Michigan大學(xué)的Holland教授首先提出并發(fā)展起來(lái)的。核心思想：初始種群產(chǎn)生之后，按照“適者生存”和“優(yōu)勝劣汰”的原理，逐代演化產(chǎn)生出越來(lái)越好的近似解?，F(xiàn)在的研究方向多為遺傳算法與其它智能優(yōu)化算法結(jié)合以及小生境遺傳算法。交叉和變異算子

單點(diǎn)交叉

隨機(jī)變異

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

(單點(diǎn)交叉)這里應(yīng)用單點(diǎn)交叉，這也是在遺傳算法中應(yīng)用最廣泛的交叉方式，另外還有雙點(diǎn)交叉，多點(diǎn)交叉，均勻交叉等。將父代交叉點(diǎn)后的基因交換位置，從而產(chǎn)生子代的基因。交叉點(diǎn)是隨機(jī)產(chǎn)生的，圖示為產(chǎn)生的在交叉點(diǎn)為17處的交叉過(guò)程。v1=[100110110100101101000000010111001]

v2=[001110101110011000000010101001000]c1=[100110110100101100000010101001000]

c2=[001110101110011001000000010111001]在17位基因處交叉變異算子變異根據(jù)變異概率確定基因是否變異。

假設(shè)染色體

v1

的第16位變異，則變異的過(guò)程如下。由于該基因?yàn)?，則變異之后變?yōu)?。要注意的是，變異概率相對(duì)于交叉概率是很小的。v1=[100110110100101101000000010111001]c1=[100110110100101001000000010111001]在16基因位開始變異選擇算子經(jīng)典的選擇算法：輪盤賭選擇適應(yīng)度高的個(gè)體被選擇為后代的概率高，而適應(yīng)度低的個(gè)體被選擇為后代的概率低這也正是體現(xiàn)了達(dá)爾文的進(jìn)化論“優(yōu)勝劣汰，適者生存”的思想偽代碼初始化種群Forgeneration=1:max_generationforind=1:n/2

輪盤賭選擇個(gè)體

ifU(0,1)<Pc

隨機(jī)產(chǎn)生

forp=s~m

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

執(zhí)行精英保留策略end

量子遺傳算法量子遺傳算法是量子計(jì)算和遺傳算法相結(jié)合的產(chǎn)物，其關(guān)鍵步驟包括染色體編碼、種群測(cè)量、種群更新等。在QGA中，染色體編碼采用量子位來(lái)實(shí)現(xiàn)。量子位與經(jīng)典位的不同之處在于它可以落在和之外的線性組合態(tài)，其狀態(tài)通常表示為：設(shè)一個(gè)染色體包含位量子位，則其編碼形式為量子旋轉(zhuǎn)門的更新操作如下所示測(cè)量過(guò)程如下：

量子旋轉(zhuǎn)門的選取

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群體智能是由大量簡(jiǎn)單個(gè)體相互交流和協(xié)作涌現(xiàn)出的智能行為。PSO源于對(duì)鳥群和魚群等覓食和遷徙等行為的模擬，是群體智能的重要代表。PSO的提出者RussellEberhartJamesKennedy粒子群算法(PSO)PSO迭代公式慣性項(xiàng)認(rèn)知項(xiàng)社會(huì)項(xiàng)w:

慣性權(quán)重

c1,c2

:學(xué)習(xí)因子

r1,r2

:[0,1]區(qū)間內(nèi)隨機(jī)數(shù)

P

：個(gè)體最優(yōu)位置；g

：全局最優(yōu)位置PSO求解Schwefel函數(shù)粒子群收斂過(guò)程示意圖求解結(jié)果迭代次數(shù)種群最優(yōu)解0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771真實(shí)解837.9658PSO的優(yōu)點(diǎn)模型簡(jiǎn)單計(jì)算簡(jiǎn)單全局優(yōu)化能力強(qiáng)具有高維多目標(biāo)優(yōu)化能力偽代碼創(chuàng)建并初始化一個(gè)M維的粒子群Repeat

for每個(gè)粒子i=1~N

If

//設(shè)置個(gè)體的最佳位置

endIf

//設(shè)置全局的最佳位置

endendfor每個(gè)粒子i=1~N

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

endUntil終止條件為真人工蜂群算法(ABC)人工蜂群算法是模仿蜜蜂行為提出的一種優(yōu)化方法。主要特點(diǎn)是不需要了解問(wèn)題的特殊信息，只需要對(duì)問(wèn)題進(jìn)行優(yōu)劣的比較，通過(guò)各人工蜂個(gè)體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來(lái)，有著較快的收斂速度。Karaboga提出了人工蜂群算法(artificialbeecolonyalgorithm)。食物源的數(shù)目＝工蜂的數(shù)目＝觀察蜂的數(shù)目偵察蜂的數(shù)目＝1工蜂尋找食物源的位置若則更新食物源的位置否則，食物源的位置保持不變。觀察蜂選擇工蜂公式實(shí)際是輪盤賭選擇機(jī)制。

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.觀察蜂根據(jù)輪盤賭選擇的工蜂的食物源位置，來(lái)更新自己的食物源位置。觀察蜂的位置更新過(guò)程跟工蜂的位置更新過(guò)程類似。當(dāng)工蜂或者觀察蜂的食物源位置經(jīng)過(guò)“l(fā)imit”次后仍然沒(méi)有更新，則工蜂或者觀察蜂變?yōu)閭刹旆?，隨機(jī)選擇食物源的位置。人工蜂群算法是一種比較有效的算法，這是因?yàn)榇怂惴ù嬖趥刹旆?，能夠在收斂的同時(shí)進(jìn)行適度發(fā)散。算法流程

Initialize

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

HongyuanGAO,JinlongCAO.Asimplequantum-inspiredparticleswarmoptimizationanditsapplication.InternationalJournalof

AdvancementinComputingTechnology.Ei源期刊已錄用

量子粒子的量子位置定義為

量子粒子群算法流程步驟1：初始化量子粒子群，包括隨機(jī)選擇量子粒子的位置,量子粒子的速度和量子粒子的局部最優(yōu)解。步驟2：對(duì)量子粒子進(jìn)行適應(yīng)度評(píng)價(jià)，從而得到全局最優(yōu)解。步驟3：更新量子粒子的量子速度和位置。步驟4：對(duì)于量子粒子的新位置，計(jì)算適應(yīng)度值。步驟5：更新量子粒子的局部最優(yōu)解，同時(shí)找到全局的最優(yōu)解作為進(jìn)化的目標(biāo)。步驟6：如果進(jìn)化并沒(méi)有終止(通常由預(yù)先設(shè)定的最大循環(huán)次數(shù)決定)，返回步驟3,否則，算法終止。Benchmark函數(shù)測(cè)試試驗(yàn)?zāi)?yōu)化理論

HongyuanGAO,JinlongCAO,Yuning

Zhao.Membranequantumparticleswarmoptimisationforcognitiveradiospectrumallocation.Int.J.ComputerApplicationsinTechnology.EI源期刊已錄用.不同的細(xì)胞膜之間采用不同的演進(jìn)規(guī)則，這樣克服了某種算法收斂精度不高或者收斂速度過(guò)慢的問(wèn)題，從而得到收斂精度高并且收斂速度快的目標(biāo)。基于非支配解排序的多目標(biāo)優(yōu)化算法

HongyuanGAO,JinlongCAO.Anon-dominatedsortingquantumparticleswarmoptimizationanditsapplicationincognitiveradiospectrumallocation.SCI源期刊已投稿。專利：高洪元，曹金龍，刁鳴，趙宇寧.基于非支配解排序的量子雁群算法的認(rèn)知無(wú)線電多目標(biāo)頻譜分配方法。多目標(biāo)優(yōu)化多于最小值多目標(biāo)優(yōu)化問(wèn)題，對(duì)于可行解，其中為可行解集合。若對(duì)所有的i都成立，且至少有一個(gè)嚴(yán)格不等式成立，則成為支配，為非支配解。

Pareto最優(yōu)解:不存在在各個(gè)目標(biāo)函數(shù)下均優(yōu)于此解的解，對(duì)于一個(gè)多目標(biāo)優(yōu)化問(wèn)題，所有的Pareto最優(yōu)解構(gòu)成Pareto前端(ParetoFront)，也稱為Pareto最優(yōu)解集。f2f1ParetofrontsolutiondominatedsolutionTheParetoFrontforaTwo-ObjectiveOptimizationProblems非支配解排序的過(guò)程如下：擁擠度每次計(jì)算的過(guò)程對(duì)每個(gè)非支配等級(jí)，根據(jù)目標(biāo)函數(shù)值由小到大進(jìn)行排序，目標(biāo)函數(shù)值最大和最小的個(gè)體的擁擠度值為。其它的個(gè)體的擁擠度為相鄰兩個(gè)個(gè)體的擁擠度的差除以最大目標(biāo)函數(shù)和最小目標(biāo)函數(shù)的差值，即進(jìn)行歸一化處理。對(duì)所有的目標(biāo)函數(shù)都進(jìn)行上述計(jì)算，最終的擁擠度值就是所有目標(biāo)函數(shù)計(jì)算出的擁擠度的總和?；诜侵浣馀判虻牧孔恿Ｗ尤核惴鞒?/p>

步驟1：初始化量子粒子的位置和量子速度，并對(duì)每個(gè)量子粒子進(jìn)行適應(yīng)度評(píng)價(jià)(求解目標(biāo)函數(shù)值)。步驟2：對(duì)種群中的個(gè)體根據(jù)其適應(yīng)度值進(jìn)行非支配解排序和擁擠度的計(jì)算。步驟3：對(duì)非支配解排序等級(jí)相同的個(gè)體進(jìn)行擁擠度由大到小進(jìn)行排序，選擇非支配解排序等級(jí)為1的解加入精英解集