GA + SA Hybrid Algorithm

    In its broadest sense, hybridization refers to the inclusion of problem-dependent knowledge in a general search algorithm. More precisely, two major hybridization models are distinguished: strong hybridization and weak hybridization.

• Strong hybrids: algorithms in which knowledge has been included as specific non-conventional problem representations and/or operators.
• Weak hybrids: algorithms resulting from the combination of lower-lever hybrid algorithms

The Mallba Library has a hybrid algorithm (newGASA) that is formed by a Genetic Algorithm and the Simulated Annealing . While the GA allow to move to good regions of the search space, the SA allow to explore in an exhaustive way those regions of the search space.

In each hybrid have been developed several versions of hybridization:

• Version 1: The SA algorithm  is used as genetic operator of the GA.

• Version 2 and Version 3: The second hybrid schema executes a GA until the algorithm completely finishes. Then the hybrid selects some individuals from the final population and executes a SA algorithm over them. Concretely, it exists a first version (newGASA2) that uses a tournament selection, and another version (newGASA3) that uses a random choice of individuals.

This skeleton (newGASA) requires the classes:

• Problem
• Solution
• Crossover
• Mutation
• DefaultMove

All these classes were explained in previous sections.

The user must configure the files:

• newGA.cfg
• SA.cfg
• and newGASA.cfg

Two first files had been explained in previous sections and the newGASA.cfg includes the following parameters:

• Selection method and its parameters (versions 2 and 3)
• Number of individuals passed to SA (version 2 and 3)
• newGA.cfg and SA.cfg paths
• Problem instance file path

There are several basic steps to running a problem solve with newGASA skeleton

1. Change to the problem directory

cd Mallba/rep/hybrid/newGASA/problem

2. Compile skeleton.

make

3. Configure algorithm parameters (SA.cfg,GA.cfg and newGASA.cfg file)
4. Run problem:
       4.1 Sequential Version (X=1,2 or 3):

make SEQ_X

        4.2 Parallel Version:
                     4.2.1 Configure pgfileLanX (or pgfileWanX) : machines where we run the program.
                     4.2.2 Run (X=1,2 or 3)

make LAN_X
     or
make WAN_X

[Up]