یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
دسته‌بندی الگوریتم‌های فرا اکتشافی

معیار‌های مختلفی می‌تواند برای طبقه‌بندی الگوریتم‌های فرا اکتشافی استفاده شود[Talb09]:

·         مبتنی بر یک جواب و مبتنی بر جمعیت : الگوریتم‌های مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شود.

·         الهام گرفته شده از طبیعت و بدون الهام از طبیعت : بسیاری از الگوریتم‌های فرا اکتشافی از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم­های فرا اکتشافی نیز از طبیعت الهام گرفته نشده اند.

·         با حافظه و بدون حافظه : برخی از الگوریتم‌های فرا اکتشافی فاقد حافظه می‌باشند، به این معنا که این نوع الگوریتم‌ها از اطلاعات به دست امده در حین جستجو استفاده نمی­کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که برخی از الگوریتم‌های فرا اکتشافی نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه، اطلاعات به دست امده در حین جستجو را در خود ذخیره می‌کند.

·         قطعی و احتمالی: یک الگوریتم فرا اکتشافی قطعی نظیر جستجوی ممنوعه، مساله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فرا اکتشافی احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.

اکثر فرا اکتشافی­ها در دو گروه طبقه­بندی می­شوند [Blum03]:

1)    راه حل­های مبتنی بر یک جواب[1] (مانند Tabu Searchو simulated annealing) که یک جواب پیشنهادی را در هر تکرار تولید می­کنند.

2)    راه حل­های مبتنی بر جمعیت[2] (مانند الگوریتم ژنتیک) که جمعی یا گروهی از جواب­های پیشنهادی را در هر تکرار تولید می­کنند.

Duvalفرا اکتشافی­­ها را به طور کلی به دو دسته تقسیم کرده است [Duva09]:

1)    روش­های جستجوی محلی مبتنی بر همسایگی[3][Hoos04]

2)    الگوریتم­های تکاملی[4] مبتنی بر جمعیت [Back97]

که نماینده گروه اول شامل Tabu Searchو simulated annealingمی­شود، درحالیکه الگوریتم­های ژنتیک، نمونه­ای شاخص از روش­های تکاملی به حساب می­ایند.

الگوریتم ژنتیک (Genetic Algorithm)

الگوریتمژنتیکGA[5]،یکروشاماری و تکنیک جستجو در علم رایانه به منظور یافتن راه‌حل تقریبی برای بهینه‌سازی و مسایل جستجو است، الگوریتم ژنتیک نوع خاصی از الگوریتم­های تکاملی است که از تکنیک­های زیست‌شناسی مانند وراثت و جهش استفاده می‌کند. ویژگی­هایخاصاین الگوریتمباعث می­شود کهنتوانیمانرایکجستجوگرتصادفیسادهقلمدادکنیم.

 ایدهاولیهاینروشاز نظریه تکاملیDarwinالهامگرفتهشده است[Gold89]وکارکردانبراساسژنتیک طبیعیاستوارمیباشد [Kave02]. در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند [Affe02].

ایدهمحاسباتتکاملیاولینباردرسال١٩٦٠توسطرچنبرگ کهدرزمینهاستراتژی­های تکاملی تحقیقمی­کردبه وجودامد [Rech73]کهنظریهاوبعدهاتوسطدیگرمحققانتوسعهدادهشد. اصولاولیه الگوریتمژنتیکتوسطهلند Hollandوهمکارانشدردانشگاهمیشیگاندرسال١٩٦٢ارائهشد [Holl75]. انان در تحقیقاتخودبهفرایندسازگاریدرسیستم­هایطبیعیتوجهنمودندوبرایمدل­سازیان در سیستم­هایمصنوعیکهبایددارایتوانایی­هایاصلیسیستم­هایطبیعیباشند،تلاشنمودند.نتیجه اینتلاش­ها،پیدایشالگوریتمژنتیکبود.سپسدرسال١٩٧٥مبانیریاضیاندرکتابی به نام "تطابقدرسیستم­هایطبیعیومصنوعی" توسطهلندمنتشر شد.

درسال ١٩٩٢،جانکوزا John Kozaالگوریتمژنتیکرابهمنظورانجاموظایفخاصیدربرنامه­هایشبکار برد [Kosa92]. او اینروشرا برنامهریزیتکاملی[6] نامید.دربرنامه­ریزی تکاملی،هدفپیداکردنالگوریتمیاستکهبتواندجواب هرصورتمساله­ایراپیداکند.دراین روش­هابایدبرایالگوریتم­هامطلوبیتتعریفکردتافهمیده شودکهکدامالگوریتمبهتراست.

الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. مختصرا گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مساله استفاده می‌کند.مساله‌ای که باید حل شود ورودی است و راه‌حل­ها طبق یک الگو کدگذاری می‌شوند و توسط تابعی که تابع fitnessنام دارد، سنجیده می­شود و این تابع هر راه حل کاندید را ارزیابی می‌کند که اکثر ان­ها به صورت تصادفی انتخاب می‌شوند.

کلا این الگوریتم‌ها از بخش­های زیر تشکیل می‌شوند : تابع برازش - نمایش - انتخاب - تغییر.

  قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و ان­هایی که این خصوصیات را نداشته باشند، به تدریج و در طی زمان از بین می‌روند. مثلا فرض کنید گونه خاصی از افراد، هوش بسیار بیشتری از بقیه افراد یک جامعه یا کولونی دارند. در شرایط کاملا طبیعی این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتا بالاتری خواهند داشت و این رفاه خود باعث طول عمر بیشتر و باروری بهتر خواهد بود. حال اگر این خصوصیت (هوش) ارثی باشد به طبع در نسل بعدی همان جامعه، تعداد افراد باهوش به دلیل زاد و ولد بیشتر این‌گونه افراد بیشتر خواهد بود. اگر همین روند ادامه پیدا کند، خواهیم دید که در طی نسل‌های متوالی دایما جامعه نمونه ما باهوش و باهوش‌تر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملا افراد کم هوش را از جامعه حذف کند، علاوه بر اینکه میزان هوش متوسط جامعه نیز دایما در حال افزایش است.

  بدین ترتیب می‌توان دید که طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه) توانسته است دایما هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد. در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه (تصادف یا Blind Search) + بقای قوی‌تر.

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

  روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی(Local Optima) را به عنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مساله خاصی کاربرد دارند.

به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد که یکی از ان­ها ماکزیمم محلی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک، مقدار ماکزیمم تابع را بیابیم. مثلا از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از ان متوقف خواهد شد. اما در روش‌های هوشمند مخصوصا الگوریتم ژنتیک، به دلیل خصلت تصادفی ان­ها، حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه، نقطه Aبه صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.

شکل 1- بهینه محلی و بهینه کلی

در مورد نکته دوم باید بگوییم که روش‌های ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مساله می‌شوند، در حالی که روش‌های هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در حل هر مساله‌ای به کار گرفته شوند.

برای شناخت الگوریتم ژنتیک، لازم است تعاریف زیر انجام شود:

·         شخص (Individual): یک جواب کاندید برای مساله که معمولا به صورت رشته بیتی نمایش داده می­شود.

·         ژن (gene): هر بیت در شخص است و واحدپایهژنتیکاست.

·         فرم (allele): حالت­هایمختلفهرژنرامی­گویند، اگر رشته بیتی باشد دارای مقادیر 0یا 1می­باشد.

·         لوکاس (Locus): موقعیت هر ژن بر روی کروموزوم را گویند.

·         جمعیت (Population): مجموعه­ای از اشخاص که سایز ان معمولا ثابت است.

·         کروموزوم (choromosome): بهگروهیازژن­هااطلاق می­شود.

الگوریتم ژنتیک، الگوریتمی اتفاقی[7] است که از تکامل طبیعی تقلید می­کند. جنبه­ای که این الگوریتم را مجزا می­کند، این است که مجموعه­ای از جواب­ها را که اشخاص یا کروموزوم نامیده می­شود، در یک جمعیت نگه می­دارد. همانند تکامل زیستی، دارای مکانیزمی است که بهترین و مناسب­ترین کروموزوم را در هر نسل انتخاب می­کند. به منظور شبیه­سازی فرایند تکامل، کروموزوم­های انتخاب شده تحت تاثیر عملگر­های ژنتیک همانند crossoverو Mutationقرار می­گیرند [Byun04].

مراحل الگوریتم ژنتیک

الگوریتم ژنتیک دارای پنج مرحله می­باشد که بدین ترتیب است:

·         Encoding

·         Evaluation

·         Crossover

·         Mutation

·         Decoding

حال به شرح مراحل ذکر شده می­پردازیم.

1)     Encoding

اینمرحلهشایدمشکل­ترینمرحلهحلمسالهبهروشالگوریتمژنتیکباشد. اینمرحلهبهاین مفهوماستکهمابایدباارائهیکشبیه­سازیوجایگذاری Representation)) خوب برای کلیه جواب­هایممکنمراحلبعدیراادامهدهیم. اهمیتاینمرحلهبهایندلیلاستکهنحوهادامهکار بهاینمرحلهبستگیدارد.درواقعمادراینمرحلهرشته­هایکروموزومییاهمان رشته­هایبیتی ممکنبرایجواب­هارامی­سازیم.چهبسامابتوانیمبا یکشبیه­سازیخوببرایجواب­ها، الگوریتم رادریکزمانخوبو معقولپیشببریم.بعدازساختاربندیبرایهرجوابممکن،از کنار هم گذاشتناینساختارهاجمعیتاولیهما (First Population)ساختهمی­شود.

