頂點(diǎn)覆蓋問題

組合優(yōu)化組合優(yōu)化問題優(yōu)化問題可以分為兩類：一類是連續(xù)變量的問題，另一類是離散變量的問題，后者稱為組合優(yōu)化問題。組合優(yōu)化問題的任務(wù)：從一個有限或可數(shù)無限集里，尋找一個使得目標(biāo)函數(shù)最優(yōu)的對象——典型地包括：一組賦值，一個集合，一個排列。組合優(yōu)化問題隨處可見，具有很強(qiáng)的工程代表性應(yīng)用。許多組合優(yōu)化問題都是NP難的：最大可滿足性（MaxSAT)問題，最大團(tuán)問題，最小頂點(diǎn)覆蓋問題，旅行商問題。。。組合優(yōu)化組合優(yōu)化問題優(yōu)化問題可以分為兩類：一類是連續(xù)變量的問題，另一類是離散變量的問題，后者稱為組合優(yōu)化問題。組合優(yōu)化問題的任務(wù)：從一個有限或可數(shù)無限集里，尋找一個使得目標(biāo)函數(shù)最優(yōu)的對象——典型地包括：一組賦值，一個集合，一個排列。組合優(yōu)化問題隨處可見，具有很強(qiáng)的工程代表性應(yīng)用。許多組合優(yōu)化問題都是NP難的：最大可滿足性（MaxSAT)問題，最大團(tuán)問題，最小頂點(diǎn)覆蓋問題，旅行商問題。。。求解NP難組合優(yōu)化問題分支限界：完備算法（保證解的最優(yōu)性），回溯搜索，遍歷解空間啟發(fā)式搜索（包括局部搜索，演化算法等）：不完備算法，迭代改進(jìn)，采樣解空間局部搜索簡單地說，局部搜索是：先產(chǎn)生一個（或一群）完整的候選解，然后進(jìn)行迭代改進(jìn)，每一步只修改解的某個局部（比如一個基本單元），直到得到一個令人滿意的解或者達(dá)到某個資源限制（一般是時間限制）。局部搜索簡單地說，局部搜索是：先產(chǎn)生一個（或一群）完整的候選解，然后進(jìn)行迭代改進(jìn)，每一步只修改解的某個局部（比如一個基本單元），直到得到一個令人滿意的解或者達(dá)到某個資源限制（一般是時間限制）。形式化一點(diǎn)說，局部搜索定義為：候選解集合（也稱搜索空間）S；目標(biāo)函數(shù)f：S->R(實(shí)數(shù)集)；初始候選解集合I；鄰域關(guān)系N:S->2^S，對于每個候選解s，N(s)={s′∈S|N(s,s′)}?S;（一般是基于候選解的海明距離，最常見的是1-海明距離鄰域）跳轉(zhuǎn)函數(shù)（Stepfunction）：定義了如何從當(dāng)前候選解跳轉(zhuǎn)到它的一個鄰居候選解局部搜索局部搜索的優(yōu)點(diǎn)：簡單；通用；容易實(shí)現(xiàn)；可擴(kuò)展性強(qiáng)；許多NP難問題在求解性能上最好的算法都是基于局部搜索什么時候使用局部搜索組合爆炸：對于NP難問題，解空間是問題規(guī)模的指數(shù)級別時間限制短，或者時間資源非常重要關(guān)于問題的領(lǐng)域知識太少接受近似解一個局部搜索的例子一個例子：最大可滿足性問題（MaxSAT）變元：x1,x2,x3,…,xn文字：變元或者其否定形式x1,~x1,…子句：文字的析取x1\/~x2,x1\/x2\/~x4,….CNF公式：子句的合取，可看為一個子句集合MaxSAT（優(yōu)化問題)：給出一組（布爾）賦值，滿足最多子句。SAT（判定問題）：是否存在一組（布爾）賦值，滿足所有子句。一個局部搜索的例子一個例子：最大可滿足性問題（MaxSAT）用局部搜索求解以下MaxSAT（或SAT）實(shí)例{x1\/~x2,x1\/x2,x2\/x3,~x1\/x2\/~x3}變元：x1,x2,x3,…,xn文字：變元或者其否定形式x1,~x1,…子句：文字的析取x1\/~x2,x1\/x2\/~x4,….CNF公式：子句的合取，可看為一個子句集合MaxSAT（優(yōu)化問題)：給出一組（布爾）賦值，滿足最多子句。SAT（判定問題）：是否存在一組（布爾）賦值，滿足所有子句。賦值不滿足的子句初始000x1\/x2,x2\/x3Step1001x1\/x2Step2101~x1\/x2\/~x3Step3110無（找到最優(yōu)解）局部搜索的循環(huán)問題局部搜索的循環(huán)問題重復(fù)訪問（近期剛訪問過的）候選解花費(fèi)很長時間在解空間的某個區(qū)域（比如某個局部最優(yōu)附近的區(qū)域）搜索導(dǎo)致：容易陷入局部最優(yōu)，花費(fèi)太多時間在做無效搜索。。。很多局部搜索的文獻(xiàn)其實(shí)都是圍繞如何解決這個問題循環(huán)問題不可能完全避免這是由局部搜索的無記憶性決定的不可能增加一個記憶機(jī)制來記住訪問過的候選解，空間時間要求都太龐大局部搜索的循環(huán)問題局部搜索的循環(huán)問題重復(fù)訪問（近期剛訪問過的）候選解花費(fèi)很長時間在解空間的某個區(qū)域（比如某個局部最優(yōu)附近的區(qū)域）搜索導(dǎo)致：容易陷入局部最優(yōu)，花費(fèi)太多時間在做無效搜索。。。很多局部搜索的文獻(xiàn)其實(shí)都是圍繞如何解決這個問題循環(huán)問題不可能完全避免這是由局部搜索的無記憶性決定的不可能增加一個記憶機(jī)制來記住訪問過的候選解，空間時間要求都太龐大已有的（通用）方法隨機(jī)游動重啟以一定條件（如概率）允許非改進(jìn)步Tabu策略：禁止反轉(zhuǎn)近期內(nèi)（t步內(nèi)）所做的改動加權(quán)方法改變能量地圖格局檢測相關(guān)概念：解的基本單元一般稱為解部件(solutioncomponent)：在最大團(tuán)問題中是一個點(diǎn)，在可滿足性問題中是一個變元。。。解部件的賦值：例如，點(diǎn){選中，沒選中},變元{true,false}格局檢測相關(guān)概念：解的基本單元一般稱為解部件(solutioncomponent)：在最大團(tuán)問題中是一個點(diǎn)，在可滿足性問題中是一個變元。。。解部件的賦值：例如，點(diǎn){選中，沒選中},變元{true,false}格局檢測（configurationchecking，簡稱CC）的直觀理解：無法記憶整個解，但可以記憶每個解部件的環(huán)境及其變化。通過檢測解部件的環(huán)境，減少解的局部結(jié)構(gòu)上的循環(huán)，以此減少整個搜索的循環(huán)問題。對于一個解部件x，如果從上次x改變賦值之后，x的環(huán)境沒有改變過，那么禁止x變回原來的賦值。格局檢測是一種從空間（或結(jié)構(gòu)）上考慮的禁忌策略格局檢測解部件的格局我們把解部件的環(huán)境信息稱為它的格局，可以有不同的定義最常見的是：一個解部件的格局，是一個由它的鄰居解部件的賦值構(gòu)成的向量。格局檢測解部件的格局我們把解部件的環(huán)境信息稱為它的格局，可以有不同的定義最常見的是：一個例子：CCforSAT鄰居變量：如果兩個變量出現(xiàn)在同一個子句中，稱他們是鄰居。變量x的格局：一個由x的所有鄰居變量的賦值構(gòu)成的向量。一個解部件的格局，是一個由它的鄰居解部件的賦值構(gòu)成的向量。格局檢測用于SAT問題CCforSAT：對于一個變量v，如果從上次v改變賦值之后，v的格局沒有改變過，那么禁止v變回原來的賦值。頂點(diǎn)覆蓋問題頂點(diǎn)覆蓋：對于一個無向圖，一個頂點(diǎn)覆蓋是一個頂點(diǎn)子集，使得每條邊都至少有一個點(diǎn)屬于該集合。最小頂點(diǎn)覆蓋問題：給定一個無向圖，找出最小的頂點(diǎn)覆蓋。格局檢測用于頂點(diǎn)覆蓋問題最小頂點(diǎn)覆蓋問題可以通過迭代解決其判定問題來求解當(dāng)找到一個規(guī)模為k的頂點(diǎn)覆蓋時，繼續(xù)尋找一個規(guī)模為k-1的頂點(diǎn)覆蓋。算法核心：對一個整數(shù)k，找一個規(guī)模為k的頂點(diǎn)集合覆蓋所有的邊。初始的時候，構(gòu)造一個規(guī)模為k的頂點(diǎn)集合（候選解）。局部搜索的每一步交換集合中的一點(diǎn)和集合外的一點(diǎn)。格局檢測用于頂點(diǎn)覆蓋問題最小頂點(diǎn)覆蓋問題可以通過迭代解決其判定問題來求解當(dāng)找到一個規(guī)模為k的頂點(diǎn)覆蓋時，繼續(xù)尋找一個規(guī)模為k-1的頂點(diǎn)覆蓋。算法核心：對一個整數(shù)k，找一個規(guī)模為k的頂點(diǎn)集合覆蓋所有的邊。初始的時候，構(gòu)造一個規(guī)模為k的頂點(diǎn)集合（候選解）。局部搜索的每一步交換集合中的一點(diǎn)和集合外的一點(diǎn)。格局檢測：對一個頂點(diǎn)v，如果從上次v被移出候選解之后，v的格局沒有改變過，那么禁止把v重新加入候選解。格局檢測更一般的說，格局檢測（CC）是一種思想不同的格局定義

