هوش مصنوعی (فصل چهارم: جستجوی آگاهانه)

هوش مصنوعی (فصل چهارم: جستجوی آگاهانه)

اسلاید 1: فصل چهارمجستجوهاي آگاهانهAlireza yousefpouryousefpour@shomal.ac.ir1

اسلاید 2: جستجوي آگاهانه Heuristic Searchيا جستجوي مکاشفه اي اگر بتوان استراتژيهاي قبلي را به نحوي تکميل کرد بطوري که فضاي جستجو بسيار کوچکتر از آنچه که هست، گردد در اين صورت مي توانيم بگوييم رفتار الگوريتم کورکورانه نيست در جستجوي آگاهانه اطلاعاتي در رابطه با هزينه رسيدن به هدف در اختيار عامل قرار مي گيردفصل چهارم: جستجوي آگاهانه تابعي را معرفي مي کنيم که توضيحاتي در مورد مطلوب بودن يا نبودن بسط گره ارائه مي دهد به نام :Evaluation functionتابع ارزياب 2

اسلاید 3: فصل چهارم: استراتژيهاي جستجوي آگاهانهانواع هاي جستجوي آگاهانه1. جستجوي اول بهترين2. جستجوي محلي و بهينه سازي حريصانه A* IDA* RBFSSMA* تپه نوردي شبيه سازي annealing پرتو محلي الگوريتمهاي ژنتيک3

اسلاید 4: فصل چهارم: جستجوي اول بهترين1- جستجوي اول بهترينBest -First Searchاين استراتژي به اين صورت بيان مي‌شود که در يک درخت، گره ها توسط تابع ارزياب ارزيابي شده ، سپس گره‌ها مرتب مي‌شوند و در نتيجه گره‌اي که بهترين ارزيابي را داشته باشد، ابتدا بسط داده مي‌شودهدف: يافتن راه‌حل‌هاي کم‌هزينه است، اين الگوريتم‌ها عموماً از تعدادي معيار تخمين براي هزينه راه‌حل‌ها استفاده مي‌‌کنند و سعي بر حداقل کردن آنها دارند.4

اسلاید 5: نکته :گره که انتخاب مي شود براساس تابع ارزياب بهترين است اگر تابع ارزياب درست باشد پس گره حقيقتاً بهترين است ولي اگر تابع ارزياب درست نباشد جستجو را گمراه مي کندفصل چهارم: جستجوي اول بهترين - ادامه5

اسلاید 6: فصل چهارم: جستجوي اول بهترين - مثالمثال: در درخت جستجوي زير به شرطي که گره O هدف باشد براساس الگوريتم جستجوي Best First ترتيب رويت گره ها کدام است؟JMTF(B) =346535423203213343ABCDEFGHIKLNPOQRS46

اسلاید 7: فصل چهارم: جستجوي حريصانه1-1- جستجوي حريصانهGreedy Searchحداقل هزينه ي تخمين زده شده براي رسيدن به هدف را انتخاب مي کنددر اين روش نزديکترين گره به هدف براي بسط انتخاب مي شود که اين هزينه توسط تابع ارزيابي تخمين زده مي شود به نام :هدف h اين است که فضاي جستجو را کوچک کند در حالي که تضمين مي کند پاسخ در اين فضاي کوچک قرار دارد . Heuristics Functionhh : حسي ، ذهني 7

اسلاید 8: - مسئله معماي 8 : h1: تعداد خانه هايي که در مکان هاي نا درست قرار دارند h2: مجموع فاصله خانه هاي نادرست تا مکان هاي صحيح شان.- براي طي مسير بين دو شهر ارزان ترين مسير مي تواند کوتاهترين مسير باشد.h(n): ارزان ترين مسير از گره n به هدف .در جستجوي حريصانه ارزيابي هر گره برابر است با :f(n) = h(n)مثال : محاسبه hفصل چهارم: جستجوي حريصانه - ادامه8

اسلاید 9: h هر تابعي مي تواند باشد فقط لازم است h(n)=0 اگر n گره هدف باشد جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف مثل جستجوي عمقي است .نکته :h(Goal) = 0 در بدترين حالت h ممکن است هدف در عمق d باشد اما گره ها در عمق بيشتر زودتر گسترش يابند و هرگز براي امتحان مسير ها ممکن بر نگرددمعيارهاي ارزيابي استراتژي جستجوي حريصانه: 1) کامل بودن: فصل چهارم: جستجوي حريصانه - ادامه9

اسلاید 10: يعني h نزديک به هدف از hهاي Nodeهاي ديگر بيشتر شود و هرگز انتخاب نشودپس کامل نيست، 2) بهينه بودن: بهينه نيست زيرا توجهي به g(n) ندارد.3) پيچيدگي زماني: 4) پيچيدگي مکاني: O(bm)O(bm)در بدترين حالت در بدترين حالت ميزان کاهش پيچيدگي، به مسئله و کيفيت تابع h بستگي دارد.فصل چهارم: جستجوي حريصانه - ادامه10

اسلاید 11: ABCDEFGHIKMLNOg=3PQJWVXYZRSTU112133232323111232111323h(B)=1351013231221121021312332جستجوي حريصانهمثالفصل چهارم: جستجوي حريصانه - مثال11

اسلاید 12: ABCDEFGHIKMLNOg=3PQJWVXYZRSTU112133232323111232111323h(B)=1351013231221121021312332جستجوي حريصانهمثالفصل چهارم: جستجوي حريصانه - مثال12

