دانلود پایان نامه ارشد درمورد الگوی حل مسئله و الگوریتم ژنتیک

2-4) تجزیه و تحلیل آماری توصیفکنندهها و انتخاب مؤثرترین آنها
داده‌های خام معمولا دچار مشکلاتی مانند نوفه، بایاس، تغییرات شدید در بازه دینامیکی و نمونه برداری هستند و استفاده از آنها به همین صورت موجب تضعیف طراحی‌های بعدی خواهد شد. بدین منظور نخست متغیرهایی را که برای 80 تا 95 درصد از مولکولها یکسان هستند، حذف میکنیم، سپس در مرحله دوم همبستگی بین متغیرها را محاسبه میکنیم. ماتریس مربع ضرایب همبستگی تشکیل داده میشود و از بین توصیفکنندههایی که حاوی اطلاعات مشابهی هستند یعنی ضریب همبستگی بالایی با یکدیگر دارند (9/0R>) یکی از آنها که معمولا نحوه محاسبه آسانتری داشته یا همبستگی بیشتری با پاسخ مورد نظر دارد، حفظ شده و بقیه حذف میگردند. از آنجا که بازه تغییرات توصیف کننده‌های محاسبه شده یکسان نبود و با در نظر گرفتن این که مقدار عددی بیشتر توصیف کننده‌ها لزوما نشان دهنده‌ی اهمیت بیشتر آنها نمی‌باشد، از روش بهنجار کردن (طبق رابطه‌ی زیر) در این پروژه جهت پیش پردازش داده‌ها استفاده شد.
(2-8)
در این رابطه
داده‌ی اصلی، داده‌ی تغییریافته، میانگین و واریانس توصیف کننده بر روی n داده می‌باشند.
پس از کاهش تعداد توصیفکنندهها، مرحله انتخاب متغیر با توجه به پاسخ دادههای QSPR / QSAR انجام میشود. روشهای مختلفی برای انتخاب مؤثرترین توصیفکنندهها وجود دارد. الگوریتم ژنتیک (GA)، یکی از موفق‌ترین روش‌های مطرح در مطالعات ساختار – فعالیت می‌باشد که در این پروژه از آن بهره گرفتیم [28].

2-4-1) الگوریتم ژنتیک (GA)
الگوریتم ژنتیک[28] تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند و از برترین روش‌های انتخاب متغیر در مطالعات کمومتریکس به شمار می‌رود. در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. مختصرا گفته می‌شود که الگوریتم ژنتیک یا (GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود ورودی است و راه ‌حل‌ها طبق یک الگو کدگذاری می‌شوند و تابع برازندگی نیز برای ارزیابی کیفیت راه حل‌های ارائه شده به کار می‌رود. هر راه حل، کاندیدی را ارزیابی می‌کند که اکثر آنها به صورت تصادفی انتخاب می‌شوند. کلا این الگوریتم‌ها از بخش‌های زیر تشکیل می‌شوند : تابع برازش، نمایش، انتخاب، تغییر.
2-4-1-1) اصول الگوریتم‌های ژنتیکی
هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد. قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین می‌روند. در حقیقت طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه)، توانسته است دائما هر نسل را از لحاظ خصوصیات مختلف ارتقاء بخشد. در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن 1 می‌تواند رنگ چشم باشد، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر. حال اگر این کروموزوم به طور کامل به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهی است که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتفاق اول جهش است. جهش، به این صورت است که بعضی ژن‌ها بصورت کاملا تصادفی تغییر می‌کنند. البته تعداد این گونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی بسیار مهم است. علاوه بر جهش اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به جهش رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این مسأله با نام تقاطع شناخته می‌شود[28] . این همان چیزیست که مثلا باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند. در مسائل انتخاب متغیر، ابتدا به صورت اتفاقی یک جمعیت از رشته‌ها (ژنوم‌ها یا راه حل‌ها) تولید می‌شود. در اینجا هررشته یک بردار سطری است که عناصر آن را متغیرها تشکیل می‌دهند و هر عنصر به صورت صفر یا یک در رشته کددار شده است. صفر برای مواقعی که متغیر وجود ندارد و یک برای موقعی که متغیر وجود دارد. برای هررشته از این جمعیت که به طور اتفاقی تولید شده مقدار شایستگی محاسبه می‌شود و بهترین رشته‌ها انتخاب می‌شوند و تحت عمل ترکیب و جهش قرار می‌گیرند. این فرآیند چند مرتبه تکرار می‌شود تا در نهایت به حل بهینه برسیم. شمای کلی از نحوهٔ عملکرد این الگوریتم در شکل زیر نمایش داده شده‌است.
جهش
زایش
فرزندان
کروموزوم
نسل جدید
جمعیت جدید
جمعیت آغازین
مورد ایده‌آل
ارزیابی سازش
انتخاب والدین برتر

این نوشته در علمی ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.