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

الگوریتم شبیه سازی تبرید SA

قبل از بررسی مسئله کوله پشتی با الگوریتم SA در پایتون بهت است با الگوریتم شبیه سازی تبرید آشنا شوید. الگوریتم شبیه سازی تبرید یا تبرید شبیه سازی شده Simulated Annealing که در بسیاری موارد با نام الگوریتم شبیه سازی حرارتی نیز شناخته می‌شود، از جمله الگوریتم‌های متاهیورستیک یا فرا ابتکاری است که برای حل مسائل بهینه سازی مورد استفاده قرار می‌گیرد. یکی از مسائلی که برای حل آن می‌توان از الگوریتم شبیه سازی تبرید SA استفاده کرد، مسئله n وزیر می‌باشد.

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

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

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

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

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

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

این مثالی از مسئله کوله پشتی می‌باشد که قابل حل با الگوریتم تبرید شبیه سازی شده Simulated Annealing می‌باشد. در ادامه درمورد سورس کد حل مسئله کوله پشتی با الگوریتم SA در پایتون بیشتر صحبت شده است.

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

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

import random as rd
import numpy as np
import matplotlib.pyplot as plt
def CreateModel():
    class model:
        def __init__(self,n,v,w,W):
            self.n = n
            self.v = v
            self.w = w
            self.W = W
    v = np.array([391,444,250,330,246,400,150,266,268,293,471,388,364,493,202,161,410,270,384,486])
    w = np.array([55,52,59,24,52,46,45,34,34,59,59,28,57,21,47,66,64,42,22,23]

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

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

***  توجه  ***

قبل از اجرای سورس کد الگوریتم در محیط پایتون حتماً از نصب پکیج‌های مورد استفاده در این سورس کد در Python خود مطمئن شوید پکیج‌های استفاده شده در این سورس کد numpy و matplotlib می‌باشد که اولی پکیج مربوط به استفاده از آرایه‌ها و ماتریس‌ها در پایتون و دومی مربوط به عملیات‌های نموداری و Plot گرفتن می‌باشد. پیشنهاد ما نصب اسپایدر (Spyder (Python 3.7 می‌باشد که هم پایتون و پکیج‌های مختلف و هم IDEهای مختلفی را همراه با امکان آپدیتشان نصب می‌کند.

درباره سورس کد

سورس کد حل مسئله کوله پشتی با الگوریتم SA در پایتون عنوان اثری است که در این پست به آن پرداخته شده است.اثر در پایتون ۳.۱۰ برنامه نویسی شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. قبل از اجرای سورس کد در محیط پایتون حتماً از نصب پکیج‌های مورد استفاده در این سورس کد در Python خود مطمئن شوید. پکیج‌های استفاده شده در این سورس کد numpy و matplotlib می‌باشد که اولی پکیج مربوط به استفاده از آرایه‌ها و ماتریس‌ها در پایتون و دومی مربوط به عملیات‌های نموداری و Plot گرفتن می‌باشد.