Modified Genetic Algorithm for Solving n-Queens Problem

سال انتشار: 1392
محل انتشار: دوازدهمین کنفرانس ملی سیستم های هوشمند ایران
کد COI اختصاصی: ICS12_213
زبان مقاله: انگلیسی
تعداد مشاهده: 772

نویسندگان

Faculty of Mathematics and Computer Science Allameh Tabataba’i University Tehran, Iran

چکیده

Genetic algorithm is applicable to a wide range of constraint satisfaction problems such as n-queens problem. In the absence of specialized solution for a particular problem, geneticalgorithm would be efficient. But holism and random choices cause problem for genetic algorithm in searching large statespaces. So, the efficiency of this algorithm would be demoted when the size of state space of the problem grows exponentially. In this paper, we attempt to cover this weakness by using local search algorithm like minimal conflicts algorithm. Minimal conflicts algorithm is trying to provide partial view for geneticalgorithm by locally searching the state space. This may cause genetic algorithm to take longer steps toward the solution.Modified genetic algorithm, is the result of collaboration between genetic algorithm and minimal conflicts algorithm. Comparingthe results of applying standard genetic algorithm and modified genetic algorithm on n-queens problem in section VI, indicates the amount of performance improvement

کلیدواژه ها

genetic algorithm; minimal conflicts algorithm; nqueens problem;

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.