A New Hybrid Distributed Double Guided Genetic Swarm Algorithm for Optimization and Constraint Reasoning: Case of Max-CSPs

A New Hybrid Distributed Double Guided Genetic Swarm Algorithm for Optimization and Constraint Reasoning: Case of Max-CSPs

Asma Khadhraoui (Hana Laboratory, ENSI-L’Ecole Nationale Des Sciences De L’informatique, University of Manouba, Tunisia) and Sadok Bouamama (Hana Laboratory, ENSI-L’Ecole Nationale Des Sciences De L’informatique, University of Manouba, Tunisia)
Copyright: © 2012 |Pages: 12
DOI: 10.4018/jsir.2012040104
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

In this paper the authors propose a new distributed double guided hybrid algorithm combining the particle swarm optimization (PSO) with genetic algorithms (GA) to resolve maximal constraint satisfaction problems (Max-CSPs). It consists on a multi-agent approach inspired by a centralized version of hybrid algorithm called Genetical Swarm Optimization (GSO). Their approach consists of a set of evolutionary agents dynamically created and cooperating in order to find an optimal solution. Each agent executes its own hybrid algorithm and it is able to compute its own parameters. The authors’ approach is compared to the GSO. It demonstrates its superiority. They reached these results thanks to the distribution using multi-agent systems, diversification and intensification mechanisms.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing