Sökning: onr:"swepub:oai:DiVA.org:liu-174078" >
Hybrid Dynamic Prog...
Hybrid Dynamic Programming for Simultaneous Coalition Structure Generation and Assignment
-
- Präntare, Fredrik, 1990- (författare)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska fakulteten,ReaL
-
- Heintz, Fredrik, 1975- (författare)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska fakulteten
-
(creator_code:org_t)
- 2021-02-14
- 2021
- Engelska.
-
Ingår i: PRIMA 2020: Principles and Practice of Multi-Agent Systems. - Cham : Springer. - 9783030693220 - 9783030693213 ; , s. 19-33
- Relaterad länk:
-
https://liu.diva-por... (primary) (Raw object)
-
visa fler...
-
http://liu.diva-port...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We present, analyze and benchmark two algorithms for simultaneous coalition structure generation and assignment: one based entirely on dynamic programming, and one anytime hybrid approach that uses branch-and-bound together with dynamic programming. To evaluate the algorithms’ performance, we benchmark them against both CPLEX (an industry-grade solver) and the state-of-the-art using difficult randomized data sets of varying distribution and complexity. Our results show that our hybrid algorithm greatly outperforms CPLEX, pure dynamic programming and the current state-of-the-art in all of our benchmarks. For example, when solving one of the most difficult problem sets, our hybrid approach finds optimum in roughly 0.1% of the time that the current best method needs, and it generates 98% efficient interim solutions in milliseconds in all of our anytime benchmarks; a considerable improvement over what previous methods can achieve.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas