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

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

اسلاید 1: Complexity, NP-Complete ProblemsAnd Meta-heuristics1محمدرضا کاویانیدکتر قدسی پور

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

اسلاید 3: تعریف مسئلهمساله (Problem) یک سوال کلی که باید جواب داده شود.مثال : مساله ی بهینه سازی فروشنده دوره گرد.پارامترها (Parameters) متغیرهای آزاد مساله که مقادیرشان نامعین قرار داده میشود.مثال : مجموعه ای از شهرهای و مسافت بین هر زوج شهر و 3

اسلاید 4: تعریف مسئلهنمونه (Instance) یک نمونه از یک مساله، با قرار دادن مقادیر معین برای تمام پارامترهای مساله بدست می آید.مثال : ....4

اسلاید 5: تعریف مسئلهمساله بهینه سازی فروشنده دوره گرد6910953طول تور مینیمم = 27طول ” تور“ی که از همه ی شهرها به ترتیب میگذرد و به شهر اول بر میگردد را حداقل کنید5

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

اسلاید 7: عوامل موثر بر پیچیدگی الگوریتمطول ورودی (Input length) تعداد سمبلهای اطلاعات ورودی مورد نیاز برای توصیف یک نمونه مساله با استفاده از یک طرح کدگذاری منطقی.بزرگترین عدد (Largest number) اهمیت (بزرگی) بزرگترین عدد در یک نمونه مسالهتابع پیچیدگی زمانی (Time-complexity function) بیان کننده ی زمان مورد نیاز الگوریتم است، توسط ارائه ی بیشترین زمان مورد نیاز الگوریتم برای حل نمونه مساله با همه طول ورودی های ممکن.7

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

اسلاید 9: الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی (ادامه)الگوریتم با زمان چندجمله ای (Polynomial-time algorithm) یک الگوریتم که تابع پیچیدگی زمانی آن است، که p یک تابع چندجمله ای و n طول ورودی است. الگوریتم با زمان نمايي (Exponential-time algorithm) هر الگوریتم که تابع پیچیدگی زمانی آن نمی تواند محدود باشد. مانند: 9 ، ، . . . ، یا و یا

اسلاید 10: الگوریتمها با زمان چند جمله ای و مسائل رام نشدنی (ادامه)10Size nSize nSize nSize nSize nSize ntime complexity function605040302010time complexity function.00006.00005s.00004s.00003s.00002s.00001s.0036s.0025s.0016s.0009s.0004s.0001s .216s.125s.064s.027s.008s.001s 13 min5.2 min1.7 min24.3s3.2s1s 366 centuries35.7 years12.7 days17.9 min1s.001s  centuries centuries3855 centuries6.5years58 min.059s مقایسه ی چندین تابع پیچیدگی زمانی چند جمله ای و نمایی

اسلاید 11: پیچیدگی زمانی T(n)11

اسلاید 12: مسائل رام نشدنی- NP-Completeمسایلی که تابع پیچیدگی زمانی حل آنها چند جمله ای نباشددر مسایل پیوسته اگرtttتابع هدف(min) : محدبtttمحدودیت ها/فضای حل: محدب جواب بهینه عمومی دارد و با شرایط KKT قابل حل استاگر دارای شرایط بالا نباشد، مساله از کلاس NP می باشد و تابع پیچیدگی زمانی حل آن از نوع نمایی است.12

اسلاید 13: مساله13مسائل تصمیم ---> پاسخ بله یا خیرمسائل بهینه سازی Optimization Problemsبرای حل یک مساله ابتدا باید کلاس آن مساله مشخص شود. برای ثابت کردن اینکه یک مساله NP-Complete است باید آن را به یکی از مسایل شناخته شده این کلاس transfer کرد و پس از آن اجازه استفاده از الگوریتم های متاهیوریستیک وجود دارد

اسلاید 14: رابطه بین P و NP14PNP-completeNP

اسلاید 15: NP – Hard Problems ممكن است بگوييم مسأله‌اي از نوع NP-hard است زيرا حداقل به اندازه‌ي مسايل NP-complete مشكل است. مفهوم NP-hard بودن عمومي‌تر از اين است، بهرحال امكان تعميم مفهوم تبديل چندجمله‌اي به گونه‌اي كه بتوان نشان داد مسايل ديگري به جز مسايل تصميم حداقل به سختي مسايل NP-complete هستند ، وجود دارد . 15

اسلاید 16: Relation Between NP-Complete & NP-Hard 16

اسلاید 17: Meta-heuristics Genetic algorithmTabu searchSimulated annealingAnt colonyScatter search...17

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

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

اسلاید 20: 20روشهای جستجوی آگاهانه – Heuristicsروشهای جستجوی آگاهانه برای حرکت در فضای جستجو از دانش مسأله استفاده می کنند.در هر نقطه ای که هستند بهترین مسیر حرکت را با توجه به مطلوبیت مسیر طی شده و پیش بینی از مسیر پیش رو انتخاب می کنند.( هیچ تضمینی وجود ندارد که آن گره بهترین گره است )ابتدا بهترین-Greedyجستجوی شعاعی- Beamتپه نوردی- Hill climbingA ستاره دار

اسلاید 21: Genetic AlgorithmComponents of a GAA 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: The GA Cycle of Reproduction22reproductionpopulationevaluationmodificationdiscarddeleted membersparentschildrenmodifiedchildrenevaluated children

