سورس کد الگوریتم مورچه 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 در متلب

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

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

function model=CreateModel()

    v=[391 444 250 330 246 400 150 266 268 293 471 388 364 493 202 161 410 270 384 486];
    
    w=[55 52 59 24 52 46 45 34 34 59 59 28 57 21 47 66 64 42 22 23];
    
    n=numel(v);
    
    W=500;
    
    model.n=n;
    model.v=v;
    model.w=w;
    model.W=W;

end

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

function [z, sol]=MyCost(x,model)

    v=model.v;
    w=model.w;
    W=model.W;

    V1=sum(v.*x);
    W1=sum(w.*x);
    V0=sum(v.*(1-x));
    W0=sum(w.*(1-x));
    
    Violation=max(W1/W-1,0);
    
    z=V0*(1+100*Violation);
    
    sol.V1=V1;
    sol.W1=W1;
    sol.V0=V0;
    sol.W0=W0;
    sol.Violation=Violation;
    sol.z=z;
    sol.IsFeasible=(Violation==0);

end

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

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

درباره محصول

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

مباحث مرتبط با الگوریتم کلونی مورچگان ACO

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