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

بسم الله الرحمن الرحیم

ارائه یک شبکه عصبی فازی ژنتیکی جدید برای حل مساله فروشنده دوره گرد

شرح مساله فروشنده دوره گرد
مساله فروشنده دوره‏گرد (Traveling Salesman Problem)

روش های متداول برای حل TSP
الگوریتم های کلاسیک جستجوی محلی
بازپخت تطبیقی
شبکه های عصبی مصنوعی
الگوریتم های ژنتیکی
برنامه نویسی تکاملی
سیستم کولونی مورچه ها
روش های آموزش افزایشی مبتنی بر جمعیت
Fine-tuned learning
کوهونن
هاپفیلد
بولین
آشوبی
CNN-TSP

شبکه عصبی CNN-TSP
یک شبکه عصبی چهار لایه
دارای دو بخش بهینه ساز و سازنده

الگوریتم آموزش CNN-TSP
الگوریتم آموزش دارای دو فاز است:
فاز سازنده: در این مرحله، شبکه با اضافه شدن شهرهای جدید به مسیر توسعه می یابد.
فاز بهینه ساز: با جابجایی شهرهای موجود بر روی مسیر، مسیر فعلی بهبود می یابد.
مزایای CNN-TSP در مقایسه با کوهونن:
.سرعت همگرایی CNN-TSP در حدود 20 برابر کوهونن
طول پاسخ های CNN-TSP به طور متوسط (برای مسیرهای 50 شهری) در مقایسه با کوهونن، 2.5% کوتاهتر است.

بهبود CNN-TSP با استفاده از منطق فازی
عامل موثر بر پاسخ های CNN-TSP
در هر مرحله از فاز سازنده کدام شهر در مسیر قرار گیرد.
تصمیم گیرنده رقابتی
در نرون های لایه های سوم و چهارم تعیین می شود که کدام نرون باید در کجای مسیر قرار گیرد
عامل موثر بر این انتخاب افزایش طول ایجاد شده، با اضافه شدن شهر جدید به مسیر است.
الگوریتم های ژنتیکی

بهبود CNN-TSP با استفاده از منطق فازی
تصمیم گیرنده فازی
افزایش طول ایجاد شده که توسط نرونهای لایه سوم محاسبه می شود.
.طول کمان برنده که توسط نرون آستانه محاسبه می شود.
ورودی ها
ارزش هر یک از شهرها
خروجی
توابع عضویت ورودی و خروجی

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

طراحی پایگاه قواعد با استفاده از الگوریتم های ژنتیکی
شکل کلی یک قانون در پایگاه داده
اگر عضو mf(i) و (یا) عضو mf(j) باشد، آنگاه خروجی عضو mf(k) شود و ارزش این قانون w است.
ساختار کلی یک کروموزوم
هر کروموزوم دارای 27 ژن است.
هر ژن بیانگر یک قانون است.
هر ژن، برداری به شکل (i j k w c) است.
cمی تواند یکی از دو مقدار یک یا دو باشد. یک یعنی ترکیب دو بخش مقدم قانون با یک t-norm و دو یعنی ترکیب دو بخش مقدم قانون با یک s-norm.
هر کروموزوم ماتریسی 5*27 است که سطر آن بیانگر یک قانون فازی می باشد.
به منظور کاهش حجم محاسبات از سیستم فازی ممدانی با موتور استنتاج ضرب، فازی‏ساز منفرد، غیر فازی‏ساز میانگین مراکز، t-norm ضرب و s-norm جمع جبری استفاده گردید.

طراحی پایگاه قواعد با استفاده از الگوریتم های ژنتیکی
عملگر برش
عددی تصادفی n بین 1 و 27 انتخاب می شود.
n ژن از هر یک از والدین انتخاب و جای آنها با یکدیگر عوض می شود.
قبل از جابجایی ژن ها بین دو ولی بر روی عناصر چهارم ژن های متناظر عملگر برش یک نقطه ای حقیقی اعمال می شود.
عملگر جهش
چنانچه عدد تصادفی تولید شده برای هر ژن کمتر از احتمال جهش باشد، ژن مذکور با ژنی که به صورت تصادفی ایجاد شده عوض می شود.
عملگر انتخاب والدین: Tournament
تولید نسل جدید
تولید نسل جدید مشابه با Genitor با جایگذاری یکی از فرزندان بجای بدترین کروموزوم جمعیت قبلی و جایگذاری دیگری بجای بدترین کروموزوم جمعیت مسابقه انجام می شود.

طراحی پایگاه قواعد با استفاده از الگوریتم های ژنتیکی
تابع هزینه
جمله اول سبب کاهش طول متوسط پاسخ های FNN-TSP نسبت به CNN-TSP می شود.
جمله دوم سبب می شود، الگوریتم ژنتیکی به ازای هر پاسخ بدتر FNN-TSP نسبت به CNN-TSP جریمه شود.
برای ارزیابی کیفیت پایگاه قواعد از 20 توزیع 100 شهری استفاده گردید.
انتخاب تابع هزینه فوق به منظور افزایش کیفیت پایگاه قواعد در تعمیم نتایج بوده است.
U تابع پله واحد
مشاهدات تجربی نشان داد که نرون برنده معمولا یکی از 20 شهری است که کمترینرا دارا هستند. بنابراین جهت کاهش حجم محاسبات و همچنین افزایش کارایی الگوریتم ژنتیکی تنها این نرونها جهت تصمیم‏گیری وارد سیستم فازی شدند.
جهت حفظ پراکندگی جمعیت تنها کروموزوم های فرزندی وارد جمعیت می شوند که پاسخ تابع هزینه به آنها با پاسخ دیگر کروموزوم های جمعیت متفاوت باشد.

شبیه سازی
احتمال جهش: 01/0
خطای متوسط پایگاه قواعد نهایی به نمونه های آموزشی: 70/1%-
اندازه جمعیت مسابقه: 7
اندازه جمعیت: 50
منحنی های مقدار تابع هزینه برای بهترین و بدترین عضو جمعیت

شبیه سازی
برای بررسی عملکرد FNN-TSP، پاسخهای آنرا برای 100 توزیع 50 شهری، 100 توزیع 60 شهری، … و 100 توزیع 250 شهری با CNN-TSP مقایسه نمودیم.
قبل از میانگین گیری از طول پاسخ های هر یک از شبکه ها، مسیرها نرمالیزه شده اند.

شبیه سازی

پایان