Report

Linkage Tree Genetic Algorithm Wei-Ming Chen Papers The Linkage Tree Genetic Algorithm, Dirk Thierens, 2010 Pairwise and Problem-Speciﬁc Distance Metrics in the Linkage Tree Genetic Algorithm, Martin Pelikan, Mark W. Hauschild, Dirk Thierens, 2011 The Linkage Tree Genetic Algorithm Dirk Thierens GECCO 2010 GA mechanism Evaluation Selection Initialization Replacement Until termination Mutation Crossover Introduction Construct the variables to a tree Hierarchical Clustering Assign each variable to a single cluster. Repeat until one cluster left Join two nearest clusters ci and cj into cij Clustering Entropy H : Distance D : Genetic Algorithm Choose a pair of chromosome Crossover mask : apart chromosome into two subsets Replacement : If one of the offspring is better than both of the parents Example (1/4) Example (2/4) Example (3/4) Example (4/4) Algorithm Initial : Create initial population of size N Repeat Build the linkage tree For every pair while the tree is not fully traversed traversed a step and set crossover mask do crossover do replacement if necessary Result Test problems Trap function NK landscape Result The problems are solved in polynomial time Similar with ECGA and DSMGA Pairwise and Problem-Speciﬁc Distance Metrics in the Linkage Tree Genetic Algorithm Martin Pelikan, Mark W. Hauschild, Dirk Thierens GECCO 2011 local search To improves the quality of the solution In first iteration, do local search before proceeding with the ﬁrst iteration Based on single-bit neighborhoods choose the step which improves the quality of the solution most Until find the local optimum Speed up Original : Pairwise matrix : Problem-Speciﬁc Metric decomposable problem composed of m subproblems prefer decompositions which minimize the sizes of subsets If two variables in the same subset, the distance of them is 1 Result Test problems Trap-5, Trap-6, Trap 7 NK landscape 2D spin glass Result The problems are solved in polynomial time Trap functions : almost same NK landscape : Original < Pairwise < Problem 2D spin glass : Original < Problem < Pairwise Conclusion LTGA : Small population size Solve all the problems in low-order polynomial time Future work : Problem-speciﬁc metrics Construct all the variables to only one tree ? Change the minimum mask size ?