الگوریتم ژنتیک در حل مسائلی که پیداکردن جوابهای بهینه در آنها دشوار است، دارای کاربردهای زیادی است. الگوریتم های ژنتیک فن های جستجوی تصادفی هستند که بر پایه مکانیسم ژنتیک و انتخاب طبیعی بنا شده اند. شکل معمول الگوریتم ژنتیک نخستین بار توسط گلدبرگ ارایه شد.
الگوریتم های ژنتیک از مجموعه ای از راه حل های تصادفی اولیه به نام «جمعیت» آغاز می شوند هر جزء از جمعیت «کروموزوم» نامیده می شود.
مشکلات الگوریتم ژنتیک و چگونگی غلبه بر آن
استفاده از الگوریتم ژنتیک مشکلاتی ازجمله سرعت جستجو، دقت پایین به علت همگرایی زودرس و گرفتار شدن در بهینه محلی را به دنبال دارد.
دو دسته فعالیت عمده برای غلبه بر مشکلات موجود در الگوریتم ژنتیک پیشنهاد شده است. گروه اول بر روی اصلاح نوع عملگرها بویژه دو عملگر بازترکیب و جهش تمرکز دارند. بعلاوه، یک الگوریتم تطبیقی برای انتخاب مناسب عملگرهای بازترکیب و جهش در حین اجرای الگوریتم ژنتیک ارائه شده است که عملکرد بهتری را در مقایسه با سایر روشهای دیگر نشان می دهد.
لذا دسته دوم فعالیتها، از تنظیم هوشمندانه و تطبیقی این پارامترها برای غلبه بر مشکلات الگوریتم ژنتیک بهره می گیرند. بطور کلی این تطبیق قادرست برای هر کروموزوم و یا برای کل کروموزوم های یک نسل انجام گیرد.
اصطلاحاً، این دو سطح تطبیق را به ترتیب سطح کروموزوم و سطح الگوریتم می نامند.
با معلوم شدن پارامترهای الگوریتم ژنتیک، عملگرهای بازترکیب و جهش بر روی نسل جاری اعمال شده و نسل آتی تولید می شود. از آنجا که پارامترهای تنظیم شده برای اعمال عملگرهای ژنتیک بر روی همه کروموزومهای نسل جاری یکسان فرض میشود، این روش نوعی از تطبیق در سطح الگوریتم می باشد.
همچنین، معیار واریانس بازندگی کروموزومها در هر نسل به عنوان معیار پراکندگی جهت تنظیم پارامترهای جهش و بازترکیب توسط یک کنترل کننده فازی ثابت مورد استفاده قرار گرفته است.
الگوریتم ژنتیک استاندارد
در این ساختار، هر نسل، شامل تعدادی کروموزوم است که محتوای عددی ژنهای هر کروموزوم، معادل محتوای عددی یکی ازمتغیرهای تصمیم درمسأله بهینه سازی می باشد. لذا، با معلوم بودن هر کروموزوم، میزان برازندگی آن بر اساس تابع هدف در مسأله بهینه سازی تعیین می گردد.
همچنین درالگوریتم استاندارد، پارامترها برای همه نسلها و همه کروموزوم ها ثابت می باشند.
الگوریتم ژنتیک پویا
الگوریتم ژنتیک، روش یادگیری بر پایه تکامل بیولوژی است این الگوریتم، برای حل مسئله، مجموعه بسیار بزرگی از راه حل های ممکن را تولید می کند. ارزیابی هریک از این راه حل ها، با استفاده از یک تابع شایستگی انجام می گیرد آنگاه تعدادی از راه حل ها موجب تولید راه حل های جدید می گردند و این کار به تکامل راه حل ها می انجامد.
بدین صورت، فضای جستجو در جهتی تکامل می یابد که به راه حل مطلوب برسد. درصورت انتخاب صحیح پارامترها، این روش بسیار موثر عمل می شود.
ذگردی و بهشتی نیا به یکپارچه سازی زمان بندی تولید و حمل ونقل در یک زنجیر تأمین دومرحله ای در زمان تخصیص سفارش ها به تأمین کنندگان پرداختند. پس از مدل سازی مسئله به عنوان یک مسئله برنامه ریزی عدد صحیح مخدتلط ازیک الگوریتم ژنتیک برای حل آن استفاده شد.
الگوریتم ژنتیک در معماری
الگوریتم‌های ژنتیک یک تکنیک محاسباتی بر اساس رشته‌های تکامل است که اخیرا، در رشته معماری به منظور بررسی و مطالعه مشکلات پیچیده موجود در عملکرد و فرم پروژه‌های معماری به وجود آمده و معرفی گردیده است. علی رغم آن‌که در خصوص به کاربردن الگوریتم‌های ژنتیک تمایل فزاینده‌ای به چشم می‌خورد و علاقه به آن روزبه روز بیشتر میشود؛ لیکن هنوز هم بررسی نظام مندی در مورد روال کار آن و کاربردهایش در معماری صورت نگرفته است.
بررسی ساختارهای جدید از الگوریتم ژنتیک در بهینه سازی بهره برداری از مخازن با ساخت سدهای بزرگ در کشورهای متفاوت دنیا، بالا بردن بازده و کارایی این سیستم های مخزنی و حداکثر سازی منافع ناشی از آنها از مهم ترین مباحث مورد بررسی در سال های اخیر است.
الگوریتم های تکاملی
الگوریتم های تکاملی از قبیل الگوریتم ژنتیک در بسیاری از مقوله های علمی و مهندسی به عنوان ابزارهای جستجو و بهینه سازی مورد استفاده قرار می گیرند.
کاربردهای بسیاری از این روش ها در مورد مساله بهره برداری بهینه از مخازن گزارش شده است.
در چند دهه اخیر، برای فایق آمدن به مشکل ها و ایرادهای احتمالی روشهای سنتی جستجو، تلاش های گسترده ای به منظور تهیه و ارایه الگوریتم های مناسب تر صورت پذیرفته است.
عملگر جابجایی
جا به جایی مهمترین عملگر ژنتیک است که برای ترکیب دو کروموزوم از والدین و ایجاد فرزندان جدید انجام می شود.
- انواع متداول جابجایی
- برش یک نقطه ای
- برش دو نقطه ای
- برش چند نقطه ای
- و جا به جایی یکنواخت از انواع متداول جابجایی است.
در این عملگر آهنگ جابجایی به طور نسبتی از تعداد فرزندان تولید شده از هر نسل به مقدار نسل حاضر تعریف می گردد. جهش ژنی نیز عملگر دیگری است که می تواند تغییرهایی در یک یا چند ژن از یک کروموزوم به وجود آورد. در الگوریتم های ژنتیک جهش ژنی نقش حساسی را به یکی از دو شکل جا به جایی ژنهای گمشده نسل در طی فرایند انتخاب به شکل یک کروموزوم جدید و یا داخل کردن ژنهایی که در نسل حاضر موجود نیستند به نسل جدید، ایفا می کنند. آهنگ جهش به صورت درصدی از مجموعه ژنهای هر نسل بیان می گردد.
در این تحقیق، هر کدام از ژنهای موجود در کروموزوم نمایانگر یک مقدار آزاد سازی ماهانه است که بدین ترتیب ریسه پاسخ شامل ژن هایی به تعداد ماه های دوره شبیه سازی است.
فرمول بندی اول GA-Elitism
اولین فرمول بندی مورد استفاده، الگوریتم ژنتیک نخبه گرایی است که از این به بعد، GA-Elitism خوانده می شود. در این فرمول بندی پس از تولید تصادفی کروموزوم ها با در نظر گرفتن قیود مساله و به تعداد جمعیت پاسخ 80 کروموزوم ها بر اساس مقداربرازندگی مرتب شده و بهترین آنها به طور مستقیم به نسل بعد انتقال می یابد. سرانجام با استفاده از انتخاب چرخ رولت کروموزوم های لازم برای تکمیل نسل دوم از مجموعه جواب نسل قبل انتخاب می شوند.
بعد از این مرحله عملگر جابجایی وارد عمل شده و بر اساس احتمال مورد نظر بر روی جفت کروموزومهای نسل جدید اعمال می شود. نکات قابل توجه در این زمینه استفاده از انواع روشهای جابه جایی، احتمال های متفاوت و انتخاب بهترین عملگر در طی آنالیز حساسیت مربوط می شود. در ضمن هر کدام از کروموزوم ها حداکثر یکبار مورد جا بجایی ژنی قرار می گیرند.
عملگر جهش زنی در مرحله بعد و بر اساس احتمال مورد نظر روی ژن های اطلاعاتی کروموزوم های نسل جدید اعمال می شود. با پایان اعمال عملگرهای ژنتیکی، مجموعه ی پاسخ جدید بر اساس برازندگی مرتب شده و بهترین پاسخ اعلام می گردد. فرآیند بالا تا جایی ادامه می یابد که معیار توقف برنامه که در این حالت رسیدن به تعداد تکرار های ویژه است ارضاء گردد.
فرمول بندی دوم CPGA
فرمول بندی دوم الگوریتم ژنتیک طبقه بندی شده که از این پس CPGA می نامند.
در این روش مانند ساختار قبلی، پس از تولید تصادفی پاسخ ها و مرتب کردن آنها، بهترین پاسخ به نسل جدید منتقل می شود. کروموزوم های لازم برای تشکیل 25 درصد مجموعه پاسخ جدید از کروموزوم های انتخابی از نسل قبل در نظر گرفته می شوند. در مرحله بعد با استفاده از عملگرهای جا به جایی 25 درصد دیگر از جمعیت جواب های جدید ایجاد می شود.
50 درصد باقیمانده به توسط از عملگرهای مختلف جهش ژنی تولید شده و بدین صورت تولید نسل جدید پایان می یابد. در نهایت، کروموزوم ها بر اساس مقدار تابع هدف منظم گردیده و بهترین آنها به عنوان پاسخ برتر اعلام خواهدشد.
بهترین چینش
بهترین چینشی که در نهایت الگوریتم ژنتیک برای حروف فارسی ارائه داد هزینه اش با توجه به تابع تناسب، 0.815 هزینه چینش کنونی حروف فارسی است.
کاربرد الگوریتم های ژنتیک خیلی زیاد است که در زیرآورده شده است:
- optimization (بهینه سازی)
- automatic programming (برنامه نویسی اتوماتیک)
- machine learning ( فراگیری زبان ماشین)
- economics (اقتصاد)
- operations research (تخقیقات عملیاتی)
- ecology (اکولوژی)
- studies of evolution (مطالعه انقلاب)
- social systems (سیستم های اجتماعی و سوشیال)
درسال 1999، یک شرکت Genetic Programming Inc یک کامپیوتر موازی با 1000 گره هریک شامل کامپیوترهای MHZ P2, 350 برای پیاده سازی روش های ژنتیک مورد استفاده قرار گرفت.
