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

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

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

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

單點交叉

隨機變異

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

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

v2=[001110101110011000000010101001000]c1=[100110110100101100000010101001000]

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

假設(shè)染色體

v1

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

輪盤賭選擇個體

ifU(0,1)<Pc

隨機產(chǎn)生

forp=s~m

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

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

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

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

慣性權(quán)重

c1,c2

:學習因子

r1,r2

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

P

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

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

for每個粒子i=1~N

If

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

endIf

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

endendfor每個粒子i=1~N

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

endUntil終止條件為真人工蜂群算法(ABC)人工蜂群算法是模仿蜜蜂行為提出的一種優(yōu)化方法。主要特點是不需要了解問題的特殊信息，只需要對問題進行優(yōu)劣的比較，通過各人工蜂個體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來，有著較快的收斂速度。Karaboga提出了人工蜂群算法(artificialbeecolonyalgorithm)。食物源的數(shù)目＝工蜂的數(shù)目＝觀察蜂的數(shù)目偵察蜂的數(shù)目＝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.觀察蜂根據(jù)輪盤賭選擇的工蜂的食物源位置，來更新自己的食物源位置。觀察蜂的位置更新過程跟工蜂的位置更新過程類似。當工蜂或者觀察蜂的食物源位置經(jīng)過“l(fā)imit”次后仍然沒有更新，則工蜂或者觀察蜂變?yōu)閭刹旆?，隨機選擇食物源的位置。人工蜂群算法是一種比較有效的算法，這是因為此算法存在偵察蜂，能夠在收斂的同時進行適度發(fā)散。算法流程

Initialize

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

HongyuanGAO,JinlongCAO.Asimplequantum-inspiredparticleswarmoptimizationanditsapplication.InternationalJournalof

AdvancementinComputingTechnology.Ei源期刊已錄用

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

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

HongyuanGAO,JinlongCAO,Yuning

Zhao.Membranequantumparticleswarmoptimisationforcognitiveradiospectrumallocation.Int.J.ComputerApplicationsinTechnology.EI源期刊已錄用.不同的細胞膜之間采用不同的演進規(guī)則，這樣克服了某種算法收斂精度不高或者收斂速度過慢的問題，從而得到收斂精度高并且收斂速度快的目標?；诜侵浣馀判虻亩嗄繕藘?yōu)化算法

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

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

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