人工智能優化算法曹金龍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源期刊已錄用.不同的細胞膜之間采用不同的演進規則，這樣克服了某種算法收斂精度不高或者收斂速度過慢的問題，從而得到收斂精度高并且收斂速度快的目標?；诜侵浣馀判虻亩嗄繕藘灮惴?/p>

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

Pareto最優解:不存在在各個目標函數下均優于此解的解，對于一個多目標優化問題，所有的Pareto最優解構成Pareto前端(ParetoFront)，也稱為Pareto最優解集。f2f1ParetofrontsolutiondominatedsolutionTheParetoFrontforaTwo-ObjectiveOptimizationProblems非支配解排序的過程如下：擁擠度每次計算的過程對每個非支配等級，根據目標函數值由小到大進行排序，目標函數值最大和最小的個體的擁擠度值為。其它的個體的擁擠度為相鄰兩個個體的擁擠度的差除以最大目標函數和最小目標函數的差值，即進行歸一化處理。對所有的目標函數都進行上述計算，最終的擁擠度值就是所有目標函數計算出的擁擠度的總和。基于非支配解排序的量子粒子群算法流程

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