الگوریتم های جستجوی آگاهانه

الگوریتم های جستجوی آگاهانه

اسلاید 1: الگوريتم هاي جستجوي آگاهانهدانشگاه صنعتي اصفهان دانشکده برق و کامپيوترتهيه کننده: عبدالرضا ميرزايي

اسلاید 2: سرفصل مطالبجستجوي اول-بهترين جستجوي حريصانه جستجوي A*جستجوي A* حافظه محدودجستجوي عميق كننده تكراريA* جستجوي اول بهترين بازگشتي(RBFA*) SMA*هيوريستيك هاالگوريتم هاي جستجوي محليجستجوي simulated annealingالگوريتم هاي ژنتيكجستجوي onlineدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر2

اسلاید 3: مرور: جستجوي درختاستراتژي توسط ترتيب گسترش يافتن گره ها تعريف مي شود.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر3

اسلاید 4: جستجوي اول - بهتريننمونه اي از الگوريتم عمومي tree-search يا graph-search است که در ان يک گره بر اساس يک تابع ارزيابي f(n) براي گسترش انتخاب مي شود.تابع ارزيابي evaluation function تخمين ”ميزان مطلوب بودن“ گره هربار مطلوب ترين گره گسترش نيافته را بسط مي دهد.پياده سازي:گره ها در fringe به ترتيب نزولي ميزان مطلوبيت مرتب مي شوند. يك صف اولويتحالت هاي خاص جستجوي حريصانه Greedy searchجستجوي A*دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر4

اسلاید 5: جستجوي اول -بهترين حريصانهتابع هيوريستيك h(n) هزينة تخميني مسير از گره n تا نزديکترين گره هدفبراي مثال، در نقشه روماني مي توان هزينة مسير از هر شهري به بخارست را از طريق مسافت يك خط مستقيم از آن شهر به بخارست تخمين زد.hSLD(n) فاصله مستقيم از n تا بخارستجستجوي اول -بهترين حريصانهجستجوي حريصانه گره اي را گسترش مي دهد كه به نظر مي رسد نزديكترين گره به هدف ( بخارست) باشد.تابع ارزيابي f(n)= h(n)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر5

اسلاید 6: نقشه روماني به همراه هزينه مراحل برحسب kmدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر6

اسلاید 7: جستجوي اول -بهترين حريصانه

اسلاید 8: جستجوي اول -بهترين حريصانه

اسلاید 9: جستجوي اول -بهترين حريصانه

اسلاید 10: جستجوي اول -بهترين حريصانه

اسلاید 11: خواص جستجوي اول -بهترين حريصانهدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر11كامل؟–خير (ممکن است در حلقه بينهايت گير کند)پيچيدگي زماني؟O(bm) – اما با يک هيوريستيک خوب مي تواند به شدت بهبود يابدپيچيدگي حافظه؟– O(bm) تمام گره ها را در حافظه نگه مي دارد.بهينه؟– خير (مثلا در مثال قبل مسير بهينه اي وجود دارد که از ديد جستجوي حريصانه مخفي مي ماند).

اسلاید 12: حلقه بينهايت در جستجوي حريصانهدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر12پايانشروعIasi  Neamt  Iasi  Neamt 

اسلاید 13: جستجوي A*ايده: از گسترش مسيرهايي كه تاكنون مشخص شده پرهزينه مي باشند، اجتناب كن. تابع ارزيابيf(n) = g(n) + h(n)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر13هزينة رسيدن به گره n هزينة تخميني ارزانترين مسير از گره n به هدفهزينة ارزانترين مسير گذرنده از گره n به هدف

اسلاید 14: مثال جستجوي A*

اسلاید 15: مثال جستجوي A*

اسلاید 16: مثال جستجوي A*

اسلاید 17: مثال جستجوي A*

اسلاید 18: مثال جستجوي A*

اسلاید 19: مثال جستجوي A*

