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