اسلاید 23: PopulationChromosomes could be:Bit strings (0101 ... 1100)Real numbers (43.2 -33.1 ... 0.0 89.2) Permutations of element (E11 E3 E7 ... E1 E15)Lists of rules (R1 R2 R3 ... R22 R23)Program elements (genetic programming)... any data structure ...23population

اسلاید 24: ReproductionParents are selected at random with selection chances biased in relation to chromosome evaluations.24reproductionpopulationparentschildren

اسلاید 25: Chromosome ModificationModifications are stochastically triggeredOperator types are:MutationCrossover (recombination)25modificationchildrenmodified children

اسلاید 26: Mutation: Local ModificationBefore:t (1 0 1 1 0 1 1 0)After:tt (0 1 1 0 0 1 1 0)Before:t (1.38 -69.4 326.44 0.1)After:tt (1.38 -67.5 326.44 0.1)Causes movement in the search space (local or global)Restores lost information to the population

اسلاید 27: Crossover: RecombinationP1 (0 1 1 0 1 0 0 0) (0 1 0 0 1 0 0 0) C1P2 (1 1 0 1 1 0 1 0) (1 1 1 1 1 0 1 0) C2Crossover is a critical feature of geneticalgorithms:It greatly accelerates search early in evolution of a populationIt leads to effective combination of schemata (subsolutions on different chromosomes)*

اسلاید 28: EvaluationThe evaluator decodes a chromosome and assigns it a fitness measureThe evaluator is the only link between a classical GA and the problem it is solvingevaluationevaluatedchildrenmodifiedchildren

اسلاید 29: DeletionGenerational GA: entire populations replaced with each iterationSteady-state GA: a few members replaced each generationpopulationdiscarddiscarded members

اسلاید 30: An Abstract ExampleDistribution of Individuals in Generation 0Distribution of Individuals in Generation N

اسلاید 31: Simulated Annealing

اسلاید 32: Simulated Annealing بطور فیزیکی از فرایند گرم کردن و سرد کردن فلزات برگرفته شده است. مواد در غالب یک ساختار یکنواختی گرم و سپس سرد می شوند. Simulated Annealing از این فرایند تقلید می کند.در SA همیشه تلاش جهت پذیرفتن حرکتهای بهتر است. اما نه لزوما.

اسلاید 33: الگوریتم شروع1.یک جواب اولیه ویک دمای اولیه T>0 را بگیر2.تا مرحله یخ زدگی ایجاد نشده انجام بده3. برای 1<i<p انجام بدهt3.1. در همسایگی جواب S، S’ راتصادفی انتخاب کنt3.2. اگر S’ از S بهتر بود جایگزین میشودt3.3. و اگر بدتر بود با احتمالی که محاسبه می شود ( )، جواب بدتر جایگزین می tشود. در غیر این ورتبه مرحله اول بر می گردیم. (C : دما)تمام

اسلاید 34: برنامه سرد کردن SA دمای اولیه دمای نهایی نرخ کاهش دما تعداد تکرار در هر دما

اسلاید 35: Ant Colony Optimization

اسلاید 36: رفتار طبیعی مورچه

اسلاید 37: چگونه جواب بعدی را بسازیم؟AEDCB1[A]1[A]1[A]1[A]1[A,D]

اسلاید 38: تکرار دومAEDCB3[C,B]1[A,D]2[B,C]4[D,E]

اسلاید 39: تکرار سومAEDCB4[D,E,A]5[E,A,B]3[C,B,E]2[B,C,D]1[A,D,C]

اسلاید 40: تکرار چهارمAEDCB4[D,E,A,B]2[B,C,D,A]5[E,A,B,C]1[A,DCE]3[C,B,E,D]

اسلاید 41: تکرار پنجمAEDCB1[A,D,C,E,B]3[C,B,E,D,A]4[D,E,A,B,C]2[B,C,D,A,E]5[E,A,B,C,D]

اسلاید 42: مسیر و ارزیابی فرومن1[A,D,C,E,B]5[E,A,B,C,D]L1 =300L2 =450L3 =260L4 =280L5 =4202[B,C,D,A,E]3[C,B,E,D,A]4[D,E,A,B,C]مقدار تابع هدف برای بهترین جواب در مرحله فعلیامk مقدارتابع هدف برای مورچه

اسلاید 43: پایان اجرای اولبهترین تور را ذخیره کنید ( ترتیب و طول )همه مورچه ها می میرندمورچه های جدید تولید می شوند

اسلاید 44: Tabu Search

اسلاید 45: فلسفه لیست تابوحرکت های قبلی را داخل لیستی قرار می دهد که از تکرار آن جلوگیری کند.دو نوع لیست دارد:tبهترین جواب های یافته شده تاکنونtحرکت های قبلی45

اسلاید 46: الگوریتمشروع1. ایجاد یک جواب به صورت رندوم2. چک کردن همسایگی های موجودtt2.1. در صورتی که همسایگی بهتری یافت شد جواب را در لیست تابو tقرار بده و همسایگی، جایگزین جواب اول می شودtt2.2. در غیر این صورت به گام 1 برو و جواب فعلی را در لیست بهترین tجوابهای یافت شده حفظ کن3. چک کردن معیار توقفپایان46