اسلاید 20: هيوريستيك قابل قبوليك هيوريستيك h(n) قابل قبول است اگر براي هر گره n داشته باشيم : h(n) ≤ h*(n) که h*(n) هزينه واقعي براي رسيدن به هدف از گره n مي باشد.يك هيوريستيك قابل قبول هرگز هزينه رسيدن به هدف را بيش از حد تخمين نمي زند، يعني خوش بينانه است.مثال: هيوريستيكhSLD(n) هيچگاه فاصله را بيش از حد واقعي تخمين نمي زند.قضيه: اگر h(n) قابل قبول باشد، A* با استفاده از TREE-SEARCH بهينه استدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر20

اسلاید 21: اثبات بهينگي A*فرض كنيد يك جواب زير بهينه مانند G2 ايجاد شده و در fringe قرار دارد. همچنين فرض کنيد n يك گره گسترش نيافته روي كوتاهترين مسير به هدف بهينه G باشد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر21f(G2) = g(G2)since h(G2) = 0 g(G2) > g(G) since G2 is suboptimal f(G) = g(G)since h(G) = 0 f(G2) > f(G)from above

اسلاید 22: اثبات بهينگي A*فرض كنيد يك جواب زير بهينه مانند G2 ايجاد شده و در fringe قرار دارد. همچنين فرض کنيد n يك گره گسترش نيافته روي كوتاهترين مسير به هدف بهينه G باشد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر22f(G2)> f(G) from above h(n)≤ h*(n)since h is admissibleg(n) + h(n)≤ g(n) + h*(n) f(n) ≤ f(G)چون f(G2) > f(n) است A* هيچگاه G2 را براي گسترش انتخاب نمي کند

اسلاید 23: بهينگي A*اگر به جايTREE–SEARCH از GRAPH–SEARCH استفاده كنيم، آنگاه قضيه قبل ديگر صدق نمي كند.ممكن است راه حلهاي نيمه بهينه برگردانده شوند، زيرا GRAPH–SEARCH مي تواند ميسر بهينه به يك حالت تكراري را كنار بگذارد، اگر اولين گره توليدي نباشد.دو راهکار براي حل اين مشكل:اولين راه حل، اين است كه GRAPH–SEARCH را به نحوي توسعه بدهيم كه از بين مسيري كه به يك گره مي رسد آن مسيري كه پرهزينه تر است را كنار بگذارد. اين روش فضاي زيادي اشغال مي كند، اما بهينگي را تضمين مي كند.راه حل دوم، اطمينان از اين موضوع است كه مسير بهينه به هر حالت تكراري، هميشه اولين مسيري است كه دنبال مي شود. شرط سازگاري (يا يكنواختي)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر23

اسلاید 24: هيوريستيک هاي سازگاريك هيوريستيك سازگار consistent است اگر h(n) ≤ c(n,a,n) + h(n)شكلي از قانون كلي نامساوي مثلث است كه تصريح مي كند هيچ ضلعي از يك مثلث نمي تواند بلندتر از مجموع دو ضلع ديگر باشد.هر هيوريستيك سازگار، قابل قبول نيز هست.قضيه: اگر h(n) سازگار باشد، A* با استفاده از GRAPH–SEARCH بهينه استدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر24

اسلاید 25: هيوريستيک هاي سازگاراگر h(n) سازگار باشد آنگاه f(n) در طول هر مسيري، غيرنزولي است. f(n) = g(n) + h(n) = g(n) + c(n,a,n) + h(n) ≥ g(n) + h(n) = f(n)مي توان نتيجه گرفت كه رشته اي از گره ها كه توسطA* با استفاده از GRAPH–SEARCH گسترش يافته اند به ترتيب غيرنزولي f(n) مي باشد. در نتيجه، اولين گره هدفي كه براي گسترش انتخاب مي شود بايد يك راه حل بهينه باشد، زيرا تمامي گره هاي بعدي حداقل به همان اندازه هزينة خواهند داشت.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر25

اسلاید 26: بهينگي A*A* به تدريج f-contour ها را اضافه مي کند. دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر26

