منبع پایان نامه ارشد درباره الگوریتمهای ژنتیک و الگوریتم ژنتیک

خاصیت مهم الگوریتم ژنتیک، مقاوم بودن آن است، بطوریکه در آن یک تعادل انعطافپذیر بین کارایی و خصوصیات لازم برای بقا در محیطها و شرایط گوناگون وجود دارد. بطور کلی هر چه سیستم مصنوعی از نظر مقاومت در درجه بالاتری باشد، هزینه طراحی مجدد آن کاهش یافته و حتی حذف میگردد. در واقع چنانچه میزان سازگاری سیستمی افزایش یابد، آن سیستم قادر خواهد بود که به مدت طولانیتر و به نحو مطلوبتری به کار بپردازد. در سیستمهای بیولوژیک میزان انعطاف پذیری، مقاومت و کارایی به شکل شگفتانگیزی زیاد است. سازگاری، بقا، خودترمیمی، هدایت و تولید مثل از دیگر ویژگیهای خاص سیستمهای طبیعی و بیولوژیک می باشد که مهندسان در صددند تا در سیستمهای مصنوعی از آنها تقلید کنند. اما بطور کلی جایی که کارکرد مقاوم مورد نیاز باشد، طبیعت بهتر عمل خواهد کرد.
Widget not in any sidebars

از الگوریتم ژنتیک در کاربردهای مختلفی مثل بهینهسازی توابع، شناسایی سیستمها و پردازش تصویر استفاده شده است. در زیر برخی از موارد استفاده از الگوریتم ژنتیک در علوم مختلف نشان داده شده است.
بیولوژی: شبیه سازی تکامل یک جمعیت از ارگانیسم های تک سلولی
علوم کامپیوتر: جستجو برای تکامل تابع ارزشیابی
مهندسی: شناسایی سیستمهای دینامیکی
فیزیک: حل معادلات غیر خطی برای انطباق سطوح پتانسیل ملکولی
تجارت: جستجو برای قوانین پیشگویی کننده سود شرکتها
در ادامه پس از آشنایی با مفاهیم اولیه الگوریتم ژنتیک، مراحل اجرای آن بیان می شود.
3-2-1-2- زمینه های بیولوژیکی
بدن تمام موجودات زنده متشکل از سلول می باشد. در هر سلول مجموعه ای از موجودات هم شکل بنام کروموزوم وجود دارند. کروموزومها، رشته های DNA می باشند که هر کدام متشکل از تعدادی ژن یا همان بلوک های DNA هستند. هر ژن یک پروتئین خاص یا در واقع یک خصیصه را کد می کند. به عنوان مثال رنگ چشم می تواند یک خصیصه باشد. مجموعه های ممکن برای یک خصیصه آلل نامیده می شوند. هر ژن در کروموزوم موقعیت خاص خودش را دارد که این موقعیت خاص لوکوس نام دارد. مجموعه کامل همه کروموزومها ژنوم نامیده می شود و یک مجموعه خاص از ژنها در ژنوم، ژنوتیپ نام دارد. ژنوتیپها بعد از تکامل بیشتر به فنوتیپها که همان خصوصیات فیزیکی و روانی مانند رنگ چشم یا هوش و غیره می باشند، تبدیل می شوند.
3-2-1-3- فضای جستجو
وقتی که ما به دنبال حل مسالهای هستیم، معمولا به دنبال جوابهایی میگردیم که بهترین جوابها در میان مجموعه جوابهای موجود باشند. فضای تمام جوابهای قابل قبول، فضای جستجو نامیده میشود.
هر نقطه در فضای جستجو یک جواب قابل قبول را نشان می دهد. هر جواب قابل قبول می تواند بر اساس ارزش یا مطلوبیتش برای مسأله مشخص گردد. هدف از پیدا کردن جواب، که میتواند یک نقطه یا بیشتر در میان جوابهای قابل قبول باشد، پیدا کردن یک نقطه یا بیشتر در فضای جستجو است.
جستجو برای یک جواب، معادل جستجو برای حدود نهایی (حداقل یا حداکثر) در فضای جواب است. کل فضای جستجو از طریق زمان حل یک مساله قابل شناسایی است، اما معمولا نقاط کمی از آن فضا برای ما مشخص است و ما از طریق ایجاد نقاط دیگر به پیدا کردن جوابها ادامه میدهیم. شکل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- اصول پایه
الگوریتمهای ژنتیکی براساس تئوری تکاملی داروین می باشند و جواب مسالهای که از طریق الگوریتم ژنتیک حل می شود به طور مرتب بهبود مییابد. الگوریتم ژنتیک با یک مجموعه از جوابها که از طریق کرموزومها نشان داده میشوند شروع میشود. این مجموعه جوابها جمعیت اولیه نام دارند. در این الگوریتم جوابهای حاصل از یک جمعیت برای تولید جمعیت بعدی استفاده می شوند. در این فرایند امید است که جمعیت جدید نسبت به جمعیت قبلی بهتر باشد. انتخاب بعضی از جوابها از میان کل جوابها (والدین) به منظور ایجاد جوابهای جدید یا همان فرزندان بر اساس میزان مطلوبیت آنها میباشد. طبیعی است که جوابهای مناسبتر شانس بیشتری برای تولید مجدد داشته باشند. این فرایند تا برقراری شرطی که از پیش تعیین شده است (مانند تعداد جمعیتها یا میزان بهبود جواب) ادامه می یابد.