[AIM] Evolutionary Algorithms II

Day 5

Outline

  • Generic permutation based operators
    • Partially mapped crossover(PMX)
    • Order crossover (OX)
    • Cycle crossover (CX)
  • Memetic Algorithms
  • Multimeme (self-adaptive/self-generating) memetic algorithms

Issues with binary representation in GA

Binary representation and classical crossover and mutation operators are not suitable for encoding permutation
for TSP, could cause illegal tours that:
- not all cities visited
- cities visited more than once
- loops formed within the tour
Because it is a permutation, there should not have any number that overlap.

So how do we solved this problem?

Partially mapped crossover

  • Choose two random cut points to serve as swapping boundaries
  • Swap segments between cut points
  • Preserving the order and position of as many cities as possible from other parent

Order Crossover (OX)

  • Choosing a subsequence of a tour from one parent
  • Preserving relative order of cities from other parent

Cycle Crossover (CX)


Memetic Algorithms(Population based metaheuristic)

  • Meme: Contagious piece of information, it is like culture, information sharing
  • Memes are similar to local refinement/local search
  • Gene vs Meme: Memes can change, evolve using rules and time scales other than the traditional genetic ones.
  • Aims to improve GAs by embedding local search
  • MAs make uses of exploration capabilities of GAs and exploitation capabilities of local search
  • MAs have an explicit mechanism to balance exploitation and exploration
  • Memetic Algorithms shown to be much faster and more accurate than GAs on some problems.
  • It is a traditional way of applying MAs. For local search, you also can apply it after initialisation, after crossover, after mutation.
When we apply for one algorithm, meme is not only local search, but maybe no meme(GA), maybe some other local search.

Note: Different memes yield different performances, designing the right meme is important

Multimeme memetic algorithms

Now meme is not only just local search!
  • Introduce memetic material for each individuals
  • A meme encodes how to apply an operator(which one to apply, max number of iterations, acceptance criteria), when to apply, where to apply, how frequent to apply.
  • Meme of each operator can be combined under a memeplex

MMA features

  • Memes represent instructions for self-improvement, specify set of rules, programs, heuristics, strategies, behaviors, etc.
  • Interaction between memes and genes are not direct, mediated by individual
  • Memes can evolve, change by means of non-traditional genetic transformations and metrics

Mutating memes during evolution

You can mutate memes during evolution by innovation rate.
  • Innovation rate (IR) is in the range of [0,1], which is the probability of mutating a meme
  • If the random number is less than IR, it will mutate the meme.
  • For example, for a MAX-SAT problem. IR is 0.5 and now it is ( 1 0 0 0 1+ HC2). Then we random a number, the number is 0.3 < 0.5, so we mutate it. It might be ( 1 0 0 0 1 + HC0)
  • if IR = 0, no innovation. If an allele is not introduced in the initial generation, it will not be reintroduced again.
  • if IR = 1, everything will be mutated. all different strategies implied by the available M memes might be equally used

Simple Inheriting Mechanism(SIM)


For example:
For a MAX-SAT problem:
(1 0 | 0 0 1 + HC1 HS1 L2) f =2
(1 1 | 0 1 1 + HC0 HS4 L1) f =1
“|” means the crossover point
Because the second one fitness value is lower, so we apply its memeplex. (1 1 0 0 1 + HC0 HS4 L1)
(1 0 0 1 1 + HC0 HS4 L1)

评论

发表评论

此博客中的热门博文

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