和聲搜索演算法調優

❶ 優化演算法筆記（二十六）和聲搜索演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
和聲搜索演算法（Harmony Search）是受音樂中的和聲啟發而提出的啟發式演算法，其提出（發表）年份為2001年，算是一個比較老的演算法了。和聲搜索演算法放在現在，其性能非常一般，不過它提出了一種領域搜索的具體實現方式，可以和不同的演算法融合，提高其他演算法的性能。

單獨看一個和聲意義不大，一個和聲的一個維度會根據群體中該維度的所以取值來確定其領域范圍，然後再進行領域搜索。

原演算法受音樂啟發，所以它所解決的目標問題也是離散的問題。
和聲搜索演算法中的一個個體被稱為和聲記憶（Harmony Memory,HM），群體中和聲記憶的數量為N,每個和聲記憶中的音數（維度）為D。每一維的取值范圍為 。

原演算法中每個維度的取值范圍L是一組有序的離散的值，即在指定的變數值中選取一個作為和聲記憶的值。
每個和聲記憶每次迭代只能變為其領域的值。
和聲演算法中有兩種操作：1.移動到領域，2.變異到領域
其概率分別為Harmony Memory Considering Rate(HMCR)和Pitch Adjusting Rate(PAR)。
其中HMCR取值約為0.95，PAR取值約為0.10。
可以看出該演算法的步驟和數值參考了遺傳演算法，而且兩者都是為了處理離散問題。

例子如下：
和聲記憶的數量為3，維度為2，其中第1維的取值范圍為{A,B,C,D,E,F,G},第2維的取值為{3,4,5,6}。
第1代，三個個體的取值如下

在計算第2代時，每個個體的每一維只能去到該維度的鄰域的值。
個體1_2能取到的值為(A,3) (A,4) (B,3) (B,4)
個體2_2能取到的值為(F,4)(F,5)(F,6)(G,4)(G,5)(G,6)
個體3_2能取到的值為(C,3)(C,4)(C,5)(D,3)(D,4)(D,5)(E,3)(E,4)(E,5),

圖中標出了這三個個體能夠到達的鄰域。

變異到鄰域到操作也很簡單，該操作是對標了遺傳演算法中的變異操作。
變異到鄰域操作時，該維度不會變異到當前已有的值。
如個體1_1變異第1維，由於群體中第1維的取值為{A,D,G}故該維度只能取到{B,C,E,F}。
下圖中標有顏色的塊出了變異操作無法到達的位置，空白位置為變異操作能夠到達的位置。（如果沒有空白位置呢？概率非常小，畢竟個體位置遠少於解空間位置，如果出現了，不變異或者隨機一個位置都行）

迭代過後，如果新的位置更好，則保留該和聲記憶，並去除最差的和聲記憶。
最後文章給出了判斷找到的解是否是最優解的判斷函數

其中Hr=HMCR,Hi會在該維度找到更好值時隨著迭代次數遞增。該公式的作用主要是為了判斷何時去結束演算法程序，不過在之前我們都是使用的最大迭代次數來結束演算法程序，所有好像沒多大用處。
演算法的流程也挺簡單的：

和聲搜索的原演算法是根據音樂中和聲概念提出的，音符是離散的，所有演算法也是離散的，對標遺傳演算法用於處理離散解空間問題，那麼如何修改和聲搜索演算法使其能處理連續數值問題呢？
最關鍵的點是如何處理「鄰域」，在連續解空間上，很難定義出一個點的領域，而且每個維度上的取值數量也是無窮的。
為和聲搜索演算法定義鄰域也有幾種思路：
1 . 將所有的個體定義為該個體的鄰域，即每次隨機從群體中選擇一個個體，該維度移動到所選中的個體處。

其中D,E,F分別為AB,AC,BC的中點，A,B,C三個和聲記憶的鄰域將由DEF這三個點及解空間邊界決定，此時的鄰域比思路2中的更小，也不會出現重疊部分。
當某一維度的兩個領域值相等時，上述（二維）的鄰域（面）將會退化成鄰域（線），可能會導致該維度快速收斂到該值，故此時需要忽略重復值，將鄰域重新展開（成為面）。
在連續演算法中，當滿足HCMR條件時，演算法將根據上面的色塊在鄰域中隨機選擇一個值；當滿足PAR條件時，由於無法剔除指定值，簡單起見，直接移動到隨機的和聲記憶的該維度。
後續的實驗由於是求解連續函數最值，故會選擇上述連續演算法中的三種思路來進行。

適應度函數 。
實驗一 ： 思路一

從圖像可以看出，思路一的策略與遺傳演算法非常的相似，移動路線類似於十字架，最終也收斂到了正解附近。前期搜索主要靠鄰域移動，後期移動則是靠變異。

