郭 建，秦玉龍，王麗華，楊慶湘

(上海核工程研究設計院有限公司，上海200233)

廣義的堆芯裝載方案優(yōu)化問題是多變量、多目標、多約束的復雜問題，直接使用數(shù)學優(yōu)化中的方法求解，難度很大。在實際換料設計中，最常見的堆芯裝載方案優(yōu)化問題是一個單循環(huán)且固定燃料富集度、可燃毒物配置及換料燃料組件數(shù)目的多目標組合優(yōu)化問題，即單循環(huán)堆芯裝載方案優(yōu)化問題。多數(shù)堆芯裝載方案優(yōu)化研究主要關注單循環(huán)、單目標堆芯裝載方案優(yōu)化問題。遺傳算法作為一種通用的優(yōu)化策略已廣泛應用于多個工程優(yōu)化領域[1]，正逐漸成為解決堆芯裝載方案優(yōu)化問題的重要工具。如Tanker等應用遺傳算法研究堆芯裝載方案優(yōu)化問題，取得了一定的優(yōu)化效果[2]；咸春宇等研究了遺傳算法在堆芯裝載方案優(yōu)化問題中的編解碼方法[3]；王濤等通過將遺傳算法與其他算法混合使用，改善了優(yōu)化效果[4]。雖然這些研究將遺傳算法用于堆芯裝載方案優(yōu)化問題，實現(xiàn)了編碼、譯碼和遺傳操作，但研究中大多使用通用的遺傳算子，且對相關遺傳算子的優(yōu)化結果未進行對比分析。本文從組合優(yōu)化問題的角度出發(fā)，首次對堆芯裝載方案優(yōu)化中各種組合優(yōu)化算子的優(yōu)化效果進行了對比分析，設計了一種適用于整數(shù)編碼的交叉算子和變異算子，并使用分段整數(shù)編碼，確保編碼具有完備性、合法性和拉馬克性質。

1 遺傳算法

遺傳算法是一種強有力且應用廣泛的隨機搜索和優(yōu)化方法，是當前影響力最大的進化算法之一。20世紀60年代，Holland首先提出遺傳算法[5]。該方法模擬了生物在自然界的演化過程，原理源于達爾文的“自然選擇”法則，即在演化過程中，那些存活的個體既不是最強大的個體，也不是最聰明的個體，而是最能適應變化的個體。遺傳算法作為一種通用的隨機搜索策略，不需要提供變量之間的關系式，非常適于解決堆芯裝載方案優(yōu)化這種多變量耦合且解空間非常大的優(yōu)化問題。

1.1 帶精英策略的遺傳算法

本文使用一種包含精英策略的遺傳算法。Rudolph等使用齊次有限馬爾科夫鏈方法，證明了經(jīng)典遺傳算法無論如何選擇初始種群、交叉算子和目標函數(shù)，均無法保證算法收斂于全局最優(yōu)解[6]；但精英策略通過保留種群中的最優(yōu)個體，可使遺傳算法收斂于全局最優(yōu)解。在單目標遺傳算法中，精英策略一般指在種群中保留目前搜索到的已知最優(yōu)解[7]，無論精英策略的執(zhí)行是在選擇前還是在選擇后，均可使遺傳算法具備全局收斂特性。

1.2 編碼和新解的產(chǎn)生方式

在實際的單循環(huán)換料設計中，新燃料組件的富集度、位置和可燃毒物的裝載方式通常已基本確定，只需對“舊料”進行重新排列。大型先進壓水堆的堆芯一般采用低泄漏換料方案[8]，可以直接將外圍燃料組件布置為“舊料”中反應性最低的燃料組件，降低需要排列的燃料組件數(shù)量。實際的單循環(huán)堆芯裝載方案設計中，“舊料”的布置可以近似為一個組合優(yōu)化問題。此外，燃料組件內(nèi)部有一定的燃耗梯度傾斜，通過旋轉燃料組件，改變其與堆芯中心位置的相對朝向，可以小幅度地展平功率分布，延長循環(huán)長度。

