اُپتی‌کد، مرجع کدهای الگوریتم فرا ابتکاری مسائل ریاضی

---

 

سلام دوستان. امیدوارم حالتون خوب باشه. خب در این بخش قصد داریم تا نحوه‌ی راه‌اندازی فایل‌های اُپتی‌کد رو در محیط متلب خدمتتون آموزش بدیم. پس از تهیه‌ی محصول مورد نظرتون، یک فایل zip در اختیارتون قرار داده می‌شه. این فایل zip حاوی 3 دسته فایل هست.

1- یک پوشه حاوی تمامی توابع و اسکریپت‌های محیط متلب.

2- یک فایل Excel حاوی داده‌های ورودی مسئله.

3- یک فایل PDF شامل مدل ریاضی مسئله.

 

 

اُپتی کد سعی کرده راه‌اندازی فایل‌ها و استفاده ازشون تا حد ممکن راحت و ساده باشه. بریم ببینیم چه اقداماتی برای این کار نیاز هست. برای آشنایی راحتتر شما عزیزان، فرض می‌کنیم فایل zip الگوریتم ژنتیک مسئله کوله پشتی رو می‌خوایم راه‌اندازی کنیم. البته دوستای گلم این رو هم اشاره کنم که مراحل زیر برای تمامی کدها صدق می‌کنه.

 

گام اول) ابتدا تمام محتویات فایل zip رو پس از دانلود، در یک پوشه‌ی مناسب در یک آدرس دلخواه یا در دسکتاپ extract کنید. مثلا فرض کنیم در یک پوشه با نام MyFiles در دسکتاپ extract کردیم.

 

 

گام دوم) فایل اسکریپت GA (یا هر تابع دیگر) رو از پوشه‌ی حاوی کدها اجرا کنید تا وارد محیط نرم‌افزار متلب بشید. در این محیط تمامی توابع در قسمت Current Folder قابل مشاهده هست.

 

گام سوم) تابع RunModel رو باز کنید و مسیر فایل اکسل رو در داخل متغیر ExcelRoute به‌روزرسانی کنید. با این کار داده‌های فایل اکسل به بدنه‌ی الگوریتم متصل میشن. در مثالی که تا الان باهم پیش اومدیم، کافیه روی فایل اکسل راست کلیک کنید و با کلیک روی گزینه Properties، محل آدرس فایل رو مشاهده کنید.

 

 

حالا، این آدرس رو از قسمت Location مربوط به فایل اکسل، داخل متغیر ExcelRoute کپی کنید. البته یادتون نره اسم فایل (ینی Data.xlsx) رو هم به آخرش اضافه کنید.

 

 

و تمام. حالا کافیه اسکریپت اصلی الگوریتم رو (در این مثال GA) اجرا کنید و خروجی‌های مسئله رو دریافت کنید.

 

نکته) این کدها برای نمودهای کلی و عمومی مسائل تدوین شدن. می‌تونید تغییرات مدنظرتون رو برای اینکه کد بتونه مسئله بخصوص شما رو حل کنه، داخل توابع متلب اعمال کنید. همچنین برای این کار می‌تونید از قسمت "تماس با ما" یا کانال تلگرامی‌مون، با ادمین‌ها در ارتباط باشید. موفق باشید.

 

---

 

---

 

 

الگوریتم‌های فرا ابتکاری

الگوریتم‌های فرا ابتکاری (Metaheuristic Algorithms) جزو روش‌های بهینه‌سازی تقریبی محسوب می‌شوند.کلمه فرا ابتكاري برای اولین بار در مقاله گلاور در هنگام معرفي الگوريتم جستجوي ممنوعه، عنوان شد. الگوريتم‌هاي فرا ابتكاري استراتژي‌هاي كلي جستجو هستند و مي‌توانند به عنوان راهكار يافتنجواب در مورد طيف وسيعي از مسائل استفاده شوند. الگوریتم‌های فراابتکاری، به طور قابل ملاحظه‌ای توانایی دست‌یابی به جواب‌های بهینه یا نزدیک بهینه را برای مسائل سخت افزایش می‌دهند. ویژگی مشترک این دسته از الگوریتم‌ها، اینست که از یک‌سری سازوکارهایی برای خروج از نقاط بهینه محلی استفاده می‌کنند و در دام این محل‌ها نمی‌افتند.

