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

صفحه 1:


صفحه 2:
فصل چهارم: بستجو ی آگاهان» جستجوي آگاهانه ‎Heuristic |‏ ‎e arc ۳ ۲ ۳ 58 00‏ * اگر بتوان استراتزيهاي قبلي رابه نحوي تكميل كرد بطع قذي ل ا ل ل ل ا ‎Ce a al‏ بكوييم رفتار الكوريتم كوركورانه نيست 7 در جستجوي آگاهلنه اطلاعلتي در رابطه با هزینه رسیدن به هدف در اختیار عامل قرار مي گیرد 5 7 تابعي را معرفي مي کنیم که توضيحاتي در مورد مطلوب بودن يا نبودن بسط گره | ارائه می دهد به نام : ‎Evaluation‏ ‎ ‏0 تابع ارزیاب ‎ 

صفحه 3:
‎OE J) ya)‏ اكيت ‏انواع هاي جستجوي آكاهانه ‎Re eee‏ ا ال ات ‎ ‏0 5 عريصانة ۳ و 3 ‎pee ۳‏ و تست 32520 : 2 يرتو مخابيي. ‏۰ 00 تا تیک 1 

صفحه 4:
فصل ههارم: مستموى اول بهتريت ‎Ras eC eet‏ ۱ ‎SD ete‏ ۱ 1 ee Reed cen Caen ES Re SET RRS he eed rer Pees cee en ep eee هدف: یافتن راه‌حل‌هاي کم‌هزینه است. ۱ 5 این الگوریتم‌ها عموماً از تعدادي معيار تخمين براي هزينه رادحلها ‎sen‏ ا ‎ee‏ بر حداقل کردن آنها دارند. 5 

صفحه 5:
‎eae)‏ ل ‎ ‏5-7 ‏كره كه انتخاب مي شود براساس تابع ارزياب بهترين است ‏> اكر تابع ارزياب درست باشد يس گره حقیقتاً بهترین است ‏عد اكر تابع ارزياب درست نباشد جستجو را يد مي ‎eG]‏ ‎32 ‎ 

صفحه 6:
فصل ههارم: مستجوي 7 مثال: در درخت جستجوي زير به شرطي كه كره © هدف باشد براساس الكوريتم مي مال من 

صفحه 7:
0 Ya. با انتخاب مي کند ‎ent. Renee y ers ets‏ ا ل ‎Cer‏ ‎renee SE‏ 010 ‎Heuristics Function. 8‏ >1: حسي ذهني 3 ‎TERR CIENT eer CEN ny res‏ 9[ پاسخ در اين فضاي کوچک قرار دارد . 3 ۹ 7 

صفحه 8:
فصل ههارم: مستجوی مریصانه -س 2 at SS ‏ا‎ f(n) = h(n) ‏ارزلنترينمسيراز كرد 0 به هدف‎ :5)0( a ere eee Es ۱ av elt at RoC Ca Weert oa Re OMT CT RC ORC CI Areas Cea 1 ed eee ae oa noma RE CR ear etn Toe SE AV 

صفحه 9:
0 2 el RoE Syn Reet nee) h(Goal) = 0 ‏هدف باشد‎ | طرف هدف مثل جستجوي عمقي است . ار را ‎PORT ne gl‏ ۹ ا ا ‎Merah o Bete Ree Re Serer‏ اما كره ها در عمق بيشتر زودتر كسترش يابند و هركز براي امتحان مسير 7 ممکن برنگردد 

صفحه 10:
فصل وهازم: مستموی مريصانه .ده يعني ‎!١‏ نزديك به هدف از (أهاي ©00لاهاي ديكر بيشتر شود و هركز ‎eee reice‏ eer or a (4 Sh Rae ses) ‏بودن:‎ 3) پيچيدگي زماني: در بدترین حالت ‎O(b‏ ی SS ‏ده‎ ۳ aaah 

صفحه 11:
فصل ههارم: مستجوي مريصانه -مند جستجوي حريصافه 

صفحه 12:
فصل ههارم: مستجوى مريصاته -مند جستجوي حريصافه 

صفحه 13:


صفحه 14:
فصل ههارم: مستموى ۱0 1-2- جستجوى ©* 1 و | ۴ جستجوي حریصانه: (0 را به سمت هدف < ‎LC)‏ ‏حداقل مي کند ۹ یت ل ان حداقل مي کند هم بهینه است و هم کاهت) ) 0 ۲ 3 0 * الكوريتم كره اي را بسط مي دهد كه كمترين *ا را داراست 

صفحه 15:
۱ ‏ل‎ clas تابع ارزیاب دیگر: ریت ان ان دا ا سيف ا ا ا ل لت در شروع تولید فضاي پاسخ مساوي یک است و سپس به تدریج کاهش پیدا مي کند ۰ Saal ‏ا ل مبداء محور رشد‎ eer Alera ‏ولى به تدريج فاصله مانده تا هدف 5 بيشتري در تولید 52-0 داشت.‎ 03 

صفحه 16:
فصل ههارم: مستجوی ۸ سر بر جستجوي 08 

صفحه 17:
فصل ههارم: مستجوی ۸ سر بر 

صفحه 18:
دا تلا :*- مثا دوم مثال: معماي 8 هنا 0 © © 008 ۹ ۳ ‏تم در‎ Ave 

صفحه 19:
|01 Walt كن 3 معماي 5 0 3 2 1 5 3 6 9 8 هبو م جه 9 د 5 ۵ ماه ]هه ]| ماه ۵اه 1 8 نياك محم هده 

صفحه 20:
فصل ههاري: مستجوی ۸ ‎FR Jol Obil a 1,4F 215‏ تقریبً تمام كشف کنندگي‌هاي مجاز داراي این ويژگي هستند که در طول هر ا 0 این خاصیت براي كشف كنند كيء خاصیت يكنوايي تيوكاي گفته مي‌شود. ‎1 omeed coe CONC PIT eee ‏ا‎ ‎۱ petted Ces to ene ’ 80 

صفحه 21:
0 Want 1 Or Ca ‏ا‎ ‎ROR COSTE aE Sane eC ee aC ARE ILS اكر 22 فرزند 1 باشد f(n’) = ‏)عتهمم‎ 1)8( , ©0)2( +h(n’) ) يت هزينه كره والد 5 ۰ ۳ از این طریق. مقادیر کمراه کننده اي که ممکن است با یک هیورستیک یکنوا پدیدار ا ا ا ‎RRO‏ ‏يٍ ‎c‏ 4 ي 0 

صفحه 22:
۱ ‏ل‎ clas بهينه بودن ©0 ی ۱ ا ل اال ل ا ل ل * يعني تابع (۳)0 تخمین اضافي نزند. 1 در مثال مسير يابي بين دو شيير ‎bs‏ ‏(0) ميت ولند خط مستقیم بیروو شهر باشد؟ ۷ بله قابل قبول است چون خط مستقیم کوهتاهترین مسیر بين دو شهر است (0)*>!: هزينه ولقعييسيدناز ه به هدفباشد آنكاى: ‎Au) - K*(a) Por dveG O 8‏ < 

صفحه 23:
۱ ‏ل‎ clas با توجه به جستجوي با هزينه يكنواخت كه وابسته به (11)© است وبا شرط اينكه هزينه يك مسير با ادامه مسيرء كاهش بيدا نخواهد كرد. كامل است آنكاه: (۳)۰ + (مه > 0 a) es GP ad es andl) ‏ان دا‎ (0)ط + (م)* < (م)ط +ج+ كك ener rea ean) 

صفحه 24:
۱ ‏ل‎ clas 5 ee ۳ 4 y@h=1 ‏در صورتي (" جواب بهینه را مي دهد‎ 3 3 ‏كه ا قابل قبول باشد‎ h=0 h=0 g(X)+h(X) = 102 g(Y)+h(Y) = 74 ‎w rela‏ ا دلق ‎!found‏ ‎ea ‎ 

صفحه 25:
۱ ‏ل‎ clas اگر *" هزینه هزینه مسیر راه حل (هزینه واقعي مسیر بهینه از شروع تا هدف) عت 00 ‏ا ا ا‎ C I TOS E. (a4) 29 

صفحه 26:
۱ ‏ل‎ clas اگر *" هزینه هزینه مسیر راه حل (هزینه واقعي مسیر بهینه از شروع تا هدف) عت 011000 ‏ا ا‎ Cn) كا ©)*ممكن است تعداد از كره هايي كه 0(38)** است قبل از اينكه كره هدف 1 2 ۰ ۰ فا مرس کند 1۹ bay }) #A(ar ‏سيييية‎ ‎۱ ‏ا‎ teen 

صفحه 27:
۱ ‏ل‎ clas ae ee ES hehe Tee ere ee ree فص مت ل 0 ‎Leos‏ ا ا ا ‎ecg |‏ ل ا ا ا ا ل ل 0 te, ie SO Sree een a eee ee en ose Sea ١ 5 ee 

صفحه 28:
ieee ee ‏رل‎ yan) ‏اثر صحت کشف کنندگي بر كارايي:‎ ‏يك راه براي تشخيص كيفيت كشفكنندكي فاكتور انشعاب مؤثر ط* است‎ b* (CPPevive Crackin Pastor) ‏فاكتور‎ ‎eee ee ORS rr teen bia ere eS ntsc seme) TERN ‏ات رت ل ل‎ CCN PN ER] pec MOR 2 © ‏گره‌هاي 0) را‎ ‏دا ل‎ * معمولاًفاکتور انشعاب ا ا ا نمایش داده مي‌شود. مقدار ثابتي دا "ديك کشف کنندگی خوب طراحی شده. ۳* آن در حدود 1 است. 

صفحه 29:
فصل ههارم: مستجوي ۸ .در منال اكر هدف در عمق 5 باشد 9-6 و تعداد گره هايي ۸۵" بسط داده تا به هدف رسیده برابر 25 باشد ۰ 25 - ل( آنگاه : ARES RIM RCSW AE UN NTRS CEA SCR NE TINy WAC] ‏برابر با 197 است‎ تابع هيورستيکي که ۲" آن به یک نزدیکتر باشد بهتر طراحي شده است 1 ace EO) A TRE IOLA Espero nee ‏تعداد کره كمتري بسط مي دهد.‎ 

