一種求解最大滿足性問題的極值優化方法
2023-10-08 18:17:04 1
專利名稱：一種求解最大滿足性問題的極值優化方法
技術領域：
本發明涉及組合優化領域和其它組合優化方法等研究領域，特別地，涉及一種用於求解最大滿足性問題的基於Bose-Einstein分布初始解和拓展演化概率分布的極值優化方法(Extremal Optimiz ation for Maximum Satisfiability Problems, EOSAT)。
背景技術：
可滿足性問題(Satisfiability Problem，簡稱SAT問題)是第一個被證明為 NP-完全(NP-Complete)的問題，不僅是理論計算機科學的核心問題之一，而且在人工智慧、電路設計自動化、工程優化、生物信息學等諸多領域中都有著重要的理論意義和應用價值。正如GOmes&Selman(2002)指出的那樣，蛋白質摺疊、工程計劃調度、大規模集成電路晶片檢測等在內的諸多領域的理論問題和實際應用都可以轉化為SAT問題及其對應的優化命題一最大滿足性問題(Maximum Satisfiability Problems，簡稱 MAX-SAT 問題)。如何設計有效求解較難SAT和MAX-SAT問題的優化算法越來越受到理論研究和工程應用領域的高度重視和廣泛研究。Gomes et al. (2008)對SAT和MAX-SAT問題的求解算法進行了綜述，這些算法大致可以兩類，即完全算法(complete algorithm)和不完全算法(incomplete algorithm)。完全算法的優勢是能夠在理論上確定問題實例是否有解，其中DPLL算法及其改進算法為最為經典的完全算法。但是，對於規模較大的問題， 完全算法的求解就會變得極其困難。不完全算法的優點是可以求解大規模的問題實例， 因此近年來對不完全算法的研究越來越受到重視。典型的不完全算法包括模擬退火算法 (Hansen&Jaumard, 1990)、GSAT 算法(Selman&Kautz, 1993)、WalkSAT 算法(Selman et al.，1994)、禁忌搜索(Glover, 1989)等算法。Mena'i&Batouche 將基於 Bose-Einstein 分布的初始解嵌入到τ -EO算法中，於2006年提出了一種被稱為Bose-Einstein-EO (BE-EO) 的算法用於求解MAX-SAT問題。對大量MAX-SAT問題實例的實驗結果表明相比模擬退火算法、GSAT算法、WALKSAT算法、τ -EO算法、禁忌搜索等算法，BE-EO算法具有更好的優化性能。然而，極值優化算法所採用的冪律分布極有可能不是最佳的演化概率分布，這勢必導致BE-EO算法的優化過程缺乏指導性，並最終導致該算法在求解MAX-SAT問題時無法獲得最佳的優化性能。
發明內容
本發明的目的旨在針對現有技術的不足，提供一種基於Bose-Einstein分布初始解和拓展演化概率分布的極值優化方法。本發明的目標是通過以下技術方案來實現的一種求解最大滿足性問題的極值優化方法，該方法為依據可分解和線性原則定義符合極值優化方法要求的局部適應度和全局適應度函數；利用Bose-Einstein分布構建優化的初始解；在選擇較差局部變量進行變異時，採用指數分布或混合分布等多種概率分布作為拓展演化概率分布；依據待求解優化問題的規模和特徵，設置算法終止條件(即最大採樣次數和每次採樣的最大運行步數)。
進一步地，該方法具體包括以下步驟
1、採用BE生成器(如圖2所示)隨機產生初始解&，並初始化設置全局最好解5·β=S0, 最好全局適值^( )=以&)，其中全局適值^(5·。)可按照下式計算
C(S0)表示在解S0下，含有變量A e Cj的不滿足子句Cj (即Cj {S,) =0)對應權重JVj的總和，其中表示待求解最大滿足性問題中布爾變量的數量， 表示待求解問題中子句的數量；
2、採用BE生成器(如圖2所示)隨機產生初始解義並初始化設置最好解&est=S,最好適值 CCStest)= C(S)；
(1)計算各個變量A局部適值2 」即
權利要求
1.一種求解最大滿足性問題的極值優化方法，其特徵在於，該方法為依據可分解和線性原則定義符合極值優化方法要求的局部適應度和全局適應度函數；利用 Bose-Einstein分布構建優化的初始解；在選擇較差局部變量進行變異時，採用指數分布或混合分布等多種概率分布作為拓展演化概率分布；依據待求解優化問題的規模和特徵， 設置算法終止條件(即最大採樣次數和每次採樣的最大運行步數)。
2.根據權利要求1所述的求解最大滿足性問題的極值優化方法，其特徵在於，該方法包括以下步驟(1)採用BE生成器(如上圖所示)隨機產生初始解&，並初始化設置全局最好解Sb= &，最好全局適值C(Sb)=以&)，其中全局適值^(5；)可按照下式計算
全文摘要
本發明公開了一種求解最大滿足性問題的極值優化方法，該方法依據可分解和線性原則定義符合極值優化方法要求的局部適應度和全局適應度函數；利用Bose-Einstein概率分布構建優化的初始解；在選擇較差局部變量進行變異時，採用指數分布或混合分布等多種概率分布作為拓展演化概率分布。與傳統的優化方法相比，此方法的優化過程更具有引導性，更容易獲得近優解甚至全局最優解，其原理簡潔清晰，調節參數較少，設計簡單，易於實施。
文檔編號G06F19/00GK102289580SQ20111022181
公開日2011年12月21日 申請日期2011年8月4日 優先權日2011年8月4日
發明者張正江, 曾國強, 鄭崇偉 申請人:溫州大學