اسلاید 13: ABCDEFGHIKMLNOg=3PQJWVXYZRSTU112133232323111232111323h(B)=1351013231221121021312332جستجوي حريصانهمثالهزينه مسير پاسخ = 7 ولي هزينه پاسخ بهينه = 4فصل چهارم: جستجوي حريصانه - مثال13

اسلاید 14: فصل چهارم: جستجوي A*حداقل‌سازي مجموع هزينه مسير جستجوي حريصانه: h(n) را به سمت هدف حداقل مي کندf(n) = h(n) جستجو با هزينه يکنواخت: g(n) يا هزينه مسير را حداقل مي کندf(n) = g(n)نه بهينه بود و نه کاملهم بهينه است و هم کاملالگوريتم A*f(n) = g(n) + h(n)الگوريتم گره اي را بسط مي دهد که کمترين f را داراست 1-2- جستجوي A*14

اسلاید 15: هنگام توليد گراف فاصله طي شده از مبداء محور رشد گراف است ولي به تدريج فاصله مانده تا هدف تاثير بيشتري در توليد گراف خواهد داشت.:  از سمت يک به سمت صفر کاهش پيدا مي کند در شروع توليد فضاي پاسخ مساوي يک است و سپس به تدريج کاهش پيدا مي کندf(n) =  g(n) + (1-) h(n) : 1  0تابع ارزياب ديگر:فصل چهارم: جستجوي A* - ادامه15

اسلاید 16: S4B1G10D1G20E6A2C3215411558712921جستجوي A*مثالفصل چهارم: جستجوي A* - مثال اولفضاي حالت16

اسلاید 17: درخت جستجوي با استفاده از جستجوي A*S4B1E6A2C3D1G10G202581412f=2+2f=5+310+63+17+04+1f* = f =6+0=6فصل چهارم: جستجوي A* - مثال اولG105C3S5124+35+56+09+017

اسلاید 18: Goal Stateh = تعداد چهارخانه‌هايي که در مکان‌هاي نادرست هستند. مثال:معماي 828316475Start State1238 4765فصل چهارم: جستجوي A* - مثال دوم18

اسلاید 19: 283164750+4283164 752831 476528316475 1+51+31+5283 147652 3184765283147652+3goal !2+4 832147653+32+3283714 653+4 231847653+2123 847654+11238 47655+0123784 655+2231847653+4جستجوي A*مثالh = تعداد چهارخانه‌هايي که در مکان‌هاي نادرست هستند. معماي 8فصل چهارم: جستجوي A* - مثال دوم19

اسلاید 20: 20فصل چهارم: جستجوي A* - ادامهدر صورتي که h يکي از آن استثناها باشد که يکنوا نيست، مي توان با ايجاد يک اصلاح جزئي آن را يکنوا مي‌کنيمخاصيت يکنوايي (monotonicity)تقريباً تمام کشف‌کنندگي‌هاي مجاز داراي اين ويژگي هستند که در طول هر مسيري از ريشه، هزينه f هرگز کاهش پيدا نمي‌کند.اين خاصيت براي کشف‌کنندگي، خاصيت يکنوايي (monotonicity) گفته مي‌شود.نگاهي گذرا به اثبات کامل A*:

اسلاید 21: f(n’) = max( f(n) , g(n’)+h(n’) )هزينه گره فرزند هزينه گره والداز اين طريق، مقادير گمراه کننده اي که ممکن است با يک هيورستيک يکنوا پديدار شوند حذف مي کنيم. به اين معادل سازي معادله pathmax ناميده مي شودهر گره جديدي که توليد مي‌شود، بايد کنترل کنيم که آيا هزينة f اين گره از هزينه f پدرش کمتر است يا خير. اگر کمتر باشد، هزينة f پدر به جاي فرزند مي‌نشيند.اگر n’ فرزند n باشد فصل چهارم: جستجوي A* - ادامه21

اسلاید 22: با شرطي بر روي تابع هيورستيک h(n) بهينه نيز خواهد بود:اين شرط عبارت است از اينکه تابع h(n) قابل قبول (admissibles) باشددر مثال مسير يابي بين دو شهر h(n) مي تواند خط مستقيم بين دو شهر باشد؟ بله قابل قبول است چون خط مستقيم کوهتاهترين مسير بين دو شهر است0  h(n)  h*(n) for all nSh*(n) : هزينه واقعي رسيدن از n به هدف باشد آنگاه:بهينه بودن A*: يعني براي هر گره مثل n ، بيشتر از هزينه واقعي مسير تا هدف نباشد. يعني تابع h(n) تخمين اضافي نزند.فصل چهارم: جستجوي A* - ادامه22

اسلاید 23: با توجه به جستجوي با هزينه يکنواخت که وابسته به g(n) است و با شرط اينکه هزينه يک مسير با ادامه مسير، کاهش پيدا نخواهد کرد، کامل است آنگاه:فصل چهارم: جستجوي A* - ادامه23f(n’) = g(n’) + h(n’) = g(n) + c + h(n’) f(n) = g(n) + h(n) f(n’)  f(n)g(n) + c + h(n’)  g(n) + h(n) c + h(n’)  h(n)نا برابري مثلثي

