General

Given a set of strings S of equal lengths over an alphabet , the closest string problem seeks a string over whose maximum Hamming distance to any of the given strings is as small as possible. A data-based coding of strings for evo-lutionary search represents candidate closest strings as se-quences of indexes of the given strings. The string such a chromosome represents consists of the symbols in the corre-sponding positions of the indexed strings. A genetic algo-rithm using this coding was compared with two GAs that encoded candidate strings directly as strings over . In tri-als on twenty-ve instances of the closest string problem with alphabets ranging is size from 2 to 30, the algorithm that used the data-based representation of candidate strings consistently returned the best results, and its advantage in-creased with the sizes of the test instances ' alphabets