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

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

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

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

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

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

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

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

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

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

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

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

این سورس کد از 4 فایل تشکیل شده است که فایل 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 در متلب در محیط Matlab 2017 برنامه نویسی و اجرا شده است و قابل اجرا با نسخه های بالاتر متلب نیز هست. این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت محصول توسط پی استور تضمین می شود و محصول دارای نشان تضمین کیفیت پی استور است. برای دانلود محصول آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.

مطالب مرتبط با الگوریتم PSO

سورس کدهای آماده حل مسئله کوله پشتی