Civl080903.qxd 1. Introduction Inverse problems often occur in many branches of engi- neering and mathematics where the values of some phys- ical model parameter(s) must be deduced from observed data. System identification comes under the category of inverse problems. It is the process of determining the parameters of a system based on the observed input and _______________________________________ *Corresponding author’s email: skris@iitm.ac.in output (I/O) of the system. In structural engineering, sys tem identification is used to determine unknown parame- ters such as mass, stiffness and damping properties of a structure. Structural identification methods can be classi- fied under various categories, eg. frequency domain and time domain, parametric and nonparametric methods. Inverse problems can be solved using classical and non- classical methods. The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 Structural System Identification in the Time Domain using Evolutionary and Behaviorally Inspired Algorithms and their Hybrids S. Sandesha , Abhishek Kumar Sahua and K. Shankar*b a Research Scholars, Department of Mechanical Engineering, Indian Institute of Technology, Madras, Chennai 600 036, India *b Department of Mechanical Engineering, Indian Institute of Technology, Madras, Chennai 60 036, India Received 3 September 2008; accepted 1 March 2009 Abstract : In this study, parametric identification of structural properties such as stiffness and damping is car- ried out using acceleration responses in the time domain. The process consists of minimizing the difference between the experimentally measured and theoretically predicted acceleration responses. The unknown param- eters of certain numerical models, viz., a ten degree of freedom lumped mass system, a nine member truss and a non-uniform simply supported beam are thus identified. Evolutionary and behaviorally inspired optimization algorithms are used for minimization operations. The performance of their hybrid combinations is also investi- gated. Genetic Algorithm (GA) is a well known evolutionary algorithm used in system identification. Recently Particle Swarm Optimization (PSO), a behaviorally inspired algorithm, has emerged as a strong contender to GA in speed and accuracy. The discrete Ant Colony Optimization (ACO) method is yet another behaviorally inspired method studied here. The performance (speed and accuracy) of each algorithm alone and in their hybrid combinations such as GA with PSO, ACO with PSO and ACO with GA are extensively investigated using the numerical examples with effects of noise added for realism. The GA+PSO hybrid algorithm was found to give the best performance in speed and accuracy compared to all others. The next best in performance was pure PSO followed by pure GA. ACO performed poorly in all the cases. Keywords: Inverse problem, System identification, Genetic algorithm, Ant colony optimization, Particle swarm optimization É¡JÉæ«ég ™e É«cƒ∏°S ¬ª¡∏e h ájQƒ£J äÉ«eRQGƒN ∫ɪ©à°SÉH øeõdG π≤M ‘ »FÉ°ûf’G ΩɶædG ájƒg ~j~– QɵfÉ°T .∑ h ƒgÉ°S QÉeƒc ∂°ûæ¡HG h ¢T~fÉ°S .¢S áá°°UUÓÓÿÿGG¢ü«∏≤J øe á«∏ª©dG ¿ƒµàJ .øeõdG π≤M ‘ π«é©àdG äÉHÉéà°SG ∫ɪ©à°SÉH √ò«ØæJ ” ~b ÚgƒàdG h IhÉ°ù≤dG πãe á«FÉ°ûf’G ¢UGƒî∏d ájƒ¡dG ¢ü«î°ûJ ” á°SGQ~dG √òg ‘ : ¿ƒ∏ªL ‘ ájô◊G øe äÉLQO ô°ûY øe ¬ÄJÉædG ¬∏àµdG AGREG ᫪bôdG êPɪædG ¢ ©H ‘ áeƒ∏©ŸG ÒZ ±GôW’G ¿G .É«ÑjôŒ á°SÉ≤ŸG ∂∏J h Éjô¶f á°SÉ≤ŸG ¬∏é©ŸG äÉHÉéà°S’G ÚH ¥ôØdG áÑ«cÎdG AGOG á°SGQO ∂dòc ” .äÉ«∏ª©dG ¢ü«∏≤àd É«cƒ∏°S ¬ª¡∏eh ájQƒ£J äÉ«eRQGƒN ∫ɪ©à°SG ” .É¡°ü«î°ûJ ” ~b ᣰùÑe ᨫ°üH ∫ƒªfih º¶àæe ÒZ πµ°ûH πªfih AÉ° YG ¬©°ùJ øe ) á«KGQƒdG äɪ«JQÉZƒ∏dG .¬æé¡ŸGGA) äÉ«Fõ÷G ~«°û– ¿EG .ΩɶædG ¢ü«î°ûJ ‘ É¡dɪ©à°SG ” ~bh G~«L áahô©e ájQƒ£J äÉ«ªKQÉZ ƒd »g (PSO¬ª¡∏e äÉ«eRQGƒN »gh ( ) ¤G …ƒb …~ëàªc Éãj~M äRôH ~b ±ô©àdGGA) πªædG Iôª©à°ùe á«∏YÉa ¬≤jôW .áb~dGh áYô°ùdG ‘ (ACOAGO’G .Éæg É¡à°SGQO â“ ~bh º¡∏e ±ô°üJ äGP á≤jôW ∂dòc »g ( ) πãe áÑcôŸG É¡àæ«ég h √OôØæe ᫪KQÉZƒd πµd áb~dGh áYô°ùdG hACOâ“ ~b »àdG AÉXƒ¶dG äGÒKÉJ ™e ᫪bQ êPɉ ∫ɪ©à°SÉH áØãµe √Qƒ°üH É¡ãëH ” ~b áæé¡e ᫪KQÉZ ƒd ( ) øé¡ŸG ºKQÉZƒdG ¿G .á«©bGƒdG πLG øe É¡àaÉ°VGPSO +GA) ƒg AGO’G ‘ á«∏j …òdG äÉjôN’ÉH áfQÉ≤e áb~dG h áYô°ùdG ‘ AGOG π° aG »£©j ¬fÉH ~Lh ~b (PSO¢üdÉÿG ( ) ¬©ÑàjhGA) AGOG ¿Éc ¢üdÉÿG (ACO .ä’É◊G ™«ªL ‘ ∞«©°V ( áá««MMÉÉààØØŸŸGG ääGGOOôôØØŸŸGG .äÉÄjõ÷G ~«°û– á«∏YÉa,πªædG Iôª©à°ùe á«∏YÉa ,»KGQh ”QÉZƒd ,ΩɶædG ¢ü«î°ûJ ,áHƒ∏≤ŸG ádÉ°ùŸG : 65 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 1.1 Classical Methods The least square method is perhaps the simplest classi- cal methods for structural identification. It estimates the unknown parameters of structural system by minimizing the sum of squared errors between the predicted outputs and the measured outputs. Many other classical methods such as maximum likelihood method, instrument variable method and extended Kalman filter method have been developed. Koh et al. (1991) used the Kalman filter method for identification of stiffness and damping coeffi- cients from measurement of dynamic responses in the time domain. Detailed information about classical meth- ods and non-linear identification are presented in the review paper by (Gaetan et al. 2006). Some classical opti- mization methods such as gradient methods (typically variations of Cauchy, Newton and Levenburg-Marquardt methods) need a good initial guess of the parameters to converge fast and accurately. Some studies have been conducted to supply good initial values using non-tradi- tional methods such as GA which would sample the search domain efficiently. Thus certain classical methods such as Levensburg-Marquardt were hybridized with GA to identify system parameters with less computational time and improved accuracy (Kishore et al. 2007 and Friswell et al. 1998). 1.2 Evolutionary Algorithms and Behaviourally Inspired Algorithms Evolutionary algorithms are robust optimization algo- rithms based on the heuristic concept of natural selection and genetic operations. Optimization algorithms find the minima or maxima of functions in a given function domain. Over the past few decades the area of genetic algorithm (GA) has been widely developed and applied for structural identification. Unlike classical methods, there is no requirement for calculation of gradients and second derivatives which frequently lead to numerical instability. GA applications in system identification such the identification of elastic properties of composite plates from dynamic test data is presented in (Jesiel et al. 1999; Chakraborthy and Mukhopadhyaya 2002). Recently efforts have been made to alter the architecture of GA and to incorporate local search algorithms to further improve its performance, see for example see (Koh et al. 2003 and Perry et al. 2004). Behaviorally inspired optimization algorithms have been developed out of attempts to model the natural behavior of a flock of birds or a colony of ants. Social insects have diverse foraging systems that reflect the enor- mous range of ecological conditions in which they oper- ate. Ant colony optimization (ACO) and Particle swarm optimization (PSO) techniques are inspired by real ant colonies and flock of birds respectively. 2. Ant Colony Optimization (ACO) Ant colonies continually adjust foraging effort to changing conditions. Individuals use local information in foraging decisions and colonies can tune foraging effort to the location, quality and abundance of food. ACO is a gen- eral purpose Combinatorial Optimization (CO) technique. CO optimization is one of the youngest and most active areas of discrete mathematics. As the name suggest CO deals with finding optimal combination of available prob- lem components. Hence, it is required that the problem is portioned into a finite set of components and CO algo- rithm attempts to find the optimal combination. ACO, a meta-heuristic which is based on the Ant System introduced in the early nineties by (Dorigo 1992 and Dorigo et al. 1996). It has been used to solve a vari- ety of combinatorial optimization problems, eg. the vehi- cle routing problem by (Bullnheimer et al. 1999) the trav- eling salesman problem by (Dorigo et al. 1997) and the industrial layout problems studied by (Hami et al. 2007; Corry and Kozan 2004 and Rajamani and Adil 1996). Abbospour et al. (2001) proposed the ACO-IM (Inverse Modeling) method for estimating soil hydraulic parame- ters. They compared results of ACO-IM with Levenberg- Marquardt (LM) method and finally complimented ACO and LM to obtain final solution which was better than pure ACO itself. Some extensions and variants of ACO are pre- sented in the review paper by (Blum 2005). Recently ACO has been applied to structural optimiza- tion and topology optimization. The goal of truss opti- mization is to optimally utilize the geometry and material of the proposed design elements to result in the lightest structure satisfying all the design, manufacturing con- straints and other physical constraints. Since ACO is a dis- crete CO problem, several studies using it to optimize steel trusses for minimum weight using discrete cross sec- tional areas and other parameters were conducted, see (Camp et al. 2004; Camp et al. 2005 and Serra et al. 2006). These studies mapped the length of the tour of the ant to the weight of the truss and represented the volume of the element as virtual paths in ACO model for truss design. A biomechanical application of PSO is presented by (Jaco et al. 2005) where ankle joint model parameters were identified and compared with gradient methods such as sequential quadratic programming, quasi-Newton algo- rithm and GA. The PSO algorithm was found insensitive to design variable scaling and gradient methods are high- ly sensitive. The parameters of Lorenz chaotic system are estimated using PSO in reference (Qie et al. 2007). It was found that PSO converges to exact value with high popu- lation size and more effective than GA. A 10-dof structur- al dynamic model was identified using frequency response function by GA and PSO in (Mouser and Dunn 2005), without using hybrids. PSO was found more likely than GA to produce better parametric models. A PSO-GA hybrid was used to successfully identify faults in the water supply system in Japanese cities by (Furuta and Yasui 2005). However only a single case is studied, and com- parisons with pure GA and PSO are not shown for that case study, but only for benchmark equations. Recently PSO has been successfully applied in many research and application areas such as pattern recognition (Peng-Yeng et al. 2006), scheduling (Binghui et al. (2007)), layout 66 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 optimization (Zhang et al. (2007), and the design opti- mization of Unmanned Aerial Vehicle (UAV) with respect to flight loads (Hu et al. 2004). 2.1 The ACO Algorithm The inspiration for ACO is the foraging behavior of ants, particularly how they find the shortest paths between food sources and their nest. While searching for food, ants initially explore the area surrounding their nest randomly. When ants move they leave a chemical pheromone trail on the ground. When choosing their way, ants tend to favor paths marked by strong pheromone concentrations. As soon as an ant finds a food source, it evaluates the quanti- ty and the quality of the food and carries some of it back to the nest. During the return trip, the quantity of pheromone that an ant leaves on the ground may depend on the quantity and quality of the food. The pheromone trails will guide other ants to the food source. ACO model consists of graph G = (V, E) (Blum et al. (2005)) where V consists of two nodes, namely vs (nest) and vd (food source). E consists of two links e1 and e2 between vs and vd and corresponding length are l1 and l2 as shown in Fig. 1. Path e1 represents the short path between vs and vd , and e2 represents the long path. Real ants deposit pheromone on the paths on which they move. Thus, the chemical pheromone trails are modeled as follows. (1) where pi is the probability of an ant choosing the ith path, τi is artificial pheromone value for each of the two links ei , i = 1, 2. Obviously, if τ1 > τ2, the probability of choos- ing e1 is higher, and vice versa. For returning from vd to vs , an ant uses the same path as it chose to reach vd and it changes the artificial pheromone value associated to the used edge. After all the ants have returned to the nest, the pheromone information is updated using Eq. (2) (2) wher p ε (0,1] is evaporation rate, Q is a constant, Lk is length of the path traversed kth ant and na is number ants in the colony. The aim of pheromone update is to increase the pheromone value associated with good or promising paths. Pheromone evaporation is needed to avoid too rapid convergence of the algorithm. Implementing the discrete ACO algorithm for a contin- uous problem requires substantial modifications. The physical problems need to be represented in a graphical from as shown in Fig. 2 and Fig 3. The elemental stiff- ness value is divided in to 'np' different values randomly with in the specified range. Each of these values can be represented as local path between the two levels and each of which leads to global path as shown in Fig. 2b and 3b. As mentioned earlier, ACO algorithm requires finite set of components, i.e. resolution of the local paths, so each stiffness value is divided in 'np' different paths (stiffness) in the given range. ACO algorithm has to find shortest path out of npnv (nv- number of parameters to be identi- fied) available combinations. In real ant colony initially ants take random paths and deposit pheromone. As the iteration proceeds, all the ants in colony take the shortest path and there by increasing the intensity of pheromone trail on the shortest path. The main goal in structural iden- tification is minimizing the objective function, which in turn decides the amount of pheromone deposition. Generally ACO minimizes the length of the Lk in Eq. 2, traversed by kth ant. In structural identification, ACO min- imizes the fitness value, ε Eq. 8, which is analogous to length of the path Lk in Eq. 2 and the amount of pheromone deposited depends on the value of ε. 3. Particle Swarm Optimization (PSO) Particle swarm optimization (PSO) is a population based continuous optimization technique developed by (Eberhart and Kennedy 1995), inspired by social behavior of bird flocking or fish schooling. PSO shares some simi- larities with evolutionary computation techniques such as Genetic Algorithms (GA). The system is initialized with a population of random solutions and searches for optima by updating generations. However, unlike GA, PSO has no evolution operators such as crossover and mutation. In PSO, the potential solutions, called particles, move through the problem space by following the current opti- mum particles. The basic PSO algorithm consists of the velocity and position equation of the kth generation: (3) (4) i - particle number k - iteration number v - velocity of ith particle x - position of the ith particle/ present solution pi - historically best position/solution found by ith particle G - historically best position/solution found by all particles γ1,2 - random number in the interval (0,1) applied to ith particle vs e1, l1 vd e2, l2 Figure 1. The ACO Model 1 2 1, 2.i i p i τ τ τ = = + 1 where(1 ) k knak i i i i k Q L τ ρ τ τ τ∑== − + ∆ ∆ = 1 2 ( 1) ( ) ( ( )) ( ( )) i i i i i i i v k v k p x k G x kγ γ+ = + − + − ( 1) ( ) ( 1) i i i x k x k v k+ = + + 67 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 The frequently used PSO form includes an inertia term and acceleration constants, hence the velocity equation of PSO algorithm is modified as: (5) ϕ - inertia function α1,2 - acceleration constants The inertia function is commonly either taken as con- stant or as a linearly decreasing function from 0.9 to 0.4. The acceleration constants are most commonly set to both equal to 2 as in (Shi and Eberhart 1998). The algorithm starts with initializing the i particles randomly with ini- tial zero velocities. PSO then searches for optima by updating the positions of particle through several genera- tions. At every generation, the location of each particle is updated based on two "best" values defined as follows. The first is the historically best solution (fitness) achieved so far by all particles and stored as gbest. Another "best" value is the historically best value obtained so far by the ith particle in the population and is called pbest. The posi- tion of each particle is updated by a quantity which reflects the difference between gbest and pbest (equation (4) and (5)) and eventually all the particles tend to con- verge to the global best (gbest) position. The superiority of PSO over other comparable heuristic algorithms such as GA could be attributed to the explicit tracking and updat- ing of gbest and pbest over the generations. 4. Genetic Algorithm (GA) Genetic Algorithms are optimization algorithms based on the mechanism of natural selection and survival of the fittest. Over the past few decades GA has been widely developed and applied for structural identification. GA combines the explorative ability of large search domains as well as reasonable guided search to the global optima (Michaelwicz 1994). GA creates an initial random sample within the specified domain of variables, called 'popula- tion'. It then ranks them in the order of fitness and con- ducts crossover operations from among a pool of 'parents' through the Roulette wheel selection. Parents having high- er fitness have a greater probability of being selected for crossovers and their offsprings contribute to the next gen- eration. These offspring have marginally better fitness than the parents and over many generations they attain the global maxima. GA can be programmed in the Binary or Continuous versions. Here the Continuous (decimal num- ber) version is used to avoid the computationally intensive conversion from binary to decimal and vice-versa. It been indicated in a few studies that continuous GA is superior to binary GA in computational performance (see (Michaelwicz 1994 and Haupt 1994) ). It may be noted that unlike PSO, GA does not explicitly keep track of the globally best solution (gbest) and particle best (pbest) solutions. 5. Numerical Examples and Discussion For structural identification problems it is usually assumed that the mass of the structure is known and the identification is limited to structural stiffness and damping k1 knv m1 mnv knv-1 mnv-1 Ants taking different paths Local paths Global paths Figure 2 (a) Multi-DOF physical mode (b) ACO-gra- physical model (a) (b) (a) (b) Figure 3 (a) Physical model of truss (b) ACO-model of the truss (for brevity only a few paths are shown 1 1 2 2 ( 1) ( ) ( ) [ ( ( ))] [ ( ( ))] i i i i i i i v k k v k p x k G x k ϕ α γ α γ + = + − + − 68 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 properties. It is assumed that the structure is excited by known forces and that the responses of the structure in terms of accelerations, are recorded at some given points. The dynamic equation of a structural system can be writ- ten as (6) where M, C and K are the mass matrix, damping matrix and stiffness matrix, respectively, u is the displacement vector and F is the force vector. Proportional damping is adopted as follows (7) where α and β are two damping constants, which can be related to the modal damping ratio. In the examples which follow, experiments are simulated numerically using the known parameters of the structure ie. the forward analysis is carried out by numerically solving the dynamic equa- tion using the parameter values (such as in Tables 1 and 4). The acceleration responses in the time domain are obtained at desired places and they are treated as experi- mentally obtained values. Noise may be added to them to be more realistic. The difference between the estimated acceleration response and measured acceleration response is used to compute the fitness value (objective function) as given by the Eq. (8) given below, which has to be min- imized (see reference Koh et al. 1991). (8) The parameters used in GA, PSO and ACO are given in the Table 2. They were applied to all the numerical examples. To compare GA and PSO they were given the same population size (200) and number of generations (50). These values are taken from Koh and Shankar (2003) which dealt with identification of structural sys- tems similar to this paper. The crossover rate (40%) and mutation rate (5%) for GA, and PSO inertia function value (0.3) and acceleration constant (2) were selected from the best parameters recommended from standard literature on these algorithms (Michaelwicz 1994; Haupt 1994; Shi and Eberhart 1998). Comparable ACO parameters were however more difficult to establish since it is a discrete approach whereas PSO and GA are continuous with their resolution decided by the precision of the smallest deci- mal number - which is by default set to double precision in MATLAB. It is impractical to obtain a comparable pre- cision in ACO by discrete division of the search interval (ie. number of paths). Thus the crucial ACO parameters such as number of ants (400), number of paths (100) and number of iterations (100) were chosen after several trials as a compromise, which would converge in a reasonably comparable time as GA, with mean errors which are acceptable for system identification purposes. Each algo- rithm has been run ten times separately to minimize the objective function, ε, for both impulse and random excita- tion with noise-free and noisy data and the final results shown is the average. 5.1 Example 1: 10-DOF Lumped Mass System In the numerical study, a 10-DOF lumped mass system studied in (Koh et al. 2003) and shown in Fig. 2(a) is con- sidered. The structural parameters are tabulated in the Table 1. Impulse and random excitation is applied at the 5th level. The impulse was given as an initial velocity of 10 m/s to the first mass, the displacements and velocities of all other DOF set to zero. The impulse excitation was simulated by imposing equivalent initial velocity condi- tions obtained from impulse momentum relation using the method followed in (Hanagud 1985). The Gaussian ran- dom force was applied as with a maximum amplitude of 10 N. Accelerations at alternate levels, ie. levels 2, 4, 6, 8, 10 are assumed to be available for the purpose of struc- tural identification. Referring to Eq. 8, here m=5, and n the time steps are 500 in the range from 0 to 2 seconds. Here the objective is to find out the unknown spring stiff- nesses k1 to k10. In all the problems hereafter the search limits for unknown parameters are taken as -50% (lower limit) to +100% (upper limit) of the exact value. In GA and PSO initial population/particles are generated within this specified range. In ACO a matrix of size nv × np is generated within the specified parameter range. ACO has to choose best combination of paths which minimize the objective function. The results for this system are shown in the Fig. 4. GA and PSO have identified the parameters more accurately as shown in Fig. 4 (a) and (b). The accuracy of identified values by PSO is more than GA which can be noticed in the almost constant plateau in Fig. 4 (b) as compared to ( ) ( ) ( ) ( )Mu t Cu t Ku t F t+ + = C M Kα β= + 2 1 1 ( , ) ( , ) Minimize: * m n mea est i j u i j u i j m n ε = = − = ∑ ∑ where ( , )meau i j and ( , )estu i j are, respectively the measured and estimated responses of ith measurement location at jth time step, m is the number of measurement location and n is the number of time steps. The “measured” responses are obtained from numerical simulation. The “estimated” responses are obtained from the mathematical model (Eq. 6 and 7) where the optimization variables are t he now unknown stiffness properties and damping ratio. The values of the variables which minimize Eq. 8 give the required structural properties. To excite higher modes for better identification the input forces are impulse and random excitations (the latte r by means of Gaussian white noise). The dynamic equations are solved using Newmark’s constant acceleration method. Two seconds of acceleration response is computed with constant time step of 0.004s in 500 steps. To investigate the effect of noisy data on identification, the I/O time signals are artificially contaminated by zero -mean Gaussian white noise. The noise level is defined as the ratio of standard deviation of the noise to the root -mean- square value of the uncontaminated time history; here it is taken as 10%. 69 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 GA (Fig 4(a)) for stiffness levels 6-10. From Fig. 5 and 6 it is clear that GA and PSO performs better with presence of noise for both types of excitations (impulse and ran- dom). But ACO fails to identify the parameters with noisy data. Table 3 gives maximum and average errors (aver- aged over 10 runs) in identification of the stiffness param- eters using impulse and random excitation. The maximum errors observed for the noisy case are 15.9% for ACO, 9.12% for GA and 4.17% for PSO (using random excita- tion). The mean errors are 12.34%, 3.47% and 2.88% respectively (using random excitation). The Table shows that using impulse excitation gives lesser errors than the random type. In such as case PSO produces a maximum error of only 3.02% with a mean error of 1.13%. Thus it is clear from the Fig. 5, Fig. 6 and Table 3, that the PSO gives superior results as compared to the other two algo- rithms for both types of excitations and with noisy data from the point of view of maximum and mean errors as well as computational time which is similar for both load cases. 5.2 Example 2: 11- Member Planar Truss In this example an 11-member planar truss is consid- ered for identification of the axial rigidity (EA) of all the 11 (ie. number of variables, nv = 11) members. Configuration and structural properties of the truss are given in Fig. 3(a) and Table 4, respectively. To implement ACO, the physical truss has to be represented as a graph- ical model with axial rigidity (stiffness) of each member discretized into 100 units ie. this would correspond to 100 paths per member. Fig. 3(b) shows schematically this division of each member into several paths. For clarity only 3 paths are shown per member. Stiffness (kN/m) Level 1-5 350 Level 6-10 600 Mass (kg) Level 1-5 500 Level 6-10 300 Damping Critical damping ratio for first 2 modes 5% Table 1. Structural properties of lumped mass system GA PSO ACO Population size 200 No. of particles 200 No. of ants 400 No. of generations 50 No. of generations 50 No. of iterations 100 Cross over rate 40% Inertia function 0.3 Evaporation rate 30% Mutation rate 5% Acceleration constants 2 No. of paths 100 Constant Q 1 Table 2. Parameters used in the algorithms Impulse excitation Random excitation Algorithms with out noi se with 10% noise With out noise with 10% noise Average computational time (sec) Max Mean Max Mean Max Mean Max Mean GA 3 1.77 4.7 1.90 5.4 2.26 9.12 3.47 95 PSO 0.23 0.06 3.02 1.13 2.51 0.58 4.17 2.88 40 ACO 4.55 1.45 15.15 7.68 4.39 2.09 15.91 12.34 140 Table 3. Absolute percentage error in identification of stiffness - lumped mass system Axial rigidity (MN) 300 Cross section area (m 2) 0.0015 Density (kg/m 3) 7800 Critical damping for first 2 modes 5% Table 4. Structural properties of truss 70 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 (a) (b) (c) Figure 4. Identified values of the level stiffness v/s no. of runs with noise-free data for impulse excitation (a) GA (b) PSO (c) ACO (a) (b) (c) Figure 5. Identified values of the level stiffness v/s no. of runs with noise-free data for impulse excitation (a) GA (b) PSO (c) ACO 71 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 The truss is excited with impulse and random input at node 2 in Y-direction and acceleration responses (using the same excitation and times as the previous case) are assumed to be available at nodes 1, 2, 3, 4 and 5 in Y- direction. Acceleration responses are simulated using properties given in Table 4, and 10% noise added to the simulated responses. The truss is modeled using finite ele- ment method. The same set of algorithm parameters (Table 2) are used in this example also for minimizing the objective function ε (Eq. 8). In all the algorithms finite element model is updated till the error between simulated acceleration responses and estimated by the algorithms is minimized. Figure 7 shows the typical percentage error in identifi- cation of axial rigidity of the truss members for impulse excitation with and without 10% noise. From Fig. 7 it can be noticed that the error in identification of all the mem- bers is small in the case of PSO and GA. But ACO appears to oscillate about zero with significant variation giving maximum errors of about 20% - 30%. The maximum and mean errors in identification by all algorithms for both excitations are tabulated in Table 5. It is seen that when noise is added to the responses the impulse excitation gives better identification than random excitation. The maximum and mean errors and computational time of PSO is much better than the others in the presence of noise. The computational time is roughly same for both load cases hence only a typical average value of time is shown to compare between the various algorithms. 5.3 Example 3: Simply Supported Beam In this example a simply supported beam, Fig. 8, with linearly varying stiffness from support to the middle is considered for element wise stiffness identification (Modulus of Elasticity) in the time domain. Cross section of the beam is square with an area of 9x10-4 m2 and den- sity of 7800 kg/m3. The beam is modeled with 2 noded, 11 Euler beam elements with two degrees of freedom per node, translation and rotation. The stiffness variation is 200 GPa at the support to 50 GPa at the center of the beam. Impulse excitation is applied at node 3 in transverse direction and acceleration responses are assumed to be available at nodes 1, 4, 7 and 10 for identification. In identification, modulus of elastic- ity of all eleven elements are considered unknown and damping ratio of 5% is assumed to be known. Here also the finite element model is updated as mentioned in the previous example to minimize the objective function given in Eq. (8). Results are represented in Fig. 9 for impulse excitation only. Again it is noted that the perform- ance of PSO is better than other algorithms. This is seen in the results where the mean error in identification is 5.8%, 3.1% and 15% for GA, PSO and ACO with noisy data, respectively. In all the examples thus presented it is found that ACO cannot identify the parameters with the same degree of accuracy as PSO and GA. So in order to combine the advantages of each of these algorithms, a hybrid approach is next investigated. (a) (b) (c) Figure 6. Identified values of the level stiffness v/s no. of runs with 10% noise data for random excitation (a) GA (b) PSO (c) ACO 72 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 5.4 The Hybrid Approach The results of hybrid approach are tabulated in the Tables 7 to 10. Table 7a shows the identification results with known damping for three cases A, B and C which represent the lumped mass, truss and beam models. The extensive data in Table 7a is summarized in Table 7b by averaging over the three cases. Table 7b data can be stud- ied from the point of view of a) average time of solution : from this point of view it is seen that GA+PSO hybrid is clearly superior with only 39.7s, followed by pure PSO with 66.7s, then ACO+PSO hybrid with 110s and pure GA at 143s. The worst time performer is pure ACO which takes 219s. b) accuracy of solution: we examine the val- ues for mean and maximum error in identification . Here also GA+PSO hybrid gives the smallest mean and maxi- mum errors (0.72% and 2.47%) followed by pure PSO (a) (b) Figure 7. Percentage error in identification of axial rigidities of the members with impulse excivation (a) with out noise (b) with 10% noise Figure 8. Simply supported beam Table 5. Absolute percentage error in identification of axial rigidity - truss GA+PSO ACO+PSO ACO+GA Algorithm parameters GA PSO ACO PSO ACO GA Population size 100 -- -- -- -- 50 No. of generations 10 -- -- -- -- 50 No. of particles -- 50 -- 50 -- -- Iterations -- 50 -- 50 -- -- No. of ants -- -- 200 -- 200 -- Iterations -- -- 50 -- 50 -- Table 6. Algorithm parameters for hybrids 73 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 1 2 3 4 5 6 7 8 9 10 11 0 50 100 150 200 250 300 Element number M od ul u s o f e la s tic ity Actual GA PSO ACO (a) 1 2 3 4 5 6 7 8 9 10 11 0 50 100 150 200 250 300 Element number M od ul u s o f e la s tic ity Actual GA PSO ACO (b) Figure 9. Identified stiffness along the length of the beam for impulse excitation (a) without noise (b) with 10% noise Case Descripti on PSO GA ACO GA+PSO ACO+PSO ACO+GA Case-A, ma x error 3.02 4.7 15.15 0.63 3.0 11.86 Case-A, mean error 1.13 1.71 7.68 0.126 0.75 4.47 Case-A, time in sec 36 90 137 26 77 89 Case-B, ma x e rror .67 1.52 30.3 0.46 7.25 19.71 Case-B, mean e rror .39 .7 12.26 0.25 4.65 7.0 Case-B, time in sec 88 164 230 34 91 104 Case-C, ma x e rror 7.45 12.66 46.06 6.31 10.09 40.13 Case-C, mean e rror 2.7 5.8 12.5 1.78 3.45 11.35 Case-C, time in sec 76 186 291 59 163 192 Table 7a. Percentage error of identified values of various cases with known damping and noise added. (Case-A is the lumped mass; Case-B is the truss and Case-C is the beam) 74 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 (1.4% and 3.71%) and then pure GA (2.73% and 6.29%). The ACO+PSO hybrid has marginally less accuracy than pure GA although speed wise it is better. The worst accu- racy is shown by ACO. The discrete nature of ACO and its lack of resolution compared to GA and PSO are obvious handicaps. Next, the same structural cases are studied, but damp- ing is considered as an additional unknown. Tables 8, 9 and 10 deal with these cases. In each table the values of all unknown parameters are presented in detail, in addition to mean error, maximum error and time taken. The accu- racy of identification of the unknown damping ratio by the algorithms is also an important parameter considered here. In Table. 8 it is seen that the GA+PSO hybrid is the fastest (ie. with least time of 23s) and next is PSO (34s) followed closely by ACO+PSO (78s) and GA (80s) and the worst is pure ACO(145s). The time trend is the same as in Table. 7. Damping parameter has been identified most accurately by GA+PSO (-1.21% error) and pure PSO (-1.05%) followed by ACO+PSO and GA. Pure ACO gives the worst value here(16%). Regarding the overall accuracy (including damping as well as stiffness) it is seen that GA+PSO has identified fairly accurately with a small mean and maximum error of 1.47% and 4.67% followed by ACO+PSO (1.7%, 4.89%) , PSO (1.85%, 7.2%) and GA (2.01% and 5.41%). Thus there are some small devia- tions in the trend of accuracy when compared to Table 7. In Table. 9 it is also seen that GA+PSO is the fastest (60s) followed by PSO (82s) then ACO+PSO (105s) and GA (107s). Accuracy-wise the best performer is GA+PSO hybrid (mean 0.44% and maximum error 1.05%) followed by PSO(2.9%, 5.68%), then GA(3.9%, 6.62%). The accu- racy of ACO+PSO in this case is quite insufficient com- pared to GA(11.6%, 23.77%). As expected pure ACO per- formed worst in time and accuracy factors. In Table.10 the same general trends are observed with respect to time .i.e., GA+PSO is the fastest (104s) fol- lowed by PSO(138s) then ACO+PSO (175s) . The accura- cy of GA+PSO is the best (mean error 2.3%, maximum error 6.39%), then PSO(4.8%, 11.07%), followed by ACO+PSO (7.6%,21.04%) and GA(11.6%, 28.35%). Pure ACO performed worst in both time and accuracy factors. Summary of observations: The general trend shown in Tables 7 to 10 is as follows. From the point of view of speed (minimum computation time) GA+PSO is the best, followed by pure PSO, then ACO+PSO and pure GA. In some cases GA is nearly comparable to ACO+PSO in speed. Pure ACO is the worst performer. From the point of Aver age over case A, B and C PSO GA ACO GA+PSO ACO+PSO ACO+GA Max error 3.71 6.29 30.5 2.47 6.78 23.9 Mean error 1.4 2.73 10.8 0.72 2.95 7.6 Time in sec 66.7 143 219.3 39.7 110.3 128.3 Table 7b. Average vbalues obtained from case A, B and C Exac t (kN/ m) PSO GA ACO GA+PSO ACO+PSO ACO+GA 350 2.81 2.26 -5.65 0.20 0.87 -0.21 350 1.54 1.10 -1.63 1.52 1.2 1.91 350 0.32 0.49 4.70 0.23 0.59 5.18 350 -2.99 -2.28 10.1 -2.81 -2.72 -3.71 350 0.86 -0.41 -3.90 1.23 -0.55 -0.98 600 -0.21 0.86 7.58 0.25 -1.62 3.27 600 -1.46 -5.41 6.42 -0.53 -2.89 -0.86 600 -0.45 1.48 -9.20 -0.81 -0.5 19.22 600 7.21 -0.25 15.90 4.69 -0.57 14.71 600 -1.41 3.47 19.7 -2.78 4.87 -10.11 Da mping 0.05 -1.05 4.05 16 -1.21 -2.46 5.4 Abs. ma x. error 7.21 5.41 19.7 4.69 4.89 19.22 Abs. mean error 1.85 2.01 9.14 1.47 1.7 5.96 Co mputational time in seconds 34 80 145 23 78 90 Table 8. Percentage error in identified value of 10-DOF lumped mass system with unknown damping and noise 75 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 view of accuracy, again GA+PSO is the best performer followed by pure PSO. Then follows GA and ACO+PSO - their relative superiority in accuracy varies from case to case. Even in these circumstances pure GA would still be preferred as it is simpler to program than the hybrid. The ACO+GA hybrid and pure ACO was not found promising in speed or accuracy. The observations from this compre- hensive numerical study would be useful in future work, such as damage detection of structural members using these algorithms. 6. Conclusions The paper studies the application of behaviorally inspired algorithms and their hybrids for structural para- metric identification in the time domain. The stiffness and Exac t (MN) PSO GA ACO GA+PSO ACO+PSO ACO+GA 300 -1.61 0.15 27.27 -0.4 17.27 18.67 300 5.68 -5.59 45.11 -1.05 -15.28 -24.25 300 3.43 4.92 -13.03 0.64 -17.75 -9.73 300 0.09 3.65 -15.15 -0.44 -10.30 20.25 300 2.73 -4.64 -1.52 0.4 -8.73 -16.38 300 -2.7 6.62 -31.21 0.37 3.12 1.14 300 5.37 -5.31 -11.52 -0.5 -2.27 5.03 300 -5.07 -6.2 3.7 -0.32 20.35 -17.72 300 -5.40 2.11 39.0 0.62 23.77 -6.41 300 1.56 -1.99 -24.1 0.42 -16.9 17.35 Da mping 0.05 0.87 5.61 25.67 -0.12 3.54 7.35 Abs. ma x. error 5.68 6.62 45.11 1.05 23.77 24.25 Abs. mean error 2.9 3.9 19.7 0.44 11.6 12.0 Co mputational time in seconds 82 107 166 60 105 137 Table 9. Percentage error in identified value of 11-member planar truss with unknown damping and noise Exac t (GP a) PSO GA ACO GA+PSO ACO+PSO ACO+GA 200.00 -3.33 11.14 -20.15 0.54 0.32 10.97 170.00 -3.58 -2.22 -3.74 -2.96 -3.45 -26.92 140.00 11.07 -5.21 -28.44 -0.43 0.32 -19.7 110.00 4.67 -3.05 -26.45 -1.87 -1.43 -33.61 80.00 6.30 -11.29 25.0 2.52 4.89 1.14 50.00 6.77 7.94 14.55 1.36 9.24 23.72 80.00 -6.25 6.71 25.76 -6.39 -9.98 -13.64 110.00 -5.73 18.04 24.44 -0.81 -13.99 -30.03 140.00 6.39 -17.03 -32.21 5.09 -5.84 -5.63 170.00 -1.18 -28.35 -38.56 -1.13 -21.04 -17.65 200.00 -2.23 27.03 17.28 4.46 19.66 35.70 Da mping 0.05 0.84 0.91 3.30 0.47 1.45 20.00 Abs. ma x. error 11.07 28.35 38.56 6.39 21.04 35.70 Abs. mean error 4.80 11.60 21.67 2.30 7.60 20.0 Co mputational time in seconds 138 279 343 104 175 225 Table 10. Prcentage error in identified value of simply supported beam with unknown damping and noise 76 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 damping parameters are predicted from the time domain acceleration responses. Impulse and random excitations cases are studied. Particle Swarm Optimization (continu- ous), Genetic Algorithm (continuous) and classical Ant Colony Optimization (discrete) are used here. Three dif- ferent hybridizations of GA, PSO and ACO have been investigated using three numerical models i.e., a lumped mass model, a truss and a non-uniform beam. Comparing the performance between pure GA and PSO it is found that the latter consistently outperforms the former in com- putational time and mean error, especially in the presence of noise. The computational implementation of PSO is also simpler than GA. Unlike GA, PSO keeps track of the global best and particle best solution from iteration to iter- ation which explains its superiority over GA and fast con- vergence. Regarding the performance of hybrid algo- rithms, the GA+PSO has shown its superiority over all the other algorithms in both speed and accuracy. The next best performer is pure PSO followed by pure GA. The per- formance of pure GA is however comparable to ACO+PSO hybrid in a few cases. However pure GA would be preferred as it is simpler to program than the hybrid. Pure ACO performed worst in all cases as expect- ed because of its discrete nature. References Abbospur, K.C., Schulin, R. and van Ganuethen, M., 2004, "Estimating Unsaturated Hydraulic Parameters using Ant Colony Optimization," Advances in water resources, Vol. 24, pp. 827-841. Binghui, Yu., Xiaohui Yuan and Jinwen Wang, 2007, "Short-Term Hydro-Thermal Scheduling using Particle Swarm Optimization Method," Energy Conversion and Management, Vol. 48, pp. 1902- 1908. Bao Zhang, Hong-Fei Teng and Yan-Jun Shi, 2008, "Layout Optimization of Satellite Module using Soft Computing Techniques," Applied Soft Computing, Vol. 8(1), pp. 507-521. Bullnheimer, B., Hartl, R.F. and Ch. Strauss, 1999, "An Improved Ant System Algorithm for the Vehicle Routing Problem," Annals of Operations Research, Vol. 89, pp. 319-328. Christian Blum, 2005, "Ant Colony Optimization: Introduction and Recent Trends," Physics of life reviews, Vol. 2, pp. 353-373. Charles V Camp and Barron Bichon, J., 2004, "Design of Space Trusses Using Ant Colony Optimization," Journal of structural engineering, ASCE, Vol. 130(5), pp. 741-751. Charles Camp, V., Barron Bichon, J. and Scott Stovall, P., "Design of Steel Frame Using Ant Colony Optimization," Journal of Structural Engineering, ASCE, Vol.131(3), pp. 369-379. Chakraborthy. S. and Mukhopadhyay, M., 2002, "Determination of Physical Parameters of Stiffened Plates using Genetic Algorithm," Journal of Computing in Civil Engineering, Vol. 16(3), pp. 206- 221. Dorigo M., 1992, "Optimization, Learning and Natural Algorithms," Doctoral Dissertation, Politecnico di Milano, Italy. Dorigo, M.; L. M. Gambardella "Ant Colony System: A cooperative learning approach to the Travelling Salesman Problem", IEEE Transactions on Evolutionary Computation, vol. 1(1), 1997, pp. 53- 66. Dorigo, M., Maniezzo, V. and Colorni, A., 1994, "Ant System: Optimization by a Colony of Cooperating Agents," IEEE Transactions on Systems, Man and Cybernetics, Vol. 26(1), pp. 29-41. Eberhant, R.C. and Kennedy, J., 1995, "A New Optimizer using Particle Swarm Theory," Proceedings Of the 6th International Symposium on Micro Machine and Human Science, Nagaya, Japan, pp. 39-43. Friswell, M.I., Penny, J.E.T. and Garvey, S.D., 1998, "A Combined Genetic and Eigensensitivity Algorithm for the Location of Damage in Structures," Computers and Structures, Vol. 69(5), pp. 547-556. Haupt, R. L., 1999, "Practical Genetic Algorithms," John Wiley and Sons, New York. Hitoshi Furuta., Masahiro Yasui. and Saeri Fukuhara., 2005, "Structural Health Monitoring using Evolutionary Computing," 6th World Congress of Structural and Multidisciplinary Optimisation, Brazil. Hami, Y., Amodeo, L., Yalowi, F. and Chen, H., 2007, "Ant Colony Optimization for Solving Industrial Layout Problem," European Journal of Operation Research (Article in press). Hanagud, V., Meyyappa, M. and Craig, J.I., 1985, " Method of Multiple Scales and Identification of Non- linear Structural Dynamic Systems," AIAA journal, Vol. 23(5), pp. 802-807. Qie, He., Ling Wang, and Bo Liu, 2007, "Parameter Estimation for Chaotic Systems by Particle Swarm Optimization," Chaos, Solitons and Fractals, Vol. 34, pp. 654-661. Hu, Y. and Zhou Z.Y., 2004, "The Particle Swarm Optimization Algorithm and Its Application in Design Optimisation of a Mini-UAV," Journal of Flight Dynamics, Vol. 22 (2), pp. 61-64. Jaco, F., Schutte Byung-Il Koh., Jeffrey, A., Reinbolt., Raphael, T., Haftka, Alan, D., George, and Benjamin Fregly, F., 2005, "Evaluation of a Particle Swarm Algorithm For Biomechanical Optimization," Journal of biomedical engineering, Vol. 127, pp. 465-474. Jesiel, C,. Scott, C. and Christophe, B., 1999, "Application of Genetic Algorithms for the Identification of Elastic Constants of Composite Materials from Dynamic Tests," International journal for numerical methods in engineering, Vol. 45, pp. 891-900. Gaetan Kerschena, Keith Worden, Alexander Vakakis, F. and Jean-Claude Golinval., 2006, "Past, Present and Future of Nonlinear System Identification in Structural Dynamics," Mechanical Systems and Signal Processing, Vol. 20, pp. 505-592. 77 The Journal of Engineering Research Vol. 6, No. 2 (2009) 64-77 Kishore Kumar, R., Sandesh, S. and Shankar, K., 2007, "Parametric Identification of Non-Linear Dynamic Systems using Combined Levenberg-Marquardt and Genetic Algorithm," International Journal of Structural Stability and Dynamics, Vol.7(4). Koh, C.G., Chen, Y.F. and Liaw, C.Y., 2003, "A Hybrid Computational Strategy for Identification of Structural Parameters," Computers and structures, Vol. 81, pp. 107-117. Koh, C.G., See, L.M. and Balendra, T., 1991, "Estimation of Structural Parameters in Time Domain: A Substructural Approach," Earthquake Engineering and Structural Dynamics, Vol. 20, pp. 787-801. Koh, C,G. and Shankar, K., 2003, "Substructural Identification Method without Interface Measurement," Journal of engineering mechanics," Vol. 129(7), pp. 769-776. Michalwicz, Z., 1994, "Genetic Algorithms + Data struc- tures = Evolutionary Programs" AI Series," Springer Verlag, New York, 1994. Mouser, C.R. and Dunn, S.A., 2005, "Comparing Genetic Algorithm and Particle Swarm Optimization for Inverse Problems," ANZIAM Journal, Vol. 46(e), pp. C89-C101. Paul Corry and Erhan Kozan., 2004, "Ant Colony Optimization for Machine Layout Problem," Computational Optimization and Application, Vol. 28, pp. 287-301. Peng-Yeng Yin., 2006, "Particle Swarm Optimization for Point Pattern Matching," Journal of Visual Communication Image Representation, Vol. 17, pp. 143-162. Perry, M.J., Koh, C.G. and Choo, Y.S., 2004, "Modified Genetic Algorithm for Structural Identification," Computers and Structures, Vol. 84, pp. 529-540. Rajamani, D. and Adil, G.K., 1996, "Machine Loading in Flexible Manufacturing Systems Considering Routing Flexibility," Intl J Adv Manuf Technology, Vol. 11(5), pp. 372-380. Serra, M. and Venini, P., "On Some applications of Ant Colony Optimization Metaheuristic to Plane Truss Optimization," Struct Multidisc Optim , Vol. 32, pp. 499-506. Shi, Y. and Eberhart, R., 1998, "Parameter Selection in Particle Swarm Optimization," Proceeding of the 7th Annual Conference on Evolutionary Programming, pp. 591-601.