An Analysis of Non-Binary Genetic Algorithms with Cardinality 2υ
Siddhartha Bhattacharyya
Department of Management,
College of Business and Administration,
Southern Illinois University at Carbondale,
Carbondale, IL 62901, USA
Gary J. Koehler
Decision and Information Sciences Department,
College of Business, University of Florida,
Gainesville, FL 32611, USA
Abstract
Genetic algorithms provide a stochastic search technique inspired by principles of natural genetics and evolution. They operate through a simulated evolution process on a population of string structures, each of which represents a candidate solution in the search space. Evolution of populations involves two basic steps: (1) a selection mechanism that implements a survival of the fittest strategy, and (2) genetic recombination of the selected high-fitness strings to produce offspring for the new generation. Recombination is effected through the two biologically inspired operators of crossover and mutation. Selection ensures that above-average strings contribute to a greater number of offspring in the next generation (on average).
Genetic algorithms (GAs) are considered suitable for application to complex search spaces and combinatorial optimization problems, where a balance is often sought between full exploitation of the currently known solutions and a robust exploration of the entire search space. GAs provide an effective means for managing this tradeoff. The selection scheme operationalizes exploitation, and the recombination operators effect the exploration of the search space.
A number of researchers have reported success with GAs applied across a wide spectrum of problems, including process control [18], communication network design [7], to learning models of consumer choice [20], nonlinear dynamical models of sociological phenomena [11], simulation of rational agents in socio-economic contexts, and scheduling of jobs on a production floor [4, 6, 25, 26, 38, 39].
GAs use an encoding of the search space attributes. The coding scheme is critical to the success of GAs, and traditionally a binary string representation has been used. The use of a binary representation is advocated by the Schema Theorem and the principle of minimal alphabets [15], which maintains that lower cardinality alphabets facilitate higher schemata processing, and thus foster the parallelism that is implicit in genetic processing. As a consequence, most theoretical studies have been conducted in terms of a binary scheme.
Empirical results have shown the value of high cardinality representations. In this paper we provide extensions to a theoretical model of binary-coded genetic search [35] to enable consideration of higher cardinality alphabets. An exact representation of GA search using higher cardinality alphabets is presented.
The organization of the paper is as follows. Section 2 briefly examines the motivation for the study of non-binary GAs. Section 3 then provides an account of the Schema Theorem and the Vose-Liepins framework. The main results of this research are then presented in section 4.
