مسأله فروشنده دوره‌گرد (Travelling Salesman Problem = TSP)

در ابتدا به مسأله فروشنده دوره‌گرد (TSP) توجه مي‌كنيم؛ در اين مسأله مأموري به صورت تصادفي در فضاي جستجو (گرافn بعدي) حركت مي‌كند. تنها موقعيت اجباري اين است كه مأمور بايد فهرست شهرهايي را كه رفته به جهت اجتناب از تكرار به خاطر بسپارد. در اين روش بعد از n حركت، مأمور به شهر شروع باز مي‌گردد و راه‌حلي به دست مي‌آيد. روش جستجوي تصادفي ممكن است تكراري بوده و يا از شهرهاي مختلف شروع شود كه شامل الگوريتم چند شروعه (Multistart) مي‌شود.

روش‌هاي فرا ابتكاري مي‌توانند مطابق موارد زير به دست آيند:

  • استفاده از شيوه‌اي مبتني بر علاقه‌مندي براي انتخاب هر حركت مأمور؛
  • استفاده از روش جستجوي محلي (معاوضه موقعيت گره‌ها) براي بهبودي راه‌حل؛
  • استفاده از روش جستجوي محلي تصادفي و تنها پذيرش تغييرات بهبود يافته؛
  • استفاده از m مأمور كه از شهرهاي مختلف شروع مي‌كنند.
  • استفاده از تعدادي مأمور با استخدام غير قطعي؛
  • استفاده از روش‌هاي گروهي براي قسمت‌بندي فضا و يا مأموران؛
  • استفاده از قانون پذيرش بدون قطع براي تغييرات اصلاح نشده؛
  • استفاده از اطلاعات آخرين حركات براي اجراي يك سيستم حافظه‌اي.