Artificial Intelligence - هوش مصنوعی

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)
-   حل مسائل معروف هوش مصنوعي (http://artificial.ir/intelligence/forum102.html)
-   -   حل مسئله فروشنده دوره گرد(tsp) به روش هاي مختلف (http://artificial.ir/intelligence/thread860.html)

Astaraki ۰۹-۳-۱۳۸۸ ۱۲:۵۲ بعد از ظهر

حل مسئله فروشنده دوره گرد(tsp) به روش هاي مختلف
 
مسئله فروشنده دوره‌گرد (به انگلیسی: Travelling salesman problem ، به‌اختصار: TSP )

http://upload.wikimedia.org/wikipedi...x-Salesman.PNG

اگر فروشنده دوره‌گرد از نقطه A شروع کند و فواصل بین نقاط مشخص باشد، کوتاه‌تربن مسیر که از تمام نقاط یکبار بازدید می‌کند و به A بازمی‌گردد کدام است؟
........
مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد این مسئله اولین بار توسط دو دانشمند به نام های 1- هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد . معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شود و در دروسی نظیر تئوری گراف می توانید مطالب مشابه را نیز بدست آورید .

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

پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد
این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می شود اما اگر به روش برنامه نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن (O(n^2*2^n خواهد شد که جز مرتبه های نمایی است. باید توجه داشت علی رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می باشد .
..............
شبه کد الگوریتم فوق بصورت زیر است که در آن تعداد زیر مجموعه های یک مجموعه n عضوی 2 به توان n می باشد
و for اول یک ضریب n را نیز حاصل می شود که به ازای تمام شهرهای غیر مبدا می باشد و حاصل (n*(2^n را پدید می آورد
بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه n داریم که در زمان فوق نیز ضرب می شود و در نهایت زمان (n^2)*(2^n) را برای این الگوریتم حاصل می کند

كد:

C({1},1) = 0
for (S=2 to n )
for All Subsets S subset of {1,2,3,...} of size S and containing 1
C(S,1) = &
for All J member of S , J<>1
C ( S , J ) = min { C ( S - { J } , i ) + D i,J : i member of S , i <> J }
return min j C ( {1 . . . n}, J ) + D J,1

.............
اين مسئله ، مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
شرح مسئله بدین شکل است:
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
تعداد کل راه‌حل‌ها برابر است با برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.

مسئله‌های مرتبط

مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP ) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاٌ از یک شهر عبور کند. این مسئله به « مسئله سیاست‌مدار مسافر» نیز شهرت دارد.

الگوریتم‌ها
مسئله فروشنده دوره‌گرد جزء مسائل NP-hard است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
استفاده از الگوریتم‌های مکاشفه‌ای که جواب‌هایی به‌دست می‌دهد که احتمالاٌ درست هستند.
پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.

الگوریتم‌های دقیق
سرراست ترین راه حل امتحان کردن تمامی جایگشت‌های ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی n22n حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.

الگوریتم‌های مکاشفه‌ای
الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آنها را به صورت زیر دسته‌بندی کرد:
مکاشفه‌ای سازنده
بهبود تکراری
مبادله دوبه‌دو
مکاشفه‌ای k-opt
مکاشفه‌ای V-opt
بهبود تصادفی

Astaraki ۰۹-۳-۱۳۸۸ ۱۲:۵۶ بعد از ظهر

ابتدا سايتهايي که کدهاي حل اين مسئله را از روش هاي متفاوت و زبانهاي مختلف ارائه کرده اند:

http://delphiforfun.org/programs/_de...er2010_bnr.gif

Source Code Library: Travelling Salesman Problem (TSP

Solving Travelling Salesman Problems Using Genetic Algorithms


Solution to Travelling Salesman Problem

:)

Astaraki ۰۹-۳-۱۳۸۸ ۰۲:۴۶ بعد از ظهر

1(ها)ضميمه
روش ابتکاری ساخت و بهبود تور مسئله فروشنده دوره گرد نامتقارن
:rolleyes:

Astaraki ۰۹-۴-۱۳۸۸ ۱۰:۱۰ قبل از ظهر

1(ها)ضميمه
کد حل مساله فروشنده دوره گرد با الگوريتم ژنتيک

Astaraki ۰۹-۱۴-۱۳۸۸ ۰۴:۳۰ بعد از ظهر

حل مسئله فروشنده دوره گرد (TSP) با شبکه هاپفیلد
:rolleyes:

Astaraki ۰۹-۱۷-۱۳۸۸ ۰۲:۰۷ بعد از ظهر

برنامه tsp
 
1(ها)ضميمه
:eek:
و اين هم توضيحات کامل و برنامه همراه سورس سي پلاس پلاس

Astaraki ۰۹-۲۶-۱۳۸۸ ۰۸:۲۳ بعد از ظهر

ارائه الگوریتم تركیبی مورچگان وژنتیك برای حل مسئله فروشنده دوره گرد
 
1(ها)ضميمه
ارائه الگوریتم تركیبی مورچگان وژنتیك برای حل مسئله فروشنده دوره گرد

منبع: چهارمین کنفرانس بین المللی مهندسی صنایع - 1384

چکیده:
مساله فروشنده دوره گرد جزء مسائل مشهور و كلاسیك تحقیق در عملیات می باشد. بسیاری از فعالیت های
علمی را می توان به صورت مسئله فروشنده دوره گرد در آورد و سپس حل نمود. روشهای بهینه یابی موجود برای حل مسائل سخت (همچون مسئله فروشنده دوره گرد) بطور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می باشند كه از كارایی عملی آنها در حل مسائل با ابعاد واقعی می كاهد بدین علت در دهه های اخیراستفاده ازالگوریتم های ابتكاری و فوق ابتكاری مورد توجه قرار گرفته است. در این بین الگوریتم های فوق ابتكاری بدلیل ساختار ساده وتوانایی هایی كه از خود نشان داده اند مورد استفاده محققین تحقیق در عملیات قرار گرفته است. در این تحقیق با تركیب دو الگوریتم كلونی مورچگان و الگوریتم ژنتیك سعی شده است الگوریتم تركیبی ساخته شود كه تور بهتری را برای مسئله فروشنده دوره گرد بدست آورد. پس از طراحی الگوریتم، تنظیم پارامترهای آن با حل مسائل متعدد صورت گرفته است و برای مقایسه روش پیشنهادی با روشهای الگوریتم ژنتیك و مورچگان برخی از مسائل حل شده است. نتایج بدست آمده نشان می دهد كه روش تركیبی پیشنهادی tsp فروشنده دوره گرد موجود در سایت در اغلب مسائل قادر است جواب بهتری بدست آورد.

وازه های كلیدی
فروشنده دوره گرد، الگوریتم تركیبی، الگوریتم كلونی مورچگان، الگوریتم ژنتیك

Astaraki ۱۰-۲-۱۳۸۸ ۰۴:۵۰ بعد از ظهر

1(ها)ضميمه
یک روش ترکیبی براي حل مساله فروشنده دوره گرد

Astaraki ۱۰-۹-۱۳۸۸ ۰۷:۵۵ بعد از ظهر

1(ها)ضميمه
يک شبکه عصبی فازی ژنتيکی جديد برای حل مسأله فروشنده دور ه گرد

Astaraki ۱۰-۹-۱۳۸۸ ۰۸:۳۲ بعد از ظهر

1(ها)ضميمه
حل مساله فروشنده دوره‌گرد احتمالي توسط اتوماتاي يادگير توزيع شده

Astaraki ۱۰-۹-۱۳۸۸ ۰۸:۳۴ بعد از ظهر

1(ها)ضميمه
حل مساله فروشنده دوره گرد پويا توسط اتوماتاهاي يادگير واكنشي توزيع شده

Astaraki ۱۰-۱۱-۱۳۸۸ ۰۱:۵۴ بعد از ظهر

مساله فروشنده دوره گرد تعميم‌يافته
 
1(ها)ضميمه
مساله فروشنده دوره گرد تعميم‌يافته

Astaraki ۱۰-۱۱-۱۳۸۸ ۰۴:۰۳ بعد از ظهر

1(ها)ضميمه
مقاله اي در زمينه حل tsp به روش الگوریتم ژنتیک

Astaraki ۱۰-۱۱-۱۳۸۸ ۰۴:۰۴ بعد از ظهر

يك روش تركيبي مبتني بر خوشه بندي براي حل مساله فروشنده دوره گرد با مقياس بزرگ

Astaraki ۱۰-۱۲-۱۳۸۸ ۱۱:۵۴ قبل از ظهر

1(ها)ضميمه
بکارگيري الگوريتم رقابت استعماري در حل مسئله فروشنده دوره گرد

Astaraki ۱۰-۱۳-۱۳۸۸ ۱۰:۰۳ قبل از ظهر

دانلود کد الگوریتم بهینه سازی کلونی مورچه ها برای حل مسأله فروشنده دوره گرد

مقايسه الگوريتم كولوني مورچه ها و جستجوگر ممنوعه در حل مسأله tsp
:23:

h.jaza ۱۰-۲۵-۱۳۸۸ ۰۵:۴۱ بعد از ظهر

حل TSP با Genetic Algorithms در #C
و روش حل با Simulated Annealing

bagheri ۰۱-۱۷-۱۳۸۹ ۰۸:۱۲ بعد از ظهر

با سلام خدمت شما دوست عزیز وتشکر از پست مفیدتون
اگر امکان دارد در مورد تابع ابتکاری برای حل این مساله فروشنده دورگرد توضیح دهید
منظورم اینه که تابع ابتکاری این مساله چیه (در روش ژنتیک)

arghavan345 ۰۳-۱۴-۱۳۸۹ ۰۳:۳۱ بعد از ظهر

با سلام
حل مسئله تی اس پی رو با زبان سی ++ و به روش الگوریتم ژنتیک می خواستم
با تشکر:2:

amir-shakh ۰۴-۸-۱۳۸۹ ۰۳:۱۲ بعد از ظهر

سلام
اگر امکان دارد من را در مورد پیاده سازی مسئله فروشنده دوره گرد به کمک الگوریتم RBFS راهنمایی کنید و یا در صورت امکان اگه کدی در این مورد به هر زبانی داشتید برای من در این قسمت بگذارید و در مورد روشهای gentic algoritm و simulated annearling اگه میشه کد و راه حلی بزارید برای فروشنده دوره گرد

Astaraki ۰۶-۱۴-۱۳۸۹ ۱۰:۴۸ قبل از ظهر

1(ها)ضميمه
حل مسئله فروشنده دوره گرد (TSP) استفاده از شبکه عصبی خود سازمانده (SOM)
A Novel Approach for Solving STP using SOM

hosseinmahan ۰۲-۶-۱۳۹۰ ۱۲:۰۴ بعد از ظهر

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

ele_girl ۰۲-۱۳-۱۳۹۰ ۰۹:۲۰ قبل از ظهر

:26:سلام من دانشجوي رشته رياضي هستم . اگر مقاله اي در مورد فروشنده ي دوره گرد دارين برام بفرستين خيلي لازمش دارم . ممنون ele_girl17@yahoo.com

Astaraki ۰۲-۱۳-۱۳۹۰ ۱۰:۱۸ بعد از ظهر

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

الگوریتم شبیه سازی تبرید یا Simulated Annealing و یا به اختصار SA، یکی از قوی ترین الگوریتم های در زمینه بهینه سازی ترکیباتی یا Combinatorial Optimization است.
این الگوریتم در سال ۱۹۸۳ توسط کیرکپاتریک و همکارانش ارائه گردید و در همان مقاله اصلی، بر روی مسأله فروشنده دوره گرد یا TSP اعمال شد.

لينک دانلود

marjan mina ۰۲-۲۷-۱۳۹۰ ۱۰:۴۸ قبل از ظهر

سلام پیاده سازی صف m/m/1به زبا نc or c++کمکم کنیسد با تشکر

marjan mina ۰۲-۲۷-۱۳۹۰ ۱۰:۵۱ قبل از ظهر

سلام من پیاده سازی صف m/m/1را در زبان سی یا سی++میخواستم لطفا به ایمیلم بفرستید با تشکر
marjan.mina.90@gmail.com

0251_0611 ۰۳-۸-۱۳۹۰ ۰۴:۵۴ بعد از ظهر

سلام تو رو خدا کمکم کنید
پنج شنبه ارائه پروژه دارم مسئله tsp با الگوریتم ژنتیک به زبان c یا c++
اینم ایمیلم :
mer30_topak@yahoo.com

arash1664 ۰۵-۱-۱۳۹۰ ۰۱:۱۴ بعد از ظهر

با سلام خدمت دوستان عزیز
من رشته مکانیک هستم. زیاد با زبان lisp کار نکردم. پروژه درس هوش مصنوعیم همین مسأله tsp هستش.اگه کسی بتونه source این برنامه رو به زبان lisp بده بهم ممنون میشم. arash_6230@yahoo.com

rezamirjalili56 ۰۸-۶-۱۳۹۰ ۱۲:۲۹ بعد از ظهر

Thanks ادمین با مرام
خیلی خوب بود ممنون

سمیرا90 ۰۸-۹-۱۳۹۰ ۰۴:۴۳ بعد از ظهر

سلام من موضوع پروژه ام فروشنده دوره گرد با الگوریتم ica است ولی نمیدونم باید چطوری شروع کنم .لطفا منو راهنمایی کنید .تشکر

fateme k ۰۹-۷-۱۳۹۰ ۰۶:۱۰ بعد از ظهر

salam halle masaleye tsp ba algoritme pso dar matlab ro mikhastam

یلدا امیدی ۰۹-۱۸-۱۳۹۰ ۰۸:۲۰ بعد از ظهر

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

hermes ۱۰-۲۵-۱۳۹۰ ۱۲:۱۰ بعد از ظهر

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

mohamads1989 ۰۱-۲۸-۱۳۹۱ ۰۳:۱۶ بعد از ظهر

ا سلام
از دوستان عزیز تقاضای کمک در مورد شیوه ی تعیین هزینه در مسئله فروشنده دوره گرد را دارم.من یه مقاله خوندم ولی قشنگ ننوشته بود شیوه تعیین هزینه شهرها.من فک کنم از روش ماتریسی استفاده کنیم بهتره یعنی crossover matrrix.
اگه توضیح بددید در ای باره ممنون می شم یا مقاله ای که حل کرده باشه.

vishay2 ۰۲-۵-۱۳۹۱ ۱۱:۲۰ قبل از ظهر

نرم افزار حل گونه های مختلف الگوریتم فروشنده دوره گرد مثل Generalized TSP,...
 
سلام

حتما میدونید که الگوریتم فروشنده دوره گرد و گونه های مختلف آن کاربرد زیادی در مسائل بهینه سازی دارند که بهینه سازی ماشینهای CNC از مهمترین کاربردهای این الگوریتم است.
نرم افزاری که در اینجا قرار میدم قادر هست که این الگوریتم و گونه های مختلف اون مثل Asymmetric or Symmetric TSP‏ و (Generalized TSP (GTSP و CTSP و مهمتر از همه حل با اولویت یعنی Precedence Constraints رو انجام بده. این برنامه از روش هیوریستیک Lin-kernighan استفاده میکنه.
توضیحات بیشتر در خود برنامه وجود دارد...
این هم لینک دانلود است:
http://www.r-azarmehr.com/TSPStudio.zip
امیدوارم مفید باشه...

faezeh_shaytoon ۰۳-۲۰-۱۳۹۱ ۰۱:۴۷ قبل از ظهر

سلام من مساله فروشنده دوره گرد (tsp) را با استفاده از sa را به زبان ++c یا pascal یا #c ...... میخواستم
ممنون میشم که کمکم کنید ...
Esmaeli69@yahoo.com

f@temeh ۰۳-۲۹-۱۳۹۱ ۰۹:۳۷ بعد از ظهر

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

seda ۰۵-۷-۱۳۹۱ ۰۵:۳۵ بعد از ظهر

سلام
سرس کد حل مسئله tspرا با الگوریتم ژنتیک لازم دارم با ++cلطفا کمکم کنید .ممنون

kamranpak ۰۵-۸-۱۳۹۱ ۰۲:۴۸ بعد از ظهر

سلام کسی توضیح کامل مساله فروشنده دوره گرد رو داره

*sepid* ۰۵-۱۳-۱۳۹۱ ۰۷:۱۱ بعد از ظهر

اينم يه مقاله كامل از مسئله فروشنده دوره گرد ( به انگليسي)

تاريخچه ، تجزيه و تحليل و ژياده سازي مسئله فروشنده دوره گرد





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

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