بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
حل مسئله فروشنده دوره گرد (TSP) با استفاده از شبکه عصبي خود سازمانده (SOM)
چکيده
اين مقاله يک شبکه عصبي خود سازمانده کوهنن (SOM) اصلاح شده را به منظور حل مسئله فروشنده دوره گرد (TSP) معرفي ميکند. در مسئله TSP هدفمان اين است که مجموعه اي از n شهر را با طي کوتاهترين مسير و در کوتاهترين زمان بپيماييم و دوباره به شهر اول باز گرديم . اين مسئله به ظاهر ساده ، بعنوان مسئله NP-Hard شناخته شده است و فضاي جستجو بصورت !n مي باشد. درنتيجه بررسي تمام راه حلهاي مسئله TSP با تعداد زياد شهرها عملاً امکان پذير نيست و نياز داريم که از روش هاي سريع و موثر مانند روشهاي هوش مصنوعي و شبکه هاي عصبي استفاده کنيم . در انتها نتايج حاصل از اجراي روش پيشنهادي در نرم افزار MATLAB را با نتايج بدست آمده از الگوريتم جمعيتي مورچه ها (Ant Colony Optimization) مقايسه و ميزان خطاي الگوريتم SOM را در مقايسه با آن مورد بررسي قرار مي دهيم .
واژه هاي کليدي : مسئله فروشنده دوره گرد (TSP)، شبکه هاي عصبي خودسازمانده (SOM)، الگوريتم جمعيتي مورچه ها (ACO)، مسئله NP-hard.
١- مقدمه
مسئله فروشنده دوره گرد يکي از معروفترين مسائل بهينه سازي در شاخه تحقيق در عمليات ميباشد. اين مسئله در بسياري از مسائل مهندسي نظير کنترل ، رباتيک ، الکترونيک ، شيمي و صنايع کاربرد دارد. به عنوان مثال به هنگام برنامه ريزي يک ربات نگهبان جهت بازديد از نقاط مختلف ساختمان در کمترين زمان ممکن از ايدة مسئله TSP استفاده مي شود[١] و همچنين در زمينه مهندسي صنايع در حل مسئله زمان بندي (JSP) آن را با يک مسئله TSP مدل ميکنيم [٢-١].
نظريه فروشنده دوره گرد، عبارت است از بازديد از يک مجموعه n شهري با شروع از يک شهر و بازگشت به همان شهر بطوريکه هر شهر فقط و فقط يک بار ملاقات شود. درنگاه اول ، ممکن است مسئله بسيار ساده به نظر برسد، ولي از لحاظ تئوري اثبات شده است که مسئله TSP در کلاس مسايل NP-hard قرار دارد[٣]. يک مسئله -NP hard با استفاده از الگوريتم هاي تحليلي شناخته شده در يک زمان چندجمله اي حل نمي شود و از روشهاي هوش مصنوعي همانند الگوريتم هاي ژنتيکي و شبکه هاي عصبي براي حل آنها استفاده ميشود. در اين مسئله فضاي جستجو بسيار بزرگ بوده و عملاً تست تمامي جوابهاي ممکن مقدور نمي باشد، بطوري که در بعضي از مسايل مهندسي مانند VLSI بيش از يک ميليون شهر وجود دارد و يک روش سريع و ذهني مورد نيازخواهدبود. روش هاي معمول حل مسئله TSP عمدتاً الگوريتم هاي تکاملي مانند جستجو در نزديک ترين همسايه (NNS)، جستجوي ممنوعه (TS)، سرمايش تدريجي (SA)، الگوريتم هاي ژنتيکي (GAs)، الگوريتم پرندگان (PSO)، الگوريتم جمعيتي مورچه ها(ACO) و شبکه هاي عصبي ميباشد .[4-7]
در اين مقاله الگوريتم SOM به عنوان يکي از انواع شبکه هاي عصبي جهت حل مسئله TSP ارائه مي شود. با توجه به نتايج بدست آمده از شبيه سازي ها اين روش از سرعت همگرايي قابل قبولي نسبت به روشهاي فوق برخوردار مي - باشد. اين نوع شبکه عصبي بدليل داشتن ويژگي خود سازمانده بودن و شروع از يک نقطه کاملاً تصادفي [٨] ، در انتهاي الگوريتم به يک جواب تقريباً بهينه (suboptimal) و قابل قبول همگرا مي شود.
٢- اساس شبکه هاي عصبي خود سازمانده
درسال ١٩٧٥، کوهنن (Kohonen) يک روش جديد از شبکه هاي عصبي رقابتي با آموزش بدون ناظر را بنام شبکه هاي خود سازمانده (Self-organizing features map) معرفي کرد[٩] . اين شبکه بيشترين شباهت را به پديده هاي زيستي دارد. اين روش بر اساس نظريه ”برنده همه چيز را ميبرد“ (WTA,winner takes all ) و ”برنده بيشتر ميبردر (winner takes most, WTM) بنا نهاده شده است . اين دو الگوريتم دراينجا بطور خلاصه شرح داده مي - شوند. رايج ترين نوع الگوريتم هاي آموزشي رقابتي ، WTA ميباشدکه در اين الگوريتم وقتي بردار ورودي (Input Pattern) به شبکه اعمال ميشود، فاصله اقليدسي آن ورودي از تمامي سلولهاي عصبي (neuron) تعريف شده براي شبکه ، محاسبه شده و نزديکترين اين سلولها به عنوان سلول برنده انتخاب ميشود. در مرحله اصلاح وزنها، تنها وزنهاي متصل به سلول برنده تتيير مييابند و بدين ترتيو سلول ، وزن هاي خود را به الگوي (pattern) ورودي نزديکتر ميکند و ساير وزنهاي متصل به سلولها بدون تتيير باقي ميمانند[٩-٨] . فرآيند آموزش در اين نوع شبکه توسط روابط زير قابل توصيف است . در ابتدا توسط رابطه (١) فاصله اقليدسي بردار ورودي را از تمامي سلول ها پيدا مي - کنيم . رابطه (٢) سلول با کمترين فاصله (سلول برنده) را مشخي ميکند. روابط (٣) و (٤) بترتيو معادپت مربوط به اصلاح وزنها در دوره ١+t براي وزنهاي سلول برنده و سلولهاي مير برنده ميباشند.
که نرا يادگيري و در بازه [١و ٠] است و به صورت خطي متناسو با معکوس t کاهش مي يابد و Wi کل وزنهاي متصل به سلول برنده را نشان مي دهد و x بردار ورودي است . اين الگوريتم ساده قابل توسعه ميباشد، بطوريکه در فرآيند آموزش علاوه بر سلول برنده، وزنهاي متصل به سلولهاي واقع در همسايگي سلول برنده نيز اصلاح شوند و در فرآيند آموزش شرکت داشته باشند. به الگوريتم اخير روش WTM گفته مي شود. به هر حال استراتژي WTM وکعيت همگرايي بهتري را نسبت به الگوريتم WTA ازخود نشان ميدهد. تنها تفاوت اين دو روش در اين است که در روش WTM تعداد سلولهاي بيشتري در فرآيند آموزش شرکت ميکنند و خود را با الگوي ورودي تطبيق ميدهند. روش اصلاح وزن سلولها بدين ترتيو است که وزنهاي متصل به سلول برنده بيشترين تتيير را در فرآيند آموزش به خود اختصاو مي - دهند و با دور شدن از سلول برنده نرا يادگيري کاهش مييابد.
الگوريتم تنظيم WTM توسط رابطه (٥) توصيف ميگردد:
که در آن Wi وزن هاي متصل به سلول برنده و سلول هاي واقع در همسايگيق آن را نمايش می دهبد. ردار x الگبوي ورودي و η نرا يادگيري و داراي مقدار مثت کبوچکتر از واحد است . تابع همسايگي را تعريف ميکند که يبک تبابع نزولبي وده و ا دور شبدن از سبلول برنبده و همچنين با گذشت زمان کاهش مي يابد و ين ترتيب و سلول واقع در دورترين همسايگي، کمترين تتيير وزنبي را خواهد داشت . اين تابع به صورت رابطه زير تعريبف می شود:
که در آن شعاع همسايگي و شامل سلول هاي واقع در همسايگي سلول برنده ميباشد. براي آموزش شبکه SOM فاصله اقليدسي بين بردار ورودي و بردارهاي وزني تمام سلولها بايد محاسبه شوند. سلولي که داراي کمترين فاصله با بردار ورودي است ، به عبارت ديگر سلولي که بيشترين شباهت را به الگوي ورودي دارد به عنوان برنده انتخاب و وزنهاي متصل به آن، جهت نزديک شدن به الگوي ورودي تتيير ميکند. همچنين سلولهاي همسايه نيز انتخاب و متناسو با فاصله آنها از سلول برنده وزن - هايشان در همان جهت اصلاح ميشوند. حرکت سلول ها و تعداد سلولهاي حرکتي در ابتداي الگوريتم زياد و در پايان به دليل کوچک شدن نرا يادگيري و شعاع همسايگي به کمترين حدق خود مي رسند. اين الگوريتم بردار ورودي را بر روي يک خط (در حالت توپولوژي يک بعدي ) و يا روي يک صفحه (در حالت توپولوژي دو بعدي ) مينگارد.
شکل (١) يک شبکه عصبي SOM دو بعدي را نمايش مي - دهد.
الگو هاي ورودي که شيه يکديگر هسبتند يعني کمترين فاصله اقليدسي را از يکديگر دارند، بعد از عمل نگاشت نيز در کنار يکديگر قرار ميگيرند. در شبکه يک بعدي هر سلول داراي ٢ همسايه ميباشد، يک همسايه در سمت چي و ديگري در سمت راست سلول قرار ميگيرد. در شبکه دو بعدي هر سلول داراي ٤ همسايه است که در سمت چي ، راست ، باپ و پايين سلول قرار ميگيرند.
شکلهاي (٢) و (٣) به ترتيو شبکه يک بعدي و دو بعدي را نشان ميدهند. همچنين شبکه هاي بيش از دو بعد نيز قابل تعميم و طراحي ميباشند، ولي در اين بين شبکه هاي دو بعدي معمول و رايج تر ميباشند.
الگوريتم اعمالي SOM در يک شبکه عصبي خودسازمانده بصورت زير خلاصه ميگردد[٩]:
١- وزن هاي تمام سلول ها را بصورت تصادفي انتخاب کنيد.
٢- الگوي ورودي را به شبکه اعمال کنيد.
٣- سلول برنده را پيدا کنيد.
٤- سلول هاي همسايه را انتخاب کنيد.
٥- وزنهاي متصل به سلول برنده و سلول هاي همسايه اش را متناسو با فاصله اقليدسي آنها و نرا يادگيري η و شعاع همسايگي اصلاح کنيد.
٦- مراحل ٢ تا ٥ را براي تعداد دوره هاي مشخي و از پيش تعيين شده تکرار کنيد.
٣- بررسي الگوريتم SOM براي حل TSP
ورودي شبکه شامل دو مقدار x و y است که موقعيت يک نقطه را در فضاي دوبعدي نمايش ميدهد. هر سلول نقطه اي
