A family of distributed double guided genetic algorithm for Max_CSPs

Abstract

This paper presents, studies and betters distributed Guided Genetic Algorithm (DGGA) dealing with Maximal Constraint Satisfaction Problems. This algorithm consists of agents dynamically created and cooperating in order to satisfy the maximal number of constraints. Each agent performs its own GA, guided by both the template concept and the Min-conflict-heuristic, on a sub-population composed of chromosomes violating the same number of constraints. D²G²A is a new multi-agent approach, which in addition to DGGA will be enhanced by a new parameter called guidance operator. The latter allows not only diversification but also an escaping from local optima. D²G²A is improved in the second part. This improvement is based on the NEO-DARWINISM theory and on the laws of nature. In fact, the new algorithm will let the species agent able to count its cross-over probability and its mutation probability. This approach is called D³G²A. In this paper, newer algorithms and their global dynamics are furnished, and experimental results are provided.