×

zbMATH — the first resource for mathematics

A genetic algorithm for optimization of a relational knapsack problem with respect to a description logic knowledge base. (English) Zbl 1421.90174
Hu, Bo (ed.) et al., Operations research proceedings 2010. Selected papers of the annual international conference of the German Operations Research Society (GOR), Universität der Bundeswehr München, September 1–3, 2010. Berlin: Springer. Oper. Res. Proc., 201-206 (2011).
Summary: We present an approach that integrates a description logic based knowledge representation system into the optimization process. A description logic defines concepts, roles (properties) and object instances for relational data, which enables one to reason about complex objects and their relations. We outline a relational knapsack problem, which utilizes the knowledge base during optimization. Furthermore, we present a genetic algorithm to outline an approximate algorithm for a heuristic solution.
For the entire collection see [Zbl 1220.90005].
MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
Software:
Pellet; Jena; swrl
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2nd edition, 2008. · Zbl 1058.68107
[2] P. C. Chu and J. E. Beasley. A Genetic Algorithm for the Multidimensional Knapsack Problem. J. Heuristics, 4(1): 63-86, 1998. · Zbl 0913.90218
[3] José E. Gallardo, Carlos Cotta and Antonio J. Fernández. Solving the multidimensional knapsack problem using an evolutionary algorithm hybridized with branch and bound. In José Mira and José R. Álvarez, editors, IWINAC (2), volume 3562 of Lecture Notes in Computer Science, pages 21-30. Springer, 2005.
[4] Raymond R. Hill and Chaitr Hiremath. Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems. International Journal of Operational Research, 1(1-2): 145-159, 2005. · Zbl 1100.90058
[5] Ian Horrocks, Peter F. Patel-Schneider, Harold Boley, Said Tabet, Benjamin Grosof, and Mike Dean. SWRL: A Semantic Web Rule Language Combining OWL and RuleML, May 2004.
[6] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer Berlin Heidelberg, 2 2004. · Zbl 1103.90003
[7] Brian McBride. Jena: A Semantic Web Toolkit. IEEE Internet Computing, 6(6): 55-59, 2002.
[8] Boris Motik, Ulrike Sattler, and Rudi Studer. Query Answering for OWL-DL with rules. J. Web Sem., 3(1): 41-60, 2005.
[9] David Pisinger. The quadratic knapsack problem – a survey. Discrete Applied Mathematics, 155(5): 623-648, 2007. · Zbl 1143.90028
[10] Tugba Saraç and Aydin Sipahioglu. A genetic algorithm for the quadratic multiple knapsack problem. In Francesco Mele, Giuliana Ramella, Silvia Santillo, and Francesco Ventriglia, editors, BVAI, volume 4729 of Lecture Notes in Computer Science, pages 490-498. Springer, 2007.
[11] Nigel Shadbolt, Tim Berners-Lee, and Wendy Hall. The Semantic Web Revisited. IEEE Intelligent Systems, 21(3): 96-101, 2006. · Zbl 1126.68003
[12] Evren Sirin, Bijan Parsia, Bernardo Cuenca Grau, Aditya Kalyanpur, and Yarden Katz. Pellet: A practical OWL-DL reasoner. J. Web Sem., 5(2): 51-53, 2007.
[13] W3C. Resource Description Framework (RDF): Concepts and Abstract Syntax, Februrary 2004.
[14] W3C. OWL 2 Web Ontology Language, October 2009.
[15] Du Wei and Li Shuzhuo.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.