earticle

영어

The population based approach of GA allows large jumps in the search space. However
GAs has not proved successful for graph coloring because of the large degree of symmetry of the solution space. In fact, because of this symmetry mismatch it is very unlikely to produce a fit offspring when combining two good solutions. Thus GAs are often considered on inappropriate approach for problems such as graph coloring with a highly degenerate objective function. In order to compensate for this degeneracy we have applied Bitstream neuron (Boltzmann Machine) to the solution obtained from GA. Unlike traditional approaches of GA and ANN the proposed hybrid algorithm is guaranteed to have 100% convergence rate to valid solution with no parameter tuning. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive. Analysis of the behavior of the algorithm sheds light on ways to further improvement.