Application of Genetic Algorithms and Neural Networks to the .ppt

1、Application of Genetic Algorithms and Neural Networks to the Solution of Inverse Heat Conduction Problems,A TutorialKeith A. Woodbury Mechanical Engineering Department,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,2,Paper/Presentation/Programs,Not on the CD Available from www.me.ua.edu/inverse,May 28

2、, 2002,4th Int. Conf. Inv. Probs. Eng.,3,Overview,Genetic Algorithms What are they? How do they work? Application to simple parameter estimation Application to Boundary Inverse Heat Conduction Problem,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,4,Overview,Neural Networks What are they? How do they

3、work? Application to simple parameter estimation Discussion of boundary inverse heat conduction problem,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,5,MATLAB,Integrated environment for computation and visualization of results Simple programming language Optimized algorithms Add-in toolbox for Geneti

4、c Algorithms,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,6,Genetic Algorithms,What are they? GAs perform a random search of a defined N-dimensional solution space GAs mimic processes in nature that led to evolution of higher organisms Natural selection (“survival of the fittest”) Reproduction Cross

5、over Mutation GAs do not require any gradient information and therefore may be suitable for nonlinear problems,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,7,Genetic Algorithms,How do they work? A population of genes is evaluated using a specified fitness measure The best members of the population a

6、re selected for reproduction to form the next generation. The new population is related to the old one in a particular way Random mutations occur to introduce new characteristics into the new generation,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,8,Genetic Algorithms,Rely heavily on random processe

7、s A random number generator will be called thousands of times during a simulation Searches are inherently computationally intensive Usually will find the global max/min within the specified search domain,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,9,Genetic Algorithms,Basic scheme (1)Initialize pop

8、ulation (2)evaluate fitness of each member (3)reproduce with fittest members (4)introduce random mutations in new generation Continue (2)-(3)-(4) until prespecified number of generations are complete,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,10,Role of Forward Solver,Provide evaluations of the ca

9、ndidates in the population Similar to the role in conventional inverse problem,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,11,Elitism,Keep the best members of a generation to ensure that their characteristics continue to influence subsequent generations,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,

10、12,Encoding,Population stored as coded “genes” Binary Encoding Represents data as strings of binary numbers Useful for certain GA operations (e.g., crossover) Real number encoding Represent data as arrays of real numbers Useful for engineering problems,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,13

11、,Binary Encoding Crossover Reproduction,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,14,Binary Encoding,Mutation Generate a random number for each “chromosome” (bit); If the random number is greater than a “mutation threshold” selected before the simulation, then flip the bit,May 28, 2002,4th Int. C

12、onf. Inv. Probs. Eng.,15,Real Number Encoding,Genes stored as arrays of real numbers Parents selected by sorting population best to worst and taking the top “Nbest” for random reproduction,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,16,Real Number Encoding,Reproduction Weighted average of the paren

13、t arrays: Ci = wAi + (1-w)*Bi where w is a random number 0 w 1 If sequence of arrays are relevant, use a crosover-like scheme on the children,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,17,Real Number Encoding,Mutation If mutation threshold is passed, replace the entire array with a randomly genera

14、ted one Introduces large changes into population,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,18,Real Number Encoding,Creep If a “creep threshold” is passed, scale the member of the population with Ci = ( 1 + w )*Ci where w is a random number in the range 0 w wmax. Both the creep threshold and wmax

15、must be specified before the simulation begins Introduces small scale changes into population,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,19,Simple GA Example,Given two or more points that define a line, determine the “best” value of the intercept b and the slope m Use a least squares criterion to

16、measure fitness:,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,20,Make up some data, b = 1; m = 2; xvals = 1 2 3 4 5; yvals = b*ones(1,5) + m * xvals yvals =3 5 7 9 11,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,21,Parameters,Npop number of members in population (low, high) real number pair specifyi

17、ng the domain of the search space Nbest number of the best members to use for reproduction at each new generation,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,22,Parameters,Ngen total number of generations to produce Mut_chance mutation threshold Creep_chance creep threshold Creep_amount parameter w

18、max,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,23,Parameters,Npop = 100 (low, high) = (-5, 5) Nbest = 10 Ngen = 100,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,24,SimpleGA Results (exact data),May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,25,SimpleGA Convergence History,May 28, 2002,4th Int. Conf.

19、 Inv. Probs. Eng.,26,SimpleGA Results (1% noise),May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,27,SimpleGA Results (10% noise),May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,28,SimpleGA 10% noise,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,29,Heat function estimation,Each member of population is an ar

20、ray of Nunknown values representing the piecewise constant heat flux components Discrete Duhamels Summation used to compute the response of the 1-D domain,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,30,Make up some data,Use Duhamels summation with t = 0.001 Assume classic triangular heat flux,May 2

