(1)
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.
