Considerations of Budget Allocation for
Sequential Parameter Optimization(SPO)
Thomas Bartz–Beielstein†,Mike Preuss
Dortmund University,44221Dortmund,Germany,
ls11-www.cs.uni-dortmund.de/people/
Abstract.Obviously,it is not a good idea to apply an optimization al-
gorithm with wrongly specified parameter ttings,a situation which can
be avoided by applying algorithm tuning.Sequential tuning procedures
are considered more efficient than single-stage procedures.[1]introduced
a quential approach for algorithm tuning that has been successfully ap-
plied to veral real-world optimization tasks and experimental studies.
The quential procedure requires the specification of an initial sample
size k.Small k values lead to poor models and thus poor predictions for
the subquent stages,whereas large values prevent an extensive arch
and localfine tuning.This study analyzes the interaction between global
and local arch in quential tuning procedures and gives recommen-
dations for an adequate budget allocation.Furthermore,the integration
of hypothesis testing for increasing effectiveness of the latter pha is
investigated.
1Introduction
面试自我介绍英语
This work deals with a tuning procedure,the quential parameter optimization (SPO)[1].It does not challenge applying tuning methods for experimental analy-sis of optimization algorithms per .Nor does it focus on any of the particular questions such methods may help to answer as has been done
elwhere[2],al-though our investigations shall lead to additional insight in this respect,too.Let us assume that SPO is uful for ,algorithm designs for(near-) optimal performance and parameter interactions.However,the tuning proce-dure itlf is not asfixed as may em:Integration of veral techniques(Design and analysis of computer models(DACE),spacefilling designs,noi reduction by increa of repeats)left some of the interfaces in a rather provisional state. Stated differently,we have to admit that even this parameter tuning method does have parameters.
As neither theoretical results nor a long empirical tradition of applying SPO exist,it remains unclear how appropriate the currently employed default meth-ods and values are.The SPO tuning procedure is model-bad and thus consists of two subquent phas:a)building afirst model,and b)repeatedly locating and evaluating points with maximal expected improvement.The latter pha †corresponding author:Thomas.Bartz-Beielstein@udo.edu
2
shall lead to good solutions for the tuning problem and a better model at the same time.Given that the tuned system usually contains nondeterministic opti-mization volutionary algorithms(EAs),three questions emerge:
1.How much effort shall be put into obtaining thefirst model?
如何做海外代购生意2.Which method shall be utilized for determining an initial t of design points?
3.How often shall cond-pha design points be evaluated?
We consider it impossible to answer the questions in a too general context, without further specifying the tuned algorithm–problem system.However,fo-cusing on a very small number of cas implies the danger of generating results without much practical value due to loss of transferability to other such systems. We face this difficulty by lecting test problems that are different in their most important ,unimodal vs.multimodal and real-valued vs.binary coded problems.Furthermore,the chon algorithm-problem systems are well known,thereby enabling to utilize the experience collected within the evolution-ary computation(EC)community over years.But still,our study can by no means be comprehensive;a certain arbitrariness remains and will only vanish when much more experimental effort than practicable in this work has been put into exploration and analysis of SPO performance.Although we restrict ourlves here to SPO as the only employed tuning procedure,the obtained conclusions may still be of interest for the application of other model-bad methods,in particular such that are built on regression techniques.The have to face the same three questions enumerated above.
In the following ction,we give a short summary of the SPO tuning proce-dure,going into details only insofar as necessary for discussing our experimen-tal results.Section3discuss initial designs issues,whereas Sect.4considers cond-pha points.The paper clos with a summary and an outlook in Sect.5. 2Sequential Parameter Optimization
特色开店SPO is a methodology for the experimental analysis of optimization algorithms to determine improved algorithm designs1and to learn,how the algorithm works.It employs computational statistic methods to investigate the interactions among optimization problems,algorithms,and environments.We consider each algo-rithm design with associated output as a realization of a stochastic process.We apply stochastic process models as introduced in[3],[4],and[5]to optimization algorithms such as EAs and particle swarm algorithms(PSO).Consider a t of m design points x=(x(1),...,x(m))T with x(i)∈R d.In the DACE stochastic process model,a deterministic function is evaluated at the m design points x. The vector of the m respons is denoted as y=(y(1),...,y(m))T with y(i)∈R. The process model propod in[3]express the deterministic respon y(x(i)) 1The contain all parameter ttings determining a specific algorithm instance, whereas problem designs subsume parameters related to the optimization problem and domain specific restrictions such as problem dimension or allowed function evaluations.
3
Algorithm 1Sequential parameter optimization
1:procedure SPO (D A ,D P ) Algorithm und problem design 2:Select p ∈D P and t t =0 Select problem instance 3:X (t )A ={x 1,x 2,...,x k } Sample k initial ,LHS 4:repeat 5:y ij =Y j (x i ,p )∀x i ∈X (t )A and j =1,...,r (t ) Fitness evaluation 6:Y (t )i =P r (t )j =1y (t )ij /r (t ) Sample statistic for the i th design point 7:x b with b =arg min i (y i ) Determine best point 8:Y (x )=F (β,x )+Z (x ) DACE model from Eq.19:X S ={x k +1,...,x k +s } Generate s sample points,s k 10:y (x i ),i =1,...,k +s Predict fitness from the DACE model 11:I (x i )for i =1,...,s +k Expected improvement,cf.[6]
12:X (t +1)A =X (t )A ∪{x k +i }m i =1/∈X (t )A Add m promising points
胡兴宽
13:if x (t )b =x (t +1)b then
14:r (t +1)=2r (t ) Increa number of repeats
15:end if
16:t =t+1 Increment iteration counter 17:until Budget exhausted
18:end procedure
for a d -dimensional input x (i )as a realization of a regression model 2F and a stochastic process Z ,
Y (x )=F (β,x )+Z (x ).(1)
Note that SPO inherits this process model but utilizes it for the situation of nondeterministic respons as the are usually obtained from the heuristic optimization algorithms we want to investigate.Algorithm 1[2]describes the SPO in a formal manner.3The lection of a suitable problem instance is done in the pre-experimental planning pha to avoid floor and ceiling effects (l.2).Latin hypercube sampling can be ud to determine an initial t of design points (l.3).After the algorithm has been run with the k initial parameter ttings (l.5),the DACE process model is ud to discover promising design points (l.10).Note that other sample statistics than the ,the median,can be ud in l.6.The m points with the highest expected improvement 4are added to the t of design points,where m should be small compared to s .The update rule for the number of reevalutions r (t )(l.13-15)guarantees that the new best design point x (t +1)b has been evaluated at least as many times as the previous best design point x (t )b .Obviously,this is a very simple update rule and more elaborate rules are 2
Bad on experiences from previous studies,quadratic regression models have been ud in our studies.
3A toolbox that implements SPO and provides additional material is available at:/3-540-32026-1.
4A situation in which each point has the same expected improvement can occur if (i)the objective function is constant and (ii)the optimization algorithm is deterministic.However,the situations are only of theoretical relevance.
彩色的梦4
possible.Other termination criteria exist besides the budget bad termination (l.17).
3Initial Designs
There is no simple or generic rule for choosing adequate initial designs.In classi-cal design and analysis of experiments(DoE),this is a chicken and egg problem: To determine a suitable regression model,design points are needed.But,the choice of optimal design points depends on the model[7].Experiments reported in[8]indicated the superiority of spacefilling design over classical fact
orial de-signs in the context of parameter tuning for stochastic arch algorithms.There-fore,we consider space-filling designs,which are nicely motivated in[4].So,are we lucky and can simply ignore the complex determination of adequate designs byfilling the design space randomly with design points?Unfortunately not,be-cau even with spacefilling designs,certain design criteria can be chon.We will u Latin hypercube designs(LHD)for the following experiments.LHD s haven been chon becau they are easy to understand and implement—and not becau they are proven to be superior to other spacefilling designs.[6, p.149]state:It has not been demonstrated that LHD s are superior to any de-signs other than simple random sampling(and they are only superior to simple random sampling in some cas).
In many real-world optimization scenarios,a limited budget,say time or function evaluations,for performing the optimization task is available.At least two situations,in which an allocation of the resources is possible,can be men-tioned here:First,the distribution of the available resources among the tuning pha and the optimization pha,and cond,the allocation of the resources to the initial design and the cond pha(quential steps)during tuning.We will consider the latter problem in this paper.The analysis will be restricted to the ca where the number of initial repeats is very ,r=2.This is reasonable,becau(i)in many real-world optimization scenarios large r values ar
e prohibitive and(ii)we are interested in a quick exploration of the arch space in thefirst step of this quential procedure.So,the experimental goal can be formulated in the SPO framework as follows:
Goal1.For a given number of function evaluations,N b,determine a number k of initial points for the initial design as introduced in Step3of Algorithm1. Note,that this goal occurs in any quential tuning procedure and is not re-stricted to SPO.And,in general,quential procedures are considered more efficient than procedures that u the available budget at once[9].Therefore, we are considering the most interesting cas and our results are of interest for other situations as well.The trade-offcan be described as follows:Shall we u a good initial design with only a few quential steps or perform many quential steps bad on a poor initial design?
A PSO was chon to illustrate our approach and to generate some empiri-cal data.The algorithm and results from experiments are outlined in[10].Our四川的乐山大佛
5 PSO implementation is bad on the PSOTOOLBOX,which was integrated into the SPO framework.The PSO algorithm design is shown in Table1.To specify the problem design,the following parameters were considered(Table2). The experiment’s name,the number of runs n,the maximum number of func-tion evaluations t max,the problem’s dimension d,the initialization method,the termin
ation criterion,the interval[x l,x u]for the initialization of the object vari-ables,as well as the optimization problem and the performance measure(PM) are reported.The reader is referred to[2]for a discussion of the parameters. Finally,we have to describe the SPO design(Table3).If no quential steps were performed,n LHD design points can be evaluated.Note,that n LHD=N b/r, where N b denotes the ,the total number of algorithm runs,and r is the number of repeats ud in thefirst design.The SPO us a quadratic regression model and a Gaussian correlation function.Four design points with the highest expected improvement and the best solution found so far are evalu-ated in the quential pha of the SPO run(m=4).The experimental analysis clearly demonstrated that the determination of a suitable initial design is of crucial importance for the cond pha,which performs a local tuning.To play safe,we recommend increasing the number of initial design points.The number of quential optimization steps could be reduced in many situations without a significant performance loss.Furthermore,experiments with veral optimiza-tion problems(Ronbrock,Sphere,Rastrigin,Griewank,and problems from the Mor´e test t)revealed that a small number of function re-evaluations is benefi-cial.To give an example:The following best function values have been obtained on the30-dim Ronbrock function(with t max=500function evaluations for the PSO and r=2reevaluations for the initial design):223with15initial LHD samples,324with100initial samples,and486with150initial samples.If the number of reevaluations was
incread to r=5,a function value of1663was obtained with15initial LHD sample points and values of403(2776)with30 (60)initial samples.All values reported here are averages from100repeats.5
4Evaluation of Second-Pha Points
SPO subquently evaluates cond-pha points(algorithm designs)for two rea-sons:a)tofind optimal designs,and b)to improve the model.In order to coun-teract the nondeterministic nature of the modeled algorithm-problem system, the standard procedure doubles the number of repeats performed of the current
Table1.PSO algorithm designs.Swarm size s,cognitive and social parameters c1and c2,and w iterScale,the percentage of the run,in which the inertia weight is decread.
褔字图片
5Note,that[10]ud80times more function evaluations to obtain similar results. They ud recommendations from theory to perform their ,theoreti-cally derived values for c1and c2.
6
Table2.Problem designs for the sphere function.Similar designs have been ud for the Ronbrock,Griewank,and Rastrigin function.The maximum number of function evaluations for one algorithm run is t max,whereas n denotes the number of repeats for each algorithm run.Altogether,n×t max function evaluations were performed.See[10]
Table3.SPO algorithm designs for tuning the particle swarm optimization.“Merge”denotes the statistic that was ud to compare the performance of algorithm designs with stochastically disturbed ,from EAs
best point whenever an iteration fails to provide an improvement,cf.l.14from Algorithm1.Conquently,to enable fair comparison between the current best and newly suggested point(s),SPO ensures that both have been sampled for the same number of times.However,this procedure can become expensive in terms of algorithm runs,resulting in rather low numbers of cond-pha points if the available budget is tight.
If we had means to decide which of the points(best or suggested)leads to better performance without necessarily carrying out the suggested number of repeats in full,algorithm runs could be saved,resulting in a higher number of cond-pha points without great loss of information.Concerning the arch for optimal designs,this is undoubtedly an advantage.However,it could be argued that reducing the number of repeats also entails reducing the intended model improvement.Nevertheless,we have to take into account that a)cond-pha points are usually evaluated much more often thanfirst-pha points,b)only clearly wor performing points can easily be rejected,and c)saved runs are invested again into new points in the following iterations.
Asssing significant differences of two underlying systems reprented by a number of samples is the intended purpo of hypothesis tests.However,the often applied t-tests require approximate normal distributions,a demand that is usually not met by results obtained from heuristic optimization algorithms.As an alternative,we therefore resort to bootstrap permutation tests([11],ction 14.5)which do not presume normality but instead anticipate identically shaped distributions.Fortunately,permutation tests are robust against small differences in shapes so that we regard this prerequisite as more realistic then to expect normality.
Table4.ES algorithm designs.The learning rateτapplies to the Rastrigin function, the mutation rate p
mut to the MMDP,resulting in4free parameters each.
family是什么意思
