naeimwtg

سلام دوستان

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

1- توی برنامه من هر شهر با کلیک کردن روی صفحه اضافه میشه و یک شماره شهر به اون داده میشه و یک مختصات X,Y مثل شکل زیر


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

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

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

با تشکر

naeimwtg

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

astudio

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

__________________

naeimwtg

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

با تشکر

astudio

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

__________________

naeimwtg

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

من یک صفحه دارم که شبیه محور مختصات دکارتی هست و هر شهر یا نقطه یک x,y دارد

حالا من توی این صفخه 30 نقطه قرار میدم

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


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

با تشکر

astudio

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

__________________

naeimwtg

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

با تشکر

naeimwtg

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

aminkop

سلام

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

در مورد کدگذاری یا بازنمائی استفاده از باینری برای این مساله اشتباه است چرا که هر شهر باید به اندازه 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 ) دارای نام خاص هستند که ساختار خاصشان حفظ شود.