پژوهش – 
تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف  …

پژوهش – تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف …

عملکردهای انسانی در طبیعت برآیندی است از تصمیم گیریهائی که بر مبنای میزان علم او به تمامی گزینه های محتمل و نتایج حاصل از انتخاب هریک از آن ها صورت می گیرد. در عمل، فرایند تصمیم گیری معمولا با توجه به چندین تابع هدف مختلف و اغلب غیر هم جهت در ارتباط است. این بدان معناست که فرآیند ارزشگذاری توابع مختلف اساسا نمی تواند یکسان و هم جهت باشد و اصولا برازندگی یک تابع هدف در جهت مطلوب، نمی تواند افزایش یابد بدون آنکه از مقدار مطلوبیت تابع هدف دیگر کاسته شود. لذا به منظور تصمیم گیری نهائی، بهره گیری از نوع مصالحه[۱۰۱] بین اهداف ضروری می باشد. این قبیل مسائل که در بر گیرنده اهداف مختلف در روند انتخاب پاسخ بهینه می باشند با عنوان تصمیم گیری چند معیاره شناخته می شوند.
از آنجا که دستیابی به مقادیر بهینه برای تمامی توابع هدف به طور همزمان غیرممکن ، مسئله تصمیم گیری چند معیاره[۱۰۲] به طور معمول به یک مسئله انتخاب تبدیل خواهد شد. بدین ترتیب، انتخاب نهائی مصالحه ای بین توابع هدف مختلف می باشد و در نهایت، ترجیح تصمیم گیرنده، تک جواب نهائی را مشخص خواهد کرد. در دنیای واقعی، بسیاری از مسائل تصمیم گیری در بر گیرنده تعداد نسبتا زیادی از متغیرهای تصمیم هستند که مقایسه تمامی آنها در عمل غیر ممکن می باشد. لذا با توجه به این نکته، مسائل بهینه سازی به یک مسئله جستجو با رویکرد انتخاب جواب بهینه بر اساس فرآیند حذف جواب های نامعقول تبدیل خواهد شد. حل اینگونه مسائل تحت عنوان بهینه سازی چند هدفه[۱۰۳] تعریف می شود.
الگوریتم های تکاملی چندهدفه[۱۰۴]
الگوریتم های تکاملی با شبیه سازی قوانین تکامل در طبیعت، روند جستجو را به سمت یافتن پاسخ بهینه هدایت می نمایند. در این الگوریتم ها بر خلاف روش بهینه سازی کلاسیک که در هر تکرار، تنها یک پاسخ مورد توجه قرار می گیرد، مجموعه ای از جواب ها یا جمعیت تولید شده و در روند بهینه سازی استفاده می شود. اگر مسئله مورد نظر از نوع تک هدفه باشد، انتظار بر این است که تمام اعضای جمعیت در الگوریتم های تکاملی به یک پاسخ بهینه، همگرا شوند. اما در مسائل چند هدفه جمعیت نهائی می تواند شامل چندین پاسخ بهینه باشد.
اولین کاربرد ثبت شده ی بهینه سازی توابع چند هدفه با استفاده از الگوریتم های تکاملی توسط شافر[۱۰۵] (۱۹۸۵) ارائه شده است. در این تحقیق الگوریتم ژنتیک بردار ارزیابی(VEGA) با اعمال یک مکانیزم اصلاح شده ی انتخاب در الگوریتم ژنتیک تک هدفه، برای مسائل چند هدفه بکار گرفته می شود. در این روش، در هر نسل، J زیر مجموعه تولید می شود که در آن، J تعداد اهداف می باشد. جمعیت jام بر اساس روش استاندارد برای انتخاب و ارزشگذاری هدف jام بدست می آید. سپس این J زیر مجموعه با هم ترکیب شده و یک جمعیت کلی را می سازند. پس از آن عملگرهای جهش و آمیزش بر این مجموعه اعمال می گردند. جواب تولید شده توسط این الگوریتم به عنوان جواب نهائی در نظر گرفته خواهد شد.
گلدبرگ[۱۰۶] (۱۹۸۸) در یک مبحث کوتاه، استفاده از مفهوم چیرگی و رتبه بندی پارتو در الگوریتم های تکاملی چند هدفه را پیشنهاد کرد. برای تعیین چیرگی[۱۰۷]، دو پاسخ با یکدیگر مقایسه می شوند. به عنوان یک قانونکلی، مشرو برارضای دو شرط به صورت همزمان، پاسخ(۱)X بر(۲)X چیره خواهد شد هرگاه: (۱) پاسخ (۱)X در هیچ یک از اهداف مسئله، از نظر برازندگی بدتر از (۲)X نباشد و (۲) پاسخ (۱)X حداقل در یکی از اهداف مسئله، دارای برازندگی بهتر از (۲)X باشد. نحوه ی رتبه بندی پارتو به دو روش در شکل (۴-۲) نمایش داده شده است.

