نوع فایل: word
قابل ویرایش 81 صفحه
چکیده:
الگوریتم PSOیک الگوریتم جستجوی اجتماعی است که از روی رفتار اجتماعی دسته‌های پرندگان مدل شده است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینه‌ی دسته به کار گرفته شد . در PSO، ذرات در فضای جستجو جاری می‌شوند. تغییر مکان ذرات در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان است. بنابراین موقعیت دیگر توده ذرات روی چگونگی جستجوی یک ذره اثر می‌گذارد. نتیجه‌ی مدل‌سازی این رفتار اجتماعی فرایند جستجویی است که ذرات به سمت نواحی موفق میل می‌کنند. ذرات از یکدیگر می‌آموزند و بر مبنای دانش بدست آمده به سمت بهترین همسایگان خود می‌روند اساس کار PSO بر این اصل استوار است که در هر لحظه هرذرهمکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگی‌اش وجود دارد، تنظیم می‌کند.
در این مقاله روشی برای حل مسأله مشهور فروشنده دوره گرد (Tsp)، با استفاده از الگوریتم PSO ارائه شده است. PSO یک روش بهینه سازی است که از رفتار اجتماعی پرندگان الهام گرفته است. در PSOهرعضو جامعه موقعیت خود را در فضای جستجو با توجه به تجربیات شخصی و تجربیات کل جامعه تغییر می دهد. الگوریتم PSO معمولا برای بهینه سازی توابع غیر خطی با متغیرهای پیوسته به کار می رود؛ در حالی که در مساله TSP با یک فضای جستجوی گسسته سروکار داریم. بنابراین با اعمال تغییرات اندکی در الگوریتم PSO وتعریف مجدد عملگرهای محاسباتی (جمع و ضرب وتفریق) این الگوریتم متناسب با ساختار مسألۀ TSP تغییر یافته سات. الگوریتم پیشنهادی بر روی گرافی متشکل از 17 شهر تست شده و در پنجمین اجرا به جواب بهنیۀ سراسری رسیده است. سایر جوابهای به دست آمده از الگوریتم نیز به جواب بهینه خیلی نزدیک می باشند.
کلمات کلیدی: PSO، مسألۀ فروشندۀ دوره گرد، الگوریتم های الهام گرفته از طبیعت.
مقدمه:
امروزه یکی از مهم‌ترین زمینه‌های تحقیق و پژوهش، توسعۀ روشهای جستجو بر مبنای اصول تکامل طبیعی می‌باشد. در محاسبات تکاملی به صورت انتزاعی از مفاهیم اساسی تکامل طبیعی در راستای جستجو برای یافتن راه حلّ بهینه برای مسائل مختلف الهام گرفته شده است. در همین راستا مطالبی که در این فصل پیش روی شما پژوهندۀ گرامی قرار خواهد گرفت مفاهیمی دربارۀ علم کامپیوتر و علم ژنتیک مانند: الگوریتم و انواع آن، جستجو، هیوریستیک، تاریخچه الگوریتم ژنتیک و علم ژنتیک، ژن، کروموزوم، ارث بری و... می باشد، و یا به بیانی خلاصه‌تر می‌توان گفت: در این فصل به بیان مقدّمات خواهیم پرداخت.
انشاءالله مطالعۀ این فصل مفهومی ساده و روشن از موضوعِ این نوشتار را برای شما خوانندۀ محترم به تصویر خواهد کشید و شما را در درک آسان و سریع فصول بعدی یاری خواهد رساند.
فهرست مطالب:
فصل اول : مختصر توضیح در موردTSP
1-1- مقدمه
1-2- درباره علم ژنتیک
1-3- تاریخچۀ علم ژنتیک
1-4- ایدۀ اصلی استفاده از الگوریتم ژنتیک
1-5- انواع الگوریتم‌های هیوریستیک
فصل دوم : الگوریتم ژنتیک
2-1- مکانیزم الگوریتم ژنتیک
2-2- عملگرهای الگوریتم ژنتیک
2-2-1- کدگذاری
2-2-2- ارزیابی
2-2-3- ترکیب
2-2-4- جهش
2-2-5- رمزگشایی
2-3- انواع الگوریتم‌های ژنتیکی
2-3-1- الگوریتم ژنتیکی سری
2-3-2- الگوریتم ژنتیکی موازی
2-4- مقایسه الگوریتم ژنتیک با سیستم‌های طبیعی
2-5- نقاط قوّت الگوریتم‌های ژنتیک
2-6- بهبود الگوریتم ژنتیک
2-7- چند نمونه از کاربردهای الگوریتم‌های ژنتیک
2-8-کد کردن(Encoding)
2-9-تابع ارزش(Evaluation)
2-10- انتخاب (Selection)
2-11-ترکیب (Crossover)
2-12-جهش (Mutation)
2-13-الگوریتم ژنتیک و حلّ مسألۀ فروشندۀ دوره‌گرد
2-14-مسئله فروشنده سیار موردی مربوط به بهینه سازی ترکیبی است
2-15- مسئله فروشنده سیار یک مسئله بهینه سازی ترکیبی است NP-hard
فصل سوم : PSO
3-1- قاعده PSO
3-2- الگوریتم 1: شبه‌دستورالعمل برای PSO پایه
3-2-1- قالب‌بندی آغازین
3-2-2- نشان دادن بهترین راه‌حل پیدا شده ؛
3-2-3- الگوریتم پیشنهادی (MHPSO)
3-3- فرمول‌بندی و شرح مسئله
3-4- روش دو گزینه‌ای
3-5- عملکرد متقاطع
3-6- الگوریتم MHPSO
3-7- نتایج تجربی
3-8- نتیجه گیری
فصل چهارم :حل مسئله TSP با GA
4-1-مقدمه
4-2- حل tsp با الگوریتم ژنتیک
4-3- مقایسه روشهای مختلف الگوریتم و ژنتیک برای TSP
4-4- نگاه مختصری به PSO
4-5- استفاده از PSO برای حل مساله فروشنده دوره گرد
4-6- بردار سرعت و عملگر حرکت (Move)
4-7- عملگر تفریق(subtraction)
4-8- عملگر جمع(addition)
4-9- عملگر ضرب(Multiplication)
4-10- الگوریتم PSO برای TSP
4-11- نتایج به دست آمده
4-12-جمع بندی و نتیجه گیری
مراجع
منابع و مأخذ:
[1] kennedy,j,and Eberhart,R.C,,”Particle swarm optimization “,proc .IEEE intl conf .on neural Network ,vol,IV,PP.1942-1948.IEEEService center , Piscataway,NJ,1995.
[2]Eberhart , R.C.and shi, Y.,”Evolving artificial neural networks”,proceedings of international conference on Neural NetworkandBrain ,1998,Beijing, P.R.China,pp.PL5-PL13,1998.
[3]Gudise ,v.G.,and venayagamoorthy,G.K.,”Comparison of particle swarm optimization and back Propagation as training algoritms for neural networks”,proceedings of the IEEE swarm Intelligence Symposium 2003 (SIS 2003),Indianapolis ,Indiana,USA,PP.110-117,2003.
[4]Xiaohui HU,”Particle Swarm optimization Tutorials”,online:
http://web.ics.purdue.edu/hux/tutorials.shtml,2002.
[5]Shi, .,and Eberhart ,R.C.,”parameter selection in particle swarm optimization “,Evolutionary programming VII:Proceedings of the Serventh Annual conference on Evolutionary programming ,New York,pp.591-600,1998.
[6]Clerc,M.,”Discrete particle swarm optimization ,III UStrated by the Traveling Salesman problem”,Online:http://www.mauriceclerc.net,2000.
پروژه حل مسأله TSP با ((GA و PSO))). doc