اسلاید 24: 27311XYh=100h=1h=0h=0g(X)+h(X) = 102g(Y)+h(Y) = 74Optimal path is not found!در صورتي A* جواب بهينه را مي دهد که h قابل قبول باشد در مثال فوق h قابل قبول نيستمثالفصل چهارم: جستجوي A* - ادامه24

اسلاید 25: اگر f* هزينه هزينه مسير راه حل (هزينه واقعي مسير بهينه از شروع تا هدف) تعريف شود مي توان گفت: A* تمام گره ها با f(n) < f* را بسط خواهد دادفصل چهارم: جستجوي A* - ادامهf*25

اسلاید 26: اگر f* هزينه هزينه مسير راه حل (هزينه واقعي مسير بهينه از شروع تا هدف) تعريف شود مي توان گفت: A* تمام گره ها با f(n) < f* را بسط خواهد داد A*ممکن است تعداد از گره هايي که f(n)=f* است قبل از اينکه گره هدف انتخاب شود بسط دهد A* تمام گره ها با f(n)>f* را بسط نخواهد داد. يعني الگوريتم A* قادر است گره هاي بدل را بدون امتحان حذف يا هرس کند.فصل چهارم: جستجوي A* - ادامه

اسلاید 27: 27فصل چهارم: جستجوي A* - ادامه (کارآ بهينه Optimally effecient) يعني هيچ الگوريتم بهينه اي که جستجو را از ريشه شروع مي کند، تضمين نمي کند تعداد گره هاي کمتري نسبت به A* ايجاد کند و در زماني که تابع هيورستيک بکار رفته در تمام الگوريتمها يکسان باشد. يک الگوريتم ممکن است که راه حل بهينه را در صورتي که همه گره ها با f(n)<f* بسط ندهد، گم کند.A* به طور موثري براي هر تابع h قابل قبول، از نظر بهينگي کارآ مي باشد.

اسلاید 28: يک راه براي تشخيص کيفيت کشف‌کنندگي فاکتور انشعاب مؤثر b* استمعمولاً فاکتور انشعاب مؤثر که توسط کشف‌کنندگي نمايش داده مي‌شود، مقدار ثابتي دارد.يک کشف‌کنندگي خوب طراحي شده، b* آن در حدود 1 است.اثر صحت کشف‌کنندگي بر کارايي:فاکتور انشعاب مؤثر b* (Effective Branching Factor) تعداد گره‌هاي بسط داده شده توسط A* براي يک مسئله ويژه N باشد و عمق راه حل d، سپسb* فاکتور انشعابي است که يک درخت يکنواخت با عمق d خواهد داشت تا گره‌هاي N را نگهدارد. بنابراين: 1+ b*+( b*)2…+( b*)d = Nفصل چهارم: جستجوي A* - کارآيي A*28

اسلاید 29: مثاليعني متوسط تعداد گره هايي که در هر سطر بسط مي دهد تا به هدف برسد برابر با 1.91 است اگر هدف در عمق 5 باشد d = 5و تعداد گره هايي A* بسط داده تا به هدف رسيده برابر 25 باشد N = 25 آنگاه :b* = 1.91 تابع هيورستيکي که b* آن به يک نزديکتر باشد بهتر طراحي شده استيعني بين توابع h آن تابعي که b* آن به يک نزديکتر است مناسبتر است زيرا تعداد گره کمتري بسط مي دهد.فصل چهارم: جستجوي A* - کارآيي A*29

اسلاید 30: معماي 8 يکي از مسائل اوليه کشف‌کنندگي بود.h2 = مجموع فواصل چهارخانه‌ها از مکان‌هاي هدف صحيحشان است. فاصله‌اي که ما حساب مي‌کنيم، مجموع فواصل عمودي و افقي است که بعضي وقتها city block distance و يا Manhattan distance ناميده مي‌شود.اگر خواستار يافتن راه‌حل‌هاي کوتاه باشيم، به يک تابع کشف‌کننده نياز داريم که هرگز در تعداد مراحل به هدف اغراق نکند. در اينجا ما دو کانديد داريم:h1 = تعداد چهارخانه‌هايي که در مکان‌هاي نادرست هستند. h1 يک کشف‌کننده مجاز است، زيرا واضح است که هر چهارخانه‌اي که خارج از مکان درست باشد حداقل يکبار بايد جابجا شود.فصل چهارم: جستجوي A* - کارآيي A*30

اسلاید 31: اگر مجموعه اي از توابع مثل {h1,h2,h3,…,hn} وجود داشته باشد و هيچ کدام بر ديگري برتري نداشته باشد بين hهاي موجود hاي انتخاب مي شود که بيشتر از همه باشد آنگاه h(n) = max{h1,h2,h3,…,hn} در مثال معماي 8h1 و h2 هر قابل قبول اند و جواب بهينه را مي دهند وh1 < h2h2 کارآتر از h1 است زيرا تعداد گرهاي کمتري را بسط مي دهدفصل چهارم: جستجوي A* - کارآيي A*31

اسلاید 32: هزينه جست و جوفاکتور انشعاب مؤثرميانگين گره هاي بسط يافته در جستجوي عمقي تکرار شوندهIDS و A* و فاکتور انشعاب مؤثر با استفاده از h1 و h2اثر صحت کشف‌کنندگي بر کارايي:فصل چهارم: جستجوي A* - کارآيي A*32

اسلاید 33: w = 0  Uniform Cost Searchw = 1/2  A*w = 1  Greedy Searchتابع ارزياب وزن دار:fw(n) = (1–w) g(n) + w h(n)فصل چهارم: جستجوي A* - ادامه33