صفحه 30:
0 Ya) ‏معماي 8 يکي از مسائل اولیه کشف کنندگي بود.‎ ]9 RENCE can ae carer eae eee ee Fe PPR IRR CPN Pen BRU CRE rs he NV Es Fa CO ۳ ۱۳۳ 7 aa ۳ ی کک شخ ننده مجاز لستپیرا «لضم لسنقه هر چهابخانه‌ليک» خابج از 5 00000 OND ICM AGENT MrT Co آلابپ! < مجموع ذ ولصلچهابفانه‌ها از مکارهاي‌مدفص میمشانناست فاصله‌اي که ما مساب ی م 00 افقي است كه ‎ee CL Ta‏ | صم 5 2 

صفحه 31:
فصل ههارم: مستموى ”در اكر مجموعه اي از توابع مثل [ي12,...,و12,12,12) وجود داشته باشد و هيج و 0 ‎ar Oesas one‏ 0 1 10792 در مثال معماي 8 ‎La‏ ا اا ل ل 00 5 ‎Lo‏ ولع ‎9 ‎0 ‎ ‎ 

صفحه 32:
ل ۱7 ‎DER it Serra Var ACR ETL NIL RGR CT Vy‏ رد و فاکتور اتشعاب موثر با استفاده از 9۳ ۲۵ ‎ 

صفحه 33:
۱ ‏ل‎ clas ‏تابع ارزیاب وزن دار:‎ ‎Dad (Fw) ۷ 7 uw k(a)‏ ان ‎ ‎w=0 ~ Uniform Cost Search ‎w=1/2 ‏بت‎ A* a ‏76 6۵16607 . ب- ۹ ‎ 

صفحه 34:
فصل ههارم: تابع هيورستيكى خوب است كه: ول صحیح عمل کند يعني قابل قبول باشد ا ل ا ا 0 و زمان جستجو كم باشد 

صفحه 35:
فصل ههارم: مستمجوى ۱00 1-8- جستجوى 3000" ۹ | ا ا ا ال 0 تكرار فوندهبدربومبيه حست :و جوى اكتشياقى ابت 0 0 ‏ا ا ا‎ 3 ‏يٍ‎ ‎_RBFS- fen) ‏جستجوي اول بهترین‎ -1-3-1 ۲9۱1۸ - CRW RY Re CLOG ig Wet ences coed 

صفحه 36:
Pree ‏ار‎ NI ee Se re MOU RC dL LOR eI te (0G REE Oe ORR ERC AME Ear ty ce] peer fuel ee eo 0 ا الگوریتم هر تکرار یک جستجوي عمقي است لا در جستجوي 16069 * مقدار برش مورد استفاده. عمق نیست بلکه هزینه ‎ha)‏ است. در هر تکراره مقدار برش کمترین هزینه *! هر گره اي است که ‎١ Se TSEC Boe!‏ > ۱ 

صفحه 37:
فصل ههارم: مستجوی ۰-۰12۸« 0 5 1O® pos ‏لا‎ ‎ero ered ne MP ne EU Scan Er : : 58 000 ‏ا ا‎ 0 ‏اا ا ل ا‎ FORE ‏ل ا ل‎ 00 ‏ا‎ ene ee < 0000 0 ‏این تکرارها آنقدر ادامه می یابد تا زمانیکه مقدار ۸-۷ بگونه اي باشد که گره هدف‎ 7 نيز براي كسترش انتخاب شود 

صفحه 38:
uts-“IDA esoaime 30/440 as © : تکرار اول 0 Soo Tele oe EE AIG 15 ‏دم مه‎ 9 3 4 و اه fLimit = 5 0+6 

صفحه 39:
ر ل زک تكرار دوم ل لت 0 9 3 1 0 9 1 ۳۹۳ «(۹ [ole نياك کی هب 

صفحه 40:
Pree ‏ار‎ ec rece OH COCs es eee dal ‎SIC Se ONES OnE Emm]‏ نظر پيچيدگي حافظه ‎an‏ | ‏البته در بدترين حالت (0)//8 است كه [] كمترين هزينه عملكر است ‏689 مثل8" كاملو بهينه لست ‏م ل 2 تواند بكيرد (تعداد باري كه مقدار *! در طول مسير تغيير يافته است) بستكي ‎SOC NPR can Se CE NS Conte Een‏ 1 ‎> ۱ 

صفحه 41:
فصل ههارم: مستجوى 11(4*-.شض متأسفانه 60068" ل روبرو مي شود ‎ei‏ ا ‎1 CE ee Teen oe ‏می کند. ‎ag ee es Ee CON Fe Wen CT COM CEPR‏ 1 لت ‎aaRY Cin rel rym Cre OC] ‎FER Pe Glee] SOU genie RUST SIO) Od OR OC) ‏۳ ۹ = سل ‎N2 ‎ 

صفحه 42:
فصل ههارم: مستموى 111315 1-83-1- جستجوي اول بهترين بازكشتي 0060-6 ‎Recursive Best-First‏ ST: od | Re goes ‏ا ا‎ PNP ‏ا ل ا‎ es 0 ‏طرق يان سير حركت كزيه‎ لس بازگشت راجا نكهداري جريان ن اس بهترین مسیر جایگزین از هر جد ‎CR eenIe PEL yCs‏ ۳ ‎Pee PaOn cy re ee RCA ISS CaP Sea‏ جایگزین برمي گردد. 620 1 

صفحه 43:
Bree asd dea eee.) Wav) CNC H 

صفحه 44:


صفحه 45:
Bree asd dea eee.) Wav) این جستجو اگر تابع اكتشافي قابل قبولي داشته باشد. بهینه است. بيجيدكي فضابي آن ۳[ 7 گره ها بستگي دارد. ا ل 00 1000* و 0890*089 در معرض افزايش تولني بيجيدكي قرار دارند كه در جست و جوي ‎Dome eI oat ents) ved ne nrene eyed ees‏ 0 ‎Coen‏ ا 0000 1 ‎OC)‏ ا ل بسین‌هر تسکرار ف قط یکعدد را نگهداریمپ ‎Cae ene ar‏ ال ۱ ا 0 ۹ ‎ ‎ 

صفحه 46:
فصل ههارم: مستجوى 51714* 1-3-2- جستجوى حافظه محدود ساده 60009)” ‎OnopliPed — Dewory — Orared 0”‏ این الگوریتم از تعام ‎ree‏ سس« ۱ ‎pe en bel RCE Oana a Se ORT COC)‏ در ادامه الكوريتم جهت انتخاب كره بعدي. بدون از بين بردن كره هاي قبلي تميتواند 00 ‏ا ا ا ا ل ل ‎aS‏ ل ‎Re‏ ‎1 ‏ل‎ LOO a) 

صفحه 47:
۱0 ya Fee Fee cena Pk INCE OEE Ren sane Fen Foes Pe a Se eee San ere ane oe aCe ‏شده. نگهداري مي‌شود.‎ ا ‎ro fC pee nye‏ 0 ال ال ل 0 لا مي باشد. مي تواند از تمام حافظه دسترس استفاده کند ‎bs‏ 9 0 A PaCS PUES PC aT cen Pa 

صفحه 48:
|۱0 ws) -t-) : ۰۵00 ‏مثال‎ هد + ‎o‏ 9 " بيشرفت جستجوي 9009)” با حافظه اي به اندازه 3 كره در فضاي حالت بالا م 

صفحه 49:
|۱0 ws) -t-) - ۳99 ‎VS ۹‏ ۸ اکنون حافظه پر است 0) براي بسط و برگي که کم عمق (قدیم) ترین و ‎ ‎ ‏* مقادیر داخل پرانتز مقدار بهترین نسل هاي مابعد فراموش شده را ذ 

صفحه 50:
put loop if empty(OPEN) return with failure; best — deepest least t leaf in if goal suce 2 = (b st),g(suce) + h(swec)); ted(best), BAC KU P(best) st) allin memory, remove best from OPE! — USED+1 MAX then remove it from its parent insert its parent on OPEN if necessary: ce on OPEN Procedure BACKUP(n) ‏كذ م كز‎ completed and has a parent then ) — least f-cost of all succe 03 ( changed, BAC KU P(pare 

صفحه 51:
|۱0 ws) -t-) SSO aE Cree Ee hE eel er ACCC ive Ree Cn os * این الگوریتم بهینه است و بهترین راه حل را برمي گرداند که بتواند با ا لل ا ‎Rw) far‏ * زماني که حافظه موجود براي درخت جستجو کامل كافي باشد جستجو ‎LO en oka Pern‏ ۹ 

صفحه 52:
فصل ههازم: بستجوی اصلام تکرازی (بهی سازي) ۱ ‎Iterative Improvement‏ ‎PERC On rer peemeee CR‏ عسطانموواه ‎free Te eee‏ 0 يك يا ند مسیر در حافظه و با ثبت جايگزينهاي پویش شده در ‎mee BS ee‏ حاصل مي شوند. زماني که هدف یافت شد « 0000 ا كت 0 ‏ل‎ See eB IESE Se ‏هشت وزیر آنچه مهم است چیدمان وزیرها در نهایت است نه توالی چیدمان آنها.‎ Roce teens ee CHEE ene CSS LEAN SCAG ‏طرح كفء برنامه ريزي كاريء برنامه نويسي خودكارء بهینه سازي شبکه هاي‎ ‏مخابراتي, مسير كزيني متحرك و مديريت يست است.‎ ey 

صفحه 53:
فصل ههارم: جستجوی اصلام تگراري .اس الگوریتم هاي اصلاح تكراري (جستجوي محلي-/50000 ,006 EO Rs ese re eaeene ae ge ‏تنها به حالت همسايگي منتقل مي شون‎ ندین مسیر) عمل مي کنند و عموما . داراي دو مزيت كليدي هستند: 0 ‏ل ل ا‎ ee Lee i cee ‏ا ا‎ at ent ee Pe ‏(بيوسته) را كه الكوريتم هاي سيستمي نامناسب هستند, بياذا مي كدئل‎ 5 1 Cae Po ceo eel Fer ‏ا‎ mean Deen ۳ 1۹ ord es oe ee ee 

صفحه 54:
فصل ههارم: جستجوي اصلام تکراري .اسب الكوريتمهاي اصلاح تكراري ‎Oe et aed‏ روي سطح حالات دارند. جاني که ارتفاع توسط تابع ۱ 

