مدل پریتسکر به صورت ذیل است :
s.t.
y_jt {۰,۱} ; j = 0, …, n+1 , t = EST_j , … , LST_j (۹)
معادله ۵، تابع هدف مسئله است که کمینه سازی زمان اتمام پروژه را نشان میدهد. معادله ۶ ، بیانگر این مطلب است که هر فعالیت فقط یک زمان شروع دارد که باید در محدوده [EFT_i , LFT_i] برای فعالیت i ام است. معادله ۷ ، بیانگر روابط تقدمی بین فعالیتها است. معادله ۸ ، بیانگر محدودیت منابع است. معادله ۹ ، نشان دهنده صفر و یک بودن متغیر y_jt است.

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

۳-۳)معرفی الگوریتم بهینه سازی جامعه نامنظم

از آنجاییکه الگوریتم بهینه سازی جامعه نامنظم^[۲۳۰] در سال ۲۰۱۱ توسط احمدی جاوید^[۲۳۱] به وجود آمده است تنها منبع موجود برای پی بردن به علل طراحی این الگوریتم و شرح فرایند الگوریتم که در این فصل قصد تشریح آنها را داریم، منبع ]۳[ است که توسط ابداع کننده آن احمدی جاوید در مقاله ای آمده است و بیشتر مطالب این فصل بر گرفته از منبع یادشده است.

۳-۳-۱)ایده طراحی الگوریتم

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

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

1. 1. با وجود اینکه الگوریتمهای فراابتکاری بهینه سازی کلونی مورچه گان (ACO) و بهینه سازی دسته پرندگان (PSO) در ابتدای پیدایشان به ترتیب برای مسائل گسسته و پیوسته به وجود آمدند الگوریتم فراابتکاری جدید بهینه سازی جامعه نامنظم (ASO) در بدو پیدایش هم برای مسائل گسسته و هم برای مسائل پیوسته میتواند مورد استفاده قرار گیرد و این برتری میتواند برای این الگورتم فراابتکاری مبتنی بر جمعیت از نوع هوش مصنوعی نسبت به سایر الگوریتمهای فراابتکاری هوش جمعی باشد.

1. 1. الگوریتم فراابتکاری بهینه سازی جامعه نامنظم (ASO) میتواند برای همه مسائلی که به وسیله الگوریتمهای فراابتکاری بهینه سازی دسته پرندگان (PSO) و الگوریتم ژنتیک (GA) حل میشود به طور مستقیم وساده مورد استفاده قرار گیرد و این یک حسن برای این الگوریتم جدید فراابتکاری است.

1. 1. تحت شرایط های عادی جوابهای الگوریتم بهینه سازی جامعه نامنظم (ASO) به صورت حدی به سمت جواب بهینه سراسری با احتمال یک، همگرا است و این مطلب، توانایی این الگوریتم را در یافتن جواب نزدیک به بهینه نشان میدهد.

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

۳-۳-۲)تشریح کلی الگوریتم

ساختار الگوریتم فراابتکاری مبتنی بر جمعیت از نوع هوش جمعی به خصوصیت اعضای جمعیت جامعه وابسته است. بنابراین انتخاب جامعه با اصول مناسب در طراحی این الگوریتمها بسیار با اهمیت است. واقعیت این است که جامعه انسانی به خاطر خصوصیات منحصر به فرد و ویژه ای که دارد انگیزه ای شد، تا الگوریتم فراابتکاری مبتنی بر جمعیت از نوع هوش جمعی که از جامعه انسانی الهام گرفته است را ابداع شودکه در آن فرض بر آن است که به جای جمعیت مبتنی بر پرندگان یا مورچه گان یا حشرات از یک جامعه انسانی با رفتار ناهنجار^[۲۳۲] استفاده کنیم. در واقع الگوریتم بهینه سازی جامعه نامنظم یک روش بهینه سازی جدید است که از جامعه انسانی الهام گرفته است که اعضای آن برای بهبود شرایطشان به طور ناهنجار رفتار میکنند. در این الگوریتم فرض بر آن است که اعضای این جامعه انسانی دارای رفتارهای غیرمعقولانه^[۲۳۳] و حادثه جو^[۲۳۴] دارند به طوریکه ممکن است اعضای این جامعه به سمت شرایط و وضعیت بدتر حرکت کنند. الگوریتم فراابتکاری بهینه سازی جامعه نامنظم (ASO) این امکان را به ما میدهد که کل فضای جواب را جستجو کنیم واز دام بهینه های محلی دوری کنیم. حال ساختار کلی الگوریتم ASO را برای حل هر مسئله بهینه سازی در ذیل نشان میدهیم.

۳-۳-۳)مفروضات و نکات اولیه الگوریتم

فرض کنیم که S فضای جواب ما باشد و تابع f : S → R ، تابعی باشد که ما قصد داریم آن را روی فضای جواب S مینیمم کنیم. یک جامعه متشکل از N عضو را در نظر بگیرید که در داخل یک سرزمین ناشناخته در حال جستجو هستند تا بهترین مکان را برای زندگی پیدا کنند ، ما این سرزمین ناشناخته را به عنوان فضای جواب S در نظر میگیریم و بهترین مکان زندگی را جایی در نظر میگیریم که تابع f بر روی فضای جواب S ، به حالت مینیمم درآید. خصوصیات اصلی اعضای این جامعه انسانی N نفره آن است که در روند جستجویشان رفتارهای ماجراجویانه و نامعقول دارند تا حرکت بعدی اعضای جامعه از قبل مشخص نباشد. X_i(k) مکان عضو i ام از جامعه انسانی N نفره را در مرحله k ام از روند جستجو برای پیدا کردن بهترین مکان زندگی در فضای جستجوی S را نشان میدهد. یکی دیگر از خصوصیات اصلی اعضای این جامعه N نفره آن است که هر عضو در مرحله k ام از بهترین مکان سراسری تا این مرحله که توسط کلیه اعضای جامعه بدست آمده است آگاهی دارد، ما بهترین مکان سراسری را تا مرحله k ام با نماد G(k) نشان میدهیم.همچنین بهترین مکانی که توسط عضو i ام جامعه تا مرحله k ام به طور فردی تجربه شده است را هر فرد جامعه، آگاهی کامل به آن دارد و ما این مکان را با نماد P_i(k) نشان میدهیم. نماد i_k^* عضوی از جامعه انسانی N نفره را نشان میدهد که در مرحله k ام در بهترین مکان نسبت به تمام اعضا قرار دارد.

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

هر عضو این جامعه نامنظم یک روند برنامه ریزی شده برای تصمیم گیری در مورد اینکه چگونه حرکت کند و مکان خودش را در مرحله بعد چگونه تغییر دهد در برنامه اش دارد. برای شناخت این روند حرکتی هر عضو جامعه انسانی نامنظم، سه سیاست حرکتی و نیز ترکیب این سیاست ها را برای مشخص کردن مکان خود در مرحله بعد دارد. حال میخواهیم این سه سیاست حرکتی را و همچنین ترکیب این سیاستها را در الگوریتم فراابتکاری ASO تشریح کنیم.

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