不同的CC策略。比如對SAT問題，變量的格局還可以定義為：變量的關(guān)聯(lián)子句的狀態(tài)構(gòu)成的向量。不同的檢測方法

不同的CC策略。比如量化CC，以格局改變的幅度作為選擇解部件的一個優(yōu)先序法則。不同的格局定義，禁忌強(qiáng)度不同。可以設(shè)計多層次的CC策略。格局檢測格局檢測已經(jīng)被使用于多個組合優(yōu)化問題SAT，MaxSAT，頂點(diǎn)覆蓋，最大團(tuán)，圖著色，集合覆蓋，支配集，刻度劃分問題等等。從2011年提出到目前已經(jīng)產(chǎn)生20幾篇論文（包括其他團(tuán)隊）。格局檢測對SAT領(lǐng)域產(chǎn)生極大影響2013年SAT比賽隨機(jī)組接近40%的solver使用該技術(shù)；最近三年，共有6個獲獎SATsolver使用該技術(shù)，包括2個第一，2個第二，2個第三；最近兩年，非完備算法組獲獎的MaxSAT

solver大都采用了格局檢測。AAAI2013年關(guān)于SAT方面的TutorialForum評價“Itisoutstanding.Itislikelychangingthegame.”機(jī)遇和挑戰(zhàn)把格局檢測（CC）用于提高原有局部搜索算法容易實(shí)現(xiàn)，開銷?。ǜ咝?shí)現(xiàn)CC策略參考本人在AIJournal2011和AIJournal2013的兩篇論文）可以普遍用于各種組合優(yōu)化問題嘗試不同的CC策略，總有一款適合你

（比如對于SAT問題已有4種CC策略：基于鄰居變量的CC，基于關(guān)聯(lián)子句的CC，量化CC，雙層CC）機(jī)遇和挑戰(zhàn)把格局檢測（CC）用于提高原有局部搜索算法容易實(shí)現(xiàn)，開銷?。ǜ咝?shí)現(xiàn)CC策略參考本人在AIJournal2011和AIJournal2013的兩篇論文）可以普遍用于各種組合優(yōu)化問題嘗試不同的CC策略，總有一款適合你

（比如對于SAT問題已有4種CC策略：基于鄰居變量的CC，基于關(guān)聯(lián)子句的CC，量化CC，雙層CC）格局檢測的理論分析目前只得到一個結(jié)果從理論上證明格局檢測的有效性？需要理論工作！參考文獻(xiàn)關(guān)于格局檢測（CC）的更多信息，請參考以下文獻(xiàn)Localsearchwithedgeweightingandconfigurationcheckingheuristicsforminimumvertexcover.Artif.Intell.175(9-10):1672-1696(2011)LocalsearchforBooleanSatisfiabilitywithconfigurationcheckingandsubscore.Artif.Intell.204:75-98(2013)ClauseStatesBasedConfigurat