الگوریتم‌های متا‌هیوریستیک

صفحه 1:
,Complexity NP-Complete Problems And Meta-heuristics محمدرضا کاویانی دکتر قدسی پور 

صفحه 2:
سوال اصلی چه زمانی اجازه داره از الگوریتم های متا هیوریستیک استفاده کنیم؟ 

صفحه 3:
تعریف مسئله (Problem) alo * یک سوال کلی که باید جواب داده شود. مثال : مساله ی بهینه سازی فروشنده دوره گرد. (Parameters) & ,1,4, * متغیرهای آزاد مساله که مقادیرشان نامعین قرار داده ميشود. *مثال : مجموعه اى از شهرهاى ‎CAG GG)‏ و مسافت (669:4 بين هر زوج شهر © و © 

صفحه 4:
تعریف مسئله Anstance) aigai co ‏يك نمونه از يك مساله با قرار دادن مقاذیر من برای تمام پارامترهای ساله‎ * می آید. C=16,6,6,4) d(g,q)=10 d(G,¢)=5 dlg,q)=9 ‏مثال : ی‎ 

صفحه 5:
تعریف مسئله مساله بهینه سازی فروشنده دوره گرد طول " تور"ی که از همه ی شهرها به ترتیب میگذرد و به شهر اول بر ميكردد را حداقل كنيد طول تور مینیمم - ۲۷ 

صفحه 6:
تعریف الگوریتم الگوریتم (مصطانده‌وله) یک الگوریتم یک رویه ی گام به گام (شامل توالی محدودی از دستورات) برای حل یک مساله است. الگوریتمها با زمان چند جمله ای ‎Polynomial Time‏ ‎Algorithms‏ ‏الگوریتمها با زمان نمایی ‎Exponential Time‏ Algorithms 

صفحه 7:
عوامل موثر بر پیچیدگی الگوریتم طول 505)3. ‎Anput length)‏ تعداد سمبلهای اطلاعات ورودی مورد نیاز برای توضیف یک نمونه مساله با استفاده از یک طرح کدگذاری منطقی. ‎(Largest number) ous 5 3555‏ * اهمیت (بزرگی) بزرگترین عدد در یک نمونه مساله تابع بيجيدكى زمانى ‎(Time-complexity function)‏ * بیان کننده ی زمان مورد نیاز الگوریتم است. توسط ارلئه ی بیشترین زمان مورد نياز الگوریتم برای حل نمونه مساله با همه طول ورودی های ممکن. 7 

صفحه 8:
الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی تعریف: به یک مساله رام نشدنی می گوییم اگر آنقدر سخت باشد که هیچ الگوریتم با زمان چندجمله ای نمی تواند آنرا حل کند. الگوریتم با زمان چند جمله ای چیست ؟ 

صفحه 9:
الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی (دامه) الکوریتم با زمان چندجمله ای (حصطاندم‌ولع مصن]-[متصهمصواوط) * یک الگوریتم که تابع پیچیدگی زمانی آن((۲70 است. که م یک تابع چندجمله ای و ۸ طول ورودی است. الكوريتم ‎(Exponential-time algorithm) 25 (05 b‏ * هر الگوریتم که تابع پیچیدگی زمانی آن نمی تواند محدود باشد. مانند: | tb Ur 73! 

صفحه 10:
9 ی با چند حمله ای و مسائل رام نشدتی مقایسه ی چندین تابع پیچیدگی زمانی چند جمله ای و نمایی Cues eo eo eo eov0e, | ooove, | ood ‏بهوه.‎ 6 er le eee 6۵ ‏اس‎ ‎= ‎pee dam OOF ‏لس موم‎ ‏وووه‎ 210 0 سس ان یی 06۶ 0.80 9 م6 006 6: وه 0000۶ Neal asl ‏د‎ i د 

صفحه 11:
بيجيدكى زمانى ‎Ma)‏ 1000000 7 100000 7 10000 1 ‏امم‎ ‎1000 7 —Ollogn) —oIn) 100 1 ‏(0)0۸2ست‎ ‏(0)2۸0ست‎ ‎10 + 10 1 5 10 50 100 50 ۰ 0 o1 J 11 

