طرح های پژوهشی انجام شده درباره بررسی آلودگی نیترات در آبهای زیرزمینی بخشی از استان ... |
تعیین نحوه نمایش یا کدبندی نقاط فضای جستجو: در این مرحله به هر حل از فضای جستجو یک رشته اختصاص یافته و هر رشته در واقع شامل متغییرهای کد شدهای است که در مسئله مورد نظر وجود دارد. نحوه نمایش در واقع نوعی نگاشت از فضای جستجو به فضای رشتههائی با طول L که با مجموعه الفبایی n کاراکتری ساخته شده اند، بوده است. هر رشته که نشان دهنده یک نقطه از فضای حل است، معادل عبارت ژنوتیپ[۱۲۲] در سیستمهای طبیعی است که هر ژنوتیپ به معنی ترکیب ژنتیکی خاصی از موجود زنده است.
تعریف میزان برازندگی: پس از اینکه تابع هدف هر رشته با توجه به خصوصیات مسئله مورد نظر تعیین شد، مقدار برازندگی رشتهها محاسبه شده است. عدد برازندگی هر رشته، عددی مثبت است که در مرحله انتخاب با توجه به مقدار برازندگی هر رشته، احتمال انتخاب شدن آن تعیین شده و با مکانیزم دیسک گردان رشتهها انتخاب شدهاند (بدیهی است رشتههایی که عدد برازندگی بیشتری دارند به تعداد بیشتری نیز انتخاب گردیدهاند). در سیستمهای طبیعی، هر ژنوتیپ (رشته)، دارای رفتار خاصی است که به آن فنوتیپ[۱۲۳] گفته شده است. در واقع فنوتیپ، نمود ظاهری ژنوتیپ است. پس بطور کلی میتوان گفت که عدد برازندگی، یک نگاشت از نقاط فضای نمایش به فضای اعداد حقیقی است که وابسته به مسئله مورد نظر است.
تعیین پارامترها و متغیرهای مربوط به الگوریتم : پارامترهای الگوریتم ژنتیک عبارتند از:
الف) میزان جمعیت و ماکزیمم تعداد تکرار (تعداد نسلها)
ب) نرخ احتمال عملگرهای ترکیب و جهش
مشخص کردن شرط پایان تکرار و نحوه انتخاب خروجی الگوریتم: شرط خاتمهی الگوریتم ژنتیک را میتوان تعداد مشخصی تکرار یا رسیدن به مقدار معینی از برازندگی قرار داد و بهترین رشته از آخرین نسل را میتوان بعنوان خروجی در نظر گرفت.
۱-۳۳ نمودار گردشی اجرای الگوریتم ژنتیک
مطابق شکل (۱-۶) در شروع اجرای الگوریتم، جمعیتی از رشتهها با تعداد مشخص P بطور تصادفی ایجاد شدهاند. در سیکل داخلی هر یک از رشتهها دیکد شده و مقدار تابع هدف برای آن بدست آمده است و سپس مقادیر بدست آمده تابع هدف در تعیین عدد برازندگی رشتهها استفاده شده است. اگر شرط یا شرایط توقف ارضاء شد، بهترین رشته بعنوان جواب بهینه انتخاب شده است. در غیر اینصورت P رشته با عدد برازندگی بیشتر بطور تصادفی انتخاب شده و برای جستجو و کنکاش در فضای حل، عملگرهای ترکیب و جهش روی درصدی از جمعیت رشتهها اعمال گردیده و سپس با جمعیت رشته های جدیدی، الگوریتم تکرار شده تا اینکه شرط توقف برقرار شود.
خیر
تولید P رشته بطور تصادفی بعنوان جمعیت اولیه
تعیین تابع هدف هر رشته از جمعیت
تعیین عدد برازندگی براساس تابع هدف رشته
آیا شرط توقف برقرار شده
بله
انتخاب P رشته با عدد برازندگی بیشتر بطور تصادفی
اعمال عملگرترکیب روی درصد از رشته های جمعیت
اعمال عملگر جهش روی رشتههایی که عملگر ترکیب بر روی آنها اعمال شده است
انتخاب بهترین رشته آخرین نسل
شکل (۱-۶) نمودار گردشی اجرای الگوریتم ژنتیک
در تشبیه طبیعی، هر دور محاسباتی معادل یک دوره زمانی مشخص است و معرف نرخ تولید مثل و مرگ و میر این دوره زمانی است. در این مدلسازی برای ثابت ماندن جمعیت در هر یک از دوره های زمانی، تعداد تولید مثل و مرگ و میر یکسان در نظر گرفته شده است. پارامترهای طراحی و یا تابع هدف نیز مشابه شرایط زیست محیطی است که موجود زنده خود را با آن تطبیق داده است.
۱-۳۴ مزایای الگوریتم ژنتیک نسبت به روشهای دیگر بهینهسازی
الگوریتم ژنتیک دارای ویژگیهای منحصر به فردی است که آن را نسبت به روشهای دیگر بهینهسازی متمایز ساخته و از آن جمله میتوان به موارد ذیل اشاره نمود:
الف) این الگوریتم حتی در مواردی که تابع هدف در برخی از نقاط، گسسته و مشتق ناپذیر بوده، قابل استفاده بوده است لذا قادر به بهینهسازی با پارامترهای پیوسته یا گسسته بوده است. از طرف دیگر در مسائلی که دارای تابع هدف ریاضی نیستند و قیدهای مسئله نیز شکل تعریف شدهای ندارند این الگوریتم بسیار کارآمد بوده است (هررا, ۱۹۹۶).
ب) به اطلاعات مشتق تابع هدف نیاز نیست.
ج) به خوبی در کامپیوترهای موازی کار کرده است.
د) وقتی که سایر روشها بر اثر مشکلات موضعی مانند نواحی که در آنها تغییرات تابع بسیار تند یا کند است کارایی خود را از دست دادهاند، این الگوریتم قابل استفاده است. بنابراین الگوریتم ژنتیک پارامترهایی را که دارای سطح هدف بسیار پیچیده هستند بهینه کرده است.
ه) به راحتی با اطلاعات تولید شده عددی و آزمایشگاهی و یا توابع ریاضی کار کرده است.
و) یک لیست از پارامترهای بهینه و نه فقط یک حل منفرد از مسئله را فراهم آورده، بنابراین گزینههای مختلف حل یک مسئله بدست آمده است.
ز) زمانی که تابع هدف دارای چند نقطه اکسترمم محلی است از این الگوریتم میتوان برای یافتن اکسترمم کلی استفاده نمود زیرا بر خلاف روشهای دیگر بهینهسازی، جستجو را از نقاط زیاد و متفاوتی از جواب مسئله آغاز نموده، بنابراین شانس رسیدن به جواب در آن بسیار بیشتر از روشهایی بوده که از یک نقطه آغاز کرده و در یک مسیر به سمت جواب بهینه حرکت کرده است. عملگرهای ترکیب[۱۲۴] و به ویژه جهش[۱۲۵] در این الگوریتم با تغییر ناگهانی برخی رشتهها و در نتیجه جابهجا کردن قسمتی از فضای جستجو از گرفتار شدن الگوریتم در یک بهینه موضعی جلوگیری کردهاند.
ح) الگوریتم ژنتیک در هر تکرار نسخهای از بهترین رشته جمعیت را ذخیره کرده و در عین حال آن را در تولید جمعیت نسل بعد شرکت داده است. پس از تولید نسل جدید بهترین جواب آن را با بهترین جواب نسل قبل مقایسه کرده و رشته با برازندگی بهتر را به عنوان جواب تا آن مرحله ذخیره کرده است. بنابراین از اینکه جواب بهینه یک نسل در اثر عملکردهای الگوریتم دچار تغییر نامطلوب شود جلوگیری نموده و در حقیقت همیشه یک جواب موجود است که این جواب با گذشت زمان بهتر شده است.
۱-۳۵ کاربرد الگوریتم ژنتیک در علوم مختلف
برخی از مهمترین کاربردهای الگوریتم ژنتیک در علوم مختلف در جدول (۱-۸) آمده است.
جدول ۱-۸ کاربرد الگوریتم ژنتیک در علوم مختلف
زمینه | کاربرد |
کنترل | خطوط انتقال گاز – پرتاب موشک – سیستمهای تعادلی- ره گیری و… |
طراحی | طراحی هواپیما – طراحی مدارات VLSI – شبکههای ارتباطی و… |
مدیریت و برنامه ریزی | برنامه ریزی تولید – زمان بندی – تخصیص منابع و… |
روباتیک |
فرم در حال بارگذاری ...
[شنبه 1400-08-22] [ 04:48:00 ب.ظ ]
|