Abstract
Genetic Algorithm (GA) (a structured framework of metaheauristics) has been used in various tasks such as search optimization and machine learning. Theoretically, there should be sound framework for genetic algorithms which can interpret/explain the various facts associated with it. There are various theories of the working of GA though all are subject to criticism. Hence an approach is being adopted that the legitimate theory of GA must be able to explain the learning process (a special case of the successive approximation) of GA. The analytical method of approximating some known function is expanding a complicated function an infinite series of terms containing some simpler (or otherwise useful) function. These infinite approximations facilitate the error to be made arbitrarily small by taking a progressive greater number of terms into consideration. The process of learning in an unknown environment, the form of function to be learned is known only by its form over the observation space. The problem of learning the possible form of the function is termed as experience problem. Various learning paradigms have ensured their legitimacy through the rigid space interpretation of the concentration of measure and Dvoretzky theorem. Hence it is being proposed that the same criterion should be applied to explain the learning capability of GA, various formalisms of explaining the working of GA should be evaluated by applying the criteria, and that learning capability can be used to demonstrate the probable capability of GA to perform beyond the limit cast by the No Free Lunch Theorem.
TopIntroduction
Genetic Algorithm (GA) has been one of the most frequently used metaheuristic for the complex engineering optimization problems for five consecutive years (Senvar, Tanoglu, & Kaharaman, 2012). It was introduced by Holland (Holland, J. H., 1968). It was popularized by Goldberg (Goldberg, D. E., 1989), the version of GA using on the fixed binary encoding and cross over and mutation operators, has been used in various tasks. Genetic algorithms are design method instead of a readymade problem solver (Moraglio, A. & Togelius, J. 2007). Genetic algorithm is often assumed to be an optimization technique. However, in the Holland’s original design of the adoptive systems it had a fairly little place. His well known co-workers Dejong and Goldberg made the assertions to appreciate this overemphasis. The same has been stated to be a misplaced overemphasis by De Jong himself (DeJong, K., 2006). GA has been used in solving almost all sorts of problems including bin-packing (Reeves 1996), Knapsack (Thiel & Vob 1994), Resource Sharing and scheduling problem (Pinto, Israele, Airbinder, & Rabinowitz, 2010), Manufacturing (Chauhan, Deep, & Pant, 2012), power system analysis (Milani & Mazaferi, 2012). Ibrahim H. Osman and Laporte (Osman & Laporte, 1996) also presented a detailed bibliography including the applications of GA. The versatility of the GA in various applications makes the problem solving easier.
But on the other hand it emphasizes on issue of understanding the working of GA. It is often felt that there should be sound theoretical framework for GA to interpret and explain the various facts like how the genetic algorithm works or how well it will perform on a particular problem; and what convergence rate will be. This information shall be useful in recommending the parameter setting for particular solution. The present state of art of the theory of GA lefts much to be desired to achieve the objective stated previously. Reeves and Rowe (Reeves & Rowe, 2002) present an extensive and updated results about the works conducted in this area. Moreover, they have been presenting his article on GA theories in conference companion on “Genetic: An evolutionary conference” (Tech. Report CSM-467, 2007). The theoretical basis of GA (i.e. how they work) is still an issue being debated among the various schools of thought. However, the main concepts provided and accepted with some respectable degree of legitimacy are being considered.
Key Terms in this Chapter
Measure: Formally, a measure µ is a function defined on a s-algebra S over a set X and taking values in the extended interval [0, ?] such that the following properties are satisfied: (1)The empty set has measure zero . (2) A probability measure is a measure with total measure one i.e., p ( X )=1, a probability space is a measure space with a probability measure.
Metaheuristic: A meta-heuristic is a heuristic approach of solving a general class of computational problem by combining heuristics themselves in a hopefully efficient way.
Hyperplane: A hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions. A hyperplane of an n-dimensional space is a flat subset with dimension. By its nature, it separates the space into two half spaces.
Probability Density: In probability theory, a probability density function p(X), or density of a function continuous random variable , is a function that describes the relative likelihood for this random variable to take on a given value.
Feature Space: In pattern recognition, a feature space (O ? ) is an abstract space where each pattern sample is represented as a point in n-dimensional space . Its dimension is determined by the number of features used to describe the patterns. Similar samples are grouped together, which allows the use of density estimation for finding patterns.
Schema: A schema is a template in computer science used in the field of genetic algorithms that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets ; and so form a topological space .
Stationary: A stochastic process is said to be a stationary if its joint probability distribution Environment does not change upon shifting in time or space.
Metric Space: In general let Y be a metric space with metric d, then the set F ={ f i : XY , i ? I } is called uniformly bounded if there exists an element a from Y and a real number M such that d ( f i ( x ), a )= M ? x ? X .
Uniformly Bounded: In mathematics, bounded functions are functions for which there exists a lower bound and an upper bound, in other words, a constant which is larger than the absolute value of any value of this function. If we consider a family of bounded functions, this constant can vary between functions. If it is possible to find one constant which bounds all functions, this family of functions is uniformly bounded.
Encoding: A representation of S will be taken a set C (the representation space or the space of chromosomes) of size at least equal to S, together with a surjective function g(the growth function) that maps C onto S: g: C ? S
Measurable Function: In mathematics, measurable functions are well-behaved functions between measurable spaces. Functions studied in analysis that are not measurable are generally considered pathological. If S is an s-algebra over a set X and ? is an s-algebra over Y, then a function f:X ? Y is measurable S/? if the pre-image of every set in ? is in S. By convention, if Y is some topological space, such as the space of real numbers {R} or the complex numbers {C} , then the Borel s-algebra generated by the open sets on Y is used, unless otherwise specified. The measurable space ( X , S) is also called a Borel space in this case. Banach spaces are defined as complete normed vector spaces . This means that a Banach space is a vector space V over the real or complex numbers with a such norm||.|| that every Cauchy sequence (with respect to the metric d ( x , y )=|| x-y| | in V has a limit in V. Since the norm induces a topology on the vector space, every Banach space is necessarily metrizable and metrizable spaces generally have very interesting properties.
Sigma-algebra: In mathematics, a s-algebra (or sigma-algebra ) ( sigma is a Greek letter, upper case S, lower case s) over a set X is a nonempty collection S of subsets of X (including X itself) that is closed under complementation and countable unions of its members. It is a Boolean algebra, completed to include countable infinite operations. The pair ( X , S) is also a field of sets, sometimes called a s-field or a measurable space. Thus, if one possible sigma algebra on X is S={ ? ,{ a , b },{ c , d },{ a , b , c , d }}.