الگوریتم‌های فرا ابتکاری ویژگی‌های دیگری نیز دارند. احتمالی بودن ماهیت این روش‌ها، از به دام افتادن آن‌ها در نقاط بهینه محلی جلوگیری می‌کند. همچنین، علی‌رغم اینکه این روش‌ها بیشتر در مسائل گسسته کاربرد دارند، در حل مسائل پیوسته نیز می‌توان از آن‌ها بهره جست. اغلب این روش‌ها، از دل مفاهیمی چون فیزیک، زیست‌شناسی و جانورشناسی الهام گرفته شده‌اند. براي استفاده از هر روش فرا ابتكاري در حل يك مسئله خاص، بايستی قوانين موجود در مسئله و پارامترهاي روش به نحوي طراحي شوند كه بهترين استفاده ممكن از الگوریتم مدنظر در حل مسئله به دست آيد. به فرآیند تنظيم و طراحي روند و نحوه مقدارگيري پارامترهاي روش‌هاي فرا ابتكاري، تنظيم سازي مي گويند.

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

 

1- روش مبتنی بر یک جواب: برخی الگوریتم‌ها مانند ، شبیه‌سازی تبرید، جست‌وجوی ممنوعه، جست‌وجوی محلی تکرار شونده، جست‌وجوی همسایگی متغیر و جست‌وجوی محلی هدایت شده یک پاسخ یکتا را در نظر می‌گیرند و با طی فرآیندهایی سعی در بهبود آن پاسخ دارند.

2- روش مبتنی بر جمعیت: در مقابل، برخی الگوریتم‌ها یک جمعیتی از پاسخ‌های اولیه را در نظر می‌گیرند و در هر تکرار تا رسیدن به شراتط خاتمه، با اعمال برخی عملیات بر روی این پاسخ‌ها، به سمت دست‌یابی به پاسخ‌های بهتر می‌روند. الگوریتم‌هایی همچون الگوریتم‌های تکاملی (ژنتیک)، جست‌وجوی پراکنده، ازدحام ذرات، کلونی زنبورعسل و کلونی مورچگان جزو این دسته از الگوریتم‌ها هستند.

 

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

آشنایی با الگوریتم بهینه‌سازی ژنتیک، می‌تواند در راستای آشنایی با این الگوریتم‌ها دید خوبی به علاقه‌مندان حوزه فرا ابتکاری‌ها بدهد. در این روش، هر پاسخ را یک کروموزوم در نظر می‌گیریم که ساختاری آرایه‌ای دارد. ابتدا یک تعداد پاسخ اولیه (n) بصورت تصادفی تولید می‌کنیم. سپس در هر تکرار با اعمال فرآیندهای تولیدمثل و جهش بر روی این جمعیت (والدین)، جمعیت نسل جدید را بوجود می‌آوریم (فرزندان). حال با یک جمعیت بزرگتر و ادغام شده از والدین و فرزندان مواجهیم. این جمعیت را با توجه به تابع هدف مسئله و محدودیت‌ها (تابع برازندگی) ارزیابی می‌کنیم و n عضو بهتر را برای بقای نسل برمی‌گزینیم و باقی جمعیت مطابق قانون انتخاب طبیعی، حذف می‌شوند. این فرآیند مکرراً تا رسیدن به تعداد تکرار معین و یا شرایط دیگری که در مسئله تعریف می‌شود، ادامه می‌یابد. با مشاهده این روند خواهیم دید که در طی نسل‌های متوالی دائماً جامعه پاسخ‌های ما بهتر و بهتر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته‌است در طی چند نسل عملاً پاسخ‌های با تابع برازش بد را از جامعه حذف کند.

جهت آشنایی با الگوریتم‌های فرا ابتکاری، پیشنهاد می‌کنیم فایل زیر را مطالعه فرمایید.

 

Metaheuristics- From Design to Implementation- El-Ghazali Talbi

 

 

---

 

---

 

 

الگوریتم‌های ابتکاری

