بایگانی‌های Traveling Salesman Problem

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

بهینه‌سازی یک مسئله ریاضی و کلی است که از قرن‌ها پیش مطرح بوده است و در حال حاضر هم یک مسئله و موضوع در دست بررسی و پژوهش است. هنوز راه حلی کلی برای تمام مسائل بهینه‌سازی مطرح نشده است. البته در بعضی موارد محدود که در آن تابع هدف کاملا مشخص شده و معین است و مسائلی مانند مشتق‌پذیری در آن وجود دارد؛ می‌توانیم بصورت دقیق آن را حل کنیم. در بعضی از مسائل هم جواب نهایی وجود دارد ولی زمان محاسبه آن بسیار زیاد طول خواهد کشید. با این حال هنوز برای بعضی از مسائل راه حل معقول و مشخصی ابداع نشده است. بر همین اساس، طبقه‌بندی‌های مختلفی برای اینگونه مسائل از لحاظ پیچیدگی و یا پارامترهای دیگر تعیین شده است. بطور مثال: مسائل برنامه‌ریزی خطی (LP)، برنامه‌ریزی غیر خطی (NLP)، مسائل درجه دوم (QP)، مسائل NP,NP-hard و…

مسئله فروشنده دوره‌گرد (TSP)

یکی از ساده‌ترین و در عین حال، پرکاربردترین و مفیدترین مسائل مطرح شده در حوزه بهینه‌سازی مسئله فروشنده دوره‌گرد (Traveling Salesman Problem) است.

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

این مسئله در طبقه‌بندی مسائل NP-hard قرار می‌گیرد و روش‌های عادی نمی تواند پاسخی برای این مسئله پیدا کند. اما بعضی از الگوریتم‌های فراابتکاری و یا تکاملی، می‌توانند در این خصوص پاسخ نه کاملا بهینه اما نزدیک به آن را به ما بدهند.

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

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

برای حل این مسئله باید تمام راه حل‌های ممکن و یا حداقل بیشتر آن‌ها بررسی شود تا به جواب و راه حل بهتر دست پیدا کنیم. مشکل ما در این بررسی، فاکتور زمان است. بطور مثال اگر در مسئله فروشنده دوره گرد N شهر داشته باشیم؛ N فاکتوریل هم راه حل خواهیم داشت.

ارتباط بهینه‌سازی و الگوریتم‌های فراابتکاری

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

بهترین و کارآمدترین الگوریتم‌ها باید یک سری ویژگی‌ها را داشته باشند. بطور مثال: قابلیت کشف و جستجوی بالا (exploration) و قابلیت استخراج کردن (exploitation)

الگوریتم‌های بهینه‌سازی کلاسیک، اغلب این قابلیت‌ها را به صورت متعادل ندارند. بطور مثال قابلیت Global search برای استخراج کردن را ندارند. مکانیزم این گونه الگوریتم‌ها Local search است. همچنین الگوریتم‌های Random search (جستجوی تصادفی) در این بین هستند که Global search خوبی دارند ولی در نهایت نمی توانند به همگرایی مورد نیاز برسند. در واقع روشی که در بین این الگوریتم‌ها بصورت هوشمندانه عمل کند و در نهایت به همگرایی برسد، همان الگوریتمهای فراابتکاری و تکاملی است.

الگوریتم ژنتیک

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

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

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

الگوریتم‌های دیگری نیز در حوزه بهینه‌سازی و محاسبات تکاملی مطرح شده اند مانند: الگوریتم مورچگان (ACO)، الگوریتم ازدحام ذرات (PSO)، الگوریتم کلونی زنبور عسل (ABC)، الگوریتم رقابت استعماری (ICA) و …

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

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

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

منبع