1 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsGenetic Algorithms (cont.)Particle Swarm OptimizationTabu SearchOptimization Algorithm SelectionLecture 12Olivier de WeckMultidisciplinary System Design Optimization2 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsToday’s Topics• Genetic Algorithms (part 2)• Particle Swarm Optimization• Tabu Search• Selection of Optimization Algorithms3 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsGenetic Algorithms (Part 2)4 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsGA ConvergenceTypical Resultsgenerationglobaloptimum(unknown)Converged toofast (mutation ratetoo small?)Average performance of individuals in a population is expected to increase, as good individualsare preserved and bred and less fit individuals die out.AverageFitness5 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsGAs versus traditional methodsDiffer from traditional search/optimization methods:• GAs search a population of points in parallel, not only a single point• GAs use probabilistic transition rules, not deterministic ones• GAs work on an encoding of the design variable set rather than the variable set itself• GAs do not require derivative information or other auxiliary knowledge - only the objective function and corresponding fitness levels influence search6 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsParallel GA’sGA’s are very ameniable to parallelization.Motivations: - faster computation (parallel CPU’s)- attack larger problems- introduce structure and geographic locationThere are three classes of parallel GA’s:• Global GA’s• Migration GA’s• Diffusion GA’sMain differences lie in :- population structure- method of selecting individuals for reproduction7 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsGlobal GAGA FarmerSelectionAssign FitnessWorker 1CrossoverMutationFunction evaluationWorker 2CrossoverMutationFunction evaluationWorker NCrossoverMutationFunction evaluation...• GA Farmer node initializes and holds entire population• Interesting when objective function evaluation expensive• Typically implemented as a master-slave algorithm• Balance serial-parallel tasks to minimize bottlenecks• Issue of synchronous/asynchronous operation“panmixia”8 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsMigration GADoes NOT operateglobally on a singlepopulationEach node representsa subgroup relativelyisolated from each other More closely mimicsbiological metaphor“breeding groups”= demesGA2GA3GA1GA5GA4“polytypic”-- Each node (Gai)WHILE not finishedSEQ… Selection… Reproduction… EvaluationPAR… send emigrants… receive immigrantsFirst introduced by Grossoin 19859 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsDiffusion GA’sI1,1I2,1I3,1I4,1I1,2I2,2I3,2I4,2I1,3I2,3I3,3I4,3I1,4I2,4I3,4I4,4Toroidal-Mesh parallel processing network-- Each Node (Ii,j)WHILE not finishedSEQ… EvaluatePAR… send self to neighbors… receive neighbors… select mate… reproduce• Population is a single continuous structure, but• Each individual is assigned a geographic location• Breeding only allowed within a small local neighborhood• Example: I(2,2) only breeds with I(1,2), I(2,1),I(2,3),I(3,2)Neighborhood, cellularor fine-grained GA10 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsGood News about GA’s• GA work well on mixed discrete/continuous problems • GA’s require little information about problem• No gradients required• Simple to understand and set up and implement• Can operate on various representations• GA’s are very robust• GA’s are stochastic, that is, they exploit randomness• GA’s can be easily parallelized11 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsBad News about GA’s• GA implementation is still an art and requires some experience• Convergence behavior very dependent on some tuning parameters: mutation rate, crossover, population size• Designing fitness function can be tricky• Cumbersome to take into account constraints• GA’s can be computationally expensive• No clear termination criteria• No knowledge of true global optimum12 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsParticle Swarm OptimizationLecture Notes prepared by and courtesyof Rania Hassan. Used with permission.Introduced in 1995: Kennedy, J. and Eberhart, R., “Particle Swarm Optimization,” Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia 1995, pp. 1942-1945.13 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsParticle Swarm OptimizationA pseudo-optimization method (heuristic) inspired by the collective intelligence of swarms of biological populations.Flocks of BirdsColonies of Insects14 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and AstronauticsSwarming in System DesignA study of great white pelicans has found that birds flying in formation use up to a fifth less energy than those flying solo (Weimerskirch et al.).Weimerskirch, H. et al. "Energy saving in flight formation." Nature 413, (18 October 2001): 697 - 698.15 © Massachusetts Institute of Technology - Prof. de Weck and Prof. WillcoxEngineering Systems Division and Dept. of Aeronautics and