Genetic Algorithm ( 基因演算法 )
這可能是所有演算法中最知名的一個，坦白說我讀的相關論文不算多，所以內文如果有誤，歡迎指證！
基因系列的演算法被廣為使用，所以它的類型變化也非常之多，據我的理解，最早最單純的基因演算法，稱為sGA(Standard GA)，大多的基因系列都依循此最初版本的流程，也就是 初始化→選擇與複製→交配→突變 來進行演算。
初始化(Initialization)
在初始化階段先隨機產生定量的個體到母體，後計算個體的適應性。
以TSP問題來說，就是隨機產生多組路線。
以TSP問題來說，就是隨機產生多組路線。
個體(Individual) 與 母體(Population)
是指對問題的一個可能解答，一個個體中有多條基因，以TSP問題為例，基因(Genetic)即是其中任兩節點構成的一條路徑，而個體就是一條由多路徑構成的路線。
許多網路上的個體都是以0、1構成的字串為範例，這是我開始學基因的時候碰到的第一個困難，基本上，個體中的基因並不是一定要用0、1的形式去表達，針對你的問題，你可以用各種不同的資料結構去表達你的基因與個體，只要該結構符合你適應性函數的需求，且能正確的運作上面提到的四個步驟即可！
※在範例中我以自訂類別Node表達一個TSP節點，以ArrayList表達一條路線(也就是一個個體、一個可能的解)，而ArrayList中Node的索引順序即為從起點到終點的路由。
母體是多個個體的集合，內含的個體數可以自行決定。
適應性(Fitness) 與 適應性函數(Fitness Function)
所謂適應性，就是個體在解決目標問題上表現的好壞程度，適應性函數即評估該程度的準則。 以TSP問題來說，個體的適應性就是路線的距離，而適應性函數就是距離越短越好！
選擇與複製(Reproduction)
在此步驟，我們利用前步驟計算出的適應性，選擇解決問題能力較佳的個體，並複製量產它們投入交配池；要選出幾個並不一定，以sGA來說是第一名跟第二名兩個。
※上述這種方式稱為競爭式選擇(Tournament Selection)。除了競爭外，常見的還有菁英式選擇(Elitism)與輪盤式選擇(Roulette Wheel)。
交配池(Mating Pool)
是被選擇上的個體的集合，個體們在此集合中等待進行交配。
交配(Crossover)
在此步驟，我們對交配池中的個體進行基因的交換動作，並期待透過此動作找出更好的基因組合，進行交換的基因數量不限，一般網路上0、1組合的範例是進行XOR運算，若以TSP為例，則為交換兩個體的路徑。
首先先在圖A(個體A)中雖機選取一個索引作為交換的標的，此例假設選中索引2，索引2在圖A中的節點是3號，接著找出3號節點在圖B中的索引，發現是索引4，最後交換A與B的索引2與4中的節點。
※把圖畫出來才發現我的交配策略寫得有瑕疵，交配單位應該是路徑而不是節點，這個方法沒辦法讓兩個體都獲得對方的特徵，由圖A2及B2這兩個新個體可以看出，只有B2獲得了A的特徵，而A2沒有獲得B的特徵。
總之，交配的概念大致是如此，改天再修正交配的副程式。
突變(Mutation)
選擇與複製是為了保留較優秀的個體，交配是為了保留較優秀的基因，但突變則是刻意隨機改變基因的構成，目的是為了當陷入區域解時能夠跳脫出來，提高找到最佳解的機率。
若為0、1組合是隨機對基因進行XOR運算，以TSP為例，則是隨機改變個體的部分路徑。
上圖為例，我在圖A隨機選取兩個節點，剛好選到索引2跟3，然後就交換這兩個節點的順序，產生出新的個體圖A2。
完成突變的個體將會從交配池中重新被加回母體，並且再次從選擇與複製步驟開始進行次下一世代的演化。
世代(Generation)
是指基因演化總共進行了多少次的流程，由於基因屬啟發式演算，所以一般終止條件即是設定再經過多少世代後終止演算。
最佳解(Global Solution) 與 區域解(Zone Solution)
說明這兩個術語，最簡單的例子應該是我指導老師對爬山演算的講解。
假設我們的目標是攀登台灣第一高峰的玉山，而我們的起點是在高雄，若以爬山演算的邏輯，即是不停地尋找自身四周的最高點並移動。
但這種方式會造成一個問題，由於從高雄出發，我們很快地會爬到附近最高的壽山上，並且由於演算邏輯的限制，而無法離開山頂。
在這個例子中，壽山就是我們所謂的區域解，而玉山才是最佳解，因此多數的啟發式演算法都需要類似突變的策略，讓解有機會向山頂外嘗試。
以上的內容與範例都是以sGA為例，常見的基因演算法的演進過程如下
sGA→EDA→cGA→pe-cGA
EDA = sGA + Local Search
最早的基因演算法雖然有交換基因，但不會保留前一代的最佳解，也就是說演化大方向上是會慢慢進步的，但每一個子世代的最佳解績效不見得能贏過上一代，甚至有連續數個世代都退步的可能性。
所以過去的研究者在EDA中導入了Local Search的概念，若次世代未能產生更好的解，則保留前代的最佳解來參與下一世代演化；這個做法能保障至少不會發生退步的情況，提高收斂的速度。
收斂(Convergence)
指的是由比較差的解推演到區域解或最佳解的過程。
cGA = EDA + Probability Vector
cGA即是前面提及的選擇與複製方式中的輪盤法，輪盤即是由一個機率向量構成，個體是否選入交配池將以轉動這個輪盤來決定，每個個體佔盤面的面積是由它的成本佔總成本的比例決定，成本越小者(適應性越高)佔盤面面積越大，選中機率也就越高。
※另一種情況是，所有的個體都可以參與交配，但是交配的比例以機率向量決定。
pe-cGA = cGA + Elitism
在cGA中輪盤是當代的每一個個體都可能被選上(只是機率高低不同)，而pe-cGA則是只有當代最優秀的個體可以被加入輪盤中，輪盤的構成則是連續數代中最優秀個體的集合。
ref：藍影、《A compact genetic algorithm for the network coding based resource minimization problem》。
source code：以TSP問題為例，請在TSP.java的主程式中執行executiveSGA()或executiveEDA()。
在此步驟，我們利用前步驟計算出的適應性，選擇解決問題能力較佳的個體，並複製量產它們投入交配池；要選出幾個並不一定，以sGA來說是第一名跟第二名兩個。
※上述這種方式稱為競爭式選擇(Tournament Selection)。除了競爭外，常見的還有菁英式選擇(Elitism)與輪盤式選擇(Roulette Wheel)。
交配池(Mating Pool)
是被選擇上的個體的集合，個體們在此集合中等待進行交配。
交配(Crossover)
在此步驟，我們對交配池中的個體進行基因的交換動作，並期待透過此動作找出更好的基因組合，進行交換的基因數量不限，一般網路上0、1組合的範例是進行XOR運算，若以TSP為例，則為交換兩個體的路徑。
我實作的方式如上圖。
首先先在圖A(個體A)中雖機選取一個索引作為交換的標的，此例假設選中索引2，索引2在圖A中的節點是3號，接著找出3號節點在圖B中的索引，發現是索引4，最後交換A與B的索引2與4中的節點。
※把圖畫出來才發現我的交配策略寫得有瑕疵，交配單位應該是路徑而不是節點，這個方法沒辦法讓兩個體都獲得對方的特徵，由圖A2及B2這兩個新個體可以看出，只有B2獲得了A的特徵，而A2沒有獲得B的特徵。
總之，交配的概念大致是如此，改天再修正交配的副程式。
突變(Mutation)
選擇與複製是為了保留較優秀的個體，交配是為了保留較優秀的基因，但突變則是刻意隨機改變基因的構成，目的是為了當陷入區域解時能夠跳脫出來，提高找到最佳解的機率。
若為0、1組合是隨機對基因進行XOR運算，以TSP為例，則是隨機改變個體的部分路徑。
上圖為例，我在圖A隨機選取兩個節點，剛好選到索引2跟3，然後就交換這兩個節點的順序，產生出新的個體圖A2。
完成突變的個體將會從交配池中重新被加回母體，並且再次從選擇與複製步驟開始進行次下一世代的演化。
世代(Generation)
是指基因演化總共進行了多少次的流程，由於基因屬啟發式演算，所以一般終止條件即是設定再經過多少世代後終止演算。
最佳解(Global Solution) 與 區域解(Zone Solution)
說明這兩個術語，最簡單的例子應該是我指導老師對爬山演算的講解。
假設我們的目標是攀登台灣第一高峰的玉山，而我們的起點是在高雄，若以爬山演算的邏輯，即是不停地尋找自身四周的最高點並移動。
但這種方式會造成一個問題，由於從高雄出發，我們很快地會爬到附近最高的壽山上，並且由於演算邏輯的限制，而無法離開山頂。
在這個例子中，壽山就是我們所謂的區域解，而玉山才是最佳解，因此多數的啟發式演算法都需要類似突變的策略，讓解有機會向山頂外嘗試。
以上的內容與範例都是以sGA為例，常見的基因演算法的演進過程如下
sGA→EDA→cGA→pe-cGA
EDA = sGA + Local Search
最早的基因演算法雖然有交換基因，但不會保留前一代的最佳解，也就是說演化大方向上是會慢慢進步的，但每一個子世代的最佳解績效不見得能贏過上一代，甚至有連續數個世代都退步的可能性。
所以過去的研究者在EDA中導入了Local Search的概念，若次世代未能產生更好的解，則保留前代的最佳解來參與下一世代演化；這個做法能保障至少不會發生退步的情況，提高收斂的速度。
收斂(Convergence)
指的是由比較差的解推演到區域解或最佳解的過程。
cGA = EDA + Probability Vector
cGA即是前面提及的選擇與複製方式中的輪盤法，輪盤即是由一個機率向量構成，個體是否選入交配池將以轉動這個輪盤來決定，每個個體佔盤面的面積是由它的成本佔總成本的比例決定，成本越小者(適應性越高)佔盤面面積越大，選中機率也就越高。
※另一種情況是，所有的個體都可以參與交配，但是交配的比例以機率向量決定。
pe-cGA = cGA + Elitism
在cGA中輪盤是當代的每一個個體都可能被選上(只是機率高低不同)，而pe-cGA則是只有當代最優秀的個體可以被加入輪盤中，輪盤的構成則是連續數代中最優秀個體的集合。
ref：藍影、《A compact genetic algorithm for the network coding based resource minimization problem》。
source code：以TSP問題為例，請在TSP.java的主程式中執行executiveSGA()或executiveEDA()。
沒有留言:
張貼留言