حل مسئله فروشنده دوره گرد با الگوریتم GPC ساخت اهرام جیزه در متلب

در این بخش سورس کد حل مسئله فروشنده دوره گرد با الگوریتم GPC ساخت اهرام جیزه در متلب قرار داده شده است. مسئله فروشنده دوره گرد و حل آن از جمله مواردی است که می‌توان به کمک الگوریتم‌های فرا ابتکاری انجام داد. الگوریتم‌های متاهیورستیک که برای مسائل بهینه سازی مورد استفاده قرار می‌گیرند، انواع مختلفی دارند که یکی از آن‌ها الگوریتم GPC یا همان Giza Pyramids Construction می‌باشد و برای حل مسئله TSP یا همان فروشنده دوره گرد استفاده می‌شود. توضیحات بیشتر درمورد این سورس کد در ادامه داده شده است.

الگوریتم ساخت اهرام جیزه GPC

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

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

برای حل مسئله فروشنده دوره گرد، می‌توان از الگوریتم ساخت اهرام جیزه به صورت بهینه استفاده نمود، در ادامه درمورد مسئله فروشنده دوره گرد توضیحات بیشتری خواهیم داد.

مسئله فروشنده دوره گرد TSP

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

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

در عین حال فروشنده دوره گرد باید یک بار از هر شهر عبور کند و همزمان با کمترین هزینه، کمترین مسافت را نیز طی کند.

حل مسئله فروشنده دوره گرد با الگوریتم GPC در متلب

در نمایش راه حل برای مسئله فروشنده دوره گرد می‌توان از یک الگویی بهره جست و مسئله TSP را با الگوریتم‌های پیوسته نیز حل کرد. برای این منظور بعد یا سایز هر جواب در الگوریتم ساخت اهرام جیزه را می‌توان دنباله‌ای از شهرها در نظر گرفت فقط به جای شماره شهرها می‌توان از اعداد بین ۰ و ۱ که بصورت اعداد پیوسته هستند استفاده کرد. در واقع اندیس کوچکترین عدد داخل بردار جواب به عنوان شماره شهر تعیین می‌شود و سپس به ترتیب اعداد از کوچک به بزرگ می‌تواند Sort شود و در حقیقت اندیس هر خانه به عنوان ترتیب ملاقات شهرها در نظر گرفته می‌شود.

مسئله فروشنده دوره گرد یا TSP قابل حل با الگوریتم‌های فرا ابتکاری می‌باشد که یکی از آن‌ها الگوریتم ساخت اهرام جیزه می‌باشد. این سورس کد دارای ۴ فایل اصلی می‌باشد که مهم ترین فایل GPC.m است و در برگیرنده کدهای اصلی می‌باشد و فراخوانی‌ها از فایل‌های دیگر در این سورس کد انجام می‌شود. فایل بعدی TourLength.m است که توابع مسئله فروشنده دوره گرد در این فایل قرار گرفته است. دو فایل دیگر CreateModel.m و PlotSolution.m می‌باشد.

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

model=CreateModel();    % Create Problem Model

CostFunction=@(tour) TourLength(tour,model); 

nVar=model.n;   % Number of Deciison Variables
VarSize=[1 nVar];          % Decision Variables Matrix Size
VarMin= -10;                 % Decision Variables Lower Bound
VarMax= 10;                % Decision Variables Upper Bound
%% Giza Pyramids Construction (GPC) Parameters
MaxIteration=1000;   % Maximum Number of Iterations (Days of work)
nPop=50;             % Number of workers

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

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

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

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