O'Reilly logo

Optimization Techniques for Solving Complex Problems by Juan Antonio Gomez, Coromoto Leon, Pedro Asasi, Christian Blum, Enrique Alba

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

images CHAPTER 21

Exact, Metaheuristic, and Hybrid Approaches to Multidimensional Knapsack Problems

J. E. GALLARDO, C. COTTA, and A. J. FERNÁNDEZ

Universidad de Málaga, Spain

21.1 INTRODUCTION

In this chapter we review our recent work on applying hybrid collaborative techniques that integrate branch and bound (B&B) and memetic algorithms (MAs) in order to design effective heuristics for the multidimensional knapsack problem (MKP). To this end, let us recall that branch and bound (B&B) [102] is an exact algorithm for finding optimal solutions to combinatorial problems that works basically by producing convergent lower and upper bounds for the optimal solution using an implicit enumeration scheme. A different approach to optimization is provided by evolutionary algorithms (EAs) [24]. These are powerful heuristics for optimization problems based on principles of natural evolution: namely, adaptation and survival of the fittest. Starting from a population of randomly generated individuals (representing solutions), a process consisting of selection (promising solutions are chosen from the population), reproduction (new solutions are created by combining selected ones), and replacement (some solutions are replaced by new ones) is repeated. A fitness function measuring the quality of the solution is used to guide the process.

A key aspect of EAs is robustness, meaning that they can be deployed ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required