پاورپوینت ارائهء یک الگوریتم جستجوی مبتنی بر روشهای جمعیت در بهینه سازی ترکیبی

ارائهء یک الگوریتم جستجوی مبتنی بر روشهای جمعیت در بهینه سازی ترکیبی

فهرست مطالب
تعریف مسایل بهینه سازی ترکیبی
مدلهای ACO
کاربردهای الگوریتم مورچه
مساله مسیریابی وسایل نقلیه
الگوریتم پیشنهادی
داده های آزمایشگاهی
تست و ارزیابی
نتیجه گیری و راهکارهای آینده
منابع
2

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

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

طبقه بندی فرااکتشافات
5

الگوریتمهای تکاملی
6

مسایل مهم در حوزه هوش گروهی
7

الگوریتم های مورچه، سیستم های چندعامله ای هستند که هر عامل، یک مورچه مصنوعی است.
ایده : مورچه ها در مسیر خود ماده شیمیایی به نام فرومون ترشح می کنند. وقتی سر دوراهی (مسیرکوتاهتر و طولانی تر) قرار می گیرند، براساس میزان فرومون استشمام شده از هر مسیر، یک انتخاب مسیر احتمالی انجام می دهند. به این ترتیب احتمال انتخاب مسیرهای دارای فرومون زیاد، به تدریج افزایش می یابد (اثر autocatalytic).
رکود: اکثر مورچه ها کوتاهترین شاخه را انتخاب می کنند
تبخیر: مکانیزم اجتناب از همگرایی سریع به مسیرهای زیربهینه
9

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

مدلهای ACO
11

کنفرانسهای مهم
International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS)
Genetic and Evolutionary Computation Conference (GECCO)
IEEE Swarm Intelligence Symposium (SIS)
Metaheuristics International Conference (MIC)
International Workshop on Hybrid Metaheuristics (HM)
IEEE Congress on Evolutionary Computation (CEC)
International Conference on Intelligent Systems Design and Applications (ISDA)
International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)
13

مجلات مرجع
Applied Mathematics and Computation
Artificial Life
Computers & Operations Research
European Journal of Operational Research
Evolutionary Computation
Evolutionary Computation in Combinatorial Optimization
IEEE Transactions on Evolutionary Computation
IEEE Transactions on Systems, Man and Cybernetics
Information Systems and Operational Research
INFORMS Journal on Computing
Journal of Mathematical Modelling and Algorithms
Journal of Operations Research Society

مساله مسیریابی وسایل نقلیه (Vehicle Routing Problem)
مجموعه ای از وسایل نقلیه با ظرفیت (معمولا) یکنواخت وجود دارد که وظیفه آنها سرویس رسانی به درخواستهای مشتریان است. هدف یافتن مجموعه ای از مسیرها با کمترین هزینه است که با شرایط به همه تقاضاها سرویس بدهد.
مسیرها باید از انبار شروع و به آن ختم شوند.
هر مشتری باید توسط دقیقا یک وسیله ملاقات شود.
مجموع تقاضاهای مشتریها در هر مسیر نباید بیشتر از ظرفیت وسیله نقلیه باشد.

تعریف فرمال مساله CVRP
G =(V, E) , V={0,1,…,n}, Q, qi, m, dij

یک نمونه مساله ساده از CVRP
17

ایده اصلی
هدف یافتن کوتاهترین مسیر
گره های نزدیک به هم بهتر است در یک تور قرار بگیرند
درخت پوشای کمینه کوچکترین درخت روی گراف است که همه گره ها را می پوشاند
گره های موجود روی یک شاخه به هم نزدیک ترند
احتمالا مسیرهایی که گره های روی یک شاخه را به هم وصل می کنند، مسیرهای کوتاهتری هستند و درخت پوشای کمینه خوشه بندی مناسبی روی گره ها فراهم می کند.
19

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

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

دریافت ورودیهای مساله
ورودیها شامل تعداد گره های گراف مساله (بجز انبار)، ظرفیت وسایل نقلیه، مختصات انبار یعنی مولفه های x و y مربوط به آن و در نهایت مختصات سایر گره های مساله و میزان تقاضای هر گره هستند.

مقادیر اولیه
23

ساخت درخت پوشای می نیمم
استفاده از روش پریم برای ساخت درخت تعریف شده روی گراف مساله
ریشه درخت: انبار
سایر گره های درخت: مشتریها
وزن یالها به ترتیب صعودی براساس پارامتر
مقداردهی اولیه به مقادیر وزنهای متناظر با یالها
25

