[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2463372.2463476acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

The influence of linkage-learning in the linkage-tree GA when solving multidimensional knapsack problems

Published: 06 July 2013 Publication History

Abstract

Linkage Learning (LL) is an important issue concerning the development of more effective genetic algorithms (GA). It is from the identification of strongly dependent variables that crossover can be effective and an efficient search can be implemented. In the last decade many algorithms have confirmed the beneficial influence of LL when solving nearly decomposable problems. As it is a well-known fact from the no free-lunch theorem, LL can not be the best tool for all optimization problems, therefore, methods to identify those problems which could be efficiently solved by LL have become necessary. This paper investigates that nearly-decomposable problems present characteristic linkage-trees, therefore, those trees can be used as reference to infer whether or not some black-box optimization problem is a good candidate to be solved by LL. In this context, we consider the linkage-tree model from the Linkage-Tree GA (LTGA) and use the silhouette measure to expose some problems' characteristics. The silhouette fingerprints (SF) are defined for overlapping deceptive trap functions and compared with the SFs obtained for Multidimensional Knapsack Problems (MKP). The comparison allowed us to conclude that MKPs do not present evident linkages. This result was confirmed by experiments comparing the performance of the LTGA and the Randomized LTGA, in which both algorithms had very similar results.

References

[1]
A. Barron, J. Rissanen, and B. Yu. The Minimum Description Length Principle in Coding and Modeling. Information Theory, IEEE Transactions on, 44(6):2743--2760, oct 1998.
[2]
P. Chu and J. Beasley. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4:63--86, 1998.
[3]
T. Cover, J. Thomas, J. Wiley, et al. Elements of information theory, volume 6. Wiley Online Library, 1991.
[4]
A. Fréville. The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1--21, 2004.
[5]
D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, January 1989.
[6]
B. Goldman and D. Tauritz. Linkage tree genetic algorithms: variants and analysis. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference, pages 625--632. ACM, 2012.
[7]
J. Gottlieb. On the Feasibility Problem of Penalty-Based Evolutionary Algorithms for Knapsack Problems. In E. Boers, editor, Applications of Evolutionary Computing, volume 2037 of Lecture Notes in Computer Science, pages 50--59. Springer Berlin Heidelberg, 2001.
[8]
I. Gronau and S. Moran. Optimal implementations of UPGMA and other common clustering algorithms. Information Processing Letters, 104(6):205--210, 2007.
[9]
G. Harik. Learning gene linkage to efficiently solve problems of bounded difficulty using genetic algorithms. PhD thesis, The University of Michigan, 1997.
[10]
J. H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 1975.
[11]
A. Kraskov, H. Stogbauer, R. Andrzejak, and P. Grassberger. Hierarchical clustering using mutual information. EPL (Europhysics Letters), 70(2), 2005.
[12]
A. Kulik and H. Shachnai. There is no EPTAS for two-dimensional knapsack. Information Processing Letters, 110(16):707--710, 2010.
[13]
S. Martello and P. Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., New York, NY, USA, 1990.
[14]
J. P. Martins, A. H. M. Soares, D. Vargas, and A. C. B. Delbem. Multi-objective Phylogenetic Algorithm: Solving Multi-objective Decomposable Deceptive Problems. In R. Takahashi, K. Deb, E. Wanner, and S. Greco, editors, Evolutionary Multi-Criterion Optimization, volume 6576 of Lecture Notes in Computer Science, pages 285--297. Springer Berlin/Heidelberg, 2011.
[15]
M. Pelikan. Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms. Studies in Fuzziness and Soft Computing. Springer, 1 edition, March 2005.
[16]
M. Pelikan. NK landscapes, problem difficulty, and hybrid evolutionary algorithms. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, GECCO 10, pages 665--672, New York, NY, USA, 2010. ACM.
[17]
M. Pelikan, M. W. Hauschild, and D. Thierens. Pairwise and problem-specific distance metrics in the linkage tree genetic algorithm. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO '11, pages 1005--1012, New York, NY, USA, 2011. ACM.
[18]
P. J. Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20(0):53--65, 1987.
[19]
K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. PhD thesis, University of Illinois at Urbana-Champaign, 2001.
[20]
H. Simon. The sciences of the artificial. the MIT Press, 1996.
[21]
J. Tavares, F. Pereira, and E. Costa. The Role of Representation on the Multidimensional Knapsack Problem by means of Fitness Landscape Analysis. In Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, pages 2307--2314, 0-0 2006.
[22]
J. Tavares, F. Pereira, and E. Costa. Multidimensional Knapsack Problem: A Fitness Landscape Analysis. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 38(3):604--616, june 2008.
[23]
D. Thierens. The Linkage Tree Genetic Algorithm. In Parallel Problem Solving from Nature, PPSN XI, volume 6238 of Lecture Notes in Computer Science, pages 264--273. Springer Berlin Heidelberg, 2010.
[24]
D. Thierens and P. A. Bosman. Optimal mixing evolutionary algorithms. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO '11, pages 617--624, New York, NY, USA, 2011. ACM.
[25]
V. Veloso de Melo, D. Vargas, and M. Crocomo. Phylogenetic Differential Evolution. International Journal of Natural Computing Research (IJNCR), 2(1):21--38, 2011.
[26]
D. Wolpert and W. Macready. No free lunch theorems for optimization. Evolutionary Computation, IEEE Transactions on, 1(1):67--82, 2002.

Cited By

View all
  • (2020)A randomized heuristic repair for the multidimensional knapsack problemOptimization Letters10.1007/s11590-020-01611-115:2(337-355)Online publication date: 29-Jun-2020
  • (2016)Pairwise independence and its impact on Estimation of Distribution AlgorithmsSwarm and Evolutionary Computation10.1016/j.swevo.2015.10.00127(80-96)Online publication date: Apr-2016
  • (2015)A differential evolution algorithm with variable neighborhood search for multidimensional knapsack problem2015 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2015.7257236(2797-2804)Online publication date: May-2015
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation
July 2013
1672 pages
ISBN:9781450319638
DOI:10.1145/2463372
  • Editor:
  • Christian Blum,
  • General Chair:
  • Enrique Alba
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. linkage-learning
  2. linkage-tree ga
  3. silhouette measure

Qualifiers

  • Research-article

Conference

GECCO '13
Sponsor:
GECCO '13: Genetic and Evolutionary Computation Conference
July 6 - 10, 2013
Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2020)A randomized heuristic repair for the multidimensional knapsack problemOptimization Letters10.1007/s11590-020-01611-115:2(337-355)Online publication date: 29-Jun-2020
  • (2016)Pairwise independence and its impact on Estimation of Distribution AlgorithmsSwarm and Evolutionary Computation10.1016/j.swevo.2015.10.00127(80-96)Online publication date: Apr-2016
  • (2015)A differential evolution algorithm with variable neighborhood search for multidimensional knapsack problem2015 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2015.7257236(2797-2804)Online publication date: May-2015
  • (2014)Multimodality and the linkage-learning difficulty of additively separable functionsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598281(365-372)Online publication date: 12-Jul-2014
  • (2014)On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problemNeurocomputing10.1016/j.neucom.2014.04.069146:C(17-29)Online publication date: 15-Oct-2014

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media