Data Mining - Mehmed Kantardzic [223]
4. GAs’ flexibility facilitates both structure and parameter identification in complex models.
The GA theory provides some explanations of why, for a given problem formulation, we may obtain convergence to the sought optimal point. Unfortunately, practical applications do not always follow the theory, the main reasons being:
1. the coding of the problem often moves the GA to operate in a different space than that of the problem itself;
2. there are practical limits on the hypothetically unlimited number of iterations (generations in the GA); and
3. there is a limit on the hypothetically unlimited population size.
One of the implications of these observations is the inability of GAs, under certain conditions, to find the optimal solution or even an approximation to the optimal solution; such failures are usually caused by premature convergence to a local optimum. Do not forget that this problem is common not only for the other optimization algorithms but also for the other data-mining techniques.
13.2 OPTIMIZATION USING GAs
Let us note first that without any loss of generality we can assume that all optimization problems can be analyzed as maximization problems only. If the optimization problem is to minimize a function f(x), this is equivalent to maximizing a function g(x) = −f(x). Moreover, we may assume that the objective function f(x) takes positive values in its domain. Otherwise, we can translate the function for some positive constant C so that it will be always positive, that is,
If each variable xi, with real values, is coded as a binary string of length m, then the relation between the initial value and the coded information is
where the variable xi can take the values from a domain Di = [a, b], and m is the smallest integer such that the binary code has the required precision. For example, the value for variable x given on the domain [10, 20] is a binary-coded string with the length equal to 3 and the code 100. While the range of codes is between 000 and 111, the question is: What is the real value of the coded variable x? For this example, m = 3 and the corresponding precision is
and that is the difference between two successive xi values that could be tested as candidates for extreme. Finally, the attribute with the code 100 has a decimal value
Each chromosome as a potential solution is represented by a concatenation of binary codes for all features in the problem to be optimized. Its total length m is a sum of the features’ code lengths mi:
where k is the number of features or input variables for the problem at hand. When we introduce these basic principles of a code construction, it is possible to explain the main steps of a GA.
13.2.1 Encoding Schemes and Initialization
A GA starts with designing a representation of a solution for the given problem. A solution here means any value that is a candidate for a correct solution that can be evaluated. For example, suppose we want to maximize function y = 5 − (x − 1)2. Then x = 2 is a solution, x = 2.5 is another solution, and x = 3 is the correct solution of the problem that maximizes y. The representation of each solution for a GA is up to the designer. It depends on what each solution looks like and which solution form will be convenient for applying a GA. The most common representation of a solution is as a string of characters, that is, a string of codes for feature representation, where the characters belong to a fixed alphabet. The larger the alphabet is, the more the information that can be represented by each character in the string is. Therefore, fewer elements in a string are necessary to encode specific amounts of information. However, in most real-world applications, GAs usually use a binary-coding schema.
The encoding process transforms points in a feature space into a bit-string representation. For instance, a point (11, 6, 9) in a three-dimensional (3-D) feature space, with ranges [0, 15] for each dimension, can be represented as a concatenated binary