الگوریتم‌های ابتکاری جزو دسته روش‌های حل تقریبی می‌باشند و در طول فرآیند حل، از اطلاعات منحصربفرد مسئله استفاده می‌کنند. با پیاده‌سازی این الگوریتم‌ها می‌توان به پاسخ‌های نزدیک به بهینه دست یافت بطوریکه این روش‌ها تضمین می‌کنند که پاسخ بدست آمده در بازه درصد مشخصی از پاسخ بهینه قرار بگیرد. گیر افتادن در نقاط بهینه محلی و همگرایی زودرس و پیش از بلوغ پاسخ‌ها به این محل‌ها (Premature convergence) دو مشکل اصلی این روش‌ها به حساب می‌آیند. اگرچه الگوریتم‌های ابتکاری غالباً تضمینی در یافتن جواب بهینه نمی‌دهند، با این حال با سرعت بالایی جواب‌هایی که نزدیک به پاسخ بهینه هستند، تولید می‌کنند. این الگوریتم‌ها به دو دسته تقسیم می‌شوند.

1- الگوریتم‌های سازنده: دسته‌ای از انواع الگوريتم‌هاي ابتكاري هستند كه در آن يك جواب از مسئله به تدريج و مرحله بهمرحله با توجه به داده‌هاي مسئله ساخته مي‌شوند. برای مثال الگوريتم نزديك‌ترين همسايگي براي حل مسئلهفروشنده دوره‌گرد يك الگوريتم سازنده محسوب می‌شود كه در طول فرآیند حل، اولين شهر را به صورت تصادفي انتخاب كرده وسپس با توجه به ماتريس فاصله در هر تكرار نزديك ترين شهر به مجموعه شهرهاي عضو تور، انتخاب شدهو به تور اضافه مي‌شود. بازیکن بازی شطرنج را در نظر بگیرید که در طول بازی طبیعتا نمی‌تواند مسیر بهینه را برای برد طی کند، با این حال از قواعد و خط مشی‌هایی در هر حرکت طوری تبعیت می‌کند که بهترین نتیجه را از آن گام بگیرد. الگوريتم‌هاي سازنده بسيار سريع هستند، اما معمولاً فاصله جواب توليد شده باجواب بهينه زياد است.

2- الگوریتم‌های بهبوددهنده: از اين الگوريتم‌ها تحت عنوان الگوريتم‌هاي جستجوي محلي نيز ياد مي‌شود. بهبوددهنده‌ها نوع ديگري از الگوريتم‌‌هاي ابتكاري هستند كه در آن‌ها معمولاً جستجو از يك جواب اوليه شروع مي شود. اين جواب اوليه ممكن است از طریق يك الگوريتم سازنده قبلاً حاصل شده باشد و یا اینکه به صورت تصادفي توليد شده باشد. در گام بعد با جستجوي موضعي در همسايه‌هاي اين جواب، سعي در بهبود جواب دارند و اين كار را به صورت بازگشتي در هر تكرار از الگوريتم‌ها انجام مي‌دهند. ساختار و چگونگی ایجاد پاسخ همسايگي اين نوع از الگوريتم‌ها بسيار مهم است. مثلاً در الگوريتم‌هاي گراديان كاهشي (براي مسائل مينيمم سازي) و تپه‌نوردي (براي مسائل ماكزيمم سازي) از ايده جستجوي محلي براي يافتن جواب‌هاي بهتر در همسايگي جواب فعلي استفاده مي‌كنند. اما مشكل اصلي اين نوع از الگوريتم‌ها آن است كه اغلب در دام بهينه محلي كه نسبت به بهينه سراسري بسيار بدتر است، گرفتار مي‌شوند.

 

---

 

 

بعنوان مثال از الگوریتم‌های ابتکاری سازنده برای مسئله TSP می‌توان به روش‌های زیر اشاره کرد:

1- نزدیک‌ترین همسایه (Nearest neighbor heuristic): این روش، ابتدا یک شهر را به تصادف بعنوان شهر آغازین انتخاب کرده و سپس در هر تکرار، از آخرین شهر اضافه شده به تور، به نزدیک‌ترین همسایه آن شهر حرکت می‌کند.

