برازش منحنی یا Curve Fitting با الگوریتم ژنتیک
Curve-Fitting با الگوریتم‌ژنتیک
در این گزارش تجربیات و نتایج حاصل از یافتن تابع مرتبه پنجم نقاط با استفاده از الگوریتم‌ژنتیک به رشته تحریر در آمده است. این گزارش قصد بیان نقاط قوت و ضعف الگوریتم‌ژنتیک در مقابله با مسئله Curve-Fitting را دارد.
Curve-Fitting
Curve-Fitting عبارت است از یافتن یک منحنی که مبین نزدیکترین تابع به مجموعه نقاط داده شده مسئله باشد.
Curve Fitting کاربرد وسیعی در اکثر رشته های مهندسی و غیر مهندسی همچون پزشکی، اقتصاد، آموزش، آمار و بسیاری علوم دیگر دارد.
در میان الگوریتم های موجود برای حل این مسئله، الگوریتم های حل تصادفی به دلیل سربار کم، سرعت بالا و کارایی نسبتا قابل قبول از جایگاه ویژهای برخوردارند. در این گزارش سعی شده به بررسی یکی از این الگوریتم ها یعنی الگوریتم‌ژنتیک پرداخته شود.
الگوریتم‌ژنتیک
الگوریتم‌ژنتیک یکی از الگوریتم های جستجوی محلی می باشد که با الهام از طبیعت و نظربه داروینی قصد حل مسائل را دارد.
ایده اصلی این الگوریتم این است در هر مرحله برخی از راه حل ها را انتخاب نما و برای راه حل های جدید بهترین تکه های راه حل ها را با هم عوض کن و این کار را تکرار کن. در واقع هدف نگه داری و ترکیب راه حل ها یا نسلهای قوی تر و ترد نسلهای ضعیف است.
در ادامه قبل از بررسی الگوریتم به برخی تعاریف پایه پرداخته میشود:
تعاریف پایه
- جمعیت: بصورت اولیه مجموعه ای از چندین وضعیت تولید شده بصورت تصادفی است. به بیانی دیگر مجموعه ای از راه حل ها که بوسیله کروموزوم ها ارائه میشوند، جمعیت نام دارد.
- نسل: جمعیت در یک نقطه از زمان است.
- فرد: یک عنصر از جمعیت است و بصورت یک رشته از ژنها توصیف میشود. همچنین به آن راه حل یا کروموزوم یا ژنوم هم گفته میشود.
- تابع شایستگی: بهینگی یا ارزش یک راه حل را تعیین میکند. واژه شایستگی بیانگر خوبی یک راه حل است.
- تعویض: دو قسمت کردن دو راه حل در یک نقطه تعویض و عوض کردن آنها باهم میباشد. این کار دو وضعیت جدید را تولید میکند. نقطه تعویض اغلب بصورت تصادفی انتخاب میشود.
- جهش: جهش بعد از عملیات تعویض انجام شده و با درصد کمی موجب تغییر در ژنهای فرزندان میشود.
یک الگوریتم‌ژنتیک پایه
خلاصه الگوریتم به این صورت است:
- یک جمعیت تصادفی از راه حل ها را تولید کن.
- مادامی که راه حلها به اندازه کافی خوب نشده اند،کارهای زیر را انجام بده(حلقه)
- راه حل ها را مورد ارزیابی قرار بده
- راه حلهای تصادفی را انتخاب نما
- عمل تعویض را روی راه حلها انجام بده
- عمل جهش را روی راه حلها انجام بده
- راه حل های جدید را تولید کن
- پایان حلقه
بنابراین دو خصیصه مهم الگوریتم‌ژنتیک،میل به سمت جواب بهتر و تصادفی بودن آن است که آنرا به الگوریتم کارایی تبدیل میکند. همچنین مزیت این الگوریتم در استفاده حداقل از حافظه و سرعت بالای آن است.
یافتن تابع نقاط Curve-Fitting با الگوریتم‌ژنتیک
با فرض اینکه نقاط زیادی از (x,y) ها داریم. قصد داریم تا تابع چند جملهای مرتبه پنجمی را پیدا کنیم که حداقل فاصله از نقاط را داشته باشد.
در واقع هدف ما بدست آوردن مقادیر ضرایب تابع y = ax5 + bx4 + cx3 + dx2 +ex + f است.
یک تابع شایستگی خوب میتواند مقدار (actual y – predicted y) برای تمامی x هارا محاسبه کرده و مجموع آنها را بعنوان معیار شایستگی در نظر بگیرد. البته روشهای گوناگونی برای محاسبه شایستگی وجود دارد که در اینجا از این تابع استفاده شده است.
به سراغ ضرایب میرویم. هر مقداری که بتوانیم برای اعضای مجموعه [a, b, c, d, e, f] پیدا کنیم در واقع راهحلی برای مسئله یافته ایم.
برای یافتن این راه حل ها از الگوریتم زیر کمک میگیریم:
- تعدادی زیاد مثلا 100 عدد کروموزم با تعداد ژن 6 را بصورت تصادفی تولید کن. در واقع این همان جمعیت اولیه است.
- 10 تا از بهترین کروموزوم ها را نگه دار و مابقی را ترد کن
- 500 مرتبه اعمال زیر را انجام بده
- تابع شایستگی را برای همه کروموزم های مجموعه محاسبه کن
- عملیات تعویض را انجام بده. بدین صورت که ابتدا احتمال هر کروموزوم را با توجه به تابع شایستگی محاسبه کن. با توجه به احتمال انتخاب هر کروموزوم، کروموزومها را دو به دو انتخاب کن. عددی تصادفی بین 1 تا 6 انتخاب کن. این عدد محل تعویض را مشخص میکند
- عمل جهش را انجام بده.
- به مرحله 4 بازگرد
در این مسئله تعداد اعضای جمعیت اولیه 100 عضو است. نکته قابل توجه این است که بر خلاف طبیعت که نسلهای قبلی (اگر چه بسیار قوی باشند) را از بین میبرد، در این مسئله بهترین نسل مراحل قبلی باقی میماند تا اینکه در نسلهای بعدی کروموزومی بهتر از آن تولید شود. تجربه نشان داده که این ایده کارایی الگوریتم‌ژنتیک را بطور چشمگیری افزایش میدهد.
همچنین احتمال جهش در ژنهای یک کروموزوم 10 درصد است و فقط یکی از این ژنها میتواند جهش داشته باشد.
در شکلهای زیر نمونه ای از اجرای الگوریتم بر روی مجموعهای از 6 نقطه مشاهده میشود.
نتيجه
در این گزارش ویژگیهای الگوریتم‌ژنتیک مورد بررسی قرار گرفت و قدرت آن در حل مسائل بهینه سازی به خصوص Curve Fitting آشکار گشت.
دقت الگوریتم در حل این مسئله به پارامترهایی بستگی دارد. اولین نکته انتخاب جمعیت اولیه است. مسلما انتخاب کروموزوم های خوب به پیشبرد مسئله بسیار کمک خواهد کرد. بنابرابن یک راه حل خوب این است که انتخاب جمعیت نخست کاملا تصادفی نباشد، بلکه خود کاربر نیز با انتخابهایی، الگوریتم را در حل مسئله یاری دهد.
مسئله بعدی مرحله تعویض است. با توجه به نتایج بدست آمده در این نوشتار، مشخص شد که تعویض مرسوم یعنی جدا کردن قسمتی از کروموزوم و بخشیدن آن به دیگری کار را در مراحلی نه تنها آسان نمیکند، بلکه مسئله را به بن بست میکشاند. طبیعی است! زیرا کروموزوم مذکور چه بسا به خاطر تکه جدا شده توانسته تا این مرحله پیشرفت کند. راه حل منطقی در تعویض این است که هنگام تعویض، تمام تکه را جدا نکنیم بلکه با توجه به احتمال هر کروموزوم اعدادی مابین دو تکه لحاظ کرده و جایگزین کنیم.
لینک های مفید:
دیدگاهتان را بنویسید