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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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 در متلب عنوان اثری است که در این پست به آن پرداخته شده است. اثر در نرم افزار متلب نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است و دارای نشان تضمین کیفیت پی استور می‌باشد. برای دانلود اثر مذکور آن را خریداری کنید.