صفحه 55:
فصل ههارم: جستجوي اصلام تکراري .اسب pea Price NT ee Res] at BS Ten CS ce Been PSCC eae Pe ‏ا ا‎ Cea E Ee eeepc eld > این عمل مشابه یافتن نقطه بلند کوه امرست در یک مه غلیظ است ‎re)‏ بتم‌ها به دو گره اصلی نق شوند ‏ال ا للك 2 ا ا ا ا ‎cers‏ ‎Cea ed‏ ‏ي وقتها مي توانت ‏بعضی تغييراتي را ایجاد کنند که حداقل بطور موقت. مشکلات " را بدتر سازند ‎ ‎ 

صفحه 56:
فصل ههارم: انکوریتم تیم نورد الكوريتم ‎TC‏ [۱ on Ie eae ‏ا‎ قدارء بي ته حركت مي ند(نسخه تد ترین شیب) و زماني ۳ ‎Ry ae‏ كه به نقطه اوجى برسد كه همسايه اي بالاتر نداشته باشد. 7 ۱ ا ا ل ا لل ا لت ل ا 2 1101 رکورد حالت و مقدار ارزیابی آن حالت (0۸۳() می باشد. . 

صفحه 57:
فصل ههارت: الكوريتم تيه نوردي .اس ۳ ۳ ۱ function HILL-CLIMBING(problem) returns a solution state inputs: problem, aproblem statie: current, anode next, anode current — MAKE-NODE(INITIAL-STATE[problein]) loop do next a highest-valued successor of current f VALUE{next] < VaLuE[current] then return current next ۱ Figure 414 The hill-climbing search algorithm. 

صفحه 58:
تيه نوردي -اامه فصل ههارم: سكس Sy nC cod Jlio 8 ‏معماي‎ Bo 13 alo ۳۳ 5 0 واه 0 3 1 0 ۳۹ 5 9 د 8ه | لماه زه إه] ماه ]هزه 8 1 8 ۲ ۲ - تعاد چهابفانه‌هاییکه ‎ty SONY‏ ۳[ 13 ۳ 

صفحه 59:
فصل ههارت: الكوريتم تيه نوردي .اس 1. ماكزيمم محلىن 2. فلات 3 ‎a5 a‏ 

صفحه 60:
فصل ههارف: الكوريتم تيه نوزدي - مكزيمم مم ار ۱9۳۳ Feat ‏ا‎ 0 0 ‏ا ال ا ا‎ SECM PRS er ro COP ear فرزندان يك كره ماكزيمم محلي . همكي ىاه كمتر از يدرشان دارند. ف ۵ Orhe(b) = 9 On en 9 @ 

صفحه 61:
فصل ههارم: الكوريتم تيه نوردي - فت ‎(Pla)-2‏ نا 1 canome Pen anes Cn PA pean ere nd tc oe . . 5 ‏ال ب ا‎ 1 ‏یا شانه اي باشد که از آن امکان پیشرفت وجود داشته باشد.‎ 2 eel ee Seek Re eee ace aia eee raha) 2 (ماصه و ‎ene) oe:‏ eae) ec ROP eRe See eee Reese EE Pea Oeste HL OO PE nny ORC ce Cepy Cs INO ١ 

صفحه 62:
فصل ههارت: الكوريتم تيه نوردي -تيفه ‎(nN eet‏ Re eerie rear hY Pe aoe Ie een eg ea ‏بسيار دشوار است‎ EOE eT Toy eared ‏تبه نوردي از جب و راست تقويت‎ مي شوند و دنبلله اي از حداکثر محلي ‎yy‏ 0 مي كنند كه بهم متصل 0 ا 0 ‎re‏ 000000 23200001 Pent Carre Pe ney PC ves IC CaP ES ‏اما عبور از آن با حركتهاي تكي در هیچ جهات امکان پذیر نباشد‎ 

صفحه 63:
Per eee ee) st : ‏جهت بر خورد با این مشکلات‎ - تيه نوردي تصادفي 1۷ ‏ا‎ yee Free reenter NCTE Sear cr On FN eran erry * موفقيت باص الها خيلى به ظاهر فضاى حالت (سطح) بستكى دا Tee pe ere ee See ‏ا ا‎ oe tee aeE شروع تصادفي خيلي سریع راه‌حل خوبي را ييدا خواهد كرد. 

صفحه 64:
00 ee ei) Wa) * الكوريتم هاي تيه نوردي كفته شده ناتامل بودند و اغلب در يافتن هدف شكست ل 0 تيه نوردى با شروع مجدد تصادفى با احتمال نزديك به يك كامل است ‎COA KEOn‏ ا 0 ا ا 0ت 0 ا 0 ا ‎ues RP eae ‏ل ل ل‎ _ 0 ۳ a Rome ea rear ene ORE Coenen TS Oe ‎Pye eee an ie ae ne Se een ary [er een ‏پیدا کند.‎ ‎or ‎ 

صفحه 65:
Eee SL ot 00 5) rer Cour or TI li GC Re ee ‎rd‏ ا ‎a Re a eS‏ م ‎ ‏7 0 2005311100000 نسخه اي از تپه نوردي تصادفي است كه در برخى از مواقع حركت روبه يايين نيز ‎۱۳ eee ee Rete Eee ee Eo) ee Med eee ea ‎ ‎ ‏5 " © جستجوي تبه نوردي تصادفى ‎en‏ ‏جستجوي بازپخت شبیه سازي شده 0 حركت رويه يليين - انتخاب ‎Ce‏ ۳ ‎Cy CEN IEO ECON EINER Bre‏ ؟ 

صفحه 66:
فصل ههارت: الكوريتم شبيه سازى عرارت -ادامه ‎Sener eS Ee ne rae‏ ال ا ل ل ‎ ‏- ابتدا تكان هاي 0011-2 ا وا 1 ‏> تغييرنكاه از الكوريتم تيه نوردي ۱ جهت حداقل سازي هزینه 3 8 آگر حرکت بعدي وضعیت را بهبود بخشد انتخاب مي شود در غیر ۳0 ۳۳ حركت را با احتمال کمتر از 1 قبول خواهد کرد این احتمال ۰ ‎ 

صفحه 67:
فصل مهارم: الكوريتم شبيه سازي عرارت -ادامه function SIMULATED-ANNEALING{ problem, schedule) returns a solution state inputs: problem, a problem schedule, a mapping from time to “temperature” + current, anode next, anode 7, a "temperature" controlling the probability of downward steps current— MAKE-NODE(INITIAL-STATE[problem]} fori 1 to ‏مد‎ 0 T+ schedule(t] if T=Othen return current next —a randomly selected successor of current AE — Vacue{next] - VaLuEfcurrent] ifAE > 0 then current—next else current —next only with probability e*”” Figure 415 The simulated annealing search algorithm. 

صفحه 68:
0000 7 Wa --) + SAs use aa control parameter T + T starts out high and gradually (very slowly) decreases toward 0, Algorithm outline for SA current := a randomly generated state: T= TO * initial temperature TO > forever do if T <= T_end then return current: next := a randomly generated new state: AE = f(next) — f(current); 1 current := next with probability Paz = 7——ary l+e * reduce T by a cooling schedule " * next != current * 7 T =schedule(T): Commonly used cooling schedule —T:=T * alpha where 0 < alpha <1 is a cooling constant 

صفحه 69:
Observations with SA AE positive increase negative decrease positive no change negative decrease + Probability ofthe system is at any particular state depends on the state’s energy (Boltzmann distribution) acceptance probability 

صفحه 70:
PALER ere, Yee) ‏ةك‎ mead ‏در الكوريتمهاى قبلى تنها نكهدارى يك كره در حافظه جهت رفع محدوديت‎ ‏حافظه بسيار افراطى بنظر مى رسد.‎ ‏اليه جاى يك حالت, ؟ا حالت را نكهدارى ميكند‎ > حالت اوليه: ؟ا حالت تصادفى * گام بعد: تمامی مابعدهای 5 حالت تولید میشوند *اگر یکی از جانشین ها هدف بود» تمام میشود "= | Nea eer es Ss aa ١ 

صفحه 71:
فصل ههارم: بستجوی پرتو مصلي .سب 1 1 7 Lave Tse oe RORAPI ‏ل‎ ia 5 ee SO coed Sree ‏ا‎ aa ae ce ees Ce eee بسهتر از مقدایشب اشد لنتخابمیکن ۱ ۱ 

صفحه 72:
فد | USC BCE oN aE INH Peay Ek (UC BPwepyS ETS حالت واحد تولید می شوند شكلي از جست و جوي پرتو تصادفي غیر قطعي که حالتهاي جانشین از طريق تركيب دو حللت والد كد 

صفحه 73:
فصل ههارت: الكوريتم _نتيك -ادامه ول مت اتت) والدین(۳۵۲6۳۲5) رتیت initial Population )aJ,! (Offspring )5)53,5 جمعیت جدید( 8۵۴0۷۵۱۵10۴ علا) 0 Sal 

صفحه 74:
فصل ههارم: 00-7 الكوريتم هاى ‎eee)‏ تست تشکیل جمعیت مساله 1 ال١‎ 

صفحه 75:
شروع 1 كس مم| انتخاب ‎lye Ye]‏ مورد نظر حاصل شده؟ 

صفحه 76:
Cae eye) yan 

صفحه 77:
‎YI:‏ 7 -ادامه بي ۱۳ يراى اينكه بتوانيم يك مساله را بوسيله الگوریتم های ژنتیک حل کنیم: بایستی آنا به فرم مخصوص مورد نیز 0 0 در اين روند ما بایستی راه حل مورد نیازمساله را به گونه ای تعریف کنیم که قابل نمایش بوسیله یک کروموزوم باشد. ‎dee DET he ht oe diese hed‏ ا ا ل بستگی دارد. 9 0 ‎NN‏ ‎\ ERUPT TS Son [VOTE Ck Pen RE ey peed ‎ ‎١‏ اعداد صحيح ۳ 4 ‎ene RRC ED Recc ste sc nats ots ens‏ ‎ 

صفحه 78:
فصل ههارت: الكوريتم _إنتيك -ادامه ارزبابی حمعیت ۴۲۴6۵55 اس تا ‎S Tone lo‏ ا ‎PO Tete ae Teneo es Ce‏ ‎Enero sel‏ FO ‏ا‎ Pee Recor eT RIBS SL we erro ۱ Se MESS oe eoe cao Recent EE Se Sts RCE Tce tec oweL tS) ۹ 7 Lome] pee Se aL PE OO Tee te Coma 5 

