مشکل با مسئله فروشنده دوره گرد
 

سلام دوستان

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

1- توی برنامه من هر شهر با کلیک کردن روی صفحه اضافه میشه و یک شماره شهر به اون داده میشه و یک مختصات X,Y مثل شکل زیر
http://up.iran-ps.com/images/559tsp1.jpg

حالا طبق اون چیزا هایی که من توی مقاله ها خوندم باید اولین کاری که انجام بدم قسمت Encoding هستش که به جند روش میشه انجام داد
1- کد مبنای دو (Binary)
2- روش کد گذاری جایگشتی Permutaion Encoding
3- روش کد گذاری مقدار Value Encoding
4- روش کد گذاری درختی Tree Encoding
من چیزی که بعد از خوندن مقالات دستگیرم شد این جند روش بود حالا توی این قست 2 تا سوال برام پیش میاد
الف )آیا استفاده از هر کدام از این روش ها در پیدا کردن جواب بهینه موثر است یا نه ؟
ب) بعد من کلا نهمیدم باید چی را کد کنم (شماره هر شهر - مختصات -فاصله تا شهر مجاور )

سوال دو :
در قسمت تشکیل جمعیت اولیه توی توضیح یک مقاله این حوری نوشته بود
در ابتدا حمعیت تصادفی از جواب های ممکن را تشکیل می دهیم
من فکر میکنم که برای حل این مسئله باد از روش جایگشت استفاده کنیم که بتونیم به جواب مسئله برسم یعنی شهر ها رو به چند حالت میشه کنار هم جید خوب ما اگه اینو میتونستم حساب کنم دیگه چه احتیاجی به استفاده از این الگوریتم است ؟

لطفا این دو قسمت رو برام توضیح بدید

با تشکر

یعنی کسی قبلا رو این موضوع کار نکرده ؟؟؟؟؟؟

سلام
ببینید در مسئله فروشنده دوره گرد شما باید کوتاهترین مسیری را بپیماید و در عین حال از هر شهر تنها یک بار بگذرد.اگر شما بخواهید این مسئله را با الگوریتم ژنتیک حل کنید در قسمت کدینگ شما باید مسیر هایتان را کد کنید مثلا اگر مسیری از شهر 1به 2به.... دارید آنگاه یک کروموزوم مثلا به صورت 1و2و.. دارید.حال بعد از کدینگ شما باید یک معیار برای برازش تعریف کنید واین معیار از روی شرایط مسئله تعیین می شود.مثلا دراین مسئله شما می توانید فاصله را معیار قرار دهید یعنی هر مسیر طول کمتری داشته باشد برازنده تر باشد وبرای مسیر هایی که از یک شهر دو بار می گذرند می توان برازش صفر در نظر گرفت.
اما الگوریتم ژنتیک در این مسئله کمی با جایگشت متفاوت است جایگشت خیلی کور عمل می کند اما در ژنتیک از این فرض استفاده می کند که احتمالا والدین خوب بچه های خوب دارند.تازه بحث جهش هم مطرح است. و اینها هم باز در ژنتیک ساده مطرح است در نسخه های بروز تر از کروموزوم ها مدل احتمالی ساخته می شودو...

ممنون که یه سوال من پاسخ دادید .
شما باید مسیر هایتان را کد کنید مثلا اگر مسیری از شهر 1به 2به.... دارید آنگاه یک کروموزوم مثلا به صورت 1و2و.. دارید
ببنید مثلا اگر من 100 نقطه داشته باشم هر نقطه میتونه به 99 نقطه دیگه وصل بشه ما که خودمون مسیر رو نمی کشیم فقط نقطه ها را مشخص میکنیم -حالا اگه این بخواد فقط برای قسمت کدینک بیاید همه این مسیر ها رو مشخص کنه که خیلی زیاد میشه -میشه یک مقدار بیشتر توضیح بدید

با تشکر

سلام
ببین برای یک حالت ساده شما مسیر ها یتان را کاملا به صورت تصادفی می سازید بدون توجه به اینکه آیا اصلا از این شهر به دیگری راه هست یانه ویا از یک شهر دو بار نمی گذریم و بعد اینها را در تابع برازش دخیل می کنید.دراین حالت شما احتیاج به جمعیت اولیه بیشتری دارید اما این به معنی ساختن همه جایگشت های ممکن نیست.شما مثلا می گویید من یک جمعیت 2000 تایی به صورت رندم درست می کنم و به الگوریتم می دهم اگر تعداد تکرار الگوریتم شما در حد مناسبی باشد دیگر لزومی ندارد نگران جمعیتی باشید که لحاظ نکردید زیرا آنها به احتمال زیاد بر اثر اعمالی مثل cross overیا mutatation تولید می شوند و اگر شایسته باشند در جمعیت های بعدی می مانند.

دوست عزیز واقعا ممنون که راهنمایی میکنید -
من با توجه به نوشته های شما تا اینجا به این شکل متوجه شدم -من مثال را برای 30 نقطه میزنم

