---
tags: 107-2, EC, GA
---
# 演化計算 Final Exam
> [color=#0d965d] 連結：http://bit.ly/EC_exam_0416235
>
> [name=**0416235 劉昱劭**]
---

## 1. GA
Let $S_1=$ `**1****10***` and $S_2=$ `*1*0*1******` be two schema
* (a) Give the order $o(\cdot)$ and the defining length $\delta(\cdot)$ of $S_1$ & $S_2$
order 表 schema 中被定義位元 (i.e. not don't care) 的數量。
defining length 表第一個和最後一個被定義位元的距離。
$o(S_1)$ = 3, $~\delta(S_1)$ = 9 - 3 = 6
$o(S_2)$ = 3, $~\delta(S_2)$ = 5 - 1 = 4

> > (b)~(e)
> >* **Holland's schema theorem (Approximated)**:
> > * 此定理描述：
> > 隨著 generation 經過， order 和 defining length 較短、且 fitness 在平均之上的 schemata 較容易繼續存活於 population。
> > * 
> > * $m(H,t)$ 描述在第 t 代，符合 schema $H$ 的 indiviudal 數量。
> > * $f(H)$ 表 schema H 的 fitnessX
> > * $\overline{f}$ 表所有符合此 schema 的 individuals 的平均 fitness

* (b) Probability for a 1-point crossover operator with a crossover rate $p_c$ to break $S_1$

* 由 crossover 破壞 schema $S_1$ 的機率：$p_c\dfrac{\delta(S_1)}{l{S_1}-1} = p_c\times\dfrac{6}{11}$

* (c\) Probability for a mutation operator with a mutation rate $p_c$ to break $S_1$
* 由 mutation 破壞 schema $S_1$ 的機率：$o(S_1)p_m= 3\times p_m$
* (d) Proabability that $S_1$ survives from (b) & (c\)'s operation
* $1 - p_c\dfrac{\delta(S_1)}{l_{S_1}-1} - o(S_1)p_m ~= ~1-\dfrac{6p_c}{11}-3p_m$
* (e)
* 由 crossover 破壞 schema $S_2$ 的機率：$p_c\dfrac{\delta(S_2)}{l_{S_2}-1} = p_c\times\dfrac{4}{11}$
* 由 mutation 破壞 schema $S_2$ 的機率：$o(S_2)p_m= 3\times p_m$
* schema $S_2$ 存活的機率：

$1 - p_c\dfrac{\delta(S_2)}{l_{S_2}-1} - o(S_2)p_m ~= ~1-\dfrac{4p_c}{11}-3p_m$

>> **Building Block Hypothesis of Genetic Algorithm**
>> * Building blocks are defined as:
>> low order, low defining-length schemata with above average fitness.
>> * Building blocks 提供有用的 (因 fitness 高，可能有用) 資訊，比起去嘗試所有可能的 schemata，不如留下又短又優秀的這些 schemata (i.e. building blocks) 來做 crossover。
>> * Holland's schema theroem 便是在說 building block 傾向於留在 population 參與往後的 operation。

* (f)
* $S_1, S_2$ 以 order 和 defining length 都蠻短的 (當然，是否足夠短其實要看問題決定)，尤其是 defining length 較短的 $S_2$，以這點來說他們也許可當作 building block 的候選人。
* 但因我們不知道這兩個 schema 的 fitness 好壞，因此無法確定他們是否該做為 building blocks。

## 2. Niching techniques

| Fitness | 10 | 20 | 30 | 40 |
| ------- |---|---|---|---|
| Fitness Sharing| 100|200|300|400|
| Deterministic Crowding| 250|250|250|250|

>> 結果應類似此圖：
>> 
* Fitness sharing 和 Deterministic crowding 都是維持 niche 的方式。
* Fitness sharing 的概念較像是環境負載力，每個 local optimum 不能無上限的容納一堆 individual，若有多個 individual 能達到同一個 local optimum，其 fitness (像是環境負載力) 會相對下降，以阻止其他 individual 繼續往同一個 optimum 靠近。
* 我們設計一個 sharing function 將 individual 和其 neighbors 的 fitness 一起下降，因此能用 selection 自動砍掉一些**相似度很高的 individual** (i.e. 佔據相同 peak 的 individuals)，以此分散 individual 的分布，或說維持 population 的多樣性。
* Fitness sharing 期望的結果是 individual 數量和 fitness 成比例的分配。
* 題目的 fitness function 有四個 peak，10:20:30:40。
* individual 數量的分布也應維持相同比例 100:200:300:400

* crowding 期望完全均分 individual 到每一個 optimum 上，因此此題期望的分布會是 250:250:250:250 = 1:1:1:1
* 我們設計一個量測 individual 間 distance(similarity) 的函式，
每次 crossover(or other binary operator) 產生子代時，量測不同的 pair 方式 (p1o1+p2o2 或 p1o2+p2o1) 的 distance，取較聚集的那種來進入 survival selection。

* 相較於 Fitness sharing 由 selection 機制，自動將過於擁擠的 individual 淘汰，Deterministic crowding 像是多插入一個 crowding operator 在 selection 之前，相對主動地保證 population 有達到 crowding/niching 的效果。

---

## 3. Local Search (memetic algorithm)
* 假設我們設計了一個 Larmarkian 的 local search operator $L(x)$，
和一個 Baldwinian 的 local search operator $B(x)$：

|Local search|After $L(x)$|After $B(x)$|
|------- | --------------|---|
|individual $x$| $x^*=L(x)$ | $x$ |
|fitness $f(x)$| $f(L(x))=f(x^*)$| $f(B(x))=f(x^*)$|
|Search space|spikely reduce to discrete grid| no change

* Larmarkian local search 會直接將 individual $x$ 用 local search 找到的 local optimum $x^*$取代，並更新該 individual 的 fitness 成 $f(x^*)$。
* 如果對 population 內所有 individual 做 Larmarkian local search，population 的多樣性會急速下降。
* 如果 fitness function 是有很多 local optimum (e.g. Ackley function)，那可能多樣性會衰減慢一點，越少 local optimum 的 local function，越可能在很少的 (甚至一、兩個) generation 之內，就會直接收斂成所有 individual 都長一樣。
* 全部的 individual 都變成 local optimum，也就是 fitness function 上的 peak，search space 會退化到類似 grid search，因 individual 只有可能位在那幾個 peak (像是格子點)。

* Baldwinian local search 只會更新 fitness 成 $f(x^*)$，而 individual 會保持原狀，所以 search space 並不會因 Baldwinian local search 而改變。

* 長期來看，靠近較好 optimum 的那些 individual，因為擁有較高的 fitness，可能會慢慢 dominate 整個 population，因此 Baldwinian local search 有可能使得所有 individual 都收歛到 global optimum 上 (當然，要先有 individual 在 global optimum 附近)。

## 4. Multiobjective problem
### 4-1. 考慮 search space
* feasible region 是由兩個不等式畫開的右半平面
* 兩條邊界有一個交點 (0.8, 1)，可得 $x_1\ge0.8$
> 

### 4-2. 考慮目標函式

| |$min~ f_1=2.5x_1-2$|$min~ f_2=\dfrac{1+x_2}{x_1}$|
|------- | --------------|---|
|search space| 若要最小化 $f_1$，<br>則應該取靠左的點，<br>即在右半平面上，<br>兩條邊界上的所有點 | 若要最小化 $f_2$，因 $x_1$ 恆正，因此應取越小的 $x_2$ 越好，<br>應取靠下的點，即在右半平面上，下面那條邊界上的所有點：|
|optimal solutions| $\{(x_1, x_2)~ \vert$<br>$(~5x_1−3x_2=1 \lor 5x_1+2x_2=6)$<br>$\land ~x_1 \ge 0.8 \}$| $\{(x_1, x_2)~ \vert ~5x_1+2x_2=6 \land x_1 \ge 0.8 \}$|
|Plot|||
* 取兩組 optimal solutions 的交集，即 $f_2$ 的最佳解 $\{(x_1, x_2)~ \vert ~5x_1+2x_2=6 \land x_1 \ge 0.8 \}$

---

### 4-3. 畫出 pareto front 跟其對應的 solutions $(x_1, x_2)$
* 下圖藍點可看到 $x_1$ 最小的那個 solution 是 (0.8, 1)
> 
* 任取線上的另一點，大約是 (4.8, -9)，也落在$~5x_1+2x_2=6$，如同上面分析的，
能造成最佳 fitness 的 solutions 就是 $~5x_1+2x_2=6 \land x_1 \ge 0.8$ 上的點。
>

---

### 4-4. MATLAB code for **problem 4**

% To plot search space
[x, y] = meshgrid(v);  
conditions = (5*x+2*y>=6) & (5*x-3*y>=1);
cond = zeros(length(v)); % Initialize
cond(conditions) = NaN;
surf(x, y, cond)
view(0,90)

% To plot the pareto front & corresponding solutions
function f=my_first_multi(x)
f(1)=x(1)*2.5 - 2;
f(2)=( 1 + x(2) )./x(1);
end

fitnessfcn=@my_first_multi;

nvars=2;
lb=[-100,-100];
ub=[100,100];
A=[-5 -2; -5 3]; b=[-6; -1];
Aeq=[];beq=[];

opt=optimoptions('paretosearch','PlotFcn',{'psplotparetof' 'psplotparetox'});
[x,fval] = paretosearch(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,[],opt);