本文使用整數(shù)編碼的方式處理燃料組件的排列組合和旋轉。整數(shù)編碼也稱為字符編碼，是離散優(yōu)化問題最適合的編碼方式，可以保證編碼所表示的解具有合法性、完備性和拉馬克性質[9]。合法性是指編碼中基因的所有可能排列均對應著一個可行解，不存在編碼無法解析為可行解的情況。整數(shù)編碼與組合優(yōu)化算子同時使用才能保證遺傳操作中解的合法性。完備性是指任意解均對應著一組編碼，可以保證解空間中的任意解在遺傳搜索過程中都是可搜索到的。拉馬克性質是指染色體編碼中某個基因的等位基因含義不依賴其他基因。編碼具有拉馬克性質可以保證遺傳操作的有效性。使用實數(shù)編碼處理組合優(yōu)化問題時，一般需要對編碼進行修補，防止產(chǎn)生非法解。當使用基因的排列順序對編碼進行修補時，無法保證編碼具備拉馬克性質。

本文使用分段整數(shù)編碼表示帶燃料組件旋轉的堆芯裝載方案優(yōu)化算法中的一個可行方案。堆芯裝載方案設計需要滿足燃料組件1/4對稱布置要求，因此，只需要對1/4堆芯進行編碼。堆芯裝載區(qū)域的位置編號及燃料組件編號，如圖1所示。中心燃料組件可以參與優(yōu)化，但多數(shù)情況下，中心燃料組件可由經(jīng)驗直接指定。確定位置編碼和燃料組件編號后，可以獲得一個可行解編碼。圖2為分段染色體編碼。其中，編碼可分為2段，前半段(0～22)表示燃料組件位置，染色體位置的序號和堆芯裝載區(qū)域位置的序號相對應，染色體基因表示可用燃料組件的序號，在旅行商問題中這種表示方式稱為路徑表示；后半段表示燃料組件的旋轉角度，分別用0，1，2，3表示繞中心旋轉0°， 90°， 180°， 270°。分段編碼后，1條染色體既可確定燃料組件的位置，也可確定燃料組件的旋轉角度。

(a)Location id

(b)Fuel assembly id圖1堆芯裝載區(qū)域的位置編號及燃料組件編號Fig.1 Location id and fuel assembly id for optimization of core load pattern

圖2 分段染色體編碼Fig.2 Segmented coding of chromosome

分段編碼不僅能表示燃料組件的位置、旋轉角度等不同類型信息，保證解的完備性，而且能應用不同的遺傳算子。遺傳算法通過交叉、變異等操作產(chǎn)生新的可行解。燃料組件位置的編碼是一串整數(shù)的排列，進行交叉、變異等遺傳操作后，解的合法性不應被破壞。因此，本文為保證解的合法性，對于分段整數(shù)編碼中的不同片段使用不同的遺傳算子進行交叉、變異等操作，編碼的前半段是組合優(yōu)化問題，采用組合優(yōu)化中使用的算子，編碼的后半段使用遺傳算法中常用的遺傳算子。

1.3 并行算法

遺傳算法的計算速度較慢，計算量主要集中在對大量可行解的評價，通常要對數(shù)以萬計甚至十萬計的可行解進行評價后才能得到優(yōu)化解。但遺傳算法具有良好的并行特性，同代個體的適應值計算不存在相互依賴問題，且適應值計算為遺傳算法計算量的主要部分。本文基于MPI并行實現(xiàn)了并行遺傳算法，可以充分利用多個服務器的計算資源，大幅度提高算法的執(zhí)行效率。除適應值計算流程外，并行遺傳算法的計算流程與原來的遺傳算法計算流程一致。并行遺傳算法將種群按照進程數(shù)等分(種群數(shù)量無法被進程數(shù)整除時近似等分)，每個進程負責所分配的個體適應值計算，所有進程均完成計算后，匯總適應值計算結果，然后按照正常的步驟進行遺傳算法中的選擇、交叉和變異操作。帶精英策略的并行遺傳算法計算流程，如圖3所示。

