---
# System prepended metadata

title: 演化式計算作業一報告

---

# 演化式計算作業一報告
---
1. 程式架構：
創建一個稱爲Population的類別，擁有「族羣大小」、「基因長度」、「搜尋空間」、「evaluate_finction」以及「基因資料」等屬性。
```python=+
class Population():
    def __init__(self, ......):
        self.group_size = 
        self.gene_length = 
        self.search_space =
        
        # 評估函式
        self.evaluate_function = 
        
        # 基因資料
        self.gene_data = np.zeros(group_size, gene_length)
        
        # 適應度
        self.fitness = np.zeros(group_size)
```
主要的class method。

評估每個個體的適應度
```python=+
    def evaluate(self):
        for i in range(self.group_size):
            self.fitness[i] = self.evaluate_function(self.gene_data[i])
```
基於適應度做排序，可選擇升序或降序。
```python=+
    def sort(self, ascending=True):
        if ascending:
            self.gene_data = self.gene_data[np.argsort(self.gene_data)]
        else:
            ...

```

交配
```python=+
    def crossover(self, baby_number, parents, b=0.5):
    # baby_number(int): 後代的數目
    # parents(int): 可以交配的父代數目
    # b(float): 雙親基因的權數
        for i in range(size):
            # 每次從母代中隨機擇二做crossover
            # b=0.5相當於簡單平均
        
```

變異
```python=+
    def mutate(self, mutation_rate, mutation_var):
        # mutation_rate(float): 每個基因突變的機率
        # mutation_var(float): 突變的變異數，採常態分佈。
```

世代迭代
```python=+
    def generation_iteration(self, parents, elite):
        # parents(int): 可以產生後代的數量， 依照適應度排序
        # elite(int):  直接保留的精英數量
```

## 題目十
---
$f_{10}(x)=-20exp(-0.2\sqrt{{1\over D} \sum _{i=1}^{30}x_i^2}) -exp({1\over D}\sum_{i=1}^Dcos2\pi x_i) + 20 + e$

因為最影響效能的部分是評估函數，所以使用numpy矩陣操作，避免使用for迴圈。
```python
def evaluate_10(x, D=30):
    sum_1 = (x ** 2).sum()
    sum_2 = (np.cos(2 * np.pi * x)).sum()

    cost = -20 * exp(-0.2 * sqrt(sum_1/D)) - exp(sum_2/D) + 20 + e

    return cost
```

![](https://i.imgur.com/hGg7O3n.gif)
這是一個aclkey function，特色就在於它不斷波折的模式，也因此造就了大量的區域最佳解。比起收斂速度，我覺得搜尋廣度是比較重要的。

在試參數時有遇到一個狀況，若是保留太多精英，很快的整個群體的就會充滿了這些的複製品。這種需要lucky strike的函數，還是以廣度作爲優先考量。

族羣大小：1000名
可參予繁衍：前200名
保留精英：三名
突變機率：0.1
突變變異數：當前最佳的fitness


![](https://i.imgur.com/1hzb5LT.png)

藍色及淺藍分別代表當前最佳以及平均的cost。因爲是個尋找極小值的函數，值越小代表適應度越高，參照左側y軸。
紅線是不同個體間基因的變異數，越大代表個體越不相似，參照右側y軸。

大概在第3~30代時，cost下降速度有點慢，不過這時紅線很明顯的上漲，代表族羣有在做搜索而不是過早收斂。

### 結果
在300次測試中：
平均迭代164.4代，平均產生164000個體。
分佈如圖：
![](https://i.imgur.com/ZMbMcYq.png)



## 題目三
$f_3(x)=\sum_{i=1}^D(\sum_{j=1}^ix_j)^2$

用`numpy`的`cumsum()`來達成累積和的效果。
```python
def evaluate_3(x):
    return (x.cumsum() ** 2).sum()
```
![](https://i.imgur.com/uLdAISq.png)


這是一個單峰的函數，所以比起多峰的題目不用太在意過早收斂的問題。
我測出效果不錯的參數如下：
族羣大小：1000名
可參予繁衍：前200名
保留精英：三名
突變機率：0.2
突變變異數：最佳$fitness^{1\over3}$

### 結果
在300次測試中：
平均執行109.96代，平均產生並評估109600名個體。
分佈如圖：
![](https://i.imgur.com/YkWUKms.png)


## 結論
在開局時的突變率及突變量應該要大，才能做到廣度的搜索、不困在區域裡。在終局時突變量應該要小，加快找到區域最佳解。可以使用適當的衰減的函數作為調整。

