Abstract— In this paper the performance of the most recent multi-modal genetic algorithms (MMGAs) on the Job Shop Scheduling Problem (JSSP) is compared in term of efficacy, multi-solution based efficacy (the algorithm’s capability to find multiple optima), and diversity in the final set of solutions. The capability of Genetic Algorithms (GAs) to work on a set of solutions allows us to reach different optima in only one run. Nevertheless, simple GAs are not able to maintain different solutions in the last iteration, therefore reaching only one local or global optimum. Research based on the preservation of the diversity through MMGAs has provided very promising results. These techniques, known as niching methods or MMGAs, allow not only to obtain different multiple global optima, but also to preserve useful diversity against convergence to only one solution (the usual behavior of classical GAs). In previous works, a significant difference in the performance among methods was found, as well as the importance of a suitable parametrization. In this work classic methods are compared to the most recent MMGAs, grouped in three classes (sharing, clearing and species competition), for JSSP. Our experimental study found that those new MMGAs which have a certain type of replacement process perform much better (in terms of highest efficacy and multi-solution based efficacy) than classical MMGAs which do not have this type of process.
Keywords—Genetic algorithms, Multimodal problems, Job shop scheduling problem, Niching methods

چکيده:  در این مقاله، عملکرد جدید ترین الگوریتم های ژنتیک جند وجهی (MMGAs) در مورد مساله برنامه ریزی کارگاهی (JSSP)، بر حسب کارایی - کارایی چند جوابی (قابلیت الگوریتم برای یافتن چندین جواب بهینه) - و نیز تنوع مجموعه نهایی جواب ها، مورد مقایسه قرار می گیرد. قابلیت الگوریتم های ژنتیک (GAs) در خصوص کار بر روی مجموعه ای از جواب ها، این امکان را برای ما فراهم می آورد تا تنها در یکبار اجرای الگوریتم، جواب های بهینه متفاوتی را بیابیم. با این وجود، الگورینم های ژنتیک ساده قادر نیستند تا در آخرین تکرار، جواب های متعددی را پشتیبانی نمایند . لذا تنها به یک جواب بهینه محلی و یا سراسری نائل می شوند. بررسی و تحقیق در خصوص حفظ تنوع از طریق استفاده از الگوریتم های ژنتیک جند وجهی ، نتایج بسیار امیدوار کننده ای را ارائه نموده است. این تکنیک ها - که با نام متد های نیچینگ و یا الگوریتم های ژنتیک جند وجهی شناخته می شوند - نه تنها امکان حصول چندین جواب بهینه سراسری را فراهم می آوردند؛ بلکه برخلاف همگرایی صرف به یک جواب (نظیر آنچه در رفتار معمول الگوریتم های ژنتیک کلاسیک وجود دارد)، امکان تنوع سودمند جواب ها را نیز حفظ می نمایند. در کارهای قبلی، اختلاف اساسی میان متد ها در نحوه عملکرد و نیز اهمیت پارامتری سازی مناسب، مشاهده می شود. در این کار تحقیقاتی، متد های کلاسیک با جدیدترین الگوریتم های ژنتیک چند وجهی در خصوص مساله برنامه ریزی کارگاهی (JSSP) مقایسه می شوند. این الگوریتم ها در سه دسته، گروه بندی شده اند که عبارتند از پاکسازی، تسهیم و رقابت گونه ای. مطالعه تجربی ما نشان می دهد که دسته ای از الگوریتم های ژنتیک چند وجهی که نوع خاصی از پروسه جانشینی را دارا می باشند، در موضوع بالاترین میزان کارایی و کارایی چند جوابی، از عملکرد بسیار بهتری نسبت به الگوریتم های ژنتیک چند وجهی که این نوع پروسه را در بر نمی گیرند؛ برخوردار می باشند.
کلمات کليديـ الگوریتم های ژنتیک، مسائل چند وجهی، مساله برنامه ریزی کارگاهی، متد های نیچینگ