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

Abstract

در این پژوهش با استفاده از الگوریتم ژنتیک آشفته، روشی جدید به منظور بهینه¬سازی مسیر حرکت یک متحرک نظیر ربات، در حضور موانع متعدد ارائه می¬شود. مسیر حرکت می¬تواند به صورت دوبعدی و یا چند¬بعدی در نظرگرفته شود و موانع موجود در مسیر نیز به صورت دایره و کره¬، فرض می¬شوند. روش به کار گرفته به این صورت است که ابتدا تعدادی کروموزوم در نسل صفر ایجاد می¬شوند و برازندگی آنها مورد محاسبه قرار می¬گیرد. سپس با استفاده از انتخاب مسابقه¬ای، والدین نسل جدید ایجاد شده و از آنجا کروموزوم¬های نسل بعد، ساخته می¬شوند و برازندگی آنها محاسبه می¬شود و این روند ادامه پیدا می¬کند تا قید در نظر گرفته شده که به صورت نسبت میانگین برازندگی¬ها به برازندگی بیشینه در هر نسل است، ارضاء شود. از آنجا که در الگوریتم ژنتیک آشفته، طول کروموزوم می¬تواند متغیر باشد، الگوریتم پیشنهادی قادر است بسته به موانع موجود، انواع مسیرها با تعداد نقاط متغیر را مورد بررسی قرار داده و با کارایی بالا، کوتاه-ترین مسیر را با احتلاف تقریبی 2 درصد نسبت به مسیر ایده¬آل، ارائه نماید. این روش قادر است حتی مسیرهای با تعداد بعد بیشتر از سه را نیز بهینه¬سازی نماید.