90 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) ISSN (Print) 2313-4410, ISSN (Online) 2313-4402 © Global Society of Scientific Research and Researchers http://asrjetsjournal.org/ Grass Root Algorithm Optimize Neural Networks for Classification Problem Prof. Dr. Hanan A.R. Akkara, Firas R. Mahdib* a,bElectrical Engineering Department, University Of Technology, Baghdad, Iraq aEmail: dr_hananuot@yahoo.com bEmail: firasrasool1980@gmail.com Abstract Artificial neural networks are computational models that trying to emulate the structure and functions of biological human networks. They have been extensively used in many applications include science, business, engineering, and data mining. Learning of an artificial neural network means how to adapt the weights of the network interconnections using suitable adaption algorithm. The training algorithms that is used to modify the weights of the network are considered the most important portion that influences the artificial networks performance. In the past few decade, many meta-heuristic algorithms have been used to optimize networks synaptic weights, in order to achieve better performance. This paper proposes a general network training method based on population-based algorithms, proposes a novel meta-heuristic algorithm that is inspired by the general grass plants root system to optimize the weights of the proposed artificial network to classify real data four classes XOR and Iris data comparing the obtained results of the proposed algorithm with other familiar evolutionary meta-heuristic algorithms. Keywords: Artificial neural networks; Classification; Grass root algorithm; Meta-heuristic techniques; Optimization; Population-based algorithms. 1. Introduction Artificial Neural Networks (ANNs) are information processing systems that have common characteristics with human biological networks. ------------------------------------------------------------------------ * Corresponding author. http://asrjetsjournal.org/ American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 4, pp 90-100 91 They have been widely used in many life applications such as medicine [1], financial [2], data mining [3], and industrials [4]. The most significant concern related to this concept is how to train the network to optimize a solution with the most trained weights. Learning of ANN is the process of adjusting the interconnection weights of the neurons. One of the most familiar training algorithms is the Error Back Propagation algorithm (EBP), this algorithm has been widely used for the network training purpose. However, it appears to be suffering from several problems such as easily trapped into local minima, and its low convergence speed [5]. Many types of research have been tried to improve the performance of the EBP, while other have just left this concept and used other meta-heuristic algorithms instead of EBP in the training phase. Therefore, many meta-heuristic algorithms have been developed and applied to raise the performance of the training process such as: Genetic Algorithm (GA) [6], Differential Evolution Algorithm (DEA) [7], Simulated Annealing (SA) [8], Artificial Bee Colony (ABC) [9], and Particle Swarm Optimization (PSO) [10]. This paper aims to propose a general method for optimizing Neural Networks (NNs) weights connections using population-based Grass Root Algorithm (GRA), that is proposed by the author, to classify four classes XOR problem, and 3 classes Iris real data sets comparing the results with other familiar population-based algorithms used for the same purpose. 2. Materials and Methods This paper uses a novel GRA to optimize an ANN weights interconnections to classify a real data four classes XOR problem and three classes Iris data set, comparing the obtained results with other population-based algorithms. The materials and methods used for that purpose are illustrated in the following sub-sections. 2.1. Multilayer Perceptron Multilayer Perceptron networks (MLPs) are popular feed-forward supervised ANNs. They consist of the input layer, an output layer, and one or multiple hidden layers. Usually, One hidden layer is sufficient to solve almost all types of problems. Two or more processing hidden layers rarely improve the network efficiency, also they may lead for trapping into a local minima solution. However, all hidden and output neurons are actually considered as the processing elements of the network. Each network layer is usually fully connected to the next layer, and it consists of multiple neurons, their number varies according to the problem the network used to solve. Each processing element neuron consists of multiplayer, adder, and activation function. Usually, each processing layer has the same activation function for all of its elements, neurons may have a linear identity activation function or nonlinear activation function such as hyperbolic tangent, logistic and Gaussian. One of the most important problems associated with NNs learning process is the overfitting, which usually occurs due to using too many neurons in the hidden layer, or when the ANN has too much information and the amount of input data patterns is not enough to justify all the neurons weights in the hidden layers at the required time. Another problem occurs when the training data set is satisfactory, but the amount of training time rise to a point that it is impossible to sufficiently learn the ANN. Therefore, some compromise must be reached between too many and few neurons in the hidden layers, another compromising method represented by regularization the network by modifying the performance function, which in most cases chosen to be the Mean Square Error (MSE) of the network. Once the number of neurons and hidden layers selected, the network's weights must be optimized to minimize the error made by the network. This is the role played by the training algorithms [11]. American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 4, pp 90-100 92 2.2. Metaheuristic Algorithms Meta-heuristics are techniques that allow optimizing large and complicated problems by delivering satisfactory and feasible solutions in an acceptable processing time. These techniques have no guarantee to find the global optimal solution. Unlike exact methods, they have the ability to solve large and complex problems. They have been used in many applications such as machine learning, data mining, system modeling, and robotics. Each meta-heuristic algorithm must have a tradeoff between, two contradictory features; diversification which is the exploration of the search space and intensification that represents the exploitation of the best solutions found so far. In intensification, the promising regions are explored more locally in the hope of finding better solutions. Meta-heuristic algorithms could be classified as population or single based search algorithm, these two families have complementary characteristics: single solution based meta-heuristics have the power to intensify the search in local regions only while population-based meta-heuristics allows better diversification in the whole search space [12]. Population-based meta-heuristic algorithms depend on initial random population, each individual in this population is a candidate solution. A new population of solutions is created, based on evolution or adapting blackboard algorithm. The evolution based reproduction of population using multiple of operators such as; crossover, and mutation. Therefore, a new population is generated from different attributes of the current population. Blackboard-based population generation depends on shared memory constructed from the previous population. The selection of the best solution will depend on the fitness value of the applied objective function after a set of rules that govern the population and redirect it towards an optimum or near optimum solution [13]. 2.3. Grass Root Algorithm Optimization is a mathematical technique that finds the best solution to a constrained problem, while an optimization problem is how to find variables that minimize or maximize an objective function, these variables must satisfy optimization function constraints. Many optimization problems have more than one local solution, therefore it is important to choose a good optimization method that has a good tradeoff between global and local search mechanisms without being trapped into a local minima solution. Grass Root Algorithm (GRA) is an optimization meta-heuristic population-based algorithm, it is essentially inspired from the grass plants reproduction, development, and theirs fibrous root system. To understand the proposed algorithm searching mechanism it's important to give a brief review for the reproduction and development of the grass plant. Grasses are generally propagated through two ways; firstly by modified subterranean stems of the plant that is usually found underground, sending out roots and shoots from its nodes that's called rhizomes, and secondly through a stems that grow just below the surface. Both reproduction ways will simultaneously develop secondary roots to replace the vanished primary roots. Hair roots are generated from secondary roots [14]. These roots (primary, secondary, and hair roots) are usually used for global and local searching of water resources and minerals. However, in GRA the global search will be performed at each iteration, while the local search performed when the global search is in stack condition or it does not lead to more improvement in the objective function. GRA has two different mechanisms for global search; survived grasses and the best obtained grass modified and reproduced. On the other hand, local search will have another two searching methods; regenerated secondary roots and secondary hair roots. American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 4, pp 90-100 93 2.3.1. GRA model governs rules Grass plants with rhizomes and stolons execute a global and local search to find better resources by reproduce new grass plants and modifying their own fibrous root system. Both the generated new grasses and their roots are developed almost randomly, but when a root arrives at a place with more resources, the corresponding plant generates more secondary roots, and root's hair, which made the plant growth faster than other. If a grass plant trapped into a local minima point it will generate more new grasses by stolons initiated from the best-obtained grass and from other grasses survived from the initial population process, these stolons are in general longer than rhizomes, which help the plant reaching farther places and escaping from local minima position. 2.3.2. GRA Mathematical Model Just like other meta-heuristic optimization algorithms, GRA starts with an initial random uniformly distributed population swarm(pop,ndim) in the search space domain of the problem, each row vector of swam initial matrix represents a grass initiated by seeding process. The number of initial grass plants is considered equal to the population size (pop). When iteration (iter) starts a new population NewSw(pop,ndim) will be generated, this new population will consist of; the fittest obtained grass represented by Gbest = min(f (swarm)) ∈ Rndim, f : Rndim → R , where f is the mean square error (MSE) function, ndim is the problem dimension, swarm and NeSw are bounded population in the range of lb(pop,ndim) ≤ swarm, NewSw ≤ ub(pop,ndim), where ub, lb ∈ Rndim are two matrices indicating the lower and upper bounds of population variables. The second element of the new population NewSw is a number (GN) of grasses deviated from Gbest by stolons (GrassBranches), these stolons usually deviated from the original grass with step size usually less than maximum ub, the last element of the NewSw are a new grasses equal to (pop – GN-1) deviated randomly from the survived best initial grasses (Survived deviated). 𝐺𝐺𝐺𝐺 = �� 𝑎𝑎𝑎𝑎𝑎𝑎(𝒎𝒎𝒎𝒎𝒎𝒎) 𝑎𝑎𝑎𝑎𝑎𝑎(𝒎𝒎𝒎𝒎𝒎𝒎)+𝑚𝑚𝑚𝑚𝑚𝑚(𝒎𝒎𝒎𝒎𝒎𝒎) � ∗ �𝑝𝑝𝑝𝑝𝑝𝑝 2 �� (1) Where GN is the number of the newly generated grass branches (stolons) from Gbest, and mse is the mean square error value of all grass population. From (1) we notice that the maximum generated new grass branches will be equal to (pop/2) and reached when the minimum of mse is too small. Each new branch grass deviated from Gbest according to (2), while the survived deviated grasses will be represented by: GrassBranches = ones(GN,1) * Gbest + 2 * max(ub) * (rand(GN,1) - 0.5) * Gbest (2) Surviveddeviated = GrassSurvived + 2 * max(ub) * (rand(pop–GN–1,1) - 0.5) * ub (3) where ones(c,1) represents one's column vector with c rows, and rand(c,1) is a random column vector with c rows their elements greater than 0 and less than 1. Grasssurvived is the (pop-GN-1) highest mse initial population. The new population (NewSw) will be represented by (4) and (5). NewSw = [ GbestT, GrassBranches T , Surviveddeviated T ]T (4) American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 4, pp 90-100 94 Which is the same as: NewSw = [ Gbest ; GrassBranches ; Surviveddeviated ] (5) The new reproduced population (NewSw) will be checked to find the grass with minimum mse and bounded it to be within the limits of ub and lb, If the fittest new grass is best than the old one then save the fittest new grass as the best solution, otherwise calculate the absolute rate of decrease in mse between the best obtained so far minimum mse (bestminmse) shown in (6) and the current iteration minimum mse (minmse) shown in (7), if the rate is less or equal a predefined tolerance value (tol) as in (8), than increase a global stack (stackg) counter by one, when stackg reached its maximum predefined value then move to the next local search mechanism. minmse = mini=1,…,pop (mse) (6) bestminmse=min j=1,…,iter (minmse) (7) � 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚−𝑏𝑏𝑚𝑚𝑚𝑚𝑡𝑡𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 ≤ 𝑡𝑡𝑡𝑡𝑡𝑡 � (8) The local search mechanism consists of two individual loops; secondary roots loop, and hair roots loop. We have considered that the hair roots are equal to the dimension of the objective function problem (ndim) so that each secondary root generated by the Gbest represents a local candidate solution. The secondary roots will be represented by a random number, these secondary roots will have a number of hair roots equal to ndim, each single hair root will modify its location according to (9) for a repeated loops equal to secondary roots number (S). m_gbest(1,i)i=1,..,ndim k=1.,.,S = avg(Gbest) + Gbest(1,i)i=1,.,ndim + C2 * (rand-0.5) (9) C = [C1 , C2 , C3 , C5 , …., C9 , C10] (10) Cc = C(1+ (‖𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 ∗ 10‖) ) (11) Where mgbest is the locally modified Gbest element by element, S is the number of secondary generated roots where (0 ≤S≤ ndim), and C is the searching step size vector equation (10), and Cc will be a random element of C chose according to the percentage repetition of C elements, as shown in (11). If the evaluated mgbest min(mse) is less than bestminmse then save Gbest as mgbest, otherwise calculate the absolute rate of decrease in mean square error as in (7), if the rate is less than tol then increase local stack counter (stackl) by one, if stackl reached its maximum predefined value then break hair root loop and begin new secondary root loop, after each completed iteration check if the stopping condition (GlobalError) is satisfied then stop iteration, otherwise go to next iteration until reached the maxit then stop. The pseudo code of GRA are as follow: 2.3.3. GRA for NN Weight Optimization GRA is a population based meta-heuristic algorithm, in which each Swarm contains a pop number of candidate American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 4, pp 90-100 95 solutions each with ndim dimensions, for NN case we have considered the weights vector of the supervised network is the problem that needs to be optimize in order to get the minimum mean square error between the network output and its predefined target. Suppose the input is input(N, n), target(N, m) is the target teacher. Therefore, N is the total input patterns, n is the number of input neurons, and m is the output neurons number. suppose l is the hidden neurons number, then the NN dimension with bias connections ndim will be represented by: ndim = ( n * l + l ) + ( l * m + m ) (12) Table 3 Initialize: maxit, pop, ndim, lb, ub, GlobalError, tol, stackg, stackl, BranchGrass, C, Gbest, minmse, bestminmse , GN, F. Initialize random grass population (Swarm). where: Swarm∈ Rndim Bound the initial population lb≤ 𝐒𝐒𝐒𝐒𝐒𝐒𝐒𝐒𝐒𝐒 ≤ 𝐮𝐮𝐮𝐮 where: ub, lb ∈ Rndim. For i=1 : pop // check for best fitness particle in the initial population. mse(i)= F(Swarm) // F is the MSE predefined function End For Sort the grass population (Swarm) ascending according to mse. For iter=1 : maxit // Iteration and global search starting Evaluate C2 according to (8) Generate the new population (NewSw) according to (4). Bound NewSw : lb≤ 𝐍𝐍𝐍𝐍𝐒𝐒𝐒𝐒𝐒𝐒 ≤ 𝐮𝐮𝐮𝐮 where:NewSw, ub, lb ∈ Rndim For i=1: pop // check the NewPar for the best fitness particle loop Mse(i)=F(NewSw) End For Minmse=min(Mse) // Save minimum mean square error Index the grass with the Minmse // Index the position of the best particle in the population. Evaluate GN as in (1). // GN is the number of stolons branches. Evaluate 𝐆𝐆𝐒𝐒𝐒𝐒𝐆𝐆𝐆𝐆𝐁𝐁𝐒𝐒𝐒𝐒𝐁𝐁𝐁𝐁𝐁𝐁𝐍𝐍𝐆𝐆 as in (2). Evaluate the GrassSurvived from the ascending sorted Swarm. Evaluate 𝐒𝐒𝐮𝐮𝐒𝐒𝐒𝐒𝐒𝐒𝐒𝐒𝐍𝐍𝐝𝐝𝐝𝐝𝐍𝐍𝐒𝐒𝐒𝐒𝐒𝐒𝐝𝐝𝐍𝐍𝐝𝐝 as in (3). If Minmse < bestminmse then bestminmse=Minmse Gbest=best indexed grass stackg=0 Else If (7) is true then increase stackg by 1 If stackg is at its maximum then stackg= 0 // Begin the local search American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 4, pp 90-100 96 For q=1:random integer less than D // secondary root loop Stackl=0 For j=1:ndim // hair root loop mgbest=Gbest //initial mgbest evaluate mgbest as in (8) localmin = F(mgbest) If localmin