اسلاید 27: خواص جستجوي A*اولين راه حل پيداشده، بايد يك راه حل بهينه باشد زيرا گره هاي هدف در تمامي contourهاي بعدي داراي هزينه f بيشتري خواهند بود و در نتيجه هزينة G بالاتري نيز دارند (زيرا تمامي گره هاي هدف داراي h(n)=0 هستند).جستجوي A* كامل است. همان طور كه نوارهاي با f در حال افزايش را اضافه مي كنيم، بايد بالاخره به نواري برسيم كه در آنجا f مساوي هزينة مسير تا يك حالت هدف است.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر27

اسلاید 28: خواص جستجوي A*دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر28كامل؟–بله، مگر اينكه تعدادي نامحدود گره با f ≤ f(G) وجود داشته باشد. A* –در گراف هاي متناهي محلي ( با فاكتور انشعاب محدود) كامل مي باشدپيچيدگي زماني؟– نمايي پيچيدگي حافظه؟– نمايي تمام گره ها را در حافظه نگه مي دارد.بهينه؟– بله

اسلاید 29: خواص جستجوي A*بهينه؟– بله نمي تواند fi+1 را گسترش دهد مگر آنکه fi تمام شده باشد. A* – تمام گره ها با f(n) <f* را گسترش مي دهد. A* – برخي گره ها با f(n) =f* را گسترش مي دهد. A* – هرگز گره اي با f(n) >f* را گسترش نمي دهد. A* داراي كارآيي بهينه optimally efficient مي باشد يعني هيچ الگوريتم بهينة ديگري تضمين نمي كند كه تعداد گره هايي كه گسترش مي دهد از A* كمتر باشد.علت اين امر آن است كه هر الگوريتمي كه تمامي گره ها را با f(n) <f* را گسترش ندهد خطر از دست دادن راه حل بهينه را دارد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر29

اسلاید 30: جستجوي A* با حافظه محدودزمان محاسبه، نقطه ضعف اصليA* نيست. از آنجا كه اين الگوريتم، تمامي گره هاي توليد شده را در حافظه نگهداري مي كند معمولاً بسيار بيشتر از آنكه وقت كم بياورد، حافظه كم مي آورد.در مورد بسياري از مسائل بزرگ، عملي نيست.چند راه حل براي مسأله حافظه در A*جستجوي عميق كننده تكراري A* (IDA*)جستجوي اول-بهترين بازگشتي(RBFS) جستجوي (ساده شده) A* با حافظه محدود ((S)MBA*)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر30

اسلاید 31: IDA*ايدة استفاده از راهکار عميق کننده تكراري در زمينة جستجوي آگاهانهتفاوت اصلي بين IDS و IDA*در IDA* به جاي محدوده عمقي از محدوده f (يعني g+h) استفاده مي شود.در هر تكرار، مقدار برش، كوچكترين هزينة f ميان تمام گره هايي است که از برش تكرار قبلي بيشتر باشند.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر31

اسلاید 32: جستجوي اول -بهترين بازگشتي (RBFS)يك الگوريتم بازگشتي با فضاي خطي كه سعي مي كند از جستجوي اول- بهترين استاندارد تقليد كند.ساختارRBFS مشابه جستجوي اول عمق بازگشتي است، اما به جاي ادامه دادن مسير فعلي به طور نامشخص، خود را از مقدار بهترين f مسير جايگزين قابل دسترس از تمام اجداد گره فعلي مطلع نگه مي دارد.اگر گره فعلي از اين محدوده فراتر رود، تابع بازگشتي آن را به عقب برمي گرداند تا روي يك مسير جايگزين ديگر قرار گيرد.در بازگشت به عقب مقدار f مربوط به هر گره موجود در مسير را با بهترين مقدار f فرزندانش جايگزين مي کند.بنابراين گسترش مجدد نتيجه فعلي هنوز ممكن مي باشد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر32

اسلاید 33: جستجوي اول -بهترين بازگشتي (RBFS)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر33

اسلاید 34: جستجوي اول -بهترين بازگشتي (RBFS)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر34

اسلاید 35: جستجوي اول -بهترين بازگشتي (RBFS)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر35

اسلاید 36: جستجوي اول -بهترين بازگشتي (RBFS)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر36

اسلاید 37: خواص جستجوي RBFSدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر37RBFSكمي كارآتر ازIDA* مي باشد – هنوز گسترش اضافي گره ها وجود دارد( تغيير عقيده)پيچيدگي زماني؟– بيان پيچيدگي زماني آن نسبتاً مشكل است: هم به دقت تابع هيوريستيك بستگي دارد و هم به اين كه در حين گسترش گره ها، بهترين مسير هر چند وقت يكبار تغيير مي كند. – مانند IDA* در معرض افزايش نمايي پيچيدگي زماني قرار داردپيچيدگي حافظه؟– O(bd)بهينه؟– همانند A* ، الگوريتم RBFS نيز يك الگوريتم بهينه است اگر تابع هيوريستيك h قابل قبول باشد.

اسلاید 38: خواص جستجوي RBFSRBFS و IDA* هر دو ممكن است در معرض افزايش نمايي بالقوه در پيچيدگي همراه با جستجو در گرافها قرار بگيرند.آنها نمي توانند حالتهاي تكراري، به جز آنهايي را كه بر روي مسير فعلي قرار دارند بررسي كنند. در نتيجه، ممكن است يك حالت را چندين بار اكتشاف كنند.از ميزان بسيار كم حافظه رنج مي برند.IDA* فقط يك عدد را نگهداري مي كند (محدوديت مقدار فعلي f)RBFS اطلاعات بيشتري را در حافظه نگهداري مي كند، ولي فقط از O(bd) حافظه استفاده مي کند.حتي اگر حافظه بيشتري در دسترس باشد نمي توانند از آن استفاده كنند.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر38

اسلاید 39: (Simplified) Memory Bounded A*ايده: استفاده از تمامي حافظه موجود– يعني، گسترش بهترين گره هاي برگي تا زماني كه حافظه موجود پر شود.SMA* دقيقا مثل A* عمل مي كند، يعني تا زماني كه حافظه پر شود، بهترين گره را گسترش مي دهد. در صورت پر شدن حافظه هميشه بدترين گره برگي (گرهي با بيشترين مقدار f) را از حافظه حذف مي كنداطلاعات گره هاي فراموش شده را در پدرشان ذخيره مي كنددانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر39

اسلاید 40: (Simplified) Memory Bounded A*SMA*كامل است، اگر راه حل دست يافتني وجود داشته باشد (يعني اگر عمق كم عمقترين گره هدف كمتر از اندازة حافظه باشد).اين الگوريتم بهينه است در صورتي كه راه حل بهينة دست يافتني وجود داشته باشد. در غير اين صورت بهترين راه حل دستيافتني را برمي گرداند.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر40