(a)Calculation flow chart

(b)Parallel algorithm圖3帶精英策略的并行遺傳算法計算流程Fig.3 Flow chart of parallel genetic algorithm with elitism

2 組合優(yōu)化算子

單循環(huán)堆芯裝載方案優(yōu)化是一個近似的組合優(yōu)化問題。本文對堆芯裝載方案設計過程進行深入分析，參考實際的優(yōu)化過程，提出了一種基于隨機子路徑的交叉算子和一種基于隨機子路徑的變異算子應用于旅行商問題及單循環(huán)堆芯裝載方案優(yōu)化問題，并與其他多種組合優(yōu)化算子的優(yōu)化效果進行了對比分析。

2.1 隨機子路徑算子

在實際的單循環(huán)裝載方案設計中，通常將幾個位置的燃料組件調(diào)換次序以獲得更好的裝載方案。用隨機子路徑算子模擬該過程時，隨機子路徑算子會隨機選擇一些燃料組件，這些燃料組件的排列構成子路徑。然后，對這些燃料組件的次序進行某種操作產(chǎn)生新的可行解。本文在隨機子路徑算子中引入交換概率Pe，用于表示隨機選取子路徑過程中燃料組件被抽中的概率。

2.1.1隨機子路徑交叉算子

隨機子路徑交叉算子(discontinuous sub-tour exchange crossover, DSE)先按照交叉概率Pc選擇成對個體作為父代，再按照交換概率Pe隨機選取一些燃料組件，保持燃料組件在父代中的順序不變，交換對應位置的子路徑。隨機子路徑交叉算子，如圖4所示。其中，箭頭表示隨機選擇的燃料組件及其位置，父代1個體的隨機子路徑為(2, 5, 6, 9)，父代2個體的隨機子路徑為(5, 6, 9, 2)，在交叉過程中子路徑的順序不變。在選擇子路徑過程中，燃料組件是隨機選擇的，在對應的父代個體中，子路徑可能是連續(xù)的，也可能是不連續(xù)的。

圖4 隨機子路徑交叉算子Fig.4 Discontinuous sub-tour exchange crossover operator

2.1.2隨機子路徑變異算子

隨機子路徑變異算子(discontinuous scramble mutation, DSM)首先按照變異概率Pm選擇一個個體作為父代；其次，按照概率Pe選擇一些燃料組件生成子路徑；最后，將子路徑中的燃料組件打亂，并按照打亂后的順序放回原來的位置。隨機子路徑變異算子，如圖5所示。若隨機選擇的子路徑為(3, 5, 7, 8)，則打亂后子路徑可以是(5, 7, 8, 3)，將打亂后的子路徑放回子路徑原來的位置就得到一個新的可行解。本文的實際優(yōu)化計算過程中，隨機子路徑變異算子的交換概率Pe與變異概率Pm取相同值。

圖5 隨機子路徑變異算子Fig.5 Discontinuous scramble mutation operator

2.2 組合優(yōu)化算子

本文除提出了2種遺傳算子外，還研究了經(jīng)典組合優(yōu)化問題中旅行商問題常用的多種基于路徑表示的遺傳算子，包括11種交叉算子和6種變異算子。這些遺傳算子是專門針對組合優(yōu)化問題設計的，在遺傳操作中可保證不產(chǎn)生非法解。

2.2.1組合優(yōu)化交叉算子

