# 演化式計算作業二-PSO粒子群聚演算法

## 程式架構
大致講解程式架構，介紹比較重要的變數、函式。

python class建構子
初始化每個粒子的位置、初速度。

class PSO():
    def __init__(self, 
                groupsize, 
                dimension, 
                search_space, 
                evaluation_function):
        ...
        # 搜尋範圍
        self.lowerbound = search_space[0]
        self.upperbound = search_space[1]
        # 初速度
        self.velocity = np.random.rand(~~~~)
        
        ...
        ...
        
        # 粒子的位置
        self.pos = np.random.rand(groupsize, dimension)
        # 均勻散佈到空間中
        self.pos = (self.pos - 0.5) * (search_space[1] - search_space[0])
        
        # 先做一次evaluate 用來初始化pbest, gbest
        self.cost = np.zeros(groupsize)
        self.evaluate()
        
        # 初始化pbest, gbest
        # 需要copy以避免兩個attribute參照同一個物件。
        # 操作numpy很常出現這樣的錯誤。
        self.pbest_pos = self.pos.copy()
        self.pbest_cost = self.cost.copy()

        self.gbest_pos = self.pos[self.cost.argmin()].copy()
        self.gbest_cost = self.cost.min()

移動粒子：
$V_{t+1} = w*V_t+c_1*rand_1*v1 + c_2*rand_2*v_2$
$v_1$：當前位置往pbest的向量
$v_2$：當前位置往gbest的向量

    def move(self, w, c1, c2):
        v0 = self.velocity
        to_pbest = self.pbest_pos - self.pos
        to_gbest = self.gbest_pos - self.pos
        
        rand1 = np.random.rand(self.size, self.dimension)
        rand2 = np.random.rand(self.size, self.dimension)

        v = v0*w + c1*rand1*to_pbest + c2*rand2*to_gbest
        
        self.pos += v
        self.velocity = v

更新pbest, gbest

    def update_best(self):
        
        # 需要更新pbest的粒子
        # 當前的cost < 目前的pbest
        update_filter = self.cost < self.pbest_cost
        
        # 更新pbest的位置以及cost
        self.pbest_pos[update_filter] = self.repo[update_filter]
        self.pbest_cost[update_filter] = self.cost[update_filter]
        
        # 更新gbest的位置以及cost
        self.gbest_cost = self.pbest_cost.min()
        self.gbest_pos = self.pbest_pos[self.pbest_cost.argmin()]

main loop:

#建立class object
p = PSO(~~~)

# 做一些初始化
...
...

for i in range(max_iter):
    p.move()  # 粒子移動
    p.evaluate()  # 評估
    p.update_best()  # 更新pbest, gbest
    
    if p.gbest_cost < acceptance:  #達到目標
        break

## 實驗結果
參數：
- 粒子數目 = 1000
- w = ~0.9
- c1 = 0.4
- c2 = 0.2

w（慣性權重）直接影響到探索能力。當w過小，粒子的速度會很快下降，並且收斂到區域最佳解。
c1 (往pbest的權重)影響較小。
c2（往gbest的權重）若是太大，會使得粒子過快群聚，影響搜索範圍。

### 第三題
cost下降圖：

跑500次模擬：
- 成功收斂：500代
- 平均迭代：162.8次
- 平均呼叫evaluate函式：162800次
- 失敗次數：0


### 第十題

cost下降圖：

跑500次模擬：
- 成功收斂：465次
- 平均迭代：135.4代
- 需要呼叫evaluate函式：135400 次
- 失敗次數：35次，佔全部測試的7%


## 與基因演算法的比較

GA的表現參考：[演化式計算作業一報告
](https://hackmd.io/ZDpu4iq1RqGm-XX2gq1W8g)

在單峰的函式（第三題）中，ga有比較好的表現。
在多峰的函式（第十題）中，pso有比較好的表現，但是考量到沒有成功收斂的狀況，可能ga穩定度還是高一些。

但是因為不同的參數有不同的表現，所以這比較不一定準確。