اسلاید 34: تابع هيورستيکي خوب است که:اولاً: صحيح عمل کند يعني قابل قبول باشدثانياً: کارآيي نيز داشته باشد گره کمتري را بسط دهد يعني هزينه جستجو بالا نرود و زمان جستجو کم باشدزمان محاسبه يکي از نقص هاي اصلي A* نيست، از آنجاييکه اين جستجو تمام گره هاي توليد شده را در حافظه ذخيره مي کند، معمولاً قبل از اينکه دچار کمبود زمان شود دچار کمبود حافظه مي شودفصل چهارم: جستجوي A* - ادامه34

اسلاید 35: 1-3-1- جستجوي اول بهترين بازگشتي - RBFS ساده ترين راه براي کاهش حافظه مورد نياز A* استفاده از الگوريتم عمقي تکرار شونده در زمينه جست و جوي اکتشافي است.Iterative Deepening A*فصل چهارم: جستجوي IDA* 351-3- جستجوي IDA*به دو دسته تقسيم مي شوند :1-3-2- جستجوي A* با حافظه محدود شده – SMA*

اسلاید 36: 36فصل چهارم: جستجوي IDA* - ادامه در جستجوي IDA* مقدار برش مورد استفاده، عمق نيست بلکه هزينه f(g+h) است. در هر تکرار، مقدار برش کمترين هزينه f هر گره اي است که از مقدار برش تکرار قبلي بيشتر باشد. در جستجوي IDA* بسط منطقي گره ها، جستجوي عمقي تکرار شونده است و در اين استراتژي به جاي محدوديت عمق در IDS، از محدوديت f-cost استفاده مي کند.در اين الگوريتم هر تکرار يک جستجوي عمقي است

اسلاید 37: الگوريتم IDA* در هر بار تکرار گره هايي که f-cost آنها از f-limit کمتر است گسترش داده مي شود مقدار اوليه f-limit مقدار f-cost ريشه مي باشد در تکرار اول تمام گره هايي که مقدار f آنها کمتر از f-limit است گسترش مي يابد در صورتي که هدف پيدا شد کار تمام است در غير اينصورت مقدار f-limit برابر با کمترين مقدار f-cost بين برگ ها مي شود و الگوريتم دوباره با اين مقدار جديد f-limit آغاز مي شود اين تکرارها آنقدر ادامه مي يابد تا زمانيکه مقدار f-limit بگونه اي باشد که گره هدف نيز براي گسترش انتخاب شودفصل چهارم: جستجوي IDA* - ادامه37

اسلاید 38: IDA* :283164750+4283164 752831 47651+51+3283 147652 3184765283147652+32+42+3تکرار اولf-Limit = 4f-Limit = 5فصل چهارم: جستجوي IDA* - مثال38

اسلاید 39: 283164750+4283164 752831 47651+51+3283 147652 31847652+3 832147653+32+3283714 653+4 231847653+2123 847654+11238 47655+0goal !IDA* :تکرار دومf-Limit = 5فصل چهارم: جستجوي IDA* - مثال39

اسلاید 40: بخاطر اينکه در هر مرحله فقط گره هايي که f(n) آنها کمتر از f-limit است در حافظه نگهداري مي شود به همين دليل از نظر پيچيدگي حافظه مثل جستجوي عمقي O(bd) است. البته در بدترين حالت O(bf*/) است که  کمترين هزينه عملگر استIDA* مثل A* کامل و بهينه است. پيچيدگي زماني IDA* به تعداد مقادير مختلفي که تابع هيورستيک مي تواند بگيرد (تعداد باري که مقدار f در طول مسير تغيير يافته است) بستگي دارد. اگر تعداد تکرارها زياد نباشد از نظر کارآيي مثل A* است.فصل چهارم: جستجوي IDA* - ادامه40

اسلاید 41: متأسفانه IDA* در دامنه هاي پيچيده تر با مشکل روبرو مي شودبه عنوان مثال :در مسئله فروشنده دوره گرد مقدار کشف کنندگي براي هر حالت فرق مي کند. بدين معناست که هر ناحيه شامل يک حالت بيشتر از حالت قبلي است اگر A* ، N گره را بسط دهد .IDA* بايد N تکرار را انجام دهد بنابراين N2 مطمئناً زمان زيادي براي انتظار است1 + 2 + 3 + … + N = N2فصل چهارم: جستجوي IDA* - مثال41

اسلاید 42: 1-3-1- جستجوي اول بهترين بازگشتي RBFSجستجوي اول بهترين را با فضاي خطي تقليد مي کند.ساختار آن شبيه جست و جوي عمقي بازگشتي است به جاي اينکه دائما به طرف پايين مسير حرکت کند: بازگشت را با نگهداري جريان f-cost بهترين مسير جايگزين از هر جد گره فعلي محدود مي نمايد. در صورتي که گره جاري از اين مقدار بيشتر شود، بازگشت به مسير جايگزين برمي گردد. بدين صورت حرکت به عقب f-cost گره جاري را با بهترين هزينه زير درخت ها جايگزين مي کند.فصل چهارم: جستجوي RBFS42Recursive Best-First Search

اسلاید 43: 43فصل چهارم: جستجوي RBFS - ادامهمثال RBFS :

اسلاید 44: 44فصل چهارم: جستجوي RBFS - ادامه

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

