ورود ثبت

Login to your account

Username
Password *
Remember Me

Create an account

Fields marked with an asterisk (*) are required.
Name
Username
Password *
Verify password *
Email *
Verify email *
Captcha *

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

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

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

برای آشنایی بیشتر با الگوریتم ژنتیک با هوش مصنوعی همراه باشد.

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

 

الگوریتم ژنتیک-(Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم های تکامل است که از تکنیک های زیست‌شناسی مانند وراثت و جهش استفاده می‌کند.

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

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

الگوریتم های ژنتیک معمولاً به عنوان یک شبیه‌ساز کامپیوتر که در آن جمعیت یک نمونهٔ انتزاعی (کروموزوم ها) از نامزدهای راه‌حل یک مسأله بهینه‌سازی به راه حل بهتری منجر شود، پیاده‌سازی می‌شوند. به طور سنتی راه‌حل ها به شکل رشته‌هایی از ۰ و ۱ بودند، اما امروزه به گونه‌های دیگری هم پیاده‌سازی شده‌اند. فرضیه با جمعیتی کاملاً تصادفی منحصر بفرد آغاز می‌شود و در نسل ها ادامه می‌یابد. در هر نسل گنجایش تمام جمعیت ارزیابی می‌شود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب می‌شوند (بر اساس شایستگی ها) و برای شکل دادن نسل جدید، اصلاح می‌شوند (کسر یا دوباره ترکیب می‌شوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل می‌شود.

شما اینجا هستید: صفحه اصلی موضوعات مطالب بهینه سازی الگوریتم ژنتیک