從結果也可以看出與遺傳演算法的差距不大，演算法不是很穩定，其策略是飛到相鄰的和聲記憶上，所以跨越度比較大，精度全靠變異。

實驗二 ： 思路二

從圖像中可以看出，種群的搜索路徑不在像實驗一中那樣直來直去的十字路徑，收斂的速度也慢了不少，但是仍能在正解附近收斂。

從結果中可以看出，思路二的結果好了不少，同時也更加穩定（誤，運氣好，之前實驗出現過不好的結果，沒能重現）。該思路的鄰域搜索麵積會更大，且個體之間的鄰域存在重疊部分，故會有可能收斂於不好的位置，不過概率也較小。

實驗三 ： 思路三

圖像逐漸貪吃蛇化！前期的圖像與思路一相似，後期的圖像有點類似遺傳演算法，可能是鄰域的面積逐漸縮小成了長條狀所致，不過最終「貪吃蛇」還是吃到了食物。

結果可以看出，思路三的穩定性不太行，當全部個體收斂到了一點後會開始進行思路一的替換操作，但無論如何替換都是相同的值，難以找到更優的位置，於是會出現一個較差的結果。這里也可以增加范圍隨機來跳出局部最優。

和聲搜索演算法是根據和聲樂理知識提出的演算法。由於音符是離散的值，演算法也對標了遺傳演算法，故原演算法也是針對離散問題提出的。在解決連續性問題時，需要對其鄰域概念進行擴展和修改，最終的效果與遺傳演算法相差不大。
在現在看來，和聲搜索演算法的效果屬實一般，對於其的針對性研究也不太多，該演算法主要提出了其不同於遺傳演算法的遍歷解空間的方式。所以在很多論文中都能看到用和聲搜索演算法與其他演算法融合來進行改進的例子。
與遺傳演算法相比，和聲搜索演算法的鄰域概念，將遺傳演算法的基因由線擴展到了面上。這一點有點類似於SVM和卷積神經網路的關系，不過，遺傳演算法和和聲搜索演算法的差別並沒有那麼大，只是搜索方式不同罷了。
參考文獻
Geem Z W , Kim J H , Loganathan G V . A New Heuristic Optimization Algorithm: Harmony Search[J]. Simulation, 2001, 2(2):60-68. 提取碼：4udl
Omran M , Mahdavi M . Global-best harmony search[J]. Applied Mathematics and Computation, 2008, 198(2):643-656. 提取碼：pk3s

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

目錄
上一篇 優化演算法筆記（二十五）飛蛾撲火演算法
下一篇 優化演算法筆記（二十七）蜉蝣演算法

❷ 優化演算法筆記（二十七）蜉蝣演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
蜉蝣演算法（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,僅供參考

目錄
上一篇 優化演算法筆記（二十六）和聲搜索演算法
下一篇 優化演算法筆記（二十八）蝗蟲演算法

❸ 元啟發式演算法和啟發式演算法有什麼區別

啟發式演算法與元啟發式演算法對區別在於是否存在「隨機因素」。 對一個同樣的問題，啟發式演算法（heuristics）只要給定了一個輸入，那麼演算法執行的步驟就固定下來了，輸出也因此固定，多次運算結果保持一致。

而元啟發式演算法（meta－heuristics）裡麵包括了隨機因素，如GA中的交叉因子，模擬退火中的metropolis准則，這些隨機因素也使得演算法有一定概率跳出局部最優解而去嘗試全局最優解，因此元啟發式演算法在固定的輸入下，而輸出是不固定的。

啟發式演算法(Heuristic Algorigthm)是一種基於直觀或經驗構造的演算法,在可接受的花費(指計算時間、計算空間等)給出待解決優化問題的每一實例的一個可行解，該可行解與與最優解的偏離程度一般不可以事先預計。

啟發式演算法是一種技術,這種演算法可以在可接受的計算費用內找到最好的解,但不一定能保證所得到解的可行性及最優性，甚至大多數情況下無法闡述所得解與最優解之間的近似程度。

元啟發式演算法（MetaHeuristic Algorigthm）是啟發式演算法的改進，它是隨機演算法與局部搜索演算法相結合的產物，常見的啟發式演算法包括遺傳演算法、模擬退火演算法、禁忌搜索演算法及神經網路演算法等。

新興的元啟發式演算法有、粒子群優化演算法、差分進化演算法，蟻群優化演算法、螢火蟲演算法、布穀鳥演算法、和聲搜索演算法、差分進化演算法、隨機蛙跳演算法、細菌覓食演算法、蝙蝠演算法的演算法等。