21、8, 2002,4th Int. Conf. Inv. Probs. Eng.,31,“Data”,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,32,Two data sets,“Easy” Problem large t Choose every third point from the generated set Harder Problem small t Use all the data from the generated set,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,33,GA pro

22、gram modifications,Let Ngen, mut_chance, creep_chance, and creep_amount be vectors Facilitates dynamic strategy Example: Ngen = 100 200 mut_chance = 0.7 0.5 means let mut_chance = 0.7 for 100 generations and then let mut_chance = 0.5 until 200 generations,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.

23、,34,GA Program Modifications,After completion of each pass of the Ngen array, redefine (low,high) based on (min,max) of the best member of the population Nelite = 5,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,35,“Easy” Problem,t = 0.18 First try, let Npop = 100 (low, high) = (-1, 1) Nbest = 10 Ngen

24、 = 100,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,36,“Easy” Problem,Npop = 100, Nbest = 10, Ngen = 100,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,37,“Easy” Problem,Npop = 100, Nbest = 10, Ngen = 100,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,38,“Easy” Problem,Npop = 100, Nbest = 10, Ngen = 100

25、,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,39,“Easy” Problem another try,Use variable parameter strategy Nbest = 20 Ngen = 200 350 500 650 750 mut_chance = 0.9 0.7 0.5 0.3 0.1 creep_chance = 0.9 0.9 0.9 0.9 0.9 creep_amount =0.7 0.5 0.3 0.1 0.05 ,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,40,“E

26、asy” Problem another try,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,41,“Easy” Problem another try,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,42,“Easy” Problem another try,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,43,“Hard” Problem,has small time step data t = 0.06 Use same parameters as last

27、Nbest = 20 Ngen = 200 350 500 650 750 mut_chance = 0.9 0.7 0.5 0.3 0.1 creep_chance = 0.9 0.9 0.9 0.9 0.9 creep_amount =0.7 0.5 0.3 0.1 0.05 ,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,44,“Hard” Problem,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,45,“Hard” Problem,May 28, 2002,4th Int. Conf. Inv.

28、 Probs. Eng.,46,“Hard” Problem,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,47,“Hard” Problem,Whats wrong? Ill-posedness of the problem is apparent as t becomes small. Solution Add a Tikhonov regularizing term to the objective function,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,48,“Hard” Problem,W

29、ith 1 = 1.e-3,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,49,“Hard” Problem,With 1 = 1.e-3,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,50,“Hard” Problem,With 1 = 1.e-3,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,51,Genetic Algorithms- Conclusions,GAs are a random search procedure Domain of soluti

30、on must be known GAs are computationally intensive GAs can be applied to ill-posed problems but cannot by-pass the ill-posedness of the problem Selection of solution parameters for GAs is important for successful simulation,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,52,Neural Networks,What are the

31、y? Collection of neurons interconnected with weights Intended to mimic the massively parallel operations of the human brain Act as interpolative functions for given set of facts,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,53,Neural Networks,How do they work? The network is trained with a set of kno

32、wn facts that cover the solution space During the training the weights in the network are adjusted until the correct answer is given for all the facts in the training set After training, the weights are fixed and the network answers questions not in the training data. These “answers” are consistent

33、with the training data,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,54,Neural Networks,The neural network “learns” the relationship between the inputs and outputs by adjustment of the weights in the network When confronted with facts not in the training set, the weights and activation functions act

34、to compute a result consistent with the training data,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,55,Neural Networks,Concurrent NNs accept all inputs at once Recurrent or dynamic NNs accept input sequentially and may have one or more outputs fed back to inputWe consider only concurrent NNs,May 28,

35、2002,4th Int. Conf. Inv. Probs. Eng.,56,Role of Forward Solver,Provide large number of (input,output) data sets for training,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,57,Neural Networks,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,58,Neurons,summation,Activation function,May 28, 2002,4th Int. Con

36、f. Inv. Probs. Eng.,59,MATLAB Toolbox,Facilitates easy construction, training and use of NNs Concurrent and recurrent networks Linear, tansig, and logsig activation functions Variety of training algorithms Backpropagation Descent methods (CG, Steepest Descent),May 28, 2002,4th Int. Conf. Inv. Probs.

37、 Eng.,60,Simple Parameter Estimation,Given a number of points on a line, determine the slope (m) and intercept (b) of the line Fix number of points at 6 Restrict domain 0 x 1 Restrict range of b and m to 0, 1 ,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,61,Simple Example,First approach: let the six

