A family of distributed double guided genetic algorithm for Max_CSPs

摘要

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~2G~2A 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~2G~2A 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~3G~2A. In this paper, newer algorithms and their global dynamics are furnished, and experimental results are provided.