[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] Linear Classification

图片
Linear Classification Discriminant functions Least squares for classification Fisher’s linear discriminant K-Nearest Neighbour(KNN) Classification What’s decision boundaries/linearly separable? The goal in classification is to take an input vector x and to assign it to one of K discrete classes \(C_k\) where k = 1,…,K. In the most common scenario, the classes are taken to be disjoint, so that each input is assigned to one and only one class. The input space is thereby divided into decision regions whose boundaries are called decision boundaries or decision surfaces. In this blog, we consider linear models for classification , by which we mean that the decision surfaces are linear functions of the input vector x and hence are defined by (D-1) -dimensional hyperplanes within the D-dimensional input space. For example: in 3D input space, the decision boundary will be a 2D surface What is Linear Separability Linearly separable data: Datasets whose classes can be separated by
阅读全文

[CS231] Neural Networks

图片
Neural Network Table of Contents: Quick intro without brain analogies Modeling one neuron Biological motivation and connections Single neuron as a linear classifier Commonly used activation functions Neural Network architectures Layer-wise organization Summary Additional references Quick intro It is possible to introduce neural networks without appealing to brain analogies. In the section on linear classification we computed scores for different visual categories given the image using the formula \( s = W x \), where \(W\) was a matrix and \(x\) was an input column vector containing all pixel data of the image. In the case of CIFAR-10, \(x\) is a [3072x1] column vector, and \(W\) is a [10x3072] matrix, so that the output scores is a vector of 10 class scores. An example neural network would instead compute \( s = W_2 \max(0, W_1 x) \). Here, \(W_1\) could be, for example, a [100x3072] matrix transforming the image into a 100-dimensional intermediate vector. The funct
阅读全文