پایان نامه بهینه‌ سازی زمان و هزینه به روش الگوریتم ژنتیک برای پروژه‌های عمرانی

پایان نامه برای دریافت درجه کارشناسی ارشد(M.A)

گرایش: ”استراتژیک"

مقدمه

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

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

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

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

به منظور بهینه سازی زمان – هزینه، روش های مختلفی در دو حوزه آنالیز موازنه زمان – هزینه به کار گرفته می شوند. به همین منظور روش های ریاضی و تحقیقی (کاوشی) متنوعی به کار می روند.

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

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

برای اولین بار Feng‌ و Lui (1997) در حل مساله موازنه زمان – هزینه، Hegazy (1999) در حل مساله تخصیص و تسطیح منابع از روش الگوریتم ژنتیک استفاده نمودند. آنها در مدلسازی خود بهینه سازی تک هدفه را دنبال کردند و تنها با روش وزن دهی به پارامترهای زمان و هزینه، ترجیحات تصمیم گیرنده را در انتخاب گزینه در نظر گرفتند.

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

فصل

2-1- مقدمه:

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

2-2- اصول تصمیم‌گیری چندهدفه

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

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

یک تقسیم بندی معمول برای حل اینگونه مسائل روشی است که در سال 1969 و بر اساس منظور نمودن نحوه اعمال اولویت های تصمیم گیرنده ارائه شده است. بر اساس این تقسیم بندی، چهار راهکار برای معرفی جواب نهایی در مسائل بهینه سازی چند هدفه وجود دارد:

1- عدم لحاظ کردن هر نوع برتری (صرفاً عمل جستجو انجام می‌گیرد)

2-لحاظ نمودن برتری (ارجحیت) تصمیم گیرنده قبل از فرآیند جستجو (تعیین ارجحیت قبل از جستجو)

3-منظور نمودن اطلاعات مربوط به برتری (ارجحیت) تصمیم گیرنده به شکل پویا (تعیین ارجحیت همزمان با جستجو)

4-منظور نمودن اطلاعات برتری (ارجحیت) تصمیم گیرنده بعد از اتمام فرایند جستجو

راهکار اول:

 شامل روشهایی است که طی آن جستجو بدون درنظرگرفتن هرگونه اولویتی از جانب تصمیم گیرنده انجام می­شود.

راهکار دوم:

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

2-3- سابقه مطالعات صورت گرفته در زمینه الگوریتم­های تکاملی چندهدفه

Goldberg، پیشنهاد داد که می توان بهینه سازی چند هدفه را با استفاده از فرایند رتبه بندی پارتو مورد بررسی قرار داد. بدین معنا که با توجه به چیرگی اعضای پارتو، به هر عضو از جمعیت یک مقدار نسبی برازندگی نسبت دهیم. این فرایند که با نام مرتب سازی غیرپست[2] شناخته می­شود، سنگ بنای تمامی الگوریتمهای بهینه سازی تکاملی چند هدفه قرار گرفته است (شکل (1-2)).

خود Goldberg نظریه خود را به مرحله اجرا درنیاورد، اما مدت اندکی بعد، الگوریتم [3]NSGA بر پایه این تفکر معرفی و به طور قابل‌ملاحظه‌ای مورد پذیرش جامعه علمی قرار گرفت.

شکل (1-2): رهیافتهای مختلف  رتبه بندی پارتو

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

2-3-1- الگوریتمهای تعاملی چند هدفه (Multi-Objective Evolutionary Algorithms)

پس از ارائه پیشنهاد بسیار کارآمد Goldberg، در دهه اخیر تعدادی از الگوریتمهای تکاملی چند هدفه (MOEAs)‌ پیشنهاد شده­اند که در زیر نام تعدادی از آنها آورده شده است.

 1-بردار ارزیابی الگوریتم ژنتیک (VEGA)

2-الگوریتم ژنتیک چند هدفه (MOGA)

3-الگوریتم ژنتیک جبهه پارتو نیچه (NPGA)

4-الگوریتم ژنتیک برپایه وزن دهی (WBGA)