روش پریم
مرتب کردن کلیه یالهای گراف مساله براساس وزن، به ترتیب صعودی
شروع از یک درخت تهی
تا زمانی که تمام گره ها به درخت متصل نشده اند مرحله زیر انجام گیرد:
افزودن یال دارای کمترین وزن به درخت که باعث تشکیل دور نگردد.
26

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

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

انتخاب بهترین شاخه مجاور
بررسی شاخه های سمت چپ و راست
مطابقت درخواست گره با ظرفیت وسیله
انتخاب بیشترین صرفه جویی
انتقال به شاخه جدید
30

انتخاب شبه تصادفی گره بعدی بجز انبار (از شاخه جاری)
31

انتخاب احتمالی براساس تابع احتمال تجمعی
32
2/10
3/10
5/10

جستجوی محلی برای بهبود مسیرها
3-opt
swap
move

3-opt(3-exchange)
35

جایگزینی گره ها در یک تور
36

جابه جایی گره در یک تور
37

به روزرسانی مقادیر فرومون
39
جمله اول: شبیه سازی عمل تبخیر برای کلیه تورها

جمله دوم: افزایش فرومون برای مورچه هایی که-1 ne بهترین جوابها را به دست آورده اند

جمله سوم: افزایش فرومون برای بهترین مسیر با ضریب ne در هر 5 بار تکرار

به روزرسانی بهترین مسیر
بررسی محدودیتهای مرزی

به روزرسانی وزن یالهای شرکت کننده در درخت
بررسی محدودیت مرزی برای وزنها
42

پارامترهای آماری
طول بهترین و بدترین مسیر ساخته شده
طول متوسط راه حلها
انحراف معیار استاندارد
شماره تکراری که بهترین جواب در آن تکرار به دست آمده
44

دستاوردهای پروژه
ساخت درخت پوشای کمینه برای انجام خوشه بندی مناسب روی گره های گراف مساله
تعریف وزن برای یالهای گراف جهت ساخت درخت پوشای کمینه
بهره گیری از مقادیر وزن یالها و میزان درخواست گره ها برای تصمیم گیری در زمان انتخاب گره بعدی
نحوه به روزرسانی وزن یالها
تعریف پارامترهای مناسب در بخشهای تغییریافته
46

مکانیزم شروع مجدد
جلوگیری از رکود و گرفتار شدن در کمینه محلی
بخش پذیری تفاضل شماره تکرار بهترین جواب از تکرار جاری بر پارامتر شروع مجدد (30)
بازگرداندن پارامترها به مقادیر اولیه
نگهداری بهترین جواب سراسری

داده های آزمایشی
مجموعه داده های موجود در اینترنت
OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/
Christofides http://mistic.heig-vd.ch/taillard/problemes.dir/vrp.dir/taillard.dir
Taillard
داده های موجود در هر بستر آزمایشی
تعداد گره ها (شهرها)
مختصات انبار
ظرفیت وسایل
مختصات گره ها
میزان درخواست هر گره
بهترین جوابی که تا به حال به دست آمده
48

نتایج ارزیابی مجموعه داده های اول و سوم
51

نتایج ارزیابی مجموعه داده های اول و سوم
52

بهبودهای ممکن
به روزرسانی وزن یالهای درخت
تصمیمات احتمالی مورچه ها
ترکیب با سایر روشهای حل مساله مثل الگوریتم ژنتیک

منابع
[Baker 2003] B.M. Baker, M.A. Ayechew, “A genetic algorithm for the vehicle routing problem”, Computers & Operations Research 30 (2003) 787–800.
[Berger 2003a] J. Berger , M. Barkaoui, O. Bräysy, “A route-directed hybrid genetic approach for the Vehicle Routing Problem with Time Windows”, Information Systems and Operational Research 41, 179-194, 2003.
[Berger 2003b] J. Berger , M. Barkaoui , “A Hybrid genetic algorithm for the capacitated vehicle routing problem”, Proceedings of the genetic and evolutionary computation conference, Chicago, 2003. p. 646–56.
[Blum 2003] C. Blum, and A. Roli, “Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison”, ACM Computing Surveys, Vol. 35,No.3, September 2003,pp.268-308.
[Blum 2005] C. Blum, “Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling”, Computers & Operations Research 32 (2005) 1565–1591.
[Doerner 2002] Karl Doerner, et al. ,”SavingsAnts for the Vehicle Routing Problem” , Proceedings of the Applications of Evolutionary Computing on Evoworkshops 2002: Evocop, Evoiasp, EvoSTIM/EvoPLAN (April 03 – 04, 2002). S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, and G. R. Raidl, Eds. Lecture Notes In Computer Science, vol. 2279. Springer-Verlag, London, 11-20, 2002.
63

