If then
and
}

}
الگوریتم ۴-۱ به گونه ­ای طراحی شده است که برای زمان­بندی هر کار، زمان شروع آن کار را در اولین زمانی که تمام پیش نیازهای آن انجام شده ­اند و شرط محدودیت منابع را نقض نمی کند، زمان­بندی کند که همان طرح تولید زمانبندی سری است. بنابراین، یک ساختار جواب به صورت تعریف شده در اینجا، تنها زمانی می ­تواند نشدنی باشد که شرط پیش­نیازی و پس نیازی را نقض کند که در این صورت، یک مقدار بزرگ، به مقدار تابع هدف آن اختصاص می­یابد، تا در مراحل بعدی اصلاح شود. در نمایش جواب از روش نمایش جواب بر اساس لیست فعالیتها استفاده می شود.

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

۴-۱-۲)جمعیت اولیه

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

1. 1. جواب اولیه بدست آمده، شدنی است: در بخش قبل گفته شد، یک ساختار جواب تعریف شده تنها در صورتی نشدنی است که شرط­های پیش­نیازی و پس نیازی را نقض کند، اما نحوه تولید جواب اولیه در الگوریتم طراحی شده به گونه ای است که این شروط، به هیچ عنوان نقض نمی­شوند.

1. 1. تولید جواب شدنی به صورت تصادفی است: در توضیح روند کلی الگوریتم ASO گفته شد، در هر مرحله، به هر یک از جواب­ها با توجه به مقدار تابع هدف خود، نسبت به سایر اعضای جمعیت، عددی به عنوان نسبت داده می­ شود که این عدد، تنها در صورتی معنا پیدا می­ کند که مقدار تابع هدف برای اعضای جمعیت با هم فرق داشته باشند. بنابراین در صورتی که تمام جمعیت جواب اولیه، یکسان باشند، بی معنی می­ شود و همچنین جواب­های بهترین هر نسل و بهترین کل نیز با این جواب­ها برابر خواهند بود، که در ادامه کار الگوریتم مشکل ساز خواهند بود. در هر مرحله از تولید جواب اولیه، یکی از کارهایی که تمام پیش­نیاز های آنها قبلا زمان­بندی شده ­اند به صورت تصادفی انتخاب می­ شود، که این روند انتخاب تصادفی باعث متمایز گشتن جواب­های اولیه در جمعیت اولیه می­شوند.روش بدست آوردن جواب اولیه بر اساس روش ابتکاری سری با قانون اولویت تصادفی بوجود می آید.

۴-۱-۳)فرایند برنامه ریزی برای حرکت هر عضو جامعه

در هر مرحله از الگوریتم ASO برای هر یک از اعضای جامعه، با توجه به موقعیت فعلی آن عضو، موقعیت گذشته آن و همچنین موقعیت آن عضو نسبت به سایر اعضای جامعه سیاست­های متمایزی برای ایجاد یک همسایه جدید برای آن عضو اتخاذ می­ شود. برای انتخاب سیاست مناسب با موقعیت فعلی هر عضو پارامتر ، برای انتخاب سیاست مناسب برای موقعیت عضو نسبت به سایر اعضای جامعه پارامتر و برای انتخاب سیاست مناسب با توجه به گذشته آن عضو پارامتر محاسبه می­شوند. سپس با توجه به مقادیر این پارامترها سیاست­های متمایزی اتخاذ می­ شود که در ادامه به توضیح آنها پرداخته می­ شود.

۴-۱-۳-۱)انتخاب سیاست حرکتی مبتنی بر مکان فعلی

برای هر یک از اعضای جامعه پارامتر به صورت زیر بدست می ­آید.
که تابع هدف مقدار تابع هدف هر جواب، که در اینجا زمان اتمام آخرین کار است، می­باشد. این معادله از معادله(شماره معادله مربوط به تعریف ضریب FI در بخش معرفی الگوریتم) با قرار دادن برای همه اعضای جامعه بدست آمده است. در صورتی که باشد در این صورت مقدار برابر صفر خواهد بود. حداکثر ممکن ضریب هنگامی اتفاق می­افتد که برابر صفر باشد که این با توجه به مساله تعریف شده غیر ممکن است. بنابراین خواهد بود. سیاست­های مختلف با توجه به مقدار به صورت زیر است:
عملگر جهش مورد استفاده در بالا، موقعیت یک کار را به تصادف انتخاب می­ کند و سپس کار واقع در آن موقعیت را با کار موقعیت دیگری در ساختار جواب که حداکثر سه خانه اختلاف دارند تعویض می­ کند. عملگر جهش موقعیت یک کار را به تصادف انتخاب کرده و سپس کار آن موقعیت را به موقعیتی دیگر در فاصله حداکثر سه خانه­ای آن موقعیت انتقال می­دهد. عملگر جهش نیز بدین صورت است که یک موقعیت از ساختار جواب به صورت تصادفی انتخاب می­ شود و سپس کارهای سمت راست این خانه مانند تولید جواب اولیه به صورت تصادفی و به گونه ­ای بدست می­آیند تا شرایط پس نیازی و پیش نیازی را رعایت کنند. مقدار پارامتر با بهره گرفتن از طراحی آزمایش­ها در بخش ‏۰ بدست می ­آید.
در عملگر جهش و در صورتی که پس از اجرای این عملگرها، شرایط پس نیازی و پیش­نیازی نقض شوند، این عملگرها آنقدر تکرار می­شوند تا شرایط ارضا شوند.

۴-۱-۳-۲)انتخاب سیاست حرکتی مبتنی بر مکان سایر اعضای جامعه انسانی

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

عملگر

در این عملگر نقطه­ای از کروموزوم اول به تصادف انتخاب می­ شود و سپس سمت چپ این کروموزوم در کروموزوم نهایی کپی می­ شود. ترتیب باقی خانه­های کروموزوم نهایی با بهره گرفتن از کروموزوم دوم بدست می­آیند. شکل ۴-۳نحوه عملکرد این عملگر را تشریح می­ کند.

شکل ۴-۳ : نحوه انجام عملگر Crossover1

عملگر

در عملگر ابتدا قسمت های برابر دو کروموزوم در کروموزوم نهایی منتقل می­ شود. سپس دو اشاره گر برای هر یک از کروموزوم­ها که به آخرین نقطه یکسان دو کروموزوم اشاره دارد تعریف می­کنیم. در هر مرحله اگر خانه­هایی که این اشاره­گرها به آنها اشاره می­ کنند قبلا در کروموزوم نهایی جایگذاری شده باشند، اشاره­گر مربوطه یک خانه به سمت راست حرکت می­ کند. در غیر اینصورت یکی از دو کروموزوم به تصادف انتخاب می­شوند و عدد خانه­ای که اشاره­گر آن کروموزوم قرار دارد در کروموزوم نهایی کپی می­ شود و سپس اشاره­گر یک خانه به سمت چپ انتقال می­یابد. شکل۴-۴ و جدول۴-۱ ذیل یک مثال و مراحل تولید جواب نهایی را نشان می­ دهند.

شکل۴-۴: نحوه انجام عملگر Crossover2
جدول ۴-۱ : مراحل انجام عملگر crossover2

مرحله

کروموزوم ۱

کروموزوم ۲

مجاز است؟

کروموزوم انتخاب شده

عدد انتخاب شده

کروموزوم حاصل

۱

۲

۱

بله