نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 دانشجوی دکترای، دانشکده نساجی، دانشگاه یزد، یزد، ایران
2 استادیار، دانشکده نساجی، دانشگاه یزد، یزد، ایران
چکیده
کلیدواژه‌ها
عنوان مقاله [English]
نویسندگان [English]
Packing is one of the well-known problems in operation research, especially in production planning. The main objective of studying the packing problem is to reduce the wastes of cutting through optimization of packing of pieces. Packing is a kind of NP-hard problem that the precise methods are not able to solve it. In this paper, in order to achieve an optimal packing of Non-guillotine cutting problems, the meta-heuristic emerging Imperialist Competitive Algorithm was used and the results were compared with the output of the genetic algorithm, which is the typical algorithm in solving packing problems. To achieve better solutions, the parameters of all meta-heuristics were calibrated with Taguchi experiment method. The efficacy of the proposed approach was tested on a set of instances, taken from the literature, and the results of the proposed algorithm were tested statistically by ANOVA. The results of this study showed that the meta-heuristic emerging Imperialist Competitive algorithm is more efficient and faster in solving packing problems.
Introduction: Packing problems are problems which are difficult or sometimes impossible to solve exactly. Researchers have provided many different solutions based on heuristic and meta-heuristic to approximately solve these problems.
Materials and Methods: Imperialist Competitive Algorithm is a new evolutionaryoptimization method which is inspired by imperialisticcompetition Atashpaz-Gargari (2007). Like other evolutionary algorithms, it startswith an initial population which is called country and isdivided into two types of colonies and imperialists which,together, form empires. Imperialistic competition among theseempires forms the proposed evolutionary algorithm. Duringthis competition, weak empires collapse and powerful onestake possession of their colonies. Imperialistic competitionconverges to a state in which there exists only one empire andcolonies have the same cost function value as the imperialist.The pseudo code of Imperialist competitive algorithm is asfollows:
1) Select some random points on the function and initializethe empires.
2) Move the colonies toward their relevant imperialist (Assimilation).
3) Randomly change the position of some colonies (Revolution).
4) If there is a colony in an empire which has lower costthan the imperialist, exchange the positions of thatcolony and the imperialist.
5) Unite the similar empires.
6) Compute the total cost of all empires.
7) Pick the weakest colony (colonies) from the weakestempires and give it (them) to one of the empires (Imperialistic competition).
8) Eliminate the powerless empires.
9) If stop conditions satisfied, stop, if not go to 2.
After dividing all colonies among imperialists and creatingthe initial empires, these colonies start moving toward theirrelevant imperialist state which is based on assimilationpolicy
Results and Discussion: In this study, in order to achieve an optimal packing of non-guillotine cutting problems, at first the meta-heuristic algorithm of Imperialist Competitive Algorithm was used. Then the results were compared with the output of the genetic algorithm which is the typical algorithm in solving packing problems. The results showed that ICA had the better fitness function average than GA. Also, ICA needs less number of function evaluations. Therefore ICA is faster than GA in solving permutation packing problems.
References
Atashpaz-Gargari, E., & Lucas, C. (2007). "Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition". IEEE Congress on Evolutionary Computation, 4661-4667
Ebrahimi, S., & Payvandy, P. (2013). "Optimization of the Link Drive Mechanism in a Sewing Machine Using Imperialist Competitive Algorithm". International Journal of Clothing Science and
Technology, 26(3), 247 – 260.
Bluma, C., & Schmid, V. (2013). "Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm". Procedia Computer Science, 18, 899 – 908.
کلیدواژه‌ها [English]
مقدمه
در فرایند تولید بسیاری از صنایع نیاز است تا قطعات کوچک‌تر با برش از اجسام بزرگ‌تر حاصل یا به‌طور معادل، قطعه‌های کوچک‌تر در جسمی بزرگ‌تر جای داده شوند. در این عمل معمولاً بخش‌هایی از جسم بزرگ‌تر به قطعاتی بدون استفاده تبدیل و ضایعات و دورریز محسوب می‌شوند. کاهش چنین ضایعاتی نقش مهمی در کاهش هزینه‌ها دارد. مسأله چیدمان یکی از موضوعات علم تحقیق در عملیات است و توجه بسیاری از پژوهشگران را به خود جلب کرده است. در بسیاری از صنایع از جمله صنایع تولیدکنندۀ بدنۀ خودرو، سازه‌های ساختمانی، کشتی و هواپیماسازی، کاغذ، پوشاک، چرم، سنگ‌بری و در فعالیت‌هایی مانند حمل‌ونقل، انبارداری و بسته‌بندی، مسأله چیدمان و یا مسائل مشابه آن مشاهده می‌شود.
تعداد الگوهایی که دسته‌ای از قطعات می‌توانند در کنار یکدیگر قرار دهند بسیار زیاد است و تعداد کمی از این الگوها ضایعات کم تولید می‌کنند؛ بنابراین استفاده از روال عمومی ریاضی برای حل این نوع مسائل امکان‌پذیر نیست. از دهۀ 50 میلادی که رایانه‌ها به‌عنوان پردازنده‌های سریع و اقتصادی داده‌ها ظاهر شدند، به مسأله چیدمان توجه بیشتری شده است. در طی سال‌ها، دو روش اصلی اکتشافی و تقریب بر پایۀ برنامه‌ریزی خطی برای حل این نوع مسائل ارائه شد (هوپر و تورتون[i]، 2001). استفاده از برنامه‌ریزی خطی بیشتر محدود به مسائل چیدمان یک‌بعدی یا دوبعدی با تعداد قطعات کم است. بیشتر توجه پژوهشگران به‌علت بزرگ‌بودن فضای جواب مسأله چیدمان، معطوف به روش‌های ابتکاری و فرا ابتکاری حل این‌گونه مسائل است؛ به‌نحوی‌که توانایی جستجوی هوشمندانه فضای جستجو را دارند (دیکهوف[ii]، 1990).
در روش‌های گوناگون حل مسائل چیدمان، از انواع الگوریتم‌های ابتکاری جایگذاری برای تبدیل مجموعه‌ای از قطعات به چیدمان معتبر استفاده می‌شود. چیدمان معتبر، چیدمانی است که در آن قطعات هیچ‌گونه هم‌پوشانی با یکدیگر ندارند و به‌طور کامل در داخل شئ مورد نظر قرار می‌گیرند. الگوریتم‌های ابتکاریِ جایگذاری با قراردادن گام‌به‌گام قطعات یا جابه‌جایی قطعاتِ جایگذاری‌شده روی شئ، مطابق قانون‌های خاص،برای تولید چیدمان معتبر استفاده می‌شوند.
بورک[iii] و همکارانش (2006)، لیو و تنگ[iv] (1999)، چازل[v] (۱۹۸۳) و اولیور و فریرا[vi] (1993) از جمله افرادی هستند که روش‌هایی ابتکاری برای چیدمان انواع قطعات ارائه کرده‌اند.
لئونگ[vii] و همکارانش (2012) روشی ابتکاری براساس جستجوی ممنوعه مبتنی بر برنامه‌ریزی غیرخطی برای حل مسأله چیدمان دوبعدی قطعات نامنظم ارائه کرده‌اند. در روش ابتکاری که اوزکان[viii] (2013) معرفی کرده است، برخلاف روش‌های دیگر در هر مرحله، محل چیدمان یک جفت قطعه به‌جای یک قطعه تعیین می‌شود.
الگوریتم‌های جستجوی فرا ابتکاری با استفاده از استراتژی‌های خاص مبتنی بر استفاده از نتایج موجود با الهام‌گرفتن از فرایندهای طبیعی یا فیزیکی توانایی پیداکردن چیدمان مناسب، مؤثر و کارآمد را دارند. الگوریتم ژنتیک یکی از الگوریتم‌های فرا ابتکاری است که برای حل مسائل چیدمان بسیار استفاده شده است. پژوهشگرانی مانند فالکنیر و فالکنوار و دلچیمبر[ix] (1992)، هوانگ[x] و همکارانش (1994)، رونارسون[xi] و همکارانش (1996)، داگلی و پوشیانُندا[xii] (1997)، لیو و تنگ (1999)، هوپر و تورتون (2002)، ولنزوئلا و وانگ[xiii] (2001)، بورتفلد[xiv](2006)، هیفی و هالاه[xv] (۲۰۰۳) و بورک و همکارانش (2006) مطالعاتی روی الگوریتم ژنتیک (ابزاری برای حل مسائل چیدمان) انجام داده‌اند.
الگوریتم انجماد تدریجی یکی دیگر از روش‌های فرا ابتکاری است که در حل مسائل چیدمان به کار گرفته شده است. داوسلند[xvi] (1993)، لیا و چان[xvii] (1997)، فاینا[xviii] (1999)، بیسیگل[xix] و همکارانش (2005)، از جمله پژوهشگرانی هستند که از الگوریتم انجماد تدریجی برای حل مسائل چیدمان استفاده کرده‌اند.
سومین الگوریتم فرا ابتکاری که در حل مسائل چیدمان از آن استفاده می‌شود، الگوریتم جستجوی ممنوعه است. ازجمله پژوهشگرانی که عملکرد الگوریتم جستجوی ممنوعه را برای حل مسائل چیدمان ارزیابی کرده‌اند عبارت‌اند از لودی[xx] و همکارانش (2004)، وی[xxi] و همکارانش (2011)، آلوارزوالد[xxii] و همکارانش (2007)، بورک و همکارانش (2006) و پورزا و مورابیتو[xxiii] (2006).
شاین و کیتا[xxiv] (2012) از الگوریتم فرا ابتکاری ازدحام ذرات و وانگ[xxv] (2010) از الگوریتم ژنتیک انطباقی برای حل مسائل چیدمان دوبعدی استفاده کرده‌اند.
مسأله چیدمانِ بین، نوعی مسأله چیدمان است که در آن قطعات باید روی تعدادی شئ با طول و عرض ثابت چیده شوند.
آمارو[xxvi] و همکارانش (2013) و جونیور[xxvii] و همکارانش (2013) سعی در حل مسأله چیدمان دوبعدی قطعات نامنظم با استفاده از ترکیب الگوریتم ژنتیک با الگوریتم‌های چیدمان، ابتکاری مختلف داشتند.
دوسلند16 (1993) از جمله اولین پژوهشگرانی بود که از روش‌های فرا ابتکاری برای حل مسائل چیدمان قطعات با اشکال منظم استفاده کرد. الگوریتم انجماد تدریجی دوسلند هر دو دسته از راه‌حل‌های معتبر و نامعتبر را بررسی و راه‌حلی با کمترین هم‌پوشانی را جستجو می‌کند. جیکوب[xxviii] (1996) روش فرا ابتکاری برای حل مسائل چیدمان دوبعدی قطعات منظم مستطیل شکل و نامنظم ارائه کرد. وی مسأله چیدمان را مسأله جایگشتی در نظر گرفته و از الگوریتم ژنتیک برای پیداکردن دنباله‌ای مناسب از قطعات برای جایگذاری و از الگوریتم جایگذاری پایین- چپ برای تبدیل دنبالۀ قطعات به یک چیدمان معتبر استفاده کرد. داگلی و پوشیانُندا[xxix] (1997) از روش دومرحله‌ای براساس الگوریتم شبکه‌های عصبی و الگوریتم ژنتیک برای حل مسأله چیدمان دوبعدی قطعات با اشکال مستطیل شکل استفاده کردند. روش داگلی و پوشیانُندا قادر است چیدمان‌هایی با بازدهی 95% تا 97% تولید کند.
سوک و بینگل[xxx] (2006) دو روش جدید برای حل مسائل چیدمان دوبعدی معرفی کردند. آنان همانند روش جیکوب مسأله چیدمان را مانند مسأله جایگشتی مدل‌سازی کردند و از الگوریتم‌های ژنتیک و انجماد تدریجی برای پیداکردن بهترین دنباله از قطعات و از الگوریتم جایگذاری پایین- چپ- جهشی برای تبدیل دنبالۀ قطعات به چیدمانی معتبر استفاده کردند. لی[xxxi] و همکارانش (2009) روشی مشابه روش سوک و بینگل با استفاده از الگوریتم جایگذاری تنظیم‌کنندۀ ارتفاع و الگوریتم ژنتیک ارائه کردند. وانگ (2010) روشی براساس ترکیب دو الگوریتم فرا ابتکاری ژنتیک و انجماد تدریجی برای حل مسائل چیدمان دوبعدی قطعات منظم ارائه کرد. در این بخش تنها روش‌های ابتکاری و فرا ابتکاری حل مسائل چیدمان منظم دوبعدی تشریح شد. برای مطالعات بیشتر دربارۀ انواع روش‌های ابتکاری و فرا ابتکاری حل مسائل چیدمان مختلف، به مطالعۀ کارگر و پیوندی (1393) مراجعه شود.
در این پژوهش مسأله برش قطعات منظم مستطیل بررسی و حل شده است. ورودی این نوع مسائل، دنباله‌ای محدود از مستطیل‌هایی با ابعاد مشخص (قطعات) است که باید بدون هم‌پوشانی داخل فضایی مستطیل شکل (شئ) به‌عرض مشخص و طول نامحدود جایگذاری شوند. هدف از حل مسأله، یافتن دنباله‌ای از قطعات است که کمترین طول فضای مستطیل شکل را اشغال کنند.
با بررسی روش‌های حل مسائل چیدمان مشاهده می‌شود نوع الگوریتم فرا ابتکاری استفاده‌شده نقش به‌سزایی در دستیابی به جواب بهینه دارد. دراین‌راستا به بررسی کارایی الگوریتم‌های فرا ابتکاری نوظهور در حل این نوع مسائل توجه بسیاری شده است؛ از جملۀ این الگوریتم‌ها، الگوریتم رقابت استعماری[xxxii] است. آتش‌پز و لوکاس، الگوریتم رقابت استعماری را ابداع کرده و در کاربردهای گوناگون توانمندی خود را نسبت به الگوریتم‌های فرا ابتکاری دیگر به اثبات رسانده است ( ابراهیمی و پیوندی، 2013) و (اورتمن[xxxiii]، 2010). در این پژوهش نیز به حل مسأله چیدمان از این روش توجه بسیاری شده است و نتایج حاصله با الگوریتم معمول و پذیرفته‌شده در این نوع مسائل یعنی الگوریتم ژنتیک مقایسه شد. در این پژوهش برای کارایی بهتر الگوریتم‌های فرا ابتکاری، پارامترهای الگوریتم‌های فرا ابتکاری به‌روش تاگوچی تنظیم شده است.
شرح مسأله
مسائل چیدمان شامل پیداکردن آرایشی مناسب از چیدمان مجموعه‌ای محدود از قطعات در یک یا چند شیء مشخص است و هدف رایج این فرایند، به حداکثر رساندن بهره‌برداری و به حداقل رساندن "دورریز" مواد اولیه، در کمترین زمان ممکن است. در فرایند چیدمان باید اطمینان حاصل شود که هیچ هم‌پوشانی بین قطعات وجود ندارد (لینز[xxxiv] و همکاران، 2003).
مجموعه‌ای از چندضلعی‌ها P=(P1, P2,…,Pn) و شئِ مستطیل شکل C=C(W , L) با عرض ثابت W و طول متغیر L را در نظر بگیرید. پایین‌ترین و چپ‌ترین رأس شئ C در نقطۀ مبدأ (0 ، 0) قرار دارد و موقعیت چندضلعی Pi از طریق مختصات نقطۀ مرجع آن Vi=(xi ,yi) نسبت به مبدأ شئ C بیان می‌شود. نقطۀ مرجع یکی از رئوس یا مرکز ثقل چندضلعی است که در این مسأله، پایین‌ترین و چپ‌ترین رأس چندضلعی در نظر گرفته شده است. شکل 1 نمایی از مسأله چیدمان نشان می‌دهد. در این مسأله فرض شده است که قطعات اجازه دوران ندارند.
شکل 1- مدلی از مسأله چیدمان
مسأله چیدمان چندضلعی‌های Pi روی شئ C باتوجه‌به شکل 1 به‌صورت مدل ذیل شرح داده می‌شود:
Minimize L
s.t.
|
(1 ≤ i ≤ n) |
(Pi⊕ Vi) ∩ (Pj⊕ Vj) = ∅ |
|
(1 ≤ i ≤ n) |
(Pi⊕ Vi) ⊆ C(W,L) |
|
(1 ≤ i ≤ n) |
Vi ∈ R2 |
|
|
L ≥ 0 |
منظور از i ترتیب قطعات برای جایگذاری است.
در پژوهش حاضر هدف حداقل‌کردن طول L از شئ به‌کمک یافتن بهترین دنباله از ترتیب قطعات برای جایگذاری روی شئ است؛ به این منظور از الگوریتم فرا ابتکاری رقابت استعماری استفاده می‌شود. این الگوریتم، الگوریتم جستجوی نوین و قدرتمندی است. در این روش فرض می‌شود فضای جستجوی شامل ترتیب‌های مختلف از قطعات برای جایگذاری روی شئ است. الگوریتم فرا ابتکاری استفاده‌شده در طول چند دهۀ اجرا روی فضای جستجو به‌سمت دنباله‌ای همگرا می‌شود که شئ با طول کمتر تولید کند.
الگوریتم‌های فرا ابتکاری
الگوریتم ژنتیک
الگوریتم ژنتیک[xxxv] روشی برای جستجوی تصادفی عددی است که از فرآیند ساده‌شدۀ تکامل طبیعی تقلید می‌کند. الگوریتم روی جمعیتی از پاسخ‌ها عمل کرده و با به کار بردن اصل بقای بهترین و تکامل، جواب‌های بهتر و مناسب‌تر ایجاد می‌کند. جزئیات روش الگوریتم ژنتیک استفاده‌شده در این مقاله، به‌صورت فلوچارت در شکل 2 نشان داده شده است (میشل[xxxvi]، 2005).
شکل 2- فلوچارت الگوریتم ژنتیک
الگوریتم رقابت استعماری
این الگوریتم به فرایند استعمار، به‌عنوان مرحله‌ای از تکامل اجتماعی-سیاسی بشر نگریسته و با مدل‌سازی ریاضی این پدیدۀ تاریخی، از آن به‌عنوان منشأ الهام الگوریتم قدرتمند در زمینۀ بهینه‌سازی بهره می‌گیرد.
فلوچارت الگوریتم رقابت استعماری در شکل 3 نشان داده شده است ( ابراهیمی و پیوندی، 2013).
شکل 3- فلوچارت الگوریتم رقابت استعماری
در ابتدای اجرای الگوریتم، باید کشورها به‌صورت تصادفی تولید شوند. در الگوریتم بهینه‌سازی، هدف یافتن جواب بهینه برحسب متغیرهای مسأله است. در یک مسأله بهینه‌سازی Nvar بعدی، یک کشور آرایه‌ای است که به‌صورت زیر تعریف می‌شود:
|
(1) |
pi(i=1, 2, 3, … Nvar) نشان‌دهندۀ متغیرهای بهینه‌سازی است. بهینه‌سازی بعد از یافتن حداقل مقدار هزینه به پایان خواهد رسید. در این مرحله تعدادی از کشورهای قوی اولیه، استعمارگر در نظر گرفته می‌شوند. باقیماندۀ کشورها مستعمراتی را تشکیل می‌دهند که هرکدام متعلق به یک امپراطوری هستند. چگونگی شکل‌گیری امپراطوری‌های اولیه در شکل 4 نشان داده شده است. مطابق شکل 4 استعمارگران قویتر، مستعمرات بیشتری به خود اختصاص داده‌اند.
شکل 4- استعمارگران اولیه تولیدشده و مستعمرات آنها
امپریالیست‌ها سعی دارند با اعمال سیاست جذب، کشورهای مستعمره را در راستای ابعاد مختلف اجتماعی -سیاسی به خود نزدیک کنند. این بخش از فرایند استعمار در الگوریتم بهینه‌سازی به‌صورت حرکت مستعمرات به‌سمت کشور امپریالیست، مدل شده است. شکل(5-الف) شمای کلی این حرکت را نشان می‌دهد. همان‌گونه‌که در این شکل نشان داده شده است، کشور مستعمره[xxxvii] به‌اندازۀ x واحد در جهت خط واصل مستعمره به استعمارگر[xxxviii] حرکت کرده و به موقعیت جدید کشانده می‌شود.
در این شکل، فاصلۀ میان استعمارگر و مستعمره با d نشان داده شده است. x نیز عددی تصادفی با توزیع یکنواخت (یا هر توزیع مناسب دیگر) است که توزیع x به‌صورت رابطۀ 2 نمایش داده می‌شود.
|
(2) |
در این رابطه، ضریبی بزرگ‌تر از یک و d فاصلۀ بین استعمارگر و مستعمره است. وجود ضریب باعث می‌شود کشور مستعمره در حین حرکت به‌سمت کشور استعمارگر، از جهت‌های مختلف به آن نزدیک شود.
|
الف |
ب |
شکل5- الف: حرکت مستقیم مستعمره به‌سمت استعمارگر مربوطه. ب: حرکت مستعمره به‌سمت استعمارگر با انحراف زاویه‌ای.
در سیاست جذب، حرکت مستعمره به‌سمت استعمارگر مربوطه، لزوماً مستقیم نیست. مستعمره به‌صورت غیرمستقیم، همراه با انحراف به‌سمت استعمارگر مربوطه نزدیک می‌شود. این انحراف احتمالی با افزودن زاویه‌ای تصادفی به مسیر جذب مستعمرات انجام می‌گیرد. شکل(5-ب) این حالت را نشان می‌دهد. بدین منظور به‌جای حرکت به‌اندازۀ x به‌سمت کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، به‌همان میزان ولی با انحراف در مسیر طی می‌کند. حرکت را به‌صورت تصادفی و با توزیع یکنواخت یا هر توزیع دلخواه و مناسب دیگر نیز می‌توان استفاده کرد؛ بنابراین:
|
(3) |
در این رابطه پارامتری دلخواه است که افزایش آن باعث افزایش جستجوی اطراف امپریالیست می‌شود و کاهش آن نیز باعث می‌شود تا مستعمرات تا حد ممکن به بردار واصل مستعمره به استعمارگرِ نزدیک حرکت کنند.
انقلاب، عملیاتی اساسی در الگوریتم و به‌معنای جابجایی تصادفی یک مستعمره به یک موقعیت جدید تصادفی است. انقلاب در الگوریتم از به دام‌افتادن پاسخ‌ها در بهینه‌های محلی جلوگیری و فضای جستجوی بیشتری را فراهم می‌کند.
در حین حرکت مستعمره به‌سمت استعمارگر، ممکن است بعضی از مستعمرات به موقعیت بهتری از استعمارگر برسند (هزینۀ کمتر از هزینۀ استعمارگر). در این حالت جای مستعمره و استعمارگر عوض می‌شود و الگوریتم با موقعیت استعمارگر جدید ادامه می‌یابد.
قدرت یک امپراطوری برابر است با قدرت کشور استعمارگر به‌اضافۀ درصدی از میانگین قدرت مستعمرات آن.
هر امپراطوری که از قدرتش کاسته شود، در جریان رقابت‌های امپریالیستی حذف خواهد شد. بدین‌صورت که یک یا چند مستعمرۀ ضعیف از ضعیف‌ترین امپراطوری‌ها حذف و در تصاحب سایر امپراطوری‌ها در خواهد آمد. لزوماً قوی‌ترین امپراطوری مستعمرات مذکور را تصاحب نخواهد کرد؛ بلکه امپراطوری‌های قویتر، احتمال تصاحب بیشتری دارند. برای مدل‌کردن این واقعیت، فرض می‌شود امپراطوریِ در حال حذف، ضعیف‌ترین امپراطوری موجود است. بدین ترتیب، برای تصاحب مستعمرات ضعیف، رقابتی میان کلیۀ امپراطوری‌ها ایجاد می‌شود. شکل 6 استراتژی رقابت ذکرشده را نشان می‌دهد.
شکل6- رقابت استعماری
الگوریتم رقابت استعماری گسسته
الگوریتم اولیه که آتش‌پز و لوکاس[xxxix] (2007) ارائه کرده‌اند قابلیت اجرا روی مسائل پیوسته را دارد. در مسائل بهینه‌چینی قطعات هدف یافتن دنباله‌ای از ترتیب قطعات برای تولید پاسخ بهینه است؛ بنابراین مسأله از انواع مسائل جایگشتی است. ازآنجایی‌که مسائل جایگشتی از نمونۀ بارز مسائل گسسته هستند، استفاده از الگوریتم رقابت استعماری معمول برای حل این‌گونه مسائل امکان‌پذیر نیست. راهکار مناسب برای حل این موضوع تبدیل متغییرهای گسسته به متغییرهای پیوسته در طول اجرای الگوریتم است. در این راهکار فرض می‌شود هدف بهینه‌سازی مسأله پیوسته است و تمام عملیات برای مسأله پیوسته انجام می‌شوند؛ بنابراین الگوریتم رقابت استعماری روی مجموعه‌ای از متغییرهای پیوسته عمل و متغیرهای بهینه‌سازی را تنها در مرحلۀ ارسال به تابع هزینه، گسسته می‌کند. برای این منظور استفاده از یک تابع واسط در مرحلۀ ارسال متغییرها به تابع هزینه لازم است. تابع واسط متغیر پیوسته را هنگام ارزیابی میزان هزینه، گسسته و به تابع هزینۀ مسأله بهینه‌سازی ارسال می‌کند. سپس این مقدار هزینه به الگوریتم رقابت استعماری برای ادامۀ عملیات برگردانده می‌شود. در اتمام اجرای الگوریتم رقابت استعماری مقادیر پاسخ‌های بهینۀ تولیدشده در الگوریتم، پیوسته هستند. این مقادیر پیوسته با تابع واسط، گسسته و به‌عنوان جواب اصلی مسأله گسسته نمایش داده می‌شوند.
در این مقاله برای حل مسأله بهینه‌چینی قطعات با استفاده از الگوریتم رقابت استعماری، ابتدا برای تولید کشورها به تعداد N_var اعداد حقیقی تصادفی بین بازۀ صفر تا یک تولید و به تعداد کشور مورد نیاز تکرار می‌شوند. سپس از کشورهای تولیدشده برای استفاده در الگوریتم رقابت استعماری استفاده می‌شود.
در مرحلۀ ارسال متغییرها به تابع هزینه، از مکان مرتب‌شدۀ (از کوچک به بزرگ و یا برعکس) هر کشور به‌عنوان مقادیر آن برای ارزیابی قدرت هر کشور استفاده می‌شود (تابع واسط پیشنهادی برای تبدیل دنبالۀ اعداد پیوسته به دنبالۀ اعداد گسسته).
در واقع با استفاده از این روش الگوریتم رقابت استعماری روی اعداد حقیقی اعمال می‌شود؛ ولی هنگام ارزیابی از مکان مرتب‌شدۀ اعداد حقیقی داخل هر آرایه استفاده می‌شود که خصوصیات لازم در مسائل گسسته مانند عدد طبیعی‌بودن و تکرارناپذیری را دارذ. شکل 7 فلوچارت گسسته‌سازی متغییرها و انتقال آنها به تابع هزینه را نشان می‌دهد.
شکل 7- فلوچارت گسسته‌سازی متغییرها قبل از انتقال به تابع هزینه
شکل 8 مراحل تبدیل دنبالۀ اعداد حقیقی به دنبالۀ قطعات (توسط تابع واسط) را نشان می‌دهد.
شکل8 - مراحل تبدیل دنباله اعداد حقیقی به دنباله قطعات
الگوریتم‌های ابتکاری جایگذاری
برای محاسبۀ تابع هدف در طول اجرای الگوریتم جستجوی فرا ابتکاری، لازم است مجموعۀ قطعات مطابق ترتیب یافت‌شده با الگوریتم جایگذاری روی شئ جایگذاری شوند و بازدهی شئ به‌عنوان تابع هدف محاسبه شود.
همان‌طورکه در شکل 9 مشاهده می‌شود، مسأله چیدمان شامل جایگذاری N قطعه با عرض و طول درفضای مستطیل شکل به‌عرض است. درصورتی‌که فضای طولی اشغال‌شده در چیدمان برابر L باشد، بازدهی چیدمان از رابطۀ 4 محاسبه می‌شود.
|
(4) |
شکل 9- نمونه‌ای از چیدمان i قطعه در عرض W
روش‌های زیادی برای جایگذاری قطعات پیشنهاد شده است. این روش‌ها شامل، روش‌های الگوریتم جایگذاری پایین- چپ، الگوریتم پایین- چپ- جاذبه‌دار، الگوریتم پایین- چپ- جهشی، الگوریتم پایین-چپ- توسعه‌یافته و الگوریتم بهترین تناسب هستند.
در این پژوهش، ابتدا بین عملکرد و سرعت اجرای پنج الگوریتم ابتکاری جایگذاری پایین- چپ (BL)، الگوریتم پایین- چپ- جاذبه‌دار (BLLT)، الگوریتم پایین- چپ- جهشی (BLF)، الگوریتم پایین-چپ- توسعه یافته (BLD) و الگوریتم بهترین تناسب (BF) ، مقایسه‌ای انجام شده است. سپس الگوریتم جایگذاری بهینه برای ترکیب با الگوریتم‌های فرا ابتکاری انتخاب شده‌اند.
تنظیم پارامترها
انتخاب مناسب پارامترها نقش بسیار مهمی در کارایی روش‌های فرا ابتکاری دارد. در این پژوهش، برای تعیین سطح مناسب هر پارامتر، از روش تاگوچی استفاده شده است (تاگوچی[xl] و همکاران، 2005).
این روش بر پایة حداکثرکردن معیار عملکرد ( که نرخ سیگنال به نویز نامیده می شود)، برای تعیین سطوح بهینة فاکتورهای مؤثر در محاسبات است.
به‌طور کلی روش تاگوچی به‌صورت زیر است:
• برای هر آزمایش نرخ سیگنال به نویز و جدول آنالیز واریانس مشخصه‌های کیفیت آن محاسبه می‌شود.
• برای فاکتورهایی که اثر مهمی بر نرخ سیگنال به نویز دارند، سطحی که نرخ سیگنال به نویز بالاتری دارد به‌منزلة سطح بهینة فاکتور انتخاب می‌شود.
• فاکتوری که اثر مهمی بر نرخ سیگنال به نویز ندارد، اما بر میانگین پاسخ اثر مهمی دارد، سطح با مقدار هدف بهتر انتخاب می‌شود.
• برای فاکتورهایی که اثر مهمی بر دو نرخ سیگنال به نویز و میانگین پاسخ ندارند، سطح با مقیاس اقتصادی به‌منزلة مقدار بهتر برای الگوریتم در نظر گرفته می‌شود.
براساس این روش زمانی که مسأله از نوع بهینه‌سازی و پاسخِ تا حد ممکن کوچک مد‌نظر است از رابطۀ 5 استفاده خواهد شد. در این رابطه منظور از S سیگنال و N مقادیر نویز در نظر گرفته شده است.
|
(5) |
آزمایشات برای تنظیم پارامترهای الگوریتم رقابت استعماری و ژنتیک در سه سطح انجام شده است. جدول‌های 1 و 2 مقدار پارامترهای الگوریتم رقابت استعماری و ژنتیک را نشان می‌دهند.
جدول 1- پارامترهای الگوریتم رقابت استعماری و سطوح آن پارامتر
|
پارامتر |
سطح |
||
|
1 |
2 |
3 |
|
|
تعداد کشورها (A) |
500 |
750 |
1000 |
|
تعداد امپراطوری (B) |
50 |
75 |
100 |
|
تعداد دهه‌ها (C) |
50 |
75 |
100 |
|
ضریب جذب (D) |
5/0 |
1 |
2 |
|
ضریب انحراف (E) |
3/0 |
5/0 |
7/0 |
|
نرخ انقلاب (F) |
2/0 |
3/0 |
4/0 |
|
نرخ مشارکت (G) |
1/0 |
15/0 |
2/0 |
جدول 2- پارامترهای الگوریتم ژنتیک و سطوح آن پارامتر
|
پارامتر |
سطح |
||
|
1 |
2 |
3 |
|
|
جمعیت اولیه |
500 |
750 |
1000 |
|
تعداد نسل‌ها |
50 |
75 |
100 |
|
نرخ ترکیب |
6/0 |
7/0 |
8/0 |
|
نرخ جهش |
2/0 |
3/0 |
4/0 |
مطابق تعداد پارامترها و سطوح مختلف آنها، طرح تاگوچی L27 برای تنظیم پارامترهای الگوریتم رقابت استعماری و طرح تاگوچی L9 برای تنظیم پارامترهای الگوریتم ژنتیک استفاده شده است. مقادیر نرخ S/N برای الگوریتم رقابت استعماری در شکل 10 نشان داده شده است.
شکل 10- میانگین نرخ S/N در هر سطح برای تنظیم پارامترهای الگوریتم رقابت استعماری
نتایج به‌دست‌آمده به‌روش تاگوچی نشان می‌دهد، سطوح 3، 3، 2، 3، 1، 3 و 3 به‌ترتیب بهترین سطوح برای پارامترهای تعداد کشورها، تعداد امپراطوری، تعداد دهه‌ها، ضریب جذب، ضریب انحراف، نرخ انقلاب و نرخ مشارکت الگوریتم رقابت استعماری و سطوح 3، 3، 2 و 2 به‌ترتیب بهترین سطوح برای پارامترهای جمعیت اولیه، تعداد نسل‌ها، نرخ ترکیب و نرخ جهش الگوریتم ژنتیک هستند.
نتایج پژوهش
در این پژوهش ابتدا عملکرد سه الگوریتم جایگذاری (پایین- چپ، الگوریتم پایین- چپ- جاذبه‌دار، الگوریتم پایین- چپ- جهشی) با یکدیگر مقایسه، سپس الگوریتم جایگذاری مناسب انتخاب و با الگوریتم رقابت استعماری و ژنتیک ترکیب شده‌اند. برای پیاده‌سازی الگوریتم رقابت استعماری و الگوریتم ژنتیک از برنامه‌نویسی تحت زبان برنامه‌نویسی متلب نسخه 2014a استفاده شد. برای ارزیابی عملکرد روش پیشنهادی از 22 مجموعه داده معیار استفاده شده است که شامل 17 تا 97 قطعه و قابل چیدمان به‌صورت 100 درصد هستند (هوپر، 2000). جدول 3 مشخصات 22 مجموعه داده‌های معیار را نشان می‌دهد.
جدول 3- مشخصات مجموعه داده‌ها
|
نام مجموعه داده معیار |
تعداد |
سایز بهینه شئ |
مرجع |
|
J1 |
25 |
20*40 |
(جیکوب، 1996) |
|
J2 |
50 |
20*40 |
(جیکوب، 1996) |
|
T1a, T1b, T1c, T1d, T1e |
17 |
200*200 |
(هوپر و تورتون، 2001) |
|
T2a, T2b, T2c, T2d, T2e |
25 |
200*200 |
(هوپر و تورتون، 2001) |
|
T3a, T3b, T3c, |
39 |
200*200 |
(هوپر و تورتون، 2001) |
|
T4a, T4b, T4c, |
49 |
200*200 |
(هوپر و تورتون، 2001) |
|
T5a, T5b, |
72 |
200*200 |
(هوپر و تورتون، 2001) |
|
T6a, T6b, |
97 |
200*200 |
(هوپر و تورتون، 2001) |
برای مقایسۀ عملکرد الگوریتم‌های جایگذاری نام برده شده در بخش (4) از لحاظ سرعت و قابلیت در تولید چیدمان بهینه، از مجموعه داده T1a استفاده شد. به این منظور تمام جایگشت‌های ممکن مجموعه داده T1a که شامل !17 حالت است با استفاده از پنج الگوریتم جایگذاری نام برده شده به چیدمان معتبر تبدیل شدند و مدت زمان اجرا و بازدهی چیدمان تولیدی هریک از الگوریتم‌های ابتکاری با یکدیگر مقایسه شدند. سرعت و بازدهی چیدمان‌های حاصل در جدول 4 گزارش شده است.
جدول 4- نتایج اجرای الگوریتم‌های ابتکاری جایگذاری در چیدمان مجموعه داده T6a،
|
الگوریت ابتکاری جاگذاری |
میانگین زمان هرجایگذاری (ثانیه) |
میانگین بازدهی چیدمان |
بهترین بازدهی چیدمان |
انحراف معیار |
|
BL |
918/0 |
72/48 |
75/93 |
52/9 |
|
BLLT |
017/1 |
77/60 |
100 |
47/6 |
|
BLF |
119/2 |
08/65 |
100 |
12/10 |
|
BLD |
045/1 |
85/53 |
75/93 |
39/6 |
|
BF |
830/2 |
87/47 |
45/84 |
50/11 |
نتایج نشان می‌دهد الگوریتم پایین- چپ- جهشی قادر است چیدمان‌هایی با بازدهی بالایی تولید کند؛ اما سرعت اجرای این الگوریتم پایین است. همچنین نتایج نشان می‌دهد علی‌رغم سرعت بالای الگوریتم پایین-چپ و پایین-چپ توسعه‌یافته، موفق به تولید چیدمان با بازدهی کامل برای این مجموعه داده نشده‌اند. همچنین میانگین بازدهی چیدمان‌های حاصل از آنها نسبت به الگوریتم پایین- چپ-جهشی و الگوریتم پایین- چپ- جاذبه‌دار، پایین است. نتایج حاصل از اجرای الگوریتم بهترین تناسب از هر دو لحاظ سرعت اجرا و بازدهی چیدمان حاصل قابل قبول نیست. این موضوع نشان می‌دهد این الگوریتم برای استفاده در این نوع چیدمان مناسب نیست. از مقایسۀ نتایج نمایش‌داده‌شده در جدول 4 نتیجه می‌شود الگوریتم جایگذاری پایین- چپ- جاذبه‌دار قادر است با سرعت مناسب جواب‌های قابل قبولی تولید کند. در پژوهش دیگری که نویسندگان این پژوهش انجام داده‌اند نیز مناسب‌بودن الگوریتم جایگذاری پایین- چپ- جاذبه‌دار به اثبات رسیده است (کارگر و پیوندی، 1393)؛ بنابراین در این پژوهش برای تبدیل دنبالۀ قطعات به چیدمان معتبر از الگوریتم پایین-چپ-جاذبه‌دار استفاده می‌شود. شکل 11 چیدمان دنباله‌ای از قطعات مستطیلی با جایگشت (۲، ۶، ۴، ۷، ۳، ۰، ۱، ۵)، توسط الگوریتم جایگذاری پایین- چپ- جاذبه‌دار را نشان می‌دهد.
شکل 11- جایگذاری دنباله‌ای از قطعات مستطیلی با جایگشت (۲، ۶، ۴، ۷، ۳، ۰، ۱، ۵) توسط الگوریتم جایگذاری پایین- چپ- جاذبه‌دار،
همان‌طورکه بیان شد در این پژوهش برای ارزیابی عملکرد الگوریتم رقابت استعماری در حل مسائل چیدمان، از مقایسۀ آن با الگوریتم ژنتیک استفاده شده است. الگوریتم ژنتیک، الگوریتم معمول در حل این‌گونه مسائل است. چیدمان هریک از 22 مجموعه داده معیار 20 مرتبه با هریک از دو الگوریتم فرا ابتکاری آزمون شده‌اند. بهترین نتایج به‌دست‌آمده با هریک از الگوریتم‌های فرا ابتکاری برای 22 مجموعه داده‌ها در جدول 5 نمایش داده شده است. حداکثر زمان اجرا برای 22 مجموعه داده معیار با هریک از الگوریتم‌های فرا ابتکاری، 15 دقیقه بوده است.
از مقایسۀ نتایج جدول 4 مشاهده می‌شود الگوریتم رقابت استعماری به چیدمان با بازدهی 100%، 4 مجموعه داده دست یافته است و درنهایت 12 چیدمان با بازدهی بالاتر نسبت به الگوریتم ژنتیک تولید کرده است. همچینین مشاهده می‌شود میانگین بازدهی چیدمان‌های تولیدشده با الگوریتم رقابت استعماری 12/2 درصد بالاتر از میانگین بازدهی چیدمان‌های تولید شده با الگوریتم ژنتیک است. شکل 12، دو نمونه چیدمان‌های بهینۀ یافت‌شده با الگوریتم رقابت استعماری را نشان می‌دهد.
جدول 5- بهترین نتایج به‌دست‌آمده با هریک از الگوریتم‌های فرا ابتکاری برای 22 مجموعه داده‌ها معیار
|
نام مجموعۀ داده معیار |
الگوریتم فرا ابتکاری |
|
|
الگوریتم رقابت استعماری |
الگوریتم ژنتیک |
|
|
J1 |
100 |
75/93 |
|
J2 |
75/93 |
75/93 |
|
T1a |
09/95 |
78/94 |
|
T1b |
83/97 |
45/94 |
|
T1c |
100 |
32/95 |
|
T1d |
67/95 |
95 |
|
T1e |
100 |
60/95 |
|
T2a |
13/95 |
69/95 |
|
T2b |
43/95 |
45/93 |
|
T2c |
90/95 |
63/93 |
|
T2d |
100 |
49/93 |
|
T2e |
32/94 |
32/93 |
|
T3a |
05/91 |
16/93 |
|
T3b |
89/95 |
89/93 |
|
T3c |
78/95 |
63/92 |
|
T4a |
59/91 |
32/91 |
|
T4b |
96/92 |
59/91 |
|
T4c |
88/91 |
45/90 |
|
T5a |
78/92 |
28/89 |
|
T5b |
98/91 |
03/92 |
|
T6a |
21/92 |
15/90 |
|
T6b |
02/91 |
88/91 |
|
میانگین |
23/95 |
11/93 |
|
J1 (length = 15, util. = 100%) |
T1e (length = 200, util. = 100%) |
شکل 12- چیدمان بهینۀ یافت‌شده با الگوریتم رقابت استعماری
برای مقایسۀ دقیق‌تر عملکرد الگوریتم رقابت استعماری و الگوریتم ژنتیک در حل این نوع مسائل چیدمان، از آزمون آماری ANOVA برای بررسی معناداربودن تفاوت نتایج حاصل از این دو الگوریتم استفاده شده است. جدول 6 خلاصۀ این نتایج را نشان می‌دهد.
جدول 6- خلاصۀ نتایج آزمون ANOVA
|
منبع تغییرات |
مجموع مربعات |
درجۀ آزادی |
میانگین مربعات |
نسبت F |
سطح معنی‌دار |
|
بین‌گروهی |
101/55 |
2 |
551/27 |
243/5 |
008/0 |
|
درون‌گروهی |
046/331 |
63 |
255/5 |
- |
- |
|
کل |
147/386 |
65 |
- |
- |
- |
همان‌طورکه جدول 5 نشان می‌دهد تفاوت نتایج حاصل از دو الگوریتم فرا ابتکاری معنادار است. در روش حل مسائل چیدمان علاوه بر قابلیت روش در دستیابی به جواب بهینه، مدت زمان حل مسأله نیز پارامتر با اهمیت در ارزیابی روش است. به‌دلیل‌آنکه نوع نرم‌افزار و نحوۀ کدنویسی برنامه تأثیر زیادی در میانگین زمان اجرای الگوریتم دارد، پارامتر میانگین زمان اجرای الگوریتم، پارامتر مناسبی برای مقایسه نیست؛ از این‌رو برای بررسی دقیق‌تر هر الگوریتم پارامتر تعداد فراخوانی تابع هدف نیز در نظر گرفته شده است. در واقع زمان‌برترین قسمت هر الگوریتم بخش ارزیابی مقدار تابع هدف است و از مقدار آن زمان لازم الگوریتم، مستقل از مشخصات رایانه تقریب زده می‌شود. درعین‌حال با هر بار فراخوانیِ تابع هدف، جواب یافته‌شده با الگوریتم ارزیابی می‌شود؛ بنابراین الگوریتمی قویتر است که با تعداد فرخوانی کمترِ تابع هدف، نتایج بهتری ارائه کند؛ برای مثال شکل 13 تغییرات تعداد فراخوانی تابع هدف (NFE) در طول نسل برای بهترین جواب الگوریتم‌های ژنتیک و الگوریتم رقابت استعماری را برای مجموعه قطعاتJ1 و J2 نشان می‌دهد.
|
الف |
ب |
شکل 13- تغییرات تعداد فراخوانی تابع هدف در طول نسل برای بهترین جواب با الگوریتم‌های ژنتیک و رقابت استعماری برای الف) مجموعۀ قطعات J1، ب)مجموعۀ قطعات J2،
همان‌طورکه از نمودارهای شکل 13 مشخص است، تعداد فراخوانی تابع هدف با الگوریتم ژنتیک در چیدمان هر دو مجموعه قطعات بیشتر از الگوریتم رقابت استعماری است. این موضوع به‌منزلۀ زمان بیشتر اجرای الگوریتم ژنتیک است. همچنین الگوریتم ژنتیک با وجود زمان اجرای بیشتر چیدمان‌هایی با میانگین بازدهی کمتر تولید کرده است؛ بنابراین الگوریتم رقابت استعماری جایگزین خوبی برای الگوریتم ژنتیک در حل مسائل چیدمان قطعات مستطیل است.
نتیجه‌گیری
در این مقاله برای حل مسائل برش قطعات منظم مستطیل شکل، روش فرا ابتکاری براساس الگوریتم نوظهور رقابت استعماری ارائه شد. کارایی روش پیشنهادی با استفاده از 22 مجموعه داده معیار ارزیابی و نتایج حاصل با نتایج الگوریتم ژنتیک مقایسه شد.
عملکرد دو روش فرا ابتکاری براساس دو فاکتور قابلیت روش در دستیابی به چیدمانی با بازدهی بالاتر و سرعت روش ارزیابی شده است.
براساس آنالیز آماری نتایج حاصل از اجرای روش‌های فرا ابتکاری مشاهده شد نتایج حاصل از ICA تفاوت معناداری با نتایج حاصل از GA دارد و الگوریتم ICA قادر به دستیابی به چیدمان‌هایی با بازدهی بالاتر است. همچنین الگوریتم ICA به چیدمان صد در صد 4 نمونه از 22 مجموعه داده دست یافته است. الگوریتم رقابت استعماری قادر است با تعداد NFE بسیار کمتر به جواب مشابه با الگوریتم ژنتیک دست یابد. ازآنجاکه تعداد NFE کمتر در طول اجرا الگوریتم فرا ابتکاری نشان‌دهندۀ سرعت بیشتر اجرای الگوریتم است، الگوریتم رقابت استعماری روشی سریع‌تر در حل این‌گونه مسائل جایگشتی است.
درنهایت نتیجه می‌شود الگوریتم ICA روشی کارامدتر نسبت به الگوریتم ژنتیک در حل مسائل چیدمان است. در حل مسائل چیدمان با استفاده از روش‌های فرا ابتکاری، تعداد بهینه‌های محلی زیاد باعث سردرگمی الگوریتم در پیداکردن مسیر درست به‌سمت بهینه مطلق می‌شود. راهکاری که برای حل این مشکل مناسب دیده می‌شود، تأثیردادن پارامتر دیگری به‌غیر از طول چیدمان در تابع هدف است. به این‌گونه که تابع هدف دو چیدمان با طولی یکسان از مجموعۀ قطعات یکسان، از یکدیگر متمایز هستند. مناسب دیده می‌شود در پژوهش‌های آینده این موضوع بررسی شود.
[i] Hopper and Turton
[ii] Dyckhoff
[iii] Burke
[iv] Liu and Teng
[v] Chazelle
[vi] Oliveira and Ferreira
[vii] Leung
[viii] Ozcan
[ix] Falkenauer and Delchambre
[x] Hwang
[xi] Runarsson
[xii] Dagli and Poshyanonda
[xiii] Valenzuela and Wang
[xiv] Bortfeldt
[xv] Hifi and Hallah
[xvi] Dowsland
[xvii] Lai and Chan
[xviii] Faina
[xix] Beisiegel
[xx] Lodi
[xxi] Wei
[xxii] Alvarez and Parreno
[xxiii] Pureza and Morabito
[xxiv] Shin and Kita
[xxv] Wang
[xxvi] Amaro and Pinheiro
[xxvii] Junior
[xxviii] Jakobs
[xxix] Poshyananda
[xxx] Soke and Bingul
[xxxi] Li
[xxxii] Imperialist Competitive Algorithm – ICA
[xxxiii] Ortmann
[xxxiv] Lins
[xxxv] Genetic Algorithm - GA
[xxxvi] Micell
[xxxvii] Colony
[xxxviii] Imperialist
[xxxix] Lucas
[xl] Taguchi
)