اولین سیاست حرکتی اعضا ی جامعه نامنظم در مرحله k ام ، که مبتنی بر مکان فعلی اعضا است با نماد MP_i^current(k) ^[۲۳۵] نشان میدهند. در حالت کلی سیاست حرکتی MP_i^current(k) ، یک روش جستجوی همسایگی است که هر عضو میتواند روش های جستجوی متفاوتی را انتخاب کند یا ممکن است همه اعضای جامعه انسانی فقط یک سیاست جستجوی همسایگی را انتخاب کنند. برای عضو i_k^* ، در این الگوریتم برای روش جستجوی همسایگی، استفاده از جستجوی همسایگی با یک سطح بالاتر از گوناگونی را، برای اجتناب از به دام افتادن در بهینه محلی پیشنهاد می شود. برای کمی کردن سیاست حرکتی مبتنی بر مکان فعلی،شاخص بی ثباتی برای این سیاست حرکتی معرفی می شود وآنرا با نماد FI_i(k) ^[۲۳۶] برای عضو i ام در مرحله k ام نشان میدهند. این شاخص میزان عدم رضایت عضو i ام را برای مکان کنونی اش، نسبت به عدم رضایت سایر اعضا را نشان میدهد. هنگامیکه تابع هدف f مقداری مثبت بر روی فضای جواب S دارد، ممکن است شاخص FI_i(k) به صورت حالت ذیل تعریف شود که در آن α_i مقداری نامنفی و در محدوده ]۱و۰[ است و فرمول آن به صورت ذیل است:
FI_i(k) = 1 – α_i – (۱ – α_i)
در فرمول بالا همه اعداد در محدوده ]۱و۰[ است. به عنوان یک پیشنهاد ممکن است بهتر باشد که برای اعضایی از جامعه انسانی که دارای شاخص بی ثباتی FI_i(k) با مقدیر بزرگ هستند (مقادیر نزدیک به یک)از روش جستجوی همسایگی استفاده کنیم که مکان فعلی این اعضا را بیشتر تغییر دهد به این دلیل که شاخص بی ثباتی FI_i(k) با مقادیر بزرگ نشان دهنده عدم رضایت بالای عضو i ام در مرحله k ام است بنابراین تغییر بیشتر مکان فعلی این اعضا معقولانه است.

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

دومین سیاست حرکتی با نماد MP_i^society(k) ^[۲۳۷] ، سیاست حرکتی مبتنی بر مکانهای سایر اعضای جمعه نامیده میشود. هر عضو جامعه نامنظم انسانی در سیاست مبتی بر مکانهای سایر اعضای جامعه MP_i^society(k) ، مکان G-best که همان بهترین مکان تا مرحله k ام است را درحالت جامعه هنجار، دراین سیاست حرکتی مد نظر دارد، اما از آنجاییکه تصمیم های اعضای جامعه حادثه جویانه و نامعقول است هر عضو جامعه ممکن است در این سیاست حرکتی، مکانهای سایر اعضای جامعه به غیر از مکان G-best را برای حرکت بعدی اش انتخاب کند. در الگوریتم فراابتکاری ASO ،به منظور کمی کردن سیاست حرکتی مبتنی بر مکان سایر اعضا جامعه، شاخص نامنظم خارجی را تعریف میکنند و آنرا برای عضو i ام در مرحله k ام با نماد EI_i(k) ^[۲۳۸] نشان میدهیند. شاخص نامنظم خارجی EI_i(k) میتواند در دو سناریو به کار گرفته شود:

• • در حالت اول شاخص نامنظم خارجی EI_i(k) را به عنوان احتمالی که عضو i ام ممکن است در مرحله k ام، به طور نامعقول و حادثه جویانه رفتارکند و در نتیجه سیاست حرکتی خودش را مبتنی بر انتخاب تصادفی مکان اعضای دیگر به وجود آورد در حالیکه در این سیاست حرکتی هیچ ارتیاطی با G-best ندارد.

• • در حالت دوم ما شاخص نامنظم خارجی را EI_i(k) با یک آستانه مقداری مقایسه میکنیم. اگر شاخص نامنظم خارجی از این آستانه مقداری بیشتر باشد بنابراین عضو i ام در مرحله k ام به طور تصادفی مکان خود را انتخاب میکند و اگر مقدار شاخص نامنظم خارجی از مقدار آستانه مقداری کمتر باشد عضو i ام در مرحله k ام طبق G-best حرکت میکند.

مقدار شاخص نامنظم خارجی EI_i(k) میتواند براساس مکان عضو iام که با G-best مرتبط است به صورت ذیل برای بعضی از مقادیر مثبت θ_i تعریف شود :
EI_i(k) = 1 –
با وجود فرمول بالا، در الگوریتم پیشنهاد شده است که شاخص نامنظم خارجی در سطوح متنوع از جامعه مورد استفاده قرار گیرد، به عنوان مثال میتوان شاخص نامنظم خارجی را به صورت ذیل در نظر گرفت که در آن _i δ مقداری مثبت است:
EI_i(k) = 1 –
که در آن D(k) یک شاخص پراکندگی است. به عنوان مثال ضریب تغییرپذیری در مرحله k ام، که با نماد CV(k) ^[۲۳۹] نشان میدهیم مقادیری از تابع هدف از اعضای جامعه را نشان میدهد موقعی که تابع هدف مقداری مثبت روی فضای جستجوی S است. این بدان معناست که افزایش تابع هدف اعضای جامعه متنوع باشد، اعضای جامعه در این حالت بیشتر تمایل دارند که نابهنجارتر رفتار کنند.

۳-۳-۴-۳)سیاست حرکتی مبتنی بر مکانهای گذشته شخصی هرعضو

