خلاصه :
این مقاله یک الگوریتم ژنتیکی سازگار (AGA) را همراه با تابع لیاقت دینامیکی، برای مسائل چند هدفه (MOPs) در محیط دینامیکی تشریح می کند.
به منظور دیدن اجرای الگوریتم، این روش برای دو نوع از مسائل MOPs بکار گرفته شده است.
اولا این روش برای پیدا کردن آرایش نیروهای نظامی برای شبیه سازی رزمی بکار گرفته شده است.
این مقاله در مورد چهار تابع هدف بحث می کند که باید بهینه شوند و یک واسطه فازی را ارئه می دهد که طرح جامعی را از چهار تابع هدف می سازد.
دومین واسطه فازی برای کنترل نرخ عملکردهای تقاطع (Crossover) و جهش (Mutation) بکار گرفته می شود که بر اساس خواص آماری لیاقت (Fitness) جامع می باشد.
علاوه بر مسئله آرایش نیروهای نظامی یک مثال ساده از بهینه سازی چند هدفه که توسط فرینا و همکارانش گشته نیز ارائه شده است و توسط این الگوریتم پیشنهادی حل شده است.
نتایج بدست آمده در اینجا نشان می دهد که الگوریتم ژنتیکی افزایش یافته، نسبت به الگوریتم ژنتیکی معمولی، عملکرد بهتری در مورد همگرائی دارد.
کلمات کلیدی:
الگوریتم ژنتیکی سازگار یافته ، منطق فازی ، آرایش نیروهای نظامی ، شبیه سازی رزمی و بهینه سازی چند هدفه .
1- مقدمه
بدیهی است که حالتهای متعددی برای مسائل عملی بهینه سازی وجود دارد که در ابتدا، بهینه سازی چندین اندازه گیری اجرا (MOP) یا محک ، غیر قابل اجتناب است و این اندازه گیری ها ممکن است که با هم تداخل هم داشته باشند.
مسائل مربوط به MOPsمی توانند استاتیکی یا دینامیکی باشند.
مهمترین موضوع در حل این گونه از مسائل عبارت از مشخص کردن توابع هدف طراحی، برای اینکه خوبی (Goodness) یک حل مشخص بر آورد شود.
در مسائل MOPs بجای یک حل بهینه ، یک مجموعه از حل های بهینه ( مجموعه بهینه پارتو )، بسته به وجود چند تابع هدف، رخ می دهد.
بدون تنزل یکی از جوابها ، هیچ بهبودی برای هر یک از حلهای بهینه پارتو وجود ندارد.
هیچ حل پارتو نمی تواند از حل دیگری بهتر باشد مگر اطلاعات بیشتری را در اختیار داشته باشیم .
برای اینکه انتخاب نهایی بهتری داشته باشیم ، بهترین راه این است که تا جایی که ممکن است حلهای مختلف بهینه پارتو را بدست آوریم.
در بعضی از کاربردهای جهانی نظیر حمل ونقل باربا روباتها ، مشخص کردن مدل و طراحی کنترل کننده ها ، مسائل محیطی و نیازهای MOPs بصورت دینامیکی تغییر می کنند و برای اینگونه کاربردها ، بهینه سازی چند هدفه وابسته به زمان، نیاز است .
در این گونه از مسائل ، توابع هدف مربوطه و قیود و پارامترهای مسئله یا همه اینها، ممکن است لحظه به لحظه تغییر کنند.
این گونه از مسائل MOPs دینامیکی نامیده می شوند.
در این حالتها ، بهینه سازی تابع باید در بازه های زمانی خیلی محدود شده انجام پذیرد.
الگوریتمهای ژنتیکی معمولا بهترین وسیله جستجو در فضاهای بزرگ در طی یک زمان قابل قبول می باشند و نیازی به تحدب، تقعر و یا پیوستگی توابع بهینه ندارند.
این موضوع منجر به دامنه وسیعی از کاربردها برای این الگوریتم در مسائل بهینه سازی بزرگ درگستره های مختلف می گردد مانند تحلیل سریع تاکتیکهای جنگی برای دفاع و حلهای انعطاف پذیر برای مدیریت زنجیره ای.
این انواع مسائل پیچیده معمولا شامل آشوبناکی ، اتفاقی و مسائل دینامیکی پیچیده غیر خطی می شوند.
غیر ممکن است که این طیف از مسائل را بتوان با روش قدیمی الگوریتم ژنتیکی حل نمود.
الگوریتمهای ژنتیکی، تحلیل مجموعه ها را بصورت موازی انجام می دهند و تشابه این حلها را توسط ترکیب آنها برجسته می کنند.
این موضوع باید تذکر داده شود که از آن جا که این گونه الگوریتمها تعداد زیادی از حلها را در مجموعه های بهینه پارتو پیدا می کنند، برای حل مسائل چند هدفه بسیار خوب می باشند .
به هر حال، در الگوریتم ژنتیکی ساده، پارامترهای ثابت، مستقیما اجرای الگوریتم را تحت تاثیر قرار می دهند.
معمولا پارامترهای بدون آهنگ منجر به مسائل متعددی نظیر همگرایی زودرس می شوند.
بنابراین تعدادی از تکنیک های سازگار یافته برای این گونه از پارامترها پیشنهاد شده است.
همانند جهش احتمالاتی ، تقاطع احتمالاتی ، اندازه جمعیت [1] و ]2[ و عملکرد تقاطع ]3[.
یکی از مهمترین راهبردها برای مسائل بهینه سازی چند هدفه ، الگوریتم ژنتیکی چند هدفه (MOGA) می باشد.
مطالعات زیادی در مورد MOGA در منابع موجود می باشد [5]، [6]، [7]، [9]، [10]، [11]، [12]، [13]، [14]، [15]، [16]، [17]، [18]، [19]، [20].
مخصوصا دب (Deb) [20] یک MOGA عالی را ارائه داده است .
یک الگوریتم ژنتیکی با بر آورد برداری (VEGA) [9] نسبت به یک الگوریتم ژنتیکی ساده متفاوت می باشد چون در این روش جدید، از یک عملگرا انتخاب اصلاح شده استفاده می شود و در هر نسل، تعدادی از زیر جمعیتها توسط اجرای انتخاب خطی تولید می شوند.
مهمترین نقص این روش آن است که قادر به تولید حلهای بهینه پارتو برای فضاهای جستجویی غیر محدب نمی باشد.
در تکنیک مرتبه لغت نویسی (lexicographic ordering ) [14]، حلهای طراح مرتبه ها، بر اساس خواص مهم توابع می باشد.
سپس حل بهینه توسط مینیم سازی توابع هدف بدست می آید که بر اساس مهم بودن آنها، از مهمترین آنها شروع می شود.
مهمترین ضعف این روش این است که ممکن است منجر به بدست آوردن توابع هدف جانبدارانه شود و این موضوع ممکن است باعث بدست آمدن یک سری از توابع هدفی گردد که باعث ازدیاد توابع هدف و اتفاقی بودن آنها ، هنگام انجام فرایند بهینه سازی شود.
الگوریتم ژنتیکی هاجِلا و لین (HLGA) از روش مجموع وزن دار برای انتصابها استفاده می کند.
ضرایب وزنی در هر تابع هدف، درکروموزمها نهفته می باشد.
واگرایی ترکیب وزنها توسط روش Phenotypic fitness sharing ارتقا داده می شود و الگوریتم ژنتیکی بصورت همزمان، حلها و ترکیب وزنی ها را تکامل می بخشد.
این روش دارای مزیتهای بخصوصی است : این روش دارای کارایی کامپیوتری خوبی است، و حلهای غیر غالب ( غیر مشرف) را بصورت قوی تولید می کند.
هر چند برای مشخص کردن وزنهای مناسب در این روش به راحتی نمی توان از بهینه سازی جعبه سیاه (black – box) استفاده نمود که هیچ دانسته ای را در مورد دامنه نیاز ندارند.
الگوریتم ژنتیکی مرتب کردن غیر مشرف (NSGA)، [11] بر اساس کلاس بندی لایه ها برای افراد می باشد.
قبل از اینکه مکانیزم انتخاب اجرا شود ، جمعیت بر اساس غیر مشرف بودن مرتب می شود بدین صورت که همه افراد در یک گروه دسته بندی می شوند.
( با یک تعداد لیاقت فرضی که متناسب با اندازه جمعیت است ).
برای باقی ماندن واگرایی جمعیت، این کلاس افراد با مقدار لیاقت فرضی آنها شریک می شود .
سپس این گروه از افراد کلاس بندی شده در نظر گرفته نمی شوند
مخصوصا دب (Deb) [20] یک MOGA عالی را ارائه داده است .
سپس این گروه از افراد کلاس بندی شده در نظر گرفته نمی شوند و لایه بعدیِ افراد غیر مشرف فرض می شود.
این فرایند ادامه می یابد تا تمام افراد داخل جمعیت، کلاس بندی شوند.
زیتزِلر و تیل، روش Strength Pareto (SPEA) [16] را گسترش دادند.
در این الگوریتم، چندین خاصیت مطلوبِ توابع چند هدفه EA اولیه ترکیب می شوند که این خواص نظیر ارتقاء پیوسته جمعیت، نگهداری واگراییِ جمعیت و بر آورد لیاقت افراد می باشند.
روشهای SPEA ، PAES [18] و NSGAII [19] بر اساس حلهای پارتو می باشند که در آنها اندازه گیری لیاقت افراد بر اساس خواص مشرفی آنها می باشد.
افراد غیر مشرف در داخل جمعیت، بعنوان لایق ترین افراد در نظر گرفته می شوند و افراد مشرف بعنوان کمترین مقدار لیاقت فرض می شوند .
روش PAES یکی از روشهای MOGA است که از استراتژی یک والد و یک فرزند استفاده می کند.
در روش NSGA، در هرتکثیر نسل، اپراتورهای تقاطع و جهش برای تولید فرزندی استفاده می شوند که تا حد ممکن در داخل نسل والدها باشد.
بهینه سازی چند هدفه بصورت گسترده ای در مراجع مختلف مورد مطالعه قرار گرفته است.
اما مطالعات مربوط بهینه سازی چند هدفه دینامیکی (DMO) خیلی کم می باشد و در مراجع [21] و [22] به آن پرداخته شده است : در مرجع [21] پنج مسئله بهینه سازی دینامیکی چند هدفه با پیچیدگیهای مختلف ( از قبیل محدب بودن ، پیوسته نبودن و وابسته بودن به زمان ) ارائه شده است و یک روش پایه ای جستجوی مستقیم در آن مرجع برای هر پنج نوع مسئله بکار گرفته شده است .
فرینا و همکارانش در مرجع [21] بیان نموده اند که الگوریتمهای بهینه سازی دینامیکی چند هدفه تکاملیِ کارایی برای اجرای خوب، مورد نیاز است و مطالعات شبیه سازیهای سخت گیرانه ای نیز لازم است.
معرفی ها یک بهینه سازی چند هدفه با قیود نامساوی می تواند به زبان ریاضی توسط یک تابع برداری f معرفی شود که یک مجموعه از m پارامتر ( متغیر های تصمیم گیری ) را به n تابع هدف می نگارد .
این موضوع می تواند مانند زیر بیان شود.
که x عبارت است از مجموعه بردارهای تصمیم گیری و X عبارت است از فضای پارامترها و y نیز بردار هدف می باشد و Y فضای تابع هدف است.
حقیقت مورد ملاحظه در مورد این گونه حلها این است که هنگامی که تمام توابع هدف در نظر گرفته شوند، هیچ کدام از حلها در فضای جستجو نسبت به بقیه برتری ندارد.
مجموعه حلهای یک مسئله بهینه سازی چند هدفه تشکیل شده است از همه پارامترهای تصمیم گیری بنحوی که بردارهای هدف آنها نتوانند بدون تنزلِ بقیه، بهبود یابند.
یک چنین حلهایی، حلهای بهینه پارِتو نامیده می شوند.
یک حل بهینه پارتو یکتا نیست اما عضوی از مجموعه نقطه هایی می باشد که هر کدام به تنهایی و با درنظرگرفتن بردارهدف، خوب می باشد.
2-1- نسبت دهی لیاقت و ماندگاری واگرایی نسبت دهی لیاقت و استراتژی ماندگاری واگرایی، دو موضوع مهم در MOPs می باشند.
برای نسبت دهی لیاقت، تعداد زیادی MOGA می توانند در دو گروه رده بندی کرد که عبارتند از حلهای پارتو و حلهای غیر پارتو.
روشهای غیر پارتو [9]، [10]، [13] مستقیما از مقادیر تابع هدف برای تصمیم گیری برای باقی ماندن یا حذف شدن افراد استفاده می کنند.
در حالی که روشهای پارتو [6]، [11]، [16]، [18]، [19] لیاقت یک فرد را در رابطه با خواص مشرف بودن آن اندازه گیری می کنند.
افراد غیر مشرف در جمعیت، بعنوان افراد با لیاقت بالاترین در نظر گرفته می شوند و افراد مشرف بعنوان افراد با لیاقت کمترین فرض می شوند.
یکی دیگر از مشخصه های MOGAs ها عبارت است ازاستراتژی ماندگاری واگرایی.
این موضوع باعث می شودکه حلها بصورت خیلی یکنواخت در تمام مجموعه بهینه پارتو پخش شوند بجای اینکه در یک ناحیه کوچک مجتمع شوند.
به اشتراک گذاشتن، لیاقت افرادی که کاندیدای یک لیاقت باشند را کم می کند و یکی از تکنیکهای خیلی جدید می باشد .
اخیرا بعضی از تکنیکهای مستقل از پارامتر نظیر SPEA و NSGA نیز پیشنهاد شده اند.
در این مطالعه، یک تکنیک مبتنی بر منطق فازی برای انجام بهتر نسبت دهی لیاقت و ماندگاری واگرایی بکار گرفته شده است.
روشهای قدیمی نظیر روش مجموع وزنها یا روش قیدهای [4] در هر بار اجراء فقط می توانند یک حل بهینه پارتو را پیدا کنند.
همچنین این روشها وابسته به مسئله مورد حل می باشند و ممکن است ساده سازیهای بسیار زیادی را انجام دهند.
در اکثر برنامه های بازیها، لیاقت استاتیکی زیر برای پیدا کردن جهت جستجو بکار برده می شود.
که fi ها feature ها هستند و wi ها وزنهای مربوطه می باشند که میزان مهم بودن feature ها را نشان می دهند.
مشخص کردن این feature ها و وزنها برای یک جستجوی کار آمد در یک مسئله بهینه سازی چند هدفه بسیار مهم می باشند.
انتخاب وزنها در یک فضای دینامیکی چند معیاری سخت می باشد و انتصاب مقادیر وزنها اغلب بصورت سعی و خطا انجام می گیرد .
این فرایند بسیار زمانبر می باشد.
به منظور غالب آمدن بر مشکل بالا ، یک تابع لیاقت با پایه منطق فازی مورد استفاده قرار می گیرد.
بهینه سازی به روش فازی بجای اینکه بر یک مدل ریاضی بنا شود بر یک مدل فازی بنا می شود.
مهمترین مزیت های این روش بهینه سازی این است که توابع هدف فازی، ماهیت غیر قابل دیفرانسیل گیری دارند و نظریه مجموعه های فازی یک روش بسیار جذاب را برای جداسازی اطلاعات از داده های نا مشخص دینامیکی و غیر مدل شده بدست می دهد.
تابع لیاقت دینامیکی زیر برای بدست آوردن وزنهای هدف در منطق فازی بکار می رود.
که ها تابع عضویت هستند که از مشخصه های fi (feature)می باشند.
3-1- توضیح صورت مسئله نرم افزار THUNDER یک نرم افزار خیلی بزرگ شبیه سازی مدل است که بر اساس شبیه سازی مونت کارلو کار می کند.
این نرم افزار یک نرم افزار شبیه سازی تئوری اتفاقی دو طرفه از کارهای نظامی می باشد که توسط System Simulation Solution Inc(531) برای مطالعات مربوط به نیروی هوائی و آژانسهای تحلیل (AFSAA) نوشته شده است.
این نرم افزار می تواند تقریبا 25 ماموریت هوایی را که شامل ماموریت های هوا به زمین ، هوا به هوا، دفاع هوایی، جاسوسی، موشکهای بالستیک ضد تاکتیکی و سوخت گیری هوایی می باشد را انجام دهد.
این نرم افزار به صورت خود کار، پیشروی ها و حرکتهای نظامی را توضیح می دهد و بر اساس یک پایه قانونمند اجرای نقش می کند.
این نرم افزار، یک پشتیبان کار آمد برای تحلیلهای است که شامل اثرهای انتگرالی بر روی حوزه فضا و زمان می باشند.
این موضوع شامل توزیع خود کار تهدیدها و هدفها، تعداد هدفهای کشته شده، پیشروی زمینی و آرایش ارتشی است.
این شبیه سازی، همچنین قیودی را بر مسائلی نظیر نرخ پروازهای هوایی کوتاه و مکان ماموریتها اعمال می کند.
مهمترین هدف این تحقیق این بود که چگونه نیروهای نظامی آرایش داده شوند که این کار توسط الگوریتم ژنتیکی سازگار و با وزنهای ارتقاء یافته انجام گرفت.
دلیل اینکه چرا الگوریتم ژنتیکی برای تعیین آرایش نظامی نیروها و شبیه سازی جنگ بکار گرفته شده این بود که اینگونه الگوریتمها یک فرایند جستجوی پایدار را برای انواع مختلفی از توابع که دارای غیر پیوستگی، چند مودی، تعداد بعد زیاد، فضا جستجو بزرگ و نویز، در اختیار قرار می دهند.
شبیه سازی با در نظر گرفتن نویزهای داخلی شناخته نشده و عدم پیوستگی انجام می شود.
الگوریتم ژنتیکی سازگار یافته که شامل قابلیت تغییر دادنِ به هنگام وزنها را داشته باشد برای انجام استراتژی های مختلف در حالتهای گوناگون جنگ مورد نیاز است چون تاکنیکهای جنگی و مکان میدان جنگ به رفتار دشمن نیز بستگی دارد و باید بتواند به مرور زمان تغییر کند.
بهینه سازی چند هدفه 2-1- توضیح در مورد فرمولبندی مسئله موقعیت های جنگی که بر اساس قابلیتهای نیروهای تهدید کننده، شرایط جنگ و قابلیت نیروهای خودی مشخص می شوند تماما می توانند توسط نرم افزار THUNDER شبیه سازی شوند.
فایل مشخصات جنگی معمولا توسط کاربر داده می شود.
این موقعیت های جنگی مستقیما توسط عقیده و نظر یک تحلیل گر مشخص می شود و وظیفه بسیار وقتگیری نیز می باشد.
این موضوع همیشه باعث تولید نتایج مستحکمی نمی شود چون خبرگی نرم افزار نمی تواند مسائل دینامیکی و اتفاقی ناشناخته را در شبیه سازی درک کند.
این موضوع باعث این می شود که رابطه های بین ورودیها و خروجیهای THUNDER به خوبی درک نشود.
هر موقعیت جنگی نیاز به خصوصیات خود را دارد.
بعنوان یک مثال در این مطالعه ، فقط 4 موقعیت جنگی و 15 روز جنگ بعنوان ورودی استفاده شده است.
موقعیتهای در نظر گرفته شده عبارتند از بی اثر کردن حمله متخاصم هوایی استراتژیک (OCA) محجور کردن هدف استراتژیک (STI) محجور کردن وسیع هوایی (DSEAD).
موقعیتهای (OCA) و (STI) و (INI)، موقعیتهای هوا به زمین می باشند.
OCA در مقابل Airbase و موقعیت INI در مقابل واحد های متحرک بر روی شبکه و در پادگان، آسان کردk عملیات لوجسیتکی، شبکه هایِ ترابری، نقاط مورد بازرسی و دفاع هوایی پیچیده می باشد.
موقعیت STI در مقابل هدفهای استراتژیک می باشد.
موقعیت DSEAD یک موقعیت باز دارنده برای ارتش دفاع هوایی است و در مقابل سایتهای هوایی انجام می گیرد.
نرم افزار THUNDER می توان با دید یک بازی دو نفره دیده شود که رنگ آبی نشان دهنده طرف خودی و رنگ قرمز نشان دهنده طرف دشمن است .
با توجه به این توضیحات توابع هدف ما چنین خواهند بود.
مینمم کردن زمینهایی که طرف آبی از دست می دهد مینمم کردن از بین رفتن هواپیماهای طرف آبی ماکزیمم کردن تعداد کشته های هدفهای استراتژیک طرف قرمز ماکزیمم کردن تعداد کشته های طرف قرمز موارد گفته شده یک حالت عمومی برای مسائل بهینه سازی چند هدفه می باشند زیرا منظورمان بهینه کردن چهار تابع هدف بالا بصورت همزمان می باشد.
خروجیهای نرم افزار THUNDER (زمینهای از دست رفته هواپیماهای از دست رفته تعداد کشته های هدف استراتژیک و تعداد کشته های طرف دشمن) با یک امتیاز مینیمم و یک امتیاز ماکزیمم، مقدار دهی می شوند.
این مقادیر ماکزیمم و مینیمم می تواند 2 و 1 باشد.
مقادیر بین این دو عدد می توانند با میان یابی بین بهترین حالت و بدترین حالت مشخص شوند که نیازمند اطلاعات مجربی می باشد.
2-2- الگوریتم ژنتیکی قرار دادی ما تابع لیاقت وزنی استاتیک در ابتدا، این مسئله بهینه سازی چند هدفه به یک شکل مفید برای استفاده مستقیم از الگوریتم ژنتیکی تبدیل می شود که بتواند از تابع لیاقت استاتیکی استفاده کند.
تابع لیاقت پایه مربعی مورد استفاده قرار گرفت چون در مقایسه با دیگر توابع لیاقت فرض شده، نتایج بهتری را بدست می دهد.
که F عبارت است از نمره لیاقت نهایی ،f1 نمره فردی از دست دادن زمین ، f2 نمره فردی برای کشته های استراتژیک طرف قرمز ،f3 نمره فردی به کشته های (افراد درجه دار ) طرف قرمز و f4 نمره فردی مربوط به هواپیماهای از دست رفته طرف آبی است.
ورودیهای f1 و f2 برای تابع لیاقت از لحاظ وزنی متفاوت بودند تا خواص متفاوتی را به تابع هدف بدهند.
به منظور مطالعه اثرات نمرات بر روی تابع لیاقت، چهار تابع مختلف لیاقت مورد استفاده قرار گرفت.
توابع هدف one- low-ptioring ,one-high-prioring بصورت زیر مورد استفاده قرار گرفت.
این توابع لیاقت توسط پارامترهای مربوط به الگوریتم ژنتیکی زیر مورد آزمایش قرار گرفت: .N=50( اندازه جمعیت ) PC= 7/0 ( اندازه احتمالاتی تقاطع ) PM 02/0 ( اندازه احتمالاتی جهش ) مقدار لیاقت برای چهار تابع لیاقت در شکل 1 نشان داده شده است .
در سه حالت F1 و F2 و F3 مقدار لیاقت بعد از 20 نسل به مقدار ماکزیمم می رسد اما در حالت F3 رسیدن به ماکزیمم بعد از 40 نسل رخ می دهد.
Fig.
1.
Four different weighted fitness functions.
همانگونه که می توان از شکل 1 ملاحظه نمود همه توابع لیاقت، مشخصه های مختلفی را از خود نشان می دهند.
تعدادی از آنها به سرعت به مقدار ماکزیمم همگرا می شوند اما این مقدار ماکزیمم خیلی بالا نیست .
F2 خیلی زود همگرا می شود اما مقداری که به آن همگرا شده است چندان مطلوب به نظر نمی رسد.
همچنین توابع هدفtwo- high- priority و two- low-priority نیز بهینه شده اند برای اینکه اثر این توابع هدف بر روی مقدار لیاقت دیده شود.
این توابع بصورت زیر می باشند.
مقادیر لیاقت برای توابع لیاقت بالا در شکل شماره 2 نشان داده شده است.
از روی شکل دیده می شود که مقادیر لیاقت خیلی به وزنها و نمره های فردی وابسته است که به مرور زمان تغییر می کند.
در تمام حالتهای بالا یک الگوریتم ژنتیکی با تابع لیاقت وزنی استاتیک نمی تواند مقادیر لیاقت ماکزیمم پایداری را تولید کند چون هر نمره فردی تابعی از زمان است .
بنابراین یک الگوریتم ژنتیکی با تابع وزنی متغییر برای بهینه سازی بهتر مورد نیاز است.
2.
Two different weighted fitness functions.
3-2- الگوریتم ژنتیکی سازگاری یافته با تابع لیاقت وزنی قانونمند برای بررسی اینکه الگوریتم ژنتیکی سازگاری یافته چگونه می تواند مسئله مورد نظر ما را انجام دهد روشی با تابع لیاقت وزنی فازی که مطابق زیر آمده است بکار گرفته شده است که این مقادیر، سیستم پیشرو بهینه پارتو می باشد.
مسئله مورد نظر توسط فرینا و همکارانش در [21] در نظر گرفته شده است.در اینجا r شمارنده تعداد نسلها می باشد، Tt تعداد نسلها می باشد برای حالتی که t ثابت بماند، و nt تعداد مراحل مختلف در t می باشد.
مقادیر پارامتری n=20 ،Tt=5 و nt=10 در [21] پیشنهاد شده اند.
شکل 3 نشان می دهد که چگونه دو متغیر اولی حل در یک زمان مشخص تغییر می کند .
مقادیر مربوطه تابع هدف در شکل 4 نمایش داده شده است.
3.
Variations on the first two decision variables for a particular time.
4.
The corresponding objectives on the first two decision variables for a particular time.
در حالت کلی فقط بهبود توابع هدف با درجه اهمیت بالا مورد نظر است مانند قیود سخت، تا اهداف مربوطه طراحی حاصل شود.
بعد از این موضوع، ممکن است که به توابع هدف با درجه اهمیت کمتر نیز پرداخته شود.
بهر حال، در حالت مورد نظر ما تمام توابع هدف باید بصورت دینامیکی به بهینه برسند.
این موضوع شناخته شده است که در مراحل مختلف جنگی، تاکنیکهای مختلفی مورد نیاز است.
این تاکنیکها فقط می توانند بصورت مکالمه ای شرح داده شوند.
بنابراین یک تابع لیاقت قانونمند بر اساس توابع هدف بالا برای محاسبه مقدار لیاقت نهایی مورد استفاده قرار گرفت.
نمرات فردی مربوط به هر تابع هدف مجذور شده اند و ضرایب وزندار به آنها اضافه شده است.
مقدار لیاقت نهایی بصورت مجموع جملات نشان داده می شود.
که مقادیر در شکل 5 نشان داده شده است.
5.
Fuzzy membership for rule-based weights of objectives.
شهودی ترین استراتژی حل مسئله هنگام برخورد با بهینه سازی چند هدفه عبارت است از استفاده از تابع لیاقت قابل به روز شدن.
در ساده ترین حالت، استفاده از روش منطق فازی روش مدرنی به نظر می رسد هنگامی که با یک مسئله بهینه سازی با دانسته های کم و محیط دینامیکی غیر خطی مواجه هستیم.
به منظور بدست آوردن دانسته های با معنی از نتایج جنگی، سیستم منطقی دومی برای مشخص کردن وزنها به کار گرفته می شود.
شکل 5 منحنی تابع عضویت را برای چهار حالت فوق الذکر برای ورودیها و خروجیها را نشان می دهد.
با تابع لیاقت قانونمند (معادله 8) الگوریتم ژنتیکی سعی می کند که بدترین نمره را با انتصاب بالاترین وزن بهبود بخشد، نمره بد بعدی را با مقدار میانی وزن و نمره بالاترین را با کمترین وزن بهبود می بخشد.
با انجام دادن اینکار، الگوریتم ژنتیکی، کمترین نمره را بالا می کشد و بالاترین نمره را پایین می کشد و این کار را با ضرایب وزنی مربوطه انجام می دهد.
این موضوع، تقدم توابع هدف را تعدیل می کند.
بالاترین و پایین ترین تقدم توابع هدف بصورت پیوسته ای در 15 روز جنگی تغییر می کنند.
قانون Eighty – one این تعدیل تقدم توابع هدف را می سازد.
این قانون را می توان همانند یک مربی در نظر گرفت که هر ورودی را کمک می کند که به همه توابع هدف دسترسی پیدا کند و این کار براساس شرایط دینامیکی جنگ انجام می دهد.
الگوریتمهای ژنتیکی کارایی بسیار عالی را دارند هنگامی که با مسائل بهینه سازی با فضای بزرگ سروکار داریم به شرطی که مقدار مناسبی برای پارامترهای از قبیل نرخ جهش ، نرخ تقاطع و اندازه جمعیت در نظر گرفته شود.
اپراتور جهش، شامل تصحیح اتفاقی ژنهاست هنگامی که فرایند کپی کردن کروموزومها از یک نسل به نسل دیگر انجام می شود.
تقاطع که قدرتمند ترین اپراتور ژنتیکی می باشد می تواند بعنوان یک ماشین اصلی برای جستجو در الگوریتم ژنتیکی در نظر گرفته شود .
این اپراتور وظیفه ترکیب بلوکها با هم و ساختن اتفاقی آنها را دارد.
در اکثر الگوریتمهای ژنتیکی، احتمال تقاطع و جهش معمولا در تمام طول مدت اجرای برنامه، ثابت در نظر گرفته می شود.
مسئله مربوط به انتخاب مقدار احتمال عملگرها این است که این مقادیر بصورت گسترده ای تغییر می کنند و اگر ثابت نگه داشته شوند.
الگوریتم ژنتیکی کارایی را ارائه نمی دهند(25).
این موضوع واضح است که هنگام اجرای برنامه، مقادیر این پارامترها باید بر اساس نمره لیاقت هر کدام از افراد داخل جمعیت تغییر کند تا الگوریتم ژنتیکی رفتار بهتری داشته باشد و یک همگرایی لیاقت هموار، نسبتا به تعداد نسلهای کمتری نیاز دارد (26)و (27).
در این کار، دو نرخ جهش و تقاطع هنگامی که الگوریتم ژنتیکی در حال اجرا می باشد، تعدیل می گردد در حالی که اندازه جمعیت برابر 100 و ثابت در نظر گرفته می شود.
به منظور اینکه این پارامتر بصورت سازگار تغییر کنند یک سیستم منطق فازی three input- two output (FLS) استفاده شده است ورودیهای FLS عبارت است از بهترین مقادیر لیاقت ها، مقدار متوسط مقادیر لیاقتهای جمعیت و واریانس مقادیر لیاقت در جمعیت.
سه نوع عضویت( LEFT, small; TR, medium; RIGHT, larg)و تابع عضویت مثلثی برای فازی کردن ورودیها در نظر گرفته شده است.
شکل 6 توابع عضویت و مقدار تغییرات هر متغیر فازی را نشان می دهد.
بهینه سازیِ این انتصابِ مقادیر، معمولا توسط سعی و خطا انجام می شود تا بهترین عملکرد FLS حاصل شود.
یک مجموعه از قوانین که تشریح می کند که چگونه باید نرخ انجام جهش و تقاطع تعدیل شود باید وضع شود که مشخص شود که تحت هر شرایطی، چه عملکردی باید انجام وظیفه کند.
این قوانین با استفاده از این حقیقتها مشخص شده است که بهبود جستجو در ابتدای اجرای برنامه، نرخ جهش باید کم باشد و نرخ تقاطع باید زیاد باشد و سپس نرخ جهش باید افزایش یابد و نرخ تقاطع باید کاهش یابد تا برنامه پایان یابد .
این کارها بصورت خلاصه در زیر آمده است.
6.
Fuzzy sets for adaptive genetic algorithm system.
Descriptions of the fuzzy system's rules: 1.
If (BF is LEFT) then (MR is LEFT) (CR is RIGHT) 2.
If (BF is TR) and (UN is LEFT) then (MR is LEFT) (CR is RIGHT) 3.
If (BF is TR) and (UN is TR) then (MR is TR) (CR is TR) 4.
If (UN is RIGHT) and (VF is TR) then (MR is RIGHT) (CR is LEFT) 5.
If (BF is RIGHT) and (UN is LEFT) then (MR is LEFT) (CR is RIGHT) 6.
If (BF is RIGHT) and (UN is TR) then (MR is TR) (CR is TR) 7.
If (UN is RIGHT) and (VF is LEFT) then (MR is RIGHT) (CR is LEFT) 8.
If (UN is RIGHT) and (VF is RIGHT) then (MR is LEFT) (CR is LEFT) فرایندی که برای حل مسئله انتصاب توسط الگوریتم ژنتیکی با تالع لیاقت وزندار ارائه شد در شکل 7 نمایش داده شده است.
7.
Schematic representation of optimization procedure.
3- نتایج و بحث در دنیای واقعی، تابعی که دارای چند مقدار هدف است و باید بهینه شود ممکن است وابسته به زمان باشد و مقدار بهینه می بایست که در یک بازه محدود زمانی بدست آید (28).
به بیان دیگر، بعضی از کاربردهای واقعی جهانی نظیر سیگنالهای نوری، کنترل ترافیک، کنترل روباتها، کنترل گر طراحی، مشخص کردن مدل، طراحی پایدار و تشخیص بیماری باید بصورت On–Line و در یک محیط دینامیکی انجام بپذیرند (29).
الگوریتمهای ژنتیکی که دارای بهینه ساز DMO می باشند قابلیت برخورد و غالب آمدن بر مسائل بn وضع را دارا می باشند مانند چند مودی بودن، عدم پیوستگی، تغییرات زمانی، اتفاقی بودن و دارا بودن نویز.
اصلی ترین راهبرد کاربرد الگوریتمهای ژنتیکی برای حل مسائل به سه دسته تقسیم می شوند :1- سازگار کردن مسائل با الگوریتم ژنتیکی 2- سازگار گردن الگوریتم ژنتیکی با مسئله 3- سازگار کردن هم مسئله و هم الگوریتم ژنتیکی با هم.
در این تحقیق، روش سوم مورد استفاده قرار گرفته است.
این راهبرد، اجازه تکامل حلهای غیر مشرف را بصورت همزمان در یک بار اجرا و رهبری جستجو در جهتهای مختلف در فضای چند بعدی را می دهد.
این موضوع بسیار با اهمیت است که فهمیده شود که جمعیت در الگوریتم ژنتیکی در نسلهای مختلف هنگامی که برای مسائل بهینه سازی چند هدفه مورد استفاده قرار می گیرد بصورت دینامیک می باشد.
این موضوع به راحتی فهمیده نمی شود که جمعیت چگونه رفتار می کند و چگونه پارامترهای الگوریتم ژنتیکی برای پیدا کردن حلهای غیر مشرف تغییر می کنند.
این موضوع عموما تشخیص داده می شود که نرخ زیادی از دانسته ها می تواند بدست آید، اگر نرخ جهش و تقاطع، صحیح انتخاب شود.
رابطه بین مشخصات جمعیت و پارامترهای الگوریتم ژنتیکی، خیلی و پیچیده و غیر خطی است.
بنابراین مفید است که روابط بصورت زبانی توضیح داده شود تا واگرایی در الگوریتم ژنتیکی باقی ماند.
یک سیستم سازگاری قانونمند با استفاده از مشخصات جمعیت برای تعدیل نرخ های تقاطع و جهش ابداع شده است.
شکل 8 نشان دهنده تغییرات نرخ جهش و تقاطع در 50 نسل می باشد.
8.
Variations of the mutation and crossover rates.
این موضوع را از شکل می توان فهمید که این نرخها بین 018/0 تا 047/0 و 65/0 تا 75/0 تغییر می کنند.
این تغییرات اجازه جستجوی نقاط حلی جدید را می دهند و باعث بهتر شدن زمان اجرای الگوریتمهای ژنتیکی می شوند.
با استفاده از تنظیماتِ خودکار این نرخ ها، جستجو در یک محدوده مشخص گیر نمی کند مخصوصا در ابتدای اجرای برنامه .
رفتار دینامیکیِ مقادیرِ لیاقت برای چهار تابع هدف در شکل 9 نمایش داده شده است.
نتایج بدست آمده از این شکل، خوبی حل را که همه توابع هدف را ار ضا می کند نشان می دهد .
9.
Dynamic behaviors of each objective.
این موضوع را می توان از شکل فهمید که هر کدام از مقادیر لیاقت توابع بین 4/1 و 6/1 تغییر می کند و مقدار واریانس هر کدام از دیگری متفاوت است.
در طی زمان شبیه سازی، تاثیرات بین چهار تابع هدف بصورت حالتهای تاثیر داخلی رخ می دهد و تصحیح هر کدام از توابع هدف بصورت دینامیکی انجام می گیرد.
الگوریتم ژنتیکی با پایه فازی به مقدار متوسط لیاقت بهینه ای در حدود 5/1 برای توابع هدف در طول مدت اجرای برنامه می رسد.
10.
Comparison of the static and dynamic GA systems.
شکل 10 نمایش دهنده مقایسه بین عملکرد دو الگوریتم ژنتیکی استاتیکی و دینامیکی می باشد.
ذات اتفاقی بودن الگوریتم ژنتیکی نیازمند این است که برای رسیدن به جواب قابل اطمینان، چندین بار برنامه را اجرا کرد.
بنابراین الگوریتم ژنتیکی چند بار اجرا شده است و هر بار نیز به جوابهای مشابهی رسیده است.
این موضوع را می توان ملاحظه کرد که الگوریتم ژنتیکی با تابع لیاقت وزنی قانونمند، نسبت به الگوریتم ژنتیکی با تابع لیاقت استاتیکی به جوابهای بهتری دست یافته است.
از نتایج حدی DMOPS می توان به کارایی کامپیوتری قیدهای زمانی، همگرایی به حلهای بهینه پارتو و انجام بر آورد بهینه سازی چند هدفه در چند ماتریس نام برد.
شبیه سازی نتایج بدست آمده نشان می دهد که بهبود زیادی در اجرا ی برنامه ایجاد شده است که این بهبود برای قیدهای زمانی، زیاد دیده می شود.
ترکیب جستجوی الگوریتم ژنتیکی و روشهای بهینه سازی با تکنیک های مکمل و مکانیزمهای سازگار، منجر به تشکیل الگوریتمهای ترکیبی می شود که روشی برای حل DMOPs است اما هنوز کارهای بیشتری برای کارائی هر چه زیاد تر این الگوریتمها باید انجام گیرد.