# 群體智慧期末報告
* M093040061 劉景翔

## Water Wave Optimization
* Author: Yu-Jun Zheng
* Published on: Computers & Operations Research
Volume 55, March 2015, Pages 1-11

## 簡介
* 以水波傳播的原理發想
* 使用三種 operator：
* 傳播 (Propagation)：
在自己周圍一定範圍搜尋
* 折射 (Refraction)：
向 global best 靠近
* 碎浪 (Breaking)：
Global best 進行的 local search
* 每一 generation 每一「水波」依照條件選擇三種 operator 之一執行

## 傳播 (Propagation)
* $x'(d)=x(d)+rand(-1,1)\cdot \lambda L(d)$
在以自身為中心，半徑為邊界寬的一定比例的範圍內隨機搜尋
* $\lambda'=\lambda \alpha^{-(f(x)-f_{min})/(f_{max}-f_{min})}$
* $\lambda_0=0.5$
該比例以某種方式遞減，解越好，遞減速度越快，範圍越小

---

* 如圖所示，如果搜尋到較佳的解，則解進行「傳播」，即變為候選解，並將浪高恢復到事先設定的最大值
* 如果搜尋到較差的解，則「浪高」遞減，直到浪高減少到零，即用完機會，進入「折射」環節

## 折射 (Refraction)
* $x'(d)=N((x_{best}(d)+x(d))/2, |(x_{best}(d)-x(d))/2|)$
失去所有機會的水波向 global best 靠近，移動到的位置遵守一常態分布，其以兩者中心為分布高點，以兩者距離的一半為一倍標準差

## 碎浪 (Breaking)
* $x'(d)=x(d)+N(0,1)\cdot \beta L(d)$
每當 global best 有進一步突破，其進行一次落點以自身為中心呈現常態分布的搜尋，標準差為邊界寬的一定比例

## 演算法參數
以下是論文的實驗使用的參數：
* $p=50\rightarrow3$
population size 由 50 往 3 線性遞減
* $h_{max}=6$
最大浪高為 6，作者說 5 ~ 6 都有不錯的效果
* $\alpha=1.026$
影響「傳播」範圍縮減率的參數，是針對測試函式集 fine tune 的結果
* $\beta=0.25\rightarrow 0.001$
影響「碎浪」範圍的參數，由 0.25 線性遞減至 0.001，是針對測試函式集 fine tune 的結果
* $k_{max}=min(12, D/2)$
「碎浪」最高改變維度數為總維度的一半，如果超出 12 則最多改變 12 維

## 修改
### 概念
* 簡化複雜而不必要的部分
* Self adaptive
* 內建的 population reduction
* Autoregulation

### 合併「傳播」與「碎浪」
「傳播」與「碎浪」的概念過於相像，都是在自身周圍以一個半徑進行搜索，其不同的點如下：
* 在讓範圍比例常數縮減的方法部分，「傳播」是透過指數方式遞減，「碎浪」則是線性遞減
* 在搜尋落點的分布上，「傳播」是均勻分布，「碎浪」是常態分布

合併的方式如下：
* 不使用比例常數，改用 searcher 之間的距離作為搜尋範圍，達成 self adaptive 與 autoregulation
* 整個演算法的搜尋分布暫時設定為均勻分布

合併後的公式如下：
* $x'(d)=x(d)+rand(-1,1)\cdot(x_{rand}(d)-x(d))$
即是隨機找尋另一 searcher，並以與其的距離作為半徑搜尋自身周圍

### 修改「折射」的公式
* 對 PSO 進行實驗並觀察可以發現，在大多數問題上，global best 的參數會恰好落在 2.0 上。推測這是因為 2.0 時該項造成的搜尋分布是以 global best 為中心。這同時也是合理的搜尋方式
* 本演算法在向 global best 靠近時，分布的中心點落在自身與 global best 的中點，但此點並沒有任何會出現好解的跡象，反而會造成群體中心不能對準較佳的位置
* 前段決定將常態分佈的元素暫時移除，以均勻分布代替
* 全員以 global best 為中心會造成過早收斂，因此將 global best 替換成隨機比自身好的 searcher
* $x'(d)=x_{randbetter}(d)+rand(-1,1)\cdot(x(d)-x_{randbetter}(d))$

### 「浪高」機制的修改
「浪高」是使搜尋能在自身周圍與向 global best 前進之間切換的機制，其有一些特性：
* 在搜尋周圍時需要新解比自身好才取代，但在向 global best 靠近時不需要。此點有利有弊，PSO 和 DE 分別採取不同的做法，雖然概念不盡一致
* 此機制需要一個以經驗法則得出的參數，但此參數或許是此演算法最重要的參數

考慮一致性與簡化和參數的減少，修改如下：
* Searcher 輪流在「以自身為中心搜尋」與「以隨機比自身好的點為中心搜尋」間切換，均要求新解比自身好才取代
* 只要發生任何取代，下一次必定重置回「以自身為中心搜尋」

