RSS  

لینک دانلود:

http://www.megaupload.com/?d=CR1MIAZR

http://www.megaupload.com/?d=MOW8G3J2

http://www.megaupload.com/?d=0KBOX7RI

 الگوریتم ژنتیک

از سال 1960 علاقه زیادی برای توسعه داد ن الگوریتم های قدرتمند برای حل مسائل بهینه سازی مشکل به وجود آمد. الگوریتم ژنتیک از اوائل سال 1970 با تلاشهای بسیار جان  هلند و شاگردانش پا به عرصه وجود گذاشت.

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

تابع برازش، نمایش، انتخاب و تغییر. که در ادامه آنها را توضیح خواهیم داد.

الگوریتم ژنتیک (GA) ، یک تکنیک برنامه نویسی است که از تکامل ژنتیک به عنوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود ورودی است و راه حل ها طبق یک الگو کدگذاری می شوند. الگوریتم های ژنتیک یکی از انواع الگوریتم های تکاملی است که از علم زیست شناسی مثل وراثت، جهش، انتخاب ناگهانی، انتخاب طبیعی و ترکیب الهام گرفته شده است.عموماً راه حل ها به صورت 2 تایی صفر و یک نشان داده می شوند ولی روشهای نمایش دیگری هم وجود دارد. تکامل از یک مجموعه کاملاً تصادفی از موجودیت ها شروع می شود و در نسل های بعدی تکرار می شود. در هر نسل، مناسب ترین ها انتخاب می شوند نه بهترین ها.

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

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

برای هر فرد، یک جفت والد انتخاب می شود. انتخاب ها به گونه ای می باشد که مناسبترین عناصر انتخاب می شوند تا حتی ضعیف ترین عناصر هم شانس انتخاب داشته باشند و از نزدیک شدن به جواب محلی جلوگیری شود.

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

دوباره جفت ها برای ترکیب انتخاب می شوند، جمعیت نسل سوم به وجود می آیند و ... این فرآیند تکرار می شود تا این که به آخرین مرحله برسیم.

بعضی از شرایط خاتمه الگوریتم های ژنتیک عبارتند از:

-        به تعداد ثابتی از نسل ها برسیم

-        بودجه اختصاص داده شده تمام شود (زمان محاسبه، پول)

-        یک فرد (فرزند تولید شده) پیدا شود که مینیمم (کمترین) ملاک را برآورده کند.

-        بیشترین درجه برازش فرزندان حاصل شود یا دیگر نتایج بهتری حاصل نشود.

-        بازرسی دستی.

1- ایده اصلی

در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه سازی های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم های او به نسل بعدی منتقل می شوند. هر ژن در این کروموزوم ها نماینده یک خصوصیت است. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهی است که در عمل چنین اتفاقی رخ نمی دهد. در واقع بصورت هم زمان دو اتفاق برای کروموزوم ها می افتد. اتفاق اول جهش است. جهش به این صورت است که بعضی ژن ها بصورت کاملاً تصادفی تغییر می کنند. البته تعداد این گونه ژن ها بسیار کم می باشد اما در هر حال این تغییر تصادفی بسیار مهم است. علاوه بر جهش اتفاق دیگری هم می افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت  به جهش رخ می دهد. این اتفاق، چسبیدن ابتدای یک کروموزوم به انتهای کروموزوم دیگر است. این مسأله با نام لقاح شناخته می شود. این همان چیزی است که مثلاً باعث می شود تا فرزندان تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن کامل فرزند به تنها یکی از والدین جلوگیری می کند.

در ابتدا تعدادی مشخص از ورودی ها،  و ... و  و  که متعلق به فضای نمونه ، X هستند را انتخاب می کنیم و آنها را در یک عدد برداری ( و ... و  و) X = نمایش می دهیم. در مهندسی نرم افزار  اصطلاحاً به آنها ارگانیسم یا کروموزوم گفته می شود. به گروه کروموزوم ها جمعیت می گوییم. در هر دوره جمعیت رشد می کند و براساس قوانین مشخصی که حاکی از تکامل زیستی است تکامل می یابند.

