است.
جستجو برای یک جواب، معادل جستجو برای حدود نهایی (حداقل یا حداکثر) در فضای جواب است. کل فضای جستجو از طریق زمان حل یک مساله قابل شناسایی است، اما معمولا نقاط کمی از آن فضا برای ما مشخص است و ما از طریق ایجاد نقاط دیگر به پیدا کردن جوابها ادامه میدهیم. شکل3-2 نمونهای از فضای جواب را نشان می دهد.
شکل 31. نمونه ای از فضای جواب
مشکلی که در اینجا وجود دارد این است که جستجو میتواند خیلی پیچیده باشد. مشخص نیست که کجاها باید به دنبال جواب گشت و اصلاً از کجا باید شروع کرد. روشهای زیادی برای پیدا کردن جواب مناسب (نه لزوماً بهترین) وجود دارد که به عنوان مثال میتوان به روشهای صعود از تپه، جستجوی محدود، شبیه سازی آبکاری فلزات (SA) و الگوریتم ژنتیک اشاره کرد. جوابهایی که از این طریق بدست میآیند، معمولاً جوابهای خوبی هستند، چون واقعاً اثباتی برای اینکه کدام یکی بهینه واقعی است وجود ندارد.
3-2-1-4- مسائل NP
اساساً، بسیاری از مسائل بهینهسازی سخت میباشند. در اصل، یک مسأله «سخت» مسألهای است که نمی توان برای آن تضمین کرد که بهترین جواب را در یک مقدار منطقی از زمان به دست آورد.
مسائل غیر چند جملهای (NP) نمونه هایی از مسائل سخت میباشند که از طریق روشهای سنتی قابل حل نیستند. برای شناخت الگوریتمهای سریع یا چند جمله ای مراحل زیادی باید سپری شود و از طرفی مسائلی هست که بصورت الگوریتمی قابل حل نیستند. برای بعضی مسائل ثابت شده است که حل آنها در یک زمان چند جملهای امکان پذیر نیست. البته وقتی ما یک جواب را نداریم، پیدا کردنش خیلی سخت است، اما اگر ما جواب را داشته باشیم، بررسی کردن جواب کار بسیار سادهتری می باشد. این مطلب منجر به مسائل NP_complete می شود. حالت NP_complete بیشتر مربوط به مسائل تصمیم گیری است. NP به معنای یک چند جمله ای غیرقطعی است و این بدین معناست که می توان بوسیله الگوریتمهای غیر قطعی در یک زمان NP جواب را حدس زد وسپس آن را بررسی نمود. اگر ما یک ماشین حدس زن داشته باشیم، آنگاه قادر به پیدا کردن جواب در یک زمان مقبول می باشیم.
مطالعه و بررسی مسائل NP_complete بخاطر سادگی اعمال شده به مسأله می باشد، چون جواب می تواند بله یا خیر باشد. بخاطر وجود کارها و مسائلی با خروجیهای بسیار پیچیده، یک گروه از مسائل، مسائل NP-hardنامیده می شوند. این گروه از مسائل به محدودیت گروه مسائل NP-hard نیستند. حالت NP-hard بیشتر مربوط به مسائل بهینه سازی است. یکی از خصوصیات بارز مسائل NP این است که هنگام رویارویی با این مسائل، الگوریتم یا الگوریتمهایی را که برای حل این مسائل مناسب هستند براحتی میتوان یافت و کار آنها تنها جستجوی تمامی جوابهای ممکن است. اما مشکل این است که این الگوریتمها بسیار کند هستند و حتی گاهی اوقات برای یک بیت اضافه تر به منظور ایجاد نمونه ای بزرگتر، الگوریتم غیر قابل استفاده میشود.
امروزه کسی نمی داند که آیا الگوریتمهای دقیق سریعتری هم وجود دارد یا خیر؟ اثبات یا عدم اثبات این مطلب جزء وظایف خطیر محققان امروزی می باشد. امروزه خیلی از محققین بر این باورند که چنین الگوریتمی وجود ندارد و بنابراین به دنبال یافتن بعضی روشهای جایگزین یا فرعی هستند که الگوریتم ژنتیک یکی از این روشها می باشد.
3-2-1-5- مفاهیم اولیه در الگوریتم ژنتیک
3-2-1-5-1- اصول پایه
الگوریتمهای ژنتیکی براساس تئوری تکاملی داروین می باشند و جواب مسالهای که از طریق الگوریتم ژنتیک حل می شود به طور مرتب بهبود مییابد. الگوریتم ژنتیک با یک مجموعه از جوابها که از طریق کرموزومها نشان داده میشوند شروع میشود. این مجموعه جوابها جمعیت اولیه نام دارند. در این الگوریتم جوابهای حاصل از یک جمعیت برای تولید جمعیت بعدی استفاده می شوند. در این فرایند امید است که جمعیت جدید نسبت به جمعیت قبلی بهتر باشد. انتخاب بعضی از جوابها از میان کل جوابها (والدین80) به منظور ایجاد جوابهای جدید یا همان فرزندان81 بر اساس میزان مطلوبیت آنها میباشد. طبیعی است که جوابهای مناسبتر شانس بیشتری برای تولید مجدد داشته باشند. این فرایند تا برقراری شرطی که از پیش تعیین شده است (مانند تعداد جمعیتها یا میزان بهبود جواب) ادامه می یابد.
3-2-1-5-2- شمای کلی الگوریتم ژنتیک
1) تولید جمعیت تصادفی شامل n کروموزوم
2) بررسی تابع مطلوبیت82 f(x) هر کروموزوم x در جمعیت
3) ایجاد یک جمعیت جدید بر اساس تکرار قدمهای زیر
3-1) انتخاب دو کروموزوم والد از یک جمعیت بر اساس میزان مطلوبیت آنها
3-2) درنظر گرفتن مقدار مشخصی برای احتمال اعمال عملگر تقاطع83 و سپس انجام عملیات ترکیب بر روی والدین به منظور ایجاد فرزندان. اگر هیچ ترکیب جدیدی صورت نگیرد فرزندان همان والدین خواهند بود.
3-3) در نظر گرفتن احتمال جهش84 و سپس تغییر فرزندان در هر لوکوس
3-4) جایگزینی فرزندان جدید در جمعیت جدید
4) استفاده از جمعیت جدید برای اجراهای بعدی الگوریتم
5) توقف اجرای الگوریتم در صورت مشاهده شرایط توقف و برگرداندن بهترین جواب در جمعیت فعلی
6) رفتن به قدم 2.
همانطورکه مشاهده میشود، اصول پایهای الگوریتم ژنتیک بسیار عمومی است. بنابراین برای مسائل مختلف فاکتورهای مختلف زیادی وجود دارد که باید مورد بررسی قرار گیرد. اولین سؤال این است که ایجاد یک کروموزوم چگونه است؟ یا اینکه چه نوعی از کدینگ انتخاب شود؟
دو عملگر بسیار مهم و پایهای الگوریتم ژنتیک عملگرهای تقاطع وجهش میباشند. سؤال بعدی این است که برای ترکیب والدین به منظور ایجاد فرزندان جدید چگونه والدین را انتخاب کنیم. این کار به طرق مختلف میتواند صورت بگیرد، اما ایده اصلی در تمامی آنها این است که والدین بهتر انتخاب شوند، به این امید که والدین بهتر باعث ایجاد فرزندان بهتر شوند.
مسألهای که ممکن است در اینجا مورد سؤال باشد این است که اگر جمعیت جدید تنها از طریق فرزندان جدید ایجاد شود، این فرایند منجر به حذف بهترین کرموزومهای نسل قبل میگردد. برای جلوگیری از این پیشامد، همیشه بهترین جواب نسل قبل را بدون هیچ تغییری به نسل جدید منتقل میکنیم.
3-2-1-5-3- کد کردن85
الگوریتم ژنتیک بجای اینکه بر روی پارامترها یا متغیرهای مساله کار کند، با شکل کد شده آنها بطور مناسب سروکار دارد. روشهای کدگذاری متداول در الگوریتم ژنتیک عبارتند از کدینگ باینری86، کدینگ جهشی87، کدینگ ارزشی88 و کدینگ درختی89. تعداد بیتهایی که برای کدگذاری متغیرها استفاده می شود وابسته به دقت مورد نظر برای جوابها، محدوده تغییرات پارامترها و رابطه بین متغیرها می باشد.
3-2-1-5-4- روش های کدینگ
1. کدینگ باینری
این نوع کدینگ، متداولترین نوع کدینگ می باشد. در این روش کدگذاری، هر کروموزوم یک رشته از بیتهای شامل ٠ و ١ می باشد. کدینگ باینری می تواند حالت های زیادی را پوشش دهد، حتی در مواردی که تعداد آلل ها کم باشد.
شکل 32. کدینگ باینری
از طرف دیگر این نوع کدینگ برای خیلی از مسائل حالت طبیعی ندارد و اغلب اوقات لازم است که بعد از تقاطع و جهش اصلاحاتی صورت بگیرد.
2. کدینگ جهشی
این نوع کدینگ میتواند در مسائل ترتیبی نظیر مساله فروشنده دوره گرد یا مساله ترتیب کارها بکار رود. در کدینگ جهشی، هر کروموزوم یک رشته از اعداد میباشد. شکل زیر نمونه ای از این نوع کدینگ را نشان میدهد.
شکل 33. کدینگ جهشی
کدینگ جهشی تنها برای مسائل ترتیبی مفید است. حتی برای همین مسائل نیز گاهی اوقات باید تقاطعها و جهشهای اصلاحی به منظور ایجاد کروموزومهای سازگار و مناسب انجام شود.
3. کدینگ ارزشی
این نوع کدینگ درمسائلی که در آنها مقادیر پیچیده نظیر اعداد حقیقی بکار میروند استفاده میشود. استفاده از کدینگ باینری برای چنین مسائلی بسیار سخت میباشد. در کدینگ ارزشی هر ژن یک کروموزوم ارزش خاصی دارد. این پارامتر با ارزش میتواند عدد، حرف یا کلمه باشد. دراین نوع کدینگ نیاز به توسعه عملگرهای جابجایی و جهش جدیدی برای مسائل خاص میباشد.
شکل 34. کدینگ ارزشی
4. کدینگ درختی
کدینگ درختی در برنامه های تکاملی به منظور برنامه ریزی تکاملی بکار میرود. در کدینگ درختی هرکروموزوم یک درخت از اشیائی نظیر توابع یا دستورها در زبان برنامه نویسی میباشد. شکل زیر دو نمونه از این کروموزومها را نشان میدهد. این نوع کدینگ برای برنامههای تکاملی بسیار عالی است.
شکل 36. کدینگ درختی
نکته ای که در انتهای این قسمت باید به آن توجه کرد این است که در الگوریتم های ژنتیکی کدینگ یک رابطه بین فضای کدینگ و فضای جوابها می باشد بطوریکه الگوریتم ژنتیک عملیات تکاملی را بطور متناوب در این دو فضا انجام می دهد (شکل 3-7). انتخاب طبیعی نیز به عنوان یک رابطه بین کروموزومها و عملکرد جوابهای کدشده آنها می باشد.
شکل 37. فضای کدینگ وفضای جواب
3-2-1-5-5- کروموزوم
رشته یا دنبالهای از بیتها که به عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مساله مورد نظر میباشد را کروموزوم میگویند. در حقیقت بیتهای یک کروموزوم، نقش ژنها را در طبیعت بازی میکنند.
3-2-1-5-6- جمعیت90
مجموعهای از کروموزومها را جمعیت گویند. یکی از ویژگیهای ژنتیک این است که به جای تمرکز بر روی یک نقطه از فضای جستجو یا یک کروموزوم، بر روی جمعیتی از کروموزومها کار میکند. بدین ترتیب در هر مرحله، الگوریتم دارای جمعیتی از کروموزومها بوده که خواص مورد نظر را بیشتر از جمعیت مرحله قبل دارا میباشد. هر جمعیت یا یک نسل از کروموزومها، دارای یک اندازه میباشد که به اندازه جمعیت91 معروف است. اندازه جمعیت معرف تعداد کروموزومهای موجود در جمعیت یا یک نسل است.
3-2-1-5-7- مقدار برازندگی92
مناسب بودن یا نبودن جواب، با معیاری که از تابع هدف بدست میآید، سنجیده میشود. هر چه که یک جواب مناسبتر باشد، مقدار برازندگی بزرگتری دارد. برای آنکه شانس بقای چنین جوابی بیشتر شود، احتمال بقای آن، متناسب با مقدار برازندگی آن در نظر گرفته میشود. بنابراین کروموزمی که برازنده ترین است با احتمال بیشتری در تولید فرزندان شرکت میکند و دنبالههای بیشتری از آن به وجود میآید. به عنوان مثال چنانچه هدف بیشینه کردن یک تابع باشد، مقدار برازندگی، یک تابع صعودی از تابع هدف در نظر گرفته میشود و اگر هدف یافتن مقدار کمینه یک تابع باشد، عدد برازندگی، یک تابع نزولی از آن قرار داده میشود. معمولاً در مواردی که امکان دارد، تابع برازندگی را در فاصله [1و0] نرمالیزه میکنند.
3-2-1-5-8- عملگر تقاطع
این عملگر بر روی یک جفت از کروموزوم ها عمل می کند و میتواند به صورت تک نقطهای، چند نقطهای و یکنواخت باشد. عملگر تقاطعی تک نقطهای، دو کروموزوم را به طور تصادفی از یک نقطه شکسته و بخش های شکسته دو کروموزوم را جابجا می کند. بدین ترتیب دو کروموزوم جدید بدست می آید. به کروموزومهای اولیه، کروموزومهای”والد“و به کروموزوم های حاصل شده از عمل جابجایی و عمل جهش، کروموزوم”فرزند“میگویند.
شکل 38. مثالی از عمل جابجایی تک نقطه ای
عملگر تقاطع با احتمال Pc بر روی کروموزوم های والد عمل میکند. بدین معنی که با احتمال Pcعمل تقاطع انجام میگیرد. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقًا مشابه والدین خواهند بود (البته این مطلب بدین معنی نیست که نسل جدید همان نسل قبلی است). در صورتی که عمل تقاطع صورت بگیرد، فرزندان از قسمتهای مختلف کروموزومهای والد ساخته میشوند. اگر احتمال تقاطع ١ باشد، تمامی فرزندان از طریق عمل تقاطعی ایجاد میشوند. عملیات تقاطع با این هدف انجام میشود که کروموزومهای جدید در بردارنده قسمتهای مناسب و خوب کروموزومهای قبلی خواهند بود و شاید این کروموزومهای جدید

مطلب مرتبط :   پایان نامه با کلید واژگانچشم انداز، طلاق، رجوع به متخصص

Written by 

دیدگاهتان را بنویسید