اسلاید 41: هيوريستيك هاي قابل قبولمثال براي پازل 8 تايي:h1 تعداد كاشيهايي كه در جاي خود قرار نگرفته اند.h2 مجموع فواصل افقي و عمودي كاشيها از موقعيتهاي هدفشان (فاصله city block يا Manhattan دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر41هر دو قابل قبولh1(S) = 8h2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18

اسلاید 42: اگر بازاء هر n داشته باشيم h2(n) ≥ h1(n)(و هر دو هيوريستيك قابل قبول باشند) آنگاه h2 بر h1 تسلط دارد و براي جستجو بهتر مي باشد. مثال هزينه جستجو: تعداد گره هاي توليد شده در عمق هاي مختلف:d=12IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodesدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر42

اسلاید 43: ضريب انشعاب موثر b*ضريب انشعاب موثر:(EBF) اگر تعداد گره هاي گسترش يافته توسط روال جستجو N و عمق راه حل d باشد b* به صورت زير محاسبه مي شود: N+1 = 1+b* + (b*)2+ … + (b*)dمثال: اگر A* راه حلي را در عمق 5 با استفاده از 52 گره پيدا كند، ضريب انشعاب موثر؟53 = 1 + b* + (b*)2 +…(b*)5 b* = 1.92در يك هيوريستيك هر چه فاكتور انشعاب به يك نزديكتر باشد، بهتر است و آن هيوريستيك كيفيت كشف كنندگي بيشتري دارد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر43

اسلاید 44: رابطه بين هزينه جستجو و ضريب انشعاب موثردانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر44

اسلاید 45: ابداع توابع هيوريستيكمسأله اي كه تعداد كمتري محدوديت براي اقدامات دارد، يك مسألةتعديل شده relaxed ناميده مي شود.هزينة يك راه حل بهينه براي يك مسألة تعديل شده، يك هيوريستيک قابل قبول براي مسألة اصلي است.هزينه راه حل بهينه يك مسأله تعديل شده، بيشتر از هزينه راه حل بهينه در مسأله واقعي نيست.مثال: پازل 8 تايي. يك كاشي مي تواند از خانه A به خانه B برود اگر A مجاور B باشد و B خالي باشد. دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر45

اسلاید 46: ابداع توابع هيوريستيكمثال: پازل 8 تايي. يك كاشي مي تواند از خانه A به خانه B برود اگر A مجاور B باشد و B خالي باشد. ميتوانيم با حذف يك يا هر دو شرط، سه مسألة تعديل شده توليد كنيم:يك كاشي مي تواند از خانه A به خانه B برود اگر A مجاور B باشد. (h2)يك كاشي مي تواند از خانه A به خانه B برود اگر B خالي باشد. يك كاشي مي تواند از خانه A به خانه B برود. (h1)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر46

اسلاید 47: الگوريتم هاي جستجوي محلي و مسائل بهينه سازيدر بسياري از مسائل بهينه سازي، مسير راه حل اهميت ندارد؛ خود حالت هدف پاسخ مسأله مي باشد.فضاي حالت = مجموعه پيكره بندي هاي كامل هدف = يافتن يك پيكره بندي كه محدوديت هاي مسأله را ارضاء كند، مانند مساله n- وزيردر چنين مواردي مي توان از الگوريتم هاي جستجوي محلي بهره گرفت.يك حالت ”فعلي“ را به تنهايي در نظر بگير؛ سعي كن آن را بهبود ببخشي.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر47

اسلاید 48: الگوريتم هاي جستجوي محلي و مسائل بهينه سازيجستجوي محلي = استفاده از يك حالت فعلي و حركت به حالت هاي همسايهمزايا:– استفاده از حافظه بسيار كم– يافتن راه حل هاي معقول در اغلب موارد در فضاهاي حالت بزرگ و يا نامحدودمفيد براي مسائل بهينه سازي محض– يافتن بهترين حالت بر طبق تابع هدف (objective function)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر48

اسلاید 49: State space landscapeيك landscape هم شامل محل (كه توسط حالت تعريف مي شود) و هم شامل ارتفاع (كه توسط مقدار تابع هيوريستيک هزينه يا تابع هدف تعريف مي شود) مي باشد.اگر ارتفاع متناظر هزينه باشد، آنگاه هدف يافتن عميقترين دره (يك كمينة سراسري) است و اگر ارتفاع متناظر با تابع هدف باشد، آنگاه هدف يافتن بلندترين قله (يك بيشينة سراسري) است.يك الگوريتم جستجوي محلي كامل، هدف را (در صورت وجود) پيدا مي كند و يك الگوريتم بهينه يك كمينه يا بيشينة سراسري را پيدا مي كند.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر49

اسلاید 50: State space landscapeدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر50

اسلاید 51: تپه نوردي( يا گراديان صعودي/نزولي)الگوريتم جستجوي تپه نوردي فقط از يك حلقه تشكيل مي شود كه مدام در جهت افزايش مقدار حركت مي كند (يعني به سمت بالاي تپه).الگوريتم هنگامي خاتمه پيدا مي كند كه به قلّه اي برسد كه در آنجا هيچ همسايه اي مقدار بيشتري نداشته باشد.اين الگوريتم، درخت جستجو را نگهداري نمي كند. بنابراين، ساختمان دادة گره فعلي تنها نياز به ثبت حالت و مقدار تابع هدفش را دارد.تپه نوردي، فراتر از همسايه هاي مجاور حالت فعلي را نگاه نمي كند.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر51

اسلاید 52: تپه نوردي( يا گراديان صعودي/نزولي)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر52

اسلاید 53: مثال: n-وزيرn وزير را در يك صفحه شطرنجn * n به گونه اي قرار بده كه هيچ دو وزيري در يك سطر، ستون و يا قطر قرار نگيرند.8- وزير:فرمول بندي حالت كامل: هر حالت شامل 8 وزير يعني يکي در هر ستونتابع پسين همه حالتهاي ممکني که با جابجايي يک وزير به مربع ديگري در همان ستون توليد مي شود را برمي گرداند. هر حالت 8*7 پسين دارد.تابع هيوريستيكh تعداد جفتهايي از وزيرهاست كه چه به صورت مستقيم و چه غير مستقيم در حال حمله به يكديگر هستند.كمينة سراسري اين تابع صفر است كه فقط در راه حل كامل اتفاق مي افتد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر53

اسلاید 54: مثال: n-وزيردانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر545 حرکتh=17h=1بهترين پسين داراي h=12 است

اسلاید 55: تپه نورديتپه نوردي اغلب به دلايل زير گير مي كند:بيشينه هاي محلي: الگوريتمهاي تپه نوردي كه به همسايگي يك بيشينة محلي مي رسند، رو به بالا به سمت قلّه كشيده مي شوند، ولي پس از آن گير مي كنند و جاي ديگري نمي روند.Ridge: داراي يك رشته بيشينة محلي هستند كه گذشتن از آنها براي الگوريتمهاي حريص بسيار مشكل است.فلاتها: فلات ناحيه اي از دورنماي فضاي حالت است كه در آن تابع ارزياب، ثابت است. فلات مي تواند يك بيشينة محلي مسطح باشد كه از آن هيچ مسير رو به بالايي وجود ندارد يا يك شانه باشد كه از آن بتوان به بالاتر هم رفت. دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر55

اسلاید 56: Ridgeدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر56

اسلاید 57: انواع ديگر تپه نورديتپه نوردي اتفاقي stochastic hill climbingبه صورت تصادفي از ميان حركتهاي رو به بالا يكي را انتخاب مي كند. احتمال اين انتخاب مي تواند براساس شيب حركتهاي رو به بالا تغيير كند. اين روش معمولاً كندتر از تيزترين شيب به نتيجه مي رسد، اما در بعضي از landscape هاي حالت، بهترين راه حل را پيدا مي كند.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر57

اسلاید 58: انواع ديگر تپه نورديتپه نوردي اولين گزينه، first choice hill climbing تپه نوردي اتفاقي را به كار مي گيرد به اين صورت كه به صورت تصادفي پسين توليد مي كند تا زماني كه پسيني توليد شود كه از حالت فعلي بهتر باشد. اين راهبرد هنگامي مناسب است كه يك حالت داراي تعداد زيادي (مثلاً هزار) پسين باشد.تپه نوردي با شروع مجدد تصادفي random restart hill climbingيك مجموعه جستجوي تپه نوردي را از حالتهاي شروع تصادفي اجرا مي كند و هنگامي كه يك هدف پيدا شد متوقف ميشود. اين روش با احتمال نزديك به يك، كامل مي باشد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر58

اسلاید 59: سردسازي شبيه سازي شدهالگوريتم تپه نوردي كه هرگز حركت رو به پايين به سمت حالتهايي با مقادير كمتر (يا هزينة بالاتر) را انجام نمي دهد، ناكامل بودنش قطعي است، زيرا ممكن است در يك بيشينة محلي گير كند.در مقابل، يك راهپيمايي كاملاً تصادفي random walk(يعني حركت به پسيني كه از مجموعة پسينها به طور يكنواخت و كاملاً تصادفي انتخاب شده است) كامل ولي به شدت ناكارآمد مي باشد.در نتيجه، تلاش در جهت تركيب تپه نوردي با يك راهپيمايي تصادفي كه هم كارآمد و هم كامل باشد، كار معقولي به نظر مي رسد.سردسازي شبيه سازي شده، يك چنين الگوريتمي است.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر59

اسلاید 60: سردسازي شبيه سازي شدهايده: Simulated Annealingاز ماكزيمم هاي محلي با انجام حركت هاي بد فرار كن.اما به تدريج اندازه و تعداد حركات بد ( به سمت پايين) را كم كندانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر60

اسلاید 61: سردسازي شبيه سازي شدهپيشروي مانند تپه نوردي مي باشد، اما در هر مرحله حالت بعدي به طور تصادفي انتخاب مي شود.اگر حالت بعدي انتخاب شده بهتر باشد، همواره به آن حالت بعدي خواهيم رفت.در غير اين صورت، تنها با يك احتمال به آن حالت خواهيم رفت و اين احتمال به صورت نمايي كاهش مي يابد.تابع احتمال:دما :Tميزان كاهش در هر مرحله :ΔEدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر61

اسلاید 62: خواص جستجوي SAدر مقادير بالاترT احتمال انجام حركات بد (رفتن به سمت پايين) بيشتر است (مانند جستجوي تصادفي رفتار مي كند).با كاهش T اين احتمال كاهش يافته و درT=0 اين احتمال به صفر مي رسد. ( مانند تپه نوردي رفتار مي كند)مي توان ثابت کرد که اگر T به اندازه کافي آرام کاهش يابد با احتمال نزديک به يک SA يک پاسخ بهينه را خواهد يافت. دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر62

اسلاید 63: جستجوي پرتوي محلي Local Beam Searchشروع با k حالت كه به طور تصادفي ايجاد شده اند. در هر تكرار، تمام فرزندان براي هرk حالت توليد مي شوند. اگر يكي از آنها حالت هدف بود جستجو متوقف مي شود و درغير اين صورت از ميان ليست كامل فرزندان k تا از بهترين ها انتخاب مي شوند و مرحله بالا تكرار مي شود.تفاوت با جستجوي با شروع مجدد تصادفي در يك جستجوي با شروع مجدد تصادفي، هر فرآيند جستجو به طورمستقل از بقيه اجرا مي شود.در يك جستجوي پرتوي محلي، اطلاعات سودمند در بين k جستجوي موازي رد و بدل مي گردد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر63

اسلاید 64: جستجوي پرتوي اتفاقي Stochastic beam searchمشکل جستجوي پرتوي محلياين روش ممکن است از نبود تنوع بين k حالت رنج ببرد. به سرعت تمامي آنها در محدوده کوچکي از فضاي حالت جمع شوند.جستجوي پرتوي اتفاقيبه جاي انتخاب k بهترين از مجموعه پسينهاي منتخب k پسين را به صورت تصادفي انتخاب کند.احتمال انتخاب هر پسين خاص تابعي از برازندگي آنالگوريتم ژنتيکنمونه اي از جستجوي پرتوي اتفاقي که توليد حالتهاي پسين علاوه بر تغيير يك حالت، از تركيب دو حالت والد نيز (تركيب جنسي) انجام مي شود.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر64

اسلاید 65: الگوريتم ژنتيکدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر65

اسلاید 66: مثال الگوريتم ژنتيک: n – وزير تابع برازندگي : تعداد جفت وزير هايي كه يكديگر را تهديد نمي كنند. (مينيمم: صفر، ماكزيمم: 8*7/2=28)24/(24+23+20+11) = 31%23/(24+23+20+11) = 29%…دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر66

اسلاید 67: مثال الگوريتم ژنتيک: n – وزير عملگر Crossover دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر67

اسلاید 68: جستجوي onlineتا كنون تمام الگوريتم هاي مطرح شده offline بودند.Offline راه حل قبل از اجراي آن معين استOnline محاسبه و عمل بصورت يك در ميانجستجوي online براي محيط هاي پويا و نيمه پويا ضروري مي باشددر نظر گرفتن تمامي امكان هاي مختلف غير ممكن استاستفاده شده در مسائل اكتشافيحالت ها و اعمال ناشناختهمثال: يك روبات در يك محيط جديد، يك نوزاد و ...دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر68

اسلاید 69: مسائل جستجوي onlineدانش عامل:عمل (ها): ليست اعمال مجاز در حالت sتابع هزينه گام ( پس از تعيين s’) c(s, a, s’)GOAL-TEST(s)فرضياتعامل مي تواند حالت قبلي را تشخيص دهداعمال قطعي هستنددستيابي به هيوريستيك قابل قبول h(s)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر69

اسلاید 70: مسائل جستجوي onlineهدف: رسيدن به حالت هدف با حداقل هزينههزينه = كل هزينه مسير پيموده شدهنسبت رقابتي = مقايسه هزينه با هزينه مسير راه حل در حالتي كه فضاي جستجو شناخته شده باشدمي تواند نا محدود باشدمثلا در مواردي كه عامل به طور تصادفي به يك بن بست مي رسدفضاي حالت قابل کاوش امناز هر حالت دست يافتني حداقل يک حالت هدف قابل دسترس باشد مثلا فضاهاي حالت با اقدامات قابل برگشتدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر70

اسلاید 71: مسائل جستجوي online حالت هاي ملاقات شده A و S حالت بعدي؟در يكي از فضاهاي حالت شكست مي خوردهيچ الگوريتمي نمي تواند از بن بست ها در تمامي فضاهاي حالت اجتناب كنددانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر71

اسلاید 72: مسائل جستجوي onlineيك محيط 2 بعدي را تصور كنيد كه حريف قادر است در حين كاوش عامل فضاي حالت را بسازدباعث مي شود يک کارگزار جستجوي برخط يک مسير اجبارا ناکارامد را به سمت هدف دنبال کند.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر72

اسلاید 73: کارگزارهاي جستجوي onlineعامل يك نقشه از محيط نگهداري مي كند– نقشه بر اساس ورودي ادراكي بهنگام مي شود– از اين نقشه براي انتخاب عمل بعدي استفاده مي شودبه تفاوت مثلا با A* دقت كنيديك نسخه online تنها مي تواند گره اي را گسترش دهد كه به طور فيزيكي در آن قرار داشته باشد.براي اجتناب از جابجايي در عرض درخت بهتر است گره ها را به ترتيب محلي گسترش دهيم. مثلا جستجوي اول عمق، جستجوي محلي و ...دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر73

اسلاید 74: کارگزارجستجوي online با کاوش اول عمقدانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر74

اسلاید 75: جستجوي محلي onlineجستجوي تپه نوردي online مي باشد!!! يك حالت ذخيره شده استعملكرد بد به دليل وجود ماكزيمم هاي محليشروع مجدد تصادفي غير ممكن استراهکار 1: گام برداشتن تصادفي random walkيکي از اقدامات موجود حالت فعلي را به صورت تصادفي توليد ميکند. مي توان به اقداماتي که تا کنون امتحان نشده اند احتمال بالاتري داد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر75

اسلاید 76: جستجوي محلي onlineگام برداشتن تصادفي random walkاگر فضا متناهي باشد گام برداشتن تصادفي در نهايت يک هدف را پيدا مي کند يا کاوشهايش را کامل مي کند.اين فرايند ممکن است خيلي کند باشد ( مي تواند حالات بسياري را به صورت نمايي توليد كند)دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر76

اسلاید 77: جستجوي محلي onlineراهکار 2: اضافه نمودن حافظه به تپه نوردذخيره بهترين تخمين فعلي H(s) از هزينه رسيدن به هدفH(s) در ابتدا تخمين هيوريستيك h(s) مي باشد. پس از آن بر اساس تجربه بهنگام مي شود.هزينه تخميني رسيدن به هدف از طريق همسايه اي مانند s’، هزينه رسيدن به s’ به علاوه ي هزينه ي تخميني رسيدن به هدف از انجاست يعني c(s,a,s’)+H(s’) دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر77

اسلاید 78: Learning real-time A*دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر78

اسلاید 79: Learning real-time A*دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر79

اسلاید 80: يادگيري در جستجوي onlineنقشه محيط نتيجه هر اقدام در هر حالتدر محيطهاي معين تنها يک تجربه براي هر اقدام کافي استبراوردهاي دقيق تر از ارزش هر حالت با استفاده از قوانين به روزاوري محلي مشابه LRTA*به مجرد تعيين دقيق مقادير تپه نوردي محض راهبرد بهينه است.يادگيري مفهوم اعمالاقدام up مختصات Y را افزايش مي دهد مگر اينکه ديواري بر سر راه قرار داشته باشد.دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر80