قدم چهارم : رشته تولید شده بوسیله رابطه (۳-۱۵) در محدوده قابل قبول قرار گیرد :
(۳-۱۵)
که در آن : L طول رشته، Pm(i) مقدار دهدهی i امین واحد تولیدی در رشته .
قدم پنجم : مقدار برازندگی را برای هر رشته در جمعیت حساب کن.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

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

۳-۵-۲-۵ فلوچارت الگوریتم ژنتیک

در این بخش چرخه الگوریتم ژنتیکی به صورت خلاصه در فلو چارت شکل (۳-۴) نمایش داده شده است:
جفت را برای تولید دوباره انتخاب کن
عملگر ترکیب
جهش
همگرایی را بررسی کن
بله
خیر
تابع هزینه را مشخص کن، هزینه متغیرو پارامتر های الگوریتم ژنتیک را انتخاب کن
جمعیت اولیه را تولید کن
کروموزوم‌ها را رمز گشایی کن
برای هر کروموزوم هزینه را بیاب

شکل (۳-۴) فلوچارت الگوریتم ژنتیک

۳-۵-۳ الگوریتم بهینه‌سازی ازدحام ذرات (PSO)

جیمز کندی^[۲۸]، روانشناس اجتماعی، و راسل سی اپرهارت^[۲۹]، مهندس برق، صاحبان اصلی ایده‌ی الگوریتم بهینه‌سازی ازدحام ذرات می‌باشند. آن‌ها در ابتدا قصد داشتند که با بهره گیری از مدل‌‌های اجتماعی و روابط موجود اجتماعی، نوعی از هوش محاسباتی را به وجود بیاورند که به توانایی‌‌های فردی ویژه نیازی نداشته باشد. اولین شبیه سازی آن‌ها که در سال ۱۹۹۵ انجام گردید، آن‌ها را به سمت شبیه سازی رفتار پرندگان برای یافتن دانه رهنمون کرد. این کار تحت تاثیر کار هپنر^[۳۰] و گرنارد^[۳۱] بود، که در سال ۱۹۹۰ برای شبیه­سازی رفتار پرندگان به صورت یک سیستم غیر خطی انجام گرفته بود. کار کندی و ابرهارت، منجر به ایجاد الگوریتمی قوی برای بهینه‌سازی، به نام الگوریتم بهینه‌سازی گروه ذرات یا PSO شد[۹].

۳-۵-۳-۱ مفاهیم اصلی الگوریتم بهینه‌سازی ازدحام ذرات

در الگوریتم بهینه‌سازی ازدحام ذرات، تعدادی از موجودات وجود دارند، که به آنها ذره گفته می‌شود و در فضای جستجو تابعی که قصد کمینه کردن (و یا بهینه کردن) مقدار آن را داریم، پخش شده ­اند. هر ذره مقدار تابع هدف را در موقعیتی از فضا که در آن قرار گرفته است، محاسبه می‌کند. سپس با بهره گرفتن از ترکیب اطلاعات محل فعلی­اش و بهترین محلی که در گذشته در آن بوده است و همچنین اطلاعات یک یا چند ذره از بهترین ذرات موجود در جمع، جهتی را برای حرکت انتخاب می‌کند. همه ی ذرات جهتی برای حرکت انتخاب می‌کنند و پس از انجام حرکت، یک مرحله از الگوریتم به پایان می‌رسد. این مراحل چندین بار تکرار می‌شوند تا آن که جواب مورد نظر به دست بیاید. در واقع انبوه ذرات که کمینه ی یک تابع را جستجو می‌کنند، همانند دسته‌ای از پرندگان عمل می‌کنند که بدنبال غذا می‌گردند ] ۹و۱۱ [.
هر ذره در الگوریتم بهینه‌سازی ازدحام ذرات از سه بردار d بُعدی تشکیل شده است که d، بُعد فضای جستجو می‌باشد. برای ذره i اُم این سه بردار عبارتند از : موقعیت فعلی ذره، سرعت حرکت ذره و بهترین موقعیتی که ذره تا به حال تجربه کرده است. مجموعه‌ای از مختصات است که موقعیت فعلی ذره را نمایش می‌دهد. در هر مرحله که الگوریتم تکرار می‌شود، به عنوان یک جواب برای مساله محاسبه می‌شود. اگر این موقعیت بهتر از جواب‌‌های پیشین باشد در ذخیره می‌شود.
مقدار تابع هدف در و مقدار تابع هدف در است که هر دو از عناصر تشکیل دهنده ی هر ذره به حساب می‌آیند. ذخیره کردن مقدار برای انجام مقایسه‌‌های بعدی، ضروری است. اما ذخیره کردن مقدار ضروری نمی باشد. در هر تکرار و جدیدی بدست می‌آیند و منظور از اجرای الگوریتم، بهتر کردن و به احتمال است.
الکوریتم بهینه‌سازی ازدحام ذرات چیزی فراتر از یک مجموعه ی ذرات است. هیچ کدام از ذرات قدرت حل هیچ مساله‌ای را ندارند، بلکه هنگامی می‌توان به حل مساله امیدوار شد که آن‌ها با هم ارتباط و تعامل داشته باشند. در واقع برای انبوه ذرات، حل مساله، یک مفهوم اجتماعی است که از رفتار تک تک ذرات و تعامل میان آن‌ها به وجود می‌آید. موقعیتی که به وسیله ی همه ی ذرات پیدا شده است به صورت نشان داده می‌شود که با مقایسه ی مقادیر به ازای همه ی ذرات و از میان ‌ها انتخاب می‌شود. مقدار تابع هدف در به صورت نشان داده می‌شود. اگر تعداد ذرات موجود در جمعیت، n باشد، آنگاه می‌توان روابط زیر را نوشت :
(۳-۱۶)
t نشان دهنده ی تکرار الگوریتم می‌باشد.

۳-۵-۳-۲ پارامتر‌‌های الگوریتم بهینه‌سازی ازدحام ذرات

برای اجرای بهینه‌سازی ازدحام ذرات، به چند پارامتر احتیاج است. که در ادامه ارائه شده است.
۱-توده ذرات
n ذره که در ابتدا به صورت اتفاقی جایابی می‌گردند و تابع را به سمت جواب بهینه رهنمون می‌سازند. هم چنین هر ذره به نوبه خود به صورت تصادفی در توده حرکت می کند. این توده به صورت زیر در نظر
گرفته می‌شود :
(۳-۱۷)
: این پارامتر، بیانگر بهترین موقعیتی است که هر ذره در طول اجرای الگوریتم کسب کرده است.
: این متغیر بهترین موقعیتی را که کل ذرات در طول اجرای الگوریتم کسب کرده‌اند، نشان می‌دهد.
ضریب لختی یا اینرسی
ضریب اینرسی w بر روی همگرایی الگوریتم بهینه‌سازی ازدحام ذرات تاثیر مستقیم دارد. در واقع می‌توان به واسطه ی ضریب اینرسی، تاثیر سرعت‌‌های گذشته را بر سرعت‌‌های زمان حال کنترل کرد. می‌توان برای برقراری موازنه بهتر میان جستجوی سراسری و جستجوی محلی مقدار w را تغییر داد. مقدار زیاد برای w باعث می‌شود که ذرات موجود در الگوریتم، به جستجوی مناطق جدیدتر روی بیاورند و یک جستجوی سراسری را انجام دهند. در مقابل یک مقدار کم برای w باعث می‌شود که ذرات در منطقه ی محدودی بمانند و در واقع یک جستجوی محلی را انجام دهند. جستجوی محلی برای دقیق‌تر کردن جواب‌‌های فعلی مناسب است و جستجوی سراسری برای یافتن جواب‌‌های بهتری که به احتمال در جاهای ناشناخته از فضای جستجو وجود دارند، به کار می‌رود.انتخاب w به صورت یک عدد تصادفی با توزیع یکنواخت در بازه‌ی ]۵/۰,۱[ نتایج خوبی را به همراه دارد. به طور کلی، ضریب اینرسی w براساس رابطه زیر ارائه می‌شود :
(۳-۱۸)
که داریم: و مقدار بیشینه و کمینه ضریب اینرسی، تعداد تکرار فعلی، تعداد تکرار بیشینه.
سرعت ذره
محدود کردن سرعت در بازه ی . اگر الگوریتم بدون در نظر گرفتن محدودیت سرعت
اجرا شود، در عرض چندین تکرار، سرعت ذرات به شدت افزایش می‌یابد و به مقادیر غیر قابل قبول می‌رسد.