2- افزودن نزدیک‌ترین گره (Nearest insertion heuristic): طی این روش، ابتدا یک تور بین دو شهر دلخواه ایجاد می‌شود و در هر تکرار، ابتدا نزدیکترین شهر را به مجموعه شهرهای موجود در تور یافته و سپس این شهر جدید را طوری به تور اضافه می‌کنیم که افزایش طول تور کمینه باشد.

3- افزودن ارزانترین گره (Cheapest insertion heuristic): این روش، مشابه روش افزودن نزدیکترین گره است، با این تفاوت که شهر جدید را طوری انتخاب می‌کند که میزان افزایش در هزینه یا طول تور، با افزودن این گره به تور کمینه باشد.

4- افزودن دورترین گره (Furthest insertion heuristic): ابتدا دو گره که دورترین فاصله را از هم دارند داخل تور قرار می‌دهیم. سپس در هر تکرار، گرهی که با قرار گرفتن در بهترین چینش تور، بیشترین مسافت را ایجاد می‌کند، به تور اضافه می‌شود. هدف این روش، اینست که ابتدا شهرهای دور در داخل تور قرار گیرند.

5- الگوریتم کریستوفیدز (Christofides heuristic): علی‌رغم گذشت بیش از 30 سال از ارائه این روش، همچنان روش کریستوفیدز بهترین الگوریتم ابتکاری حل مسئله TSP بشمار می‌رود و پاسخ‌های بدست آمده از این روش، از 1.5 برابر پاسخ بهینه بدتر نخواهند بود. این الگوریتم از مفاهیم نظریه گراف، بسط دادن درخت پوششی کمینه، جدا کردن رأس‌های با درجه فرد، یافتن بهترین تطابق میان این رأس‌ها، تشکیل تور اویلری میان این رأس‌ها و حذف میانبرها (shortcuts) که درنهایت منجر به تشکیل یک تور TSP می‌شود. تشکیل یافته است.

 

همچنین برخی از الگوریتم‌های بهبوددهنده ارائه شده برای مسئله TSP به شرح زیر است:

1- الگوریتم دو-گزینشی (Two-opt heuristic): این الگوریتم، یک تور کامل را در نظر می‌گیرد و در هر تکرار، دو یال نامجاور را در نظر می‌گیرد و آن‌ها را حذف می‌کند. سپس دو زیرتور ایجاد شده را طوری به هم وصل می‌کند که طول تور نهایی، کمینه شود. بعبارتی، سعی در حذف برخورد مابین یال‌ها دارد و اگر فواصل مسئله TSP ماهیت اقلیدسی داشته باشند، هیچ برخوردی در نهایت مابین یالهای تور نخواهد ماند.

 

 

2- الگوریتم چند-گزینشی (k-opt heuristic): این الگوریتم حالت کلی و جامع الگوریتم قبلی است و در هر تکرار k یال نامجاور را حذف کرده و زیرتورهای ایجاد شده را به بهترین شکل مجدداً به هم متصل می‌کند. پاسخ بهینه بدست آمده از روش چند-گزینشی را k-optimum می‌نامند. این الگوریتم نیازمند حجم عملیات زیادی است و اغلب به ازای k=2,3 کاربرد دارد.

3- الگوریتم لین-کرنیگان (Lin-Kernighan heuristic): این الگوریتم نسخه دیگری از چند-گزینشی است که در آن مقدار k در تکرارهای مختلف تغییر می‌کند.

 

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

 

“Design of Modern Heuristics – Principles and Applications” by Franz Rothlauf

 

 

---

 

 

بهینه‌سازی یعنی چه؟

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

 

دسته‌بندی‌های الگوریتم‌های بهینه‌سازی؟

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

 

---

 

1- روش‌های دقیق

اين دسته از الگوريتم‌ها رسيدن به جواب بهينه را به ازاي هر نمود از مسئله تضمين مي‌كنند و استفاده از آن‌ها در مسائل با پیچیدگی چندجمله‌ای پیشنهاد می‌شود. با این حال تاكنون بهترين الگوريتم‌هاي دقيقي كه براي مسائل سخت ارائه شده اند داراي پيچيدگي بدترين حالت نمايي بوده‌اند و ازین رو در حل مسائل رده سخت (NP-Hard) کارایی مطلوبی ندارند. مشكل ديگر استفاده از الگوريتم‌هاي دقيق براي حل مسائل سخت آن است كه حجم محاسباتي چنين الگوريتم‌هايي با افزايش اندازه نمود، به سرعت زياد شده و اغلب دچار خطاي محاسباتي گرد كردن و يا كمبود حافظه موردنياز مي‌شوند.

برخی از الگوریتم‌های دقیق به‌کار رفته در مسائل بهینه‌سازی عبارتند از:

1.1- روش‌های تحلیلی (Analytical methods)

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

می‌دانیم در این مسئله با محاسبه گرادیان تابع f و یافتن مقادیری از بردار جواب x طوری که مقدار بردار گرادیان برابر 0 شود، نقاط بالقوه مسئله (بهینه محلی) هستند. حال می‌توان مینیمم، ماکسیمم یا نقطه عطف بودن هریک از این نقاط بالقوه را با بررسی جواب‌های اطراف این نقاط و یا با استفاده از محاسبات ماتریس هسیان، بدست آورد. سپس جواب‌هایی که ماهیت نقطه عطف دارند را کنار می‌گذاریم و بسته به نوع تابع هدف، پاسخ‌های مینیمم یا ماکسیمم را بررسی کرده و پاسخ بهینه را از بین تمام نقاط بهینه محلی برمی‌گزینیم.

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

2.1- روش‌های عددی (Numerical methods)

برخی مسائل پیچیدگی‌های دارند که علی‌رغم برخورداری از فرم عادی توابع، باعث می‌شود حل رابطه‌ی بالا (گرادیان) برای آن‌ها مشکل باشد.

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

روش گرادیان:

روش نیوتن-رافسون:

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

 

روش گرادیان نزولی

 

بطور خلاصه روش‌های تحلیلی و عددی برای مسائل مشتق‌پذیر و خوش تعریف قابل پیاده‌سازی هستند. هرچند این روش‌ها دارای نقطه ضعف‌های عمده‌ای هستند. مسائلی که با این روش‌ها قابل حل شدن هستند، بسیار محدود و اندک‌اند. همچنین این روش‌ها به این دلیل که توابع هزینه غالباً تک-مدوله (Unimodal) نیستند، الزاماً به جواب بهینه سراسری منجر نمی‌شوند و برای این کار نیاز به انجام محاسبات زیادی برای یافتن تمام نقاط بهینه محلی و سپس یافتن جواب بهینه دارند.

 

---

 

 

مسائل خطی پیوسته (Linear Continuous)، بخش دیگری از حوزه بهینه‌سازی را تشکیل می‌دهند. ساختار ترکیب خطی متغیرها در تابع هدف و محدودیت‌ها، ویژگی اساسی این دسته مسائل است. با توجه به توسعه الگوریتم‌های دقیقی که می‌توانند تمام نمودهای مسائل خطی پیوسته را در یک مرتبه زمانی چندجمله‌ای حل کنند، این دسته از مسائل جزو مسائل رده P بشمار می‌روند. روش‌های حل زیر جهت حل مسائل خطی پیوسته توسعه یافته‌اند.

3.1- الگوریتم سیمپلکس (Simplex): این الگوریتم توسط دانتزیگ در سال 1947 توسعه یافت. روش سیمپلکس، مدل به فرم استاندارد یک مسئله خطی پیوسته را دریافت کرده و خروجی آن جواب بهینه مسئله است. علی‌رغم اینکه این روش پیچیدگی بدترین حالت نمایی را دارد، ولی بسیار روش کارآمدی برای دسته مسائل LP بشمار می‌رود.

 

نمونه جدول سیمپلکس

 

4.1- الگوریتم نقطه درونی (Interior Point): این روش توسط خاچیان در سال 1979 ارائه شد و بعدها توسط کارمارکار و سایر پژوهشگران بهبودهایی یافت. ویژگی مهم این الگوریتم، پیچیدگی بدترین حالت چندجمله‌ای آن است. هرچند که از نظر کارایی همسطح روش سیمپلکس است.

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

 

---

 

