مسئله فروشنده دوره‌گرد با استفاده از الگوریتم ژنتیک

[NIMA_1981]

سلام دوستان

میشه یک مقدار در مورد نوشتم برنامه برای حل مسئله فروشنده دوره‌گرد با استفاده از الگوریتم ژنتیک توضیح بدید
http://upload.wikimedia.org/wikipedia/commons/5/57/Example_The_travelling_salesman_problem_(TSP)_pena lty_cost_1.gif

[torisoft]

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

موفق باشید.

یا علی

TSP-GA (http://www.codeproject.com/KB/recipes/tspapp.aspx)

69125

[NIMA_1981]

سلام ممنون بابت لینک ها



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



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

http://up.iran-ps.com/images/559tsp1.jpg



حالا طبق اون چیزا هایی که من توی مقاله ها خوندم باید اولین کاری که انجام بدم قسمت Encoding هستش که به جند روش میشه انجام داد

1- کد مبنای دو (Binary)

2- روش کد گذاری جایگشتی Permutaion Encoding

3- روش کد گذاری مقدار Value Encoding

4- روش کد گذاری درختی Tree Encoding

من چیزی که بعد از خوندن مقالات دستگیرم شد این جند روش بود حالا توی این قست 2 تا سوال برام پیش میاد

الف )آیا استفاده از هر کدام از این روش ها در پیدا کردن جواب بهینه موثر است یا نه ؟

ب) بعد من کلا نهمیدم باید چی را کد کنم (شماره هر شهر - مختصات -فاصله تا شهر مجاور )



سوال دو :

در قسمت تشکیل جمعیت اولیه توی توضیح یک مقاله این حوری نوشته بود

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

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



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



با تشکر

[torisoft]

سلام ممنون بابت لینک ها



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


حالا طبق اون چیزا هایی که من توی مقاله ها خوندم باید اولین کاری که انجام بدم قسمت Encoding هستش که به جند روش میشه انجام داد

1- کد مبنای دو (Binary)

2- روش کد گذاری جایگشتی Permutaion Encoding

3- روش کد گذاری مقدار Value Encoding

4- روش کد گذاری درختی Tree Encoding

من چیزی که بعد از خوندن مقالات دستگیرم شد این جند روش بود حالا توی این قست 2 تا سوال برام پیش میاد

الف )آیا استفاده از هر کدام از این روش ها در پیدا کردن جواب بهینه موثر است یا نه ؟

ب) بعد من کلا نهمیدم باید چی را کد کنم (شماره هر شهر - مختصات -فاصله تا شهر مجاور )



سوال دو :

در قسمت تشکیل جمعیت اولیه توی توضیح یک مقاله این حوری نوشته بود

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

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



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



با تشکر

1- الف ) بسته به نوع Option هائی که در الگوریتم ژنتیک استفاده می کنید ممکن است در جواب تاثیر گذار باشد.

1- ب ) معمولا فاصله تا شهر مجاور کد می شود و یکی از روش های محاسبه فاصله معمول فاصله همینگ است.

2- اولا اینکه به چند طریق میشه کنار هم چید ربطی به بدست آوردن جواب بهینه ندارد اینکه فاصله کم باشد و تمام شهرها طی شوند مهم است. دوما با استفاده از این الگوریتم در سریعترین حالت ممکن به جواب بهینه می رسید. سوما انعطاف پذیری این الگوریتم باعث می شود پارامتر ها و Option های بروز را وارد الگوریتم کرد.

موفق باشید

یا علی

[NIMA_1981]

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

حوب اینجوری که خیلی جواب را باید کد گنه جون هر نقطه می تونه به همه نقطه ها وصل بشه این مشکل رو چطوری حل میکنه نو این سیستم

و در مورد قسمت دوم سوالم متوجه حواب شما نشدم

ما باید از جه چیز هایی حمعیت اولیه رو بسازیم

با تشکر

[torisoft]

حوب اینجوری که خیلی جواب را باید کد گنه جون هر نقطه می تونه به همه نقطه ها وصل بشه این مشکل رو چطوری حل میکنه نو این سیستم

و در مورد قسمت دوم سوالم متوجه حواب شما نشدم

ما باید از جه چیز هایی حمعیت اولیه رو بسازیم

با تشکر

