LZW Encoding in Genetic Algorithm

LZW Encoding in Genetic Algorithm

Worasait Suwannik
Copyright: © 2013 |Pages: 12
DOI: 10.4018/978-1-4666-3628-6.ch015
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

To solve a problem using Genetic Algorithms (GAs), a solution must be encoded into a binary string. The length of the binary 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 paper presents a genetic algorithm, called LZWGA, that uses compressed chromosomes. An LZWGA chromosome must be decompressed using an LZW decompression algorithm before its fitness can be evaluated. By using compressed encoding, the search space is reduced dramatically. For one-million-bit problem, the search space of the original problem is 21000000 or about 9.90x10301029 points. When using a compressed encoding, the search space was reduced to 8.37x10166717 points. LZWGA can solve one-million-bit OneMax, RoyalRoad, and Trap functions.
Chapter Preview
Top

Lzwga

The main difference between LZWGA and Simple GA is that a chromosome is in a compressed format. The LZWGA chromosome has to be decompressed before its fitness can be evaluated. The pseudo code of LZWGA is shown in Figure 1. The algorithm begins by creating the first generation of compressed chromosomes. Before evaluating the fitness of a chromosome, the compressed chromosome is decompressed using LZW Decompression algorithm. The fitness evaluation is performed on the uncompressed chromosome. After that, the new population is created to replace the old population. The algorithm repeats the process of decompression, fitness evaluation, and creating a new population until the termination criterion is met. The algorithm terminates when a solution is found or a maximum generation is reached.

Figure 1.

LZWGA pseudo code

978-1-4666-3628-6.ch015.f01

Complete Chapter List

Search this Book:
Reset