صفحه 79:
فصل ههارت: الكوريتم _إنتيك -ادامه نخاب 56161101 (نتخاب والدین) 0 ‏ل‎ Eel Bee ee tL oe DE eee aS 0 نسل جدیدی از راه حل ها را با انتخاب والدینی که بالاترین ۴160655 را دارند تولید می کند. اام 000 17 ‏مال‎ Pe) Caner Cea 

صفحه 80:
فصل ههارت: الكوريتم _إنتيك -ادامه ی ST Romer eee rrerorlem( ‏ل ل‎ Cen] 0 kee Tete d Rett eet aaa else ie eee Tek Se wees) tr Se ‏این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و‎ bs sree eR eR ee ee vac | ‏ال‎ a Teee me Le wen Riser ere ee a See hee eee ed 

صفحه 81:
فصل ههارم: الكوريتم نتيك - اداه دراين روش .يك مكان تصادفى در طول رشته انتخاب مى شود و ©13 © ها از اين مكان به بعد جابجا مى cut \eut ۳ 0 0 ۵0 0 0 ۴ 1110000 0001111 oftspring Si 

صفحه 82:
فصل ههارم: الگوریتم آنتیک - انامه ‎La cela) eee‏ ليا PSS Te en EBB bee a Reed tees 2) برای انجام جهش به این صورت عمل می کنیم: بصورت تصادفی تعدادی از کروموزوم های فرزند را انتخاب می کنیم به صورت تصادفی مقادیر یک یا چند ژن وی را ‎al‏ سينا همجنين در هنكام بياده سازى به صورت زير عمل مى كنيم: به ازای هر کروموزوم اعمال زیر را انجام می دهیم: ~ 9 ی 5 ‎mee ne eee)‏ ۱ ۷ به ازاى هر زن اعمال زير را انجام مى دهيم. در غير اينصورت از جهش دادن كروموزوم صرف نظر مى كنيم 0 یک عدد تصادفی بین صفر و یک تولید می کنیم 3 1 

صفحه 83:
فصل ههارم: الكوريتم نتيك - اداه 6۲۵۲۶ ۱1 1 1 1 1 1 1 after 1110111 mutated bit 

صفحه 84:
فصل ههارت: الكوريتم _إنتيك -ادامه شرط خاتمه الكوريتم 7 . جواب مساله مشخص نیست و نمی دانیم که ‎Ee ae ere eke oe ec‏ ا 0 همین دلیل. معیارهای دیگری را برای شرط خاتمه در نظر می گیریم: ۱ تعداد مشخصی نسل: می توانیم شرط خاتمه را مثلاً ۱۰۰ دور چرخش حلقه اصلی برنامه قرار دهیم. FP ene Cee Beene re re coe Re peony re end واريلنس شايستكى جمعيت ازنيك مقدار مشخصى بائين .تر بيليد وديا اينكه در طى جند تسل متوللى مشخص: ۳۳۹ 3 ۴ بهترین شایستگی جمعیت از یک حد خاصی کمتر شود. ۲ شرایط دیگری نیز می توانیم تعریف کنیم و همچنین می توانیم ترکیبی از موارد فوق را به عنوان شرط خات ربه کار ببندیم. 

