[發明專利]基于云控制器的自適應多核并行模擬退火遺傳方法

無效

• 申請號: 201010139215.3
• 申請日: 2010-03-31
• 公開（公告）號: CN101826167A
• 公開（公告）日: 2010-09-08
• 發明（設計）人: 李妮;董麗麗;龔光紅
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 周長琪

1.基于云控制器的自適應多核并行模擬退火遺傳方法，其特征在于，該方法包括如下步驟：

步驟一：初始化參數；

初始化參數包括兩部分：使用線程構造模塊TBB時環境變量的設置以及自適應并行模擬 退火遺傳方法APSAGABA本身的參數初始化；

TBB并行數據處理平臺的安裝與環境設置，在計算機里置入TBB的文件包，并添加TBB 的包含文件、庫文件和可執行文件；

設置問題規模，包括種群的數目、每個種群中個體的數目、每個個體中變量的數目、每 個變量的編碼長度、最大遺傳代數、溫度收斂系數、最低溫度和目標函數；

步驟二：初始化每個種群中的個體；

初始化每個個體，就是將個體中的每個變量賦值；利用TBB的并行模板規范類 parallel_for構造并行模塊；

在所有個體中找到適應度最大值和適應度最小值，并獲得初始溫度T0：

T0=min-maxlog0.95]]>

其中min為適應度最小值，max為適應度最大值；

步驟三：每個種群獨立選擇遺傳個體；

采用確定法選擇遺傳個體，確定法的具體操作過程是：

步驟3.1：獲取種群中各個個體在下一代中的期望生存數目N，N的獲取方式如下：

N=[f(x)Σf(x)×M]]]>

其中f(x)為個體的適應值，∑f(x)為種群中所有個體的適應值之和，M為種群中個體 的數目，[..]表示取符號內實數的整數部分；

步驟3.2：將N作為對應個體在下一代種群中的生存數目；

步驟3.3：將N取整前的小數部分進行從大到小的降序排序，順序取前M個作為加入到 下一代種群中的個體，其中M+N為每個種群中個體的數目；至此確定出下一代種群中的個 體；

其中所述的每個種群選擇遺傳個體的過程是相互獨立的，采用TBB的并行模板規范類 parallel_for構造并行模塊；

步驟四：獲取當前最優個體；

當迭代次數為1時，在種群的所有個體中選擇適應度最高個體作為最優個體；當迭代次 數大于1時，將當前種群中適應度最大的個體與最優個體比較，取二者適應度較大者作為當 前迭代次數下的最優個體；

其中所述的比較是利用TBB的并行模板規范類parallel_reduce構造并行模塊；

步驟五：最優個體替換每個種群中的最差個體；

用最優個體替換每個種群中的最差個體，替換的過程是相互獨立，采用TBB的并行模板 規范類parallel_for構造并行模塊；

步驟六：每個種群中的個體進行交叉；

交叉方式選擇兩點交叉，具體的操作過程為：

步驟6.1：在相互配對的兩個個體編碼串中隨機設置兩個交叉點；

步驟6.2：交換兩個個體在所設定的兩個交叉點之間的部分染色體；

交叉概率是由云控制器確定的；

步驟七：Mertropolis準則接受交叉后新的個體；

經過交叉后得到新的個體，利用Metropolis準則判斷新的個體是否能代替舊的個體；如 果符合Metropolis準則要求，則用新的個體代替舊的個體，否則保持舊個體不變；

步驟八：每個種群中的個體進行變異；

變異方式選擇基本位變異，其具體操作過程如下：

步驟8.1：對個體的每一個基因位，依照變異概率指定其為變異點；如果隨機生成的0 到1之間的數小于變異概率，則該位為變異點，否則不是；

步驟8.2：對每一個指定的變異點，對其基因值做取反運算；若是0，則為1；若是1， 則為0；

變異概率是由云控制器確定的；

步驟九：Mertropolis準則接受變異后新的個體；

經過變異后得到新的個體，利用Metropolis準則判斷新的個體是否能代替舊的個體；如 果符合Metropolis準則要求，則用新的個體代替舊的個體，否則保持舊個體不變；

步驟十：降溫操作；

利用公式T'＝T×α獲取新的溫度值T'，其中α為溫度收斂系數，T為當前溫度，T′為新 的溫度；

步驟十一：判斷是否滿足終止條件；

終止條件有如下三條，只要滿足其中的一條，則轉向步驟十二，否則轉向步驟三；

（1）達到最大遺傳代數；

（2）當前溫度小于最低溫度；

（3）最優個體50代保持不變；

步驟十二：結束；

最終尋到問題的最優解。