فروشنده دوره گرد با شبکه عصبی هاپفیلد در نرم افزار متلب

فروشنده دوره گرد با شبکه عصبی هاپفیلد

در این بخش پروژه فروشنده دوره گرد با شبکه عصبی هاپفیلد با نرم افزار MATLAB را به همراه کامنت گذاری کدها آماده کردیم که بر اساس مقاله Solving Traveling Salesman Problem Using Continuous Hopfield Network انجام شده است. در ادامه به شرح مسئله TSP و زمینه های کاری آن پرداخته و فیلم و تصاویری از خروجی این پروژه قرار داده شده و مقاله مرجع نیز به صورت رایگان قابل دانلود می باشد.

شرح مسئله فروشنده دوره گرد

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

مسائل بهینه سازی ترکیبی

مسائل بهینه سازی ترکیبی، مثل مسئله فروشنده دوره گرد (TSP) و کوتاه ترین مسیر (SP)، از خانواده مسائل NP-Complete می باشند که مدت زمان مورد نیاز به جهت حل این نوع مسائل با افزایش تعداد پارامترها به طور نمایی افزایش یافته و این در حالی است که با پیشرفت روز افزون تکنولوژی ها، نیازمندی به حل سریع تر و مناسب تر این مسائل نیز به سرعت رو به افزایش می باشد. مشخص کردن مسیر بهینه حرکت مته جهت سوراخ نمودن صفحه های PCB، مشخص کردن مسیر بهینه انتقال داده در شبکه های کامپیوتری، بهینه سازی شبکه های توزیع نیرو، پردازش تصویر و تشخیص الگو، هدایت ربات، تفکیک و دسته بندی داده ها از جمله زمینه هایی می باشند که حل مسئله فروشنده دوره گرد برای آنها بسیار مهم می باشد.

حل مسئله TSP

فروشنده دوره گرد (Traveling Salesman Problem – TSP)، عبارت است از پیدا کردن کوتاه ترین مسیر بسته ممکن بین N، شهر می باشد و روش هایی که تا کنون به منظور حل مسئله TSP ارائه شده اند، اغلب بر اساس جستجوگرها و آشکار ساز های معین یا احتمالی می باشند که از مهم ترین آنها، الگوریتم های کلاسیک جستجوی محلی، الگوریتم آبکاری شبیه سازی شده (SA)، شبکه های عصبی مصنوعی مانند کوهونن یا نگاشت های خودسازمانده (SOM)، شبکه عصبی هاپفیلد (Hopfield)، بولین و آشوبی، الگوریتم های ژنتیکی، برنامه نویسی تکاملی، سیستم کولونی مورچه ها (ACO)، روش های یادگیری افزایشی مبتنی بر جمعیت و روش های آموزش با تنظیم ظریف می باشند.

نقاط ضعف و قوت الگوریتم ها

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

تصاویری از خروجی پروژه فروشنده دوره گرد با شبکه عصبی هاپفیلد

شکل 1

شکل 2

شکل 3

شکل 4

شکل 5

شکل 6

شکل 7

شکل 8