組合優(yōu)化中常用的交叉算子，如表1所列。每個交叉算子的具體操作方式可參見相應的參考文獻。這些交叉算子中， PMX和EX采用交叉和修補的方式產(chǎn)生新解；PMX使用子串的映射修補非法解；EX是由經(jīng)典的2點交叉算子改進得到的，為了避免非法解的產(chǎn)生，使用基因的排列順序對解進行修補；其余的交叉算子均不會產(chǎn)生非法的中間解。OX，OBX，PBX，SE，PMX，MPX這6種交叉算子也是基于子路徑設計的，OX， SE， PMX， MPX這4種交叉算子按照2點交叉的方式選擇子路徑，OBX和PBX的子路徑是離散的。交叉算子PBX， OBX， EX均引入了交換概率Pe用于調(diào)整交換基因的數(shù)量。 MPX和PMX的原理相似，在交叉操作中破壞的邊界信息少，優(yōu)化效果可能更好。VR是一個p-sexual交叉算子，即參與交叉操作的父代個體數(shù)量為p，p通常取2或4。ER是基于邊界信息的交叉算子，比較適用于對稱旅行商問題。AP通過按照順序依次選擇父代個體中的基因產(chǎn)生新的個體，選擇過程中忽略已經(jīng)選擇過的基因。

表1 組合優(yōu)化中常用的交叉算子Tab.1Commonly used crossover operatorin combination optimization

2.2.2組合優(yōu)化變異算子

組合優(yōu)化中常用的變異算子，如表2所列。表2中每個變異算子的具體操作方式可參見相關的參考文獻。DM算子隨機選擇一個子路徑，然后將子路徑隨機插入到染色體中。ISM算子的原理與DM算子相同，只是ISM的子路徑僅包含一個基因。SIM和IVM隨機選擇一個連續(xù)子路徑，SIM在原來的位置反轉子路徑中的基因，IVM將反轉后的子路徑隨機插入到染色體中。SM選擇一個連續(xù)子路徑，將子路徑隨機打亂后放回原來的位置。EM算子和經(jīng)典的互換變異操作相同，即交換染色體隨機2個位置的基因。

表2 組合優(yōu)化中常用的變異算子Tab.2Commonly used mutation operatorin combination optimization

3 計算結果

3.1 中國旅行商問題的優(yōu)化結果

對中國旅行商問題(Chinese traveling salesman problem, CTSP)，應用不同算子組合的數(shù)值實驗，得到了相應的交叉概率、變異概率和交換概率的最佳選取方式，分析了不同算子的優(yōu)化效果。中國旅行商問題中共有31個城市[15]，表3列出了中國31個城市的坐標。從任意城市出發(fā)依次通過每一城市后返回出發(fā)城市的最短路徑，即為該問題的最優(yōu)解。中國旅行商問題的已知最短路徑長度為15 381[16]，路徑示意圖如圖6所示。

表3 中國旅行商問題中的城市坐標Tab.3City coordinates for Chinese traveling salesman problem

圖6 中國旅行商問題已知的最短路徑Fig.6 The shortest known path to Chinesetraveling salesman problem

為了得到算子最佳交叉概率、變異概率和交換概率，使用不同的參數(shù)取值進行數(shù)值實驗。數(shù)值實驗中各參數(shù)的取值，如表4所列。在數(shù)值實驗中，種群數(shù)統(tǒng)一取為500，演化代數(shù)統(tǒng)一取為200，使用競標賽選擇算子，統(tǒng)計得到各個交叉算子和變異算子組合在不同交叉概率、變異概率和交換概率下的最佳優(yōu)化結果，如表5所列。分析表5中同一交叉算子與不同變異算子組合的平均路徑長度可知，DSE，PBX， OBX的優(yōu)化效果在12種交叉算子中的優(yōu)化效果最好，這3種交叉算子與其他各種變異算子的組合均能獲得良好的優(yōu)化效果，且均獲得了比目前已知最優(yōu)解更短的路徑，最短路徑長度為15 378，路徑示意圖如圖7所示。

表4 數(shù)值實驗中交叉概率、變異概率和交換概率的取值Tab.4Probabilities for crossover, mutation and exchange in the numerical test

表5 中國旅行商問題數(shù)值實驗得到的路徑長度Tab.5Tour length for numerical test of Chinese traveling salesman problem

圖7 用本文算子得到的中國旅行商問題最短路徑Fig.7 The shortest path of Chinese traveling salesmanproblem based on the operator presented in this paper