38、 values of x be fixed at 0, 0.2, 0.4, 0.6, 0.8, and 1.0 Inputs to the network will be the six values of y corresponding to these Outputs of the network will be the slope m and intercept b,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,62,Simple Example,Training data 20 columns of 6 rows of y data,Colu

39、mns 1 through 8 0 0.2500 0.5000 0.7500 1.0000 1.0000 0.7500 0.50000.2000 0.4000 0.6000 0.8000 1.0000 1.0000 0.8000 0.60000.4000 0.5500 0.7000 0.8500 1.0000 1.0000 0.8500 0.70000.6000 0.7000 0.8000 0.9000 1.0000 1.0000 0.9000 0.80000.8000 0.8500 0.9000 0.9500 1.0000 1.0000 0.9500 0.90001.0000 1.0000

40、1.0000 1.0000 1.0000 1.0000 1.0000 1.0000,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,63,Simple Example,Network1 6 inputs linear activation function 12 neurons in hidden layer Use tansig activation function 2 outputs linear activation function trained until SSE 10-8,May 28, 2002,4th Int. Conf. Inv.

41、 Probs. Eng.,64,Test Input Data,input_data1 =0.9000 0.1000 0.9000 0.3000 0.5000 0.3000 0.7000 0.70001.0400 0.2800 0.9200 0.4000 0.5600 0.4400 0.7600 0.88001.1800 0.4600 0.9400 0.5000 0.6200 0.5800 0.8200 1.06001.3200 0.6400 0.9600 0.6000 0.6800 0.7200 0.8800 1.24001.4600 0.8200 0.9800 0.7000 0.7400

42、0.8600 0.9400 1.42001.6000 1.0000 1.0000 0.8000 0.8000 1.0000 1.0000 1.6000output_data1 =0.9000 0.1000 0.9000 0.3000 0.5000 0.3000 0.7000 0.70000.7000 0.9000 0.1000 0.5000 0.3000 0.7000 0.3000 0.9000,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,65,Simple Example,Network1:Test data1 resultsb m bNN mN

43、N0.9000 0.7000 0.8973 0.72360.1000 0.9000 0.0997 0.90060.9000 0.1000 0.9002 0.09980.3000 0.5000 0.3296 0.53560.5000 0.3000 0.5503 0.32310.3000 0.7000 0.3001 0.69990.7000 0.3000 0.7000 0.30010.7000 0.9000 0.7269 0.8882,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,66,Network2,Increase number of neuron

44、s in hidden layer to 24 Train until SSE 10-15 Test data1 results: b m bNN mNN0.9000 0.7000 0.8978 0.71020.1000 0.9000 0.0915 0.93140.9000 0.1000 0.9017 0.09200.3000 0.5000 0.2948 0.57990.5000 0.3000 0.4929 0.35750.3000 0.7000 0.3017 0.69340.7000 0.3000 0.6993 0.30320.7000 0.9000 0.7008 0.8976,May 28

45、, 2002,4th Int. Conf. Inv. Probs. Eng.,67,Network3,Add a second hidden layer with 24 neurons Train until SSE 10-18 Test data1 results: b m bNN mNN0.9000 0.7000 0.8882 0.70180.1000 0.9000 0.1171 0.90670.9000 0.1000 0.8918 0.10020.3000 0.5000 0.3080 0.50840.5000 0.3000 0.5033 0.31830.3000 0.7000 0.293

46、7 0.69990.7000 0.3000 0.7039 0.29960.7000 0.9000 0.7026 0.9180,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,68,Network Design,First add more neurons in each layer Add more hidden layers if necessary,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,69,Simple Example Second Approach,Add the 6 values of x

47、to the input (total of 12 inputs) Network4 24 neurons in hidden layer Trained until SSE 10-12,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,70,Network4,Test data1 resultsb m bNN mNN0.9000 0.7000 0.8972 0.71710.1000 0.9000 0.1016 0.90810.9000 0.1000 0.9002 0.09790.3000 0.5000 0.2940 0.50590.5000 0.300

48、0 0.5115 0.30130.3000 0.7000 0.2996 0.69800.7000 0.3000 0.7000 0.30090.7000 0.9000 0.7108 0.8803,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,71,Network4,Try with x values not in the training data (x = 0.1, .3, .45, .55, .7, .9 )b m bNN mNN0.9000 0.7000 0.9148 0.36220.1000 0.9000 0.1676 0.49010.9000 0.1000 0.9169 -0.14880.3000 0.5000 0.3834 0.16320.5000 0.3000 0.5851 0.01090.3000 0.7000 0.3705 0.33380.7000 0.3000 0.7426 0.01390.7000 0.9000 0.7284 0.5163,May 28, 2002,4th Int. Conf. Inv. Probs. Eng.,