-
Notifications
You must be signed in to change notification settings - Fork 0
/
part_introduction.tex
172 lines (172 loc) · 10.5 KB
/
part_introduction.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
%
\section{Introduction}%
%
\begin{frame}%
\frametitle{Quick Overview}%
\begin{itemize}%
\item Concept of optimization algorithms%
\item<2-> How to \alert<4>{benchmark} optimization algorithms%
\item<3-> How to \alert<4>{evaluate data} obtained from benchmarking and how to compare algorithms%
\item<4-> \alert<4>{The \optimizationBenchmarking\ Framework can help with this!}%
\end{itemize}%
\end{frame}%
%
%
\begin{frame}[t]%
\frametitle{Optimization}%
\begin{itemize}%
\item Many questions in the real world are actually optimization problems\only<2->{, e.g.,\only<-7>{%
\begin{itemize}%
%
\item \only<-5>{Find the \emph{shortest} tour for a salesman to visit certain set of cities\only<-2>{ in China and return to Hefei!}}\only<6->{\alert<6>{Traveling Salesman Problem}\scitep{ABCC2006TTSPACS,LLKS1985TTSPAGTOCO,GP2004TTSPAIV,L2011SGEFTSPIMSS}}%
%
\item<3-> \only<-5>{I need to transport $n$ items from here to another city\only<-3>{ but they are too big to transport them all at once. How can I load them best into my car so that I have to travel back and forth the least times?}}\only<6->{\alert<6>{Bin Packing Problem}\scitep{KSH1995EHFTBPP}}%
%
\item<4-> \only<-5>{Which setting of $x_1$, $x_2$, $x_3$, and $x_4$ can make $(x_1\lor\lnot x_2 \lor x_3)\land(\lnot x_2\lor\lnot x_3 \lor x_4) \land (\lnot x_1\lor\lnot x_3 \lor \lnot x_4)$ become true\only<-4>{ (or, at least, as \emph{many} of its terms as possible)?}}\only<6->{\alert<6>{Maximum (3-)Satisfiability Problem}\scitep{HS2000SAORFROS,TH2004UAIAEEFSAFSAMS,S1978TCOSP,RMK2000EASP}}%
%
\item<5-> \only<-5>{I want to build a large factory with $n$ workshops. I know the flow of material between each two workshops and now need to choose the locations of the workshops such that the overall running cost incurred by material transportation is \emph{minimized}.}\only<6->{\alert<6>{Quadratic Assignment Problem}\scitep{MF1999ACOMATSAACFTQAP,GTD1999ACOQAP}}%
\end{itemize}%
}\only<8->{ the Traveling Salesman Problem\scitep{ABCC2006TTSPACS,LLKS1985TTSPAGTOCO,GP2004TTSPAIV,L2011SGEFTSPIMSS}}%
}%
%
\item<7-> Many optimization problems are \NPHard, meaning that finding the \textcolor<9-11>{green}{best possible solution} will often take \textcolor<9-11>{green}{way too long}.%
%
\item<10-> Of course, it is easy to get \textcolor<10-11>{red}{\emph{some} solutions (usually of bad quality)}%
%
\item<11-> We use metaheuristic optimization algorithms to give us good approximate solutions within acceptable runtime.%
\item<12-> Examples of such algorithms are\only<-22>{ %
Evolutionary Algorithms\scitep{BFM1997EA,CWM2011VOEAFRWA,BFM2000EC1BAAO,BFM2000EC2BAAO,DLJD2000EC,EM1999EC,CDGDMPP1999NIIO,GT2002AIECTAA,WGOEB}\uncover<13->{, %
Ant Colony Optimization\scitep{DMC1996ACO,DS2004ACO,GM2002APBATDOP,ZBMD2004MBSFCOACS,WGOEB}\uncover<14->{, %
Evolution Strategies\scitep{R1965ES,R1973ES,R1994ES,S1965KYASDEFIDS,S1968EOEZDT1,S1975EUNO,WGOEB}\uncover<15->{, %
Differential Evolution\scitep{PSL2005DE,F2006DE,WGOEB}\uncover<16->{, %
Particle Swarm Optimization\scitep{KE1995PSO,C2006PSO,WGOEB}\uncover<17->{, %
Estimation of Distribution Algorithms\scitep{PSL2005DE,F2006DE,MMVRCC2006DE,BZSM2006DE,LZ2000DE,MM2005DE,BVPK2006DE,S2010DEFCFOAABKPARS}\uncover<18->{, %
CMA-ES\scitep{HOG1995ESAD,HO1996AANMDIESTCMA,HO2001ESCMA,HMK2003RTTCOTDESWCMACE,HK2004ETCESOMTF,H2006TCESACR,AH2005ARCESWIPS,AH2005PEOAALSEA}\uncover<19->{, and %
Local Search methods\scitep{HS2005SLSFAA,AL1997LSICO,DBSD2001DOILSA}\uncover<20->{ such as %
Simulated Annealing\scitep{SSF2002FCAIFSA,LA1987SATAA,B1987GAASA,JCS2003HC,KGV1983SA,VC1985SA,DPSW1982MCTICO,DPSW1982MCTICO2,P1970AMCMFTASOCTOCOP,WGOEB}\uncover<21->{ or %
Tabu Search\scitep{G1989TSPI,G1990TSPII,GL1993TABU,DWH1989TSTATAAATNN,BT1994TABU}\uncover<22->{, %
as well as hybrids of local and global search, such as Memetic Algorithms\scitep{M1989MA,M2002MA,MC2003AGITMA,ES2003HWOTMA,HKS2005RAIMA,DM2004MA,RS1994FMA}%
}}}}}}}}}}}\only<23->{\dots\ \alert{many}}%
%
\item<24-> \alert<24>{Which of them is best (for my problem)?}%
\item<25-> \alert<25>{How can I make a good algorithm better (for my problem)?}%
%
\end{itemize}%
~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\%
%
\locateGraphic{2}{width=0.6\paperwidth}{graphics/problem_examples/tsp/tsp}{0.2}{0.29}%
\locateGraphic{3}{width=0.875\paperwidth}{graphics/problem_examples/bin_packing/bin_packing}{0.0625}{0.495}%
\locateGraphic{4}{width=0.55\paperwidth}{graphics/problem_examples/sat/sat}{0.225}{0.5}%
\locateGraphic{5}{width=0.85\paperwidth}{graphics/problem_examples/qap/qap}{0.075}{0.625}%
\locateGraphic{7}{width=0.75\paperwidth}{graphics/exponential_functions/exponential_functions}{0.1625}{0.55}%
%
\locateGraphic{8}{width=0.75\paperwidth}{graphics/optimization_concept/optimization_concept_1}{0.125}{0.53}%
\locateGraphic{9}{width=0.75\paperwidth}{graphics/optimization_concept/optimization_concept_2}{0.125}{0.53}%
\locateGraphic{10}{width=0.75\paperwidth}{graphics/optimization_concept/optimization_concept_3}{0.125}{0.53}%
\locateGraphic{11}{width=0.75\paperwidth}{graphics/optimization_concept/optimization_concept}{0.125}{0.53}%
%
\end{frame}%
%
%
\begin{frame}[t]%
\frametitle{Performance and Anytime Algorithms}%
%
\emph{\inQuotes{We use metaheuristic optimization algorithms to give us \alert<3->{good approximate solutions} within \alert<4->{acceptable runtime}.}}%
%
\uncover<2->{%
\begin{itemize}%
\item Algorithm performance has two dimensions\scitep{NAFR2010RPBBOB2ES,WCTLTCMY2014BOAAOSFFTTSP}:\uncover<3->{ solution quality\uncover<4->{ and required runtime}}%
\only<-9>{%
\item<5-> Anytime Algorithms\scitep{BD1989STDPP2} are optimization methods which maintain an approximate solution at \emph{any time} during their run and iteratively improve this guess.%
\item<6-> All metaheuristics are Anytime Algorithms.%
\item<7-> Several exact methods like Branch-and-Bound\scitep{LMSK1963AAFTTSP,Z1993TBABACSOTATSP,Z1999TAADFBABACSOTATSP} are Anytime Algorithms.%
\item<8-> Consequence: Most optimization algorithms produce approximate solutions of different qualities at different points during their process.%
\item<9-> \alert{Experiments must capture data on the whole runtime behavior!}%
}%
\item<10-> If we just compare \inQuotes{final} results, we may arrive at incomplete \only<12->{or entirely wrong} conclusions%
\end{itemize}%
}%
%
\locateGraphic{3}{width=0.55\paperwidth}{graphics/performance/performance_dimensions/performance_dimensions_1}{0.225}{0.542}%
\locateGraphic{4}{width=0.55\paperwidth}{graphics/performance/performance_dimensions/performance_dimensions_2}{0.225}{0.542}%
\locateGraphic{5,10}{width=0.55\paperwidth}{graphics/performance/performance_dimensions/performance_dimensions}{0.225}{0.542}%
\locateGraphic{11}{width=0.55\paperwidth}{graphics/performance/performance_dimensions/performance_cuts}{0.225}{0.542}%
\locateGraphic{12}{width=0.55\paperwidth}{graphics/problems_with_points/points}{0.225}{0.542}%
\locateGraphic{13}{width=0.55\paperwidth}{graphics/problems_with_points/lines}{0.225}{0.542}%
%
\end{frame}%
%
%
\begin{frame}[t]%
\frametitle{Experimentation Procedure}%
\begin{itemize}%
\item The following experimentation procedure is suitable for optimization and Machine Learning\uncover<2->{:%
\begin{enumerate}%
\item Select a set of (well-known) benchmark instances which covers some \textcolor<18>{red}{different problem features}\only<5->{ \alert{(done)}}\only<3-4>{:%
\begin{itemize}%
%
\only<-3>{%
\item<3-> e.g., \tspLib\expandafter\scitep{\tspLibReferences} for the TSP has instances with different numbers of cities and geometries%
}%
\only<-4>{%
\item<4-> e.g., \bbob\expandafter\scitep{\bbobReferences} offers different benchmark functions for numerical optimization problems%
}%
%
\end{itemize}%
}%
\item<5-> Do experiments\only<11->{ with \textcolor<18>{red}{different algorithms/setups}\only<11->{ \alert{(done)}}}\only<6-10>{:%
\begin{itemize}%
\item several independent runs of algorithm for each benchmark instance%
\item<7-> collect algorithm progress information, e.g., as \emph{\inQuotes{(runtime, best-objective-value-so-far)}} tuples%
\item<8-> one log file per run, each log file has several such tuples%
\item<9-> repeat for different algorithm parameter settings (e.g., different population sizes of an EA)%
\item<10-> repeat with other algorithms for comparison purposes%
\end{itemize}%
}%
\item<12-> Evaluate the gathered data\only<13->{, e.g.:%
\begin{itemize}%
\item \textcolor<17>{green}{draw diagrams of progress of solution quality over time}%
\item<14-> \textcolor<17>{green}{draw diagrams of advanced statistical parameters such as ECDF\scitep{HAFR2012RPBBOBES,HS1998ELVAPAR,TH2004UAIAEEFSAFSAMS,WCTLTCMY2014BOAAOSFFTTSP}\only<15->{ and ERT\scitep{HAFR2012RPBBOBES,WCTLTCMY2014BOAAOSFFTTSP}} (over time)}%
\end{itemize}%
}%
%
\item<16-> But doing this is cumbersome\dots%
\end{enumerate}%
}%
\item<17-> The \optimizationBenchmarking\ framework \textcolor<17>{green}{can automatize} much of the evaluation procedure\uncover<18>{\dots}%
\item<18-> {\dots}and make use of \textcolor<18>{red}{meta-data} about experiments to group and aggregate information.%
\end{itemize}%
%
\locateWithCaption{3}{%
\includegraphics[width=0.925\paperwidth]{graphics/tspLib_features/tspLib_features_symmetric}%
}{%
The relative amounts of the instances of the 110 symmetric instances of \tspLib\expandafter\scitep{\tspLibReferences} according to their features (the 10 asymmetric instances are not plotted).%
}{0.0375}{0.51}{0.925}%
%
\locateWithCaption{4}{%
\includegraphics[width=0.925\paperwidth]{graphics/bbob_features/bbob_features}%
}{%
The relative amounts of \bbob\expandafter\scitep{\bbobReferences} benchmark functions according to their features.%
}{0.0375}{0.51}{0.925}%
%
\locateWithCaption{7-8}{%
\includegraphics[width=0.8\paperwidth]{graphics/tspSuite_logfile_example/tspSuite_logfile_example}%
}{%
Example for data collected in a log file by \tspSuite\expandafter\scitep{\tspSuiteReferences}.%
}{0.0375}{0.53}{0.925}%
%
\locateWithCaption{13-15}{
\strut%
\includegraphics[width=0.28\paperwidth]{graphics/performance/progress_example/progress_example}%
\uncover<14->{%
\strut\hfill\strut%
\includegraphics[width=0.28\paperwidth]{graphics/performance/ecdf_example/ecdf_example}%
\uncover<15->{%
\strut\hfill\strut%
\includegraphics[width=0.28\paperwidth]{graphics/performance/ert_example/ert_example}%
}}\strut%
}{%
Examples for progress\only<14->{ and ECDF}\only<15->{, ERT, and ECDF} diagrams from \tspSuite\expandafter\scitep{\tspSuiteReferences} for different algorithms (signified by different colors) over different sub-sets of the \tspLib\expandafter\scitep{\tspLibReferences} data.%
}{0.0375}{0.545}{0.925}%
%
\end{frame}%