Grasp and Path-Relinking for Coalition Structure Generation

• Autorzy: Di Mauro N. , Basile T.M.A. , Ferilli S. , Esposito F.

Identyfikatory

DOI

10.3233/FI-2014-971

• Języki publikacji: EN

Abstrakty

EN

In Artificial Intelligence with Coalition Structure Generation (CSG) one refers to those cooperative complex problems that require to find an optimal partition (maximizing a social welfare) of a set of entities involved in a system. The solution of the CSG problem finds applications in many fields such as Machine Learning (set covering machines, clustering), Data Mining (decision tree, discretization), Graph Theory, Natural Language Processing (aggregation), Semantic Web (service composition), and Bioinformatics. The problem of finding the optimal coalition structure is NPcomplete. In this paper we present a greedy adaptive search procedure (GRASP) with path-relinking to efficiently search the space of coalition structures. Experiments and comparisons to other algorithms prove the validity of the proposed method in solving this hard combinatorial problem.

Słowa kluczowe

EN

coalition structure generation; stochastic-local-search; GRASP procedure; path-relinking

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 3
• Strony: 251--277
• Opis fizyczny: Bibliogr. 29 poz., rys., wykr.

Twórcy

autor

Di Mauro N.

• Department of Computer Science University of Bari, Italy

autor

Basile T.M.A.

• Department of Computer Science University of Bari, Italy

autor

Ferilli S.

• Department of Computer Science University of Bari, Italy

autor

Esposito F.

• Department of Computer Science University of Bari, Italy

Bibliografia

• [1] Apt, K. R., Witzel, A.: A Generic Approach To Coalition Formation, International Game Theory Review, 11(3), 2009, 347–367.
• [2] Barzilay, R., Lapata, M.: Aggregation via set partitioning for natural language generation, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, Association for Computational Linguistics, 2006.
• [3] Di Mauro, N., Basile, T. M. A., Ferilli, S., Esposito, F.: Coalition Structure Generation with GRASP, Proceedings of the 14th International Conference on Artificial Intelligence: Methodology, Systems, and Applications (D. Dicheva, D. Dochev, Eds.), 6304, Springer, 2010.
• [4] Feo, T. A., Resende, M. G. C.: Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 1995, 109–133.
• [5] Fern, X. Z., Brodley, C. E.: Solving cluster ensemble problems by bipartite graph partitioning, Proceedings of the 21st International Conference on Machine Learning (C. E. Brodley, Ed.), 2004.
• [6] Garey,M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1990.
• [7] Glover, F.: Tabu search and adaptive memory programing Advances, applications and challenges, Interfaces in Computer Science and Operations Research, Kluwer, 1996.
• [8] Glover, F., Laguna,M.: Tabu Search, Kluwer, 1997.
• [9] Hoos, H., St¨utzle, T.: Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., 2004.
• [10] Kahan, J. P., Rapoport, A.: Theories of Coalition Formation, Lawrence Erlbaum Associates Publisher, 1984.
• [11] Kein¨anen, H.: Simulated Annealing for Multi-agent Coalition Formation, Proceedings of 3rd International KES Symposium on Agents and Multi-agent Systems Technologies and Applications, Springer, 2009.
• [12] Kirkpatrick, S., Gelatt Jr., C. D., Vecchi, M. P.: Optimization by Simulated Annealing, Science, 220(4598), 1983, 671–680.
• [13] Laguna,M., Mart, R.: GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS Journal on Computing, 11, 1999, 44–52.
• [14] Larson, K. S., Sandholm, T. W.: Anytime coalition structure generation: an average case study, Proceedings of the third annual conference on Autonomous Agents, ACM, 1999.
• [15] Matatov, N., Rokach, L., Maimon, O.: Privacy-preserving data mining: A feature set partitioning approach, Information Sciences, 180, 2010, 2696–2720.
• [16] Milne, S. C.: Restricted Growth Functions, Rank Row Matchings of Partitions Lattices, and q-Stirling Numbers, Advances in Mathemathics, 43, 1982, 173–196.
• [17] Mockus, J., Eddy, E., Mockus, A., Mockus, L., Reklaitis, G. V.: Bayesian Heuristic Approach to Discrete and Global Optimization, Kluwer Academic Publishers, 1997.
• [18] Myllymaki, P., Tirri, H.: Constructing Computationally Efficient Bayesian Models via Unsupervised Clustering, Probabilistic Reasoning and Bayesian Belief Networks (A.Gammerman, Ed.), AlfredWaller Publishers, 1995.
• [19] Rahwan, T., Jennings, N. R.: An improved dynamic programming algorithm for coalition structure generation, Prooceedings of 7th International Conference on Autonomous Agents and Multiagent Systems, 2008.
• [20] Rahwan, T., Ramchurn, S. D., Jennings, N. R., Giovannucci, A.: An anytime algorithm for optimal coalition structure generation, Journal of Artificial Intelligence Research, 34(1), 2009, 521–567.
• [21] Resende, M. G., Ribeiro, C. C., Glover, F., Mart, R.: Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications, in: Handbook of Metaheuristics (F. S. Hillier, M. Gendreau, J.-Y. Potvin, Eds.), vol. 146 of International Series in Operations Research & Management Science, Springer US, 2010, 87–107.
• [22] Resende,M. G. C., Ribeiro, C.: GRASP with path-relinking: Recent advances and applications, Metaheuristics: Progress as Real Problem Solvers, Springer-Verlag, 2005.
• [23] Rokach, L.: Decomposition methodology for classification tasks – a meta decomposer framework, Pattern Analysis and Applications, 9(2), 2006, 257–271.
• [24] Rokach, L.,Maimon, O.: Theory and Application of Attribute Decomposition, Proceedings of the First IEEE International Conference on Data Mining, IEEE Computer Society Press, 2001.
• [25] Sandholm, T., Larson, K., Andersson, M., Shehory, O., Tohm´e, F.: Coalition structure generation with worst case guarantees, Artificial Intelligence, 111(1-2), 1999, 209–238.
• [26] Sen, S., Dutta, P. S.: Searching for Optimal Coalition Structures, Proceedings of the 4th International Conference on Multi-Agent Systems, IEEE Computer Society, 2000.
• [27] Strehl, A., Ghosh, J.: Cluster ensembles - a knowledge reuse framework for combining multiple partitions, Journal of Machine Learning Research, 3, 2003, 583–617.
• [28] Verykios, V. S., Bertino, E., Fovino, I. N., Provenza, L. P., Saygin, Y., Theodoridis, Y.: State-of-the-art in privacy preserving data mining, Newsletter ACM SIGMOD Record, 33, 2004, 50–57.
• [29] Yeh, D. Y.: A dynamic programming approach to the complete set partitioning problem, BIT, 26(4), 1986, 467–474.