مکاترونیک

1-     مقدمه

بنابراین هدف از انتقال و برطرف کردن مسئله‏ی فروشنده به شرح زیر می‏باشد: ارائه‏ی یک مجموعه‏ی شهرهای n و هزینه‏های انتقال بین تمامی جفت‏های شهرها، ارائه‏ی نزدیک‏ترین مسیر  برای دیدن شهر و بازگشت به شهر اولیه. این مسئله مثال راهنمای خیلی سختی می‏باشد. فضای جستجوی آن بسیار بزرگ است  (n!)و باعث به وجود آمدن برخی مشکلات مهندسی می‏شود، همانند طراحی VLSI، نیاز به 1.2 میلیون شهر و یک روش ادراکی مؤثر و سریع می‏باشد.

در این مقاله، یک الگوریتم که بر پایه شبکه‏های عصبی طراحی شده است ارائه داده‏ایم و آن را با روش ادراکی مؤثر مقایسه کرده‏ایم: الگوریتم تکاملی با اپراتور ترکیب مجدد لبه‏ای بهینه‏سازی شده.

2-نقشه‏ی خودسازمانی Kohonen برای استفاده در TSP

در سال 1975، آقای تیووکوهن یک نوع جدید از شبکه‏های عصبی را معرفی کرد که از روش‏های آموزشی و یادگیری بدون نظارت رقابتی استفاده می‏کرد. اصول الگوریتم به کارگیری شده بر مبنای تطبیق یک شبکه‏ی خاص با یک مجموعه‏ی سازماندهی نشده و اطلاعات نامشخص بوده است. بعد از فاز آزمایشی تمرینی، این شبکه برای انجام فرایندهای کلاس‏بندی ساده و انبوه مورد استفاده قرار می‏گیرد.

نتایج دلخواه و مورد نظر فرایند خودسازمانی را می‏توان با استفاده از شبکه‏هایی که دارای یک بردار ورودی 2 بعدی و یک همسایه‏ی مجاور تک بعدی هستند به دست آورد. در این مورد ورودی برای شبکه‏ی مورد نظر می‏تواند به عنوان یک مختصات در فضای 2 بعدی x و y در نظر گرفته شود. با استفاده از این تکنیک، می‏توان یک خط بر روی تصویر باینری اختیاری را رسم کرد. علاوه بر آن، اگر فردی یک الگوریتم با اعداد مشابه نرون‏ها و به عنوان تعداد شهرها ارائه کرد، این سیستم یک تور مؤثر و مناسب از شهرها در خروجی ارائه خواهد کرد: این فرایند در شکل 1 نشان داده شده است

شکل 1-این مثال حاوی 6 میدان می‏باشد. اولین میدان بخشی را نشان می‏دهد که یاد گرفته شده است. دومین میدان نشان‏دهنده‏ی شبکه است و فقط بعد از انجام فرایند تصادفی سازی تمامی وزن‏های عصبی این کار را انجام می‏دهد. میدان‏های بعدی نشان‏دهنده‏ی فرایندهای یادگیری می‏‏باشند. لطفا به این مورد توجه داشته باشید که هر دایره ارائه دهنده‏ی نقطه‏ای است که مختصات آن برابر است با وزن‏های مربوط به نرون

3-بهینه‏سازی

همانند موردی که در بالا به آن اشاره شد، برای ارائه‏ی یک راه حل، دو مسئله است که برای اصلاح نتایج باید صورت بپذیرد. اولین مسئله این است: به خاطر اینکه الگوریتم بر مبنای هشدار وزن‏های واقعی دایره‏ها کار می‏کند شاید هیچ‏گاه مقدار واقعی را که منطبق با مختصات شهرها باشد، به دست نیاورد. بنابراین یک فرایند ساده برای بهینه‏سازی نقشه‏برداری 1-1 بین شهرها و نرون‏ها واحد ایجاد می‏شود.

اما دیگر فرایند بهینه‏سازی و بهبود‏سازیی که می‏توان به آن دست پیدا کرد، به کارگیری یک الگوریتم opt-2 بسیار سریع و مشهود می‏باشد. این الگوریتم بر مبنای جفت‏های عمل مجدد[1] مسیرهایی که شهرها را در حالتی که ارائه کننده‏ی تورهای کلی ارزان‏تر هستند، به یکدیگر متصل می‏کنند. الگوریتمopt-2 راه حل‏های بهینه‏سازی محلی را ارائه می‏کند و هنگامی که آرایش‏بندی شهرها را به صورت تصادفی آغاز می‏کند، نتایج کاملی را ارائه نمی‏کند. اما به هر حال در گذشته و به عنوان یک راه حل مناسب مورد استفاده قرار می‏گرفت.