انواع کدینگ

کدینگ به دو صورت کلی می­باشد :

·         کدینگ مستقیم: در این روش کل یک جواب به عنوان یک کروموزوم در نظر گرفته می­شود. برای مسائل پیچیده چنین روشی مناسب نیست، زیرا عملگرهای ژنتیکی به خاطر گستردگی زیاد فرزندان غیرکاربردی می­شوند و در نتیجه منجر به جواب­های غیرقابل قبول و غیرقانونی می­شوند.

·         کدینگ غیرمستقیم: در این روش تنها قسمتی از یک جواب به صورت یک کروموزوم کد می­شود.

روش­های کدینگ

الگوریتم ژنتیک به جای این که بر روی پارامتر­ها یا متغیر­های مساله کار کند، با شکل کد شده ان­ها سروکار دارد.

1)    کدینگ باینری

یکی از روش­های کد کردن، کد کردن دودویی می­باشد که در ان هدف، تبدیل جواب مساله به رشته­ای از اعداد باینری در مبنای 2 است. ایننوعکدینگ،متداولتریننوعکدینگمیباشد.دراینروشکدگذاری،هرکروموزومیکرشتهاز بیت­هایشامل0 و١می­باشد.کدینگباینریمی­تواندحالت­هایزیادیراپوششدهد،حتیدرمواردی کهتعدادالل­هاکمباشد.

برای مساله انتخاب ویژگی، یک رشته با Dرقم دودویی در نظر گرفته می­شود. هر رقم دودویی بیان کننده یک ویژگی است، مقدار 1معرف انتخاب شدن و مقدار 0معرف حذف شدن می­باشد. به عنوان مثال، کروموزوم 00101000به این معنی است که ویژگی­های سوم و پنجم انتخاب شده­اند [Byun04].

شکل 2 - کدینگ باینری

ازطرفدیگرایننوعکدینگبرایخیلیازمسائلحالتطبیعینداردواغلباوقاتلازماستکهبعد ازتقاطع[8]وجهش[9]اصلاحاتیصورتبگیرد.

2)    کدینگ جهشی[10]

ایننوعکدینگمی­توانددرمسائلترتیبینظیرمسالهفروشندهدورهگردیامسالهترتیبکارهابه کار رود.درکدینگجهشی،هرکروموزومیکرشتهازاعدادمی­باشد.شکلزیرنمونه­ایازایننوع کدینگرانشانمی­دهد.

شکل 3 - کدینگ جهشی

شکل 3 - کدینگ جهشی

کدینگجهشیتنهابرایمسائلترتیبیمفیداست.حتیبرایهمینمسائلنیزگاهیاوقاتباید تقاطع­هاوجهش­هایاصلاحیبهمنظورایجادکروموزوم­هایسازگارومناسبانجامشود.

3)    کدینگ ارزشی[11]

ایننوعکدینگدر مسایلیکهدران­هامقادیرپیچیدهنظیراعدادحقیقیبه کار می­روند،استفادهمی­شود.استفادهازکدینگباینریبرایچنینمسایلیبسیارسختمیباشد.درکدینگارزشی،هرژن یککروموزومارزشخاصیدارد. اینپارامتربا ارزشمی­تواندعدد،حرفیاکلمهباشد. در این نوعکدینگنیازبهتوسعهعملگرهایجابجاییوجهشجدیدبرایمسایلخاصمیباشد.

شکل 4 - کدینگ ارزشی

شکل 4 - کدینگ ارزشی

4)    کدینگ درختی

کدینگدرختیدربرنامه­هایتکاملیبهمنظوربرنامه­ریزیتکاملیبه کارمی­رود. درکدینگدرختی هر کروموزوم،یکدرختازاشیایینظیرتوابعیادستورهادرزبانبرنامهنویسیمیباشد.شکل زیر دو نمونهازاینکروموزوم­هارانشانمی­دهد.ایننوعکدینگبرایبرنامه­هایتکاملیبسیارعالی است.زبانبرنامهنویسی Lispاغلبازایننوعکدینگاستفادهمی­کندواینبدینعلتاستکه برنامه­هایانبهاینفرمنمایشدادهمی­شوندومی­توانندبه راحتیموردتجزیهقراربگیرند. بنابراین عمل تقاطعوجهشنیزبههماننسبتراحتانجاممی­شود.

 

