W. Haas and S. Houghten (Canada)
Evolutionary Algorithms, Simulated Annealing, Optimal
Codes, Maximum Clique Problem.
The maximum possible number of codewords in a q-ary
code of length n and minimum distance d is denoted
Aq(n,d). It is a fundamental problem in coding theory to
determine this value for given parameters q, n and d.
Codes that attain the maximum are said to be optimal.
Unfortunately, for many different values of these
parameters, the maximum number of codewords is
currently unknown: instead we have a known upper bound
and a known lower bound for this value.
In this paper, we investigate the use of different
evolutionary algorithms for improving lower bounds for
given parameters. We relate this problem to the well
known Maximum Clique Problem. We compare the
performance of the evolutionary algorithms to Hill
Climbing, Beam Search, Simulated Annealing, and greedy
methods. We found that the GAs outperformed all other
algorithms in general; furthermore, the difference in
performance became more significant when considering
harder test cases.