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

無效

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

技術領域

本發明屬于計算機仿真與智能優化領域，具體涉及一種基于云控制器的自適應多核并行 模擬退火遺傳方法。

背景技術

智能優化方法是一個近年來發展起來的非常活躍的研究領域。系統工程、自動化、計算 機、管理工程、機械等許多領域都在廣泛的采用智能優化方法。比如，遺傳方法、蟻群方法、 禁忌搜索方法、模擬退火方法等在國民經濟的各個行業中都獲得了廣泛的應用。

遺傳方法(Genetic?Algorithm，簡稱GA)起源于對生物系統所進行的計算機模擬研究。 美國Michigan大學的Holland教授于1975年提出了一種基于生物遺傳和進化機制的適應 于復雜系統優化的自適應概率優化技術-遺傳方法。它將問題的可行解編碼為由基因組成的 個體，模擬生物界“優勝劣汰、適者生存”的機制，通過種群的選擇、交叉和變異等操作， 不斷迭代，最終收斂到高適應度值的個體，從而求得問題的最優解或滿意解。然而遺傳方法 作為一種優化方法，它存在自身的局限性，其中最主要的是它容易產生“早熟”現象、局部 尋優能力較差等。傳統遺傳方法的交叉概率和變異概率是固定不變的，對不同的優化問題， 需要反復實驗來確定它們，過程非常繁瑣且很難找到每個問題的最佳值。

模擬退火方法是一種隨機尋優方法，其出發點是基于物理中固體物質的退火過程與一般 組合優化問題之間的相似性。該方法在某一初溫下，伴隨溫度的不斷下降，結合概率突跳特 性在解空間中隨機尋找目標函數的全局最優解。模擬退火基于Metropolis準則進行隨機搜 索，最終達到一種平衡狀態。其中Metropolis準則是指用概率來接受新狀態，經過大量的概 率接受過程，系統將趨于能量最低的平衡狀態。該方法具有跳出局部最優的能力，將其與遺 傳方法結合可以發揮各自的優勢，提高方法的搜索能力。

傳統的智能優化方法由于其固有的密集計算特性，存在的主要問題是運行時間長和計算 內存大，這是大型數據庫求解的主要瓶頸。隨著問題規模不斷擴大，基于單核串行智能優化 方法所消耗的時間迅速增長，往往不能滿足人們的實時處理數據要求，智能優化方法的并行 實現技術能大幅度地提高其性能，能從本質上減少處理數據的時間。

隨著計算機技術向著多處理器及多核架構的發展，使單機上的多核并行處理數據成為可能， 以剛剛推出的線程構造模塊(Threading?Building?Blocks，簡稱為TBB)開發庫為代表的 多核處理器并行處理平臺引起工程人員的重視。TBB與其他并行編程模型相比，編程難度較 低、自動調度效率高，有豐富的函數庫，還有良好的擴展功能，可以和消息傳遞接口(Message Passing?Interface，簡稱MPI)、OpenMP等結合，是一種簡單高效的并行技術。但是目前 TBB技術和智能優化領域的結合仍然很少，TBB并行處理平臺和模擬退火遺傳方法的結合 更是空白。

發明內容

本發明的目的是改進傳統遺傳方法的不足，將其與模擬退火方法結合，利用現有的并行 技術，實現混合方法的并行處理，使其能在實際的生產和科研領域中快速有效地執行，提高 運行效率，更快更好地解決組合優化和函數優化等優化問題。

在本發明中，提出了一種基于云控制器的自適應并行模擬退火遺傳方法(Adaptive?& Parallel?Simulated?Annealing?Genetic?Algorithm?based?on?Cloud?Controller，簡稱 APSAGABC)。該方法的改進主要包含以下幾點：

第一點，遺傳方法的編碼機制改進。

傳統的遺傳方法是采用二進制編碼，這不便于反映所求問題的結構特征，對于一些連續 函數的優化問題等，也由于遺傳方法的隨機特性而使得其局部搜索能力較差。采用格雷碼便 于提高遺傳方法的局部搜索能力，同時交叉、變異等遺傳操作易于實現。

第二點，遺傳算子的云控制自適應調節。