پژوهش دانشگاهی – طراحی مدل یکپارچه تشکیل سلول با چیدمان سلول و زمانبندی عملیات ها با در نظر گرفتن …

فیزیک: حل معادلات غیر خطی برای انطباق سطوح پتانسیل ملکولی
تجارت: جستجو برای قوانین پیشگویی کننده سود شرکتها
در ادامه پس از آشنایی با مفاهیم اولیه الگوریتم ژنتیک، مراحل اجرای آن بیان می شود.

منبع فایل کامل این پایان نامه این سایت pipaf.ir است

۳-۲-۱-۲- زمینه های بیولوژیکی

بدن تمام موجودات زنده متشکل از سلول می باشد. در هر سلول مجموعه ای از موجودات هم شکل بنام کروموزوم وجود دارند. کروموزومها، رشته های DNA می باشند که هر کدام متشکل از تعدادی ژن یا همان بلوک های DNA هستند. هر ژن یک پروتئین خاص یا در واقع یک خصیصه را کد می کند. به عنوان مثال رنگ چشم می تواند یک خصیصه باشد. مجموعه های ممکن برای یک خصیصه آلل نامیده می شوند. هر ژن در کروموزوم موقعیت خاص خودش را دارد که این موقعیت خاص لوکوس نام دارد. مجموعه کامل همه کروموزومها ژنوم نامیده می شود و یک مجموعه خاص از ژنها در ژنوم، ژنوتیپ نام دارد. ژنوتیپها بعد از تکامل بیشتر به فنوتیپها که همان خصوصیات فیزیکی و روانی مانند رنگ چشم یا هوش و غیره می باشند، تبدیل می شوند.

۳-۲-۱-۳- فضای جستجو

وقتی که ما به دنبال حل مسالهای هستیم، معمولا به دنبال جوابهایی میگردیم که بهترین جوابها در میان مجموعه جوابهای موجود باشند. فضای تمام جوابهای قابل قبول، فضای جستجو نامیده میشود.
هر نقطه در فضای جستجو یک جواب قابل قبول را نشان می دهد. هر جواب قابل قبول می تواند بر اساس ارزش یا مطلوبیتش برای مسأله مشخص گردد. هدف از پیدا کردن جواب، که میتواند یک نقطه یا بیشتر در میان جوابهای قابل قبول باشد، پیدا کردن یک نقطه یا بیشتر در فضای جستجو است.
جستجو برای یک جواب، معادل جستجو برای حدود نهایی (حداقل یا حداکثر) در فضای جواب است. کل فضای جستجو از طریق زمان حل یک مساله قابل شناسایی است، اما معمولا نقاط کمی از آن فضا برای ما مشخص است و ما از طریق ایجاد نقاط دیگر به پیدا کردن جوابها ادامه میدهیم. شکل۳-۲ نمونهای از فضای جواب را نشان می دهد.
شکل ۳‑۱٫ نمونه ای از فضای جواب
مشکلی که در اینجا وجود دارد این است که جستجو میتواند خیلی پیچیده باشد. مشخص نیست که کجاها باید به دنبال جواب گشت و اصلاً از کجا باید شروع کرد. روشهای زیادی برای پیدا کردن جواب مناسب (نه لزوماً بهترین) وجود دارد که به عنوان مثال میتوان به روشهای صعود از تپه، جستجوی محدود، شبیه سازی آبکاری فلزات (SA) و الگوریتم ژنتیک اشاره کرد. جوابهایی که از این طریق بدست میآیند، معمولاً جوابهای خوبی هستند، چون واقعاً اثباتی برای اینکه کدام یکی بهینه واقعی است وجود ندارد.

۳-۲-۱-۴- مسائل NP

اساساً، بسیاری از مسائل بهینهسازی سخت میباشند. در اصل، یک مسأله «سخت» مسألهای است که نمی توان برای آن تضمین کرد که بهترین جواب را در یک مقدار منطقی از زمان به دست آورد.
مسائل غیر چند جملهای (NP) نمونه هایی از مسائل سخت میباشند که از طریق روشهای سنتی قابل حل نیستند. برای شناخت الگوریتمهای سریع یا چند جمله ای مراحل زیادی باید سپری شود و از طرفی مسائلی هست که بصورت الگوریتمی قابل حل نیستند. برای بعضی مسائل ثابت شده است که حل آنها در یک زمان چند جملهای امکان پذیر نیست. البته وقتی ما یک جواب را نداریم، پیدا کردنش خیلی سخت است، اما اگر ما جواب را داشته باشیم، بررسی کردن جواب کار بسیار سادهتری می باشد. این مطلب منجر به مسائل NP_complete می شود. حالت NP_complete بیشتر مربوط به مسائل تصمیم گیری است. NP به معنای یک چند جمله ای غیرقطعی است و این بدین معناست که می توان بوسیله الگوریتمهای غیر قطعی در یک زمان NP جواب را حدس زد وسپس آن را بررسی نمود. اگر ما یک ماشین حدس زن داشته باشیم، آنگاه قادر به پیدا کردن جواب در یک زمان مقبول می باشیم.
مطالعه و بررسی مسائل NP_complete بخاطر سادگی اعمال شده به مسأله می باشد، چون جواب می تواند بله یا خیر باشد. بخاطر وجود کارها و مسائلی با خروجیهای بسیار پیچیده، یک گروه از مسائل، مسائل NP-hardنامیده می شوند. این گروه از مسائل به محدودیت گروه مسائل NP-hard نیستند. حالت NP-hard بیشتر مربوط به مسائل بهینه سازی است. یکی از خصوصیات بارز مسائل NP این است که هنگام رویارویی با این مسائل، الگوریتم یا الگوریتمهایی را که برای حل این مسائل مناسب هستند براحتی میتوان یافت و کار آنها تنها جستجوی تمامی جوابهای ممکن است. اما مشکل این است که این الگوریتمها بسیار کند هستند و حتی گاهی اوقات برای یک بیت اضافه تر به منظور ایجاد نمونه ای بزرگتر، الگوریتم غیر قابل استفاده میشود.
امروزه کسی نمی داند که آیا الگوریتمهای دقیق سریعتری هم وجود دارد یا خیر؟ اثبات یا عدم اثبات این مطلب جزء وظایف خطیر محققان امروزی می باشد. امروزه خیلی از محققین بر این باورند که چنین الگوریتمی وجود ندارد و بنابراین به دنبال یافتن بعضی روشهای جایگزین یا فرعی هستند که الگوریتم ژنتیک یکی از این روشها می باشد.

