Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > محاسبات نرم > الگوریتم ژنتیک(Genetic Algorithm)


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۲-۳-۱۳۹۰, ۰۹:۲۱ قبل از ظهر   #1 (لینک دائم)
عضو فوق فعال
 
آواتار naeimwtg
 
تاريخ عضويت: بهمن ۱۳۸۸
محل سكونت: مسکو
پست ها: 34
تشكرها: 5
1 تشكر در 1 پست
Send a message via Skype™ to naeimwtg
پيش فرض مشکل با مسئله فروشنده دوره گرد

سلام دوستان

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

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


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

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

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

با تشکر
naeimwtg آفلاين است   پاسخ با نقل قول

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۰۲-۷-۱۳۹۰, ۰۶:۰۲ بعد از ظهر   #2 (لینک دائم)
عضو فوق فعال
 
آواتار naeimwtg
 
تاريخ عضويت: بهمن ۱۳۸۸
محل سكونت: مسکو
پست ها: 34
تشكرها: 5
1 تشكر در 1 پست
Send a message via Skype™ to naeimwtg
پيش فرض

یعنی کسی قبلا رو این موضوع کار نکرده ؟؟؟؟؟؟
naeimwtg آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۷-۱۳۹۰, ۰۶:۴۰ بعد از ظهر   #3 (لینک دائم)
Active users
 
آواتار astudio
 
تاريخ عضويت: خرداد ۱۳۸۹
پست ها: 48
تشكرها: 4
50 تشكر در 31 پست
پيش فرض

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



نه چندان بزرگم

که کوچک بیابم خودم را

نه آنقدر کوچک

که خود را بزرگ...

گریز از میانمایگی

آرزویی بزرگ است؟
astudio آفلاين است   پاسخ با نقل قول
از astudio تشكر كرده اند:
naeimwtg (۰۲-۸-۱۳۹۰), zmmhmmdrz (۰۲-۷-۱۳۹۰)
قديمي ۰۲-۸-۱۳۹۰, ۰۹:۱۳ قبل از ظهر   #4 (لینک دائم)
عضو فوق فعال
 
آواتار naeimwtg
 
تاريخ عضويت: بهمن ۱۳۸۸
محل سكونت: مسکو
پست ها: 34
تشكرها: 5
1 تشكر در 1 پست
Send a message via Skype™ to naeimwtg
پيش فرض

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

با تشکر
naeimwtg آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۸-۱۳۹۰, ۱۱:۳۰ قبل از ظهر   #5 (لینک دائم)
Active users
 
آواتار astudio
 
تاريخ عضويت: خرداد ۱۳۸۹
پست ها: 48
تشكرها: 4
50 تشكر در 31 پست
پيش فرض

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



نه چندان بزرگم

که کوچک بیابم خودم را

نه آنقدر کوچک

که خود را بزرگ...

گریز از میانمایگی

آرزویی بزرگ است؟
astudio آفلاين است   پاسخ با نقل قول
از astudio تشكر كرده است:
naeimwtg (۰۲-۹-۱۳۹۰)
قديمي ۰۲-۹-۱۳۹۰, ۰۱:۳۱ قبل از ظهر   #6 (لینک دائم)
عضو فوق فعال
 
آواتار naeimwtg
 
تاريخ عضويت: بهمن ۱۳۸۸
محل سكونت: مسکو
پست ها: 34
تشكرها: 5
1 تشكر در 1 پست
Send a message via Skype™ to naeimwtg
پيش فرض

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

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

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

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


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

با تشکر
naeimwtg آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۹-۱۳۹۰, ۱۰:۰۸ قبل از ظهر   #7 (لینک دائم)
Active users
 
آواتار astudio
 
تاريخ عضويت: خرداد ۱۳۸۹
پست ها: 48
تشكرها: 4
50 تشكر در 31 پست
پيش فرض

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



نه چندان بزرگم

که کوچک بیابم خودم را

نه آنقدر کوچک

که خود را بزرگ...

گریز از میانمایگی

آرزویی بزرگ است؟
astudio آفلاين است   پاسخ با نقل قول
از astudio تشكر كرده اند:
Astaraki (۰۲-۹-۱۳۹۰), naeimwtg (۰۲-۹-۱۳۹۰)
قديمي ۰۲-۹-۱۳۹۰, ۱۰:۰۶ بعد از ظهر   #8 (لینک دائم)
عضو فوق فعال
 
آواتار naeimwtg
 
تاريخ عضويت: بهمن ۱۳۸۸
محل سكونت: مسکو
پست ها: 34
تشكرها: 5
1 تشكر در 1 پست
Send a message via Skype™ to naeimwtg
پيش فرض

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

با تشکر
naeimwtg آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۱۳-۱۳۹۰, ۱۱:۵۶ قبل از ظهر   #9 (لینک دائم)
عضو فوق فعال
 
آواتار naeimwtg
 
تاريخ عضويت: بهمن ۱۳۸۸
محل سكونت: مسکو
پست ها: 34
تشكرها: 5
1 تشكر در 1 پست
Send a message via Skype™ to naeimwtg
پيش فرض

دوستان میشه این تاپیک رو ادامه بدید لطفا
naeimwtg آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۱۳-۱۳۹۰, ۰۲:۳۱ بعد از ظهر   #10 (لینک دائم)
Active users
 
آواتار aminkop
 
تاريخ عضويت: آبان ۱۳۸۸
پست ها: 45
تشكرها: 7
123 تشكر در 35 پست
پيش فرض

سلام

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

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

ويرايش شده توسط aminkop; ۰۲-۱۳-۱۳۹۰ در ساعت ۰۲:۴۵ بعد از ظهر
aminkop آفلاين است   پاسخ با نقل قول
از aminkop تشكر كرده است:
kian_abdollahi (۰۳-۲۸-۱۳۹۰)
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۱۰:۵۹ قبل از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design