نمایش نتایج 1 تا 13 از 13

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

  1. #1

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

    سلام دوستان

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

  2. #2
    کاربر تازه وارد آواتار torisoft
    تاریخ عضویت
    اردیبهشت 1384
    محل زندگی
    مشهد
    پست
    53

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

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

    موفق باشید.

    یا علی

    TSP-GA

    assaf-ga.zip

  3. #3

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

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



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



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





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

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

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

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

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

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

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

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



    سوال دو :

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

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

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



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



    با تشکر

  4. #4
    کاربر تازه وارد آواتار torisoft
    تاریخ عضویت
    اردیبهشت 1384
    محل زندگی
    مشهد
    پست
    53

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

    نقل قول نوشته شده توسط NIMA_1981 مشاهده تاپیک
    سلام ممنون بابت لینک ها



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


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

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

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

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

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

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

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

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



    سوال دو :

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

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

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



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



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

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

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

    موفق باشید

    یا علی

  5. #5

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

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

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

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

    با تشکر

  6. #6
    کاربر تازه وارد آواتار torisoft
    تاریخ عضویت
    اردیبهشت 1384
    محل زندگی
    مشهد
    پست
    53

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

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

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

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

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

    موفق باشید

    یا علی

  7. #7

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

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

  8. #8
    کاربر تازه وارد آواتار torisoft
    تاریخ عضویت
    اردیبهشت 1384
    محل زندگی
    مشهد
    پست
    53

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

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

    موفق باشید

    یا علی
    آخرین ویرایش به وسیله torisoft : پنج شنبه 08 اردیبهشت 1390 در 23:10 عصر

  9. #9

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

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

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



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



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



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





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

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

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



    با تشکر

  10. #10
    کاربر تازه وارد آواتار torisoft
    تاریخ عضویت
    اردیبهشت 1384
    محل زندگی
    مشهد
    پست
    53

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

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

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

    موفق باشید.

    یا علی

  11. #11
    کاربر دائمی آواتار BOB
    تاریخ عضویت
    خرداد 1383
    محل زندگی
    http://www.mshams.ir
    پست
    450

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

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

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

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

    این لینک را حتما ببینید

  12. #12

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

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

  13. #13
    کاربر دائمی آواتار BOB
    تاریخ عضویت
    خرداد 1383
    محل زندگی
    http://www.mshams.ir
    پست
    450

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

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

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •