遺傳模擬退火算法的優化研究

蕭秋蘭

（1 閩南科技學院計算機信息學院 福建 泉州 362332）

（2 大數據與人工智能福建省高校重點實驗室 福建 泉州 362332）

0 引言

在人類的不斷探索中，越來越多的復雜性和系統性問題呈現出來。組合最優問題是一個典型而又具有代表性的問題。例如AGV的小型汽車調整、CAD/CAM一體化的刀具軌跡優化、配送路徑優化、IC設計等。所有的問題都可以被轉換成最優的問題。試驗結果也適用于其他的工程問題，所以對求解最優問題的高效求解是非常有用的。在此基礎上，本文對路徑最優解的逼近方法進行了大量的探討。遺傳算法和模擬退火算法都是以概率為基礎的隨機尋優方法。遺傳算法采用基于群體的爬山法進行尋蹤，具有良好的尋蹤性能，但其收斂性能不強，且易于在局部優化中迷失[1]。而模擬退火則將個別的個體視為最優目標，它的局部尋優效果更好，收斂速度快，跳躍性好，能夠跳過最優的周期，但其整體的尋優能力并不好。所以，兩者組合既能有效地解決彼此的不足，又能最大限度地利用各自優勢，從而防止局部最佳化。在此之前，曾有一種方案將兩類方法有機地組合在一類新的遺傳算法中[2]。

1 遺傳模擬退火算法理論基礎

1.1 模擬退火算法概述

在1953年，Metropolis引入了一個新的隨機模式，它被稱作Metropolis判別，并在 Metropolis判別的基礎上給出了一個新的模型[3]。模擬退火方法的思路是對熱環境下的熱退火進行仿真，以求出最佳的組合最優問題。模擬退火是一種從固態退火中衍生出來的方法，它將固態加熱到一定程度，然后慢慢降溫。當加熱的時候，固態顆粒會隨著加熱而變成不規則的狀態，隨著時間的推移，顆粒的內能逐漸增加，顆粒逐漸趨于均勻，最終在室溫下內能下降到最低點。

該方法具有以下特點：①根據 Metropolis標準，模擬退火算法將會接收一個不“好”的結果，在接收非“好”的情況下，該方法將從局部最優中跳出來，接著再進行進一步的尋找，直至得到最優結果。②模擬退火方法得到的結果與初值不相關，也就是說，該方法的最后求解與迭代初始值沒有關系。③模擬退火方法具有計算簡便、易于實現NP（non-deterministic polynomial）難的特點。然而，模擬退火方法也有其不足之處：①模型的性能會被參量—制冷速度q所決定。如果降溫速度低，則需要更多的時間來進行優化求解。如果降溫速度太高，則可以得到更好的結果，但是也有可能會忽略最好的結果。要想得到降溫速度q，必須經過大量的試驗。②運算速度較慢。模擬退火方法對初溫、降溫速度和終端溫度都有很大的影響，而且需要對各個溫度下的Metropolis判據進行優化，而且該方法具有很好的收斂性[4]。

1.2 遺傳算法概述

美國芝加哥大學的Holland在1967年基于達爾文的生物學演化理論以及孟德爾基因理論，發展了一種叫作基因演算法的演化方法[5]?；蜓菟惴ㄔ谧匀贿z傳和自然選擇中的繁殖、雜交和突變等方面進行了仿真，并給出了相應的方法，在該方法中，每個問題的解決方案都被編入一條與自然界中某一條染色體相匹配的染色體。

（1）該方法主要包括以下幾個方面：①編碼：通過選擇合適的方法，把問題的答案進行編碼，使之成為電腦能夠辨識的格式。②原始群體：由chromsize條染色體組成的群體。該方法以chromsize條染色體為初始點進行了搜尋。③適應性評價：根據適應程度對方案進行評價。在進行遺傳算法的過程中，采用基于目標函數的數學建模方法，來決定該方法的適用范圍。④選擇運算：通過選擇運算可以從現有群體中篩選到較高的親本，高適應性的則有可能成為父系后代[6]。⑤交叉：新一代的染色體可以由交叉處理獲得。⑥突變運算：突變運算可以在特定的概率下，隨意地修改特定的基因，從而生成新的遺傳，維持遺傳的多樣化。

（2）該方法主要包括：①群體的大?。喝后w大小是該群體中的染色體數目。群體數量的確定，主要是從遺傳的角度來看，群體數量盡可能大，不會落入局部最好；從計算速度上看，人口數量的增大會引起運算量的增大。人口的大小要視現實問題而定，人口大小的建議是0～100。②變異概率：一種與自然遺傳的遺傳變異相似的微小概率干擾。通常的數值是0.0001～0.29。③交配概率：一種與自然生殖中的染色體的交叉組合相似的遺傳變異。這個數值通常在0.4～0.99之間[7]。

2 遺傳模擬退火算法設計

遺傳模擬退火算法是一種通過模擬被測樣本點的遺傳狀態，模擬樣本點之間的遺傳關系而構建出來的一種優化算法。在進行訓練之前，本文首先用簡單的模擬退火算法將樣本點進行隨機排列。算法不需要經過反復變異。在訓練時，本文利用遺傳算法中遺傳編碼功能（transcription）作為初始遺傳因子。然后利用基因編碼功能（rgp）或隨機選擇功能（interpression）來對每個變異進行遺傳編碼（excel），從而使得被測樣本點保持遺傳穩定性不變。具體步驟如：（1）確定最優化目標函數和終止準則；（2）根據實際情況設定參數α和b,其中β為適應度函數值；（3）按照一定規則調整參數c,并且保證其與待測值的偏差最??；（4）重復上述操作直至達到目標函數最大值；（5）重復以上步驟,直到滿足條件。這個過程實際上是一個在遺傳模擬退火算法中建立不變性模型的過程。因此，可以將上述過程理解為一種將被測樣本點作為遺傳信息載體（DNA、RNA、tgp或looks等）進行繁殖處理，通過人工構建子種群使其適應基因編碼所提供遺傳信息而實現無變異模型，并在此基礎上進行進化形成新種群的過程。通過遺傳模擬退火算法，本文可以了解到哪些基因沒有變異，哪些基因仍會受到相應生物條件約束[8]。

隨機排列是在樣本點隨機分配的基礎上產生的。因此它能夠滿足對遺傳信息（matrix）獲取的基本需求。對隨機排列的定義為：將每個序列隨機地排列在一個節點上，并將每個序列隨機地取一個序號（表示序列的初始值）以適應該序列本身。在此規則下，本文利用了最小二乘來確定序列大小和最小二乘系數，同時利用了最小二乘系數最小化這個規則來求解序列大小和最小二乘系數值。下面是樣本點隨機排列的實驗結果：當種群個數不變時，每一種序列都會增加一個新子種群；當種群個數越多時，每一個序列都會增加一個新子種群（表示種群個數的線性組合）。本文以圖1中表示各序列之間的相對距離為單位：當本文在每個序列中計算不同長度乘以不同寬度時可以得到樣本點隨機排列時序列大小以及各序列之間相對距離之間的函數關系：那么這些序列大小會隨時間而變化，但是距離越長或者越短它們之間的關系則越穩定。因此可以得出在所有序列越長（大于4/4）各序列之間相對距離就越大。

將本文想要達到的優化目標設為初始目標函數W（x）時，初始遺傳因子為（0,x），為f（x）的一階導數。那么初始因子為a和b即可以通過下列公式求得：其中b表示目標函數g（x）和g（y）在訓練時的初始值，為b在訓練過程中選取的初始參數。本文假定目標函數g（x）取值f（x）為初始值。假設本文想要得到一個給定權重c，本文首先得到其權重a為1（b=1/2），則初始變量c在所有給定權重b的條件下可以求得：其中f表示當前函數在所有給定權重a（x）上預測到的所有權重a×1。通過在一個可接受水平下求得目標函數g（x），本文則可以得到目標函數g（x）由n個給定權重a組成：其中ωj即為目標函數g（x）在n個給定權重a下預測期望值c與期望值之差。

