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.