گیاهی ترین گیاهی ترین AnzanDigital فروشگاه

آموزش الگوریتم WalkSAT

آموزش الگوریتم WalkSAT

الگوریتم WALKSAT خانواده ای از الگوریتم های کارآمد در استنتاج گزاره ای مبتنی بر بازرسی مدل است که به جست وجوی تپه نوردی مربوط میشود و بخشی از “فناوری” منطق گزاره ای می باشد.

الگوریتم های جست وجوی محلی مستقیما میتوانند به مسئله های ارضا شدنی اعمال شوند، به شرطی که تابع ارزیابی مناسبی را انتخاب کنیم. چون هدف یافتن تناسبی است که هر clause را ارضا کند.(جهت آشنایی با مفاهیم اینجا را مطالعه کنید) تابع ارزیابی ای که تعداد clause های ارضا نشده را میشمارد، این کار را انجام میدهد. در واقع این معیار توسط الگوریتم MIN – CONFLICTS برای CSP ها بکار رفته است. تمام این الگوریتم ها در فضای انتساب های کامل گام برمیدارند و در هر زمان، “مقدار درستی” یک نماد را معکوس میکند. این فضا معمولا شامل چندین مینیمم محلی برای فرار از شکل های گوناگونی از تصادفی سازی های مورد نیاز است. در سالهای اخیر، آزمایش های زیادی برای یافتن توازن خوبی برای “تصادفی سازی” و “حریص بودن” انجام شده است.

 

یکی از ساده ترین و کارآمدترین الگوریتم ها WALKSAT است که شبه کد آن را نیز در ادامه خواهید دید. در هر تکرار، الگوریتم یک clause ارضا نشده را انتخاب میکند و نمادی را از آن clause انتخاب میکند تا تغییر دهد.

بطور تصادفی یکی از روشها را برای انتخاب نماد جهت تغییر برمیگزیند:

(۱) مرحله “کمترین تناقض” : که تعداد کلازهای ارضا نشده در حالت جدید را مینیمم میکند.

(۲) مرحله “پیمایش تصادفی” : که نماد را بطور تصادفی انتخاب میکند.

وقتی WALKSAT مدلی را برمی گرداند، جمله ورودی ارضاپذیری است، اما وقتی  failure را برمیگرداند دو علت ممکن وجود دارد : یا جمله ارضانشدنی است یا باید زمان بیشتری به الگوریتم بدهیم.

اگر قرار دهیم max_flips =   و  p>0 ، آنگاه WALKSAT سرانجام یک مدل را برمیگرداند (در صورت وجود) ، زیرا مراحل پیمایش تصادفی سرانجام منجر به جواب میشوند. اگر max_flips  بی نهایت و جمله ارضاناپذیر باشد، آنگاه الگوریتم هرگز خاتمه نمی یابد.

به همین دلیل ، وقتی انتظار داریم جوابی وجود داشته باشد، WALKSAT مفیدتر خواهد بود. از طرف دیگر WALKSAT همیشه نمیتواند ارضاپذیری را تشخیص دهد، که برای تصمیم گیری راجع به ایجاب منطقی ضروری است.

 

شبه کد الگوریتم WALKSAT 

 

function   WALKSAT(clauses, p , max_flips)  returns  a  satisfying  or  failure

         inputs:   clauses,  a  set  of  clauses  in  propositional  logic

                       p,  the  probability  of  choosing  to do  a “random  walk”  move, typically  around  ۰٫۵

                       max_flips,  number  of  flips  allowed  before  giving  up

 

         model <– a  random  assignment  of  truel  false  to  the  symbols  in  clauses

         for   i = 1  to   max_flips  do

                       if  model   satisfies  clauses  then  return  model

                       clause <– a randomly  selected  clause  from  clauses  that   is  false  in  model

                        with  probability  p  flip  the  value  in  model  of  a  randomly  selected  symbol  from  clause

                       else   flip  whichever  symbol  in  clause  maximizes  the  number  of   satisfied   clauses

         return  failure

 

جهت انجام پروژه در خصوص مسئله SAT با انواع الگوریتم های هوشمند و تکاملی با ما تماس بگیرید:

شماره تماس: ۰۹۱۲۰۵۶۳۲۶۴    (تلگرام)

ایمیل : matlab24ir@gmail.com و یا info@matlab24.ir

حل مسئله ۳-SAT با الگوریتم GSAT .

حل مسئله ۳-SAT با الگوریتم WalkSAT .

حل مسئله ۳-SAT با الگوریتم GSAT.

حل مسئله ۳-SAT با الگوریتم ژنتیک .

حل مسئله ۳-SAT با الگوریتم PSO .

حل مسئله ۳-SAT با الگوریتم ABC .

حل مسئله ۳-SAT با الگوریتم DE .

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

telegramchanel کانال تلگرام    با عضویت در کانال تلگرام از مطالب آموزشی و مطالب جدید وب سایت مطلع شوید

@matlab24Dotir

جهت عضویت کلیک کنید

 

      طراحی وب سایت

طراحی وب

شماره تماس:09120563264