Solving Temporal Constraint Satisfaction Problems with Heuristic Based Evolutionary Algorithms

In this paper we discuss the applicability of evolutionary algorithms enhanced by heuristics and adaptive fitness computation for solving the temporal constraint satisfaction problem (TCSP). This latter problem is an extension of the well known CSP, through our TemPro model, in order to handle numeric and symbolic temporal information. We test the evolutionary algorithms on randomly generated TCSPs and analyze and compare the performance of the algorithms tested, based on different measures. The results show that heuristics do not promise better performance for solving TCSPs. The basic genetic algorithm (GA) and microgenetic iterative descendant (MGID) are the most effective ones. We also noticed that MGID is more efficient than basic GA for easier problems.