Chromosome A

Chromosome B

 

 

( +  x  ( /  5  y ) )

( do_until  step  wall )

 

شکل 5 - کدینگ درختی

2)     Evaluation

اینمرحلهنیزنقشبسیارمهمیرادرحلمسالهبهروش الگوریتمژنتیکایفامی­کند. مادراین مرحلهبامعرفییکمعیارو اندازه،بهبهتربودنیانبودنهرجوابممکنازجمعیتاولیهپی می­بریم.یعنیاین کهاینمعیاربهمامی­گویدکهمثلاجواب xواقعدر جمعیت اولیه چقدرخوب است.اینمعیارمی­تواندبانسبتدادنیکعددبههرجوابممکن، میزانخوببودنانجوابرا بیانکند.هرچهکه یکجوابمناسب­ترباشد،مقداربرازندگیبزرگتریدارد.برایانکهشانس بقایچنینجوابیبیشتر شود،احتمالبقایان،متناسببامقداربرازندگیاندرنظرگرفتهمی­شود.بنابراینکروموزومیکه برازند­ه­تریناست،بااحتمالبیشتریدرتولیدفرزندانشرکتمی­کندو دنباله­هایبیشتریازانبه وجودمی­اید. معمولا درمواردیکهامکاندارد،تابعبرازندگیرا در فاصله[0,1] نرمالیزهمی­کنند.

ارزیابی کار اسانی است، چون کروموزوم مجموعه ویژگی انتخاب شده Xرا نشان می­دهد و تابع ارزیابی واضح می­باشد. برای این که مجموعه ویژگی، اندازه مورد نیاز ما را رعایت کند، مقدار اندازه dرا به عنوان یک قید در نظر می­گیریم و برای کروموزوم­هایی که این قید را بشکنند، جریمه اعمال می­کنیم. برازندگی کروموزوم Cبه این ترتیب تعریف می­شود [Seon04]:

رابطه (1)                                                        Fitness (C) = J(XC) - Penalty(XC)         

که XC متناظر با مجموعه ویژگی Cاست. تابع J(XC)   کارایی متغیر xرا می­سنجد. همچنین داریم:

رابطه (2)                                                                      Penalty(XC) =  w * || XC| - d|

تابع Penalty(X)، تابع جریمه با ضریب جریمه wاست.

3)     Crossover

درالگوریتمژنتیک،برایبه وجوداوردنیکنسلجدید (یایکسریکروموزومجدید) ازجواب­ها، ما یکسریازتغییراترارویجواب­هایانتخابشده (Selected)یا کروموزوم­ها اعمالمی­کنیم. بهاینگونهازتغییرات،اِعمالعملگر می­گوییم.

حالعملگرهایمادراینتغییراتدوعملگر Crossoverو Mutationمی­باشدکهمادراین قسمتبهنحوهعملکردCrossoverمی­پردازیم.

در طبیعت، بقای یک نسل یکی از مهمترین فاکتورها است و تنها عملگر ممکن برای این امر امیزش است. در الگوریتم­های ژنتیکی به طبع، طبیعت امیزش وجود دارد. امیزش با تعویض ژن­ها بین دو کروموزوم انجام می­گیرد و هر کدام از کروموزوم­ها خصوصیاتی از خود را به فرزندان انتقال می­دهند. بدیهی است کروموزوم­هایی که دارای برازندگی بیشتری باشند، شانس بیشتری برای امیزش دارند.

مهمترین عملگر در الگوریتم ژنتیک، عملگر ترکیب است. ترکیب، فرایندی است که در ان نسل قدیمی کروموزوم­ها با یکدیگر مخلوط و ترکیب می­شوند تا نسل تازه­ای از کروموزوم­ها به وجود بیاید. جفت­هایی به عنوان والد، ژن­هایشان را با هم مبادله می­کنند و اعضایی جدید به وجود می­اورند. ترکیب در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی جمعیت می­شود، زیرا اجازه می­دهد ژن­های خوب یکدیگر را بیابند.

عملگر Crossoverرویجواب­هایانتخابشدهبرایتغییر،بهاین گونهعملمی­کندکهیک نقطهبهصورتتصادفیرویرشته کروموزومیانتخابمی­کند، بعدناحیه­های چپیاراستان نقطهدررشتهکروموزومیجا بجامی­شود.


[1] Single-pointsolutions

[2] Population-based solutions

[3] Neighborhood-based

[4] Evolutionary algorithms

[5] Genetic Algorithm

[6] Genetic Programming

[7] stochastic algorithm

[8] Crossover

[9] Mutation

[10]Permutation Encoding

[11]Value Encoding

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26