۳-۲-۱-۵- مفاهیم اولیه در الگوریتم ژنتیک

۳-۲-۱-۵-۱- اصول پایه

الگوریتمهای ژنتیکی براساس تئوری تکاملی داروین می باشند و جواب مسالهای که از طریق الگوریتم ژنتیک حل می شود به طور مرتب بهبود مییابد. الگوریتم ژنتیک با یک مجموعه از جوابها که از طریق کرموزومها نشان داده میشوند شروع میشود. این مجموعه جوابها جمعیت اولیه نام دارند. در این الگوریتم جوابهای حاصل از یک جمعیت برای تولید جمعیت بعدی استفاده می شوند. در این فرایند امید است که جمعیت جدید نسبت به جمعیت قبلی بهتر باشد. انتخاب بعضی از جوابها از میان کل جوابها (والدین[۸۰]) به منظور ایجاد جوابهای جدید یا همان فرزندان[۸۱] بر اساس میزان مطلوبیت آنها میباشد. طبیعی است که جوابهای مناسبتر شانس بیشتری برای تولید مجدد داشته باشند. این فرایند تا برقراری شرطی که از پیش تعیین شده است (مانند تعداد جمعیتها یا میزان بهبود جواب) ادامه می یابد.

۳-۲-۱-۵-۲- شمای کلی الگوریتم ژنتیک

۱) تولید جمعیت تصادفی شامل n کروموزوم
۲) بررسی تابع مطلوبیت[۸۲] f(x) هر کروموزوم x در جمعیت
۳) ایجاد یک جمعیت جدید بر اساس تکرار قدمهای زیر
۳-۱) انتخاب دو کروموزوم والد از یک جمعیت بر اساس میزان مطلوبیت آنها
۳-۲) درنظر گرفتن مقدار مشخصی برای احتمال اعمال عملگر تقاطع[۸۳] و سپس انجام عملیات ترکیب بر روی والدین به منظور ایجاد فرزندان. اگر هیچ ترکیب جدیدی صورت نگیرد فرزندان همان والدین خواهند بود.
۳-۳) در نظر گرفتن احتمال جهش[۸۴] و سپس تغییر فرزندان در هر لوکوس
۳-۴) جایگزینی فرزندان جدید در جمعیت جدید
۴) استفاده از جمعیت جدید برای اجراهای بعدی الگوریتم
۵) توقف اجرای الگوریتم در صورت مشاهده شرایط توقف و برگرداندن بهترین جواب در جمعیت فعلی
۶) رفتن به قدم ۲٫
همانطورکه مشاهده میشود، اصول پایهای الگوریتم ژنتیک بسیار عمومی است. بنابراین برای مسائل مختلف فاکتورهای مختلف زیادی وجود دارد که باید مورد بررسی قرار گیرد. اولین سؤال این است که ایجاد یک کروموزوم چگونه است؟ یا اینکه چه نوعی از کدینگ انتخاب شود؟
دو عملگر بسیار مهم و پایهای الگوریتم ژنتیک عملگرهای تقاطع وجهش میباشند. سؤال بعدی این است که برای ترکیب والدین به منظور ایجاد فرزندان جدید چگونه والدین را انتخاب کنیم. این کار به طرق مختلف میتواند صورت بگیرد، اما ایده اصلی در تمامی آنها این است که والدین بهتر انتخاب شوند، به این امید که والدین بهتر باعث ایجاد فرزندان بهتر شوند.
مسألهای که ممکن است در اینجا مورد سؤال باشد این است که اگر جمعیت جدید تنها از طریق فرزندان جدید ایجاد شود، این فرایند منجر به حذف بهترین کرموزومهای نسل قبل میگردد. برای جلوگیری از این پیشامد، همیشه بهترین جواب نسل قبل را بدون هیچ تغییری به نسل جدید منتقل میکنیم.

۳-۲-۱-۵-۳- کد کردن[۸۵]

الگوریتم ژنتیک بجای اینکه بر روی پارامترها یا متغیرهای مساله کار کند، با شکل کد شده آنها بطور مناسب سروکار دارد. روشهای کدگذاری متداول در الگوریتم ژنتیک عبارتند از کدینگ باینری[۸۶]، کدینگ جهشی[۸۷]، کدینگ ارزشی[۸۸] و کدینگ درختی[۸۹]. تعداد بیتهایی که برای کدگذاری متغیرها استفاده می شود وابسته به دقت مورد نظر برای جوابها، محدوده تغییرات پارامترها و رابطه بین متغیرها می باشد.

۳-۲-۱-۵-۴- روش های کدینگ