Alireza yousefpour yousefpour@shomal.ac.ir 1 فصل چهارم :جستجوي آگاهانه جستجوي آگاهانه ‏Heuristic يا جستجوي مکاشفه اي ‏Search فضاي اگر بتوان استراتژيهاي قبلي را به نحوي تکميل کرد بطوري که جستجو بسيار کوچکتر از آنچه که هست ،گردد در اين صورت مي توانيم بگوييم رفتار الگوريتم کورکورانه نيست در جستجوي آگاهانه اطالعاتي در رابطه با هزينه رسيدن به هدف در اختيار عامل قرار مي گيرد تابعي را معرفي مي کنيم که توضيحاتي در مورد مطلوب بودن يا نبودن بسط گره ارائه مي دهد به نام : 2 تابع ارزياب ‏Evaluation فصل چهارم :استراتژيهاي جستجوي آگاهانه انواع هاي جستجوي آگاهانه .1جستجوي اول بهترين حريصانه ‏ *A *IDA  • RBFS • *SMA 3 .2جستجوي محلي و بهينه سازي تپه نوردي شبيه سازي annealing پرتو محلي الگوريتمهاي ژنتيک فصل چهارم :جستجوي اول بهترين -1جستجوي اول بهترين ‏Best -First Search اين استراتژي به اين صورت بيان مي‌شود که در يک درخت ،گره ها توسط تابع ارزياب ارزيابي شده ،سپس گره‌ها مرتب مي‌شوند و در نتيجه گره‌اي که بهترين ارزيابي را داشته باشد ،ابتدا بسط داده مي‌شود هدف: يافتن راه‌حل‌هاي کم‌هزينه است، اي ن الگوريتم‌ه ا عموماً از تعدادي معيار تخمي ن براي هزين ه راه‌حل‌ه ا ي‌کنند و سعي بر حداقل کردن آنها دارند. استفاده م ‌ 4 فصل چهارم :جستجوي اول بهترين -ادامه نکته : گره که انتخاب مي شود براساس تابع ارزياب بهترين است اگر تابع ارزياب درست باشد پس گره حقيقتًا بهترين است ولي اگر تابع ارزياب درست نباشد جستجو را گمراه مي کند 5 فصل چهارم :جستجوي اول بهترين مثال: -مثال در درخت جستجوي زير به شرطي که گره Oهدف باشد براساس الگوريتم جستجوي Best Firstترتيب رويت گره ها کدام است؟ ‏A 4 C 5 D 4 I 6 ‏F(B) B =3 4 H ‏T ‏S ‏R 3 3 1 ‏Q 2 2 G ‏P 3 ‏O 0 5 F ‏N 4 ‏M 3 6 E ‏L 2 ‏J ‏K 3 3 فصل چهارم :جستجوي حريصانه -1-1جستجوي حريصانه ‏Greedy Search حداقل هزينه ي تخمين زده شده براي رسيدن به هدف را انتخاب مي کند در اين روش نزديکترين گره به هدف براي بسط انتخاب مي شود که اين هزينه توسط تابع ارزيابي تخمين زده مي شود به نام : ‏h : hحسي ،ذهني ‏Heuristics Function هدف hاي8ن اس8ت ک8ه فضاي جس8تجو را کوچ8ک کن8د در حال8ي ک8ه تضمي8ن م8ي کند پاسخ در اين فضاي کوچک قرار دارد . 7 فصل چهارم :جستجوي حريصانه -ادامه در جستجوي حريصانه ارزيابي هر گره برابر است با : )f(n) = h(n ) :h(nارزا8نت88ري8نم8سير از گ88ره n 8ب888ه هدف. مثال : محاسبه h -براي طي مسير بين دو شهر ارزان ترين مسير مي تواند کوتاهترين مسير باشد. مسئله معماي : 8 :h1تعداد خانه هايي که در مکان هاي نا درست قرار دارند :h2مجموع فاصله خانه هاي نادرست تا مکان هاي صحيح شان. 8 فصل چهارم :جستجوي حريصانه -ادامه نکته h  :هر تابعي مي تواند باشد فقط الزم است h(n)=0اگر nگره هدف باشد ‏h(Goal) = 0 جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف مثل جستجوي عمقي است . معيارهاي ارزيابي استراتژي جستجوي حريصانه: )1کامل بودن: 9 در بدترين حالت hممکن است هدف در عمق dباشد اما گره ها در عمق بيشتر زودتر گسترش يابند و هرگز براي امتحان مسير ها ممکن بر نگردد فصل چهارم :جستجوي حريصانه -ادامه يعن ي hنزدي ک ب ه هدف از hهاي Nodeهاي ديگ ر بيشت ر شود و هرگز نشودکامل نيست، انتخابپس )2 بودن: بهينه بهينه نيست زيرا توجهي به ) g(nندارد. )3پيچيدگ5ي زماني: در بدترين حالت ‏O(b )4پيچيدگ5ي مکاني: در بدترين حالت ) )O(bm 10 ‏m ميزان کاهش پيچيدگي ،به مسئله و کيفيت تابع hبستگي دارد. فصل چهارم :جستجوي حريصانه -مثال جستجوي حريصانه مثال ‏A 1 3 ‏C 1 2 ‏G 3 3 11 ‏F 1 2 ‏M 2 3 1 ‏Z ‏Y ‏X ‏W 1 2 0 1 1 2 1 3 2 1 ‏N ‏O 1 ‏g=3 ‏E 2 1 3 ‏L 1 ‏D 3 ‏J ‏K 0 ‏B ‏h(B)=1 3 2 3 ‏V ‏U ‏T 2 1 1 5 1 3 1 ‏I3 2 3 ‏S ‏R ‏Q 2 2 1 2 ‏H 3 2 ‏P 3 فصل چهارم :جستجوي حريصانه -مثال جستجوي حريصانه مثال ‏A 1 3 ‏C 1 2 ‏G 3 3 12 ‏F 1 ‏M2 2 3 1 1 2 1 3 2 1 ‏N ‏O 1 ‏g=3 ‏E 2 1 ‏L3 ‏K 2 3 0 ‏B ‏h(B)=1 1 ‏D 3 5 3 1 ‏J 2 3 ‏I3 3 1 2H 3 2 ‏Z ‏Y ‏X ‏W ‏V ‏U ‏T ‏S ‏R ‏Q 1 2 0 1 2 1 1 2 2 1 ‏P 3 فصل چهارم :جستجوي حريصانه -مثال جستجوي حريصانه مثال ‏A 1 3 ‏C 1 2 ‏G 3 3 13 ‏F 2 1 1 ‏N ‏O 1 ‏M2 2 3 1 ‏Z ‏Y ‏X 1 2 0 1 ‏g=3 1 3 ‏E 2 1 ‏L3 2 ‏K 3 0 2 ‏B ‏h(B)=1 1 ‏D 3 5 3 1 ‏J 2 3 ‏I3 3 مسير پاسخ =7 T ‏Wهزينه ‏U ‏V ولي 2 2 1 1 2 1 هزينه پاسخ بهينه = 4 ‏S ‏R 1 2H 3 2 ‏Q 1 ‏P 3 فصل چهارم :جستجوي A -1-2جستجوي A * * حداقل‌سازي مجموع هزينه مسير = )f(n جستجوي حريصانه h(n) :را به سمت هدف نه بهينه بود و نه کامل)h(n حداقل مي کند جستجو با هزينه يکنواخت g(n) :يا هزينه مسير را = )f(n هم بهينه است و هم کامل حداقل مي کند )g(n الگوريتم A 14 * )f(n) = g(n) + h(n الگوريتم گره اي را بسط مي دهد که کمترين fرا داراست فصل چهارم :جستجوي A * -ادامه تابع ارزياب ديگر: )f(n) =  g(n) + (1-) h(n ‏ : 10  :از سمت يک به سمت صفر کاهش پيدا مي کند در شروع توليد فضاي پاسخ مساوي يک است و سپس به تدريج کاهش پيدا مي کند ‏هنگام توليد گراف فاصله طي شده از مبداء محور رشد گراف است ولي به تدريج فاصله مانده تا هدف تاثير بيشتري در توليد گراف خواهد داشت. 15 فصل چهارم :جستجوي A جستجوي A * فضاي حالت 2 2 ‏A 2 1 ‏B 1 1 1 2 ‏D 1 مثال 1 1 5 ‏G2 0 ‏S 4 5 ‏C 3 16 * -مثال اول 4 ‏G1 0 5 7 8 9 ‏E 6 فصل چهارم :جستجوي A ‏S 4 2 5 ‏A 2 ‏C ‏f=5+ 3 3 3+1 B 1 ‏S 5 17 5+ 5 ‏C 3 ‏f* = f =6+0=6 ‏ ‏E 10+6 6 4 1 1 4+ 3 2 ‏f=2+ 2 8 1 2 * -مثال اول 4+1 D 1 6+ G2 0 0 ‏G1 7+0 0 5 9+ G1 0 0 درخت جستجوي با استفاده از جستجوي A * فصل چهارم :جستجوي A مثال: * -مثال دوم معماي 8 ‏Goal State 3 2 4 5 6 ‏Start State 1 3 8 2 8 4 6 1 7 5 7 ‌هاي = hت888عداد چ8ه8ار8خان8ه‌هاي8يک88ه در م8کان ن88ادر8س8تهستند. 18 فصل چهارم :جستجوي A جستجوي A مثال معماي 8 3 8 2 4 6 1 7 5 3 8 2 3 4 6 1 4 5 7 8 2 3 4 1 4 8 6 7 5 6 3 2 3 2 4 8 1 4 8 1 5 6 7 5 6 7 3 2 1 3 2 1 4 8 7 4 8 5 6 5 6 3 5 19 * * 1+5 5 2+4 3+4 5+2 8 6 مثال دوم = hت888عداد چ8ه8ار8خان8ه‌هاي8يک88ه ‌هاين88ادر8س8ته8ستند. در م8کان 0+4 2 3 8 2 1 4 6 1 5 7 2 3 8 1 4 1 7 5 6 7 1+3 2+3 3+2 4+1 2 7 2+3 3 8 2 3 8 4 1 7 4 1 2 5 6 5 6 7 3 2 4 7 1+5 5 1 8 6 7 3+4 ! GOAL 5+0 3+3 فصل چهارم :جستجوي A * -ادامه نگاهي گذرا به اثبات کامل :*A تقريباً تمام کشف‌کنندگي‌هاي مجاز داراي اي ن ويژگ ي هس تند ک ه در طول ه ر مسيري از ريشه ،هزينه fهرگز کاهش پيدا نمي‌کند. اين خاصيت براي کشف‌کنندگي ،خاصيت يکنوايي ( )monotonicityگفته مي‌شود. خاصيت يکنوايي ()monotonicity در صورتي که hيکي از آن استثناها باشد که يکنوا نيست ،مي توان با ايجاد يک اصالح جزئي آن را يکنوا مي‌کنيم 20 فصل چهارم :جستجوي A * -ادامه هر گره جديدي که توليد مي‌شود ،بايد کنترل کنيم که آيا هزينة fاين گره از هزينه fپدرش کمتر است يا خير .اگر کمتر باشد ،هزينة fپدر به جاي فرزند مي‌نشيند. اگر ’nفرزند nباشد )’f(n’) = max( f(n) , g(n ) )’+h(n هزينه گره فرزند هزينه گره والد از اين طريق ،مقادير گمراه کننده اي که ممکن است با يک هيورستيک يکنوا پديدار شوند حذف مي کنيم .به اين معادل سازي معادله pathmaxناميده مي شود 21 فصل چهارم :جستجوي A * -ادامه بهينه بودن :*A با شرطي بر روي تابع هيورستيک ) h(nبهينه نيز خواهد بود: اين شرط عبارت است از اينکه تابع ) h(nقابل قبول ( )admissiblesباشد • يعني براي هر گره مثل ، nبيشتر از هزينه واقعي مسير تا هدف نباشد. • يعني تابع ) h(nتخمين اضافي نزند. در مثال مسير يابي بين دو شهر ) h(nم يت واند خط م ستقيم ب يندو ش هر ب اشد؟ بله قابل قبول است چون خط مستقيم کوهتاهترين مسير بين دو شهر است ) : h*(nهزي8نه وا8ق8عير8س8يدناز nب8ه هدفب888اشد آن8گاه:8 22 0 ‏for all nS ) h(n)  h*(n فصل چهارم :جستجوي A * -ادامه با توجه به جستجوي با هزينه يکنواخت که وابسته به ) g(nاست و با شرط اينکه هزينه يک مسير با ادامه مسير ،کاهش پيدا نخواهد کرد ،کامل است آنگاه: )f(n) = g(n) + h(n )’f(n’) = g(n’) + h(n’) = g(n) + c + h(n ‏f(n’)  )f(n)g(n) + c + h(n’)  g(n) + h(n 23 ) c + h(n’)  h(nنا برابري مثلثي فصل چهارم :جستجوي A 73 ‏Y h=1 1 ‏h=0 2 ‏X ‏h=100 1 ‏h=0 * -ادامه مثال در صورتي Aجواب بهينه را مي دهد که hقابل قبول باشد * ‏g(X)+h(X) = 102 ‏g(Y)+h(Y) = 74 ‏Optimal path is not !found 24 در مثال فوق hق5اب5لق5بولن55يست فصل چهارم :جستجوي A * -ادامه اگر *fهزينه هزينه مسير راه حل (هزينه واقعي مسير بهينه از شروع تا هدف) تعريف شود مي توان گفت: *A تمام 8گره ها با *f(n) < fرا بسط خواهد داد ‏f 25 * فصل چهارم :جستجوي A * -ادامه اگر *fهزينه هزينه مسير راه حل (هزينه واقعي مسير بهينه از شروع تا هدف) تعريف شود مي توان گفت: *A تمام گره ها با *f(n) < fرا بسط خواهد داد *A ممکن است تعداد از گره هايي که *f(n)=fاست قبل از اينکه گره هدف انتخاب شود بسط دهد *A تمام گره ها با *f(n)>fرا بسط نخواهد داد. يعني الگوريتم * Aقادر است گره هاي بدل را بدون امتحان حذف يا هرس کند. فصل چهارم :جستجوي A * -ادامه بول از ن ظر ب هينگيک ارآ م يب اشد. موثري رايهر ت اب ع hق اب لق ، ب *Aب ه ط ور (کارآ بهينه )Optimally effecientيعني هيچ الگوريتم بهينه اي که جستجو * را از ريشه شروع مي کند ،تضمين نمي کند تعداد گره هاي کمتري نسبت به A ايجاد کند و در زماني که تابع هيورستيک بکار رفته در تمام الگوريتمها يکسان باشد. يک الگوريتم ممکن است که راه حل بهينه را در صورتي که همه گره ها با *f(n)<fبسط ندهد ،گم کند. 27 فصل چهارم :جستجوي A * -کارآيي A * اثر صحت کشف‌کنندگي بر کارايي: يک راه براي تشخيص کيفيت کشف‌کنندگي فاکتور انشعاب مؤثر *bاست فاکتور انشعاب مؤثر )b* (Effective Branching Factor تعداد گره‌هاي بسط داده شده توسط *Aبراي يک مسئله ويژه Nباشد و عمق راه حل ،dسپس *bفاکتور انشعابي است که يک درخت يکنواخت با عمق dخواهد داشت تا گره‌هاي Nرا نگهدارد. بنابراين: ‏b*+( b*) …+( b*) = N +1 ‏d 2 معموالً فاکتور انشعاب مؤثر که توسط کشف‌کنندگي نمايش داده مي‌شود ،مقدار ثابتي دارد. 28 يک کشف‌کنندگي خوب طراحي شده *b ،آن در حدود 1است. فصل چهارم :جستجوي A * -کارآيي A * مثال ‏d=5 اگر هدف در عمق 5باشد و تعداد گره هايي *Aبسط داده تا به هدف رسيده برابر 25باشد آنگاه : ‏N = 25 ‏b* = 1.91 يعن8ي متوس8ط تعداد گره هاي8ي ک8ه در ه8ر س8طر بس8ط م8ي ده8د ت8ا ب8ه هدف برسد برابر با 1.91است تابع هيورستيکي که *bآن به يک نزديکتر باشد بهتر طراحي شده است يعني بين توابع hآن تابعي که *bآن به يک نزديکتر است مناسبتر است زيرا تعداد گره کمتري بسط مي دهد. 29 فصل چهارم :جستجوي A * -کارآيي A * معماي 8يکي از مسائل اوليه کشف‌کنندگي بود. اگر خواستار يافتن راه‌حل‌هاي کوتاه باشيم ،به يک تابع کشف‌کننده نياز داريم که هرگز در تعداد مراحل به هدف اغراق نکند .در اينجا ما دو کانديد داريم: ‌هاين88ادر8س8تهستند. = h1ت888عداد چ8ه8ار8خان8ه‌هاي8يک88ه در م8کان 8س8تز8يرا وا8ض8ح ا8س8تک88ه هر چ8ه8ار8خان‌ 8ها8يک88ه خ8ار8ج از ‌ک88ننده 8م8جاز ا ، h1ي88کک88شف م8کاندر8س8تب888اشد ح8دا8ق8لي88کبار ب888ايد ج8اب8جا ش88ود. 8ت ‌هايهدفص88حيحشانا8س . = h2م8جموع ف88وا8ص8لچ8ه8ار8خان8ه‌ها از م8کان فاص8له‌اي ک8ه م8ا حس8اب مي‌کني8م ،مجموع فواص8ل عمودي و افق8ي اس8ت ک8ه بعضي وقتها city block distanceو يا Manhattan distanceناميده مي‌شود. 30 فصل چهارم :جستجوي A * -کارآيي A * اگر مجموعه اي از توابع مثل { }h1,h2,h3,…,hnوجود داشته باشد و هيچ کدام بر ديگري برتري نداشته باشد بين hهاي موجود hاي انتخاب مي شود که بيشتر از همه باشد آنگاه }h(n) = max{h1,h2,h3,…,hn در مثال معماي 8 h1و h2هر ق8اب8لق88بولا8ند و ج8وا8بب888هينه را م8يد8هند و 31 h2ک88ارآتر از h1ا8س8تز8يرا8 تعداد گرهاي کمتري را بسط مي دهد ‏h1 < h2 فصل چهارم :جستجوي A * -کارآيي A * اثر صحت کشف‌کنندگي بر کارايي: فاکتور انشعاب مؤثر هزينه جست و جو ميانگين گره هاي بسط يافته در جستجوي عمقي تکرار شونده IDSو *A 32 و فاکتور انشعاب مؤثر با استفاده از h1و h2  ادامه- * A جستجوي:فصل چهارم :تابع ارزياب وزن دار fw(n) = (1–w) g(n) + w h(n) w=0  w = 1/2  w=1  Uniform Cost Search A* Greedy Search 33 فصل چهارم :جستجوي A * -ادامه تابع هيورستيکي خوب است که: يعني قابل قبول باشد اوالً :صحيح عمل کند ثانياً :کارآيي نيز داشته باشد گره کمتري را بسط دهد يعني هزينه جستجو باال نرود و زمان جستجو کم باشد زمان محاسبه يکي از نقص هاي اصلي *Aنيست، از آنجاييکه اين جستجو تمام گره هاي توليد شده را در حافظه ذخيره مي کند، معموالً قبل از اينکه دچار کمبود زمان شود دچار کمبود حافظه مي شود 34 فصل چهارم :جستجوي IDA * ‏Iterative Deepening *A -1-3جستجوي IDA ‏ساده ترين راه براي کاهش حافظه مورد نياز *Aاستفاده از الگوريتم عمقي تکرار شونده در زمينه جست و جوي اکتشافي است. به دو دسته تقسيم مي شوند : -1-3-1جستجوي اول بهترين 5بازگشتي RBFS - -1-3-2جستجوي *A 5با حافظه محدود شده – *SMA 35 فصل چهارم :جستجوي IDA * -ادامه در جستجوي *IDAبسط منطقي گره ها ،جستجوي عمقي تکرار شونده است و در اين استراتژي به جاي محدوديت عمق در ،IDSاز محدوديت f- costاستفاده مي کند. در اين الگوريتم هر تکرار يک جستجوي عمقي است در جستجوي *IDAمقدار برش مورد استفاده ،عمق نيست بلکه هزينه ) f(g+hاست .در هر تکرار ،مقدار برش کمترين هزينه fهر گره اي است که از مقدار برش تکرار قبلي بيشتر باشد. 36 فصل چهارم :جستجوي IDA الگوريتم IDA * -ادامه * در هر بار تکرار گره هايي که f-costآنها از f-limitکمتر است گسترش داده مي شود مقدار اوليه f-limitمقدار f-costريشه مي باشد در تکرار اول تمام گره هايي که مقدار fآنها کمتر از f-limitاست گسترش مي يابد در صورتي که هدف پيدا شد کار تمام است در غير اينصورت مقدار f-limitبرابر با کمترين مقدار f-costبين برگ ها مي شود و الگوريتم دوباره با اين مقدار جديد f-limitآغاز مي شود اين تکرارها آنقدر ادامه مي يابد تا زمانيکه مقدار f-limitبگونه اي باشد که گره هدف نيز براي گسترش انتخاب شود 37 فصل چهارم :جستجوي IDA * -مثال : *IDA تکرار اول 3 2 8 4 1 6 7 5 0+4 ‏f-Limit = 4 3 8 4 5 3 5 38 6 8 2 3 4 1 4 8 6 7 5 6 2+4 2 3 8 2 1 4 6 1 5 7 2 3 8 1 4 1 7 5 6 7 1+3 2+3 ‏f-Limit = 5 1+5 2 7 2+3 فصل چهارم :جستجوي IDA : *IDA تکرار دوم ‏f-Limit = 5 3 2 8 4 1 6 5 3 7 8 0+4 2 3 8 2 1 4 6 1 5 7 2 3 8 4 8 1 4 1 5 6 7 5 6 3 2 4 8 1 5 6 7 3 2 1 4 8 5 6 4 5 6 3 39 * -مثال 7 1+3 2+3 3+2 2 7 2+3 3 8 2 3 8 4 1 7 4 1 2 5 6 5 6 7 3 2 4 4+1 7 1+5 5 1 8 6 7 3+4 ! GOAL 5+0 3+3 فصل چهارم :جستجوي IDA * -ادامه بخاطر اينکه در هر مرحله فقط گره هايي که ) f(nآنها کمتر از f-limit است در حافظه نگهداري مي شود به همين دليل از نظر پيچيدگي حافظه مثل جستجوي عمقي ) O(bdاست. البته در بدترين حالت ) O(bf*/است که کمترين هزينه عملگر است است *IDAم ثل *Aک ام لو ب هينه . پيچيدگي زماني *IDAبه تعداد مقادير مختلفي که تابع هيورستيک مي تواند بگيرد (تعداد باري که مقدار fدر طول مسير تغيير يافته است) بستگي دارد .اگر تعداد تکرارها زياد نباشد از نظر کارآيي مثل *Aاست. 40 فصل چهارم :جستجوي IDA * -مثال متأسفانه *IDAدر دامنه هاي پيچيده تر با مشکل روبرو مي شود به عنوان مثال : در مسئله فروشنده دوره گرد مقدار کشف کنندگي براي هر حالت فرق مي کند. بدين معناست که هر ناحيه شامل يک حالت بيشتر از حالت قبلي است اگر A* ، Nگره را بسط دهد . *IDAب ايد Nت کرار را ان جام دهد ب نابراين N2م طمئنًا زمانزيادي ب رايان تظار است 41 = 1+2+3+…+N ‏N2 فصل چهارم :جستجوي RBFS -1-3-1جستجوي اول بهترين بازگشتي RBFS ‏Recursive Best-First ‏جستجوي اول بهترين را با فضاي خطي تقليد مي کندSearch . ‏ساختار آن شبيه جست و جوي عمقي بازگشتي است به جاي اينکه دائما به طرف پايين مسير حرکت کند: بازگشت را با نگهداري جريان f-costبهترين مسير جايگزين از هر جد گره فعلي محدود مي نمايد. در ص ورتي ک ه گره جاري از اي ن مقدار بيشت ر شود ،بازگشت ب ه مسير جايگزين برمي گردد. 42 بدين صورت حرکت به عقب f-costگره جاري را با بهترين هزينه زير درخت ها جايگزين مي کند. فصل چهارم :جستجوي RBFS مثال : RBFS 43 -ادامه فصل چهارم :جستجوي RBFS 44 -ادامه فصل چهارم :جستجوي RBFS -ادامه اين جستجو اگر تابع اکتشافي قابل قبولي داشته باشد ،بهينه است. پيچيدگي فضايي آن ) O(bdاست. تعيين پيچيدگي زماني آن به دقت تابع اکتشافي و ميزان تغيير بهترين مسير در اثر بسط گره ها بستگي دارد. استاما گ ره هايزياديت وليد م يکند. RBFSت ا حدياز *IDAک ارآمدتر ، *IDAو RBFSدر معرض افزايش تواني پيچيدگي قرار دارند که در جست و جوي گرافها مرسوم است ،زيرا نميتوانند حالتهاي تکراري را در غير از مسير فعلي بررسي کنند. لذا ،ممکن است يک حالت را چندين بار بررسي کنند. *IDAو RBFSاز ف ضاياندکياستفاده م يکنند ک ه ب ه آن ها آسيبم يرساند*IDA . استو RBFS ب ينهر ت کرار ف قط ي کع دد را ن گهداريم يکند ک ه هزينه ف علي. f اطالعات يشتريدر حافظه ن گهداريم يکند 45ب فصل چهارم :جستجوي SMA * -1-3-2جستجوي حافظه محدود ساده *SMA *Simplified – Memory – Bounded A اين الگوريتم از تمام حافظه موجود براي جستجو استفاده مي کند ،مسلماً وجود حافظه بيشتر کارآيي جستجو را وسعت مي بخشد *SMAب*هتري*نب**رگرا ب سط م يدهد ت ا حافظه پ ر ش ود. در ادامه الگوريتم جهت انتخاب گره بعدي ،بدون از بين بردن گره هاي قبلي نميتواند گره جديدي اضافه کند براي انجام اي ن ام ر ،ي ک گره را حذف مي‌کند .گره‌هاي ي ک ه ب ه اي ن طري ق از ص ف حذف مي‌شوند ،گره‌هاي فراموش‌شده( )forgotten nodesيا گره هاي بدون اميد (( )unpromiseبا هزينه باال و قديمي) ناميده مي‌شوند. 46 فصل چهارم :جستجوي SMA * -ادامه براي اجتناب از جس تجوي مجدد زيردرخت‌هاي ي ک ه از حافظ ه حذف شده‌ان د ،در گره‌هاي اجدادي ،اطالعات ي در مورد کيفي ت بهتري ن مس ير در زي ر درخ ت فراموش شده ،نگهداري مي‌شود. • هزينه بهترين مسير فراموش شده را در اجداد نگه مي دارد. • مسيرهاي بلندتر از صف داراي هزينه مي باشد. مي تواند از تمام حافظه دسترس استفاده کند از حاالت تکراري تا جايي که حافظه اجازه مي دهد جلوگيري مي کند 47 فصل چهارم :جستجوي SMA مثال : *SMA ‏A 12 8 ‏f=8+ 5 16 10 ‏G 5 ‏B 5 8 ‏I 0 10 ‏f=10+ 5 5 ‏D 0 ‏f=16+ H 2 2 3 f=20 8 8 +0 ‏f=24 +0 48 * -ادامه ‏K 5 ‏J 0 ‏f=24 +5 ‏f=24 +0 ‏F 0 ‏f=18+ 0 ‏C 5 ‏F=15+5 10 ‏E 5 ‏F=25+ 5 پيشرفت جستجوي *SMAبا حافظه اي به اندازه 3گره در فضاي حالت باال ... فصل چهارم :جستجوي SMA 8 ‏A 13(15 12 ) 13 G ‏G 5 5 8 ∞ )4 10 (B 20 )∞ 5 10 49 13 12 A 12 A 12 10 12 10 ‏B 5 ‏B 5 15 15  18 Hاکنون حافظه پر است Gبراي بسط و برگي که کم عمق (قديم) ترين و 2 ‏A بيشترين هزينه دارد حذف مي کنيم A ‏A 20(2 12 2 0 8 13 A 12 * -ادامه ‏D 0 15(2 A 4) 10 12 ‏B 5 15 10 ‏C 5 8 ‏G 5 24(2 )4 ∞25 12 15 10 ‏B 5 15 15(15 )8 16 ‏I 0 12 ‏G 5 2 مقادير داخل پرانتز مقدار بهترين نسل هاي مابعد فراموش شده را نشان 4مي دهد (24 )∞ فصل چهارم :جستجوي SMA 50 * -ادامه فصل چهارم :جستجوي SMA * -ادامه اين الگوريتم کامل است اگر حافظه براي ذخيره کم عمق ترين مسير راه حل کافي باشد اين الگوريتم بهينه است و بهترين راه حل را برمي گرداند که بتواند با حافظه موجود مطابقت داشته باشد زماني که حافظه موجود براي درخت جستجو کامل کافي باشد جستجو کارآ بهينه Optimally efficientاست 51 فصل چهارم :جستجوي اصالح تکراري (بهينه سازي) الگوريتم هاي بهينه سازی تکراري: ‏Iterative Improvement ‏Algorithms الگوريتمهاي جستجو که تا به حال مطرح شدند براي پويش سيستماتيک فضاهاي حالت طراحي شده اند اين سيستمي بودن از طريق ذخيره يک يا چند مسير در حافظه و با ثبت جايگزينهاي پويش شده در هر نقطه در طول مسير، حاصل مي شوند .زماني که هدف يافت شد ،مسير به آن هدف نيز شامل بر پاسخي براي مسئله است در بسياري از مسائل مسير تا هدف بي اهميت است .براي مثال ،در مسئله هشت وزير آنچه مهم است چيدمان وزيرها در نهايت است نه توالي چيدمان آنها. 52 اين گروه مسائل شامل کاربردهاي بسيار مهمي همانند طراحي مدارات مجتمع، طرح کف ،برنامه ريزي کاري ،برنامه نويسي خودکار ،بهينه سازي شبکه هاي مخابراتي ،مسير گزيني متحرک و مديريت پست است. فصل چهارم :جستجوي اصالح تکراري -ادامه الگوريتم هاي اصالح تکراري (جستجوي محلي)LOCAL SEARCH- بر مبناي يک حالت جاري واحد (به جاي چندين مسير) عمل مي کنند و عموماً تنها به حالت همسايگي منتقل مي شوند .داراي دو مزيت کليدي هستند: .1از حافظه بسيار کمي اس*تفاده مي کنند ،معموالً يک مقدار ثابت. . 2مي توانند اغلب راه حلهاي منطقي در فضاي حالت بزرگ يا نامتناهي (پيوسته) را که الگوريتم هاي سيستمي نامناسب هستند ،پيدا مي کنند. 53 در اين الگوريتمها براي فضاي حالت مسئله بر اساس تابع ارزياب تعريف شده سطحي رسم مي شود .در اين نمودار ارتفاع هر نقطه از فضاي حالت ،مقدار تابع ارزياب در آن حالت را نشان مي دهد. فصل چهارم :جستجوي اصالح تکراري -ادامه ‏Evaluation الگوريتم‌هاي اصالح تکراري سعي بر يافتن قله‌هايي بر روي سطح حاالت دارند، جائي که ارتفاع توسط تابع ‏Current ‏state ارزياب تعريف مي‌شود. ‏State Space 54 فصل چهارم :جستجوي اصالح تکراري -ادامه ‏الگوريتمهاي اصالح تکراري ،بلندترين قله در فضاي حالت يعني هدف بهينه را مي يابند اين الگوريتم ها فقط اثر جاري را حفظ مي کنند و توجهي فراتر از همسايگي آن حالت ندارد. ‏اين عمل مشابه يافتن نقطه بلند کوه اورست در يک مه غليظ است اين الگوريتم‌ها به دو گره اصلي تقسيم مي‌شوند .1الگوريتم‌هاي تپه‌نوردي ()Hill-climbing هميشه سعي بر ساخت تغييراتي دارند که حالت جاري را بهينه کنند ‏Simulated annealing .2 بعضي وقتها مي توانند تغييراتي را ايجاد کنند که حداقل بطور موقت ،مشکالت 55 را بدتر سازند فصل چهارم :الگوريتم تپه نوردي م تپه‌نوردي ()Hill-climbing الگوريت ‌ الگوريتم‌ جستجوي تپه نوردي شامل حلقه اي است که در جهت افزايش مقدار ،پيوسته حرکت مي کند(نسخه تندترين شيب) و زماني متوقف مي شود که به نقطه اوجي برسد که همسايه اي باالتر نداشته باشد. الگوريتم تپه نوردي گاهي جستجوي محلي حريصانه نيز ناميده مي شود. زيرا که يک همسايه خوب را بدون فکر براي حرکت بعد انتخاب مي کند اين الگوريتم شامل درخت جستجو نيست بنابراين ساختار داده گره فقط شامل 56 رکورد حالت و مقدار ارزيابي آن حالت ( )Valueمي باشد. فصل چهارم :الگوريتم تپه نوردي 57 -ادامه فصل چهارم :الگوريتم تپه نوردي جستجوي تپه نوردي مثال معماي 8 4 6 1 7 5 3 8 2 3 4 6 1 4 5 7 8 2 3 4 1 4 8 6 7 5 6 3 2 3 2 4 8 1 4 8 1 5 6 7 5 6 7 3 2 1 3 2 1 4 8 7 4 8 5 6 5 6 3 5 58 3 8 2 5 5 4 4 2 8 6 ادامه = hت888عداد چ8ه8ار8خان8ه‌هاي8يک88ه ‌هاين88ادر8س8ته8ستند. در م8کان ‏h=4 2 3 8 2 1 4 6 1 5 7 2 3 8 1 4 1 7 5 6 7 3 3 2 7 فالت : 3 فرزندان بهتر از والد نیستند 2 3 2 4 7 ‏h=5 1 5 1 8 6 7 ! GOAL 0 فصل چهارم :الگوريتم تپه نوردي اين سياست ساده سه مشکل عمده دارد: .1ماکزيمم محلي .2فالت -ادامه .3لبه تيغ تابع ارزياب (فالت ) 59 فصل چهارم :الگوريتم تپه نوردي -ماکزيمم محلي : Local Maxima -1 ي ک ماکزيم م محل ي ،قله‌اي اس ت ک ه پائين‌ت ر از بلندتري ن قل ه درفضاي حال ت است .زماني که روي ماکزيمم محلي هستيم ،الگوريتم توقف خواهد نمود ،اگرچه راه حل نيز ممکن است دور از انتظار نباشد. فرزندان يک گره ماکزيمم محلي ،همگي valueکمتر از پدرشان دارند. 60 ‏Value(a) = 4 ‏a ‏Value(b) = 3 ‏Value(c) = 1 ‏Value(d) = 2 ‏c ‏d ‏b فصل چهارم :الگوريتم تپه :Plateaux (Flat)-2 نوردي -فالت يک فالت يا سطح صاف محوطه‌اي از فضاي حالت است که تابع ارزياب يکنواخت باشد: -1محل صافي که هيچ خروجي باال رونده اي يافت نشود. -2يا شانه اي باشد که از آن امکان پيشرفت وجود داشته باشد. جستجوي تپه نوردي ممکن است راهي براي خروج از سطح صاف نيابد. (فالت) ‏Value(a) = 4 ‏a ‏Value(b) = 4 ‏Value(c) = 4 ‏Value(d) = 4 61 ‏d ‏c ‏b وقتي که بيش از يک فرزند خوب براي انتخاب وجود داشته باشد آنگاه يک اصالح خوب ،الگوريتم بتواند به طور تصادفي از ميان آنها يکي را انتخاب کند فصل چهارم :الگوريتم تپه : Ridges-3 نوردي -تيغه تيغه حاصل دنباله حداکثر محلي است که براي الگوريتم حريصانه ،پويش آن بسيار دشوار است 62 • شبکه حاالت (دايره هاي تيره) در حين تپه نوردي از چپ و راست تقويت مي شوند و دنباله اي از حداکثر محلي را تولي د م ي کنن د ک ه به م متصل نيستند. • و ه ر حداکث ر محل ي تمامي اعمال موجود بسوي پايين اشاره مي کنند. تيغه ،يک ناحيه در فضاي جستجو است که باالتر از نواحي اطراف خود باشد اما عبور از آن با حرکتهاي تکي در هيچ جهات امکان پذير نباشد فصل چهارم :الگوريتم تپه نوردي تصادفي جهت برخورد با اين مشکالت : -تپه نوردي تصادفي تپه نوردي تصادفي يکي از حرکات در جهت شيب را تصادفي انتخاب مي کند .اين الگوريتم معموالً سرعت همگرايي بسيار آهسته تري نسبت به تندترين شيب دارد • موفقيت hill-climbingخيلي به ظاهر فضاي حالت (سطح) بستگي دارد، و در بعضي از مواقع که ماکزيمم‌هاي محلي کمي وجود داشته باشد ،تپه‌نوردي با شروع تصادفي خيلي سريع راه‌حل خوبي را پيدا خواهد کرد. 63 فصل چهارم :الگوريتم تپه نوردي تصادفي -ادامه • الگوريتم هاي تپه نوردي گفته شده ناکامل بودند و اغلب در يافتن هدف شکست مي خورند چرا که اغلب گير مي کنند. تپه نوردي با شروع مجدد تصادفي با احتمال نزديک به يک کامل است اين دليل که احتماالً يک حالت هدف را به عنوان حالت آغازين توليد خواهد کرد. اين الگوريتم براي مسائلي که تعداد زيادي حالت مابعد(هزاران) داشته باشد خوب است. ولي بسياري از مسائل سخت واقعي که داراي سطحي شبيه جوجه تيغي است. آنگاه در تمام حاالت نمي تواند بهتر از زمان نمايي يک راه حل خوب و منطقي را پيدا کند. 64 فصل چهارم :الگوريتم شبيه سازي حرارت – Simulated annealing -باز پخت شبيه سازي شده در الگوريتم تپه نوردي هيچ گاه حرکت رو به پايين ندارد يعني گره اي با هزينه بيشتر را انتخاب نمي کند زيرا تضمين دارد که کامل نيست. نسخه اي از تپه نوردي تصادفي است که در برخي از مواقع حرکت رو به پايين نيز دارد و حرکات رو به پايين به راحتي در مراحل اوليه باز پخت قابل قبولند اما در مراحل پاياني به سختي پذيرفته مي شوند oجستجوي تپه نوردي تصادفی oحرک=ت روب=ه پا=يين – انتخاب گره بد با احتمال کمتر ا=ز يک 65 جستجوي بازپخت شبيه سازي شده -هم کامل و هم کارآ مي باشد فصل چهارم :الگوريتم شبيه سازي به عنوان مثال: حرارت -ادامه بردن توپ پينگ پونگ به عمق ترين حفره در سطح ناهموار -ابتدا تکان هاي شديد(درجه باال) -سپس کاهش شدت تکانها (کاهش دما) تغييرنگاه از الگوريت م تپ ه نوردي ب ه گراديان نزولي ()Gradian descent جهت حداقل سازي هزينه اگر حرکت بعدي وضعيت را بهبود بخشد انتخاب مي شود در غير اينصورت، الگوريت م حرک ت را ب ا احتمال کمت ر از 1قبول خواه د کرد .اين احتمال بصورت نمايي با ”بد بودن “ حرکت کاهش پيدا مي کند. 66 فصل چهارم :الگوريتم شبيه سازي 67 حرارت -ادامه فصل چهارم :الگوريتم شبيه سازي 68 حرارت -ادامه فصل چهارم :الگوريتم شبيه سازي 69 حرارت -ادامه فصل چهارم :جستجوي پرتو محلي جستجوي پرتو محلي در الگوريتمهاي قبل2ي تنه2ا نگهداري ي2ک گره در حافظ2ه جه2ت رف2ع محدوديت حافظه بسيار افراطي بنظر مي رسد. ‏به جاي يک حالت k ،حالت را نگهداري ميکند ‏حالت اوليه k :حالت تصادفي ‏گام بعد :تمامي مابعدهاي kحالت توليد ميشوند ‏اگر يکي از جانشين ها هدف بود ،تمام ميشود 70 ‏وگر نه بهترين جانشين( kتا بهترين) را انتخاب کرده ،تکرار ميکند فصل چهارم :جستجوي پرتو محلي -ادامه تفاوت عمده با جستجوي شروع مجدد تصادفي در جست و جوي شروع مجدد تصادفي ،هر فرايند مستقل از بقيه اجرا ميشود ‏در جست و جوي پرتو محلي ،اطالعات مفيدي بين kفرايند موازي مبادله ميشود جستجوي پرتو تصادفي به جاي انتخاب بهترين kاز جانشينها، 2تما2ل2ن2تخابي22کي kج2ان2شينت22صاد2ف2يرا ب22طور2ي2که ا2ح ا ب22هتر از م2قدار2شب22اشد ،ا2ن2تخابم2يکند 71 فصل چهارم :الگوريتم ژنتيک الگوريتم هاي ژنتيک در الگوريتم GAحاالت مابعد از طريق ترکيب دو حالت والد به جاي تغيير در حالت واحد توليد مي شوند شکلي از جست و جوي پرتو تصادفي غير قطعي ک ه حالتهاي جانشين از طريق ترکيب دو حالت والد توليد ميشود 72 فصل چهارم :الگوريتم ژنتيک -ادامه انتخاب ( )Selection والدين()Parents کروسور()Crossover فرزندان( )Offspring جمعيت اوليه( )Initial Population جهش ()Mutation جمعيت جديد( )New Population 73 جايگزينی جمعيت جديدبجای جمعيت قبلی فصل چهارم :الگوريتم ساختار الگوریتم های ژنتیک ژنتيک -ادامه مساله مدلسازی مساله تشکیل جمعیت اولیه تست شرط خاتمه انتخاب فرزندان ارزیابی جمعیت انتخاب والدین جهش 74 جستج*وی ژنتیکی بازترکیبی جواب فصل چهارم :الگوريتم ژنتيک -ادامه شروع جمعيت اوليه ‏T=0 ارزيابی جوابها خير انتخاب کروسور آيا جواب مورد نظر حاصل شده؟ بله پايان جهش 75 ‏T=T+1 فصل چهارم :الگوريتم 76 ژنتيک -ادامه فصل چهارم :الگوريتم ژنتيک -ادامه مدلسازی مساله (بازنمایی) برای اینکه بتوانیم یک مساله را بوسیله الگوریتم های ژنتیک حل کنیم ،بایستی آنرا به فرم مخصوص مورد نیاز این الگوریتم ها تبدیل کنیم. oدر این روند ما بایستی راه حل مورد نیاز مساله را به گونه ای تعریف کنیم که قابل نمایش بوسیله یک کروموزوم باشد. oاینکه چه نوع بازنمائی را برای مساله استفاده شود ،به شخص طراح و فرم مساله بستگی دارد. چند نمونه از بازنمائی هایی را که معمو ً ال استفاده می شوند : .1اعداد صحیح 77 .2رشته های بیتی .3هر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم فصل چهارم :الگوريتم ژنتيک -ادامه ارزیابی حمعیت Fitness برای اینکه بتوانیم موجودات بهتر را درون جمعیت تشخیص بدهیم بایستی معیاری را تعریف کنیم که بر اساس آن موجودات بهتر را تشخیص دهیم .به این کار ،یعنی تعیین میزان خوبی یک موجود ،ارزیابی آن موجود می گویند. ارزیابی ،اینگونه است که بر حسب اینکه موجود چقدر خوب است یک عدد به آن نسبت می دهیم، این عدد که برای موجودات بهتر بزرگتر (یا کوچکتر) است را شایستگی آن موجود می نامیم. ب*ه عنوان مثال در ص*ورتی ک*ه ب*ه دنبال مینیم*م ی*ک تاب*ع هس*تیم ،مقدار شایس*تگی را م*ی توانیم ورودیهایی که مقادیر تابع برای آنها کمتر است در نظر بگیریم که ورودیهای بهتری هستند. 78 بسته به نوع مساله ما می خواهیم شایستگی را بیشینه و یا کمینه کنیم. فصل چهارم :الگوريتم تخاب ژنتيک -ادامه ( Selectionانتخاب والدین) oسوق دادن جستجو به بخشهايی از فضا که امکان يافتن جوابهای با کیفيت باالتر وجود دارد. oنسل جدیدی از راه حل ها را با انتخاب والدینی که باالترین Fitnessرا دارند تولید می کند. والدین :در هر نسل تعدادی از عناصر جمعیت این فرصت را پیدا می کنند که تولید مثل کنند .به این ع*ناصر که از میان جمعیت انتخاب می شوند ،والدین می گویند. 79 فصل چهارم :الگوريتم بازترکيبی ژنتيک -ادامه ()Recombination/Crossover امکان ترکيب جوابهای جزيی ( )partial solutionsيافت شده و در نتيجه بدست آوردن جوابهایی با کيفيت باالتر را فراهم میآورد. در جریان عمل بازترکیبی به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیق ًا مشابه یکی از والدین نباشند. هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند. 80 فصل چهارم :الگوريتم ژنتيک -ادامه ازترکیبی تک نقطه ای ()Single Point Crossover در این روش یک مکان تصادفی در طول رشته انتخاب می شود و geneها از این مکان به بعد جابجا می شوند. 81 فصل چهارم :الگوريتم ژنتيک -ادامه جهش ()mutation ويژگی تصادفی بودن و امکان فرار از نقاط بهينه محلی را فراهم* میآورد. برای انجام جهش به این صورت عمل می کنیم: بصورت تصادفی تعدادی از کروموزوم های فرزند را انتخاب می کنیم به صورت تصادفی مقادیر یک یا چند ژن وی را تغییر می دهیم. همچنین در هنگام پیاده سازی به صورت زیر عمل می کنیم: به ازای هر کروموزوم اعمال زیر را انجام می دهیم: oیک عدد تصادفی بین صفر و یک تولید می کنیم اگر عدد تولید شده کوچکتر از Pmبود، به ازای هر ژن اعمال زیر را انجام می دهیم ،در غیر اینصورت از جهش دادن کروموزوم صرف نظر می کنیم oیک عدد تصادفی بین صفر و یک تولید می کنیم 82 اگر عدد تولید شده کوچکتر از Pgبود ،ژن مربوطه را جهش* می دهیم فصل چهارم :الگوريتم ژنتيک -ادامه جهش بيتی ( )Bitwise Mutation 83 فصل چهارم :الگوريتم ژنتيک -ادامه شرط خاتمه الگوریتم چون که الگوریتم های ژنتیک بر پایه تولید و تست می باشند ،جواب مساله مشخص نیست و نمی دانیم که کدامیک از جواب های تولید شده جواب بهینه است تا شرط خاتمه را پیدا شدن جواب در جمعیت تعریف کنیم .به همین دلیل ،معیارهای دیگری را برای شرط خاتمه در نظر می گیریم: .1تعداد مشخصی نسل :می توانیم شرط خاتمه را مث ً ال 100دور چرخش حلقه اصلی برنامه قرار دهیم. .2عدم بهبود در بهترین شایستگی جمعیت در طی چند نسل متوالی .3واریان*س شایس*تگی جمعی*ت از ی*ک مقدار مشخص*ی پائی*ن ت*ر بیای*د و ی*ا اینک*ه در ط*ی چن*د نس*ل متوال*ی مشخص، تغییر نکند. .4بهترین شایستگی جمعیت از یک حد خاصی کمتر شود. شرایط دیگری نیز می توانیم تعریف کنیم و همچنین می توانیم ترکیبی از موارد فوق را به عنوان شرط خاتمه 84به کار ببندیم.