الگوریتم ژنتیک یا Genetic Algorithm (GA) یکی از شناختهشدهترین روشهای بهینهسازی تکاملی است که از مفاهیم انتخاب طبیعی و ژنتیک الهام گرفته شده است. این الگوریتم به جای بررسی مستقیم همه جوابهای ممکن، با یک جمعیت از جوابهای اولیه شروع میکند و با استفاده از عملگرهایی مانند انتخاب، آمیختگی و جهش، نسلهای جدیدی از جوابها را تولید میکند.
الگوریتم ژنتیک در بسیاری از مسائل بهینهسازی که فضای جستجوی بزرگ، غیرخطی یا پیچیده دارند قابل استفاده است و به همین دلیل در حوزههای مختلف مهندسی، هوش مصنوعی و علوم کاربرد فراوانی پیدا کرده است.
الگوریتم ژنتیک چگونه کار میکند؟
در یک مسئله بهینهسازی، ابتدا باید متغیرهای تصمیم مشخص شوند. سپس هر جواب ممکن به شکلی قابل استفاده برای الگوریتم نمایش داده میشود.
الگوریتم ژنتیک معمولاً با مراحل زیر اجرا میشود:
- تولید جمعیت اولیه
- محاسبه مقدار تابع برازندگی
- انتخاب والدین مناسب
- انجام Crossover
- اعمال Mutation
- تولید نسل جدید
- ارزیابی نسل جدید
- تکرار مراحل تا رسیدن به شرط توقف
هدف این فرایند آن است که با گذشت نسلها، کیفیت جوابهای موجود در جمعیت افزایش پیدا کند.
کروموزوم در الگوریتم ژنتیک
در GA هر جواب ممکن برای مسئله با یک Chromosome نمایش داده میشود.
کروموزوم شامل مجموعهای از ژنها است و هر ژن میتواند نماینده یکی از متغیرهای مسئله باشد.
برای مثال اگر مسئله دارای سه متغیر تصمیم باشد، یک کروموزوم میتواند اطلاعات مربوط به این سه متغیر را در خود نگه دارد.
نحوه نمایش کروموزوم اهمیت زیادی دارد، زیرا ساختار آن باید متناسب با مسئله بهینهسازی انتخاب شود.
کدگذاری باینری و حقیقی
یکی از روشهای کلاسیک نمایش کروموزومها، Binary Encoding است. در این روش متغیرها به رشتههای صفر و یک تبدیل میشوند.
با این حال برای بسیاری از مسائل مهندسی استفاده از Real-Valued Encoding مناسبتر است، زیرا متغیرها مستقیماً به صورت اعداد حقیقی نمایش داده میشوند.
انتخاب نوع کدگذاری به ساختار مسئله، نوع متغیرها و روش اعمال عملگرهای ژنتیکی بستگی دارد.
Population یا جمعیت
مجموعهای از چند کروموزوم یک Population را تشکیل میدهد.
هر عضو جمعیت یک جواب احتمالی برای مسئله است. در ابتدای اجرای الگوریتم، جمعیت اولیه معمولاً به صورت تصادفی ایجاد میشود.
سپس در هر Generation جمعیت جدیدی تولید میشود که انتظار داریم نسبت به نسلهای قبلی جوابهای مناسبتری در آن وجود داشته باشد.
تعداد اعضای جمعیت یکی از پارامترهای مهم الگوریتم ژنتیک است.
تابع هدف و Fitness Function
یکی از مهمترین مراحل استفاده از الگوریتم ژنتیک، تعریف صحیح Objective Function یا تابع هدف است.
الگوریتم باید بتواند کیفیت هر جواب را اندازهگیری کند. این کار از طریق Fitness Function انجام میشود.
برای مثال ممکن است هدف مسئله یکی از موارد زیر باشد:
- کمینه کردن هزینه
- کمینه کردن خطا
- بیشینه کردن سود
- بیشینه کردن راندمان
- کاهش مصرف انرژی
- پیدا کردن بهترین پارامترهای یک مدل
اگر تابع هدف به درستی تعریف نشود، حتی یک الگوریتم ژنتیک خوب نیز نمیتواند جواب مناسبی برای مسئله پیدا کند.
Selection یا انتخاب
بعد از محاسبه Fitness، باید مشخص شود کدام اعضای جمعیت برای تولید نسل بعد انتخاب شوند.
به این مرحله Selection گفته میشود.
در حالت کلی جوابهایی که Fitness بهتری دارند، شانس بیشتری برای انتقال ویژگیهای خود به نسل بعد خواهند داشت.
روشهای مختلفی برای Selection وجود دارد.
Roulette Wheel Selection
یکی از روشهای معروف انتخاب در GA، Roulette Wheel Selection است.
در این روش احتمال انتخاب هر عضو با کیفیت یا Fitness آن ارتباط دارد.
به صورت مفهومی میتوان یک چرخ رولت را تصور کرد که اعضای بهتر سهم بیشتری از آن را در اختیار دارند؛ بنابراین احتمال انتخاب آنها بیشتر است.
با این حال اعضای ضعیفتر نیز احتمال صفر ندارند و همین موضوع به حفظ تنوع جمعیت کمک میکند.
Tournament Selection
روش Tournament Selection نیز یکی از روشهای پرکاربرد انتخاب است.
در این روش چند عضو از جمعیت انتخاب شده و با یکدیگر مقایسه میشوند. سپس عضو مناسبتر به عنوان والد انتخاب میشود.
این عملیات چندین بار تکرار میشود تا تعداد کافی والد برای تولید نسل بعد در اختیار الگوریتم قرار گیرد.
Elitism
در الگوریتم ژنتیک ممکن است بهترین جواب یک نسل در هنگام Crossover و Mutation از بین برود.
برای جلوگیری از این اتفاق میتوان از Elitism استفاده کرد.
در روش نخبهگرایی، تعدادی از بهترین اعضای جمعیت بدون تغییر مستقیماً به نسل بعد منتقل میشوند.
این کار کمک میکند بهترین جواب پیدا شده تا آن لحظه از دست نرود.
Crossover یا آمیختگی
یکی از اصلیترین عملگرهای الگوریتم ژنتیک Crossover است.
در این مرحله دو کروموزوم والد انتخاب میشوند و بخشهایی از اطلاعات آنها با یکدیگر ترکیب میشوند تا فرزندان جدیدی ایجاد شوند.
ایده اصلی این است که شاید ترکیب ویژگیهای خوب دو والد بتواند یک جواب بهتر تولید کند.
Single Point Crossover
در Single Point Crossover یک نقطه روی کروموزوم انتخاب میشود.
قسمتی از ژنهای بعد از این نقطه میان والدها جابهجا میشوند و به این ترتیب دو فرزند جدید ایجاد میشوند.
این روش یکی از سادهترین روشهای آمیختگی در الگوریتم ژنتیک است.
Two-Point و Multi-Point Crossover
در Two-Point Crossover دو نقطه روی کروموزوم مشخص میشود و بخش قرار گرفته بین این دو نقطه میان والدها جابهجا میشود.
اگر تعداد بیشتری نقطه Crossover داشته باشیم، با یک روش Multi-Point Crossover مواجه هستیم.
انتخاب روش مناسب Crossover میتواند روی سرعت و کیفیت جستجو تأثیر بگذارد.
Uniform Crossover
در Uniform Crossover انتخاب ژنهای فرزند میتواند برای هر موقعیت به صورت جداگانه انجام شود.
در نتیجه ترکیب ژنهای والدین انعطاف بیشتری نسبت به روشهای تکنقطهای دارد.
نوع Crossover باید با نوع کدگذاری کروموزوم و ساختار مسئله هماهنگ باشد.
Mutation یا جهش
اگر تنها از Selection و Crossover استفاده شود، احتمال دارد جمعیت به تدریج تنوع خود را از دست بدهد.
Mutation برای ایجاد تغییرات تصادفی کوچک در کروموزومها استفاده میشود.
در کدگذاری باینری، Mutation میتواند یک بیت صفر را به یک یا برعکس تبدیل کند.
در کدگذاری حقیقی نیز میتوان مقدار یکی از متغیرها را با یک تغییر تصادفی اصلاح کرد.
هدف Mutation حفظ تنوع ژنتیکی و کمک به الگوریتم برای جستجوی نواحی جدید فضای جواب است.
تعادل Exploration و Exploitation
یکی از موضوعات مهم در الگوریتمهای بهینهسازی، ایجاد تعادل میان:
- Exploration: جستجوی نواحی جدید
- Exploitation: بهبود جوابهای خوب موجود
است.
Selection و Elitism معمولاً الگوریتم را به سمت جوابهای خوب هدایت میکنند، در حالی که Mutation و تنوع جمعیت کمک میکنند فضای بیشتری از جوابهای ممکن بررسی شود.
تنظیم مناسب پارامترها برای ایجاد این تعادل اهمیت زیادی دارد.
احتمال Crossover و Mutation
دو پارامتر مهم GA عبارتند از:
- Crossover Probability
- Mutation Probability
اگر Mutation بسیار کم باشد ممکن است الگوریتم تنوع کافی نداشته باشد. اگر بیش از حد زیاد باشد، رفتار الگوریتم میتواند بیش از اندازه تصادفی شود.
همین موضوع درباره نرخ Crossover نیز وجود دارد.
در پروژههای عملی ممکن است لازم باشد چند مقدار مختلف برای این پارامترها آزمایش شود.
شرط توقف الگوریتم
الگوریتم ژنتیک نمیتواند برای همیشه اجرا شود و باید یک معیار برای پایان عملیات تعریف کنیم.
شرط توقف میتواند بر اساس یکی از موارد زیر باشد:
- رسیدن به تعداد مشخصی Generation
- رسیدن Fitness به مقدار مورد نظر
- عدم بهبود جواب طی چند نسل
- رسیدن به محدودیت زمانی
- رسیدن تغییرات Fitness به مقدار بسیار کم
پس از تحقق شرط توقف، بهترین جواب موجود در جمعیت به عنوان جواب الگوریتم گزارش میشود.
همگرایی زودرس
یکی از مشکلات احتمالی الگوریتم ژنتیک، Premature Convergence است.
در این حالت اعضای جمعیت خیلی زود شبیه یکدیگر میشوند و الگوریتم در یک ناحیه از فضای جستجو متوقف میشود.
این مسئله میتواند باعث شود الگوریتم به یک جواب محلی برسد و جواب بهتر موجود در فضای جستجو را پیدا نکند.
تنظیم Mutation، اندازه Population و روش Selection در کاهش این مشکل اهمیت دارند.
پیادهسازی الگوریتم ژنتیک در MATLAB
تمرکز اصلی این دوره بر پیادهسازی عملی Genetic Algorithm در MATLAB است.
MATLAB محیط مناسبی برای پیادهسازی الگوریتمهای بهینهسازی است، زیرا کار با بردارها، ماتریسها، اعداد تصادفی، توابع و نمودارها در آن ساده است.
در یک پیادهسازی GA معمولاً بخشهایی برای موارد زیر نوشته میشوند:
- تعریف مسئله
- تولید Population
- محاسبه Cost
- Selection
- Crossover
- Mutation
- ذخیره بهترین جواب
- رسم روند همگرایی
درک این اجزا به کاربر اجازه میدهد الگوریتم را برای پروژههای متفاوت تغییر دهد.
رسم نمودار همگرایی
برای بررسی عملکرد GA معمولاً بهترین مقدار تابع هدف در هر نسل ذخیره میشود.
سپس میتوان Convergence Curve را رسم کرد.
این نمودار نشان میدهد الگوریتم در طول نسلها چگونه جواب مسئله را بهبود داده است.
با مشاهده نمودار همگرایی میتوان درباره سرعت بهبود الگوریتم و نیاز احتمالی به تغییر پارامترها تصمیمگیری کرد.
الگوریتم ژنتیک برای مسائل مهندسی
Genetic Algorithm محدود به یک رشته خاص نیست و میتوان آن را در بسیاری از مسائل مهندسی استفاده کرد.
نمونههایی از کاربردهای آن عبارتند از:
- بهینهسازی طراحی
- سیستمهای قدرت
- کنترل
- مکانیابی
- زمانبندی
- مهندسی صنایع
- انتخاب ویژگی
- تنظیم پارامترهای مدل
- طراحی شبکه عصبی
- مدیریت انرژی
- بهینهسازی سازه
- مسائل اقتصادی
نکته اصلی این است که مسئله باید به شکلی تعریف شود که متغیرهای تصمیم، تابع هدف و در صورت وجود قیود آن مشخص باشند.
استفاده از GA در یادگیری ماشین
الگوریتم ژنتیک میتواند در مسائل Machine Learning نیز استفاده شود.
برای مثال میتوان از GA برای:
- Feature Selection
- Hyperparameter Optimization
- انتخاب ساختار مدل
- تنظیم پارامترهای شبکه عصبی
- انتخاب متغیرهای ورودی
- کمینه کردن خطای مدل
استفاده کرد.
در این حالت عملکرد مدل یادگیری ماشین میتواند در داخل تابع هدف محاسبه شود و GA به دنبال ترکیبی از پارامترها باشد که عملکرد بهتری ایجاد کند.
این آموزش برای چه افرادی مناسب است؟
این دوره برای افراد زیر میتواند مفید باشد:
- دانشجویان مهندسی برق
- دانشجویان کامپیوتر و هوش مصنوعی
- دانشجویان صنایع
- دانشجویان مکانیک و عمران
- پژوهشگران بهینهسازی
- دانشجویان کارشناسی ارشد و دکتری
- افرادی که در پایاننامه از GA استفاده میکنند
- افرادی که قصد کدنویسی الگوریتمهای تکاملی در MATLAB را دارند
پیشنیاز دوره
پیشنیاز معرفیشده برای این محصول، آشنایی با مبانی بهینهسازی است.
قبل از پیادهسازی یک الگوریتم ژنتیک باید بتوانید متغیرهای تصمیم، تابع هدف، محدوده متغیرها و در صورت نیاز قیود مسئله را به درستی تعریف کنید.
همچنین آشنایی مقدماتی با MATLAB برای استفاده بهتر از بخش کدنویسی توصیه میشود.
هدف این آموزش
هدف این دوره آن است که مخاطب ابتدا اجزای اصلی Genetic Algorithm را به صورت مفهومی درک کرده و سپس نحوه تبدیل این اجزا به کد MATLAB را یاد بگیرد.
پس از مشاهده آموزش، کاربر باید دید روشنتری نسبت به Population، Chromosome، Fitness Function، Selection، Crossover، Mutation و Generation داشته باشد و بتواند ساختار الگوریتم را برای مسئله بهینهسازی خود توسعه دهد.