Abstract
In this paper, we introduce knapsack problem formulations, discuss their time complexity and propose their representation and solution based on the instance size. First, deterministic methods are briefly summarized. They can be applied to small-size tasks with a single constraint. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. The problem representations and parameter settings for a genetic algorithm and simulated annealing frameworks are shown.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Goldberg, D.E.: The Design of Innovation (Genetic Algorithms and Evolutionary Computation). Kluwer Academic Publishers, Dordrecht (2002)
Gulina, I., Matousek, R.: Efficient nearest neighbor searching in RRTs. In: Matousek, R. (ed.) Proceedings of 22nd International Conference on Soft Computing, MENDEL 2016 (2016)
Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and Its Variations. Kluwer Academic Publishers, Dordrecht (2002)
Klapka, J., Dvořák, P., Popela, P.: Optimisation Methods. VUTIUM, Brno (2001). (in Czech)
Matousek, R., Popela, P.: Stochastic quadratic assignment problem: EV and EO reformulations solved by HC12. In: Proceedings of 20th International Conference on Soft Computing, MENDEL 2014. Brno University of Technology, VUT Press, Brno (2014)
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd edn. Springer, Heidelberg (1996)
Michalewicz, Z., Fogel, D.B.: How to Solve It: Modern Heuristics. Springer, Berlin (2002)
Reeves, C.R.: Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications, Oxford (1993)
Šeda, M., Šeda, P.: A Minimisation of network covering services in a threshold distance. In: Matoušek, R. (ed.) Mendel 2015. Recent Advances in Soft Computing, vol. 378, pp. 159–169. Springer, Berlin (2015)
Wolpert, D.H., McReady, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1, 67–82 (1997)
Zelinka, I., Snášel, V., Abraham, A. (eds.): Handbook of Optimization. From Classical to Modern Approach. Springer, Berlin (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Šeda, M., Šeda, P. (2019). Stochastic Heuristics for Knapsack Problems. In: Matoušek, R. (eds) Recent Advances in Soft Computing . MENDEL 2017. Advances in Intelligent Systems and Computing, vol 837. Springer, Cham. https://doi.org/10.1007/978-3-319-97888-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-97888-8_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-97887-1
Online ISBN: 978-3-319-97888-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)