Genetic algorithms in solving constraint satisfaction problems. The timetable case

This article examines the possibility of using genetic algorithms (GAs) in solving constraint satisfaction problems (CSP). Initial efforts have shown that the naive design of the fitness function causes CSP to become a deceptive problem for GA. This paper demonstrates empirically and analytically how knowledge of the problem coded in the form of heuristics can be incorporated in genetic algorithm. Such an improvement can let GA converge to the optimal solution in a reasonable time. This confirms the fundamental artificial intelligence proposition that the success of the implemented method depends on how well the design respects the structure of the problem.