اسلاید 46: 1-3-2- جستجوي حافظه محدود ساده SMA* Simplified – Memory – Bounded A*SMA* بهترين برگ را بسط ميدهد تا حافظه پر شود. در ادامه الگوريتم جهت انتخاب گره بعدي، بدون از بين بردن گره هاي قبلي نميتواند گره جديدي اضافه کنداين الگوريتم از تمام حافظه موجود براي جستجو استفاده مي کند، مسلماً وجود حافظه بيشتر کارآيي جستجو را وسعت مي بخشدفصل چهارم: جستجوي SMA*46براي انجام اين امر، يک گره را حذف مي‌کند. گره‌هايي که به اين طريق از صف حذف مي‌شوند، گره‌هاي فراموش‌شده(forgotten nodes) يا گره هاي بدون اميد (unpromise) (با هزينه بالا و قديمي) ناميده مي‌شوند.

اسلاید 47: براي اجتناب از جستجوي مجدد زيردرخت‌هايي که از حافظه حذف شده‌اند، در گره‌هاي اجدادي، اطلاعاتي در مورد کيفيت بهترين مسير در زير درخت فراموش شده، نگهداري مي‌شود.فصل چهارم: جستجوي SMA* - ادامه47مي تواند از تمام حافظه دسترس استفاده کند از حالات تکراري تا جايي که حافظه اجازه مي دهد جلوگيري مي کند هزينه بهترين مسير فراموش شده را در اجداد نگه مي دارد. مسيرهاي بلندتر از صف داراي هزينه  مي باشد.

اسلاید 48: فصل چهارم: جستجوي SMA* - ادامه48SMA* :مثالA12B5G5108f=10+5f=8+5D0K5C5E5H2J0F0I0f=18+0f=20+0F=25+5F=15+5f=24+0f=24+5f=24+0f=16+258103108816پيشرفت جستجوي SMA* با حافظه اي به اندازه 3 گره در فضاي حالت بالا ...

اسلاید 49: فصل چهارم: جستجوي SMA* - ادامه49 مقادير داخل پرانتز مقدار بهترين نسل هاي مابعد فراموش شده را نشان مي دهدA12B5101513D0202518101213(15)∞24(∞)A12A12B510A12B5G5108A12G58H28A12G58I02416A12B5G5108A12B510C51012131515(15)1515(24)24(24)20(24)1520(∞)1513∞ اکنون حافظه پر است G براي بسط و برگي که کم عمق (قديم) ترين و بيشترين هزينه دارد حذف مي کنيم

اسلاید 50: فصل چهارم: جستجوي SMA* - ادامه50

اسلاید 51: اين الگوريتم کامل است اگر حافظه براي ذخيره کم عمق ترين مسير راه حل کافي باشد اين الگوريتم بهينه است و بهترين راه حل را برمي گرداند که بتواند با حافظه موجود مطابقت داشته باشد زماني که حافظه موجود براي درخت جستجو کامل کافي باشد جستجو کارآ بهينه Optimally efficient استفصل چهارم: جستجوي SMA* - ادامه51

اسلاید 52: فصل چهارم: جستجوي اصلاح تکراري (بهينه سازي)الگوريتم هاي بهينه سازی تکراري: Iterative Improvement Algorithmsالگوريتمهاي جستجو که تا به حال مطرح شدند براي پويش سيستماتيک فضاهاي حالت طراحي شده اند اين سيستمي بودن از طريق ذخيره يک يا چند مسير در حافظه و با ثبت جايگزينهاي پويش شده در هر نقطه در طول مسير، حاصل مي شوند. زماني که هدف يافت شد، مسير به آن هدف نيز شامل بر پاسخي براي مسئله استدر بسياري از مسائل مسير تا هدف بي اهميت است. براي مثال، در مسئله هشت وزير آنچه مهم است چيدمان وزيرها در نهايت است نه توالي چيدمان آنها.اين گروه مسائل شامل کاربردهاي بسيار مهمي همانند طراحي مدارات مجتمع، طرح کف، برنامه ريزي کاري، برنامه نويسي خودکار، بهينه سازي شبکه هاي مخابراتي، مسير گزيني متحرک و مديريت پست است.52

اسلاید 53: فصل چهارم: جستجوي اصلاح تکراري - ادامهبر مبناي يک حالت جاري واحد (به جاي چندين مسير) عمل مي کنند و عموماً تنها به حالت همسايگي منتقل مي شوند. داراي دو مزيت کليدي هستند:در اين الگوريتمها براي فضاي حالت مسئله بر اساس تابع ارزياب تعريف شده سطحي رسم مي شود. در اين نمودار ارتفاع هر نقطه از فضاي حالت، مقدار تابع ارزياب در آن حالت را نشان مي دهد. 1. از حافظه بسيار کمي استفاده مي کنند، معمولاً يک مقدار ثابت. 2. مي توانند اغلب راه حلهاي منطقي در فضاي حالت بزرگ يا نامتناهي (پيوسته) را که الگوريتم هاي سيستمي نامناسب هستند، پيدا مي کنند.الگوريتم هاي اصلاح تکراري (جستجوي محلي-Local Search) 53

اسلاید 54: EvaluationCurrentstateState Spaceالگوريتم‌هاي اصلاح تکراري سعي بر يافتن قله‌هايي بر روي سطح حالات دارند، جائي که ارتفاع توسط تابع ارزياب تعريف مي‌شود.فصل چهارم: جستجوي اصلاح تکراري - ادامه54

