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

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

الگوریتم‌های ابتکاری جزو دسته روش‌های حل تقریبی می‌باشند و در طول فرآیند حل، از اطلاعات منحصربفرد مسئله استفاده می‌کنند. با پیاده‌سازی این الگوریتم‌ها می‌توان به پاسخ‌های نزدیک به بهینه دست یافت بطوریکه این روش‌ها تضمین می‌کنند که پاسخ بدست آمده در بازه درصد مشخصی از پاسخ بهینه قرار بگیرد. گیر افتادن در نقاط بهینه محلی و همگرایی زودرس و پیش از بلوغ پاسخ‌ها به این محل‌ها (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