صفحه 12:
مسائل رام نشدنی- طم 0003-60 #مسایلی که تابع پیچیدگی زمانی حل آنها چند جمله ای نباشد در مسایل پیوسته اگر تابع هدف(02111 : محدب محدوديت هاافضاى حل: محدب جواب:بهيئه عمومى :دازد ويا شرایط 1 قابل حل است اگر دارای شرایط بالا نباشد. مساله از کلاس ۳[ می باشد و تابع پیچیدگی زمانی حل آن از نوع نمایی است. 

صفحه 13:
مساله مسائل تصمیم ---> پاسخ بله یا خیر Optimization (gjle aug filuo Problems برای حل یک مسأله ابتدا باید کلاس آن مساله مشخص شود. براى ثلبت كردن اينكه يك مساله ‎ou! NP-Complete‏ باید آن رابه یکی از مسايل شناخته شده اين كلاس 5531351613 كرد و يس از الگوریتم های متاهیوریستیک وجود دارد ن اجازه استفاده از 

صفحه 14:


صفحه 15:
۶ - Hard Problems © ممکن است بگوییم مسأله‌ای از نوع ۱۳-۳۵۲0[ است زیرا حداقل به اندازه‌ی مسایل ۳-60۳00166 ۱[ مشکل است. #منهوم 11-1270 بودن عمومی‌تر از لين است. بهرحال امکان تعمیم مفهوم تبدیل چندجمله‌ای به گونه‌ای که بتوان نشان داد مسایل دیگری به جز مسایل تصمیم حدلقلبه سختی مسایل ۳-00۳0[01616 ۱[ هستند . وجود دارد . 

صفحه 16:
۱ ۲-۱۳ ! مقر ‎P=NP‏ اعم 

صفحه 17:
Wieta-heurislcs © Genetic algorithm © Tabu search © Simulated annealing ® Ant colony © Scatter search ۰ 

صفحه 18:
گاهی اوقات جستجوی بی اطلاع نامیده می شوند. از آنجایی که هیچ دانشی در مورد دامنه مسأله ندارند. هیچ اولیتی برای رفتن به حالت بعدی (کدام گره بعدی را بسط دهند ) ندارند. براساس ترتیبی که گرههای بعدی را بسط می دهند. در انواع مختلفی تعریف می شوند. 

صفحه 19:
Owe 2 2 انه سنو كر عمق جستجو در سطح و در عمی مج وط جستجو با عمق دهی متوالی بر اسان تابعی حرکت می کند که‌میزان عطلوبیت نا نقطه فعلي حرکت را اندازه گیری می کند و دیدی نسبت به مسیر پیش رو ندارد. 

صفحه 20:
گروشهای جستجوی آگاهلنه برای حرکت در فضای جستجو از دانش مسأله استفاده می کنند. # در هر نقطه ای که هستند بهترین مسیر حرکت را با توجه به مطلوبیت مسیر طی شده و پیش بینی از مسر پیش رو انتخاب مى كنند.( هيج تضميتى وجود ندارد كه آن گره بهترین گره است ) ابتدا بهترين-037 00166 جستجوى شعاعى- 1862112 ‎Hill climbing - 9,55 45‏ يوار 20 

صفحه 21:
, Algorithm Components of a GA A problem to solve, and ... © Encoding technique (gene, chromosome) ® Initialization procedure (creation) © Evaluation function (environment) © Selection of parents (reproduction) © Genetic operators (mutation, recombination) © Parameter settings (practice and art) 21 

صفحه 22:
Reproductio children modified parents children deleted members 22 

صفحه 23:
9 ————— Crema) Chromosomes could be: ۰ Bit strings (0101 ... 1100) ® Real numbers (43.2 -33.1 ... 0.0 89.2) © Permutations of element (E11 E3E7... E1 E15) ® Lists of rules (R1 R2 R3 ... R22 R23) © Program elements (genetic programming) ©... any data structure ... 23 

صفحه 24:
تشه ۱9 children parents © Parents are selected at random with selection chances biased in relation to chromosome evaluations. 24 

صفحه 25:
“Modification inodified children ® Modifications are stochastically triggered © Operator types are: © Mutation ® Crossover (recombination) 25 

صفحه 26:
‎٩ ٩ ۵(‏ ۵ ۵ 0 بیط (© 0 4 ۵ ۵ 1 0) سوه ‎8 ‏:عسوتاج‎ (96) -O9|F 566 ‏مم6‎ ‎0.4) ‎Per: (906° 3TS 0 © Caupes)movement in the search space (local or global) ‎© Restores lost information to the population ‎ 

صفحه 27:
Precombination pi (9101000) (01001000) c1 ‏جم‎ (114011010) (11111010) 02 Crossover is a critical feature of genetic algorithms: © It greatly accelerates search early in evolution of a population ° It leads to effective combination of schemata (subsolutions on different chromosomes) 

صفحه 28:
Evaluation evaluated children modified children © The evaluator decodes a chromosome and assigns it a fitness measure © The evaluator is the only link between a classical GA and the problem it is solving 

صفحه 29:
اا ۱۳۳ Deletion discarded member: © Generational GA: entire populations replaced with each iteration © Steady-state GA: a few members replaced each generation 

صفحه 30:
وس سس 9 Distribution of Individuals in Generation 0 Distribution of Individuals in Generation N 

صفحه 31:


صفحه 32:
Simulated Annealing © بطور فیزیکی از فرایند گرم کردن و سرد کردن فلزات برگرفته شده است. © مواد در غالب يك ساختار یکنواختی گرم و سپس سرد می شوند. ‎Simulated Annealing ®‏ ]| !4 41,8 تقليد مى كند. ‏#در 9۸ هميشه تلاش جهت پذیرفتن حرکتهای بهتر است. اما نه لزوما. 

صفحه 33:
الگوریتم شروع .یک جولب اولیه ویک دمای اولیه 0< 1 را بگیر ".تا مرحله يخ زدگی ایجاد نشده انجام بده ۳ پرای 1>0<۱ انجام بده ۰۱ در همسایگی جواب ۰ 8" راتصادفی انتخاب كن ۲ اگر 9 از 5 بهتر بود جایگزین میشود ۳ و اگر بدتر بود با احتمللی که محاسبه می شود ( این ورتبه مرحله اول بر می گردیم. (0 : دما) تمام هذا 5 تر جايكزين مى شود. در غير 

صفحه 34:
برنامه سرد کردن ‎SA‏ ‎add) elas ®@‏ © دمای نهایی # نرخ کاهش دما © تعداد تكرار در هر دما 

صفحه 35:


صفحه 36:


صفحه 37:
چگونه جواب بعدى رأ بسازیم؟ رد ‎CO eight tal‏ 0 otherwise 2 > ز ]1 

