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

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

الگوریتم ازدحام ذرات – Particle Swarm Optimization

الگوریتم بهینه سازی ازدحام ذرات Particle Swarm Optimization به اختصار PSO یکی از مهم‌ترین الگوریتم های بهینه سازی است که با الهام از رفتار اجتماعی حیوانات مانند پرندگان که در گروه‌هایی کوچک و بزرگ کنار هم زندگی می‌کنند، طراحی شده است. این الگوریتم جزو الگوریتم‌های حوزه هوش جمعی است.

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

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

برای توضیح این مسئله به زبان ساده می‌توان از یک سری مثال‌های واقعی استفاده کرد، چرا که این مسئله در زندگی روزمره هم می‌تواند کاربرد داشته باشد. اگر دانشجوی رشته کامپیوتر باشید و یا با مسائل بهینه سازی سر و کار دارید، حتماً با مسئله کوله پشتی یا Knapsak Problem آشنایی خواهید داشت.

موارد استفاده از این مسئله در زندگی روزمره بسیار است، مانند برش پارچه با الگو به طوری که کم‌ترین هدرروی انجام شود. اما توضیح این مسئله با مدل سازی ریاضی کمی ممکن است کاربران را سردرگم سازد، بنابراین با معروف‌ترین مثال این مسئله را برای ما توضیح می‌دهیم.

فرض کنید یک دزد وجود دارد که قصد دزدی از خانه دارای وسایل گران قیمت بی‌‎شماری است. این دزد یک کیف یا کیسه به همراه دارد که تنها وزن مشخصی را می‌تواند تحمل کند. برای مثال اگر میزان تحمل این کیسه ۳۰ کیلو باشد، امکان اینکه وسایلی با حجم بیشتر از ۳۰ کیلو یا مجموع حجم بیشتر را نخواهد داشت.

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

این مثالی از مسئله کوله پشتی می‌باشد که قابل حل با الگوریتم Particle Swarm Optimization است. در ادامه درمورد سورس کد حل مسئله کوله پشتی با الگوریتم ازدحام ذرات بیشتر صحبت شده است.

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

این سورس کد از ۴ فایل تشکیل شده است که فایل PSO.m فایل اصلی برنامه است و فراخوانی دیگر توابع و مقادیر پارامترها و الگوریتم ازدحام ذرات در داخل این فایل قرار دارد. فایل CreateModel.m فایلی است که از آن برای ایجاد وزن و ارزش کالاها از این تابع استفاده شده است؛ و در نهایت فایل MyCost.m می باشد که تابع هزینه را دربر گرفته است. بخشی از سورس کد تابع هزینه در زیر آورده شده است.

function [z, sol]=MyCost(pos,model)
    x=round(pos);
    v=model.v;
    w=model.w;
    W=model.W;
    V1=sum(v.*x);   % Sum of the selected values
    W1=sum(w.*x);   % Sum of selected weight
    V0=sum(v.*(1-x)); % Sum of the unselected values
    W0=sum(w.*(1-x)); % Sum Of unselected weight

برای دریافت سورس کامل حل مسئله کوله پشتی با الگوریتم PSO در متلب لطفا آن را خریداری کنید.

تصاویر خروجی حل مسئله

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

سورس کد حل مسئله کوله پشتی با الگوریتم PSO در متلب در محیط Matlab 2017 برنامه نویسی و اجرا شده است و قابل اجرا با نسخه‌های بالاتر متلب نیز هست. این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت اثر توسط پی استور تضمین می‌شود و دارای نشان تضمین کیفیت پی استور است. برای دانلود محصول آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.