الگوریتم ژنتیک، الگوریتمی برای بهینه سازی و جستجو است که بر اساس اصول علم ژنتیک و انتخاب طبیعی پایه ریزی شده است. در الگوریتم ژنتیک گروهی از موجودات زنده مصنوعی به وجود می آیند و در شرایطی رشد و نمو می کنند که هدف کلی آن بیشینه کردن شایستگی کل جمعیت یا کمینه کردن یک هزینه مرتبط با جمعیت است. این روش در دهه های 1960 و 1970 توسط جان هالند معرفی و ایجاد شد و نهایتا توسط یکی از شاگردانش به نام دیوید گُلدبرگ جمع آوری شد.
مهم ترین و ابتدایی ترین نوع الگوریتم ژنتیک، الگوریتم ژنتیک باینری است که در آن متغیرها به صورت باینری کد می شوند. این نوع از الگوریتم ژنتیک را، الگوریتم ژنتیک گسسته نیز می نامند. زیرا متغیرها در آن دارای تغییرات پیوسته نیستند و نمی توانند هر مقداری به خود بگیرند. مجموعه متغیر های مسأله، که می بایست مقدار بهینه برای آن ها پیدا شود، در قالب رشته های باینری کد می شوند و به همدیگر الحاق می گردند. به این ترتیب یک کروموزوم از متغیر های مسأله به دست می آید. همان طور که در طبیعت، هر رشته ژنی، یک موجود خاص و منحصر به فرد را مشخص می کند، در مورد الگوریتم ژنتیک نیز، هر کروموزوم یک جواب منحصر به فرد برای مسأله مورد بررسی را مشخص می کند.
این کد، قابلیت استفاده در انواع مسائل بهینه سازی را دارد و می توان با تغییراتی بسیار جزئی در آن، برای حل مختلف از این کد استفاده نمود. دانلود:
حل مسائل بهينه سازي گسسته با الگوريتم ژنتيک باينري
صورت مساله
الگوريتم ژنتيک تکنيک جستجويي در علم رايانه براي يافتن راهحل تقريبي براي بهينهسازي و مسائل جستجو است. الگوريتم ژنتيک نوع خاصياز الگوريتمهاي تکاملي است که از تکنيکهاي زيستشناسي فرگشتي مانند وراثت و جهش استفاده ميکند.
در واقع الگوريتمهاي ژنتيک از اصول انتخاب طبيعي داروين براي يافتن فرمول بهينه جهت پيشبيني يا تطبيق الگو استفاده ميکنند. الگوريتمهاي ژنتيک اغلب گزينه خوبي براي تکنيکهاي پيشبيني بر مبناي رگرسيون هستند. مختصراً گفته ميشود که الگوريتم ژنتيک يک تکنيک برنامهنويسي است که از تکامل ژنتيکي به عنوان يک الگوي حل مسئله استفاده ميکند.مسئلهاي که بايد حل شود ورودي است و راهحلها طبق يک الگو کد گذاري ميشوند که تابع برازش يا تابع هزينه، هر راه حل کانديد را ارزيابي ميکند که اکثر آنها به صورت تصادفي انتخاب ميشوند.
کلاً اين الگوريتمها از بخش هاي زير تشکيل ميشوند :
تابع برازش
نمايش
انتخاب
تغيير
موتور الگوريتم ژنتيک يک جمعيت اوليه از فرمول ايجاد ميکند. هر فرد در برابر مجموعهاي از دادههاي مورد آزمايش قرار ميگيرند و مناسبترين آنها (شايد 10 درصد از مناسبترينها) باقي ميمانند؛ بقيه کنار گذاشته ميشوند. مناسبترين افراد با هم جفتگيري (جابجايي عناصر دي ان اي) و تغيير (تغيير تصادفي عناصر دي ان اي) کردهاند. مشاهده ميشود که با گذشت از ميان تعداد زيادي از نسلها، الگوريتم ژنتيک به سمت ايجاد فرمولهايي که دقيقتر هستند، ميل ميکنند. در حالي که شبکههاي عصبي هم غيرخطي و غيرپارامتريک هستند، جذابيت زياد الگوريتمهاي ژنتيک اين است نتايج نهايي قابل ملاحظهترند. فرمول نهايي براي کاربر انساني قابل مشاهده خواهد بود، و براي ارائه سطح اطمينان نتايج ميتوان تکنيکهاي آماري متعارف را بر روي اين فرمولها اعمال کرد. فناوري الگوريتمهاي ژنتيک همواره در حال بهبود است و براي مثال با مطرح کردن معادله ويروسها که در کنار فرمولها و براي نقض کردن فرمولهاي ضعيف توليد ميشوند و در نتيجه جمعيت را کلاً قويتر ميسازند.
عموماً راهحلها به صورت 2 تايي 0 و 1 نشان داده ميشوند، ولي روشهاي نمايش ديگري هم وجود دارد. تکامل از يک مجموعه کاملاً تصادفي از موجوديتها شروع ميشود و در نسلهاي بعدي تکرار ميشود. در هر نسل، مناسبترينها انتخاب ميشوند نه بهترينها.
يک راهحل براي مسئله مورد نظر، با يک ليست از پارامترها نشان داده ميشود که به آنها کروموزوم يا ژنوم ميگويند. کروموزومها عموماً به صورت يک رشته ساده از دادهها نمايش داده ميشوند، البته انواع ساختمان دادههاي ديگر هم ميتوانند مورد استفاده قرار گيرند. در ابتدا چندين مشخصه به صورت تصادفي براي ايجاد نسل اول توليد ميشوند. در طول هر نسل، هر مشخصه ارزيابي ميشود وارزش تناسب توسط تابع تناسب اندازهگيري ميشود.
گام بعدي ايجاد دومين نسل از جامعه است که بر پايه فرآيندهاي انتخاب، توليد از روي مشخصههاي انتخاب شده با عملگرهاي ژنتيکي است: اتصال کروموزومها به سر يکديگر و تغيير.
براي هر فرد، يک جفت والد انتخاب ميشود. انتخابها به گونهاياند که مناسبترين عناصر انتخاب شوند تا حتي ضعيفترين عناصر هم شانس انتخاب داشته باشند تا از نزديک شدن به جواب محلي جلوگيري شود. چندين الگوي انتخاب وجود دارد: چرخ منگنهدار(رولت)، انتخاب مسابقهاي،... .
معمولاً الگوريتمهاي ژنتيک يک عدد احتمال اتصال دارد که بين 0.6 و 1 است که احتمال به وجود آمدن فرزند را نشان ميدهد. ارگانيسمها با اين احتمال دوباره با هم ترکيب ميشوند. اتصال 2 کروموزوم فرزند ايجاد ميکند، که به نسل بعدي اضافه ميشوند. اين کارها انجام ميشوند تا اين که کانديدهاي مناسبي براي جواب، در نسل بعدي پيدا شوند. مرحله بعدي تغيير دادن فرزندان جديد است. الگوريتمهاي ژنتيک يک احتمال تغيير کوچک و ثابت دارند که معمولاً درجهاي در حدود 0.01 يا کمتر دارد. بر اساس اين احتمال، کروموزومهاي فرزند به طور تصادفي تغيير ميکنند يا جهش مييابند، مخصوصاً با جهش بيتها در کروموزوم ساختمان دادهمان.
اين فرآيند باعث به وجود آمدن نسل جديدي از کروموزومهايي ميشود، که با نسل قبلي متفاوت است. کل فرآيند براي نسل بعدي هم تکرار ميشود، جفتها براي ترکيب انتخاب ميشوند، جمعيت نسل سوم به وجود ميآيند و .... اين فرآيند تکرار ميشود تا اين که به آخرين مرحله برسيم.
شرايط خاتمه الگوريتمهاي ژنتيک عبارتند از:
* به تعداد ثابتي از نسلها برسيم
* زمان اختصاص دادهشده تمام شود
* يک فرد(فرزند توليد شده) پيدا شود که مينيمم (کمترين) ملاک را برآورده کند
* بيشترين درجه برازش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود
سلام به دوستان
کسی می دونه چه طوری میشه تو matlab ماتریسی داشته باشم که طول سطرهای ماتریس متغیر ویکسان با همدیگر نباشد( مثلا برای نوشتن الگوریتم ژنتیک با طول متغیر)؟
ممنون
دوست عزيز. براي اين كار نميتوني از ماتريس استفاده كني. حتما بايد از آرايه هاي سلولي يا ساختاري استفاده كني.
سلام
بی نهایت ممنونم از کد فوق العاده کاربردی که به اشتراک گذاشتید...
نحوه ی وارد کردن قیود مساله در این الگوریتم به چه نحوی می باشد ؟
پیشاپیش از راهنمایی شما بسیار سپاس گزارم
سلام ، من در زمینه teacher assignment تحقیق میکنم، و موضوع مقاله ای که دارم کار می کنم an application of genetic algorithm methods for teacher assignment problem هست، کسی آشنایی با این موضوع داره؟ من خیلی به کمک نیاز دارم جهت نوشتن کد ژنتیک این مسئله
فوری....دوستان پروژه دارم....فوری...رفقا درخواست کمک....
سلام
دوستان از چه برنامه ای واسه اجرای سورس کد این برنامه باید استفاده کنم
ممنون میشم زود خبرم کنید
سلام دوستان
ببخشید که احتمال زیاد سوالم رو جای نامناسبی میپرسم چون زیاد آشنایی با این مباحث ندارم
میخواستم بدونم تو الگوریتم ژنتیک چجوری میشه (RMSE) رو بدست آورد؟ و آیا این مقدار همون کمترین میزان Best fitness در نمودار Fitness value-Generation هست که در پایان ران الگوریتم نشون داده میشه ؟