اسلاید 55: الگوريتمهاي اصلاح تکراري، بلندترين قله در فضاي حالت يعني هدف بهينه را مي يابند اين الگوريتم ها فقط اثر جاري را حفظ مي کنند و توجهي فراتر از همسايگي آن حالت ندارد.اين الگوريتم‌ها به دو گره اصلي تقسيم مي‌شوندالگوريتم‌هاي تپه‌نوردي (Hill-climbing)هميشه سعي بر ساخت تغييراتي دارند که حالت جاري را بهينه کنند2. Simulated annealing بعضي وقتها مي توانند تغييراتي را ايجاد کنند که حداقل بطور موقت، مشکلات را بدتر سازنداين عمل مشابه يافتن نقطه بلند کوه اورست در يک مه غليظ استفصل چهارم: جستجوي اصلاح تکراري - ادامه55

اسلاید 56: فصل چهارم: الگوريتم تپه نوردي الگوريتم‌ تپه‌نوردي (Hill-climbing) الگوريتم‌ جستجوي تپه نوردي شامل حلقه اي است که در جهت افزايش مقدار، پيوسته حرکت مي کند(نسخه تندترين شيب) و زماني متوقف مي شود که به نقطه اوجي برسد که همسايه اي بالاتر نداشته باشد. اين الگوريتم شامل درخت جستجو نيست بنابراين ساختار داده گره فقط شامل رکورد حالت و مقدار ارزيابي آن حالت (Value) مي باشد. الگوريتم تپه نوردي گاهي جستجوي محلي حريصانه نيز ناميده مي شود.زيرا که يک همسايه خوب را بدون فکر براي حرکت بعد انتخاب مي کند 56

اسلاید 57: 57فصل چهارم: الگوريتم تپه نوردي - ادامه

اسلاید 58: 28316475h=4283164 752831 476528316475 h=535283 147652 3184765283147653goal !43 231847652123 8476511238 47650123784 652231847654جستجوي تپه نورديمثالh = تعداد چهارخانه‌هايي که در مکان‌هاي نادرست هستند. معماي 858فصل چهارم: الگوريتم تپه نوردي - ادامه فلات :فرزندان بهتر از والد نیستند

اسلاید 59: اين سياست ساده سه مشکل عمده دارد:(فلات) 1. ماکزيمم محلي 2. فلات 3. لبه تيغتابع ارزيابفصل چهارم: الگوريتم تپه نوردي - ادامه 59

اسلاید 60: يک ماکزيمم محلي، قله‌اي است که پائين‌تر از بلندترين قله درفضاي حالت است. زماني که روي ماکزيمم محلي هستيم، الگوريتم توقف خواهد نمود، اگرچه راه حل نيز ممکن است دور از انتظار نباشد.فرزندان يک گره ماکزيمم محلي ، همگي value کمتر از پدرشان دارند.adcbValue(a) = 4Value(b) = 3Value(c) = 1Value(d) = 21- Local Maxima : فصل چهارم: الگوريتم تپه نوردي - ماکزيمم محلي 60

اسلاید 61: يک فلات يا سطح صاف محوطه‌اي از فضاي حالت است که تابع ارزياب يکنواخت باشد: 1- محل صافي که هيچ خروجي بالا رونده اي يافت نشود.2- يا شانه اي باشد که از آن امکان پيشرفت وجود داشته باشد. جستجوي تپه نوردي ممکن است راهي براي خروج از سطح صاف (فلات) نيابد.adcbValue(a) = 4Value(b) = 4Value(c) = 4Value(d) = 42-Plateaux (Flat): وقتي که بيش از يک فرزند خوب براي انتخاب وجود داشته باشد آنگاه يک اصلاح خوب، الگوريتم بتواند به طور تصادفي از ميان آنها يکي را انتخاب کندفصل چهارم: الگوريتم تپه نوردي - فلات 61

اسلاید 62: تيغه حاصل دنباله حداکثر محلي است که براي الگوريتم حريصانه، پويش آن بسيار دشوار است3-Ridges : تيغه، يک ناحيه در فضاي جستجو است که بالاتر از نواحي اطراف خود باشد اما عبور از آن با حرکتهاي تکي در هيچ جهات امکان پذير نباشدفصل چهارم: الگوريتم تپه نوردي - تيغه 62شبکه حالات (دايره هاي تيره) در حين تپه نوردي از چپ و راست تقويت مي شوند و دنباله اي از حداکثر محلي را توليد مي کنند که بهم متصل نيستند.و هر حداکثر محلي تمامي اعمال موجود بسوي پايين اشاره مي کنند.

اسلاید 63: - تپه نوردي تصادفي موفقيت hill-climbing خيلي به ظاهر فضاي حالت (سطح) بستگي دارد، و در بعضي از مواقع که ماکزيمم‌هاي محلي کمي وجود داشته باشد، تپه‌نوردي با شروع تصادفي خيلي سريع راه‌حل خوبي را پيدا خواهد کرد.جهت برخورد با اين مشکلات :تپه نوردي تصادفي يکي از حرکات در جهت شيب را تصادفي انتخاب مي کند. اين الگوريتم معمولاً سرعت همگرايي بسيار آهسته تري نسبت به تندترين شيب داردفصل چهارم: الگوريتم تپه نوردي تصادفي63