5-الگوریتم ژنتیک برپایه مرتب سازی غیرپست (NSGA)

6-الگوریتم تکاملی با استفاده از پارتو SPEA))

7-الگوریتم پیشرفته (SPEA-II) SPEA

8-استراتژی تکاملی پارتو (PAES)

9-الگوریتم انتخابی برپایه پارتو (PESA)

10-الگوریتم تکاملی چندهدفه پویا (DMOEA)

بعضی از ویژگی­های این الگوریتمها در جدول (2-1) آمده است.

در الگوریتم­های بهینه سازی چند هدفه، فضا یا موقعیت معمولا توسط فاصله اعضاء از هم و در فضای هدف تعریف می شود. تقسیم برازندگی یا دیگر روشهای مشابه به منظور حفظ پراکندگی جوابها در فضای هدف مورد استفاده قرار می گیرند. شکل (2-2) برخی از این روشها را نمایش می­دهد.

در شکلهای شماتیک فوق،‌راه حل های غیرپست توسط نقاط توپر و راه حلهای مغلوب توسط نقاط توخالی نمایش داده شده­اند.

در شکل (2-2) در قسمت (a) به اشتراک گذاردن برازندگی نمایش داده شده که در این روش همانند آنچه که در NSGA و MOGA مورد استفاده قرار گرفته است، از مقدار برازندگی عضوی که در فضای عضو دیگر قرار می‌گیرد کاسته می شود.

[1] Multi Criteria Decision Making

[2]. Non-dominated sorting

[3]. Non-dominated sorting Genetic Algorithm

شکل (2-2): فرمهای مختلف محاسبه فضا و موقعیت را در الگوریتم­های MOEA جهت ایجاد پراکندگی

قسمت (b)‌ نشان می دهد که رتبه بندی شلوغی همانند آنچه که در الگوریتم NSGA-II مورد استفاده قرار گرفته است. فاصله نزدیک ترین راه حل غیرپست را تا جواب موردنظر محاسبه می نماید. در قسمت (c) موقعیت خطوط مشخصه نشان داده شده است. همانند آنچه که در الگوریتمهای PAES، PESA‌ و PESA_II مورد استفاده قرار گرفته است. هرچه تعداد راه حلهای داخل یک خانه مشخص بیشتر باشد، امکان انتخاب شدن کمتری در انتظار اعضای آن خانه می­باشد.

قسمت (d) چیرگی‌است در این روش، آن راه حلی که دقیقا بر راه حل­های اطراف خود غلبه می کند توسط پارامتر ε نمایش داده می­شود. با این تفاسیر قرار گرفتن جوابهای بسیار نزدیک به مجموعه غیرپست در میان مجموعه جواب نهایی عملا غیرممکن می گردد.

تاکنون بیشترین بررسی­ها بر روی الگوریتمهای NSGA، MOGA و NPGA صورت گرفته است و مقبولیت زیادی در میان الگوریتم­های بهینه سازی تکاملی چندهدفه دارا می باشند. امروزه نیز بسیاری از الگوریتمهای MOEA به نوعی مفهوم رتبه بندی چیرگی را مورد استفاده قرار می دهند و در عین حال، گاهاً برای حفظ پراکندگی بر روی فضای هدف، نخبه گرایی و یا فرمهای دیگری از نسبت دادن برازندگی براساس فضا و موقعیت جواب نیز مورد استفاده قرار می گیرند.

2-3-2- الگوریتمهای بهینه سازی نخبه گرا براساس رتبه بندی پارتو

عبارت نخبه گرائی در ادبیات الگوریتم­های تکاملی به معنای نگهداری و حفظ والدین خوب و انتقال آنها از نسلی به نسل دیگر جهت شرکت دادن آنها در فرآیند انتخاب و ترکیب می باشد. سابقه اولین استفاده از مفهوم نخبه گرائی حدودا به همان سالهای اولیه توسعه الگوریتم­های MOGA، NSGA و NPGA برمی­گردد و به طور مشخص و مفصل در حدود  سال های 94-1993 مورد بررسی قرار گرفت.