من یک صفحه دارم که شبیه محور مختصات دکارتی هست و هر شهر یا نقطه یک x,y دارد
http://upload.wikimedia.org/wikipedi...system.svg.png
حالا من توی این صفخه 30 نقطه قرار میدم
http://up.iran-ps.com/images/147norand.jpg
حالا در این قسمت باید الگوریتم بصورت رندم یک تعداد نقطه رو از بین نقطه های موجود میکنه
http://up.iran-ps.com/images/777rand.jpg

فقط در این قسمت من 2 تا مسله رو نفهمیدم
1- این نقاط اتفاقی باید از بین نقاطی که ما ساختیم انتخاب بشه یا از هر جایی در دستگاه مختصات دکارتی میتونه انخاب بشه
2- قبل از انتخاب به صورت رندم باید فاصله هر شهر را با نقاط دیگه محاسبه کنیم یا بعد از انتخاب تصادفی

با تشکر

سلام
در ژنتیک مفهومی به نام کروموزوم داریم که در واقع یک راه حل کاندید برای مسئله مان است.هر کدام از این کروموزوم ها شامل مقادیری از خصوصیات مسئله هستند که آنها را ژن می نامیم.فرض کن می خواهیم نقطه ماکزیمم یک تابع را(در دو بعد) تخمین بزنیم.خوب اولین کاری که می کنیم تشکیل کروموزوم ها یا همان جواب های کاندید است هر کدام از این کروموزوم ها شامل دو ژن X1و X2 (مختصات نقاط )می باشند.مقادیر ژنها باید معتبر باشد(در مثال بالا همه مقادیر real معتبرند) اما در مثال فروشنده دوره گرد نه تنها مقادیر مختصات شهر ها معتبر هستند چون فروشنده می خواهد از شهر ها عبور کند چیزی که در این مسئله رندم انتخاب می شود ترتیب قرار گرفتن شهرها کنار هم است.مجموع فاصله شهر های یک کروموزوم تایع برازش می باشد

پس در این مرحله عملا کاری به فاصله بین شهر ها نداریم فقط اگر 30 تا شهر داریم ار عدد 1 تا 30 باید بصورت رندم این عداد رو کنار هم قرار بدیم
من از حر فهای شما این رو فهیمدم !!

با تشکر

دوستان میشه این تاپیک رو ادامه بدید لطفا

سلام

چند نکته را براتون جمع بندی می کنم.

در مورد کدگذاری یا بازنمائی استفاده از باینری برای این مساله اشتباه است چرا که هر شهر باید به اندازه 1Logn کد شود که هر کروموزومnLogn اندازه دارد و جهش هم رشته های غیر موجه تولید می کند و مسائل دیگر اصلاح و ...

پس بازنمائی می شود عدد صحیح و بصورت جایگشت به خاطر نوع مساله که از هر شهر فقط یک بار می گذریم
و تابع شایستگی می شود طول مسیر شهر ها به یکدیگر.
و عملگرهای ژنتیکی برای جایگشت می شود: بازترکیبی (order1; pmx; cycle; edge; modified edge ) و جهش (درج - تعویض - عکس - scramble)

مراحل کامل الگوریتم برای پیاده سازی:
1) تعيين روش بازنمايي

2) ايجاد جمعيت اوليه

3) تكرار تا برقراري شرط خاتمه()
3-1) ارزيابي جمعيت
3-2) انتخاب والدين
3-3) اعمال عملگرهاي ژنتيكي و توليد فرزندان
3-4) انتخاب بازماندگان

خوب جمعیت اولیه را تصادفی تولید می کنید که یک رشته می شود به اندازه 30 عدد تصادفی از 1تا 30 که مثلا 50 نسل اولیه تولید می کنید.(یعنی 50 رشته 30 تایی)
ارزیابی جمعیت هم مسافت شهرها را که به هم دارید با هم جمع می کنید.
انتخاب والدین یکی از الگوریتمهای (مبتنی بر شایستگی- مبتنی بر رتبه - تورنمنت) را استفاده می کنید.
بعد عملگرها را با یک درصدی اعمال می کنید(این مقدار معمولا برای بازترکیبی زیاد و برای جهش پایین است و بین 0 تا 1)
و انتخاب بازماندگان که همان الگوریتمهای انتخاب والدین است
و این کار را تا یک نسلی مثلا 500 بار ادامه می دهید

یک نکته را برای همه دوستان تاکید کنم که این دیگر یک الگوریتم ژنتیک نیست چون مثلا روش باینری برای بازنمائی استفاده نکردیم و یک الگوریتم تکاملی کلی است (البته یک تعبیری بین جامعه مهندسین وجود دارد که به همه این الگوریتمها ژنتیک می گویند ولی دانشمندان هوش به همه این الگوریتمها بطور کلی تکاملی می گویند و فقط آن چهار الگوریتم ga ; gp ; es ; ep ) دارای نام خاص هستند که ساختار خاصشان حفظ شود.