Bitstring Chromosomes

Traditionally, genetic algorithms used bitstring chromosomes. These chromosomes consisted of only '0's and '1's. Modern genetic algorithms more often use problem specific chromosomes as the balance between flexibility and raw efficiency tends away from the latter and with evidence that use of real-valued chromosomes often outperformed bitstring chromosomes anyway. In order to provide the ability to duplicate classical genetic algorithm experiments, GAUL has two built-in chromosome types using only '0's and '1's.

• Bitstring Chromosomes - Binary-encoded or Gray-encoded values efficiently stored using a single bit per allele.
• Boolean Chromosomes - Boolean values ('TRUE' and 'FALSE', or equivalently '0' and '1') stored in arrays of short integer values. This scheme consumes much more memory, but may be more rapid depending on the exact details of the computation. These chromosomes are guaranteed to be platform independent, although, in practice the bitstring chromosomes are also platform independent if a little care is taken.

Bitstring Utility Functions

When coding genetic algorithms using bitstrings, a set of functions within GAUL are highly beneficial. The functions described below may be used by external code for handling and manipulation of binary-encoded and Gray-encoded bitstrings. A datatype named "byte" is used to store a certian number of bits. These utility functions use an array of bytes to store the required number of bits. In the interests of efficiency, it is the caller's responsibility to track the length of the bitstrings and not overflow them.

• byte *ga_bit_new(int size) - Allocate a new bitstring. 'size' specifies the number of bits.
• void ga_bit_free(byte *bstr) - Deallocate a bitstring, 'bstr'.
• void ga_bit_set(byte *bstr, int n) - Set (i.e. change to '1') a single bit.
• void ga_bit_clear(byte *bstr, int n) - Clear (i.e. change to '0') a single bit.
• void ga_bit_invert(byte *bstr, int n) - Toggle (i.e. flip value) a single bit.
• boolean ga_bit_get(byte *bstr, int n) - Return the value of a single bit.
• void ga_bit_randomize(byte *bstr, int n) - Randomly define a single bit.
• void ga_bit_copy(byte *dest, byte *src, int ndest, int nsrc, int length) - Copies a sequence of bits from one bitstring to another bitstring. If the destination and source bitstrings are the same, this function is safe for copying between overlapping regions.
• size_t ga_bit_sizeof(int length) - Return the minimum size of the array of bytes required to store a given number of bits.
• byte *ga_bit_clone(byte *dest, byte *src, int length) - Copies a bitstring. Pass NULL pointer as dest if allocation of new bitstring is required.
• byte *ga_bit_decode_binary_uint(byte *bstr, int n, int length) - Convert a binary-encoded bitstring into an unsigned int starting at a given offset.
• void ga_bit_encode_binary_uint(byte *bstr, int n, int length, unsigned int value) - Convert an unsigned int into a binary-encoded bitstring starting at a given offset.
• byte *ga_bit_decode_binary_int(byte *bstr, int n, int length) - Convert a binary-encoded bitstring into a signed int starting at a given offset.
• void ga_bit_encode_binary_int(byte *bstr, int n, int length, unsigned int value) - Convert a signed int into a binary-encoded bitstring starting at a given offset.
• byte *ga_bit_decode_gray_uint(byte *bstr, int n, int length) - Convert a Gray-encoded bitstring into an unsigned int starting at a given offset.
• void ga_bit_encode_gray_uint(byte *bstr, int n, int length, unsigned int value) - Convert an unsigned int into a Gray-encoded bitstring starting at a given offset.
• byte *ga_bit_decode_gray_int(byte *bstr, int n, int length) - Convert a Gray-encoded bitstring into a signed int starting at a given offset.
• void ga_bit_encode_gray_int(byte *bstr, int n, int length, unsigned int value) - Convert a signed int into a Gray-encoded bitstring starting at a given offset.
• byte *ga_bit_decode_binary_real(byte *bstr, int n, int length) - Convert a binary-encoded bitstring into a double starting at a given offset.
• void ga_bit_encode_binary_real(byte *bstr, int n, int length, unsigned int value) - Convert a double into a binary-encoded bitstring starting at a given offset.
• byte *ga_bit_decode_gray_real(byte *bstr, int n, int length) - Convert a Gray-encoded bitstring into a double starting at a given offset.
• void ga_bit_encode_gray_real(byte *bstr, int n, int length, unsigned int value) - Convert a double into a Gray-encoded bitstring starting at a given offset.

Bitstring Operators

The built-in seed, mutation and crossover operators for bitstring chromosomes are:

ga_seed_bitstring_random()
ga_mutate_bitstring_singlepoint()
ga_crossover_bitstring_singlepoints()
ga_crossover_bitstring_doublepoints()
ga_crossover_bitstring_mixing()
ga_crossover_bitstring_allele_mixing()

Boolean Operators

The built-in seed, mutation and crossover operators for boolean chromosomes are:

ga_seed_boolean_random()
ga_seed_boolean_zero()
ga_mutate_boolean_singlepoint()
ga_mutate_boolean_multipoint()
ga_crossover_boolean_singlepoints()
ga_crossover_boolean_doublepoints()
ga_crossover_boolean_mixing()
ga_crossover_boolean_allele_mixing()

Examples

The exploratory "onemax" problem is implemented using the bitring chromosome in onemax.c.

John Holland proposed a GA benchmark known as the "royal road" problem. This is implemented using both chromosome types in royalroad_boolean.c and royalroad_bitstring.c. These examples may be used to compare the relative performance of the chromosome types.

Another example utilizing the boolean chromosome is wildfire.c.