兩種改進的模擬退火算法求解大值域約束滿足問題
發(fā)布時間：2019-06-20 03:53
【摘要】：隨機約束滿足問題的相變現(xiàn)象及求解算法是NP-完全問題的研究熱點。RB(revised B)模型是一個非平凡的隨機約束滿足問題,它具有精確的可滿足性相變現(xiàn)象和極易產生難解實例這兩個重要特征。針對RB模型這類具有大值域的隨機約束滿足問題,提出了兩種基于模擬退火的改進算法即RSA(revised simulated annealing algorithm)和GSA(genetic-simulated annealing algorithm)。將這兩種算法用于求解RB模型的隨機實例,數(shù)值實驗結果表明,在進入相變區(qū)域時,RSA和GSA依然可以有效地找到隨機實例的解,并且在求解效率上明顯優(yōu)于隨機游走算法。在接近相變閾值點時,由這兩種算法得到的最優(yōu)解僅使得極少數(shù)的約束無法滿足。
[Abstract]:The phase transition phenomenon and algorithm of stochastic constraint satisfaction problem are the research hotspots of NP- complete problem. RB (revised B) model is a non-trivial stochastic constraint satisfaction problem, which has two important characteristics: accurate satisfied phase transition phenomenon and easy to produce difficult examples. In order to solve the problem of satisfying stochastic constraints with large range, such as RB model, two improved algorithms based on simulated annealing, RSA (revised simulated annealing algorithm) and GSA (genetic-simulated annealing algorithm).), are proposed. The two algorithms are used to solve the random examples of RB model. The numerical experimental results show that RSA and GSA can still find the solution of random examples effectively when they enter the phase transition region, and the efficiency of the solution is obviously better than that of random walk algorithm. When the threshold point of phase transition is close to the threshold point of phase transition, the optimal solution obtained by these two algorithms makes only a very small number of constraints unsatisfied.
【作者單位】： 上海理工大學理學院;
【基金】：國家自然科學基金資助項目(11301339,11491240108,11471215) 上海高校青年教師培養(yǎng)計劃資助項目
【分類號】：TP18
[Abstract]:The phase transition phenomenon and algorithm of stochastic constraint satisfaction problem are the research hotspots of NP- complete problem. RB (revised B) model is a non-trivial stochastic constraint satisfaction problem, which has two important characteristics: accurate satisfied phase transition phenomenon and easy to produce difficult examples. In order to solve the problem of satisfying stochastic constraints with large range, such as RB model, two improved algorithms based on simulated annealing, RSA (revised simulated annealing algorithm) and GSA (genetic-simulated annealing algorithm).), are proposed. The two algorithms are used to solve the random examples of RB model. The numerical experimental results show that RSA and GSA can still find the solution of random examples effectively when they enter the phase transition region, and the efficiency of the solution is obviously better than that of random walk algorithm. When the threshold point of phase transition is close to the threshold point of phase transition, the optimal solution obtained by these two algorithms makes only a very small number of constraints unsatisfied.
【作者單位】： 上海理工大學理學院;
【基金】：國家自然科學基金資助項目(11301339,11491240108,11471215) 上海高校青年教師培養(yǎng)計劃資助項目
【分類號】：TP18
【相似文獻】
相關期刊論文 前10條
1 劉彥秀;姜華;潘全科;;基于全局和聲搜索的模擬退火算法改進[J];計算機工程與科學;2010年11期
2 謝玉瓏,王繼紅,俞汝勤;通用模擬退火用于穩(wěn)健多元分析校正[J];高等學校化學學報;1993年02期
3 李洪瑞;基于模擬退火算法的多目標數(shù)據關聯(lián)[J];情報指揮控制系統(tǒng)與仿真技術;1998年10期
4 郭茂祖,姜俊峰,李靜梅;模擬退火算法中冷卻調度選取方法的研究[J];計算機工程;2000年09期
5 鐘太勇;許小勇;;模擬退火算法求算一維非線性方程的根[J];鄖陽師范高等�？茖W校學報;2006年06期
6 鄭玉|，
本文編號：2502900
本文鏈接：http://sikaile.net/kejilunwen/zidonghuakongzhilunwen/2502900.html