اسلاید 64: تپه نوردي با شروع مجدد تصادفي با احتمال نزديک به يک کامل استاين دليل که احتمالاً يک حالت هدف را به عنوان حالت آغازين توليد خواهد کرد. الگوريتم هاي تپه نوردي گفته شده ناکامل بودند و اغلب در يافتن هدف شکست مي خورند چرا که اغلب گير مي کنند.فصل چهارم: الگوريتم تپه نوردي تصادفي - ادامه64 اين الگوريتم براي مسائلي که تعداد زيادي حالت مابعد(هزاران) داشته باشد خوب است. ولي بسياري از مسائل سخت واقعي که داراي سطحي شبيه جوجه تيغي است. آنگاه در تمام حالات نمي تواند بهتر از زمان نمايي يک راه حل خوب و منطقي را پيدا کند.

اسلاید 65: در الگوريتم تپه نوردي هيچ گاه حرکت رو به پايين ندارد يعني گره اي با هزينه بيشتر را انتخاب نمي کند زيرا تضمين دارد که کامل نيست.- Simulated annealing – باز پخت شبيه سازي شدهفصل چهارم: الگوريتم شبيه سازي حرارت65نسخه اي از تپه نوردي تصادفي است که در برخي از مواقع حرکت رو به پايين نيز دارد و حرکات رو به پايين به راحتي در مراحل اوليه باز پخت قابل قبولند اما در مراحل پاياني به سختي پذيرفته مي شوند حرکت روبه پايين – انتخاب گره بد با احتمال کمتر از يکجستجوي تپه نوردي تصادفیجستجوي بازپخت شبيه سازي شده- هم کامل و هم کارآ مي باشد

اسلاید 66: تغييرنگاه از الگوريتم تپه نوردي به گراديان نزولي (Gradian descent) جهت حداقل سازي هزينهفصل چهارم: الگوريتم شبيه سازي حرارت - ادامه66به عنوان مثال: بردن توپ پينگ پونگ به عمق ترين حفره در سطح ناهموار- ابتدا تکان هاي شديد(درجه بالا) - سپس کاهش شدت تکانها (کاهش دما)اگر حرکت بعدي وضعيت را بهبود بخشد انتخاب مي شود در غير اينصورت، الگوريتم حرکت را با احتمال کمتر از 1 قبول خواهد کرد. اين احتمال بصورت نمايي با ”بد بودن “ حرکت کاهش پيدا مي کند.

اسلاید 67: 67فصل چهارم: الگوريتم شبيه سازي حرارت - ادامه

اسلاید 68: 68فصل چهارم: الگوريتم شبيه سازي حرارت - ادامه

اسلاید 69: 69فصل چهارم: الگوريتم شبيه سازي حرارت - ادامه

اسلاید 70: فصل چهارم: جستجوي پرتو محليجستجوي پرتو محليبه جاي يک حالت، k حالت را نگهداري ميکندحالت اوليه: k حالت تصادفيگام بعد: تمامي مابعدهاي k حالت توليد ميشونداگر يکي از جانشين ها هدف بود، تمام ميشودوگر نه بهترين جانشين( k تا بهترين) را انتخاب کرده، تکرار ميکند70در الگوريتمهاي قبلي تنها نگهداري يک گره در حافظه جهت رفع محدوديت حافظه بسيار افراطي بنظر مي رسد.

اسلاید 71: تفاوت عمده با جستجوي شروع مجدد تصادفيبه جاي انتخاب بهترين k از جانشينها، k جانشين تصادفي را بطوريکه احتمال انتخاب يکي بهتر از مقدارش باشد، انتخاب ميکنددر جست و جوي شروع مجدد تصادفي، هر فرايند مستقل از بقيه اجرا ميشوددر جست و جوي پرتو محلي، اطلاعات مفيدي بين k فرايند موازي مبادله ميشودجستجوي پرتو تصادفيفصل چهارم: جستجوي پرتو محلي - ادامه71

اسلاید 72: فصل چهارم: الگوريتم ژنتيک الگوريتم هاي ژنتيکشکلي از جست و جوي پرتو تصادفي غير قطعيکه حالتهاي جانشين از طريق ترکيب دو حالت والد توليد ميشود72در الگوريتم GA حالات مابعد از طريق ترکيب دو حالت والد به جاي تغيير در حالت واحد توليد مي شوند

اسلاید 73: 73والدين(Parents) فرزندان( Offspring)جمعيت جديد( New Population)جمعيت اوليه( Initial Population)انتخاب ( Selection)کروسور(Crossover)جهش (Mutation)جايگزينی جمعيت جديدبجای جمعيت قبلیفصل چهارم: الگوريتم ژنتيک - ادامه

اسلاید 74: 74ساختار الگوریتم های ژنتیکفصل چهارم: الگوريتم ژنتيک - ادامه مساله تشکیل جمعیت اولیه جستجوی ژنتیکی مدلسازی مساله جواب ارزیابی جمعیت انتخاب والدینبازترکیبیجهشانتخاب فرزندان تست شرط خاتمه

اسلاید 75: 75فصل چهارم: الگوريتم ژنتيک - ادامه شروعجمعيت اوليهارزيابی جوابها آيا جواب مورد نظر حاصل شده؟پايانانتخابکروسوربلهجهشT=T+1T=0خير

اسلاید 76: جمعيت اوليهتابع برازشانتخابهم ريختي-بازترکيبی جهشفصل چهارم: الگوريتم ژنتيک - ادامه 76

