Restricted-Access

 

 
       

 

MMGAs> Crowding: Deterministic Crowding (DC)

                                                                                                                                                                                                                                                                

 

Last update: 06/2011

 
 

     Parameters

 

 

Without parameters

 
 

     Description

 

The Cavichio (1970)�s idea was the beginning of the deterministic crowding (DC) method. He thought that children being the individuals with more resemblance to their parents should be the ones to replace them. In DC method, the selection is removed and randomly divided the population into pairs in order to reproduce. Then, each child competes against one of the parents in a tournament, obtaining the individual that will survive for the next generation. The replacement tournament firstly evaluates which combination father (P) child (C) is more similar from  both possibilities: (P1-C1 y P2-C2) or (P1-C2 y P2-C1). Once this is known the father competes to survive against his most similar child. The survival is directly established by quality, the one with highest quality will survive and continue to the next generation.

 

This process is shown in the following flowchart:

 

This method is not steady state, but generational, as it is formed all the population that will substitute the initial one at the same time.

 

 
 

     Executable

 

The following three files have to be in the same folder. Do not change the name of the file. Double-click the .exe file to run it.

 

 
  JSSP

Executable

 exe

Data File

Open .txt file of the instance you want to run (for JSSP), copy and paste its contents inside this file.

 D_Entrada

Parameters File

Open the file and change the parameters

 D_Algoritmo

 

The following five files of solutions are generated:

■ D_Sal_Mejores-txt (includes the best solutions).

■ D_Sal_Optimos (includes the value of the objective function, i.e., Cmax).

■ D_Sal_NumOptimos (includes the number of different solutions where the optima value specified in the data file has been reached). This file is empty if this value is not reached.

■ D_Sal_Distancias (includes the distances between solutions where the optima value specified in the data file has been reached). This file is empty if either this value is not reached or only one solution is achieved.

■ D_Sal_Soluciones (includes the schedule of the solutions where the optima value specified in the data file has been reached). This file is empty if this value is not reached.

 
 

     References
 

Mahfoud, S. W. (1992). Crowding and preservation revisited. Parallel problem solving form nature II. M�nner, R. and Manderick, B. (Eds.). Elsevier. Pp. 27-36.

 
   

Universidad de Valladolid. Webmaster � Marta Posada