CHC Method

    A CHC is a non-traditional GA which combines a conservative selection strategy (that always preserves the best individuals found so far) with a highly disruptive recombination (HUX) that produces offsprings that are maximally different from their two parents. The traditional though of preferring a recombination operator with a low disrupting properties may not hold when such a conservative selection strategy is used. On the contrary, certain highly disruptive crossover operator provide more effective search in many problems, which represents the core idea behind the
CHC search method. This algorithm introduce a new bias against mating individuals who are too similar (incest prevention). Mutation is not performed, instead, a restart process re-introduces diversity whenever convergence is detected.

 1 t = 0
 2 initialize P(t)
 3 evaluate structures in P(t)
 4 while not end do
 5    t = t + 1
 6    select: C(t) = P(t-1)
 7    recombine: C'(t) = 'incest prevention' + HUX(C'(t))
 8    evaluate structures in C'(t)
 9    replace P(t) from C''(t) and P(t-1)
10    if convergence(P(t))
11        diverge P(t)

The CHC method skeleton (CHC) requires the classes:

• Problem
• Solution
  

The class Problem corresponds to the definition of a problem instance. The skeleton filler must provide a complete definition of this class.

And finally, the class Solution corresponds to the definition of a solution (feasible or not) of a problem instance. The skeleton filler must provide a complete definition of the class Solution.

In adition, the user must configure the following algorithm parameters (in file CHC.cfg):

• number of independent runs.
• number of generations.
• size of population.
• Selection operator parameters (selection of new parents and the diverge method that the algorithm uses whenever the convergence is detected).
• Intra operators parameters (crossover and mutation parameters).
• Inter operators (operators to apply between sub-populations) parameters: operator number, operator rate, number of individuals and selection of individual to send and replace.
• Parallel Configuracion: interval of generation to refresh global state, running mode (synchronized or asyncronized) and interval of generations to check solutions from other populations.

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

1. Change to the problem directory

cd Mallba/rep/CHC/problem

2. Compile skeleton.

make

3. Configure algorithm parameters (CHC.cfg file)
4. Run problem:
       4.1 Sequential Version:

make SEQ
     or
MainSeq CHC.cfg_path instance_path res_file_path

        4.2 Parallel Version:
                     4.2.1 Configure Config.cfg file.
                     4.2.2 Configure pgfileLan (or pgfileWan) : machines where we run the program.
                     4.2.3 Run

make LAN
     or
make WAN

[Up]