演算法紅點

1. a星演算法找不到路徑是會遍歷全圖么

C語言的A星叫A*演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。 如在一張dota地圖上，英雄從一個地方走動到地圖上另一個點，它選擇最優路線的演算法。

綠點是開始點，紅點是目的地，黑色區域是不可通過區域。 通過A*演算法，黃色線段就是找到的最優路線。

其實用漫水演算法也能找這路線啊。這A星演算法優點在於處理速度快，並不是像漫水一樣，各個方向都在尋找。

2. 基於DEAP庫的Python進化演算法從入門到入土--（六）多目標遺傳演算法 NSGA-II

在很多實際工程問題中，我們的優化目標不止一個，而是對多個目標函數求一個綜合最優解。例如在物流配送問題中，不僅要求配送路徑最短，還可能需要參與運輸車輛最少等。

多目標優化問題的數學模型可以表達為：

多目標優化問題通常具有如下特點：

對於多目標優化問題，傳統方法是將原問題通過加權方式變換為單目標優化問題，進而求得最優解。該方法具有兩大問題：

遺傳演算法具有多點多方向搜索的特徵，在一次搜索中可以得到多個Pareto最優解，因此更適合求解多目標優化問題。

而當前用於求解多目標優化問題的遺傳演算法一般有兩種思路：

NSGA-II(nondominated sorting genetic algorithm II)是2002年Deb教授提出的NSGA的改進型，這個演算法主要解決了第一版NSGA的三個痛點：

針對這三個問題，在NSGA-II中，Deb提出了快速非支配排序運算元，引入了保存精英策略，並用「擁擠距離」(crowding distance)替代了共享(sharing)。

在介紹NSGA-II的整體流程之前，我們需要先了解快速非支配排序和擁擠距離的定義。

解的支配關系與Pareto最優解

下圖表示了解之間的支配和強支配關系：

下圖表示了一個最小化問題解集中的Pareto最優解和Pareto弱最優解：

快速非支配排序步驟

快速非支配排序就是將解集分解為不同次序的Pareto前沿的過程。

它可以描述為：

DEAP實現

DEAP內置了實現快速非支配排序操作的函數 tools.emo.sortNondominated

tools.emo.sortNondominated(indivials, k, first_front_only=False)

參數：

返回：

擁擠距離的定義

在NSGA II中，為了衡量在同一個前沿中各個解質量的優劣，作者為每個解分配了一個擁擠距離。其背後的思想是 讓求得的Pareto最優解在objective space中盡量分散 。也就有更大可能讓解在Pareto最優前沿上均勻分布。

DEAP實現

DEAP中內置了計算擁擠距離的函數 tools.emo.assignCrowdingDist

tools.emo.assignCrowdingDist(indivials)

參數：

返回：

比較操作

根據快速非支配排序和擁擠距離計算的結果，對族群中的個體進行排序：

對兩個解 ，

在每個迭代步的最後，將父代與子代合為一個族群，依照比較操作對合並後族群中的個體進行排序，然後從中選取數量等同於父代規模的優秀子代，這就是NSGA-II演算法中的精英保存策略。

DEAP實現

DEAP內置了實現NSGA-II中的基於擁擠度的選擇函數 tools.selNSGA2 用來實現精英保存策略：

tools.selNSGA2(indivials, k, nd='standard')

參數：

返回：

這里選用ZDT3函數作為測試函數，函數可表達為：

其Pareto最優解集為

這里為了方便可視化取 。

下圖給出了該函數在Decision Space和Objective Space中的對應：

其pareto最優解在Objective Space中如下圖紅點所示：

將結果可視化：

得到：

可以看到NSGA-II演算法得到的Pareto最優前沿質量很高：最優解均勻分布在不連續前沿的各個線段上；同時在最優前沿以外沒有個體存在。

3. 優化演算法筆記（十七）萬有引力演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
萬有引力演算法（Gravitational Search Algorithm）是受物體之間的萬有引力啟發而提出的演算法。演算法提出於2008（2009）年，時間不長，不過相關的文章和應用已經相對較多，也有不少的優化改進方案。
萬有引力演算法中，每一個物體的位置代表了一個可行解，而物體的質量則反映了該位置的好壞，位置越好的物體的質量越大，反之物體的質量越小（質量由適應度值計算出，不是直接相等）。物體在解空間中的運動方式由其他物體的引力決定，質量越大的物體，在同等引力作用下的加速度較小，所以單位時間內的速度也相對較小，位移距離較短，反之加速度和速度都較大，位移距離較長。故可以簡單的認為， 位置越優的個體的移動速度越慢，位置越差的個體的移動速度越快 。

萬物之間皆有萬有引力，不過在我們談到萬有引力之時，對象大多是天體，否則萬有引力太小可以忽略不計。所有這次我們的主角就是天體了。（總不可能是蘋果吧）。

每一個天體都有個屬性：位置X，質量M，加速度A，以及速度V，還有適應度值F。
在D維空間內有N個天體，其位置為

，加速度

，速度

，其適應度值為

。

第i個天體的質量則是根據其適應度值計算得出：

其中M為天體的質量在群體重質量中的佔比， 分別表示全局最差天體的適應度值和全局最優個體的適應度值。
可以看出，處於最優位置的天體的質量m為1，最差位置的天體的質量m為0。當最優天體和最差天體重合時，所有的天體的質量m都為1。

由萬有引力計算公式和加速度公式可以計算出當前天體收到另一個天體萬有引力而產生的加速度：

其中R表示第i個天體和第j個天體之間的歐式距離，aij為天體i在第d維上受到天體j的萬有引力而產生的加速度,ai為第i個天體受到的其他所有天體萬有引力的合力產生的加速度。G為萬有引力常量，可以根據一下公式計算：

