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

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

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