# INDRODUCTION TO ARTIFICIAL INTELLIGENCE
## HW1

## 1. (10%) 以文字說明如何實現 P1 (Brute Force) ？

temp = 999999 #initialize the value 
for x in range(x_lower_bound, x_upper_bound):
    for y in range(y_lower_bound, y_upper_bound):
        if func(x,y) <= temp: 
            temp = func(x,y)
            temp_x, temp_y = x, y
return temp, temp_x, temp_y #return [minimun of f(x,y), x, y]

以2個 `for` 迴圈遍巡在 `x` 和 `y` 的上下界中的所有數值組合
若帶入`func()`得到的值比`temp`小就會替換掉
不斷重複這個動作直至所有組合都執行過後結束這個程式
> 以作業中所附的`input.txt`給的 x 和 y 範圍，該過程會執行
> [60-(-60)]*[70-(-30)]=12000 次 func()

## 2. (20%) P2 (SA,模擬退火法) 透過調整參數觀察到什麼？

模擬退火法中經典的Metropolis演算法，以一定概率的接受新的狀態
\begin{equation}
Probability=
\left\{
\begin{array}{lr}
1 &, E(x_{new})\ <\ E({x_{old}}) \\
\exp(-\frac{E(x_{new})\ -\ E({x_{old}})}{T}\ \ ) & E(x_{new})\ \geq\ E({x_{old}})\\
\end{array}
\right.
\end{equation}

經典模擬退火演算法的降溫方式為
\begin{equation}
T(t)=\frac{T_{0}}{log(1+t)} \\
\end{equation}

作業中嘗試的降溫方式為
\begin{equation}
T(t)=\frac{T_{0}}{1+t}
\end{equation}

以下方組合嘗試：
| Initial_T | Minimun_T | The annealing schedule|
|:---------:|:--------:|:--------------:|
| 1000 | 10 | $T(t)=\frac{T_{0}}{1+t}$|
:::danger
發現Metropolis演算法求換成較差的neighbor的機率非常高
導致求最小解的過程會不斷替換，沒有意義
:::
經嘗試後發現關係為求解時`Initial_T`和`Minimun_T`的數量級會影響該機率
$\exp(-\frac{E(x_{new})\ -\ E({x_{old}})}{T}\ )$ 中 $E(x_{new})\ -\ E({x_{old}})$ 和 $T$ 若相差太多倍會使得機率趨近於1。
因而調整`Initial_T`和`Minimun_T`的比例以及降溫的方法
| Initial_T | Minimun_T | The annealing schedule|
|:---------:|:--------:|:--------------:|
| 0.01 | 0.00001 | $T(t+1)=T(t)*\beta$ ($\beta=0.999$)|
可得出結果(總執行次數：6906)：
左方為求解的過程中最小值的變化，而右邊為求解過程中記錄發生替換的變化(`值=1`為找到較小解、`值=2`為$E(x_{new})\ \geq\ E({x_{old}})$ 但替換成較差的neighbor的發生次數)

嘗試下列組合
| Initial_T | Minimun_T | The annealing schedule|
|:---------:|:--------:|:--------------:|
| 0.01 | 0.00001 | $T(t+1)=T(t)*\beta$ ($\beta=0.99$)|
| 0.01 | 0.00001 | $T(t+1)=T(t)*\beta$ ($\beta=0.97$)|

$\beta=0.99$ (總執行次數：689)
$\beta=0.97$ (總執行次數：228)
:::info
**發現$\beta$越接近1**過程中**接近最小的過程越快**(以執行的整個過程而言)
:fire: **但其中也發現$\beta=97$時並未找出最小解就執行完畢了**
:zap: **注意：** 執行的次數較多，且接近最小值的執行次數仍比較多
:::

:::success
接下來嘗試以固定機率將最小值替換成較小的解，嘗試下列組合
:::
$P=0.01$ 且 $\beta=0.999$ (總執行次數：4604)
$P=0.01$ 且 $\beta=0.99$ (總執行次數：460)
$P=0.001$ 且 $\beta=0.999$ (總執行次數：4604)
$P=0.001$ 且 $\beta=0.99$ (總執行次數：460)
發現**當 $P=0.01$ 且 $\beta=0.99$ 的組合**過程中發生替換成較差neighbor的圖形較理想，有替換成較差的值最終也能收斂於最小解，且執行的次數也較少。
:::warning
:zap: 該方法也具機率性無法找到最小解
:::
## 3. (10%) 比較兩方法有哪些優缺點？實作過程的心得？
暴力法中所有的組合都會被嘗試過一遍，雖然可能需要執行較多次，但**保證得出來的一定是最小解**，但當精度提高後，可能需要小數點後3位、甚至更高的需求，而**執行的次數則是以$10^n$成長**，但**可以作為不同測試方法的baseline**。
相較之下，模擬退火演算法具有一定的機率得到最佳解，缺點也包含**需要針對各種任務設計不同的參數**、演算法，但模擬退火卻大大減少需要測試的次數，利於在**提高精度的時候可以減少不少運算量**。

在設計模擬退火法時，我認為主要影響的參數有：
1. 如何取下一個嘗試的值(如何在函式中移動)，若移動的太多則會錯過最佳解，若太小有可能卡在區域最佳解，本次作業隨機數取值的範圍為總範圍的$\frac{1}{10}$(移動的step為總範圍的$\frac{1}{10}$以內)

    x_new = x + random.randint(ads(x_lower_bound)*-0.1, x_upper_bound*0.1)
    y_new = y + random.randint(abs(y_lower_bound)*-0.1, y_upper_bound*0.1)

2. 模擬降溫的方法會影響執行的次數
3. 如何設計替換成較差解的方法，可以設計成隨著執行次數增加減少替換的機率(假設在會找到最佳解的基礎上)
4. 找的起始點

寫作業的時候蠻像在調整神經網路的參數，但依據不同的任務需要調整找解的方法，而了解運作的原理則有助於較有系統的調整。
:::info
我認為該種找尋方法依賴於對題目的理解，若無法公布測資則無法針對題目做特定的優化方法，可能會影響到是否能找出最佳解。
:::