Applications of Genetic Algorithms to Neural Networking - Term Paper Example

0 Genetic Algorithm 1 Introduction Genetic algorithm refers to search techniques which are based on experience that are used for purposes of solving problems, discovery and even learning. These search techniques imitate natural evolution. They use simulated evolution (Weisman & Pollack, 1995). Here a group of strings which are referred to as chromosomes and sometimes the genotype of the genome, usually encode candidate solutions which are also known as individuals and sometimes called creatures or phenotypes to a problem and this problem evolves to an optimal solution. Problems used to be in form of binary strings of 0s and 1s. Currently, there is usage of other encodings. This evolution normally begins from a group of randomly created phenotypes and this process takes place through generations. During each generation, the fitness of each individual in the population/group is cross examined, multiple phenotypes are chosen from the group as per their fitness and then they are modified and can be randomly mutated to create a new population which is then used in the iteration calculations whose procedure is step-by-step also known as the algorithm. This algorithm is mostly terminated after the production of a maximum number of generations. A fulfilling solution may or may not be accomplished if the algorithm has been terminated when because of a maximum number of generations. The most widely accepted representation of the result is using an array of bits. Any other arrays can be used similarly. What makes the representation that uses genetics convenient is the fact that their parts can be aligned conveniently because of their fixed size. This facilitates easy crossover operations. 1.2 Applications and results of Genetic Algorithm 1.2.1Metaheuristic This term is designated from a computational method which optimizes problems through iteration. This iteration tries to improve the solution of a candidate as per a given measure of quality. Few or no assumptions are made about the problem being optimized. As far as candidate solutions are involved it can search very large spaces. However, optimal solutions are not guaranteed to be found by Metaheuristic. Stochastic optimization is mostly implemented in a metaheuristic way. It can also be referred to as: Derivative free Direct search Black box Heuristic optimizer 1.2.2 Computational creativity This is also referred to as artificial, mechanical creativity and sometimes creative computation. It comprises of the bringing together of fields such as cognitive psychology, artificial intelligence and philosophy. Computational creativity improvises the combinational perspective which allows one to model creativity in form of a search procedure through several possible combinations. These combinations can be as a result of composition of different representations. Cross over representations which capture different inputs can be generated using neural networks and genetic algorithms. 1.2.3 Multiple sequence alignment This refers to a sequence alignment of at least 3 biological sequences namely: Protein Dna Rna Most of the times the sequences are assumed to have an evolutionary relationship through which they are descended from a common ancestor hence share a lineage. As a result, sequence homology can be inferred from the Multiple Sequence Alignment and to look into the sequences’ shared evolutionary origins phylogenetic analysis is carried out. In trying to widely simulate the evolutionary process which gave rise to the broadening of the query set, genetic algorithms have been used for production of Multiple Sequence Alignment.This is done by breaking several potential MSAs into pieces and rearranging the pieces repeatedly.Gaps are introduced at several positions.During simulation a common objective function is achieved which is the sum-of-pairs function that emerges in the broad programming Multiple sequence alignment. 1.3 GA (genetic algorithm) used with NN (neural networks) 1.3.1 Evolving weights The frequent use of GA with NN is because genetic algorithms are good at perusing a state space. The genetic algorithm should be set up to develop a string of floating point numbers (which should be within the range specified) which can be used as the weights of the network. The problem with the use of genetic algorithm comes when the range of the weights is being specified. The network weights however are not supposed to be too big. For example, “The absolute XOR net weights don't get larger than 3.” The other problem with GA and NN is finding out the appropriate way of replicating and crossing over most of the weights. This depends on how the weights have been set up. As per our example using the XOR net weights, the weights can be easily represented in a 3*3-array. Figure1. XOR network m_fWeights[3][3] 0 0 0 0 0 0 0 0 0 In this set up, the group of weights are swapped over (Mathews J. 2000). Two population examples are selected. That is: 1. Lower error (LE). 2. Higher error (He). The weights’ representation will not be as simple if the neural network happens to be more complicated. It is recommended that the weights are grouped together. The weights that will result will not be as good as the random ones. One should consider a genetic operator. Mutation is one of the genetic operators you should consider. In the program example, there is a quite high (10%) chance of mutation, whereas the weights are changed by anything flanked by and 1. 1.3.2 Timing of usage Genetic algorithms are an alternative, but they are not by any chance always the most excellent alternative. The GA is a lot slower than BP (back propagation) when applied to the Xor problem. The GA (genetic algorithm) gives improved results than the BP example used: B.P: 0,0 = 0.0494681 0,1 = 0.955633 1,0 = 0.942529 1,1 = 0.0433488 G. A: 0 Xor 0 = 2.47602e-005 0 Xor 1 = 0.997028 1 Xor 0 = 0.999292 1 Xor 1 = 0.010474 Table1. Comparison between BP and GA The GA finds more precise results, but the back-propagation is close to instantaneous. However, the genetic algorithm will take anything between 5-20 seconds (233 MHz test computer). 1.3.3 Architecture Since the overall architecture of the network is essential to the operation, a broad study has focused on using evolutionary techniques to evolve the best architecture (much similar to the development of our own brainpower). One simple method is to use a Boolean (N x N) matrix, (where N is the quantity of neurons in the neural network). Any given place on the matrix represents a connection between the X and Y neurons. For example, for the Xor Network: 1 2 3 4 5 1 0 0 1 1 0 2 0 0 1 1 0 3 0 0 0 0 1 4 0 0 0 0 1 5 0 0 0 0 0 Table2. Connection between neurons X and Y for a Xor network This is a very easy way, and gets inefficient for the huge NNs that optimization in architecture is often applied to. 1.4 Genetic Programming This refers to an evolutionary algorithm based technique influenced by biological evolutionwhich search for a computer that carries out tasks that have been defined by the user. It is also specialized in genetic algorithm of which each individual represents a computer. It is a machine learning methodology which is used to make effective a computer programs population in accordance to a fitness landscape which is determined by the program’s capability to do a given computational command. The main aim of having computers solve problems automaticallyis the basis of artificial intelligence and machine learning. As Arthur Samuel explained, the chief objective of machine learning and (A.I) artificial intelligence is “to get machines to behave like humans through the use of intelligence”. Genetic programming can be therefore defined as an evolutionary computation that accepts problems and solves them without the need of the user to have the knowledge or be aware of the form of the solution to theproblem. It is a domain independent and systematic way of making computers solve problems automatically beginning from a high level statement of what should be accomplished.Genetic programming has generated a lot of interestfrom so many people across the globe since its inception. 1.5 Survey of the whole area of "Evolutional Computing" Evolutionary computing refers to a branch of Artificial Intelligence which is involved in combinational optimization problems. It makes use of continuous progress for example: growth and development in a population. Parallel processing is used to select the population in a guided random. Theinspirations of these processes are mostly biological mechanisms of evolution. Evolution has many applications in computer science since has the ability to produce processes and networks that are highly optimised. Nils Aall Barr celli started the simulations of evolution by the implementation of artificial life and evolutionary algorithm. Alex Fraser happens to be the one who extended these simulations. He also published several papers based on the simulation of artificial-selection. Ingo rechenberg used evolution strategies which solved complex engineering problems in the 1960s and early 1970 that widely popularised artificial evolution. John Holland popularised genetic algorithms. This popularity of the computer in the academic field came along with increased power of the computers which allowed practical applications such as the automatic evolution of computer programs. Multi-dimensional problems are now solved using evolutionary algorithms which are more efficient than the software that would be designed by human designers. It also optimises the system’s design. In automated problem solving, Darwinian principles were not used until the fifties. It was in the nineteen sixties that three interpretations of the idea began to be developed in 3 different locations: 1. Evolutionary programming by Lawrence J. Fogel in the USA. 2. Genetic algorithm (GA) by John Henry Holland. 3. Evolution strategies by Ingo Rechenberg and Hans Pauls Schwefel in Germany. The areas were developed separately for approximately 15 years. But since the nineties they were unified and seen as individuals representatives of one technology referred to as evolutionary computing. In the early nineties a fourth interpretation emerged known as genetic programming. At the same time evolutionary computation became swarm-based computation, and algorithms inspired by nature increasing became a big part. In evolutionary computation, evolution algorithms are a subset of evolutionary computation in that they involve only techniques that have mechanisms influenced by biological evolution methods such as mutation natural selection reproduction recombination Survival of the fittest. In the optimization problem, candidate solutions are equivalent to individuals in a population and cost function is the main determinant of where solutions live. Only after the repeated application of these operators does evolution take in a population. There are two main forces that make up the basis of evolutionary systems: 1. Recombination 2. Mutation These two create the required diversity hence facilitate novelty; meanwhile, selection is the force increasing quality. Most of the aspects of these are non-deterministic. Pieces of that have been changed during the recombination and mutations are randomly selected. The selection operators however could be deterministic or non-deterministic.Individuals whose fitness is higher are more likely to be selected than individuals whose fitness is lower. Nevertheless, weaker individuals have the chance to survive or to even become parents. 1.6 Conclusion These are only 2 applications of GAs to neural networking (NN) - other areas comprise of local minima avoidance, function minimizing plus other "tweaking" techniques. Keep in mind that every parameter can be evolved using a GA. However, the amount of its effect to the overall performance of the neural network varies from parameter to parameter. The weights are obviously the most significant. Remember to use only a genetic algorithm when other training methods are ineffective, not practical or you feel that GAs will provide an improvement over other training methods. References Mathews, J. (2000): Using genetic algorithms with neural networks retrieved from http://www.generation5.org/content/2000/nn_ga.asp?Print. Weisman, O. & Pollack, Z. (1995): Neural network using genetic algorithms Retrieved from http://www.cs.bgu.ac.il/~omri/NNUGA/. Read More