در کنار مسائل خطی پیوسته، با مسائل بهینه‌سازی گسسته (Discrete Optimization Problem) مواجه‌ایم که در این مسائل همه (IP) یا برخی (MIP) از متغیرهای تصمیم ماهیت عدد صحیح دارند. به مسئله‌ای که در آن همه متغیرها گسسته بوده و تعداد پاسخ‌ها محدود باشد، بطوریکه بتوانیم تمام پاسخ‌های موجه مسئله را بشماریم، مسئله بهینه‌سازی ترکیبی (Combinatorial Optimization Problem) گویند. اولین راهی که در حل این مسائل به ذهن می‌رسد، حل آزادسازی خطی مسئله با حذف محدودیت‌های عددصحیح مسئله توسط الگوریتم‌های خطی پیوسته است. هرچند پاسخ بدست آمده به احتمال بالایی مناسب مسئله اصلی نیست که در این صورت از تکنیک‌های گرد کردن پاسخ مسئله آزادسازی خطی (Rounding) یا جست‌وجوی محلی اطراف این پاسخ است. هرچند باید توجه شود لزوماً این تکنیک‌ها نیز تضمین کننده‌ی دست‌یابی به پاسخ بهینه عدد نیستند و می‌توان مثال‌هایی یافت که جواب بهینه مسئله اصلی با جواب بهینه مسئله آزادسازی فاصله زیادی دارند.

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

5.1- روش درخت جست‌وجو: در صورتی که فضای جست‌وجوی پاسخ‌های مسئله گسسته یا ترکیبی محدود و کوچک باشد، می‌توان با استفاده از ساختار درختی و در قالب رأس‌ها و یال‌های یک گراف مسئله را مدل کرده و با استفاده از یک سیاست جست‌وجوی کارآمد جواب مناسب را بیابیم.

6.1- روش شاخه و کران: تمرکز اصلی در این روش، تبدیل مسئله اصلی به تعدادی زیرمسئله در طی یک سری تکرارهای بازگشتی است. این کار را می‌توان به کمک افزودن محدودیت‌هایی بر روی بازه‌های متغیرها انجام داد. نتیجه این روش، حذف زیرمسئله‌های نامناسب و دست‌یابی سریعتر به پاسخ بهینه مسئله است. اصطلاح شاخه برای دسته‌بندی و اعمال محدودیت بر وی مقادیر یک متغیر و اصطلاح کران (حد) برای حذف یا ادامه دادن یک شاخه و زیرمسئله به کار می‌روند. روش شاخه و کران در مسائل غیرخطی نیز کاربرد دارد.

7.1- برنامه‌ریزی پویا: روش برنامه‌ریزی پویا نیز همانند شاخه و کران، یک روش هوشمندانه برای شمارش پاسخ‌های مسئله ترکیبی است. کارکرد این روش به صورت عقب‌گرد است. کافیست با مقداردهی به آخرین متغیرهای تصمیم و تعریف رابطه بازگشتی مابین متغیرها، به متغیرهای تصمیم اولیه برسیم. نکته مهم اینکه پیاده‌سازی برنامه‌ریزی پویا، مستلزم تعریف مسئله در چارچوب یک فرآیندچندمرحله‌ای است. همچنین باید حالت‌ها، سیاست‌ها و شرایط مرزی مسئله نیز قبل از پیاده‌سازی تعریف شوند. خروجی این الگوریتم،، یک توالی از مقادیر متغیرهای تصمیم را به عنوان پاسخ بهینه مسئله ترکیبی، معین خواهد کرد.

8.1- روش صفحات برش: صفحات برش گموری، روشی است که طی آن محدودیت‌هایی را به مسئله اضافه می‌کنیم تا بتوانیم فضاهای جواب نامناسب را البته بدون حذف هیچ‌گونه نقطه عدد صحیحی، کنار بگذاریم. این صفحات را به دو روش می‌توان پیاده کرد. 1- ادغام با روش شاخه و کران 2- افزودن برش در هر تکرار الگوریتم سیمپلکس در حل مسئله آزادسازی خطی. جهت مطالعه و آشنایی بیشتر با روش صفحات برش، پیشنهاد می‌شود به گزارش زیر مراجعه کنید.

 

فضای عدد صحیح

 

آشنایی با صفحات برش

 

 

---