Solving One-Million-Bit Problems using LZWGA
Naris Kunasol, Worasait Suwannik, Prabhas Chongstitvatana · 2006
To solve a problem using genetic algorithm (GA), a solution must be encoded into a binary string. The length of this string represents the size of the problem. As the length of the binary string increases, the size of the search space also increases at an exponential rate. To reduce the search space, one approach is to use a compressed encoding chromosome. This work proposes LZWGA that used compressed chromosomes. An LZWGA chromosome has to be decompressed using an LZW decompression algorithm before its fitness can be evaluated. The paper reports how to solve one-million-bit OneMax, royal road and trap functions using LZWGA. The search space of the original problem is 210000000or about 9.90times10301029points. When using a compressed encoding, the search space was reduced to 8.37times10166717points. The result from the experiment shows that it is practical to solve the problem of this size with the proposed method