سورس کد الگوریتم مورچه ACO برای حل مسئله کوله پشتی Knapsack در متلب

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

مسئله کوله پشتی Knapsack

فرض کنید که جهانگردی می خواهد کوله پشتی خود را با انتخاب حالت های ممکن از بین وسایل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسایل از 1 تا n و تعریف برداری از متغیرهای دودویی بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است، که محدودیت را برآورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه ای از مساللی که می توانند بصورت مسئله کوله پشتی فرمول بندی شوند.

مسئله کوله پشتی

مسئله زیر را در نظر بگیرید:

فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد. بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهد که بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم.

در این رابطه باید روشی برای حل این مسئله پیدا کرد. یک روش ابتدایی که در نگاه اول توجه ما را به خود جل می کند، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است. بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = 60 بیش از 30 سال وقت لازم دارد و بیش از 60 سال برای n = 61 و ده ها قرن برای n = 65 والی آخر. با این وجود، با استفاده از الگوریتمهایی خاص می توان در بسیاری موارد مسئله ای با n = 100000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد.

معروف ترین نوع از این مسئله، مسئله کوله پشتی 0 و 1 است. یعنی تعداد از هر شی،  0 یا 1 است  0 یعنی آن شی را انتخاب نمی کنیم( یا 1 )آن شی انتخاب می شود.

مسئله کوله پشتی

الگوریتم بهینه سازی کلونی مورچگان ACO

الگوریتم بهینه سازی کلونی مورچه  Ant Colony Optimization یا به اختصار ACO مورچگان تحت عنوان الگوریتم های هوش ازدحامی (هوش گروهی) شناخته شده و به مدل سازی رفتار مورچه های واقعی می پردازد. مورچه ها حشراتی هستند که می توانند گروه ها (کلونی ها) را شکل دهند. چنین رویکرد جمعیت محوری این امکان را برای الگوریتم ACO ایجاد می کند تا به حل مسائل بهینه سازی پویا به طور کاملا کارآمد بپردازد. مورچه ها به عنوان مخلوقات خودسازمانده می باشند.

از آنجایی که مورچه ها اصلا چشم ندارند، تعاملات آن ها از طریق ماده شیمیایی فرومون که از آن برای نشان گذاری مسیر استفاده می شود، اانجام می گیرد. هرچه فرومن های بیشتری در مسیر قرار گیرد مابقی مورچه ها از این مسیر بیشتر استفاده می کنند؛ بنابراین، چنین کمیتی نشان می دهد که این مسیر به عنوان یکی از بهینه ترین و کوتاه ترین راه می باشد. اکنون نگاهی به یک نمونه عینی می اندازیم. هدف پیدا کردن بهترین راه از نقطه آغازی N (آشیانه) به نقطه مقصد F (منبع غذا) می باشد.الگوریتم مورچه ACO

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

سورس حل مسئله  کوله پشتی با الگوریتم کلونی مورچه ACO در متلب

در این قسمت سورس برنامه حل مسئله فروشنده دوره گرد TSP با الگوریتم کلونی مورچه ACO در متلب آماده شده است این سورس کد شامل 4 فایل می باشد که عبارتند از:

  • aco.m: فایل اصلی برنامه است و فراخوانی دیگر توابع و مقادیر پارامتر ها و الگوریتم مورچه در داخل این فایل قرار دارد.
  • CreateModel.m: برای ایجاد وزن و ارزش کالاها از این تابع استفاده می شود.

  • RouletteWheelSelection.m: انتخاب چرخه رولت که در بحث انتخاب تصادفی برای حرکت مورچه است از این تابع استفاده می شود.
  • MyCost.m: تابع هزینه می باشد که بصورت زیر است.

برای دریافت سورس کامل محصول لطفا آن را خریداری کنید.

ویدئوی معرفی محصول

درباره محصول

سورس برنامه حل مسئله کوله پشتی Knapsack  با الگوریتم کلونی مورچه ACO در متلب عنوان محصولی است که در این پست به آن پرداخته شده است. محصول در نرم افزار متلب نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. محصول دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود محصول آن را خریداری کنید.

17,000 تومان

1 دیدگاه برای سورس کد الگوریتم مورچه ACO برای حل مسئله کوله پشتی Knapsack در متلب

  1. programstore

    نظرات و دیدگاه های خود را با ما درمیان بگذارید.

دیدگاه خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.