اسلاید 77: 77فصل چهارم: الگوريتم ژنتيک - ادامه مدلسازی مساله (بازنمایی)برای اینکه بتوانیم یک مساله را بوسیله الگوریتم های ژنتیک حل کنیم، بایستی آنرا به فرم مخصوص مورد نیاز این الگوریتم ها تبدیل کنیم.در این روند ما بایستی راه حل مورد نیاز مساله را به گونه ای تعریف کنیم که قابل نمایش بوسیله یک کروموزوم باشد. اینکه چه نوع بازنمائی را برای مساله استفاده شود، به شخص طراح و فرم مساله بستگی دارد. چند نمونه از بازنمائی هایی را که معمولاً استفاده می شوند :اعداد صحیحرشته های بیتی هر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم

اسلاید 78: 78فصل چهارم: الگوريتم ژنتيک - ادامه برای اینکه بتوانیم موجودات بهتر را درون جمعیت تشخیص بدهیم بایستی معیاری را تعریف کنیم که بر اساس آن موجودات بهتر را تشخیص دهیم. به این کار، یعنی تعیین میزان خوبی یک موجود، ارزیابی آن موجود می گویند. ارزیابی، اینگونه است که بر حسب اینکه موجود چقدر خوب است یک عدد به آن نسبت می دهیم، این عدد که برای موجودات بهتر بزرگتر (یا کوچکتر) است را شایستگی آن موجود می نامیم.به عنوان مثال در صورتی که به دنبال مینیمم یک تابع هستیم، مقدار شایستگی را می توانیم ورودیهایی که مقادیر تابع برای آنها کمتر است در نظر بگیریم که ورودیهای بهتری هستند.بسته به نوع مساله ما می خواهیم شایستگی را بیشینه و یا کمینه کنیم. ارزیابی حمعیت Fitness

اسلاید 79: 79فصل چهارم: الگوريتم ژنتيک - ادامه انتخاب Selection (انتخاب والدین)سوق دادن جستجو به بخشهايی از فضا که امکان يافتن جوابهای با کیفيت بالاتر وجود دارد.نسل جدیدی از راه حل ها را با انتخاب والدینی که بالاترین Fitness را دارند تولید می کند.والدین : در هر نسل تعدادی از عناصر جمعیت این فرصت را پیدا می کنند که تولید مثل کنند. به این عناصر که از میان جمعیت انتخاب می شوند، والدین می گویند.

اسلاید 80: 80فصل چهارم: الگوريتم ژنتيک - ادامه بازترکيبی (Recombination/Crossover)امکان ترکيب جوابهای جزيی (partial solutions) يافت شده و در نتيجه بدست آوردن جوابهایی با کيفيت بالاتر را فراهم می‏آورد.در جریان عمل بازترکیبی به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.

اسلاید 81: 81فصل چهارم: الگوريتم ژنتيک - ادامه بازترکیبی تک نقطه ای (Single Point Crossover)در این روش یک مکان تصادفی در طول رشته انتخاب می شود و gene ها از این مکان به بعد جابجا می شوند.

اسلاید 82: 82فصل چهارم: الگوريتم ژنتيک - ادامه جهش (mutation)ويژگی تصادفی بودن و امکان فرار از نقاط بهينه محلی را فراهم می‏آورد.برای انجام جهش به این صورت عمل می کنیم:بصورت تصادفی تعدادی از کروموزوم های فرزند را انتخاب می کنیم به صورت تصادفی مقادیر یک یا چند ژن وی را تغییر می دهیم. همچنین در هنگام پیاده سازی به صورت زیر عمل می کنیم:به ازای هر کروموزوم اعمال زیر را انجام می دهیم:یک عدد تصادفی بین صفر و یک تولید می کنیماگر عدد تولید شده کوچکتر از Pm بود، به ازای هر ژن اعمال زیر را انجام می دهیم، در غیر اینصورت از جهش دادن کروموزوم صرف نظر می کنیم یک عدد تصادفی بین صفر و یک تولید می کنیماگر عدد تولید شده کوچکتر از Pg بود، ژن مربوطه را جهش می دهیم

اسلاید 83: 83فصل چهارم: الگوريتم ژنتيک - ادامه جهش بيتی ( Bitwise Mutation)

اسلاید 84: 84فصل چهارم: الگوريتم ژنتيک - ادامه شرط خاتمه الگوریتم چون که الگوریتم های ژنتیک بر پایه تولید و تست می باشند، جواب مساله مشخص نیست و نمی دانیم که کدامیک از جواب های تولید شده جواب بهینه است تا شرط خاتمه را پیدا شدن جواب در جمعیت تعریف کنیم. به همین دلیل، معیارهای دیگری را برای شرط خاتمه در نظر می گیریم:تعداد مشخصی نسل: می توانیم شرط خاتمه را مثلاً 100 دور چرخش حلقه اصلی برنامه قرار دهیم. عدم بهبود در بهترین شایستگی جمعیت در طی چند نسل متوالیواریانس شایستگی جمعیت از یک مقدار مشخصی پائین تر بیاید و یا اینکه در طی چند نسل متوالی مشخص، تغییر نکند.بهترین شایستگی جمعیت از یک حد خاصی کمتر شود.شرایط دیگری نیز می توانیم تعریف کنیم و همچنین می توانیم ترکیبی از موارد فوق را به عنوان شرط خاتمه به کار ببندیم.