slides02

Practical Optimization Algorithm Design Lesson 2: The Structure of OptimizationDr.-Ing. Thomas WeiseNature Inspired Computation and Applications Laboratory (NICAL)School of Computer Science and TechnologyUniversity of Science and Technology of China (USTC)Contents•Example Algorithm •Problem Space•Objective Function•What does “good” mean? •Search Space•Genotype-Phenotype Mapping •Further Definitions•Overall Structure•Solving Optimization Problems •SummaryWhat is optimization?• Hm, can you give some examples for optimization problems?a)Bin Packing: bins of size , objects of size … .Question: Can we pack them into the bins?b =5bin 0bin 1bin 2bin 3bin 4to a 110•Bin Packing: bins of size ,objects of size … .•Optimization: Find assignment withleast overflow minimize• 0,Problem Space•Problem SpaceThe problem space (phenome) of an optimization problem is the set containing all elements which could be its solution. •Candidate SolutionA candidate solution (phenotype) is an element of theproblem space of a certain optimization problemProblem Space•What could possible problem spaces be?a)Bin Packingb)Circuit Layoutc)Job Shop Schedulingd)Routinge)Find the roots off)Find mathematical formulag)Stock Predictionh)Truss Optimizationi)Medical Classificationj)Airplane Wing DesignProblem Space•Practical constraints: Why can a (default) implementation of an optimization algorithm on a 80x86 processor not discoverelements such as 1 10 even if ?Objective Function•Objective FunctionAn objective function : is a (mathematical) functionwhich is subject to optimization.•Usually subject to minimization•Not necessary a function like but may be arbitrarily complex…Objective Function•Example: Stone’s ThrowWhich is best velocity with which I should throw a stone (in an 15° angle) so that it lands exactly 100 away (assuminguniform gravity and the absence of drag and wind)?Objective Function• Example: Stone’s Throw• Problem Space:• Objective function:Minimize | 100 |sin 20.051⁄Objective Function•Example: Stone’s Throw•Problem Space:•Objective function:Minimize | 100 |Easily solved, since formula and minimalvalue of is known and straightforwardObjective Function•Example: Traveling Salesman ProblemA salesman wants to visit cities in the shortest possible time underthe assumption that no city is visited twice and that he will againarrive at the origin by the end of the tour.The goal of the Traveling Salesman Problem (TSP) is to find a cyclic path of minimum total weight which visits all vertices of a weightedgraph.Objective Function••Beijing, Chengdu, Guangzhou, Shanghai•Objective function: Hefei, 0 , 13 ,HefeiObjective FunctionHefei Beijing Guangzhou Chengdu Shanghai Hefei 8311 HefeiBeijing Guangzhou Shanghai Chengdu Hefei 7886 Hefei Beijing Shanghai Chengdu Guangzhou Hefei 7381 Hefei Beijing Shanghai Guangzhou Chengdu Hefei Hefei Chengdu Beijing Guangzhou Shanghai Hefei 8787 HefeiChengdu Beijing Shanghai Guangzhou Hefei 7857 Hefei Chengdu Guangzhou Beijing Shanghai Hefei 8602 Hefei Chengdu Shanghai Beijing Guangzhou Hefei 8743 Hefei Guangzhou Beijing Chengdu Shanghai Hefei Hefei Guangzhou Chengdu Beijing Shanghai Hefei 7566Objective Function• Example: Traveling Salesman Problem• The size of the problem space is1 !f(x)=xf(x)=x 2f(x)=x 4f(x)=x 810f(x)=x 10xms per day picoseconds since big bang xxxObjective Function•What could possible objective functions be?a)Bin Packingb)Circuit Layoutc)Job Shop Schedulingd)Routinge)Find the roots off)Find mathematical formulag)Stock Predictionh)Truss Optimizationi)Medical Classificationj)Airplane Wing DesignObjective Function •Example: Antenna Design •Example: Analog Electric Circuit Design •Example: Interactive OptimizationWhat does “good” mean?•Single objective function1What does “good” mean?•Extrema: Minima and Maxima of : andis local extremum of 0• 0 0 is local minimum • 0 0 is local maximum •sign change of ’from –to is local minimum •sign change of ’from to is local maximumWhat does “good” mean?•Differentiation only possible for differentiable objective functions •Differentiation a bit more complicated for and large … •Many cases, have to live without the formulas from the previous slideWhat does “good” mean?•Global MaximumA global maximum of one (objective) function : is aninput element with .•Global MinimumA global minimum of one (objective) function : is aninput element with .•Global OptimumDepending on whether the objective function is subject tominimization or maximization, a global optimum is either a globalminimum or a global maximum.What does “good” mean?•There may be multiple global and local optima•Global Optimal SetThe optimal set of an optimization problem is the set thatcontains all its globally optimal solutions-1-0.50.5120406080100What does “good” mean?•Global Optimal SetThe optimal set of an optimization problem is the set that contains all its globally optimal solutions•Optimization ResultThe set X contains output elements x X of an optimizationprocess.What does “good” mean?•Multi-Objective Optimization Problem (MOP)In a multi-objective optimization problem (MOP), a set f:consisting of objective functions : , each representing one criterion, is to be optimized over a problem space .relationdependent independent conflict harmonyWhat does “good” mean?•Harmonizing Objective Functions~ ,•Conflicting Objective Functions,•Independent Objective FunctionsProblem can be decomposed into sub-problems which can beoptimized separately and solutions of sub-problems can becomposed to solution of overall problemWhat does “good” mean? •Example: Factory•Example: Artificial Ant•Example: Independent Objectivesrelationdependent independent conflict harmonyWhat does “good” mean? •What does good mean?a)Bin Packingb)Circuit Layoutc)Job Shop Schedulingd)Routinge)Find the roots off)Find mathematical formulag)Stock Predictionh)Truss Optimizationi)Medical Classificationj)Airplane Wing DesignWhat does “good” mean?•Constraint optimizationIn an optimization problem, 0 inequality constraints and 0 equality constraints may be imposed additionally to the objectivefunctions. Then, a candidate solution is feasible, if and only if itfulfils all constraints:feasible 0 1..0 1..What does “good” mean? •Can/should we formulate some constraints?a)Bin Packingb)Circuit Layoutc)Job Shop Schedulingd)Routinge)Find the roots off)Find mathematical formulag)Stock Predictionh)Truss Optimizationi)Medical Classificationj)Airplane Wing DesignSearch Space•Search SpaceThe search space (genome) of an optimization problem is the set of all elements which can be processed by the search operations. •GenotypesThe elements of the search space of a given optimizationproblem are called the genotypes.Search Space•GeneThe distinguishable units of information in genotypes whichencode properties of the candidate solutions are called genes.•AlleleAn allele is a value of specific gene.•LocusThe locus is the position where a specific gene can be found in agenotype.Search Space•Search OperationA search operation searchOp takes elements .. from thesearch space as parameter and returns another element from thesearch space.•Operations with 0 usually assume causality•Many operations with 1 assume Building Block HypothesisSearch Space•Set of Search Operationsis the set of search operations searchOp which are available to an optimization process.•CompletenessA set of search operations searchOp is complete if and only ifevery point in the search space can be reached from everyother point by applying only operations searchOp . •Weak CompletenessA set of search operations searchOp is weakly complete if andonly if every point in the search space can be reached byapplying only operations searchOp .Search Space•What would we use as search spaces?a)Bin Packingb)Circuit Layoutc)Job Shop Schedulingd)Routinge)Find the roots off)Find mathematical formulag)Stock Predictionh)Truss Optimizationi)Medical Classificationj)Airplane Wing DesignGenotype-Phenotype Mapping•Genotype-Phenotype MappingThe genotype-phenotype mapping (GPM) : is a left-total binary relation which maps the elements of the search space toelements in the problem space .Genotype-Phenotype Mapping•How can we map the search spaces to the problem spaces?a)Bin Packingb)Circuit Layoutc)Job Shop Schedulingd)Routinge)Find the roots off)Find mathematical formulag)Stock Predictionh)Truss Optimizationi)Medical Classificationj)Airplane Wing DesignFurther Definitions•IndividualAn individual is a tuple . , . of an element . in the search space and the corresponding element . .in the problem space .•PopulationA population is a list consisting of individuals which are jointlyunder investigation during an optimization process.. , . . .Overall Structure•Overall structure of optimization processesSummary•Most optimization algorithms consist of common types of modules •Most often, specific sets and transformations are involved •Search space with genotypes•Set of search operations :•Problem space with phenotypes•Genotype-Phenotype Mapping :•Objective Functions f: ,•Fitness with谢谢你们！再见！。