برای هر کروموزوم ، ما یک ارزش تناسب داریم که آن را  هم می نامیم. عناصر قویتر یا کروموزوم هایی که ارزش تناسب آنها به بهینه جمعیت نزدیک تر است شانس بیشتری برای زنده ماندن در طول دوره های دیگر و دوباره تولید شدن را دارند و ضعیفتر ها محکوم به نابودی اند. به عبارت دیگر، الگوریتم، ورودی هایی که به جواب بهینه نزدیکترند را نگه داشته و از بقیه صرف نظر می کند. یک گام مهم دیگر در الگوریتم، تولد است که در هر دوره یک بار اتفاق می افتد. محتویات دو کروموزوم جدید که ما آنها را فرزند می نامیم ایجاد کنند. این پدیده به ما اجازه می دهد تا 2 تا از بهترین ها را برای ایجاد یکی بهتر از آن ها با هم ترکیب کنیم. (تکامل). به علاوه در طول هر دوره، یک سری از کروموزوم ها ممکن است جهش یابند.

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

2- روش های نمایش

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

سومین روش برای نمایش صفات در یک GA، رشته ای از حروف است که هر حرف نمایش دهنده یک خصوصیت می باشد.

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

3- روشهای انتخاب

روش های مختلفی برای الگوریتم های ژنتیک وجود دارد که می توان برای انتخاب ژنوم ها از آنها استفاده کرد. امام روش های لیست شده در پایین بعضی از معمولترین روش ها هستند.

-         نخبه گزینی: مناسبترین عضو هر اجتماع انتخاب می شود.

-   انتخاب چرخان: یک روش انتخاب است که در آن عنصری که عدد برازش (تناسب) بیشتری داشته باشد، انتخاب می شود.

-        مقیاس گزینی: به موازات افزایش متوسط عدد برازش جامعه، سنگینی انتخاب هم بیشتر و جزئی تر می شود. این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند و فقط تفاوت های کوچکی آنها را از هم تفکیک می کند.

-    انتخاب رقابتی: یک زیر مجموعه از صفات یک جامعه انتخاب می شوند و اعضای آن مجموعه با هم رقابت می کنند و سرانجام فقط یک صفت از هر زیر گروه برای تولید انتخاب می شوند.

4- روش های تغییر

وقتی کروموزوم ها انتخاب شدند، باید به طور تصادفی برای افزایش تناسب اصلاح شوند. دو راه حل اساسی برای این کار وجود دارد. اولین و ساده ترین راه، جهش (موتاسیون) نامیده می شود. درست مثل جهش در موجودات زنده که تغییر یک ژن به ژن دیگری است. در الگوریتم ژنتیک جهش تغییر کوچکی در یک نقطه از کد خصوصیات ایجاد می کند.

دومین روش کراس اور نام دارد. این فرآیند براساس فرآیند ترکیب کروموزوم ها در طول تولید مثل در موجودات زنده شبیه سازی شده است. اغلب روش های معمول کراس اور شامل لقاح تک – نقطه هستند که نقطه تعویض در جایی تصادفی بین ژنوم ها می باشد.

3-3-5 نقاط قوت الگوریتم های ژنتیک

اولین و مهمترین نقطه قوت الگوریتم های ژنتیک این است که ذاتاً موازی هستند. اکثر الگوریتم های دیگر موازی نیستند و فقط می توانند فضای مسئله مورد نظر را در یک لحظه جستجو کنند و اگر راه حل پیدا شده یک جواب بهینه محلی باشد و یا زیر مجموعه ای از جواب اصلی باشد باید تمام کارهایی که تا به حال انجام شده را کنار گذاشت و دوباره از اول شروع کرد. از آنجایی که GA چندین نقطه شروع دارد، در یک لحظه می تواند فضای مسئله را از چند جهت مختلف جستجو کند. اگر یکی از نقاط شروع به نتیجه نرسید سایر راه ها ادامه می یابند و منابع بیشتری در اختیارشان قرار می گیرد.

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

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

5- محدودیت های الگوریتم ژنتیک

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

6- کاربردها

از مهمترین کاربردهای الگوریتم ژنتیک در شیمی می توان به موارد زیر اشاره کرد:

-        بهینه سازی ساختار مولکولی

-        تشخیص الگو و استخراج داده[1]

-        آموزش شبکه های عصبی مصنوعی

-        یادگیری قوانین فازی با استفاده از الگوریتم های ژنتیک

-        تخمین پارامترهای سینتیکی

-        بهینه سازی پارامترهای کنترل کیفی

-        روابط کمی ساختار – فعالیت

-        طبقه بندی سریهای مولکولی بزرگ

-        انتخاب طول موج برای کالیبراسیون چند متغیره

-        بررسی رفتار کروماتوگرافی غیرخطی

-        نمایش ساختارهای شیمیایی .