其中G0為初始值，T為最大迭代次數。

計算出了天體的加速度，則可以根據當前速度計算出下一步天體的運行速度以及天體下一步的位置。

這一步比較簡單與粒子群、蝙蝠等有速度的演算法一致。

可以看出萬有引力演算法的流程異常的簡單，與經典的粒子群差不多。萬有引力演算法也可以看做是一個優化改進版的粒子群，不過設計比較巧妙，引入的質量、加速度等概念，但實現仍然很簡單。萬有引力演算法的效果如何，在下一節將會進行實驗測試。

適應度函數 。
實驗一：

從圖像中可以看出，各個天體都在不停的運動，由於沒有貪心演算法（優於當前值才改變位置）的加入，所以個天體有可能運動到比原先位置更差的地方，而且其收斂速度也比較快。
從結果上看，似乎還不錯，受到最差值的影響均值也相對較大，演算法結果的穩定性不是太好。
直覺上感覺演算法有點問題。根據物理得來的直覺告訴我，這些天體會相互靠近，所以，它們不會集中到它們所構成的凸包之外， 凸實心物體的質心不會跑到該物體的外部 。做個試驗驗證一下，將測試函數的最優解設置到一個極端的位置。
實驗二 ： 適應度函數

這次最優解位置在（90,90）處，該點有很大概率出現在初始天體所圍成的凸多邊形外。

從圖像中可以看出，在天體們還沒有到達最優位置附近（右下角的紅點）時，它們已經收斂於一個點，之後則很難再次向最優解靠經。看結果可以發現幾乎每一次實驗的結果都不太好，演算法果然有點問題，不過問題不大。
萬有引力出現這種現象可能有兩個原因： 1.演算法收斂的太快 ，還未對全局進行充分搜索之時就收斂到了一點，收斂到一點後無法再運到。 2.演算法沒有跳出局部最優的策略 ，萬有引力作用下的天體慢慢聚集到奇點，形成黑洞，無法從中逃離。
那接下來，對萬有引力演算法的改進方向也比較明確了：1.減緩其收斂速度，2增加跳出局部最優操作，使之逃離黑洞。
看看萬有引力常量G的函數圖像

將萬有引力常量的值修改為隨著迭代次數線性下降，從圖像中可以看出，效果還是比較明顯的，天體在不斷的運動，最後才收斂、聚集於一起。從實驗結果也可以看出，演算法相對穩定。結合圖像可以知道，改進後，演算法的收斂性下降，但全局搜索能力有較大的提升，演算法的結果不會很差但是精度較低。

將萬有引力常量的下降趨勢放緩為原來的1/4，從圖像中可以看出，演算法的收斂速度非常快，也得到了較好的結果，相比線性下降，演算法有著更好的精度，不足之處則是沒有跳出局部最優的操作，收斂過快也容易陷入局部最優。
不知道原文為什麼讓萬有引力常量G的如此快的降到0，明明降的更慢能有更好的全局搜索能力，但精度可能較差。猜測如果精度較差則在測試函數結果和曲線上比不贏對比的其他演算法，論文沒法發了。其使用的測試函數的最優解大多處於解空間的中心位置附近，即很少出現最優解在天體所圍成的凸多面體之外的情況，而實際問題中我們是無法預知最優解在個位置的。
接下來，將試著為萬有引力演算法加入一點跳出局部最優的操作。

實驗四 ：改進,新增以下規則及操作
在實驗二的條件下
1 . 處於最優位置的天體保持自己的位置不動.
2 . 如果某一個天體的運動後的位置優於當前全局最優個體的位置則將當前的最優個體初始化到解空間的隨機位置.(將被自己幹掉的大哥流放)。
3 . 如果觸發了規則2，將所有的個體的以迭代次數重置為0，即計算G=G0*e^(-20t/T)中的t置為0，重新計算萬有引力常量，若未觸發條件2則t=t+1。

從圖像上看，演算法的全局搜索能力有大幅的增強，並且已經集中到了最優解的附近，而且由於加入了「流放」這一跳出局部最優的操作，可以看出，不斷的有新的個體出現在距最優位置較遠的位置。不過收斂速度有所下降，因此局部搜索能力有一定減弱。
看結果，好像沒有實驗三那麼好，但與實驗二相比，已經有了很大的提升，而且有了跳出局部最優的操作，結果也相對穩定。
上述的實驗僅僅是對直觀猜想的實現，如果想以此為改進點，還要對其進行大量的調優，相信會有不錯的結果。

萬有引力演算法根據萬有引力提出，結合了牛頓第二定律，可以說其操作步驟與真實的物理規律非常的貼切。不過就像前文說過，受物理現象啟發而來的優化演算法其性能是未知的，因為它們不具備智能，只有著規律，有規律就會存在弱點，就會有搜索盲區。宇宙那麼大，肯定存在沒有任何天體到達過的空間。
不過由於萬有引力演算法流程簡單，理解方便，其優化方案和能改進的地方相對較多。萬有引力演算法的收斂速度過快，導致其全局搜索能力較弱而局部搜索能力很強，容易陷入局部最優。根據其特點，我們可以降低其收斂速度或者增加跳出局部最優操作，來平衡演算法的各個性能。

參考文獻
Rashedi E , Nezamabadi-Pour H , Saryazdi S . GSA: A Gravitational Search Algorithm[J]. Information Sciences, 2009, 179(13):2232-2248. 提取碼：xhpa

以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（十六）混合蛙跳演算法
下一篇 優化演算法筆記（十八）灰狼演算法

優化演算法matlab實現（十七）萬有引力演算法matlab實現