[發明專利]并行進化計算中跨子群體使用全局和局部突變的方法系統

在審

• 申請號: 201310000680.2
• 申請日: 2013-01-04
• 公開（公告）號: CN103295062A
• 公開（公告）日: 2013-09-11
• 發明（設計）人: J·F·坎汀
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 北京市金杜律師事務所 11256
• 代理人: 酆迅

技術領域

本發明主題的實施例一般地涉及進化計算領域，并且更具體地涉及在進化計算中使用局部和全局突變。?

背景技術

軟件工具運用元啟發式(metaheuristic)優化算法以解決優化問題。元啟發式優化算法的示例包括進化算法(例如，遺傳算法、差分進化)、蟻群優化算法、模擬退火算法等。?

進化算法使用寬松地基于達爾文進化和生物機制的技術來發展對設計問題的解。實現進化算法的軟件工具開始于隨機生成的解群體并且迭代地使用性別重組、交叉、變異和達爾文自然選擇原理來在相繼的世代(generation)中創建新的更適合的解。進化算法已經有效用于許多研究和開發方面并且已經針對廣泛的問題生成能與人類競爭的解。在國際商業機器公司(IBM)內，(SNAP)已經成功應用于Power7/7+的I/O電路設計、掃描鏈路由、高性能計算(HPC)競價過程、用于z系列總線的信號完整性和編譯器標志調節。?

進化算法的執行實例可能過早收斂。候選解群體在少數適合的候選解的基因迅速支配該群體并且將該群體限制在局部最優時收斂。過早收斂意味著用于優化問題的候選解群體收斂地太早，因此提供次優結果。?

發明內容

本發明主題的實施例包括一種用于并行遺傳算法計算過程中的局部突變的方法。該方法跟蹤第一子群體跨其世代的向前進展?(forward?progress)。第一子群體是形成對優化問題的候選解群體的多個子群體之一。在第一子群體的當前世代，確定第一子群體的向前進展未滿足一個或者多個向前進展標準的集合。響應于確定第一子群體的向前進展在當前世代未滿足一個或者多個向前進展標準的集合，針對第一子群體的當前世代調用局部突變。在調用局部突變之后重新填充第一子群體。在重新填充之后重新建立第一子群體而限制向第一子群體的遷移。?

本發明主題的實施例還包括一種用于在并行進化算法計算過程中針對子群體調用局部突變的計算機程序產品。該計算機程序產品包括計算機可讀存儲介質，計算機可讀存儲介質具有與之一起實現的計算機可用程序代碼。計算機可用程序代碼包括配置成跟蹤候選解群體跨其世代的向前進展的計算機可用程序代碼。群體跨多個計算實體被劃分成多個子群體，多個計算實體在搜索對優化問題的解時迭代地創建多個候選解子群體的新世代。計算機可用程序代碼被配置成跟蹤多個計算實體在多個計算實體上調用的局部突變。在群體的當前世代，計算機可用程序代碼被配置成確定群體的向前進展未滿足一個或者多個向前進展標準的集合。響應于確定群體的向前進展在當前世代未滿足一個或者多個向前進展標準的集合，計算機可用程序代碼被配置成選擇影響全局突變的參數值。該選擇至少部分基于局部突變的向前進展。計算機可用程序代碼被配置成命令多個計算實體根據參數值共同地將全局突變應用于多個子群體。?

附圖說明

通過參照附圖可以更好地理解當前實施例并且對于本領域技術人員來說，許多目的、特征和優點變得顯而易見。?

圖1描繪了在單個子群體內的局部突變和跨較晚世代的群體的全局突變的示例概念圖。?

圖2描繪了用于在未滿足局部向前進展標準時調用局部突變的示例操作的流程圖。?

圖3描繪了用于在未滿足全局向前進展標準時調用全局突變的示例操作的流程圖。?

圖4-6描繪了用于在同類群的平均適合度和最佳適合度未達到局部向前進展標準時調用局部突變的示例操作的流程圖。圖5描繪了從圖4繼續的示例操作的流程圖。圖6描繪了從圖5繼續的示例操作的流程圖。?

圖7-9描繪了用于在群體的平均適合度和最佳適合度未進展時調用全局突變的示例操作的流程圖。圖7描繪了用于在群體的平均適合度和最佳適合度未進展時調用全局突變的示例操作的流程圖。圖8描繪了從圖7的塊721繼續的示例操作的流程圖。圖9描繪了從圖7繼續的示例操作的流程圖。?

圖10描繪了全局/局部突變單元的示例計算機系統。?

具體實施方式

以下描述包括實現本發明主題的技術的示例系統、方法、技術、指令序列和計算機程序產品。然而，應理解的是，在沒有這些具體細節的情況下仍然可以實現所描述的實施例。例如，雖然示例涉及機器，但是可以在虛擬化環境中實現本發明主題的實施例。例如，可以向單個機器所支持的不同虛擬機分配子群體。作為另一示例，可以向多核環境中的不同核分配子群體。在其它實例中，并未具體示出公知指令實例、協議、結構和技術從而避免使描述模糊不清。?

術語?