### 相似公式與概念的合併
* $x'(d)=x(d)+rand(-1,1)\cdot(x_{rand}(d)-x(d))$
* $x'(d)=x_{randbetter}(d)+rand(-1,1)\cdot(x(d)-x_{randbetter}(d))$

可以看出修改後「折射」的公式與修改後「傳播」的公式十分相似，都是以某一 searcher 為中心，以與另一 searcher 之距離作為搜尋半徑，進行落點為均勻分布的搜尋，兩式可以合併如下：

* $x'(d)=x_{center}(d)+rand(-1,1)\cdot(x_{partner}(d)-x_{center}(d))$

其中當「以自身為中心搜尋」時：
* $x_{center}=x$，$x_{partner}=x_{rand}$

當「以隨機比自身好的點為中心搜尋」時：
* $x_{center}=x_{randbetter}$，$x_{partner}=x$


### population redection 部分
根據實驗觀察，本演算法因為將「浪高」機制的參數拿掉，導致在多 local optimum 的 function 中過早收斂，不適合 population reduction，因次放棄原有的 population redection 機制

### 修改後演算法特色
* 極度簡單，只有一種搜尋方式及其變化，和一種簡單的切換機制
* 零參數，達成完全的 self adaptive

## 實驗結果
本次以報告要求中的十個測試函式進行實驗，並與 PSO 與 DE 比對，實驗的條件設置如下：
* PSO：$inertia=0.5,~local~best=2.0,~global~best=2.0$
* DE：$mutation~rate=0.5$
* 函式的維度均為 30 維
* 結果取 30 次執行之算數平均
* 每次執行做 300000 次 evaluation
* 各演算法以 {10, 30, 100, 300} 的 population size 實驗，取最佳組別與其他演算法比較
* 最佳解在零點的函式，每個維度做 bounds 20~40% 的平移

### Ackley
在 Ackley 上收斂速度勝過 PSO 與 DE，最終收斂的數字則差不多

### Griewank
在 Griewank 上與 PSO 一同卡在區域最佳解，平均較 PSO 為優

### Rastrigin
在 Rastrigin 上收斂速度不佳，但最後依然在收斂且比 PSO 快

### Schwefel
在 Schwefel 上很快掉入區域最佳解，推測 PSO 沒有掉入是因為這是帶著趨勢的 function，momentum 類演算法會有較好的表現

### Sphere
在平滑的 Sphere 上收斂速度勝過 PSO 與 DE，尾端的直線是因為採用算術平均時只要有一次不是 0 就會大幅影響收斂圖，整體效果很好

### SumSquares
在平滑的 SumSquares 上收斂速度勝過 PSO 與 DE，尾端的直線是因為採用算術平均時只要有一次不是 0 就會大幅影響收斂圖，整體效果很好

### Zakharov
在平滑的 Zakharov 上收斂速度勝過 PSO 與 DE，尾端的直線是因為採用算術平均時只要有一次不是 0 就會大幅影響收斂圖，整體效果很好

### Rosenbrock
在 Rosenbrock 上收斂速度穩定，勝過 DE，PSO 在跑第一次 30 runs 時是贏的，這次是輸的，可能效果與 PSO 差不多或略輸。

### Michalewicz
在鞍點眾多的 Michalewicz 上效果不佳

### Powell
在 Powell 上收斂速度勝過 PSO 與 DE，但除了 PSO 以外其餘兩個直到最後都還在收斂

### 實驗分析
本演算法在平滑的函式上效果普遍不錯，在有淺 local optimum 的 Ackley 上也有超常的表現，但一旦遇到深度足夠且眾多 local optimum 的函式即會表現不佳。PSO 有時可以靠著 momentum 機制對趨勢的紀錄突破，DE 則是可以透過內部不明的資訊交換突破。

## 結論與未來展望
本演算法在進行修改之後與原先的樣貌已經截然不同，在無參數與簡單的特點上有優勢，但在對較深的 local optimum 的抵抗性上有所不足，其可能可以改進的方向有以下幾點：
* 搜尋落點的分布調整：
本次修改中將搜尋落點的分布統一為均勻分布，如果設為常態分佈或許會有改進
* 「浪高」參數的回歸：
將捨棄的「浪高」參數取回，改變成經過 h 次「以自身為中心搜尋」後切換至「以隨機比自身好的點為中心搜尋」，或許可以增加對區域最佳解的抵抗能力
* 搜尋中心與搜尋範圍的選擇方式：
目前的設定使用「以隨機比自身好的點為中心搜尋」，將隨機方式做出調整，或將決定搜尋範圍的 searcher 調整至離自身較接近的點，或許會有變化
* 加入 DE 機制取代隨機：
將搜尋的落點從機率分布改為從其他 searcher 獲取資訊或許可以獲得 DE 的能力
* 加入 PSO 中動量的機制：
加入類似動量的機制或許可以在 Schwefel 等在整體解空間上有梯度趨勢的函式上獲得好的結果