The Errors Correcting Code Design Problem - ECC

Problem Definition

The ECC problem was presented in [MS77]. We will consider a three-tuple (n,M, d), where n is the length of each codeword (number of bits), M is the number of codewords, and d is the minimum Hamming distance between any pair of codewords. Our objective will be to find a code which has a value for d as large as possible (reflecting greater tolerance to noise and errors), given previously fixed values for n and M.

The fitness value to be maximized is:

(1)

For further information about this problem, click here.

The Algorithm

In [ACDL04], a comparison between panmictic, structured and hybridized (with a new local search method -the repulsion algorithm-) GAs is presented. In this work, an especial fitness function is used because function (1) could assign in some cases a lower fitness value to a code C1 than another code C2, being the minimal distance between 2 codewords in C1 -d(C1)- largest than d(C2), which is no desirable. The fitness function used in this work is:

(2)

Results

In Table 1 we can see the results obtained by the canonical cGA, CHC, ssGA (steady state GA), and the new proposed Repulsion Algorithm (RA). The figures of tables 1 to 3 correspond to the succes percentage of finding a solution, the medium value and the standard deviation of the best solutions found, and the medium value and the standard deviation of the number of evaluations made.

Table 1. Results of RA, ssGA, CHC and
cGA for ECC. |

Table 2 contains the results obtained by some distributed GAs (dGA), composed by 5, 10, and 15 islands.

Table 2. Results of the distributed models
for ECC. |

Finally, in Table 3 the results of the ssGA and the different dGA hybridized with the new proposed RA are shown.

Table 3. Results of the hybridized models
(with the new RA) for ECC. |

As it can be seen in tables 1 to 3, the used of decentralized populations and, specially, the hybridization with RA, are two techniques wich favours the search for the optimal solution to the problem.