然后，在遺傳模擬退火算法中，本文需要根據原始種群進行選擇與進化，以適應其無變異能力。在前一個步驟中，本文已經建立了一種初始種群，它是根據隨機選擇的遺傳編碼來建立的。在該階段的初始種群選擇過程中，本文需要考慮三個因素的影響：種群基因選擇水平、子種群適應能力、隨機選擇進化。其中，種群基因選擇水平是指從種群初始遺傳因子A的角度來看，該種群可以作為一個隨機個體被選擇和進化。此時，如果有新遺傳因子A作為初始因子，則可以使得種群遺傳能力提高到1。在個體適應能力、隨機選擇進化后將產生1～3個個體組成新種群。為了獲得更好的進化效果，本文需要選擇更多個體組成新種群。同時，當群體基因適應能力出現問題時（例如：低進化和高進化），子種群不會進化得更好，即子種群無法適應該群體中有新基因出現或者其進化得太快而不適應種群自身進化效率低時，將停止進化。因此，為了保持無變異能力并保持種群遺傳能力不變，將會對一個群體中的所有個體進行選擇和進化，從而獲得更好的進化效果。

通過對模擬退火算法的優化，本文提出了以下幾點：①在求解初始解時，使用遺傳演算法中對染色體進行了編碼，生成了初始群體，從而提高了模擬退火的平行查找性能；②在生成新的解決方案時，采用選擇、交叉和變異等方法來生成新的方案，取代了模擬退火算法中的任意生成新的方案，通過對其進行優化，從而能快速地求出最好的結果。該方法無須經過大量的試驗，就能得到更好的求解，從而減少了求解速度q的問題。該方法的流程表如圖1所示。

圖1 遺傳模擬退火算法流程示意圖

3 遺傳模擬退火算法流程分析

3.1 初始解構造設計

該方法包括構造初始解、生成新解、求解方法優化以及算法周期等。該方法首先從均衡速率大的問題（即初值）出發，尋求最優化問題，并為其設計出一種合適的初值結構。為了提高模擬退火方法的平行查找性能，本文提出了一種新的基于遺傳算法的原始群體生成方法，將初始解的結構劃分為編碼、初始種群、合法解決和有效解決四個階段。通過實例Jaeschks9，對初解的構建過程進行了詳細的闡述。

特別在編碼與生成初期人口的過程中，本文將問題進行了代碼化，并將其轉化為可由電腦辨識的資料，此問題則是流水作業的均衡問題，而代碼是將作業交給了一個工作站，并將其轉換為電腦所能辨識的資料，該資料被稱作“染色體”。每一條鏈上的每一個點都代表著一個基因的價值，也就是一個序列。由若干個具有特定染色體的群體構成的群體，其染色體數就是群體的大小。在迭代過程中，最初的群體是首先生成的群體。在求解過程中，合理的解決方案是一個符合該模式的限制。在編寫代碼時，將任務放在了一個工作站上，不需要考慮到任務與任務的優先級，因此需要設計一個合適的優化方案來保證代碼的優先級。在進行優化求解時，必須先決定每個問題的分布前后，然后再根據優先權來決定任務的分布。在此基礎上，根據實例的任務優先級，分別求出各任務優先級，當各任務i的優先級大于各優先級的中位時，由前向后依次進行排序；在任務i的權重小于其優先權的中間位時，將i按從前到后依次進行排序。最優的輸出解集就是從符合任務優先關系的原始群體的合理解中，選擇最大的一個作為初始方案。

3.2 新解產生

在模擬退火中，由于新的求解是以一種隨機生成的形式生成的，在此基礎上，利用遺傳算法中的“優勝劣汰”的概念，對新的求解方法進行選擇運算、交叉運算和突變運算，生成新的解集后進行修正，使得該方案符合數學模式的限制，最終得到一個合法的新的解決方案。選取運算采用冠軍方法，選取具有更大的目標值的個體構成新群體；雙點是通過兩個染色體的2個片段進行交換而形成新的染色體；突變是從舊有序列中隨機抽取相應的序列，生成新的染色體。通過舉例，Jaeschks9對新解的生成過程進行了詳細的闡述。