خوب این همون مزیت الگوریتم های تکاملی از جمله ژنتیکه. اصلا مهم نیست چه تعداد باید کد بشن الگوریتم سریعتر از اونچه که فکر می کنید به جواب می رسد. خود الگوریتم جواب رو پیدا می کنه.
در مورد جمعیت اولیه باید ببینید جواب شما بین چه بازه ای حرکت می کنه بین همون بازه بصورت رندوم به تعداد دلخواه جمعیت ایجاد کنید. هرچی تعداد جمعیت بیشتر باشد جواب بهینه بهتر است ولی سرعت برنامه کندتر می شود. اگه کد کردن شما بصورت باینری یا همون فاصله همینگ باشه جمعیت اولیه هم باید بصورت باینری ایجاد بشه. در مورد باینری لازم به ایجاد بازه نیست چون با یه بیت تغییر ممکنه از بازه خارج بشه . لذا با تعیین طول رشته مثلا 10 بصورت رندم اینن تعداد بیت رو تغییر میدید به تعداد جمعیت اولیه.

موفق باشید

یا علی

[NIMA_1981]

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


ااقا من نیمدونم چرا این قسمت رو درک نیمکنم -ببنید -الگوریتم رو ما باید خودمون بنویسم پش اگه کاری بخواد انجام بشه باید کد نوشته بشه - حالا اگه مثلا ما 100 نقطه داشته باشیم هر نقطه به 99 شهر دیگه وصل میشه واگه اینو باری 100 شهر حساب کنیم یک عدد بزرگی میشه میشه بگید توی این قسمت را ه حل چیه

[torisoft]

ااقا من نیمدونم چرا این قسمت رو درک نیمکنم -ببنید -الگوریتم رو ما باید خودمون بنویسم پش اگه کاری بخواد انجام بشه باید کد نوشته بشه - حالا اگه مثلا ما 100 نقطه داشته باشیم هر نقطه به 99 شهر دیگه وصل میشه واگه اینو باری 100 شهر حساب کنیم یک عدد بزرگی میشه میشه بگید توی این قسمت را ه حل چیه

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

موفق باشید

یا علی

[NIMA_1981]

دوست عزیز واقعا ممنون که راهنمایی میکنید -

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



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

http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Cartesian-coordinate-system.svg/250px-Cartesian-coordinate-system.svg.png

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

http://up.iran-ps.com/images/147norand.jpg

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

http://up.iran-ps.com/images/777rand.jpg



فقط در این قسمت من 2 تا مسله رو نفهمیدم

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

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



با تشکر

[torisoft]

در مورد سوال اول این بستگی به خود شما و اون چیزی که مسئله ازتون خواسته داره یعنی اگه می خواید بین نقاطی که ایجاد کردید چند نقطه به صورت رندم انتخاب بشه خوب اون کارو بکنید اگرم میخواید تو دستگاه چند نقطه انتخاب بشن که اصلا لازم نیست نقاط اولیه تشکیل بدید از همون اول چند نقطه رندم درست کنید.

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

موفق باشید.

یا علی

[BOB]

ااقا من نیمدونم چرا این قسمت رو درک نیمکنم -ببنید -الگوریتم رو ما باید خودمون بنویسم پش اگه کاری بخواد انجام بشه باید کد نوشته بشه - حالا اگه مثلا ما 100 نقطه داشته باشیم هر نقطه به 99 شهر دیگه وصل میشه واگه اینو باری 100 شهر حساب کنیم یک عدد بزرگی میشه میشه بگید توی این قسمت را ه حل چیه

سلام

مهمترین ویژگی ژنتیک استفاده از جستجوی تصادفی هدفمند است. یعنی اگر تمام جایگشتهای یک پاسخ n حالت باشند (و حتما n عدد بسیار بزرگی است که ما میخواهیم از ژنتیک استفاده کنیم) ، الگوریتم ژنتیک تنها درصد کوچکی از این n حالت را به صورت تصادفی تست میکند، اما از آنجا که روش تصادفی هدفمندی دارد، پس از محاسبه پاسخ تصادفی، ما احتمال میدهیم که پاسخ مناسبی بدست آمده باشد.

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

این لینک را حتما ببینید (http://www.mshams.ir/programs/gatsp)

[اس کا م]

سلام یه سوال مهم پیچیدگی الگوریتم فروشنده دوره گرد با الگوریتم ژنتیک چیه؟؟ خواهش می کنم هر چه زودتر منو راهنمایی کنین

[BOB]

برای الگوریتمهای تکاملی، معمولا پیچیدگی زمانی محاسبه نمیشود چون ذات آنها تصادفی است.
معمولا از مقایسه ارزیابی با اعلام تمام پارامترهای متغیر استفاده میکنند