蕭秋蘭

（1 閩南科技學(xué)院計(jì)算機(jī)信息學(xué)院 福建 泉州 362332）

（2 大數(shù)據(jù)與人工智能福建省高校重點(diǎn)實(shí)驗(yàn)室 福建 泉州 362332）

0 引言

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

1 遺傳模擬退火算法理論基礎(chǔ)

1.1 模擬退火算法概述

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

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

1.2 遺傳算法概述

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

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

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

2 遺傳模擬退火算法設(shè)計(jì)

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

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

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

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

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

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

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

3.1 初始解構(gòu)造設(shè)計(jì)

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

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

3.2 新解產(chǎn)生

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

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

3.3 算法循環(huán)

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

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

在T的條件下，采用馬爾可夫鏈長(zhǎng)度L和周期u對(duì)遺傳模擬退火方法進(jìn)行優(yōu)化。若周期數(shù)u比馬爾可夫鏈長(zhǎng)度L（u＜L）少，則該方法可在T的最大值下求出最好的結(jié)果；在此條件下，若周期u的周期比馬爾可夫L更大，則在目前的環(huán)境下完成該周期。

（2）冷卻工藝

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

4 結(jié)論

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