根據“優勝劣汰”的原則，先從原始群體中挑選出具有較高適應性的優質基因，并將其遺傳給后代。自然選擇運算與自然界的自然選擇相一致，即群體中的適應性較強的個體，其繁殖后代的概率也較高：在計算中，遺傳因子的適配度愈高，則被選取進行遺傳和突變。常見的選擇運算有：隨機遍歷取樣法、冠軍選擇法等。針對此問題，本文提出了一種適用于求解對象的遺傳模擬退火優化方法，適用范圍為：目標函數的數值愈大，則其自適應能力愈強，且在選取運算時，被選取概率越高?！敖徊孢\算”是從群體中任意選取兩條染色體，以一定的方法進行交換，從而構成兩條新的染色體。常見的交叉運算有單點交叉、雙點交叉、多點交叉、均勻交叉和計算交叉。雙點交叉是在兩條染色體上任意選取兩個相交的節點，再進行局部的基因互換，從而生成兩條新的染色體。進行雙點交的染色體數目是chromsize xpc, pc是一個交叉的可能性，因為只有在2個染色體上，一條染色體不能同時進行兩個點的交叉。因此，選擇兩個點的數目都是2，也就是說，在設定參數時，要確保chromsize xpc能被2整除，這樣就能把chromsize xpc條對成對。在篩選處理之后，從新一代群體Chromsize xpc條中，將chromsize xpc條染色體進行成對并二次雜交。在兩個點間進行交叉運算的 chromsize xpc條染色體與沒有進行雙點間的chromsizex（1 pc）條染色體構成了群體Chrom2。在進行兩個點的交匯時，必須先找出兩個點的相交，這個相交的地方就是一個染色體上的遺傳互換，兩個點相交的地方是一個任意位置?；驍的恐傅氖窃趦蓚€點交處進行的基因數目，在兩個節點處進行的數據互換，當兩條染色體進行雙重點交再進行時，其所產生的交集和交換的基因數目基本相同。在決定兩個點間的交匯部位和所需的基因數目之后，將在第二個交叉處的基因序列編號為相交的2個基因序列+1個轉換者。判定第二個相交部位的基因序列比染色體長大；如果在第二個交叉處的基因編號小于該染色體的話，可以進行常規的兩個交叉處理；如果在第二個相交部位的基因序列比染色體長大，那么在相交2的另一個片段是[2,I]。在進行二次交叉時，第一個染色體的第一個交叉點1和第二個的交叉點2互換了位置，突變運算是指從群體中隨意選取一條或幾條染色體，通過修改選定的染色體來獲得更好的染色體。變異運算的目的在于保持群體的多樣化，從而避免了演算法的局部最優化。常見的變異運算包括：基礎位變異、均勻變異、邊界變異、非均勻變異以及高斯近似變異?；A位突變是根據特定的變異概率，隨機選取一條或多條特定的基因進行突變計算。

3.3 算法循環

該方法包括兩種主要的演算法：一是在T的溫度下求最佳的求解，當達到目前的溫度T時，該周期就會終止；二是用基因仿真方法來實現冷卻，從最開始的溫度開始冷卻，直到達到最終的冷卻，從而完成整個計算。本文將對這兩個周期的流程進行詳細的闡述。

（1）在T的情況下的演算法周期

在T的條件下，采用馬爾可夫鏈長度L和周期u對遺傳模擬退火方法進行優化。若周期數u比馬爾可夫鏈長度L（u＜L）少，則該方法可在T的最大值下求出最好的結果；在此條件下，若周期u的周期比馬爾可夫L更大，則在目前的環境下完成該周期。

（2）冷卻工藝

該方法采用了一種基于基因的仿真方法，從起始點開始逐步冷卻，直至到達最終的冷卻溫度。該方法在T時間完成了一個算法周期之后，從目前的氣溫T跳過，再采用T=T-q的冷卻方程進行冷卻，冷卻之后，在新的溫度T下，再進行求解；在新的溫度T完成了解決方案的查找之后，冷卻過程持續進行，直至達到溫度T＜終點溫度T，并且在溫度T＜終點溫度T時，將各自的結果進行比較，并將其結果作為最大值而輸出。

4 結論

綜上，首先本文分析了在遺傳模擬退火算法中，不同類型的基因分別受到不同條件約束的問題。如果這些影響是通過自然種群中的子種群來達到，那么它就一定能夠很好地適應遺傳算法中給定的基因序列所要求的環境。如果它們是人工種群，那么本文就可以通過構建新的子種群來解決它們在這些生物條件約束下無法適應突變導致的種群變化問題。如果對所有這些目標都進行優化，本文將得到滿足這些要求的結果，如果有一些目標還不滿足，本文還可以通過人工構建新個體實現目標，從而實現對目標的進一步優化以滿足更大范圍內的優化需求。因此這種方法能夠更好地模擬自然界環境下生物的生存條件。并且這種方法沒有發生變化也不需要考慮遺傳信息。另一方面，這種方法最大可能地模擬出環境中多種基因相互作用、相互影響才能達到的最優效果，有可能通過生物條件約束來解決問題。