بخشی از مقاله
چکیده
چیدمان اشیاء در رشته کامپیوتر یکی از مباحث مهم در سال های اخیر بوده است. بعنوان مثال چیدمان وسایل خانه، چیدمان در فروشگاه های زنجیرهای، چیدمان بسته بندی کالا در صنایع، چیدمان در صنعت حمل و نقل نیاز به روشهای کامپیوتری در زمینه بهینه سازی دارد. در این روش های بهینه، سرعت عمل همراه با دقت در چیدمان مورد نظر است.در این پژوهش ما یک چیدمان بهینه 3بعدی در کانتینر ها را به نحوی انجام دادیم که اشیاء متمایز کنار هم قرار نگیرند. لذا به هر جعبه یک رنگ اختصاص دادیم. در نتیجه اشیاء متمایز همرنگ بوده و نباید از لحاظ سطر و ستون و قطر کنار هم قرار گیرند. بعلاوه فاکتور وزن را برای جعبه ها نیز ملحوظ کردیم به طوریکه تعادل وزن در کانتینر برقرار باشد.با استفاده از فاکتور رنگ و وزن از الگوریتم ژنتیک استفاده کردیم. با استفاده از این الگوریتم، توانستیم در چیدمان رنگ به موفقیت %90 و در وزن به %49 برسیم.
کلمات کلیدی: الگوریتم ژنتیک، چیدمان اشیاء، رنگ، وزن، هوش جمعی
مقدمه:
مسئله چیدمان در تمامی عرصه ها یک مسئله بسیار مهم است. چیدمان جعبه ها در کانتینرها، چیدمان اسباب منزل، چیدمان اشیاء در هایپر مارکت ها، چیدمان در بردهای الکترونیکی، چیدمان جعبه ها در انبارها ، چیدمان وسایل در چمدانهای مسافرتی و غیره. اگر در هر یک از موارد ذکر شده چیدمان به درستی و اصولی انجام نشود دچار مشکل خواهیم شد. بنابراین در هر نوع از چیدمان سعی بر آن است که کار را به طور اصولی انجام دهیم. چیدمان در برخی جاها از اهمیت ویژه ای برخوردار است و این مسئله باعث شده تا سیستماتیک برخورد کنیم. به عنوان مثال چیدمان اشیاء در کارخانجات مسئلهدارتر می شود به لحاظ مسائل امنیتی و مالی. بنابراین با پیشرفت علم سعی شده این مشکل را به صورت علمی رفع نماییم. در گذشته این کار به صورت دستی انجام می شده که گاهی با کاهش دقت و صرف وقت و هزینه زیاد همراه بوده و نیاز به نیروی انسانی را دوچندان میکرده است. امروزه با تکنولوژی جدید ایجاد شده به روش اتوماتیک و ماشینی به حل اینگونه مسائل پرداخته ایم.
یکی از روش های چیدمان اشیاء، رنگ آمیزی می باشد که می توان با رنگ اشیاء را از هم تفکیک کرد. حال اشیاء متمایز و اشیائی که قرار است در کنار هم قرار نگیرند را هم رنگ انتخاب می کنیم.مسئله چیدمان 3بعدی با استفاده از اختصاص رنگ به جعبه ها در مورد چگونگی رنگ آمیزی و نحوه قرار گرفتن جعبه های هم اندازه کنار هم با رعایت تعادل وزنی می باشد به طوری که هیچ دو جعبه کنار هم از لحاظ سطر و ستون و قطر همرنگ نباشند و همچنین تعادل وزن در جعبه ها رعایت شود. رنگ آمیزی 3بعدی شکل تعمیم یافته ای از مسئله بسته بندی اشیاء با در نظر گرفتن محدودیت رنگ می باشد.از این خصوصیت رنگ به عنوان جنبه تزیینی در بسیاری از محصولات صنعتی، کاربردی و هنرهای سنتی مثل فرش، گلیم ، پارچه ، طراحی و دوخت لباس، معماری و شهرسازی بهره می بردند.[4]
مسئله رنگ آمیزی گراف یک مسئله بهینه سازی است که اکثر مسائل علوم کامپیوتر و ریاضیات را شامل میشود.[5]رنگ آمیزی گراف ازاوایل دهه 70 به عنوان یک مسئله الگوریتمی مورد بررسی قرار گرفته است. مساله رنگ آمیزی گراف عبارت است از انتصاب k رنگ به رئوس یک گراف به صورتی که هیچ دو راس مجاور در گراف دارای رنگ یکسانی نباشند. کمترین تعداد رنگی که بتوانبا آن یک گراف را رنگ آمیزی کرد، عدد رنگی گراف نامیده میشود. یافتن عدد رنگی در مساله رنگ آمیزی گراف از جمله مسائل NP-Hardمی باشد.[6]رنگ آمیزی یک نقشه با حداقل تعداد رنگ می باشد، به طوری که هیچ دو شهر مجاور نقشه، دارای رنگ یکسان نباشند. از آنجا که جغرافیای یک نقشه را می توان به شکل یک گراف معادل ، در نظرگرفت، در حالات خاص ،می توان روش های موجود در تئوری گراف ها را برای آن گسترش داد.[7]
در عین حال، بسیاری از روش های سنتی موجود در هوش مصنوعی، برای حل این مسئله، به کار گرفته شده است.[8,9] با توجه به اینکه مسئله رنگ آمیزی گراف، دارای پیچیدگی NP-hard می باشد[10,11]، توانایی روشهای مذکور با ازیاد تعداد گره ها رو به کاهش می رود. ظاهرا در حل مسائل NP-hard، استفاده از روش های هوشمندتری چون شبکه های عصبی و الگوریتم های ژنتیک، می تواند سودمند باشد.[12] که برای بسیاری از مسائل از این دست کارایی این روش ها، نشان داده شده است .[13,14,15] مسئله رنگ آمیزی گراف نیز توسط الگوریتم ژنتیک و الگوریتم های تکاملی مختلفی مورد بررسی قرار گرفته و راه حل هایی نیز برای آن ارائه شده است.[16,17]رنگ آمیزی دو بعدی شطرنجی به ابعاد m - m*n تعداد سطرهاو n تعداد ستون ها - به روش رنگ آمیزی گراف، با شرط هم رنگ نبودن همسایه ها، یکی از کارهایی بوده که در گذشته به آن پرداخته شده بود.
اگر دو مربع همسایه در همان سطر یا ستون باشند و هیچ مربعی بین آن ها نباشد، دو مربع همسایه دارای رنگ های مختلفی بودند.[18]برخی محققان روش های دقیقی توسعه دادهاند که مسائل 2 بعدی و 1 بعدی با اندازه متوسط را به صورت بهینه حل می کند، مانند مدل های برنامه ریزی پویا و خطی مورد استفاده قرار گرفته است.[19]بارگیری درکانتینرها را می توان به عنوان بسته بندی جعبه در نظر گرفت که در آن تعدادی جعبه باید در یک کانتینر قرار گیرد. مساله کلاسیک که مساله پالت معروف است تنها به جعبه های مشابه می پردازدکه برای آن یک الگوریتم دقیق ارائه داده است.[20]یکی از روش های رنگ آمیزی به وسیله کامپیوتر، استفاده از الگوریتم ژنتیک است که تنها در صفحات 2بعدی انجام شده است. ما در این تحقیق قصد داریم رنگ آمیزی را در محیط 3بعدی اجرا کنیم.
رنگ آمیزی 3 بعدی را می توان شاخه ای از بسته بندی 3بعدی در نظر گرفت که در آن جعبه ها هم اندازه هستند و با استفاده از رنگ می توان جعبه ها را از هم جدا کرد. تخصیص محل به اشیاء با رنگ های مختلف - تعداد رنگ ها می تواند نامحدود باشد - از جمله مشکلات در بسته بندی اشیاء دانسته شده است.[22]در این جا یک روش جدید با استفاده از الگوریتم ژنتیک برمبنای کلید تصادفی برای مسئله بسته بندی 2بعدی و 3بعدی ارائه شد. در این روش از بیشترین فضای ارائه شده برای مدیریت فضای خالی در جعبه ها استفاده میشود.[23]مسئله بسته بندی 2بعدی و 3بعدی می تواند دارای محدودیت هایی باشد که ما در اینجا رنگ آمیزی را با محدودیت را در نظر گرفته ایم بدین گونه که جعبه های متمایز را همرنگ در نظر گرفته و سعی داریم که هم رنگ ها کنار هم قرار نگیرند و نیز یک محدودیت دیگری هم داریم و آن این است که تعادل وزنی در جعبه ها رعایت شود.
روش پیشنهادی
ابتدا الگوریتم ژنتیک را به طور کامل بیان کرده و به بخش های آن می پردازیم . سپس به شرح کامل الگوریتم استفاده شده در برنامه خواهیم پرداخت. به طور کلی، الگوریتمهای ژنتیکی از اجزاء زیر تشکیل میشوند:
کروموزوم
در الگوریتمهای ژنتیکی، هر کروموزوم نشان دهنده یک نقطه در فضای جستجو و یک راه حل ممکن برای مسئله مورد نظر است.
جمعیت1
مجموعه ای از کروموزوم ها یک جمعیت را تشکیل می دهند. با تاثیر عملگرهای ژنتیکی بر روی هر جمعیت، جمعیت جدیدی با همان تعداد کروموزوم تشکیل می شود.
تابع تناسب2
به منظور حل هر مسئله با استفاده از الگوریتم های ژنتیکی، ابتدا باید یک تابع تناسب - برازندگی - برای آن مسئله ابداع شود. برای هر کروموزوم، این تابع عددی غیر منفی را برمی گرداند که نشان دهنده شایستگی یا توانایی فردی آن کروموزوم است.
عملگرهای الگوریتم ژنتیک
در الگوریتمهای ژنتیکی، در طی مرحله تولید مثل3 ازعملگرهای ژنتیکی استفاده می شود. با تاثیر این عملگرها بر روی یک جمعیت، نسل4 بعدی آن جمعیت تولید می شود. عملگرهای انتخاب5 ، آمیزش6 و جهش13معمولًا بیشترین کاربرد را در الگوریتمهای ژنتیکی دارند.
راه حل ارائه شده
در الگوریتم پیشنهادی با استفاده از ژنتیک تصادفی سعی بر بهینه نمودن تابع تناسب الگوریتم و رسیدن به چیدمان مطلوب، با توزیع رنگ مناسب و همچنین رعایت توازن وزنی جعبه ها شده است که در ادامه بخش های مختلف آن را شرح می دهیم.
ساختار کروموزوم
برای هر پیاده سا زی الگوریتم ژنتیک، نخستین گام نگاشت خصوصیات ویژه راه حل در قالب یک رشته کروموزوم است. هر کروموزوم از ترکیبی از ژن ها ساخته شده است. این ژن ها می تواند مجموعه ای از اعداد دودویی، اعداد حقیقی، اعداد طبیعی، نمادها، یا ماتریس ها باشد.
جمعیت اولیه