شکل ۴-۲-رهیافت مختلف رتبه بندی پارتو

در شکل(۴-۲-الف)، به اعضای جمعیت حاضر، برازندگی نسبی بر اساس روش Goldberg نسبت داده شده است. مقدار برازندگی ۱، به جواب های غیر مغلوب جمعیت اختصاص داده شده و سپس، این جواب ها از درون جمعیت حذف می شوند. در ادامه، مقدار برازندگی ۲، به جواب های غیرمغلوب باقیمانده در مجموعه حاضر تعلق می گیرد و آن ها نیز از جمعیت کنار می روند. این روند به تمام اعضای جمعیت، مقدار برازندگی مناسبی نسبت داده می شود ادامه می یابد. در شکل (۴-۲-ب)، از روش متفاوتی برای انتساب برازندگی به اعضای جمعیت استفاده می شود. بر این اساس، اگر هیچ جوابی وجود نداشته باشد که بر پاسخ مورد نظر چیره شود، مقدار برازندگی ۱ برای آن پاسخ در نظر گرفته می شود. به همین صورت، اگر یک جواب بر آن چیره شود مقدار ۲ و در صورتی که دو جواب غالب وجود داشته باشد، مقدار برازندگی ۳ به پاسخ مورد نظر نسبت داده می شود. این فرآیند نیز تا جائی که تمامی جواب ها دارای برازندگی شوند ادامه می یابد.
بر پایه این تفکر، کاربردهای متنوعی از MOEA ها توسط شماری از محققین در سرتاسر دنیا توسعه داده شده است که از آن جمله می توان به الگوریتم ژنتیک مبتنی بر مرتب سازی غیرمغلوب (NSGA)[108] توسط اسرینیواس و همکاران[۱۰۹] (۱۹۹۴)و الگوریتم ژنتیک چند هدفه (MOGA)[110] توسط فلمینگ[۱۱۱] (۱۹۹۵) اشاره کرد. در الگوریتم NSGA از رتبه بندی پارتو به روش Goldberg و در MOGA از روش شمارش تعداد اعضای غالب استفاده شده است.
در دهه های اخیر الگوریتم های متعددی در این زمینه ارائه شده اند. جدول (۲-۲) برخی از مهمترین ویژگیهای مربوط به شناخته شده ترین الگوریتم های تکاملی چند هدفه را با یکدیگر مقایسه می کند. در بسیاری از این الگوریتم ها، رتبه بندی بر اساس مفهوم چیرگی به نوعی مورد استفاده قرار گرفته است. در عین حال، در مواردی به منظور حفظ پراکندگی در فضای هدف، نخبه گرائی و یا فرم های دیگری از نسبت دادن برازندگی بر مبنای فضا و موقعیت جواب نیز مورد استفاده قرار گرفته است.
جدول ۳-۲- مقایسه ویژگیهای برخی از مشهورترین الگوریتم های چند هدفه (۲۰۰۶Konak,)

الگوریتم تعیین برازندگی مکانیزم پراکندگی نخبه گرائی جمعیت خارجی مزایا معایب
VEGA ارزیابی هر زیر جمعیت بر پایه اهداف متفاوت خیر خیر خیر پیاده سازی اولیه MOGA تمایل همگرائی به کرانه های هر هدف
MOGA رتبه بندی پارتو تقسیم برازندگی با niche خیر خیر بسط ساده الگوریتم ژنتیک تم هدفه همگرائی کند مطابق با پارامتر niche
NPGA فاقد تعیین برازندگی، انتخاب به روش مسابقه ای محاسبه بر اساس niche در روش انتخاب مسابقه ای خیر
دانلود متن کامل این پایان نامه در سایت abisho.ir
برچسب گذاری شده با: , , , , , ,