本文提出的交叉算子DSE的平均值最低，優(yōu)化效果最好。ER，OX，SE，MPX的優(yōu)化效果次于DSE，PBX，OBX，優(yōu)化路徑平均長度均低于16 000，其余交叉算子的優(yōu)化效果更次。

變異算子的引入是為了擴大遺傳算法的搜索空間，避免陷入局部最優(yōu)，但由于變異過程是隨機的，引入變異算子后的可行解可能變好也可能變差。通過比較變異算子與不同交叉算子組合的優(yōu)化結果可以看出，變異算子在遺傳算法中的作用有限，當交叉算子的效果比較差時，變異算子并不能顯著改善優(yōu)化效果。綜合比較變異算子與不同交叉算子組合的優(yōu)化解平均值、最大值和最小值可以看出，SIM的效果最好，能明顯改善PM交叉算子的優(yōu)化效果。本文提出的變異算子DSM效果不突出，但在交叉算子優(yōu)化效果較好時，DSM不會使可行解變差。

在分析最短路徑長度的基礎上，統(tǒng)計了各個交叉算子與DSM，SIM，IVM 3個變異算子組合獲得最短路徑時的相應參數(shù)，結果如表6所列。由表6可見，優(yōu)化效果最好的3種交叉算子DSE，PBX，OBX對應的交換概率約為0.5，這表明交叉操作中2個父代個體交換一半的基因。對比變異概率為0.01和0.001時的結果可知，變異概率為0.01時的結果更好。統(tǒng)計得到路徑長度隨交叉概率的變化關系，如圖8所示。由圖8(a)可見，對于DSE，PBX，OBX，交叉概率變大時優(yōu)化效果變好，交叉概率在0.7～0.9時優(yōu)化結果較好。由圖8(b)可見，對于AP和VR，交叉概率小于0.5時優(yōu)化效果較好，交叉概率大于0.5時優(yōu)化效果顯著惡化；其他優(yōu)化算子的優(yōu)化效果隨交叉概率的變化不發(fā)生明顯改變。

表6 算子組合獲得最優(yōu)解時的參數(shù)取值Tab.6Parameters of operator combinations when obtain the best optimum solution

(a)Path length vs Pc for the combinations of 9 operators (b)Path length vs Pc for SIM with different crossover operators圖8中國旅行商問題路徑長度隨交叉概率的變化Fig.8 Path length vs. crossover probability for Chinese traveling salesman problem

3.2 單循環(huán)堆芯裝載方案優(yōu)化問題

將本文提出的交叉算子DSE和變異算子DSM應用于單循環(huán)堆芯裝載方案優(yōu)化問題。為對比交叉算子的優(yōu)化效果，根據(jù)中國旅行商問題的測試結果，在單循環(huán)堆芯裝載方案優(yōu)化問題中測試了不同交叉算子與SIM組合的優(yōu)化效果。為測試變異算子DSM，對比了DSM與中國旅行商問題中優(yōu)化效果較好的SIM和IVM變異算子。測試的算子組合只對編碼的位置部分進行操作，編碼的旋轉部分使用同樣的交叉和變異算子。旋轉部分的交叉算子為均勻交叉算子[17]，即在2個父代個體中隨機選擇一些基因位置并交換2個位置的基因。旋轉部分的變異算子可從染色體中隨機選擇一個基因位置并改變該位置的基因。為方便比較，除AP和VR外，交叉算子的交叉概率統(tǒng)一取0.9，AP和VR的交叉概率均取0.3，交換概率統(tǒng)一取0.5，變異算子的變異概率取0.01，每代種群數(shù)為156，總演化代數(shù)為300，使用競標賽算子。用實際工程中使用的核設計程序對可行解進行評價，為快速獲得測試結果，以壽期初的硼質量分數(shù)為優(yōu)化目標，硼質量分數(shù)越大，則可行解越好。在實際優(yōu)化計算中也可根據(jù)需求選擇其他的優(yōu)化目標。本文測試的堆芯裝載區(qū)域與圖1類似，新燃料組件的位置固定不變，最外側燃料組件為反應性最低的燃料組件，共包含13個燃料組件(1/4堆芯)的排列和旋轉。

單目標堆芯裝載方案優(yōu)化問題中9種算子組合優(yōu)化得到的初始臨界硼質量分數(shù)，如表7所列。由表7可見，由于這9種算子組合是通過對中國旅行商問題測試得到的效果較好的算子組合，所以DSE，OBX，PBX 3種交叉算子的優(yōu)化結果非常接近，優(yōu)化后的臨界硼質量分數(shù)均明顯大于初始方案的臨界硼質量分數(shù)1 764.4×10-6，3種交叉算子相互之間并沒有明顯的優(yōu)勢。變異算子中IVM和SIM的優(yōu)化效果相當，略優(yōu)于本文提出的變異算子DSM。

不同交叉算子和SIM變異算子組合優(yōu)化得到的初始臨界硼質量分數(shù)，如表8所列。

表7 單目標堆芯裝載方案優(yōu)化問題中9種算子組合優(yōu)化得到的初始臨界硼質量分數(shù)Tab.7Initial critical boron mass fraction for combinations of 9 operators of single-object core load pattern optimization problem

表8 單目標堆芯裝載方案優(yōu)化問題中不同交叉算子和SIM變異算子組合優(yōu)化得到的初始臨界硼質量分數(shù)Tab.8Initial critical boron mass fraction for SIM with different crossover operators of single-object core fuel load pattern optimization problem

由表8可見，在中國旅行商問題中優(yōu)化效果好的交叉算子，如DSE，PBX，OBX，在單目標堆芯裝載方案優(yōu)化問題中的優(yōu)化效果也較好，但在中國旅行商問題中最優(yōu)的交叉算子(DSE，PBX，OBX)和次優(yōu)的交叉算子(ER，OX，SE，MPX)之間優(yōu)化效果的差異在堆芯裝載方案優(yōu)化問題中變小。在中國旅行商問題中優(yōu)化效果較差的交叉算子，在堆芯裝載方案優(yōu)化問題中優(yōu)化效果也較差。還有部分算子在這2個問題中的優(yōu)化效果不一致，如ER和MPX在堆芯裝載方案優(yōu)化問題中的優(yōu)化效果與在中國旅行商問題中的優(yōu)化效果相比變差，CX算法的優(yōu)化效果變好。

單目標堆芯裝載方案優(yōu)化問題中不同算子組合的收斂曲線，如圖9所示。

(a)Convergence curve for combinations of 9 operators

(b)Convergence curve for SIM with different crossover operators圖9單目標堆芯裝載方案優(yōu)化問題中不同算子組合的收斂曲線Fig.9 Convergence curve for different operator combinationsof single-object core load pattern optimization problem

由圖9可見，除了AP交叉算子外，其他算子組合在100代附近均已收斂。由于使用了帶精英策略的遺傳算法，最優(yōu)個體在種群中得到保留，所以收斂曲線是單調(diào)的。

4 結論

本文研究了單目標堆芯裝載方案優(yōu)化問題的遺傳算子，提出了一種新的隨機子路徑交叉算子DSE和一種隨機子路徑變異算子DSM。測試結果表明，交叉算子DSE在單目標堆芯裝載方案優(yōu)化問題中的優(yōu)化效果與PBX和OBX相當，DSE在旅行商問題中的優(yōu)化效果優(yōu)于其他算子。變異算子DSM在單目標堆芯裝載方案優(yōu)化問題中的優(yōu)化效果與IVM和SIM算子相比略差。本文提出的基于分段整數(shù)編碼進行遺傳操作的新解產(chǎn)生策略，可以描述燃料組件的位置和旋轉信息，避免了非法解的產(chǎn)生，具有良好的擴展性和通用性。后續(xù)將基于本文設計的優(yōu)化算子開展多目標堆芯裝載方案優(yōu)化問題研究，給出多個優(yōu)化目標下的結果。