Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Extremal Optimisation with a Penalty Approach for the Multidimensional Knapsack Problem
verfasst von : Pedro Gómez-Meneses, Marcus Randall
Erschienen in: Simulated Evolution and Learning
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The extremal optimisation (EO) meta-heuristic is a recent form of search that is suitable for combinatorial optimisation problems. EO has been applied to problems such as graph partitioning, spin glass, and graph colouring. However, only a relatively small amount of work has been done on other combinatorial problems particularly those having constraints. This paper examines the issue of satisfying constraints with a penalty approach using the multidimensional knapsack problem. An EO model is presented which finds solutions through the analysis of the number of overloaded constraints. This approach allows the solution state move between feasible and infeasible spaces. The results show that the new algorithm is able to obtain optimal results for small problems and finds competitive solutions for large problems.