روش بهینه سازی کلنی مورچه برای مسئله نبساک باینری در حالت فازی
چکیده
در این مقاله ما یک الگوریتم جدید بهینه ساز کلنی مورچه برای حل مسئله نبساک باینری را ارائه می کنیم . در الگویتم پیشنهادی برای N گروه نامزد تولید شده و هر کدام از گروه های نامزد دقیقاً دارای M متغیر (برای M مورچه) به صورت صفر یا یک هستند . برای هر کدام از مقادیر برگزیده در هر گروه یک فرمون با مقدار ۰٫۱ و ۰٫۹ در نظر گرفته و هر موچه یک مقدار برگزیده در هر گوه انتخاب می کنند . بنابراین راه حل باینری برای هر کدام از مورچه ها با گزینش مقادیر از هر گروه به کار گرفته می شود . در هر نسل فرمون کار بروز رسانی و تبخیر را انجام می دهد . در طول اجرای الگوریتم پس از به وجود آمدن تعدادی از نسل ها بهترین راه حل به صورت به راه حل مربوط به جمیعت موقت شناسایی شده و پس از آن شاهد استفاده از روش های کراس اور و همچنین شکل های دیگری از تکثیر نسل های مورچه ها خواهیم بود . ما سود را در نظر گرفته و ضریب وزنی فازی را به عنوان یک رقم فازی ذوزنقه ای منظور می کنیم . قابلیت فازی و ضرورت این روش برای به دست آوردن تصمیم بهینه با پیشنهاد الگوریتم کلنی مورچه به کار گرفته شده است . آزمایشات محاسباتی با مجموعه های متفاوتی از داده ها برای پشتیبانی از روش پیشنهادی انجام شده اند .
کلید واژه ها : مقدار برگزیده – بهینه سازی کلنی مورچه – رقم فازس ذوزنقه ای – مسئله نبساک – احتمال – ضرورت
مقدمه
پیشینه تحقیقات مربوط به مسئله نبساک باینری بسیار اثر گذار بوده و یکی از مهمترین مسائل کلاسیک در بهینه سازی ترکیبی است . با توجه به مجموعه محدودی از گزینه ها هر کدام از این موارد ضریبی را بر اساس مقدار سود دریافت کرده و هدف آن مشخص کردن زیر مجموعه گزینه ها به گونه ای است که مقدار کل ضرایب کمتر از مقداری باشد که در محدوده های مجاز در نظر گرفته شده و سود کلی نیز تا سر حد ممکن بزرگ باشد . به واسطه این که بودجه های مالی و غیر مالی و همچنین هزینه های مالی و غیر مالی معیارهای پیشگیری احتمالاً دارای ماهیتی همراه با عدم قطعیت هستند . از این رو روش فازی ۰۱ در مدل نبساک پیشنهاد می شود . در مدل فازی سنجش کمیت ضرایب ، هزینه و اهداف بودجه با ارقام فازی در نظر گرفته می شوند .
الگوریتم بهنیه سازی کلنی مورچه توسط دوریگو ، مانیزو و کلرنی پیشنهاد شده و برای حل مسائل سفرهای دریانوردان به کار گرفته شده است . کلنی مورچه شامل عوامل همکاری کننده ای است که دوریگو و گامبرلا آن ها را توصیف کرده اند . شوکل و دوریگو الگوریتم بهنیه سازی کلنی مورچه را در حوزه پیوسته ارائه کرده اند . الگوریتم ACO برای حل مسئله کوتاه ترین مسیر و همچنین مسائل برنامه نویسی خطی به کار رفته و می توان از آن برای حل تکالیف دو جمله ای و غیره استفاده کرد . مسئله نبساک باینری می تواند در حلس مائل عملی مختلف مثل ارتباطات راه دور ، تولید و مسائل بودجه بندی و غیره مؤثر واقع شود .
گامبردلا و همکرات یک سیستم ترکیبی کلنی مورچه برای مسئله تعیین سفارش ترتیبی ارائه هستند . یوو و همکاران نیز به توسعه یک مدل متعامد پرداخته اند که پایه و اساس آن جستجو در کلنی مورچه برای حل مسئله بهینه سازی پیوسته است . ژیائو و لی مسئله بهنیه سازی کلنی مورچه به صورت ترکیبی برای حوزه پیوسته پیشنهاد کرده اند . در سال های اخیر بسیاری از الگوریتم هیورستیک برای حل مسائل باینری نبساک به کار رفته اند . لین و لیو پیشنهاد کرده اند از الگوریتم تکاملی طرح وار برای مسئله ۰۱ نبساک استفاده شود . کتاب خوبی در مورد الگوریتم ها و اجرا در کامپیوتر در حوزه مسائل نبساک توسط مارتلو و همکاران نوشته است . لین به حل مسئله نبساک با استفاده از الگوریتم ژنتیکی GA پرداخته و ضرایب آن را در محیط فازی در نظر گرفته است . وی از درجه عضویت رقم فازی استفاده کرد . کنگ و همکاران نیز الگوریتم ACO را برای مسئله نبساک چند بعدی با استفاده از پدیده های مختلف استراتژی های متفاوت مربوط به وضعیت پوششی الگوریتم به کار برده و از همگرایی پیش از موعد اجتناب کرده اند .
تورنگ و همکاران به تشریح واکنش شیمیایی بهینه سازی با استفاده از استراتژی حریصانه برای مسئله باینری نبساک پرداخته اند . رن و همکاران الگوریتم ACO با تقلیل لاگرانژ را برای مسئله نبساک چند بعدی که امکان انتخاب متغیرهای آن وجود دارد ارائه نمده اند . انواع متفاوتی از مسائل نبساک باینری وجود دارد که با استفاده از تکنیک های بهینه سازی مختلف محاسبه شده اند ، اما تحقیق در مورد آن ها همچنان از اهمیت برخوردار است . به واسطه این که برخی از مهمترین مسائل باینری نبساک در جهان واقعی مخفی شده اند باید برای حل آن ها از روش های متفاوت اجرایی در قالب برخی شکل های بهینه استفاده کرد . برخی الگوریتم ها ممکن است بیشتر بر اساس مزیت و محدودیت ها موارد عمل شوند اگر چه برخی روش های جدید امکان حل ابعاد در سطوح پایین ۰۱ را فراهم می کنند اما ممکن است نتوان از آن برای حل ابعاد بالاتر از مسائل باینری نبساک استفاده کرد .
در مسئله تقلیلی نبساک فروشگاه یک بسته تخفیفی را در جایی ارائه می کند که بیش از یک شیئی از یک فروشگاه خریداری شود . مدل جدید مسئله نبساک به نام مدل تخفیف یافته نبساک ۰۱ توسط کلرر و همکاران تشریح شده و در بردارنده شکل توسعه یافته از موارد منتخب مربوط به هر کدام از گروه ها بر اساس مفهوم تخفیف است . سیستم کلنی مورچه برای برنامه ریزی شغلی فروشگاهی توسط کلرنی و همکاران تشریح شده است . فریویلا به تشریح ابعاد چندگانه مدل نبساک ۰۱ پرداخته که پیش از این در حوزه کاربرد تشریح شده و باس و همچنین کارامان یک مدل استدلال بر اساس سرمایه فازی پیشنهاد کرده اند که در بردارنده نوعی از مدل های نبساک چند بعد پیوسته است .
ژانگ و همکاران از الگوریتم ارگانیسم آموبادی برای حل کردن مسئله نبساک ۰۱ در جایی استفاده کرده اند که امکان تبدیل این مسئله به الگوریتم مستقیم شبکه گراف وجود داشته است . باس یک مدل دو بعدی فازی ۰۱ نبساک برای سرمایه گذاری پیشگیرانه با نابرابری های فازی پیشنهاد کرده است . چن و همکاران نیز یک مدل فازی پیوسته از مدل نبساک ا در قالب یک تابع واحد ارائه کرده که در بر دارنده ضرایب فازی و پارامترهای مدل نبساک است که توسط لین و همکاران پیشنهاد شده است.
در این مقاله ما هدف واحد فازی ۰۱ در مدل نبساک با ضریب و سود فازی در نظر گرفته و روش بهینه سازی کلنی مورچه برای حل مسئله نبساک باینری در محیط فازی مورد استفاده قرار دادیم . در این جا فرمون آغازی به صورت تصادفی تولید شده و پس از یک تعامل واحد بهترین مسیر استخراج و سپس تقاطع آن به همراه جهش اجرا شده و از مقدار برگزیده استفاده می شود . یک ویژگی جدید در قالب بهینه سازی اصلاحی در این الگوریتم به کار رفته که بهترین راه حل را با بدترین راه حل جایگزین می کند . مدل فازی را می توان مجدداً از حالت فازی خارج کرد و برای این منظور می توانیم از روابط فازی مختلف استفاده کنیم . از آن جا که بهینه سازی اهداف فازی به خوبی تعریف نشده اند ارزیابی راه حل بهینه دشوار است . به واسطه این پیچیدگی قابلیت های فازی ضرورت بر مبنای رویکردهایی را مطرح می کنند که در آن اهداف فازی در چارچوب های معادل در نظر گرفته شده است . اگوریتم ACO پیشنهادی ما می تواند این مسئله را با ابعادی حل کند که به طور پیوسته مسائل گسسته را حل می کند . در ادامه این مقاله به صورت زیر سازمندهی شده . بخش ۲ به تخصیص ویژگی های ریاضی پیش فرضی پرداخته که از آن ها برای حل مسئله پیشنهادی استفاده شده . در بخش ۳ ما به تعریف مسئله در محیط فازی پرداخته و الگوریتم را در یک نگاه بررسی می کنیم . الگوریتم پیشنهادی برای مسئله مورد نظر در بخش ۴ تعریف شده ، بخش ۵ به تعریف نتایج آزمایش و تحلیل نتایج پرداخته و کاربرد مسئله نیز در بخش ۶ مورد بحث قرار داده ایم . نتیجه گیری ها در بخش ۷ آورده شده اند .
An Ant colony optimization approach for binary knapsack problem under fuzziness
Abstract
In this paper, we represent a novel ant colony optimization algorithm to solve binary knapsack problem. In the proposed algorithm for n objects, n candidate groups are created, and each candidate group has exactly m values (for m ants) as 0 or 1. For each candidate value in each group a pheromone is initialized by the value between ۰٫۱ and ۰٫۹, and each ant selects a candidate value from each group. Therefore, the binary solution is generated by each ant by selecting a value from each group. In each generation, pheromone update and evaporation is done. During the execution of algorithm after certain number of generation the best solution is stored as a temporary population. After that, crossover and mutation is performed between the solution generated by ants. We consider profit and weight are fuzzy in nature and taken as trapezoidal fuzzy number. Fuzzy possibility and necessity approaches are used to obtain optimal decision by the proposed ant colony algorithm. Computational experiments with different set of data are given in support of the proposed approach.
لینک مقاله اصلی :
https://www.sciencedirect.com/science/article/pii/S0096300313008278
لطفاً براي ارسال دیدگاه، ابتدا وارد حساب كاربري خود بشويد