آیا ساختار پنهان میتواند ما را به مسیرهای بهتر برساند؟
مسئلهی فروشندهی دورهگرد یکی از آن مسائل کلاسیک است که در ابتدا ساده به نظر میرسد، اما خیلی زود به مسئلهای چالشبرانگیز تبدیل میشود. تعریف آن روشن است: مجموعهای از شهرها داده میشود و هدف این است که کوتاهترین مسیر ممکن را بیابیم که هر شهر را دقیقاً یکبار ملاقات کند و سپس به نقطهی شروع بازگردد. بیان مسئله آسان است؛ حل آن موضوع دیگری است.
با افزایش تعداد شهرها، تعداد مسیرهای ممکن بهصورت انفجاری رشد میکند و بررسی همهی حالتها عملاً غیرممکن میشود. همین ویژگی باعث شده TSP به یکی از مسائل مهم در حوزهی بهینهسازی تبدیل شود؛ مسئلهای که در عین سادگی، محدودیت بسیاری از روشها را آشکار میکند.
در این مقاله، قصد دارم به یک ایدهی متفاوت بپردازم. به جای اینکه شهرها را صرفاً مجموعهای از نقاط مستقل در نظر بگیریم، اگر تلاش کنیم ساختار درونی موجود در مسئله را استخراج کنیم چه میشود؟ آیا این ساختار میتواند ما را در ساخت یک مسیر بهتر هدایت کند؟
من این رویکرد را مدل کریستالی نامیدهام.
از تصمیمهای حریصانه تا استفاده از ساختار
یکی از روشهای رایج برای ساخت یک مسیر اولیه، الگوریتم «نزدیکترین همسایه» است. در این روش، از یک شهر شروع میکنیم، نزدیکترین شهرِ بازدیدنشده را انتخاب میکنیم و این روند را تا تکمیل مسیر ادامه میدهیم. این روش سریع، ساده و قابل پیادهسازی است و معمولاً یک مسیر اولیه ارائه میدهد.
اما ضعف آن کاملاً مشخص است: این روش تنها به گام بعدی نگاه میکند. تصمیمی که در لحظه مناسب به نظر میرسد، ممکن است در ادامه مشکلساز شود. الگوریتم هیچ درکی از شکل کلی مسیر ندارد و صرفاً نزدیکترین گزینه را انتخاب میکند.
روشهایی مانند 2-opt میتوانند بخشی از این مشکل را کاهش دهند. با حذف دو یال و اتصال مجدد مسیر، معمولاً تقاطعها حذف میشوند و مسیر بهبود مییابد. با این حال، کیفیت نتیجهی نهایی همچنان به مسیر اولیه وابسته است.
این موضوع من را به پرسش اصلی این کار رساند:
آیا میتوان پیش از آغاز جستوجوی محلی، با استفاده از اطلاعات ساختاری، یک مسیر اولیهی بهتر ساخت؟
مدل کریستالی
ایدهی اصلی این مدل آن است که یک مسیر خوب، زنجیرهای تصادفی از یالها نیست؛ بلکه دارای ساختار است.
شهرهایی که از نظر فضایی به یکدیگر نزدیکاند، معمولاً الگوهایی تشکیل میدهند و یک مسیر مناسب باید این الگوها را تا حد امکان رعایت کند، در حالی که همچنان یک چرخهی کامل ایجاد میکند. مدل کریستالی تلاش میکند این روابط ساختاری را در مرحلهی ساخت مسیر وارد کند.
به جای اتصال شهرها بهصورت گامبهگام و صرفاً بر اساس فاصلهی لحظهای، این روش مسیر را بر پایهی روابط ساختاری میان نقاط سازماندهی میکند.
نام «کریستالی» از این جهت انتخاب شده که این رویکرد شباهتی به نحوهی آرایش اتمها در یک کریستال دارد: نظمی که از دل یک مجموعهی پیچیده پدیدار میشود.
هدف این روش حدسزدن مسیر بهینه نیست؛ هدف سادهتر است: ساخت یک مسیر اولیه که از همان ابتدا به یک جواب خوب نزدیک باشد.
یک آزمایش کوچک
برای بررسی رفتار این روش، آن را روی یک مسئلهی ۷۰ شهری آزمایش کردم و با چند روش استاندارد مقایسه نمودم:
روش |
طول مسیر |
فاصله از بهینه |
جواب دقیق |
136.442 |
0.00% |
Multi-start NN + 2-opt |
139.570 |
2.29% |
مدل کریستالی + 2-opt |
141.292 |
3.55% |
مدل کریستالی |
141.412 |
3.64% |
NN + 2-opt |
150.869 |
10.57% |
نزدیکترین همسایه |
168.574 |
23.55% |
نتیجهی نزدیکترین همسایه بسیار ضعیف است و حدود ۲۳.۵۵٪ بالاتر از جواب بهینه قرار میگیرد. افزودن 2-opt این فاصله را به حدود ۱۰٪ کاهش میدهد.
مدل کریستالی اما از همان ابتدا در وضعیت بسیار بهتری قرار دارد: فاصلهی اولیهی آن تنها ۳.۶۴٪ است و پس از اعمال 2-opt تقریباً تغییری نمیکند.
تفسیر نتایج
قصد ندارم ادعا کنم مدل کریستالی بهترین روش موجود است؛ چنین نیست.
در این آزمایش، روش Multi-start NN + 2-opt عملکرد بهتری داشته و فاصلهی ۲.۲۹٪ را ثبت کرده است. این نکته باید صریح بیان شود.
با این حال، نتیجه همچنان قابل توجه است. مدل کریستالی با رویکردی کاملاً متفاوت، به جواب نسبتاً خوبی میرسد و مسیری تولید میکند که 2-opt تنها اندکی آن را بهبود میدهد. این موضوع ممکن است نشان دهد که ساختار مسیر از ابتدا بهدرستی شکل گرفته و بسیاری از مشکلات معمول اصلاً ایجاد نشدهاند.
این نتیجه هنوز اثباتکنندهی چیزی نیست، اما نشانهی مهمی است.
مزایا و جایگاه روش
هر الگوریتمی دارای یک مبادلهی عملکردی است: برخی سریع اما ضعیفاند، برخی قوی اما پرهزینه.
مدل کریستالی در میانهی این طیف قرار میگیرد. در حال حاضر، این روش بیشتر بهعنوان یک نقطهی شروع مناسب قابل استفاده است تا یک حلکنندهی نهایی. این مدل میتواند ورودی مناسبی برای روشهای زیر باشد:
· جستوجوی چندآغازی
· 2-opt و 3-opt
· جستوجوی محلهی متغیر
· الگوریتمهای ژنتیک
· کلونی مورچگان
· شبیهسازی تبرید
· حلکنندههای ترکیبی TSP
بنابراین، پرسش مهم این نیست که آیا مدل کریستالی جایگزین روشهای موجود میشود؛ بلکه این است که آیا میتواند عملکرد آنها را بهبود دهد.
مسائلی که هنوز باید بررسی شوند
یک آزمایش ۷۰ شهری برای نتیجهگیری کافی نیست. چند پرسش مهم باقی میماند:
· آیا این روش روی مسائل بزرگتر نیز عملکرد مناسبی دارد؟
· آیا روی توزیعهای مختلف نقاط پایدار است؟
· هزینهی محاسباتی آن چقدر است؟
· روی خانوادههای مختلف TSP چه رفتاری دارد؟
· آیا در اجراهای تکراری نتایج مشابه تولید میکند؟
اینها موضوعاتی هستند که باید در ادامه بررسی شوند.
جمعبندی
مسئلهی TSP سالهاست مورد مطالعه قرار گرفته و روشهای بسیار قدرتمندی برای آن توسعه یافتهاند. بنابراین هدف این کار ادعای یک دستاورد خارقالعاده نیست.
هدف سادهتر است:
شاید ساختار درونی مسئله اهمیت بیشتری داشته باشد از آنچه روشهای حریصانه تصور میکنند.
در این آزمایش اولیه، مدل کریستالی مسیر بسیار بهتری نسبت به نزدیکترین همسایه تولید کرد و پس از 2-opt نیز نتیجهی قابل قبولی داشت. این روش بهترین روش موجود را شکست نداد، اما نشان داد که استفاده از اطلاعات ساختاری میتواند یک جزء مفید باشد.
همین موضوع کافی است تا ارزش بررسی بیشتر را داشته باشد—نه به این دلیل که برنده شده، بلکه به این دلیل که به نظر میرسد مسیر درستی را نشان میدهد.
هیچ نظری موجود نیست:
ارسال یک نظر