[AIM] MetaHeuristics

Day2

Outline

  • Metaheuristics -definition
  • Single point based search method(simple stochastic local search)
  • Iterated local search
  • Scheduling
  • Tabu Search

Metaheuristic

what is a metaheuristic?
A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms.
what is the difference between heuristic and metaheuristic?
Heuristic: Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution.
Metaheuristic: Meta-heuristics, on the other hand, are problem-independent techniques. As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes. In general, they are not greedy. In fact, they may even accept a temporary deterioration of the solution (see for example, the simulated-annealing technique), which allows them to explore more thoroughly the solution space and thus to get a hopefully better solution (that sometimes will coincide with the global optimum).
Hyper-heuristics: The particularity of hyper-heuristics is that their search space is not the usual space of the solutions but is rather the space of heuristics or meta-heuristics. Indeed, hyper-heuristics can be viewed as “heuristics to search for heuristics”.
Available:https://www.researchgate.net/post/What_are_the_differences_between_heuristics_and_metaheuristics [accessed Apr 17, 2017].

Classifications


Three fundamental classes of metaheuristics can be distinguished, based on the way in which solutions are manipulated.
  • Local search metaheuristics iteratively make small changes to a single solution.
  • Constructive metaheuristics construct solutions from their constituting parts. It starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained.
  • Population-based metaheuristics iteratively combine solutions into new ones.
  • More Here

Mechanisms for escaping from local optima

In Day1, we have covered representation/ evaluation function/ initialisation/ neighbourhood, now we will cover stopping conditions(termination criteria) and mechanism for escaping from local optima.
  • Iterate with different solutions, or restart(re-initialize search whenever a local optimum is encountered)
    Initialization could be costly
    e.g. Iterated local search, GRASP
  • Change the search landscape
    change the objective function (e.g. guided local search)
    use(mix) different neighbourhoods (e.g. variable neighbourhood search, hyper-heuristics)
  • Use memory(Tabu search)
  • Accept non-improving moves: allow search using candidate solutions with equal or worse evaluation function value than the one in hand
  • None of the mechanisms is guaranteed to always escape effectively from local optima

Termination criteria examples

Stop if
  • a fixed maximum number of iterations, or moves, or fixed amount of CPU time is exceeded
  • the consecutive number of iterations since the last improvement in the best objective function value is larger than a specified number
  • evidence can be given that an optimum solution has been obtained
  • no feasible solutions can be obtained for a fixed number of steps/time

Iterated local search(ILS)

First, we will look at stochastic local search-single point based iterative search

Then, what is a good search algorithm?
  • Effective search techniques provide a mechanism to balance exploration and exploitation
  • Exploitation/intensification aims to greedily increase solution quality or probability, e.g., by exploiting the evaluation function
  • Exploration/diversification aims to prevent stagnation of search process getting trapped at a local optimum
Aims is to design search algorithms/metaheuristics that can
  • escape local optima
  • balance exploration and exploitation
  • make the search independent from the initial configuration

Based on visiting a sequence of locally optimal solutions by:
  • perturbing the current local optimum(exploration/diversification)
  • applying local search(exploitation/intensification) after starting from the modified solution
A perturbation phase might consist of one or more steps, if the perturbation strength is
- Too small(weak): may generate cycles
- Too big(strong): good properties of the local optima are lost
Acceptance criteria
- accept only improving solutions
- accept any solutions
- deterministic(like threshold), probabilistic(like simulated annealing)

Some guidelines of ILS

  • Initial solution should be to a large extent irrelevant for longer runs
  • The interactions among perturbation strength and acceptance criterion can be particularly important
  • Advanced acceptance criteria take into account search history, e.g. by occasionally reverting to incumbent solution
  • Advanced ILS algorithms may change nature and/or strength of perturbation adaptively during search
  • Local search should be as effective and as fast as possible. Better local search generally leads to better ILS performance.
  • Choose a perturbation operator whose steps cannot be easily undone by the local search
  • Uses history(memory structures) to escape from local minina.
  • Applies hill climbing/local search

Tabu-search fundamental

  • A stochastic local search algorithm which heavily relies on the use of an explicit memory of the search process
  • In each step, move to ‘non-tabu’ best neighbouring solution (admissible neighbours) although it may be worse than current one
  • To avoid cycles, tabu search tries to avoid revisiting previously seen solutions
  • Tabu-list contains moves which have been made in the recent past

Tabu-search example

It is unclear what Tabu search actually is, let us look at a scheduling example:

The scheduling problem explains that there is four jobs on a machine, and what we need is to maximize the sum of Wj * Tj
For this problem, we need two things: operator to visit neighbourhood and tabu-list
Because the scheduling problem is all about the order of each job, so we will use numbers(which are not overlap) to represent the sequence of jobs. Then neighbourhood operator will be exchange the adjacent pairwise jobs. Then we store these jobs which are exchanged as a pair in the tabu list.

Let’s have a look at this illustration.
First, we initialize a permutation <2, 1, 4, 3>
The initial solution has a fitness value of 500
  • This evaluation function is a little bit complex. w is the weight of each job. d is the due time, is designed or required before. p is the actually processing time. T is tardness which is like a delay time.
  • For <2, 1, 4, 3>, the first job 2 has a value 12*(10-2) = 12 * 8.
  • Job 1 has 14 * (10+10-4) = 14 * 16. Because the job 2 has a processing time of 10 and job1 has another 10.
  • Job 4 has 12 * 12 because 12 * (10+10+4-12)
  • Job 1 then has 1 * (10+10+4+13 -1) = 1* 36
Then we exchange all the adjacent pairwise number, we find <2, 4, 1, 3> is the best solution. So we add (1,4) into tabu list.
On the next step, (1,4) will be in tabu-list so we can’t accept it no matter what evaluation value it is. We will accept 460 one, although is is not better than current best one.

Tabu tenure

Stop here!
We haven’t think about tabu tenure.
Tabu tenure is the length of time/number of steps t for which a move is forbidden.
Every time we add a new thing into tabu-list, we decrement each tabu-tenure by 1.
  • Appropriate choice of tabu tenure critical for performance
  • if t is too low, the pair(let’s assume it is a pair) will be free from tabu-list quickly and it might encounter the risk of cycle
  • if t is too high, the pair cannot be free from tabu-list easily, it may restrict the search too much
  • t =7 has often been found sufficient to prevent cycling or we can use root n
  • if a tabu move is smaller than the aspiration level then we accept the move (use of aspiration criteria to override tabu status)
  • This means that if we can only create 3 sub-solution but the tabu tenure is 5. Then there will be a time that we cannot accept any solution because of the tabu-tenure, then we will be more flexible, we will accept the move.
Further improvements can be achieved by using intermediate-term or long-term memory to achieve additional intensification or diversification.
  • backtrack to elite candidate solutions, reset tabu list
  • freeze certain solution components for a number of steps
  • occasionally force rarely used solution components
  • extend evaluation function to capture frequency of use of candidate solutions (or components)

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文