Stochastic search versus genetic algorithms for solving real time and over-constrained temporal constraint problems

Article type: Research Article

Authors: Mouhoub, Malek

Affiliations: Department of Computer Science, University of Regina, 3737 Waskana Parkway, Regina SK, Canada, S4S 0A2. Tel.: +1 306 585 4700; Fax: +1 306 585 4745; E-mail: [email protected]

Abstract: The aim of this work is to study the applicability of Genetic Algorithms (GAs) and stochastic local search methods to solve real time and over constrained temporal constraint problems. Solving these two type of problems consists of finding a possible scenario (solution) satisfying the temporal constraints within a given deadline. In the case where a complete scenario satisfying the constraints cannot be found, a partial one maximizing the number of solved constraints should be returned. This is an optimization problem where the objective function corresponds to the number of solved constraints. Experimental comparison of genetic algorithms and three stochastic local search methods have been conducted on randomly generated temporal constraint problems. The results of the experimentation favour the Min-Conflicts-Random-Walk (MCRW) local search method for under constrained problems while the GA based method is the technique of choice for middle constrained and over constrained problems.

Keywords: genetic algorithms, local search, temporal reasoning, constraint satisfaction

DOI: 10.3233/KES-2005-9104

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 9, no. 1, pp. 33-41, 2005