HackMD
演化計算導論
演化計算基本架構
概述
演化計算是一個基於生物進化原理的優化和搜索方法，用於解決各種組合優化問題，機器學習，人工智慧和其他領域。演化計算方法包括遺傳算法（Genetic Algorithms），演化策略（Evolution Strategies），差分進化（Differential Evolution），粒子群優化（Particle Swarm Optimization）等。這些方法都具有相似的基本架構。
基本架構
- 個體表示（Representation）：在演化計算中，解決方案被表示為一個或多個個體，這些個體通常是由某種編碼方式表示的。這種表示方式可以是二進制、整數、實數、字串或其他形式，具體取決於問題的性質。
- 初始種群（Initial Population）：演化計算算法首先創建一個初始個體群體，通常是隨機生成的。這個初始種群是搜索過程的起點。
- 適應度函數（Fitness Function）：適應度函數評估每個個體的性能，它定義了解決方案的品質。適應度函數的目標是最大化（或最小化），根據具體問題的性質而定。
- 選擇（Selection）：在每代中，根據個體的適應度，一部分個體被選中用於繁殖下一代。通過選擇操作，優秀的個體更有可能被選中。
- 交叉（Crossover）：選中的個體進行交叉操作，創建新的個體。交叉操作模擬了生物學中的基因交換過程，產生了後代。
- 變異（Mutation）：部分個體可能會經歷變異操作，這通常是在個體的基因中引入隨機變化，以增加多樣性。
- 生成下一代（Generate Next Generation）：通過選擇、交叉和變異操作，創建下一代個體。這一代的個體將取代上一代，並繼續搜索過程。
- 停止條件（Termination Criteria）：搜索過程持續進行，直到滿足某個停止條件，例如達到最大迭代次數、適應度達到一定閾值，或達到時間限制。
- 結果（Result）：最終的搜索結果是最優的個體，其對應的解決方案是問題的近似最優解或一個高品質解。
hill-climbing
原理
找局部最佳解
比如說下一步有ABC三個走法，其中A走法的cost最低，則選擇A
缺點
只找到局部最佳解，沒辦法找到全局最佳解
tabu search
原理
為了破解局部最佳解的盲區，所以在禁忌搜尋法中，在找到一處的局部最佳解後，就將其列入禁忌表中，不能再被訪問，以鼓勵最佳解的多樣性，過了一段時間之後，禁忌表中的局部最佳解將會被釋放，以繼續向下探索。
實作步驟
- 從初始解開始，通常是隨機生成的。
- 在每一步中，生成相鄰的解，評估它們的品質，並選擇一個最佳的相鄰解。然而，禁忌搜索不總是選擇最佳解，而是優先考慮那些不在禁忌表中的解，以鼓勵多樣性。
- 更新禁忌表，將新選擇的決策添加到禁忌表中，同時去除已經過時的決策。
- 重複步驟2和步驟3，直到達到停止條件，例如達到一定的迭代次數或達到一個時間限制。
- 返回搜索過程中找到的最佳解或高品質解。
應用
禁忌搜索的效能取決於禁忌表的設置、相鄰解的生成方法、目標函數的定義等因素。這個算法常用於解決組合優化問題，如旅行商問題（TSP）、排程問題、集合覆蓋問題等，並且已在實際應用中取得了成功。禁忌搜索的靈活性和能力避免局部最優解使其成為一個有價值的優化工具。
Bit String（位元字串）
- 表示方式：將問題的解表示為一個由0和1組成的位元字串，每個位元對應問題的一個參數或特徵。
- 突變操作：可以通過對位元的翻轉（0變為1，1變為0）來進行突變。
- 交叉操作：可以通過將兩個位元字串交叉來產生新的後代。
Integer Array（整數陣列）
- 表示方式：將問題的解表示為一個整數陣列，每個元素對應問題的一個參數或特徵。
- 突變操作：可以通過改變陣列中的某個整數值來進行突變。
- 交叉操作：可以通過交換兩個整數陣列的部分來產生新的後代。
Real-Valued Array（實數陣列）
- 表示方式：將問題的解表示為一個實數陣列，每個元素對應問題的一個參數或特徵。
- 突變操作：可以通過改變陣列中的某個實數值來進行突變。
- 交叉操作：可以通過交換兩個實數陣列的部分來產生新的後代。
Permutation（排列）
- 表示方式：將問題的解表示為一個排列，即元素的順序。
- 突變操作：可以通過交換排列中的兩個元素來進行突變。
- 交叉操作：可以通過部分映射交叉等方法來產生新的排列。
Tree（樹狀結構）
- 表示方式：將問題的解表示為一個樹狀結構，其中節點表示操作或值，邊表示操作的順序或關係。
- 突變操作：可以通過添加、刪除或修改樹的節點來進行突變。
- 交叉操作：可以通過交換兩個樹的子樹來產生新的樹。