سیاست حرکتی سوم که مبتنی بر مکانهای گذشته شخصی هر عضو مبتنی است با نماد MP_i^past(k) ^[۲۴۰]، نشان میدهند. برای هر عضو جامعه میتواند رفتار هنجاری باشدکه درسیاست حرکتی مبتنی بر مکانهای گذشته شخصی هر عضو MP_i^past(k) ، هر عضو فقط بر اساس P-best حرکت خود را پایه ریزی کند. از آنجاییکه اعضای جامعه دارای رفتار ماجراجویانه و نامعقولانه است ،در نتیجه هر عضو جامعه ممکن است هر یک از مکانهای گذشته خود را به طور تصادفی انتخاب کند و کاری به بهترین تجربه شخصی خود از لحاظ مکان یا همان P-best نداشته باشد. در این سیاست حرکتی ،شاخص نامنظم داخلی را که با نماد II_i(k) ^[۲۴۱] نمایش میدهند را میتوانیم مانند سیاست حرکتی قیل در دوسناریو تعریف کنیم شبیه آنچه در قسمت قبل توضیح دادیم. در انتخاب هر یک از سه سیاست حرکتی یاد شده یک موضوع مهم آن است که چگونه یک عضو میتواند یک سیاست حرکتی مبتنی بر مکان کنونی یا مکانهای دیگر اعضا یا از مکانهای گذشته خودش را انتخاب کند. برای مسائل پیوسته چندین ایده جبری درباره این انتخاب وجود دارد با این وجود این انتخاب نیاز به نوع آوری بیشتری دارد وقتیکه با مسائل گسسته برخورد میکنیم. به عنوان یک مثال شبیه سازی شده در مسائل گسسته میتوانیم هر جواب را به عنوان کروموزوم کدگذاری در نظر گرفته وسپس از عملگرهای جهش و ادغام که در الگوریتم ژنتیک بدان اشاره شد به عنوان سیاست های حرکتی استفاده کنیم. این ایده میتواند هم در تبدیل فضای جواب به فضای ژنتیک و هم در مشخص کردن سیاست حرکتی بر اساس عملگرهای ژنتیک، در بعضی از مسائل به ما یاری رساند و حل این نوع مسائل را تسهیل بخشد.

۳-۳-۴-۴)سیاست حرکتی مبتنی بر قانون ترکیبی^[۲۴۲]

بعد از انتخاب سه سیاست حرکتی یاد شده MP^current ، MP^society و MP^past ،هر عضو جامعه نامنظم انسانی میتواند این سیاستها را برای حرکت به سمت یک مکان جدید ترکیب کند که به قانون ترکیب نیازمند معروف است. ساده ترین رویکرد آن است که سیاست حرکتی خود را بر اساس بهترین مکانهای جدید انتخاب کنیم به طوریکه در قانون ترکیبی بر انتخاب بهترینها بر اساس قانون ترکیبی بهترینها^[۲۴۳] تاکید شده باشد. یک رویکرد دیگر میتواند آن باشد که سه سیاست یاد شده را به طور متوالی روی مکان جدید به کار گرفته شود که این رویکرد به قانون ترکیبی متوالی^[۲۴۴] معروف است. انواع دیگری از قوانین ترکیبی را میتوان طبق شرایط هر مسئله تعریف کرد به عنوان مثال وقتی هر جواب از مسئله گسسته را به عنوان یک کروموزوم کدگذاری میکنیم ما میتوانیم عملگر ادغام را برای ترکیب کردن همه مکانهایی که از سیاست های حرکتی مختلف به دست میایند استفاده کنیم. توجه به این مطلب بسیار بااهمیت است که اعضای مختلف جامعه نامنظم انسانی ممکن است از قوانین ترکیبی متفاوتی استفاده کنند.

