۴-۱ مقدمه
ماهیت بسیاری از مسائل بهینه سازی مهم نظری و کاربردی شامل جستجوی بهترین پیکربندی برای مجموعه ای از متغیرها به منظور دستیابی به یک یا چند هدف خاص می باشد]۶۴[ این نوع مسائل به دودسته کلی تقسیم می شوند: در دسته اول جواب مسئله به صورت متغیرهای با ارزش واقعی کدگذاری می شوند ودر دسته دوم این متغیرها دارای ساختار گسسته می باشند.مسائل بهینه سازی ترکیب کلاس مهمی از مسائل دارای متغیرهای گسسسته می باشند که هدف آنها یافتن یک جواب بهینه سراسری در میان تمامی جوابهای موجود در فضای جستجو مسئله می باشد.مسائل زمانبندی از جمله مهمترین مسائل بهینه سازی ترکیبی محسوب می شوند.با توجه به اهمیت فراوان این مسائل الگوریتمهای مختلفی به منظور بهینه سازی این مسائل ارائه گردیده است. دو دسته کلی از روشهای حل مسایل بهینه‌سازی شامل روشهای دقیق[۳۲] و روشهای تقریبی[۳۳] وجود دارد
( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
روشهای دقیق، الگوریتم‌هایی می‌باشند که جوابهای بهینه را پیدا نموده و شرط بهینگی را تضمین می‌نمایند. بعضی از این الگوریتمها عبارتند از برنامه‌ریزی پویا و الگوریتمهای خانواده شاخه و کران. روشهای دقیق برای ابعاد کوچک بعضی از مسایل بهینه‌سازی دشوار نیز قابل به کارگیری می‌باشند
در طبقه روشهای تقریبی دو زیر طبقه از الگوریتمها شامل الگوریتمهای تقریب‌زنی و الگوریتمهای هیوریستیکی، وجود دارد. برخلاف هیوریستیک‌ها، که معمولاً به دنبال راه حل های خوب در زمان معقولی می‌باشند، الگوریتمهای تقریب‌زنی حدود قابل اثباتی برای زمان اجرا و کیفیت جواب، ارائه می‌نمایند.
هیوریستیک‌ها راه حل های خوب را برای مسایل با اندازه‌های بزرگ جستجو می‌نمایند. آنها عملکرد قابل قبولی را، همراه با هزینه قابل قبولی برای حوزه وسیعی از مسایل به همراه دارند. هیوریستیک‌ها به دو خانواده تقسیم‌بندی می‌شوند: هیوریستیک‌های خاص و متاهیوریستیک‌ها. هیوریستیک‌های خاص برای حل یک مسأله خاص طراحی شده‌اند. متاهیوریستیک‌ها، الگوریتمهای عمومی می‌باشند که برای حل اغلب مسایل بهینه‌سازی قابل استفاده می‌باشند. آنها را می‌توان به عنوان متدولوژی‌های سطح بالای عمومی دید که به عنوان استراتژی راهنما برای طراحی هیوریستیک‌های خاص، برای حل مسایل بهینه‌سازی خاص، به کار روند.
در بخشهای آتی این فصل ابتدا به تشریح مبانی الگوریتم های فراابتکاری بکار رفته در این تحقیق شامل الگوریتم ژنتیک و الگوریتم توده ذرات pso پرداخته می شود.در ادامه یک رویکرد ترکیبی با بهره گرفتن از این الگوریتم ها به منظور حل مسئله مورد بررسی این تحقیق ارائه می گردد و در نهایت نتایج محاسباتی الگوریتم ارزیابی می شود.
۴-۲ الگوریتم ژنتیک
نظریه تکامل چارلز داروین[۳۴] که در سال ۱۸۵۹ ارائه گردید، جایگاه ویژه‌ای را در مسایل بهینه‌سازی به خود اختصاص داد. این نظریه براساس تکامل بهترین‌ها[۳۵] ارائه گردید و آن را می‌توان به عنوان نقطه شروعی برای محاسبات تکاملی دانست. بررسی وضعیت موجودات زنده، رفتاری پیچیده و بهینه‌ای را در تمامی سطوح شامل یک سلول، یک عضو، یک شخص و یک جمعیت نشان می‌دهد. به عبارت دیگر، در دنیای طبیعی، گونه‌های زیادی از تکامل یا بهبود و حرکت به سمت بهینه‌شدن مشاهده میگردد. این گونه‌ها در رفتار داخل یک سلول تا رفتار جمعیتی از موجودات زنده دیده میشود. نگرش‌های تکاملی برای حل مسایل بهینه‌سازی از این پدیده طبیعی، الگو گرفته شده است.
براساس تئوری انتخاب طبیعی، گیاهان و موجودات زنده‌ای که در حال حاضر وجود دارند، نتیجه میلیون‌ها سال تطابق با تقاضاهای محیط می‌باشند. در هر زمانی، تعدادی از جانداران[۳۶] مختلف، ممکن است که با همدیگر در یک اکوسیستم[۳۷] زندگی نمایند و برای دستیابی به منابع مشترک با همدیگر به رقابت بپردازند. موجوداتی که توانایی بیشتری در دستیابی به منابع و تولیدمثل داشته‌اند، در طبیعت نیز بیشتر مشاهده می‌شده‌اند. موجوداتی که توانایی کمتری داشته‌اند، به دلایل مختلف، به مرور، تعداد آنها کم و کمتر شده و حتی به نابودی کشیده شده‌اند. در این حالت، گفته میشود که گونه‌های اول (با توانایی بیشتر) نسبت به گونه‌های بعدی (گونه‌های دارای توانایی کمتر) شایسته‌تر[۳۸] می‌باشند و مشخصه‌هایی که موجب شده است تا بعضی گونه‌ها شایسته‌تر باشند، مشخصه های ارجح می‌باشند. در طول زمان، گفته میشود که کل جمعیت اکوسیستم دچار تکاملی[۳۹] شده است به طور متوسط، شامل موجوداتی شده است که شایسته‌تر از موجودات قبلی آن می‌باشند، زیرا این موجودات مشخصاتی داشته‌اند که منجر به بقای بیشتر آنها شده است.
تکنیک محاسبات تکاملی (EC) این قواعد تکامل را در الگوریتم‌هایی برای جستجوی راه حل های بهینه مسایل به کار می‌گیرد. در اصل، تکنیک محاسبات تکاملی، توسعه علوم تکامل بیولوژیکی به حوزه علوم محاسباتی و کامپیوتر بوده است. در یک الگوریتم جستجو، تعدادی از راه حل های ممکن از یک مسأله در اختیار بوده و هدف یافتن بهتری راه‌حل ممکن در زمان محدود میباشد. تفاوت اصلی الگوریتمهای تکاملی نسبت به الگوریتمهای دیگر این است که این الگوریتمها مبتنی بر جمعیت[۴۰] عمل می‌نمایند. در این الگوریتمها، معمولاً یک جمعیت اولیه ایجاد و سپس تکامل داده میشود.
مشهورترین تکنیک در تحقیقات محاسبات تکاملی، الگوریتم ژنتیک است. در الگوریتم ژنتیک، معمولاً از یک رشته با طول ثابت[۴۱] برای نمایش راه حل ها استفاده میگردد. در این الگوریم فرض میگردد که هر موقعیت (نقطه) در رشته معرف یک ویژگی خاص از یک فرد (راه‌حل یا عضو جمعیت) است و مقدار مشخص شده برای آن موقعیت، نشان‌دهنده نحوه بیان آن ویژگی در راه‌حل است.
اصول اولیه الگوریتم ژنتیک توسط هالند و همکارانش در طول تحقیقات آنها در زمینه مدل سازی فرایند سازگاری سیستم های طبیعی در قالب سیستمهای مصنوعی ارائه شد و نتیجه این تحقیقات پیدایش الگوریتم زنتیک بود.
الگوریتم ژنتیک کار خود را با جامعه ای از جوابها که از طریق یک فرایند تصادفی ایجاد شده اند آغاز می کند.جامعه جوابها توسط یک تابع برازش ارزشیابس می شود. هر بار که ارزشیابی اعضای جامعه صورت می پذیرد،تعدادی از آنها با توجه به میزان برازش محاسبه شده به عنوان والدین انتخاب می شوند.به طور طبیعی اعضایی که میزان برازش بیشتری دارند از احتمال بیشتری برای انتخاب برخوردارند.با بکارگیری عملیات ژنتیک بر روی والدین، فرزندان آنها تولید می شوند و پس از آن از میان اعضای جامعه فعلی و این فرزدان جامعه جدید تولید می شود. تا این مرحله الگوریت یک تکرار یا یک نسل را طی نموده است و پس از طی چندین نسل به تدریج به سمت جواب بهینه همگرا می شود.
الگوریتم ژنتیک دو ویژگی مهم را در بر دارد. اولین ویژگی رفتار تصادفی این الگوریتم است که نقش مهمی را در الگوریتم بر عهده دارد. رویه‌های انتخاب و تولیدمثل بر پایه روشهای تصادفی عمل می‌نمایند. ویژگی مهم دوم این است که الگوریتم ژنتیک براساس جمعیتی از راه حل ها عمل می کند. استفاده از یک جمعیت در هر تکرار، به جای یک نقطه تکی، مزایای زیادی را به همراه دارد. این الگوریتم می‌تواند راه‌حل‌‌های مختلف را به منظور تولید راه‌حل بهتر با همدیگر ترکیب نموده و می‌تواند از مزایای طبقه‌بندی راه‌حل سود ببرد. یک الگوریتم مبتنی بر جمعیت، قابلیت بیشتری برای موازی‌سازی[۴۲] دارد. با موفقیت الگوریتم ژنتیک، الگوریتمهای دیگری از قبیل استراتژی تکاملی و برنامه‌نویسی ژنتیک، از قواعد تکامل طبیعی استفاده نمودند.
۴-۲-۱ شمای کلی الگوریتم ژنتیک
مراحل الگوریتم ژنتیک استاندارد به صورت زیر می‌باشند:
[شروع] تولید جمعیت اولیه. در این مرحله، یک جمعیت اولیه شامل n کروموزوم تولید میگردد.
[برازندگی] مقدار برازندگی (x) f هر کروموزوم x از جمعیت ارزیابی میگردد.
[جمعیت جدید] ایجاد یک جمعیت جدید با تکرار مراحل زیر تا زمانی که جمعیت جدید کامل گردد:
- [انتخاب] انتخاب دو کروموزوم از جمعیت مطابق با مقدار برازندگی آنها (افراد با برازندگی بیشتر؛ شانس بیشتری برای انتخاب دارند).
- [عملگر تقاطعی][۴۳] با بهره گرفتن از عملگر تقاطغی احتمالی روی والدین انتخاب شده، فرزندان[۴۴] جدید تولید می‌گردند. اگر عملگر تقاطع انجام نگردد، فرزندان همان والدین خود خواهند بود.
- [جهش] با بهره گرفتن از یک عملگر جهش احتمالی، فرزندان جدید تحت عمل جهش قرار می‌گیرند. در این حالت، جهش روی هر لوکوس (موقعیت هر کروموزوم) صورت می‌گیرد.
- [پذیرش] فرزند جدید در جمعیت جدید قرار داده میشود.
[جابه‌جایی] جمعیت جدید (فرزندان) با جمعیت قبلی (والدین) با همدیگر تشکیل یک نسل جدید را می‌دهند. در این حالت، بعضی از والدین حذف شده و بعضی از فرزندان جانشین آنها می‌شوند و دو جمعیت تبدیل به یک جمعیت شده و اندازه جمعیت نیز ثابت می‌ماند.
[شرط توقف] اگر شرط توقف برآورده شده است، توقیف کنید و بهترین راه‌حل در جمعیت جاری (آخرین جمعیت) را گزارش دهید.
[تکرار] در صورت عدم برآورده شدن شرط توقف، به قدم دوم که برازندگی است، برگردید.
۴-۳) اجزای الگوریتم ژنتیک:
در ساختار استاندارد الگوریتم ژنتیک بحث شده در قسمت قبلی، اجزایی به کار گرفته شده است که در زیر بعضی از آنها مورد بحث قرار می‌گیرد.
۴-۳-۱) کروموزوم:
رشته یا دنباله‌ای از بیت‌ها که به عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مسأله موردنظر میباشد، کروموزوم نام دارد. در حقیقت، بیت‌های یک کروموزوم، نقش ژن‌ها را در طبیعت بازی می‌کنند. هر بیت، متغیری گسسته است که از یک مجموعه Q یا آلل عضوی انتخاب میشود. چنانچه از کدگذاری باینری استفاده شود،هر بیت یکی از دو مقدار ۰ یا ۱ را می‌پذیرد و بنابراین در این حالت Q=2 میباشد.
۴-۳-۲) جمعیت:[۴۵]
مجموعه‌ای از کروموزوم‌ها را جمعیت گویند. یکی از ویژگی‌های ژنتیک این است که به جای تمرکز بر روی یک نقطه از فضای جستجو یا یک کروموزوم، بر روی جمعیتی از کروموزوم‌ها تمرکز می‌کند. بدین‌ترتیب در هر مرحله، الگوریتم دارای جمعیتی از کروموزوم‌ها بوده که خواص موردنظر را بیشتر از جمعیت مرحله قبل دارا میباشد. هر جمعیت یا یک نسل از کروموزوم‌ها، دارای یک اندازه میباشد که به اندازه جمعیت[۴۶] معروف است. اندازه جمعیت معرف تعداد کروموزوم‌های موجود در جمعیت یا یک نسل است. اگر تعداد کروموزوم‌های خیلی کم باشد، امکان شکل‌گیری عملیات جابه‌جایی توسط الگوریتم ژنتیک بسیار کم خواهد بود و تنها قسمت کمی از فضای جستجو مورد کاوش قرار خواهد گرفت. براساس تحقیقات، جمعیت‌های با اندازه حدود ۲۰ تا ۳۰ کروموزوم، مناسب‌تر می‌باشند. البته، گاهی اوقات جمعیت با اندازه ۵۰ تا ۱۰۰ بهترین جوابها را داده‌اند. بعضی تحقیقات نیز نشان می‌دهد که اندازه جمعیت باید براساس نوع مسأله و کدینگ آن تعریف شود و افزایش بیشتر آن بی‌فایده خواهد بود و هرگز به حل سریع‌تر مسأله کمک نمی‌کند
۴-۳-۳) مقدار برازندگی:[۴۷]
مناسب‌بودن یا نبودن جواب، با معیاری که از تابع هدف به دست می‌آید، سنجیده میشود. جواب هرچه مناسب‌تر باشد، به همان اندازه مقدار برازندگی بزرگتری دارد. برای آنکه شانس بقای چنین جوابی بیشتر شود، احتمال بقای آن، متناسب با مقدار برازندگی آن در نظر گرفته میشود. بنابراین، کروموزومی که برازنده‌تر است با احتمال بیشتری در تولید فرزندان شرکت می‌کند و دنباله‌های بیشتری از آن به وجود می‌آید. به عنوان مثال، چنانچه هدف بیشینه‌کردن یک تابع باشد، مقدار برازندگی، یک تابع صعودی از تابع هدف در نظر گرفته میشود و اگر هدف یافتن مقدار کمینه یک تابع باشد، عدد برازندگی، یک تابع نزولی از آن قرار داده میشود. معمولاًً در مواردی که امکان دارد و مناسب باشد، تابع برازندگی را در فاصله [۰و۱] نرمال می‌کنند.
۶-۳-۴) کدگذاری:
کدگذاری، فرایندی است که به واسطه آن، راه حل ها در فضای فیزیکی مسأله تبدیل به راه حل هایی با کدهایی میگردد که قابل فهم برای کامپیوتر و محاسبات است. به عبارت دیگر، راه‌حل واقعی با بهره گرفتن از ژن‌های او بیان میگردد. البته، ژن‌ها نیز به زبان کامپیوتری بیان می‌گردند. کدگذاری تأثیر زیادی روی کیفیت الگوریتم خواهد داشت و طراحی مناسب یک ساختار کدگذاری، از اهمیت بالایی در الگوریتم ژنتیک برخوردار است. روشهای مختلفی برای کدگذاری یک راه‌حل وجود دارد که در فصل دوم مورد بحث قرار گرفتند و در این قسمت به آنها پرداخته نمی‌شود. راه حل های ارائه شده در آن فصل برای کدگذاری راه حل ها در الگوریتم ژنتیک نیز کاربردی می‌باشند. همچنین، خصوصیات یک کدگذاری مناسب نیز در آن فصل بحث گردید که در ارتباط با الگوریتم ژنتیک نیز مورد استفاده می‌باشند.
۴-۳-۵) انتخاب:
انتخاب، فرایند انتخاب دو والد از جمعیت برای عمل تقاطع است. در این مرحله، باید در ارتباط با نحوه انتخاب والدین برای عمل تقاطع، نحوه تولید فرزندان و تعداد فرزندان تصمیم‌گیری گردد. هدف انتخاب این است که والدین شایسته‌تر انتخاب شده که منجر به تولید فرزندانی با برازندگی بالا گردد. کروموزوم‌هایی که از جمعیت اولیه برای تولیدمثل انتخاب می‌گردند، والدین نام دارند. انتخاب، نحوه تعیین این والدین را مشخص می کند. براساس نظریه کامل داروین، بهترین‌ها باید شانس بیشتری برای تولیدمثل و بقا داشته باشند.
انتخاب روشی است که به طور تصادفی کروموزوم‌هایی را از جمعیت، برای تولیدمثل بیرون می‌آورد. کروموزوم با تابع برازندگی بالاتر، شانس بیشتری برای انتخاب دارد. فشار رویه انتخاب[۴۸] به معنای درجه توجه به والدین بهتر در رویه انتخاب است که توسط گلدبرگ و دب[۴۹] در سال ۱۹۹۱ تعریف گردید. فشار بالای رویه انتخاب منجر به تأکید بیشتر در انتخاب والدین با شایستگی بیشتر میگردد.
همگرایی الگوریتم ژنتیک وابستگی بالایی به دامنه و شدت فشار رویه انتخاب دارد. فشار بالای رویه انتخاب منجر به افزایش نرخ همگرایی الگوریتم میگردد. الگوریتم ژنتیک قادر به یافتن جواب بهینه یا نزدیک به بهینه، تحت دامنه معقولی از فشار رویه انتخاب میباشد. با این وجود، اگر فشار رویه انتخاب خیلی کم باشد، نرخ همگرایی خیلی کند خواهد شد و الگوریتم ژنتیک نیاز به زمان بسیار طولانی و غیرضروری برای رسیدن به جواب بهینه خواهد داشت. در صورتی که فشار رویه انتخاب خیلی زیاد باشد، موجب میگردد که الگوریتم ژنتیک به طور نابهنگام به بهینه تقریبی همگرا گردد. از طرفی، در هنگام طراحی برنامه انتخاب، باید دقت گردد که گوناگونی جمعیت حفظ گردد که از همگرایی زودرس الگوریتم جلوگیری گردد.
به‌طور کلی، دو نوع از برنامه انتخاب وجود دارد، رویه مبتنی بر تناسب[۵۰] و رویه مبتنی بر ترتیب.[۵۱] رویه مبتنی بر تناسب، والدین را براساس مقدار برازندگی آنها نسبت به مقدار برازندگی سایر والدین جمعیت انتخاب می‌کند. برنامه انتخاب مبتنی بر ترتیب، والدین را نه بر اساس مقدار خام برازندگی آنها، بلکه براساس رتبه آنها در جمعیت انتخاب می‌کند. در این حالت، فشار رویه انتخاب مستقل از توزیع مقدار برازندگی جمعیت در نظر گرفته شده و مقدار ترتیب (رتبه) آنها در جمعیت به جای مقدار برازندگی آنها، در نظر گرفته میشود. چند روش برای رویه انتخاب در زیر آمده است.
۴-۳-۵-۱) روش چرخ رولت:[۵۲]
روش چرخ رولت، یکی از روشهای سنتی انتخاب در الگوریتم ژنتیک است. در این حالت یک کروموزوم از استخر تولیدمثل[۵۳] براساس احتمالی متناسب با مقدار شایستگی‌اش انتخاب میگردد. در این مدل، سطح چرخ به بخش‌هایی تقسیم میشود که تعداد آنها برابر با تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم است. سپس چرخ به گردش در می‌آید تا در نقطه‌ای به تصادف متوقف گردد. این نقطه، کروموزوم انتخاب شده را مشخص می‌سازد. شکل ۴-۱۳ شمایی از چرخ رولت را نشان می‌دهد. در این شکل، کروموزوم‌های ۱ و ۲ دارای برازندگی بیشتری نسبت به کروموزوم‌های ۳ و ۴ می‌باشند و بنابراین در مرحله انتخاب، شانس بیشتری دارند. این شیوه انتخاب سبب میشود که با گذشت زمان، تعداد کروموزوم‌های مطلوب در جمعیت افزایش یابد به طوری که میانگین مقدار برازندگی جمعیت، در مقایسه با جمعیت مرحله قبل، بیشتر میشود.
شکل۴-۱: چرخ رولت [۱]
شکل ۴-۲ نمونه‌ای از محاسبات در چرخ رولت را نشان می‌دهد. همان‌طور که در این شکل مشاهده میگردد، ۷ فرد (راه‌حل) با مقدار شایستگی مشخص شده، وجود دارند. سطح چرخ رولت متناسب با مقدار شایستگی آنها تنظیم شده است. دو نوع چرخ رولت در این شکل مشاهده میگردد. در چرخ سمت چپ، با هر بار چرخش یک کروموزوم انتخاب میگردد. در این حالت، پس از چرخاندن چرخ، در هنگام توقف چرخ، کروموزوم مقابل نشانه انتخاب میگردد. در چرخ سمت راست، چهار نشانه وجود دارد و در هر بار چرخش، چهار فرد یا کروموزوم انتخاب میگردد.
شکل۴-۲: نمونه‌ای از انتخاب در چرخ رولت [۱]
پیاده‌سازی مدل چرخ رولت در کامپیوتر، می‌تواند شامل مراحل زیر باشد:
کروموزوم‌های جمعیت به شکل دنباله در آورده شده و سپس مجموع مقدار برازندگی هر کروموزوم با مقدار برازندگی تمام کروموزوم‌های قبل از آن محاسبه میگردد. سپس مقدار برازندگی نسبی تجمعی کروموزوم‌ها محاسبه میگردد. یک عدد تصادفی n بین صفر و یک ایجاد میشود. از بین کروموزوم‌ها، اولین کروموزومی که مقدار برازندگی تجمعی نسبی آن، بیشتر از n باشد، انتخاب میگردد. جدول ۴-۱ نمونه‌ای از انتخاب کروموزوم‌ها با استفاد از مدل چرخ رولت، را نشان می‌دهد.
