Simulating Non Stationary Operators in Search Algorithm

Adrien Goeffon

LERIA, University of Angers (France)

Frederic Lardeux

LERIA, University of Angers (France)

Frederic Saubion

LERIA, University of Angers (France)

1. INTRODUCTION

1. Contributions

Our simulation model is used to compare the different performances of operator selection policies and clearly identify their ability to adapt to such specific operators behaviours and can be used as a surrogate operator model when designing new adaptive search algorithms. Hence, the general description of operator based search algorithms may be helpful in this design processwhen the user has to precisely identify the components and performance criteria that are used in the adaptive process. The experimental study provides interesting results on the respective behaviours of operator selection policies when faced to such non stationary search scenarios. Considered as a multiarmed bandit problem, our model corresponds to a specific restless banditproblem that could be used to model different real applications as soon as the efficiency of a given action decreases according to successive frequent uses. For instance, such reinforcement learning techniques are used to schedule online advertisement display on web pages. Our model could be pertinent in this context since it may be clear that the relevance of an advertisement decreases if it is too much shown to the same user. Other cases of such decrease repeated actions may actually be observed in various application domains.

2. Selecting the most suitable operators in a search algorithm when solving optimization problems is an active research area (Eiben et al., 2007; Lobo et al., 2007). Given an optimization problem, a search algorithm mainly consists in applying basic solving operators — heuristics — in order to explore and exploit the search space for retrieving solutions. The choice of the successive operators along the search process is often driven by means September 8, 2014 of parameters. The improvement of the performance of the algorithm thus relies on an adequate setting of these parameters. An optimal setting may be achieved by an optimal operator selection policy. Unfortunately, according to the underlying intuitions provided by the No Free Lunch theorems for optimization (Wolpert and Macready, 1997), this optimal policy may strongly depend on the instances of the problems to be solved.

3. Organization of the paper

In section 2, we describe optimization algorithm that are based on applications of basic search operators. We also define the problem of designing the best possible operator selection policy and show its relationship with multiarmed bandit problems. Section 3 is dedicated to review different operator selection policies. Section 4 presents our model for simulating non stationaryoperators. Experiments are presented in section 5.

4. Motivations

In this paper, we propose an alternative model for simulating search operators whose behaviour often change continuously during the search. In these scenarios, the performance of the operators decreases when they are applied. This is motivated by the fact that operators for optimization problems are often roughly classified into exploitation operators and exploration operators. Exploitation operators aim at focusing on the evaluation of the visited configurations of the search space in order to converge quickly to a local optimum. Exploration operators aim at diversifying the search trajectory by visiting sparse areas of the search space. Unfortunately, it is not possible to always exploit nor explore the search space. For instance, it is unlikely thatan exploitation operator will always improve a configuration and find directly an optimal solution (except for simple problems). Therefore, decreasing performance may be observed along the search as well as changing behaviours of operators.

5. Initial parameters setting can be achieved by automated tuning algorithms (Hutter et al., 2009; Nannen et al., 2008). Nevertheless, the values of the parameters may require more continuous control (Fialho, 2010) and should rather not be fixed during the whole search process. Adaptive operator selection is strongly related to reinforcement learning problems, and especially to multi-armed bandit problems (Fialho et al., 2008; Costa et al., 2008). Various methods for managing the famous exploration vs. exploitation balance in search heuristics have been investigated in the literature; see for instance (Maturana et al., 2009; Lobo et al., 2007; Thierens, 2005). The performance of adaptive selection policies depends on the characteristics of the problem’s search space, as well as on the specificities of the search operators. Therefore different families of practical problems have been handled, but also more abstract operators models in order to provide more general and comprehensive testing frameworks as in Thierens (2005) and Costa et al. (2008), taking into account changes in the operators behaviours.

Exercise3.16. Look through the Introduction. Put the paragraphs in the logical order.

Exercise3.17. What do the highlighted phrases express?

1. Our simulation model is used to compare the different performances of operator selection policies and clearly identify their ability to adapt to such specific operators behaviours and can be used as a surrogate operator model when designing new adaptive search algorithms.

2. Considered as a multiarmed bandit problem, our model corresponds to a specific restless banditproblem that could be used to model different real applications as soon as the efficiency of a given action decreases according to successive frequent uses.

3. Section 4 presents our model for simulating non stationary operators.

4. In this paper, we propose an alternative model for simulating search operators whose behaviour often change continuously during the search.

5. Therefore different families of practical problems have been handled, but also more abstract operators models in order to provide more general and comprehensive testing frameworks as in Thierens (2005) and Costa et al. (2008), taking into account changes in the operators behaviours.

6. Exploitation operators aim at focusing on the evaluation of the visited configurations of the search space in order to converge quickly to a local optimum.

Exercise 3.18. Find the words with the same meaning.

a) exactly

b)useful

c) element, ingredient, constituent

d) toutilize, to use

e) toinvestigate

f) approximately

g) complete, exhaustive,thorough

Exercise 3.19. Make up the list of keywords.

Exercise 3.20. Write the Abstract based on the Introduction given above.

Exercise 3.21. Summarize the Introduction.

Exercise3.22. Boost your vocabulary with the words from the Introduction.

Noun	Verb	Adjective	Adverb
surrogate	explore	respective	precisely
performance	exploit	successive	unfortunately
efficiency	converge	pertinent	roughly
reinforcement	diversify	adequate
relevance		sparse
heuristics		comprehensive

PART D

Exercise 3.23. Readthe Abstractand Introduction given below.Compare the information given in the Abstract and Introduction.Choose the correct form of the infinitive.