Shih-Huan Hsu
ABSTRACT
This paper proposes a new evolutionary algorithm, called DSMGA-II, to efficiently solve optimization problems via exploiting problem substructures. The proposed algorithm adopts pairwise linkage detection and stores the information in the form of dependency structure matrix (DSM). A new linkage model, called the incremental linkage set, is then constructed by using the DSM. Inspired by the idea of optimal mixing, the restricted mixing and the back mixing are proposed. The former aims at efficient exploration under certain constrains. The latter aims at exploitation by refining the DSM so as to reduce unnecessary evaluations. Experimental results show that DSMGA-II outperforms LT-GOMEA and hBOA in terms of number of function evaluations on the concatenated/folded/cyclic trap problems, NK-landscape problems with various degrees of overlapping, 2D Ising spin-glass problems, and MAX-SAT. The investigation of performance comparison with P3 is also included.
- E. Álvarez-Miranda, I. Ljubić, and P. Mutzel. The maximum weight connected subgraph problem. Springer, 2013.Google Scholar
Cross Ref
- P. A. Bosman and D. Thierens. The roles of local search, model building and optimal mixing in evolutionary algorithms from a bbo perspective. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011), pages 663--670, 2011. Google ScholarDigital Library
- P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012), pages 585--592, 2012. Google ScholarDigital Library
- P. A. Bosman and D. Thierens. More concise and robust linkage learning by filtering and combining linkage hierarchies. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2013), pages 359--366, 2013. Google ScholarDigital Library
- W.-M. Chen, C.-Y. Hsu, T.-L. Yu, and W.-C. Chien. Effects of discrete hill climbing on model building forestimation of distribution algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2013), pages 367--374, 2013. Google ScholarDigital Library
- K. Deb and D. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of Mathematics and Artificial Intelligence, 10(4):385--408, 1994.Google ScholarCross Ref
- A. Galluccio and M. Loebl. A Theory of Pfaffian Orientations I: Perfect Matchings and Permanents. The Electronic Journal of Combinatorics, 1997.Google Scholar
- A. Galluccio and M. Loebl. A theory of pfaffian orientations. ii. t-joins, k-cuts, and duality of enumeration. Electronic Journal of Combinatorics, 6(1):7, 1999.Google ScholarCross Ref
- D.E.Goldberg,K.Deb,andJ.H.Clark.Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1991.Google Scholar
- D. E. Goldberg, K. Deb, and J. Horn. Massive multimodality, deception, and genetic algorithms. Urbana, 51:61801, 1992.Google Scholar
- B. W. Goldman and W. F. Punch. Parameter-less population pyramid. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2014), pages 785--792, 2014. Google ScholarDigital Library
- J. H. Holland. Adaptation in Natural and Artificial Systems. MIT Press, 1992. Google ScholarCross Ref
- S. Kullback and R. A. Leibler. On information and sufficiency. The Annals of Mathematical Statistics, 22(1):79--86, 1951.Google ScholarCross Ref
- H. F. Lee and D. R. Dooly. Decomposition algorithms for the maximum-weight connected graph problem. Naval Research Logistics (NRL 1998), 45(8):817--837, 1998.Google Scholar
- N. H. Luong, H. La Poutré, and P. A. Bosman. Multi-objective gene-pool optimal mixing evolutionary algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2014), pages 357--364, 2014. Google ScholarDigital Library
- M. Munetomo and D. E. Goldberg. Identifying linkage groups by nonlinearity/non-monotonicity detection. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), 1:433--440, 1999.Google Scholar
- M. Pelikan. Hierarchical Bayesian optimization algorithm. Springer Berlin Heidelberg, 2005.Google ScholarCross Ref
- M. Pelikan, M. W. Hauschild, and D. Thierens. Pairwise and problem-specific distance metrics in the linkage tree genetic algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011), pages 1005--1012, 2011. Google ScholarDigital Library
- M. Pelikan, M. Pelikan, D. E. Goldberg, and D. E. Goldberg. Hierarchical boa solves ising spin glasses and maxsat. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2003), pages 1271--1282, 2003. Google ScholarDigital Library
- M. Pelikan, K. Sastry, D. E. Goldberg, M. V. Butz, and M. Hauschild. Performance of evolutionary algorithms on nk landscapes with nearest neighbor interactions and tunable overlap. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2009), pages 851--858, 2009. Google ScholarDigital Library
- K. L. Sadowski, P. A. Bosman, and D. Thierens. On the usefulness of linkage processing for solving max-sat. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2013), pages 853--860, 2013. Google ScholarDigital Library
- D. Thierens. The linkage tree genetic algorithm. Proceedings of Parallel Problem Solving from Nature: Part I (PPSN 2010), pages 264--273, 2010. Google ScholarDigital Library
- D. Thierens and P. A. Bosman. Optimal mixing evolutionary algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2011), pages 617--624, 2011. Google ScholarDigital Library
- D. Thierens and P. A. Bosman. Hierarchical problem solving with the linkage tree genetic algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2013), pages877--884, 2013. Google ScholarDigital Library
- D. Thierens and D. E. Goldberg. Mixing in genetic algorithms. Urbana, 51:61801, 1993.Google Scholar
- S.-M. Wang, Y.-F. Tung, and T.-L. Yu. Investigation on efficiency of optimal mixing on various linkage sets. Evolutionary Computation (CEC 2014), pages 2475--2482, 2014.Google ScholarCross Ref
- T.Yu,D.E.Goldberg,K.Sastry,C.F.Lima,and M. Pelikan. Dependency structure matrix, genetic algorithms, and effective recombination. Evolutionary Computation, 17(4):595--626, 2009. Google ScholarDigital Library
- T.-L. Yu and D. E. Goldberg. Conquering hierarchical difficulty by explicit chunking: Substructural chromosome compression. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006), pages 1385--1392, 2006. Google ScholarDigital Library
- T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-p. Chen. A genetic algorithm design inspired by organizational theory: Pilot study of a dependency structure matrix driven genetic. Proceedings of Artificial Neural Networks in Engineering (ANNIE 2003), pages 327--332, 2003.Google ScholarCross Ref
- T.-L. Yu, K. Sastry, and D. E. Goldberg. Linkage learning, overlapping building blocks, and systematic strategy for scalable recombination. Proceedings of the Genetic and Evolutionary Computation Conference(GECCO 2005), pages 1217--1224, 2005. Google ScholarDigital Library
- T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing for entropy-based model building in discrete estimation of distribution algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007), pages 601--608, 2007. Google ScholarDigital Library
Index Terms
- Optimization by Pairwise Linkage Detection, Incremental Linkage Set, and Restricted / Back Mixing: DSMGA-II
Recommendations
Comparative mixing for DSMGA-II
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation ConferenceDependency Structure Matrix Genetic Algorithm-II (DSMGA-II) is a recently proposed optimization method that builds the linkage model on the base of the Dependency Structure Matrix (DSM). This model is used during the Optimal Mixing (OM) operators, such ...
Two-edge graphical linkage model for DSMGA-II
GECCO '17: Proceedings of the Genetic and Evolutionary Computation ConferenceDSMGA-II, a model-based genetic algorithm, is capable of solving optimization problems via exploiting sub-structures of the problem. In terms of number of function evaluations (NFE), DSMGA-II has shown superior optimization ability to LT-GOMEA and hBOA ...
A linkage-learning niching in estimation of distribution algorithm
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationThis work proposes a linkage-learning niching method that improves the capability of estimation of distribution algorithms (EDAs) on reducing spurious linkages which increase problems difficulty. Concatenated parity function (CPF), a class of allelic ...
Comments