منابع (ادامه)
[Dorigo 2004] M. Dorigo and T. Stützle, Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
[Dorigo 2005] M. Dorigo, C. Blum, “Ant colony optimization theory: A survey”, Theoretical Computer Science 344 (2005) 243 – 278.
[Gambardella 1999b] L. M. Gambardella, E. D. Taillard, and G. Agazzi, “MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows”, New Ideas in Optimization, D. Corne et al., Eds. McGraw Hill, London, UK, 1999, pp. 63–76.
[Jeon 2007] G. Jeon, H.R. Leep, J.Y. Shim, “A vehicle routing problem solved by using a hybrid genetic algorithm”, Computers & Industrial Engineering (2007), doi:10.1016/j.cie.2007.06.031.
[Dorigo 2005] M. Dorigo, C. Blum, “Ant colony optimization theory: A survey”, Theoretical Computer Science 344 (2005) 243 – 278.
[Gambardella 1999b] L. M. Gambardella, E. D. Taillard, and G. Agazzi, “MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows”, New Ideas in Optimization, D. Corne et al., Eds. McGraw Hill, London, UK, 1999, pp. 63–76.
[Jeon 2007] G. Jeon, H.R. Leep, J.Y. Shim, “A vehicle routing problem solved by using a hybrid genetic algorithm”, Computers & Industrial Engineering (2007), doi:10.1016/j.cie.2007.06.031.
[Kennedy 2001] J. Kennedy, R.C. Eberhart, Swarm Intelligence, Morgan Kaufmann. 2001.

منابع (ادامه)
[Kruskal 1959] J.B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem”. Proceedings of the American MathematicalSociety 1956;7:48–50.
[Machado 2002] P. Machado, J. Tavares, F.B. Pereira, E. Costa, “Vehicle Routing Problem: Doing it the Evolutionary Way” , Proceedings of the Genetic and Evolutionary Computation Conference, p.690, July 09-13, 2002.
[Osman 1993] I.H. Osman, “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem”, Annals of Operations Research 1993;41:421–51.
[Pisinger 2007] D. Pisinger, S. Ropke, “A general heuristic for vehicle routing problems”, Computers & Operations Research 34 (2007) 2403 – 2435.
[Prim 1957] R.C. Prim. Shortest connection networks and some generalizations. Bell Systems Technology Journal 1957;36:1389–401.
[Prins 2004] C. Prins , “A simple and effective evolutionary algorithm for the vehicle routing problem”, Computers & Operations Research 2004;31: 1985–2002.
[Reimann 2001] M. Reimann, S. Shtovba, E. Nepomuceno, “A hybrid ACO-GA approach to solve Vehicle Routing Problems”, Student Papers of the Complex Systems Summer School, Budapest, Santa Fe Institute, (2001).

منابع (ادامه)
[Reimann 2002] M. Reimann, K. Doerner, R.F. Hartl, “Insertion based Ants for Vehicle Routing Problems with Backhauls and Time Windows”, Ant Algorithms, Springer LNCS 2463, Berlin/Heidelberg, pp 135–147, 2002.
[Reimann 2004] M. Reimann, K. Doerner, R.F. Hartl, “D-Ants: Savings Based Ants divide and conquer the vehicle routing problem”, Computers & Operations Research 31 (2004) 563–591.
[Reimann 2005] M. Reimann, M. Laumanns, “Savings based ant colony optimization for the capacitated minimum spanning tree problem”, Computers & Operations Research 33 (2006) 1794–1822.
[Taillard 1993] E.D. Taillard, “Parallel iterative search methods for vehicle routing problems”, Networks, 23:661–73, 1993.
[Thangiah 1991] S.R. Thangiah, P.L. Nygard and P.L. Juell, “A genetic algorithm system for vehicle routing with time windows”, Proceedings of the seventh IEEE conference on artificial intelligence applications (pp. 322–328), Miami, FL, 1991.
[Xu 2006] Y.-L. Xu, M.-H. Lim, Y.-S. Ong, J. Tang, “A GA-ACO-Local Search Hybrid Algorithm for Solving Quadratic Assignment Problem”, Proceedings of the genetic and evolutionary computation conference, p. 599–606, 2006.

منابع
M. Kheirkhahzadeh, A. Abdollahzadeh, “A hybrid algorithm for the Vehicle Routing Problem” Accepted in The fifth IEEE World Congress on Computational Intelligence (WCCI 2008), Hong Kong, 2008.
M. Kheirkhahzadeh, A. Abdollahzadeh, “An Efficient Algorithm for SLR(1) Grammar Recognition” ,Accepted in the third International Computer Engineering Conference Smart Applications for the Information society (ICENCO 2007), Egypt , 2007.
67

پایان
68

تعداد صفحات : 68 | فرمت فایل : .ppt

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