A new genetic algorithm encoding for coalition structure generation problems. (English) Zbl 07346006
Summary: Genetic algorithms have proved to be a useful improvement heuristic for tackling several combinatorial problems, including the coalition structure generation problem. In this case, the focus lies on selecting the best partition from a discrete set. A relevant issue when designing a Genetic algorithm for coalition structure generation problems is to choose a proper genetic encoding that enables an efficient computational implementation. In this paper, we present a novel hybrid encoding, and we compare its performance against several genetic encoding proposed in the literature. We show that even in difficult instances of the coalition structure generation problem, the proposed approach is a competitive alternative to obtaining good quality solutions in reasonable computing times. Furthermore, we also show that the encoding relevance increases as the number of players increases.
MSC:
| 90C27 | Combinatorial optimization |
| 68W50 | Evolutionary algorithms, genetic algorithms (computational aspects) |
| 91A12 | Cooperative games |
References:
| [1] | Paige, R.; Tarjan, R. E., Three partition refinement algorithms, SIAM Journal on Computing, 16, 6, 973-989 (1987) · Zbl 0654.68072 · doi:10.1137/0216062 |
| [2] | Aumann, R. J.; Dreze, J. H., Cooperative games with coalition structures, International Journal of Game Theory, 3, 4, 217-237 (1974) · Zbl 0313.90074 · doi:10.1007/bf01766876 |
| [3] | Rahwan, T.; Michalak, T. P.; Wooldridge, M.; Jennings, N. R., Coalition structure generation: a survey, Artificial Intelligence, 229, 139-174 (2015) · Zbl 1344.68249 · doi:10.1016/j.artint.2015.08.004 |
| [4] | Guajardo, M.; Rönnqvist, M., Operations research models for coalition structure in collaborative logistics, European Journal of Operational Research, 240, 1, 147-159 (2015) · Zbl 1339.90051 · doi:10.1016/j.ejor.2014.06.015 |
| [5] | Salkin, H. M.; Lin, C. H., Note-aggregations of subsidiary firms for minimal unemployment compensation payments via integer programming, Management Science, 25, 4, 405-408 (1979) · doi:10.1287/mnsc.25.4.405 |
| [6] | Lin, C.-H. M.; Salkin, H. M., An efficient algorithm for the complete set partitioning problem, Discrete Applied Mathematics, 6, 2, 149-156 (1983) · Zbl 0523.90062 · doi:10.1016/0166-218x(83)90069-0 |
| [7] | Basso, F.; Guajardo, M.; Varas, M., Collaborative job scheduling in the wine bottling process, Omega, 91, 102021 (2020) · doi:10.1016/j.omega.2018.12.010 |
| [8] | Basso, F.; D’Amours, S.; Rönnqvist, M.; Weintraub, A., A survey on obstacles and difficulties of practical implementation of horizontal collaboration in logistics, International Transactions in Operational Research, 26, 3, 775-793 (2019) · Zbl 07766329 · doi:10.1111/itor.12577 |
| [9] | Frisk, M.; Göthe-Lundgren, M.; Jörnsten, K.; Rönnqvist, M., Cost allocation in collaborative forest transportation, European Journal of Operational Research, 205, 2, 448-458 (2010) · Zbl 1188.90154 · doi:10.1016/j.ejor.2010.01.015 |
| [10] | Audy, J.-F.; D’Amours, S.; Rousseau, L.-M., Cost allocation in the establishment of a collaborative transportation agreement-an application in the furniture industry, Journal of the Operational Research Society, 62, 6, 960-970 (2011) · doi:10.1057/jors.2010.53 |
| [11] | Bell, E. T., Exponential polynomials, The Annals of Mathematics, 35, 2, 258-277 (1934) · Zbl 0009.21202 · doi:10.2307/1968431 |
| [12] | Rota, G.-C., The number of partitions of a set, The American Mathematical Monthly, 71, 5, 498-504 (1964) · Zbl 0121.01803 · doi:10.1080/00029890.1964.11992270 |
| [13] | Sandholm, T.; Larson, K.; Andersson, M.; Shehory, O.; Tohmé, F., Coalition structure generation with worst case guarantees, Artificial Intelligence, 111, 1-2, 209-238 (1999) · Zbl 0997.91004 · doi:10.1016/s0004-3702(99)00036-3 |
| [14] | Yeh, D. Y., A dynamic programming approach to the complete set partitioning problem, BIT Numerical Mathematics, 26, 4, 467-474 (1986) · Zbl 0622.68047 |
| [15] | Rahwan, T.; Ramchurn, S. D.; Jennings, N. R.; Giovannucci, A., An anytime algorithm for optimal coalition structure generation, Journal of Artificial Intelligence Research, 34, 521-567 (2009) · Zbl 1182.68264 · doi:10.1613/jair.2695 |
| [16] | Michalak, T.; Rahwan, T.; Elkind, E.; Wooldridge, M.; Jennings, N. R., A hybrid exact algorithm for complete set partitioning, Artificial Intelligence, 230, 14-50 (2016) · Zbl 1344.68271 · doi:10.1016/j.artint.2015.09.006 |
| [17] | Yang, T., An evolutionary simulation-optimization approach in solving parallel-machine scheduling problems—a case study, Computers & Industrial Engineering, 56, 3, 1126-1136 (2009) · doi:10.1016/j.cie.2008.09.026 |
| [18] | Holland, J., Adaption in Natural and Artificial Systems (1975), Ann Arbor, MI, USA: The University of Michigan Press, Ann Arbor, MI, USA · Zbl 0317.68006 |
| [19] | Levine, D., A parallel genetic algorithm for the set partitioning problem, Meta-Heuristics, 23-35 (1996), Berlin, Germany: Springer, Berlin, Germany · Zbl 0877.90064 |
| [20] | Chu, P. C.; Beasley, J. E., Constraint handling in genetic algorithms: the set partitioning problem, Journal of Heuristics, 4, 4, 323-357 (1998) · Zbl 1071.90573 · doi:10.1023/a:1008668508685 |
| [21] | Vaziri, S.; Etebari, F.; Vahdani, B., Development and optimization of a horizontal carrier collaboration vehicle routing model with multi-commodity request allocation, Journal of Cleaner Production, 224 (2019) · doi:10.1016/j.jclepro.2019.02.043 |
| [22] | Ronald, S., Robust encodings in genetic algorithms: a survey of encoding issues, Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC’97), IEEE · doi:10.1109/icec.1997.592265 |
| [23] | Schmeidler, D., The nucleolus of a characteristic function game, SIAM Journal on Applied Mathematics, 17, 6, 1163-1170 (1969) · Zbl 0191.49502 · doi:10.1137/0117107 |
| [24] | Arabeyre, J. P.; Fearnley, J.; Steiger, F. C.; Teather, W., The airline crew scheduling problem: a survey, Transportation Science, 3, 2, 140-163 (1969) · doi:10.1287/trsc.3.2.140 |
| [25] | Deveci, M.; Demirel, N. Ç., A survey of the literature on airline crew scheduling, Engineering Applications of Artificial Intelligence, 74, 54-69 (2018) · doi:10.1016/j.engappai.2018.05.008 |
| [26] | Lin, C.-H., Corporate tax structures and a special class of set partitioning problems (1975), Cleveland, OH, USA: Case Western Reserve University, Cleveland, OH, USA, Ph.D. thesis |
| [27] | Horn, H.; Persson, L., The equilibrium ownership of an international oligopoly, Journal of International Economics, 53, 2, 307-333 (2001) · doi:10.1016/s0022-1996(00)00059-3 |
| [28] | Han, Z.; Niyato, D.; Saad, W.; Başar, T.; Hjørungnes, A., Game Theory in Wireless and Communication Networks: Theory, Models, and Applications (2012), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 1260.94002 |
| [29] | Basso, F., Collaborative systems in logistics and transportation (2018), Santiago, Chile: Universidad de Chile, Santiago, Chile, Ph.D. thesis |
| [30] | Bellman, R., Dynamic programming, Science, 153, 3731, 34-37 (1966) · doi:10.1126/science.153.3731.34 |
| [31] | Björklund, A.; Husfeldt, T.; Koivisto, M., Set partitioning via inclusion-exclusion, SIAM Journal on Computing, 39, 2, 546-563 (2009) · Zbl 1215.05056 · doi:10.1137/070683933 |
| [32] | Rahwan, T.; Michalak, T.; Jennings, N.; Wooldridge, M.; McBurney, P., Coalition structure generation in multi-agent systems with positive and negative externalities, Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence |
| [33] | Banerjee, B.; Kraemer, L., Coalition structure generation in multi-agent systems with mixed externalities, Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems |
| [34] | Rahwan, T.; Michalak, T.; Wooldridge, M.; Jennings, N. R., Anytime coalition structure generation in multi-agent systems with positive or negative externalities, Artificial Intelligence, 186, 95-122 (2012) · Zbl 1251.68262 · doi:10.1016/j.artint.2012.03.007 |
| [35] | Ueda, S.; Iwasaki, A.; Conitzer, V.; Ohta, N.; Sakurai, Y.; Yokoo, M., Coalition structure generation in cooperative games with compact representations, Autonomous Agents and Multi-Agent Systems, 32, 4, 503-533 (2018) · doi:10.1007/s10458-018-9386-z |
| [36] | Ieong, S.; Shoham, Y., Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM Conference on Electronic Commerce |
| [37] | Michalak, T.; Marciniak, D.; Szamotulski, M., A logic-based representation for coalitional games with externalities, Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems |
| [38] | Skibski, O.; Michalak, T. P.; Sakurai, Y.; Wooldridge, M.; Yokoo, M., A graphical representation for games in partition function form, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence |
| [39] | Liao, X.; Koshimura, M.; Nomoto, K.; Ueda, S.; Sakurai, Y.; Yokoo, M., Improved WPM encoding for coalition structure generation under MC-nets, Constraints, 24, 1, 25-55 (2019) · Zbl 1468.68203 · doi:10.1007/s10601-018-9295-4 |
| [40] | Zha, A.; Nomoto, K.; Ueda, S.; Koshimura, M.; Sakurai, Y.; Yokoo, M., Coalition structure generation for partition function games utilizing a concise graphical representation, Proceedings of the International Conference on Principles and Practice of Multi-Agent Systems, Springer · Zbl 1503.91022 |
| [41] | Shehory, O.; Kraus, S., Methods for task allocation via agent coalition formation, Artificial Intelligence, 101, 1-2, 165-200 (1998) · Zbl 0908.68032 · doi:10.1016/s0004-3702(98)00045-9 |
| [42] | Sen, S.; Dutta, P. S., Searching for optimal coalition structures, Proceedings of the Fourth International Conference on MultiAgent Systems, 2000, IEEE |
| [43] | Keinänen, H., Simulated annealing for multi-agent coalition formation, Proceedings of the KES International Symposium on Agent and Multi-Agent Systems: Technologies and Applications, Springer |
| [44] | Di Mauro, N.; Basile, T. M.; Ferilli, S.; Esposito, F., Coalition structure generation with grasp, Proceedings of the International Conference on Artificial Intelligence: Methodology, Systems, and Applications, Springer |
| [45] | Dos Santos, D. S.; Bazzan, A. L. C., Distributed clustering for group formation and task allocation in multiagent systems: a swarm intelligence approach, Applied Soft Computing, 12, 8, 2123-2131 (2012) · doi:10.1016/j.asoc.2012.03.016 |
| [46] | Farinelli, A.; Bicego, M.; Ramchurn, S.; Zucchelli, M., C-link: a hierarchical clustering approach to large-scale near-optimal coalition formation, Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence |
| [47] | Yang, X.-S., Nature-Inspired Optimization Algorithms (2014), Amsterdam, Netherlands: Elsevier, Amsterdam, Netherlands · Zbl 1291.90005 |
| [48] | Whitley, D.; Sutton, A. M., Genetic algorithms—a survey of models and methods, Handbook of Natural Computing, 637-671 (2012), Berlin, Germany: Springer, Berlin, Germany |
| [49] | Srinivas, M.; Patnaik, L. M., Genetic algorithms: a survey, Computer, 27, 6, 17-26 (1994) · doi:10.1109/2.294849 |
| [50] | Beasley, D.; Bull, D. R.; Martin, R. R., An Overview of Genetic Algorithms: Part 1, Fundamentals, 56-69 (1993), Cardiff, UK: University of Cardiff, Cardiff, UK |
| [51] | Beasley, D.; Bull, D. R.; Martin, R. R., An Overview of Genetic Algorithms: Part 2, Research Topics, 170-181 (1993), Cardiff, UK: University of Cardiff, Cardiff, UK |
| [52] | Lee, C. K. H., A review of applications of genetic algorithms in operations management, Engineering Applications of Artificial Intelligence, 76, 1-12 (2018) · doi:10.1016/j.engappai.2018.08.011 |
| [53] | Kar, A. K., Bio inspired computing—a review of algorithms and scope of applications, Expert Systems with Applications, 59, 20-32 (2016) · doi:10.1016/j.eswa.2016.04.018 |
| [54] | Venugopal, V.; Narendran, T. T., A genetic algorithm approach to the machine-component grouping problem with multiple objectives, Computers & Industrial Engineering, 22, 4, 469-480 (1992) · doi:10.1016/0360-8352(92)90022-c |
| [55] | Gonçalves, J. F.; Resende, M. G., An evolutionary algorithm for manufacturing cell formation, Computers & Industrial Engineering, 47, 2-3, 247-273 (2004) · doi:10.1016/j.cie.2004.07.003 |
| [56] | Boulif, M., Genetic algorithm encoding representations for graph partitioning problems, Proceedings of the 2010 International Conference on Machine and Web Intelligence (ICMWI), IEEE |
| [57] | Pirlot, M., General local search methods, European Journal of Operational Research, 92, 3, 493-511 (1996) · Zbl 0914.90227 · doi:10.1016/0377-2217(96)00007-0 |
| [58] | Chu, P.; Beasley, J., A Genetic Algorithm for the Set Partitioning Problem (1995), London, UK: Imperial College, London, UK |
| [59] | Boussaïd, I.; Lepagnot, J.; Siarry, P., A survey on optimization metaheuristics, Information Sciences, 237, 82-117 (2013) · Zbl 1321.90156 · doi:10.1016/j.ins.2013.02.041 |
| [60] | Beasley, J. E.; Chu, P. C., A genetic algorithm for the set covering problem, European Journal of Operational Research, 94, 2, 392-404 (1996) · Zbl 0953.90565 · doi:10.1016/0377-2217(95)00159-x |
| [61] | Solar, M.; Parada, V.; Urrutia, R., A parallel genetic algorithm to solve the set-covering problem, Computers & Operations Research, 29, 9, 1221-1235 (2002) · Zbl 0994.90109 · doi:10.1016/s0305-0548(01)00026-0 |
| [62] | Kotecha, K.; Sanghani, G.; Gambhava, N., Genetic algorithm for airline crew scheduling problem using cost-based uniform crossover, Proceedings of the Asian Applied Computing Conference, Springer |
| [63] | Chatterjee, S.; Carrera, C.; Lynch, L. A., Genetic algorithms and traveling salesman problems, European Journal of Operational Research, 93, 3, 490-510 (1996) · Zbl 0912.90276 · doi:10.1016/0377-2217(95)00077-1 |
| [64] | Goldberg, D. E.; Lingle, R., Alleles, loci, and the traveling salesman problem, Proceedings of an International Conference on Genetic Algorithms and Their Applications, Hillsdale, NJ, USA: Lawrence Erlbaum, Hillsdale, NJ, USA · Zbl 0674.90095 |
| [65] | Whitley, L. D.; Starkweather, T.; Fuquay, D., Scheduling problems and traveling salesmen: the genetic edge recombination operator, Proceedings of the 3rd International Conference on Genetic Algorithms |
| [66] | Bean, J. C., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 2, 154-160 (1994) · Zbl 0807.90060 · doi:10.1287/ijoc.6.2.154 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