4- آزمایش:

  دو نوع آزمایش تحت مدیریت و کنترل قرار گرفته است: استفاده از شهرهایی که از TSPLIB گرفته شده‏اند و استفاده از شهرهای انتخابی و استفاده از مجموعه‏ی شهرهای به صورت تصادفی. TSPLIB کاملا سخت و دشوار است. دلیل این امر هم این است که در بسیاری از موارد شهرها به صورت تصادفی انتخاب نمی‏شوند. معمولا مجموعه‏های شهری بزرگ‏تر شامل الگوهای کوچک‏تری هستند. بنابراین در هر الگوی کوچک‏تر تور بهینه به صورت یکسان می‏باشد. به بیان دیگر، سیستم SOM سعی می‏کند یک تور منحصر به خود را در هر الگوی کوچک‏تر، شکل‏بندی کند.

آزمایش به کارگیری تصادفی شهرهای انتخاب شده بسیار هدفمند است. این آزمایش بر اساس مدل Held-Karp طراحی شده است که یک ارتباط تجربی بین طول تور مورد نظر، تعداد شهرها و نواحی میدانی که آن شهرها در آن قرار گرفته‏اند می‏باشد.

در این آزمایش، سه مجموعه‏ی شهری تصادفی مورد استفاده قرار گرفته است. طول بعدی حوزه‏ی میدانی برابر با 500 بوده است.

تمامی آمارهای مورد استفاده در SOM بعد از 50 بار اجرا در مجموعه‏های شهری تهیه و تولید شده‏اند. متوسط طول تور برای مجموعه‏های شهری برای حداکثر 2000 شهر در حدود 5 تا 6 درصد بدتر از مقدار بهترین حالت است.

دستاوردها و نتایج SOM می‏تواند راه‏حل‏هایی را ارائه کند که همواره و تقریباً 10 درصد کم‏تر و بدتر از تور بهترین حالت می‏باشد، اما به هر حال در بیشتر موارد، تفاوت درصد بسیار کمی را شامل می‏شود.

مجموعه‏ی سیستم SOM با مجموعه‏یEA جفت شده با اپراتور ترکیب مجدد لبه‏ای بهینه شده، انتخاب ریسکی حالت پایدار، انتخاب اعضای تورنمنت با اندازه‏ی تورنمنت که بستگی به تعداد شهرها و میزان جمعیت دارد، مقایسه می‏شود. رمز گذاری دو طرفه مورد استفاده قرار گرفته است. نرخ بهینه‏سازی دو طرفه به مقدار شهرها و حالت‏های ارزیابی بستگی دارد. بنابراین نرخ دو طرفه خودتطبیقی مورد استفاده قرار گرفته است. هر نوع ژن[2] دارای نرخ دو طرفه مختص به خود است. در یک مسیر مشابه و به عنوان استراتژی ارزیابی تعدیل و اصلاح شده است. این استراتژی به صورت اتوماتیک، نرخ دو طرفه را با تعداد شهرها و حالت ارزیابی تطبیق می‏دهد، پس نیازی نیست تا به صورت دستی پارامترهایی را که برای هر مجموعه‏ی شهری بهینه هستند، چک کرد.

زمانی که جمعیت به یکدیگر ملحق می‏شوند، فرایند ارزیابی متوقف می‏گردد. میزان جمعیت 1000 تعیین شده است. هنگامی که کار سیستم EA متوقف می‏گردد، با استفاده از الگوریتم opt-2 ، بهترین حالت و راهکار آن، بهینه‏سازی می‏گردد. نتایج مربوط به هر دو سیستمSOM و EAدر جدول شماره‏ی 1 نشان داده شده است.

بعد از 50 اجرا در هر مجموعه‏ی شهری، تمامی آمارهای متعلق به SOM تولید می‏شوند. برای EA 10 اجرا الگوریتم برای مجموعه‏ها وجود دارد: EIL101,EIL51 و RAND100 برای دیگر مجموعه‏ها EA فقط یکبار اجرا می‏گردد.

راهکارهای بهینه برای تمامی مثال‏ها از TSPLIB که از قبل ارائه شده بود، گرفته شده است و از طرف دیگر راهکارهای بهینه برای مثال‏های  تصادفی از ارتباط تجربی توضیح داده شده در بالا مورد محاسبه قرار گرفته است. تمامی محاسبات بر روی پردازشگر AMD Athlon 64-bit 3500+صورت می‏گیرد.

جدول شماره 1-نتایج تجربی