[AIM] Cross-domain search and selection hyper-heuristics

Day 6

Outline

  • Cross-domain search: observations
  • Hyper-heuristics - definition, origins
  • A classification of hyper-heuristics
  • Selection hyper-heuristics controlling perturbative heuristics
  • Selection hyper-heuristics controlling constructive heuristics
  • Cross-domain parameter tuning of a memetic algorithm
There are a lot of different search domain which needs new operators, search method and evaluation function. For example, flowshop scheduling, vehicle routing, nurse rostering, you can not use the same heuristic.
  • Most of the real-world optimisation problems are proven to be NP-hard
  • The current state of the art in search methodologies tend to focus on bespoke systems
  • In general, these systems are expensive to build, but provide successful results. Unfortunately, their application to new problem domain still requires expert involvement
  • A different heuristic might generate good performance on different problem instance
  • A goal is raising the level of generality of search methodologies through learning and adaptation so that they would be applicable across a broad range of problems without requiring any human expert intervention.

Hyper-heuristics

A hyper-heuristic is a search method or learning mechanism for selecting or generating heuristics to solve computationally difficult problems.
enter image description here
  • Hyper-heuristics operate on a search space of heuristics rather than directly on a search space of solutions
  • Existing(or computer generated) heuristics can be used within hyper-heuristics
  • Aim is to take advantage of strengths and avoid weaknesses of each heuristic
  • No problem specific knowledge is required during the search over the heuristics space

Classification of hyper-heuristics

According to the nature of the heuristic search space, it can be classified to be heuristic selection and generation, for each one, there is constructive and perturbative.
For heuristic selection, it will always use fixed heuristic, for heuristic generation, it will automatically generated heuristic from components.
According to the feedback, it can be online learning, offline learning and no-learning.
Online learning: while solving a problem instance(adapt). Examples are: reinforcement learning, meta-heuristics
Offline learning: From a set of training instances(generalise), we trained it and choose one heuristic, after train it, we use it for all the instance. Examples are: classifier systems, GP

A hyper-heuristic Framework

enter image description here

A selection hyper-heuristic framework

For a selection hyper-heuristic framework, it will have a heuristic selection method and move acceptance criteria
enter image description here

Heuristic selection

We can divide heuristic selection method to with learning and with no learning
  • With no learning: Simple random and random permutation
  • With learning:
    • Greedy
    • Peckish(faster version of greedy)
    • Random Gradient
    • Random permutation Gradient
    • Choice Function
    • Reinforcement Learning

Greedy

Apply each low level heuristic to the candidate solution and choose the one that generates the best objective value

Peckish

If you have 100 heuristics, you apply each using greedy and choose the top 10 one

Random Gradient and Random Permutation Gradient

These are learning versions of simple random and random permutation. You randomly choose one heuristic and apply it. If there is improvement, you continue apply it until there is no improvement.

Reinforcement Learning

Reward and punishment!
Maintains a score, if an improving move then increase (+1), otherwise decrease (-1)

Choice Function

The choice function maintains a record of the performance of each heuristic. Three criteria are maintained:
  • Its individual performance
  • How well it has performed with other heuristics
  • The elapsed time since the heuristic has been called
    F\(_t\)(h\(_j\))+ \(\alpha_t\)f\(_1\)(h\(_j\)) + \(\beta_t\)f\(_2\)+\(\gamma_t\)f\(_3\)(h\(_j\))

HyFlex: Hyper-heuristics Flexible Interface

HyFlex defines a interface between problem domain and hyper-heuristic layer.
enter image description here

评论

发表评论

此博客中的热门博文

[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
阅读全文

[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, t
阅读全文