poster

Landscape Properties of the 0-1 Knapsack Problem

Authors:

GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1343 - 1344

https://doi.org/10.1145/2739482.2764688

Published: 11 July 2015 Publication History

Get Access

Abstract

This paper studies two landscapes of different instances of the 0-1 knapsack problem. The instances are generated randomly from varied weight distributions. We show that the variation of the weights can be used to guide the selection of the most suitable local search operator for a given instance.

References

[1]

K. Alyahya and J. E. Rowe. Local optima and weight distribution in the number partitioning problem. In PPSN XIII, volume 8672, pages 862--871. 2014.

Crossref

Google Scholar

[2]

J. Gottlieb. On the feasibility problem of penalty-based evolutionary algorithms for knapsack problems. In Applications of Evolutionary Computing, volume 2037, pages 50--59. 2001.

Digital Library

Google Scholar

[3]

Z. Michalewicz and J. Arabas. Genetic algorithms for the 0/1 knapsack problem. In Methodologies for Intelligent Systems, volume 869, pages 134--143. 1994.

Digital Library

Google Scholar

[4]

D. Pisinger. Where are the hard knapsack problems? Comput. Oper. Res., 32(9):2271--2284, 2005.

Digital Library

Google Scholar

[5]

P. F. Stadler. Fitness landscapes. In Biological Evolution and Statistical Physics, volume 585, pages 183--204. 2002.

Crossref

Google Scholar

Index Terms

Landscape Properties of the 0-1 Knapsack Problem
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Advanced fitness landscape analysis and the performance of memetic algorithms
Special issue on magnetic algorithms

Memetic algorithms (MAs) have demonstrated very effective in combinatorial optimization. This paper offers explanations as to why this is so by investigating the performance of MAs in terms of efficiency and effectiveness. A special class of MAs is used ...
Low-Budget Exploratory Landscape Analysis on Multiple Peaks Models
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

When selecting the best suited algorithm for an unknown optimization problem, it is useful to possess some a priori knowledge of the problem at hand. In the context of single-objective, continuous optimization problems such knowledge can be retrieved by ...
Solving the 0-1 Quadratic Knapsack Problem with a competitive Quantum Inspired Evolutionary Algorithm

Quadratic Knapsack Problem (QKP) extends the canonical simple Knapsack Problem where the value obtained by selecting a subset of objects is a function dependent not only on the value corresponding to individual objects selected but also on their pair-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1568 pages

ISBN:9781450334884

DOI:10.1145/2739482

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2015

Check for updates

Author Tags

Qualifiers

Poster

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
125
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Advanced fitness landscape analysis and the performance of memetic algorithms

Low-Budget Exploratory Landscape Analysis on Multiple Peaks Models

Solving the 0-1 Quadratic Knapsack Problem with a competitive Quantum Inspired Evolutionary Algorithm