MikeChen's Blog

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) Mem

Day 4 Outline Evolutionary Algorithms Genetic Algorithms Basic Components of Generic GAs Representation Initialisation Fitness evaluation Mate Selection Crossover Mutation Replacement Termination criteria Evolutionary Algorithms GA simulated natural evolution of individual structures at the genetic level using the idea of survival of the fittest via processes of selection, mutation, and reproduction(recombination) An individual(chromosome) represents a candidate solution for the problem at hand A collection of individuals currently “alive”, called population is evolved from one generation to another depending on the fitness of individuals in a given environment Last generation will contain the final solution EAs –Features Avoid converging to local optima Use exploration of the search space and exploitation of promising areas Reproduction focuses attention on high fitness individuals, thus exploiting (exploitation) the available fitness informatio

Day 3 Outline Performance Analysis/Comparison of Algorithms Move Acceptance Nature of components Stochastic vs non-stochastic basic vs threshold Nature of parameter setting static move acceptance dynamic move acceptance adaptive move acceptance Parameter tuning vs Parameter control Performance analysis Can we say A is much better than B and C? No. Though for instance 1 the average, standard deviation, median and minimum of algorithm A are all best. If we have more instance, now a bit stronger conclusion can be made. But if you want to fully convince people, you should make experiments in all instance. Well, you will definitely not doing these things, Different classification of move acceptance For different classification of move acceptance, we can classify them from two categories. From nature of components , it has non-stochastic and stochastic move acceptance. In non-stochastic, there is non-stochastic basic and threshold . From nature of p

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

Day1 Outline Benchmark function optimisation Components of heuristic search Representation Evaluation Neighbourhoods Basic Hill Climbing/Local Search Methods Strengths and weaknesses of hill climbing Benchmark function optimisation Benchmark function: The function, which can be used to test performance of any optimization approach and the related problem. Why to use benchmark functions for optimisation? Benchmark functions servers as a testbed for performance comparison of heuristic optimisation algorithms The global minimum should be known The function should be easily computed The function is recognised to have certain characteristics(e.g. separable vs. non-separable) Classification of benchmark functions Continuity(Differentiability): Discontinuous vs continuous Dimensionality Modality: Unimodal vs Multimodal with few local minima vs Multimodal with exponential number of local minima Separability Explanation: 1. What do you mean by modality ? mo

File Stream header file: < fstream> ofstream //output file stream, write things into file ifstream //input file stream, read things to the buffer fstream //read and write the opening file Opening the file void open ( const char * filename, ios_base::openmode mode = ios_base::in | ios_base::out ); open() is a little bit different from normal file open, it has more parameters: mode : ios::in: read ios::out: write ios::ate: initial position at the end of the file ios::app: all output will be added (appended) to the end of the file. In other words you cannot write anywhere else in the file but at the end ios::trunc: if the file is already exists, then delete the file ios::binary: binary way According to different use, you can use different mode by “|” symbol. Write to a file Note: remember to using namespace std and close the file stream Read from a file What we read is the file we create before