ضرورت الگورتیم های کامپیوتری در مسائل بهینه سازی

شیما شفیعی- وجود مسائل پیچیده علمی منجر می‌شود تا سراغ روش‌های بهینـه‌سـازی رفتـه و مسائل بسیاری از جمله مسائل پر کاربرد بهینه سازی را به وسیله آن‌ها حل کرده و در واقع با توجه به زمانبر بودن و پیچیدگی روش‌های دقیق از روش‌هـای بهینـه‌سـازی هوشمند استفاده می‌شود. تاکنون روش‌های بهینه‌سازی متعددی معرفی شده‌اند کـه از مهـم‌تـرن آن‌هـا می‌توان به الگوریتم‌های الگـوریتم بهینه‌سازی ازدحام ذرات ، الگوریتم ژنتیک اشاره نمود.بارزترین انواع مسائل بهینه‌سازی عبارتند از:
الف)مسائل بدون محدودیت ب)مسائل اجباری ج)مسائل ترکیبی مانند مسائل چیدمان بسته‌ها .
در حل این مسئله‌ی پر کاربرد بهینه سازی ترکیبی ، دو گروه از الگوریتم‌ها به کار گرفته می‌شوند. دسته‌ی اول الگوریتم‌های دقیق هستند که جواب بهینه مسئله را برای هر اندازه ورودی پیدا می‌کنند. در این دسته از الگوریتم‌ها، زمان اجرای الگوریتم به اندازه‌ی نمونه مسئله وابسته است و با افزایش اندازه‌ی نمونه، زمان اجرای الگوریتم به صورت نمایی افزایش می‌یابد. که در واقع همین موضوع بزرگترین محدودیت این دسته از الگوریتم‌ها است. دسته‌ی دیگر، الگوریتم‌های بهینه سازی هستند که در سال‌های اخیر مورد توجه ویژه‌ای قرار گرفته‌اند. به بیانی دیگر به دلیل موفقیت الگوریتم‌های بهینه سازی از نوع تکاملی در دستیابی به راه حل-های تقریبی در مسائل فوق، الگورتیم تکاملی از نوع ژنتیک را بکار گرفتیم . الگوریتم ژنتیک که ازسیر تکامل انسان الهام گرفته و بر پایه نظریه تکامل در طبیعت بنا گردیده و نخستین بار توسط جان هلند در دانشگاه میشیگان هلند در رساله‌ای با عنوان «تطابق در طبیعت و سیستم‌های مصنوعی» معرفی شد و الگورتیم پر کاربرد دیگر الگورتیم بهینه سازی ازدحام ذرات است که یکی از مهم ترین الگوریتم های بهینه سازی هوشمند است که در حوزه هوش ازدحامی جای می گیرد. این الگوریتم، توسط جیمز کندی و راسل سی ابرهارت معرفی گردید و با الهام از رفتار اجتماعی حیواناتی چون ماهی ها و پرندگان که در گروه هایی کوچک و بزرگ کنار هم زندگی می کنند، طراحی شده است. در الگوریتم بهینه سازی ازدحام ذرات، اعضای جمعیت ، به صورت مستقیم با هم ارتباط دارند و از طریق تبادل اطلاعات با یکدیگر و یادآوری خاطرات خوب گذشته، به حل مسئله می پردازند.
درهمین راستا، ترجمه یک مقاله ژورنالی که به حل یک مسئله بهینه سازی چند هدفه معروف بنام چیدمان بسته ها با الگورتیم های کامپیوتری تحت عنوان الگورتیم بهینه سازی ازدحام ذرات و الگورتیم ژنتیک پرداخته نیز ارائه می گردد .
« A Hybrid of Particle Swarm Optimization and Genetic Algorithm for the Bin-Packing Problem»
(پذیرفته شده در American Journal Of Operations Research، اثری ازمهندس شیما شفیعی (دانش آموخته کارشناسی ارشد کامپیوتر از دانشگاه طبری بابل، دکتر همایون مؤتمنی ( عضو هیئت علمی دانشگاه آزاد ساری ) و دکتر فرهاد رمضانی( عضو هیئت علمی دانشگاه آزاد ساری ))
1-مقدمه :
در این مقاله روشی نوین مبتنی بر الگوریتم بهینه‌سازی اجتماع ذرات و ترکیب آن با الگورتیم ژنتیک به منظور حل مسئله‌ی چیدمان بسته‌ها ارائه شده است. مسئله چیدمان بسته‌ها یکی از مسائل پایه‌ای در علوم کامپیوتر است که کاربردهای فراوانی در زمینه‌هایی مانند صنایع، ریاضیات کاربردی، حمل‌و‌نقل، برنامه‌ریزی تولید و افزایش کارایی مدارات مجتمع دارد. یکی از مشکلات مربوط به دستیابی به پاسخ بهینه برای این مسئله ی بهینه سازی، افزایش زمان رسیدن به پاسخ بهینه با افزایش ابعاد مسئله است. در مدل پیشنهادی، علاوه بر کمینه کردن فضای تحت چیدمان، افزایش تعداد بسته ها تحت چیدمان در نظر گرفته شد. در نهایت، کارایی روش های پیشنهادی در حل مسئله چیدمان بسته‌ها در مطالعات عددی مختلف با نرم‌افزار متلب بررسی شده و مقایسه نتایج حاصل از شبیه‌سازی روش های پیشنهادی با نتایج حاصل از روش‌های پیشین مانند الگوریتم بهینه سازی ازدحام ذرات، کارایی روش‌های پیشنهادی ( ترکیب الگورتیم ژنتیک و الگورتیم بهینه سازی ازدحام ذرات ) را در کاهش چشم‌گیر زمان دستیابی به پاسخ بهینه و بهبود آن نشان می‌دهد.
2- اهداف اصلی
در همین راستا اهداف اصلی این مقاله مبتنی بر ترکیب الگورتیم های کامپیوتری : بهینه سازی ازدحام ذرات و و ژنتیک عبارتند از:
I. کمینه کردن فضای تحت چیدمان بهینه در فضای دو بعد
II. بیشینه کردن تعداد بسته‌ها برای چیدمان بهینه در فضای دو بعد
III. قیاس روش‌های پیشنهادی به منظور ارزیابی کارایی آنان برای دست‌یابی به چیدمان بهینه
3- روش تحقیق
در مسئله چیدمان بسته‌ها ، بایستی مجموعه‌ای از بسته‌ها به گونه‌ای در فضای دو بعدی قرار گیرند که همزمان مجموعه‌ای از اهداف اصلی نظیر: بیشینه‌سازی تعداد بسته‌های کاربردی در فضای دو بعدی و کمینه فضای تحت چیدمان برآورده شوند. هدف در این مقاله، ارائه‌ی تکنیکی ‌مبتنی بر ترکیب الگورتیم ژنتیک و الگورتیم بهینه سازی ازدحام ذرات برای دست‌یابی به چیدمان بهینه از طریق ارزیابی و قیاس آنان است. در ادامه نتایج پیاده‌سازی مسئله چیدمان بسته‌ها و مبتنی بر هر یک از روش‌های پیشنهادی با به کارگیری نرم افزار متلب ارائه گردیده است.
4-ارزیابی نتایج تجربی
مسئله بهینه سازی ترکیبی چیدمان بسته‌ها و مبتنی بر الگورتیم‌های فراابتکاری پیشنهادی برای دست‌یابی به حالت بهینه به گونه‌ای پیاده‌سازی گردید که در آن داده‌های ورودی به صورت تصادفی و با متد توزیع یکنواخت ایجاد شدند. یعنی کدهای پیاده‌سازی‌ شده به ‌صورت‌ تصادفی‌، داده‌ها را ایجاد می‌کنند. ضمن این که زبان برنامه‌نویسی MATLAB هم از توزیع یکنواخت ‌برای تولید این اعدادتصادفی استفاده‌ می‌کند و داده‌های ‌ورودی ‌شامل‌ دو ‌بخش اندازه و مساحت بسته هستند.
5- نتیجه گیری:
زمان محاسبات در حل مسائل غیر چند جمله ای سخت مقیاس بزرگ از جمله چیدمان بسته ها دارای اهمیت فراوانی است. در این مقاله روشی نوین مبتنی بر الگوریتم بهینه سازی ازدحام ذرات و ترکیب آن با الگورتیم ژنتیک به منظور حل مسئله چیدمان بسته‌ها ارائه شد که دارای زمان محاسباتی کمتری نسبت به روش‌های پیشین است. در نهایت، عملکرد روش های پیشنهادی بر روی مسئله نمونه مورد بررسی قرار گرفت و کارایی آن از نظر بهبود پاسخ نشان داده شد.