Continuous Optimisation Algorithms

  • Dodaj recenzję:
  • Kod: 3351
  • Producent: Wydawnictwo Politechniki Gdańskiej
  • Autor: Krzysztof Tesch

Continuous Optimisation Algorithms

rok wydania: 2016, wydanie pierwsze
ilość stron: 211
ISBN: 978-83-7348-681-2
 
Opis
Książka poświęcona jest zagadnieniom optymalizacji ciągłej. Oprócz klasycznych algorytmów gradientowych omówiono współczesne algorytmy bezgradientowe, które stosowane są z powodzeniem w optymalizacji globalnej. Większość prezentowanych algorytmów określona może być mianem metaheurystycznych. Zaliczyć do nich można metody optymalizacji inspirowane procesami zachodzącymi w przyrodzie, które następnie można dzielić na inspirowane zjawiskami fizycznymi, procesami biologicznymi czy inteligencją roju. Osobne rozdziały poświęcono zagadnieniom optymalizacji z ograniczeniami i optymalizacji wielokryterialnej. Przedstawiono w nich również informacje o rachunku wariacyjnym. Większość omawianych algorytmów poddano analizie statystycznej dla przypadku minimalizacji skomplikowanych i wielowymiarowych funkcji.

Wszystkie omawiane algorytmy opisane są w postaci pseudokodu, który z łatwością można zamienić na dowolny język programowania. W załączniku zamieszczono przykładowe listingi w wybranym języku programowania, które są krótkie i przejrzyste. Mogą one być łatwo modyfikowane dla indywidualnych potrzeb i zastosowań.
Podręcznik przeznaczony jest dla studentów studiów magisterskich i doktoranckich wydziałów mechanicznych, informatyki oraz fizyki i matematyki stosowanej. Zainteresować może również specjalistów z przemysłu, którzy chcą wykorzystać nowoczesne metody optymalizacyjne w celu ulepszenia swoich konstrukcji i rozwiązań.

Spis treści
Contents
1 Introduction / 7
1.1 Standard problem formulation / 7
1.2 Global and local minima / 8
1.3 Feasibility problem / 8
1.4 Example / 8
1.5 Classi cation of optimisation problems / 9
1.6 Classi cation of algorithms / 10
1.7 Hyperoptimisation / 11
1.8 Test functions / 11
1.8.1 Multimodal test function / 12
1.8.2 Unimodal test function / 12
1.9 Products  / 13
2 Single-point, derivative-based algorithms / 14
2.1 Introduction / 14
2.1.1 Classi cation / 14
2.1.2 Gradient and Hessian of a function / 14
2.1.2.1 Gradient / 14
2.1.2.2 Hessian / 15
2.2 Newton's method / 16
2.3 Modi ed Newton's method / 17
2.4 Method of steepest descent / 18
2.5 Quasi-Newton methods / 20
2.5.1 Secant method / 20
2.5.2 Other methods / 20
2.6 Conjugate gradient method / 21
2.7 Conditions for optimality / 22
3 Single-point, derivative-free algorithms / 25
3.1 Random variables and stochastic processes / 25
3.1.1 Selected random variables / 25
3.1.1.1 Discrete uniform distribution / 25
3.1.1.2 Continuous uniform distribution / 26
3.1.1.3 Normal distribution / 26
3.1.1.4 Lévy alpha-stable distribution / 27
3.1.2 Selected stochastic processes / 28
3.1.2.1 Wiener process / 28
3.1.2.2 Lévy ight / 29
3.2 Random walk / 30
3.2.1 Uncontrolled random walk / 30
3.2.2 Domain controlled random walk / 31
3.2.3 Position controlled random walk / 32
3.3 Simulated annealing / 34
3.4 Random jumping / 36
4 Multi-point, derivative-free algorithms / 37
4.1 Introduction / 37
4.1.1 (Meta)heuristic / 37
4.1.2 Nature-inspired algorithms / 37
4.2 Physics-based algorithms  / 38
4.2.1 Gravitational search algorithm / 38
4.3 Bio-inspired algorithms / 41
4.3.1 Genetic algorithms / 41
4.3.1.1 Evolutionary algorithms / 41
4.3.1.2 Binary representation / 42
4.3.1.3 Floating-point representation / 43
4.3.2 Di erential evolution / 47
4.3.3 Flower pollination algorithm / 49
4.4 Swarm intelligence based algorithms / 51
4.4.1 Particle swarm optimisation / 51
4.4.2 Accelerated particle swarm optimisation / 52
4.4.3 Fire y algorithm / 54
4.4.4 Bat algorithm / 57
4.4.5 Cuckoo search / 59  
5 Constraints / 62
5.1 Unconstrained and constrained optimisation / 62
5.2 Lagrange multipliers / 63
5.2.1 The method / 63
5.2.2 Equality constraints / 64
5.2.3 Inequality constraints / 66
5.2.4 Equality and inequality constraints / 68
5.2.5 Box constraints / 69
5.3 Penalty function method / 70
5.4 Barrier method / 71
6  Variational calculus / 72
6.1 Functional and its variation / 72
6.1.1 Necessary condition for an extremum / 72
6.1.2 The Euler equation / 73
6.1.3 Constraints / 75
6.2 Classic problems / 75
6.2.1 Shortest path on a plane / 75
6.2.2 Brachistochrone / 76
6.2.3 Minimal surface of revolution / 78
6.2.4 Isoperimetric problem / 79
6.2.5 Geodesics / 81
6.2.6 Minimal surface passing through a closed curve in space / 83
6.2.7 Variational formulation of elliptic partial di erential equations / 84
6.3 Variational method of  nding streamlines in ring cascades for creeping  ows / 85
6.3.1 Introduction / 85
6.3.2 Conservation equation in curvilinear coordinate systems / 85
6.3.3 Dissipation function and dissipation power / 86
6.3.4 Analytical solutions / 86
6.3.5 Dissipation functional / 87
6.3.6 Dissipation functional vs.  equations of motion / 88
6.3.7 Streamlines / 89
6.3.7.1 Both ends constrained / 89
6.3.7.2 One end partly constrained / 90
6.3.7.3 One end unconstrained / 91
6.3.8 Summary  / 92
6.4 Minimum drag shape bodies moving in inviscid  uid / 92.
6.4.1 Problem formulation / 92
6.4.2 Fluid Resistance / 93
6.4.2.1 Drag force / 93
6.4.2.2 Pressure coefficients and its approximation / 93
6.4.3 Two-dimensional problem / 94
6.4.4 Three-dimensional problem / 95
6.4.4.1 Functional and Euler equation / 95
6.4.4.2 Exact pseudo solution / 96
6.4.4.3 Approximate solution due to the functional / 96
6.4.4.4 Approximate solution due to form of the function / 96  
6.4.4.5 Approximate solution by means of a Bézier curve / 97
6.4.5 Summary / 98
7 Multi-objective optimisation / 100
7.1 De nitions / 100
7.2 Domination / 100
7.2.1 The Pareto set / 101
7.2.2 The Pareto front / 101
7.3 Scalarisation / 101
7.3.1 Method of weighted-sum / 101
7.3.2 Method of target vector / 102
7.3.3 Method of minimax / 102
7.4 SPEA / 102
7.5 Examples / 103
7.5.1 Two objective  tness functions of a single variable / 103
7.5.1.1 Analytical solution / 104
7.5.1.2 Single objective reconstruction of Pareto set / 104
7.5.1.3 Multi-objective SPEA / 104
7.5.2 Two objective  tness functions of two variables / 104
7.5.2.1 Analytical solution / 106
7.5.2.2 Single objective reconstruction of Pareto set / 107
7.5.2.3 Multi-objective SPEA / 107
7.6 Multi-objective description of Murray's law / 109
7.6.1 Introduction / 109
7.6.2 Multi-objective description / 110
8 Statistical analysis / 113
8.1 Distributions / 113
8.2 Discrepancy / 115
8.3 Single-problem statistical analysis / 115
8.4 Multiple-problem statistical analysis / 173
8.4.1 D = 2, 100 evaluations / 174
8.4.2 D = 2, 400 evaluations / 175
8.4.3 D = 2, 2000 evaluations / 176
8.4.4 D = 10, 104 evaluations / 177
Bibliography / 178
A Codes / 181
A.1 Single-point, derivative-free algorithms / 181
A.2 Multi-point, derivative-free algorithms / 184
A.3 Miscellaneous / 193
B AGA { Advanced Genetic Algorithm / 194
B.1 Brief introduction / 194
B.2 Detailed introduction / 195
B.3 I/O Console / 203
B.4 Script writing / 208