1. TSP演算法在實際中有什麼意義
不要問解決數學問題有什麼用，總會有用的，數學是自然科學的基礎。
TSP問題的概述
旅行商問題，即TSP問題（Traveling Salesman Problem）是數學領域中著名問題之一。假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值，這是一個NP難問題。
TSP問題的由來
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線形規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
TSP在中國的研究
同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發，到所轄街道投郵件，最後返回郵局，如果他必須走遍所轄的每條街道至少一次，那麼他應該如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題（Chinese Postman Problem CPP）因為是我國學者管梅古教授於1962年提出的這個問題並且給出了一個解法。
2. 優化演算法筆記（二十七）蜉蝣演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
蜉蝣演算法（mayfly optimization algorithm）是根據蜉蝣的飛行和繁衍行為提出的優化演算法。該演算法提出與2020年（論文接收在2019年），算是一個新演算法。演算法的流程和結構其實與蜉蝣的關系不大，可以看作是對粒子群的一個修改。
蜉蝣演算法中群體分為雄性和雌性，雄性的行為與粒子群相似，通過全局最優和自身歷史最優移動，而雌性則是向優於自己的配偶移動，若配偶弱於自己則自行局部搜索。然後這對雌性和雄磨搭孝性會產生兩個後代，並保留群體中的較優個體。
演算法的流程結構都有些許復雜，不過有粒子群基礎的小夥伴應該能很好的理解。
這次我們的主角就是蜉蝣了（雖然關系不太大）。
蜉蝣演算法中有兩種角色，雄性蜉蝣和雌性蜉蝣，其數量均為N/2,N為群體總數, 其位置為 ,速度 為了方便描述，下面使用XM表示雄性蜉蝣的位置，XF表示雌性蜉蝣的位置。
整個演算法的每次迭代流程大致可以分為四步：
1. 將蜉蝣群體均分為雄性組和雌性組，每組內按優劣順序排列。
2. 雄性個瞎稿體移動
3. 雌性個體移動
4. 雄性雌性交配產生兩個後代
5. 在這2N個個體中選出N個作為下一代
可以看出每次迭代演算法產生了2N個新個體，所以說蜉蝣演算法的計算速度會比其他演算法更慢，因為蜉蝣演算法多計算了N個個體的適應度值。（其他大多數演算法每次迭代只計算N個值）。
由於1.分組和5.選擇比較簡單，不需要再詳細描述，下面只介紹2,3,4這三個步驟。
雄性蜉蝣的移動方式與粒子群中的粒子相似枝攜，新位置當前位置和速度決定：
其中 表示第n代群體中的第i個個體的第j維的位置。
其速度則有以下公式決定：
其中如果該個體使群體中的最優個體則使用公式（3）進行移動，其他個體則使用公式（2）進行移動。 表示第n代群體中的第i個個體的第j維的速度，pbest為該個體所到過的最好位置，gbest為全局最好位置，a1,a2,beta為常數，一般取值為2，rp為當前位置與pbest的歐式距離，rg為當前位置與gbest的歐式距離，e為自然常數，d為常數，一般取值為0.1，r為[-1,1]內的隨機數。
公式2是不是和粒子群的速度更新公式很像？下面是粒子群的速度更新公式
與粒子群相比雄性蜉蝣的速度更新公式將兩個隨機數r1與r2替換成了與距離相關的值，個人認為這不是一個好的修改，不過後面可以看出，該改動為演算法提供了強大的局部搜索能力。
下面做一個試驗：現在將蜉蝣演算法中所有個體全部劃分為雄性，即沒有雌性的搜索行為和交配產生後代的行為。也可以認為是在粒子群演算法中將公式（3）替換為公式（2），我們看看效果。（唯一不同的是蜉蝣演算法中雄性中的全局最優個體使用公式（3）進行移動）。
可以看出，只有最優個體在緩慢的移動，並且在略過最優解附近後仍在移動。問題出在哪呢？
有兩個原因：
1 .如下公式的值
我們上述的實驗中取值范圍（-100,100），初始化時兩個個體之間的歐式距離r的取值范圍在10以下的都比較少，此時自身的歷史最優就是自己本身，也不會產生速度。
當r=10時，其分母為e^200,其值約等於0，此時公式（2）如下
即速度不會發生任何變化。
下面，我們把解空間縮小100倍看看效果。
可以看出僅僅是修改了取值范圍，雄性蜉蝣們的行為就發生了巨大的改變。因為距離參數會受到解空間范圍的影響，當距離足夠小時，公式（2）中的距離參數所算出的速度不在是0，所以雄性蜉蝣們便活躍了起來。
當然這是一個不好的現象，運算元不應該受解空間范圍改變有如此大的影響。
2 .初始速度
每個蜉蝣都有初始速度呀，就像粒子群一樣，所以一開始應該也會移動。
蜉蝣確實有初始速度，不過速度的每一維都是0。為什麼呢？不能是一個不是0的值嗎？可以但又不完全可以，因為蜉蝣演算法沒有給出速度的上下限范圍，沒有范圍就無法初始化到該范圍內的值。作者將速度的上下限作為了一個改進點放到了文章的後部！
結合上述1,2兩點，雄性個體中除最優個體外，其他個體的速度幾乎都是0，可以說是以肉眼不可見的方式在緩慢移動。或者也可以理解為該步驟的主要作用是局部搜索，當個體之間距離較遠時則不會移動，將雄性單獨拿出來實驗是沒有意義的。如果必須單獨拿出來用則需要設置速度上下限，並在初始化中為個體設置隨機速度。
其實論文中的速度上下限，以及慣性系數遞減等粒子群中已有的步驟，完全可以直接沿用到原始的蜉蝣演算法中，而不應作為改進單獨拎出來說明。此處也可以直接沿用粒子群算的速度更新公式。
每隻雌性個體會有自己對應的雄性個體作為配偶，雌雄兩組順序配對，即最優的雌性配對最優的雄性，次優的雌性配對次優的雄性。
雌性的移動方式為向由於自己的配偶移動，若配偶弱於自己則自行搜索。
其位置的計算公式與雄性相同均為公式（1），速度的更新公式如下：
其中xm為該雌性個體配對的雄性個體的位置，xf為該雌性個體的位置，rmf為這兩只蜉蝣之間的位置，fl為常量一般取值為0.1，r為[-1,1]內的隨機數。
當該雌性個體差於雄性個體時，使用公式(7)中的上式，當雌性個體優於該雄性個體時，使用公式(7)中的下式。
與雄性的速度更新公式相似的問題，因為距離參數rmf的值可能非常大，會導致公式(7)中的上式做小范圍的局部搜索，速度更新幅度較小。可以試著用隨機數去代替距離參數：
其中r2為[0,1]內的隨機數。
交配行為中一對雌性和雄性會產生兩個後代，其產生公式如下：
其中L為隨機數，取值范圍應該是(0,1),xm為雄性蜉蝣，xf為雌性蜉蝣，可以看出產生的兩個個體關於這對雌性的中心對稱。該步驟為蜉蝣演算法提供了全局搜索能力，並結合選擇操作加快了演算法的收斂速度。
整個蜉蝣演算法的流程如下：
其流程看上去還是挺簡單的，不過由於分了雌性和雄性兩種，導致所需操作的步驟細節很多，同時由於父輩母輩更新自身位置後還產生了後代，其實每次迭代計算了2N個個體的適應度值，導致其速度慢。
適應度函數 。
實驗一 ： 原演算法
從圖像可以看出，蜉蝣演算法的收斂速度非常的快，在解附近聚集後群體仍然能夠移動並向著正解運動，並最終收斂在正解附近。和之前的全是雄性蜉蝣的實驗大相徑庭，應該是因為交配產生的後代優於了父輩母輩，父輩母輩被替代了，所以看上去移動了。當距離變小後，雌性雄性蜉蝣的速度更新公式則開始生效了。
不過，結果並不太好，但是在預期內，可以看出，其精度是非常高的，但是演算法不太穩定，會出現非常差的結果。
因為距離較遠時全靠著交配產生的後代更新位置，此時會快速收斂到當前的最優個體附近。當距離變小後，雌性和雄性的速度更新公式開始生效，此時的群體較為集中，其運動軌跡就像貪吃蛇一樣。
綜上，可以看出演算法的前期收斂很快，演算法的局部搜索精度很高，同時全局搜索能力較弱，依靠局部搜索花上跟多時間也能找到最優解。由於全局搜索能力不強，且收斂過快，演算法應該比較容易陷入局部最優。
實驗二 ： 去除距離操作，還原成類似粒子群的速度更新方式，使用公式（4）（8）
實驗二的圖像中蜉蝣的收斂速度比實驗一中慢了一點，而且也沒有那麼集中，最終也聚集在了正解附近，這個圖像其實和粒子群也有了幾分相似。不過由於選擇操作的作用，蜉蝣演算法的總是會收斂的更快，即使設置了速度上限依然如此，因為即使該個體迭代數次可以飛到最優解，但後代可是可以直接降生與最優解附近的，如此一來該個體會被取代，剩下的個體則集中在了最優解附近。
從結果上看，實驗二損失了不上精度有點不能接受，但是也穩定了不少，局部搜索能力也有所削弱。蜉蝣演算法的收斂行為主要由交配繁衍後代和選擇下一代來提供，如果要調整其搜索速度需要修改交配操作。原論文中也寫出了相關的改進，如，父代母代產生一雌一雄兩個子代，子代雄性優於父代則保留，子代雌性優於母代則保留。此處不再贅述，可以閱讀原文。
蜉蝣演算法受雌雄蜉蝣的運動和交配產生後代的行為啟發而提出的優化演算法，個人感覺該演算法與蜉蝣關系不大，而是更像是對粒子群的一種改進。演算法的流程較為復雜，不過有粒子群作為基礎也很好理解。演算法的性能比我想像的要好，其中雌性和雄性的移動為演算法提供了局部搜索能力，而交配繁衍後代進行選擇提供了全局搜索能力。演算法的局部搜索能力很強但是穩定性較差，容易陷入局部最優。由於每次迭代產生了更多的新個體數，為了保證公平，它的迭代次數應為其他演算法的1/2。
其實原文中還有許多的優化和改進步驟，這里也不一一實驗了，還是推薦去看看原論文。
看到蜉蝣演算法，想起了之前一個寫著玩的演算法，也是將種群分為了雌雄兩類。不過沒有蜉蝣演算法這么復雜的操作，只是通過雌雄交配產生後代進行更新迭代，通過母輩生育有幾率死亡以及近親繁殖的後代有幾率死亡來控制跳出局部最優，效果中規中矩，不提了。
參考文獻
Zervoudakis, K., Tsafarakis, S., A mayfly optimization algorithm, Computers &
Instrial Engineering (2020) 提取碼：ogl4
以下指標純屬個人yy,僅供參考
目錄
上一篇 優化演算法筆記（二十六）和聲搜索演算法
下一篇 優化演算法筆記（二十八）蝗蟲演算法