صفحه 38:
[0,0] © © 0.0 [0,0] 

صفحه 39:
68,0 ]۵,0,۵[ 

صفحه 40:
202037 تکرار ج [,0,0,0] (9,0,0,0] Z © © 8 9 [0,ه,ه,ه] ]0۵,۵,۵[ 6 0 © 

صفحه 41:
]۵,0,۵,۵,۵[ [0,0,0,0,0) fal @ @ [2,0,0,0,0) 0 

صفحه 42:
مسیر و آرریابی 2 if(i, fy tour Ati, =) he 0 otherwise مقدار تابع هدف براى بهترين جواب در مرحله فلي - 02 مقدارتابع هدف براى مورجه عام - 4 0 20 ما 0 ,نا 20 وا 

صفحه 43:
بایان اجرای اول بهترين تور را ذخيره كنيد ( ترتيب و طول ) همه مورجه ها مى ميرند مورجه هاى جديد توليد مى شوند 

صفحه 44:


صفحه 45:
0 حرکت های قبلی را داخل لیستی قرار می دهد که از تکرار آن جلوگیری کند. #دو نوع ليست داردة بهترين جواب هاى يافته شده تاكنون حركت هاى قبلى 45 

صفحه 46:
الگوریتم شروع ۱. ایجاد یک جواب به صورت رندوم ۲. چک کردن همسایگی های موجود ۰۱ در صورتی که همسایگی بهتری یافت شد جواب را در لیست تابو قرار بده و همسایگی, جایگزین جواب اول می شود ۳۲ در غیر این صورت به گام ۱ برو و جواب فعلی را در لیست بهترین جوایهای یافت شده حفظ کن ۴۳ جك كردن معيار توقف پایان 46 

,Complexity NP-Complete Problems And Meta-heuristics محمدرضا کاویانی دکتر قدسی پور 1 سوال اصلی چه زمانی اجازه داره از الگوریتم های متا هیوریستیک استفاده کنیم؟ 2 تعریف مسئله مساله ()Problem • یک سوال کلی که باید جواب داده شود. مثال :مساله ی بهینه سازی فروشنده دوره گرد. پارامترها ()Parameters • متغیرهای آزاد مساله که مقادیرشان نامعین قرار داده میشود. • مثال :مجموعه ای از شهرهای C  c1, c2,...,cnو مسافت ) d(ci , cjبین هر زوج شهر ciو cj 3 تعریف مسئله نمونه ()Instance • یک نمونه از یک مساله ،با قرار دادن مقادیر معین برای تمام پارامترهای مساله بدست می آید. مثال : 4 .... ‏C  c1, c2, c3, c4 d(c1, c2) 10 d(c2, c3) 5 d(c3, c4) 9 تعریف مسئله مساله بهینه سازی فروشنده دوره گرد ‏c1 طول ” تور“ی که از همه ی شهرها به ترتیب میگذرد و به 5 9 شهر اول بر میگردد را حداقل کنید ‏c3 3 طول تور مینیمم = 27 5 10 ‏c4 6 9 ‏c2 تعریف الگوریتم الگوریتم ()Algorithm یک الگوریتم یک رویه ی گام به گام (شامل توالی محدودی از دستورات) برای حل یک مساله است. الگوریتمها با زمان چند جمله ای ‏Algorithms الگوریتمها با زمان نمایی ‏Algorithms 6 ‏Polynomial Time ‏Exponential Time عوامل موثر بر پیچیدگی الگوریتم طول ورودی ()Input length • تعداد سCمبلهای اطالعات ورودی مورد نیاز برای توصCیف یCک نمونCه مسCاله بCا استفاده از یک طرح کدگذاری منطقی. بزرگترین عدد ()Largest number • اهمیت (بزرگی) بزرگترین عدد در یک نمونه مساله تابع پیچیدگی زمانی ()Time-complexity function • بیان کننده ی زمان مورد نیاز الگوریتCم اسCت ،توسCط ارائCه ی بیشترین زمان مورد نیاز الگوریتم برای حل نمونه مساله با همه طول ورودی های ممکن. 7 الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی تعریف :به یک مساله رام نشدنی می گوییم اگر آنقدر سخت باشد که هیچ الگوریتم با زمان چندجمله ای نمی تواند آنرا حل کند. الگوریتم با زمان چند جمله ای چیست ؟ در چه مساله ای؟ در کدام کامپیوتر؟ 8 الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی (ادامه) الگوریتم با زمان چندجمله ای ()Polynomial-time algorithm • یک الگوریتم که تابع پیچیدگی زمانی آن)) O( p(nاست ،که pیک تابع چندجمله ای و nطول ورودی است. الگوریتم با زمان نمايي ()Exponential-time algorithm • هر الگوریتم که تابع پیچیدگی زمانی آن نمی تواند محدود باشد .مانند: ‏ m ‏n ! ،nn. . . ، 3n، 2n و یا  یا ‏ n 9 )الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی (ادامه مقایسه ی چندین تابع پیچیدگی زمانی چند جمله ای و نمایی Size n time complexity function n 2 n n3 5 n n 2 3n 10 20 30 40 50 60 .00001s .00002 .00003 s s .00004s .00005s .00006 .0001s .0004s .0009s .0016s .0025s .0036s .064s .125s .216s .001s .008s 1s 3.2s .001s 1s .059s 58 min .027s 24.3s 1.7 17.9 min 6.5years 12.7 min days 3855 centuries 5.2 min 35.7 years 2* 108 centuries 13 min 366 centuries 1.3* 1013 centuries 10 پیچیدگی زمانی )T(n 11 مسائل رام نشدنیNP-Complete - ‏مسایلی که تابع پیچیدگی زمانی حل آنها چند جمله ای نباشد ‏در مسایل پیوسته اگر محدب تابع هدف(: )min محدودیت ها/فضای حل :محدب جواب بهینه عمومی دارد و با شرایط KKTقابل حل است اگر دارای شرایط باال نباشد ،مساله از کالس NPمی باشد و تابع پیچیدگی زمانی حل آن از نوع نمایی است. 12 مساله مسائل تصمیم >---پاسخ بله یا خیر مسائل بهینه سازی ‏Problems ‏Optimization ‏برای حل یک مساله ابتدا باید کالس آن مساله مشخص شود. ‏برای ثابCت کردن اینکCه یCک مسCاله NP-CompleteاسCت بایCد آCن را بCه یکی از مسCایل شناختCه شده ایCن کالس transferکرد و پCس از آCن اجازه استفاده از الگوریتم های متاهیوریستیک وجود دارد 13 NP وP رابطه بین NP P NPcomplete 14 NP – Hard Problems ممكPن اسPت بگوييم مسPأله‌اي از نوع NP-hardاسPت زيرا حداقل به اندازه‌ي مسايل NP-completeمشكل است. ‏مفهوم NP-hardبودن عمومي‌تCر از اين اسCت ،بهرحال امكان تعميم مفهوم تبديل چندجمله‌اي بCه گونه‌اي كه بتوان نشان داد مسCايل ديگري بCه جCز مسايل تصCميم حداقPلبPه سPختي مسCايل NP-completeهستند ،وجود دارد . 15 Relation Between NP-Complete & NP-Hard 16 Meta-heuristics Genetic algorithm Tabu search Simulated annealing Ant colony Scatter search ... 17 مقدمه روشهای جستجوی کورکورانه ‏گاهی اوقات جستجوی بی اطالع نامیدCه می شوند ،از آنجایی که هیچ دانشی در مورد دامنه مسأله ندارند. هیچ اولیتی برای رفتن به حالت بعدی (کدام گره بعدی را بسط دهند ) ندارند. براساس ترتیبی که گرههای بعدی را بسط می دهند ،در انواع مختلفی تعریف می شوند. 18 روشهای جستجوی کورکورانه ‏جستو در عمق ‏جستجو در سطح ‏جستجو در عمق محدود ‏جستجو با عمق دهی متوالی ‏بر اساس تابعی حرکت می کند که میزان مطلوبیت تا نقطه فعلی حرکت را اندازه گیری می کند و دیدی نسبت به مسیر پیش رو ندارد. 19 روشهای جستجوی آگاهانه – Heuristics ‏روشهای جسCتجوی آگاهانCه برای حرکCت در فضای جسCتجو از دانCش مسCأله اسCتفاده می کنند. در هر نقطه ای که هستند بهترین مسیر حرکت را با توجه به مطلوبیت مسیر طCی شده و پیش بینی از مسیر پیش رو انتخاب می کنند (.هیچ تضمینی وجود ندارد که آن گره بهترین گره است ) ابتدا بهترینGreedy- جستجوی شعاعیBeam - تپه نوردیHill climbing - AسCCتارCه Cدار 20 Genetic Algorithm Components of a GA A problem to solve, and ... Encoding technique (gene, chromosome) Initialization procedure (creation) Evaluation function (environment) Selection of parents (reproduction) Genetic operators (mutation, recombination) Parameter settings (practice and art) 21 The GA Cycle of Reproduction reproduction children modified children parents population modification evaluated children evaluation deleted members discard 22 Population population Chromosomes could be: Bit strings Real numbers Permutations of element Lists of rules Program elements ... any data structure ... (0101 ... 1100) (43.2 -33.1 ... 0.0 89.2) (E11 E3 E7 ... E1 E15) (R1 R2 R3 ... R22 R23) (genetic programming) 23 Reproduction reproduction children parents population Parents are selected at random with selection chances biased in relation to chromosome evaluations. 24 Chromosome Modification children modification modified children Modifications are stochastically triggered Operator types are: Mutation Crossover (recombination) 25 Mutation: Local Modification Before: (1 0 1 1 0 1 1 0) After: (0 1 1 0 0 1 1 0) Before: 0.1) (1.38 -69.4 326.44 After: (1.38 -67.5 326.44 Causes 0.1) movement in the search space (local or global) Restores lost information to the population Crossover: Recombination * P1 P2 C2 (0 1 1 0 1 0 0 0) (1 1 0 1 1 0 1 0) (0 1 0 0 1 0 0 0) (1 1 1 1 1 0 1 0) C1 Crossover is a critical feature of genetic algorithms: It greatly accelerates search early in evolution of a population It leads to effective combination of schemata (subsolutions on different chromosomes) Evaluation evaluated children modified children evaluation The evaluator decodes a chromosome and assigns it a fitness measure The evaluator is the only link between a classical GA and the problem it is solving Deletion population discarded members discard Generational GA: entire populations replaced with each iteration Steady-state GA: a few members replaced each generation Distribution of Individuals in Generation 0 Distribution of Individuals in Generation N Simulated Annealing بطور فیزیکی از فرایند گرم کردن و سرد کردن فلزات برگرفته شده است. مواد در غالب یک ساختار یکنواختی گرم و سپس سرد می شوند. Simulated Annealing از این فرایند تقلید می کند. ‏در SAهمیشه تالش جهت پذیرفتن حرکتهای بهتر است .اما نه لزوما. الگوریتم شروع .1یک جواCب اولیه ویک دمای اولیه T>0را بگیر .2تا مرحله یخ زدگی ایجاد نشده انجام بده .3برای i<p<1انجام بده .3.1در همسایگی جواب ’S ، Sراتصادفی انتخاب کن .3.2اگر ’Sاز Sبهتر بود جایگزین میشود .3.3و اگCر بدتCر بود بCا احتمالCی کCه محاسCبه مCی شود ( این ورتبه مرحله اول بر می گردیم : C ( .دما) تمام )، ‏ ‏ ‏ P ‏cجCواب ‏eتCر جایگزیCن مCی شود .در غیر بد برنامه سرد کردن SA دمای اولیه دمای نهایی نرخ کاهش دما تعداد تکرار در هر دما رفتار طبیعی مورچه چگونه جواب بعدی را بسازیم؟ [A] 1 A B [A] 1 [A] C 1 [A,D] [A]  [  ij ( t )] [  ij ]  if j  allowed  k 1    1 k [  ( t )] [  ]  ik pij ( t )  Dkallowed ik k E   otherwise 0 تکرار دوم [C,B] A B [B,C] 2 [A,D] 1 C [D,E] D 4 E 3 تکرار سوم [D,E,A] 4 [E,A,B] 5 A B [A,D,C] 1 C [B,C,D] [C,B,E] 2 D 3 E تکرار چهارم [B,C,D,A] 2 [D,E,A,B] 4 A B [E,A,B,C] 5 [C,B,E,D] D 3 C [A,DCE] 1 E تکرار پنجم [A,D,C,E,B] [C,B,E,D,A] 1 3 A B [D,E,A,B,C] 4 C [E,A,B,C,D] [B,C,D,A,E] D 5 E 2 مسیر و ارزیابی فرومن [A,D,C,E,B] L1 =300  ik, j 1 [B,C,D,A,E] L2 =450 2 [C,B,E,D,A] total 3A,B   1 L3 =260 2 A,B A,B   [D,E,A,B,C] L4 =280 4 [E,A,B,C,D] L5 =420 5 Q if (i, j)  tour   Lk 0 otherwise  Q مقدار تابع هدف برای بهترین جواب در مرحله فعلی Lk  امk مقدارتابع هدف برای مورچه   3 A,B   4 A,B   5 A,B پایان اجرای اول بهترین تور را ذخیره کنید ( ترتیب و طول ) همه مورچه ها می میرند مورچه های جدید تولید می شوند فلسفه لیست تابو حرکت های قبلی را داخل لیستی قرار می دهد که از تکرار آن جلوگیری کند. ‏دو نوع لیست دارد: بهترین جواب های یافته شده تاکنون حرکت های قبلی 45 الگوریتم شروع .1ایجاد یک جواب به صورت رندوم .2چک کردن همسایگی های موجود . 2.1در صورتی که همسایگی بهتری یافت شد جواب را در لیست تابو قرار بده و همسایگی ،جایگزین جواب اول می شود .2.2در غیر این صورت به گام 1برو و جواب فعلی را در لیست بهترین جوابهای یافت شده حفظ کن .3چک کردن معیار توقف پایان 46