صفحه قبلی – صفحه بعدی

نمایش راه حل

یکی از مهمترین تصمیمات در هنگام اجرای یک الگوریتم ژنتیک تصمیم گیری درباره نحوه نشان دادن راه حل های مساله می باشد. مشاهده شده است که نحوه نامناسب نمایش راه حل می تواند منجر به عملکرد ضعیف GA شود.
بنابراین برای موفقیت GA انتخاب یک نمایش مناسب، با داشتن تعریف مناسب از نگاشت بین فضای فنوتیپ و ژنوتیپ ضروری است .
در این بخش، ما برخی از روش های مرسوم نمایش راه حل ها در الگوریتم های ژنتیک را ارائه می دهیم. با این حال، نحوه نمایش راه حل بستگی زیادی به نوع مساله دارد و خواننده ممکن است دریابد که نمایشی از نوع دیگر یا ترکیبی از نمایشهای ذکر شده در اینجا می تواند برای حل مساله او بهتر باشد.

نمایش باینری

این روش یکی از ساده ترین و گسترده ترین نوع نمایش راه حل ها در GA است. در این نوع نمایش، ژنوتیپ از رشته های بیتی تشکیل شده است.
برای برخی از مسائل که فضای راه حل شامل متغیرهای تصمیم گیری بولین مانند بله یا نه می باشد، نمایش دودویی طبیعی است. برای نمونه، در مساله کوله پشتی (0/1 Knapsack) اگر n نوع یا آیتم وجود داشته باشد، ما می توانیم یک راه حل را با یک رشته دودویی از n عنصر نشان دهیم، در حالیکه عنصر x می گوید که آیتم x انتخاب شده است (1) یا نه (0).
Binary Representationبرای مسائل دیگر، به ویژه آنهایی که با شماره ها کار می کنند، می توانیم اعداد را با نمایش باینری خود نمایش دهیم. مشکل این نوع رمزگذاری این است که بیت های مختلف اهمیت زیادی دارند و بنابراین اپراتورهای برش یا تقارن و جهش می توانند پیامدهای ناخواسته ای داشته باشند. این مشکل را می توان تا حدودی با استفاده از رمزگذاری گرید حل نمود، که در آن یک تغییر در یک بیت تاثیر زیادی بر راه حل ندارد.

نمایش حقیقی

برای مسائلی که ما می خواهیم ژن ها را با استفاده از متغیرهای پیوسته تعریف کنیم، طبیعی است که باید از نمایش حقیقی استفاده کنیم. البته دقت این نوع اعداد یا اعداد شناور (Floating Point) محدود به کامپیوتر است.
Real Valued Representation

نمایش صحیح

برای ژنهای با مقدار گسسته، ما همیشه نمی توانیم فضای راه حل را به باینری “بله” یا “نه” محدود کنیم. برای مثال، اگر ما می خواهیم چهار جهت شمال، جنوب، شرق و غرب را رمزگذاری کنیم می توانیم آنها را به صورت {0،1،2،3} نمایش دهیم. در چنین مواردی نمایش راه حل بصورت عدد صحیح مطلوب است.
Integer Representation

نمایش جایگشتی

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

صفحه قبلی – صفحه بعدی

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *