Article Preview
Top1. Introduction
Genetic algorithms (GA) and Particle Swarm Optimization (PSO) belong to the family of the evolutionary algorithms which proved their capacities to resolve successfully difficult problems in various domains. These problems include the constraint satisfaction problems CSPs. However both GA and PSO have strength and weakness. Several attempts of combination between both methods were registered in the literature to benefit from their advantages.
One of the most known problems which can be however resolved by GAs and PSO is the Constraint Satisfaction Problems: CSPs. Several problems of the real life can be easily formulated in the form of CSP. A CSP can be defined as a triple (X, D, C) where:
- •
X ={X1, X2, …,Xn} is a set of n variables,
- •
D ={D1, D2,…,Dn} is a set of domains, for each variable Xi is associated a domain Di,
- •
C= {C1, C2,…,Cn} the constraints are the relations between the variables.
A CSP solution is an instantiation of the variables with values from the respective domains which satisfies all the constraints and the limitations imposed by domains.
In this work we are interested in one of CSP extensions: Max-CSPs for Maximal Constraint Satisfaction Problems. A Max-CSP is a CSP where a solution corresponds to an instantiation of all the variables which satisfies the maximum of constraints. Other extensions made the object of the research for these problems: the dynamic CSPs, the distributed CSPs, the CSOP (for Constraint Satisfaction and Optimization Problems), the ∑CSPs, etc. Seen the importance of these problems several methods were implemented for the resolution of Max-CSPs. These methods are classified in two categories: the complete and the incomplete methods. The first are able to provide an optimal solution but they are limited by the combinatorial explosion. The second family such as Guided Genetic Algorithm (GGA), Distributed Double Guided Genetic Algorithm (D²G²A), Dynamic Distributed Double Guided Genetic Algorithm (D3G2A) and Dynamic distributed Double Guided Particle Swarm Optimization (D3GPSO) sacrifice completeness for efficiency. They have the advantage to escape from local optima.
The present work is inspired by the D3GPSO and the D3G2A. These two algorithms are based on the multi-agent systems. They outperform respectively the centralized versions of GA and PSO. Our approach is a combination between these lasts.
This paper is organized as follow: = Section 1 recalls the basic principles of GA and PSO, it recalls the D3G2A and the D3GPSO then it presents the different hybrid algorithms between GA and PSO registered in the literature. The Section 2 presents the Dynamic Distributed Double Genetic Swarm Optimization D3GSO, the basic concept, the global dynamic and the agent structure. Section 3 details the experiments and the experimental results. Finally a conclusion and possible perspectives are proposed.