۳-۳-۵)فلوچارت الگوریتم فراابتکاری ASO

برای آشنایی بهتر با الگوریتم فراابتکاری ASO فلوچارت آن را در ذیل میاوریم.

شکل۳-۱: فلوچارت الگوریتم ASO

۳-۴)مقایسه الگوریتمهای PSO و ASO

بعد از مطالعات بر روی رفتار جمعی پرندگان توسط کندی و ابرهارت الگوریتم فراابتکاری PSO در سال ۱۹۹۵ بوجود آمد]۴۰[. ایده اصلی که در پشت الگوریتم فراابتکاری PSO است آن است که هر پرنده به عنوان یک ذره شناخته میشود که در فضای جواب مسئله بهینه سازی، برای رسیدن به جواب بهینه در حال جستجو است. هر ذره میزان سرعت خود را بر اساس تجربیات شخصی و اطلاعاتی که از طریق تعامل و ارتباط با جمعیت بدست می آورد، مشخص میکند. ساختار الگوریتم PSO در ابتدای پیدایش برای مسائل بهینه سازی پیوسته بدون داشتن محدودیت معرفی شده بود. در یک فضای جستجوی پیوسته هر بعد از بردار مکان پرنده با مقدار یک متغیر تصمیم از مسئله موردنظر در ارتباط است. به عبارت دیگر مکان هر ذره یک جواب بالقوه برای مسئله مورد نظر است و برازندگی این ذره میتواند به وسیله قرار دادن مقادیر مکان هر ذره ، در یک تابع هدف که از قبل مشخص شده محاسبه گردد. وقتی که تابع برازندگی برای مکان یک ذره بیشتر از حد مطلوب باشد مکان این ذره به عنوان مکان بهتر تشخیص داده میشود، حال شمای ریاضی الگوریتم فراابتکاری PSO را به صورت ذیل بیان میکنیم: فرض کنید یک جمعی از ذرات در حال جستجو برای رسیدن به جواب بهینه سراسری در داخل فضای جواب d بعدی هستند. دو بردار d بعدی برای هر ذره i ام در مرحله k ام باید مشخص شود که اولی بردارd بعدی X_i(k) است که مکان ذره i ام را در مرحله k ام نشان میدهد. دومین بردار d بعدی، بردار V_i(k) است که سرعت ذره i ام را در مرحله k ام نشان میدهد. دو بردار d بعدی مهم دیگر در الگوریتم PSO ، بردارهای P_i(k) و G(k) است که به طور مشابه آنچه در قسمت قبل برای الگوریتم ASO تعریف شده اند، در الگوریتم PSO نیز تعریف میشود.
سرعت جدید هر ذره در الگوریتم فراابتکاری PSO به صورت ذیل محاسبه میشود:
V_i (K + 1 ) = ωV_i(k) + ʎ_۱r₁(k) [G(K) – X_i(k)] + ʎ_۲r₂(k) [P_i(k) – X_i(k)]
در فرمول بالا _۱ʎ و _۲ʎ مقادیر ثابت مثبتی هستند که به عنوان ضریب تندی سرعت^[۲۴۵] در نظر گرفته میشوند.
در فرمول بالا ω یک مقدار ثابت مثبت است که فاکتور سکون^[۲۴۶] نامیده میشود.
همچنین در فرمول بالا (k)₁r و (k)₂r مقادیری هستند که توسط یک توزیع احتمال^[۲۴۷] در محدوده مقداری (۱و۰)، به طور تصادفی در مرحله k ام مقداردهی میشوند.
مکان هر ذره در الگوریتم فراابتکاری PSO به وسیله فرمول ذیل بروزرسانی میشود: