Skip to main content
Erschienen in: Pattern Analysis and Applications 2/2023

06.02.2023 | Short Paper

Learning automata-based partitioning algorithms for stochastic grouping problems with non-equal partition sizes

verfasst von: B. John Oommen, Rebekka Olsson Omslandseter, Lei Jiao

Erschienen in: Pattern Analysis and Applications | Ausgabe 2/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

It is very fascinating that the principles of Artificial Intelligence, that were proposed many decades ago, have remained to be the foundations of many of the modern-day techniques, and a brief summary of these principles is given in the paper itself. While this truism is valid for problem solving and game playing, in the context of this paper, we emphasize that it is also pertinent for the so-called partitioning problems. In this paper, we consider the general partitioning problem that has been studied for decades. Unlike the heuristic and search strategies, our attention focuses on learning automata (LA) and reinforcement learning methods, and their powerful ability to solve problems in stochastic environments. These render the latter tools to be applicable to various complex tasks. As we shall explain, LA have been employed for partitioning, and in particular, the paradigm of Object Migration Automata (OMA) has offered state-of-the-art adaptive methods for solving grouping and partitioning problems. However, because the number of possible partitions is combinatorially exponential, and of the NP-hardness of the underlying tasks, the existing state-of-the-art OMA algorithms can only solve problems of equal-sized groups. To resolve this, in this paper, we propose two new OMA variants that can solve both equally and unequally sized partitioning problems. The key here is to provide additional information to the algorithms, and in doing so, to expand the solution space. The first variant, the Greatest Common Divisor OMA (GCD-OMA), relaxes the constraint of having equally sized groups by mapping the actions onto a larger state space, and thus permitting it to solve problems where the group sizes have a GCD that is greater than unity. Subsequently, we propose a second variant named the Partition Size Required OMA (PSR-OMA) to make the algorithm more versatile. The PSR-OMA can handle groups of arbitrary sizes when the group sizes are known a priori. We demonstrate the proposed algorithms’ strength in solving stochastic grouping problems through extensive simulations, even with high noise levels. The GCD-OMA and the PSR-OMA represent the current state-of-the-art when it concerns resolving the extremely complex problem of partitioning and can be used in any of the numerous applications in which the OMA itself has been utilized .

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
The Pursuit OMA (POMA) is another version of the OMA. However, similar to the OMA variant, it suffers from a Deadlock situation. Therefore, the PEOMA is preferred over the POMA [20].
 
2
Preliminary abridged versions of some of the results in this paper were first reported by Omslandseter et al. [13, 14] These papers contained significantly reduced versions of the algorithmic concepts and experimental results presented here.
 
3
We emphasize that the results presented here are merely representative of all the experiments done in the course of this research. More detailed results are included in the thesis of the Second Author xx (Anonymized) and are abridged here in the interest of space and brevity.
 
4
“Noise” is the proportion of queries presented to the automaton that do not belong together in \(\varDelta ^*\).
 
5
The experimental results concerning the TPEOMA are currently being compiled for a separate publication, because it details a scheme in which one can create the partitioning with both real and “artificial” data, which is a fascinating concept.
 
6
We emphasize that hyper-tuning of the \(\kappa\) and \(\tau\) parameter could have yielded even better results than those presented in this paper.
 
Literatur
1.
Zurück zum Zitat Berend D, Tassa T (2010) Improved bounds on bell numbers and on moments of sums of random variables. Probab Math Stat 30(2):185–205MathSciNetMATH Berend D, Tassa T (2010) Improved bounds on bell numbers and on moments of sums of random variables. Probab Math Stat 30(2):185–205MathSciNetMATH
2.
Zurück zum Zitat Ekaba Bisong O, John Oommen B (2020) Optimizing self-organizing lists-on-lists using transitivity and pursuit-enhanced object partitioning. Artif Intell Appl Innov 583:227–240 Ekaba Bisong O, John Oommen B (2020) Optimizing self-organizing lists-on-lists using transitivity and pursuit-enhanced object partitioning. Artif Intell Appl Innov 583:227–240
3.
Zurück zum Zitat Fayyoumi E, Oommen B (2009) “Achieving microaggregation for secure statistical databases using fixed-structure partitioning-based learning automata,” IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics: a publication of the IEEE Systems, Man and Cybernetics Society, 39:1192–205 Fayyoumi E, Oommen B (2009) “Achieving microaggregation for secure statistical databases using fixed-structure partitioning-based learning automata,” IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics: a publication of the IEEE Systems, Man and Cybernetics Society, 39:1192–205
4.
Zurück zum Zitat Gale W, Das S, Yu CT (1990) Improvements to an algorithm for equipartitioning. IEEE Trans Comput 39(5):706–710CrossRef Gale W, Das S, Yu CT (1990) Improvements to an algorithm for equipartitioning. IEEE Trans Comput 39(5):706–710CrossRef
5.
Zurück zum Zitat Glimsdal S, Granmo O-C (2014) “A novel bayesian network based scheme for finding the optimal solution to stochastic online equi-partitioning problems,” In: 2014 13th international conference on machine learning and applications,pp 594–599 Glimsdal S, Granmo O-C (2014) “A novel bayesian network based scheme for finding the optimal solution to stochastic online equi-partitioning problems,” In: 2014 13th international conference on machine learning and applications,pp 594–599
6.
Zurück zum Zitat Hacibeyoglu M, Tongur V, Alaykiran K (2014) “Solving the bi-dimensional two-way number partitioning problem with heuristic algorithms,” In: 2014 IEEE 8th international conference on application of information and communication technologies (AICT),pp 1–5 Hacibeyoglu M, Tongur V, Alaykiran K (2014) “Solving the bi-dimensional two-way number partitioning problem with heuristic algorithms,” In: 2014 IEEE 8th international conference on application of information and communication technologies (AICT),pp 1–5
7.
Zurück zum Zitat Jobava A (2015) “Intelligent traffic-aware consolidation of virtual machines in a data center”, master’s thesis, university of oslo, department of informatics, Oslo Jobava A (2015) “Intelligent traffic-aware consolidation of virtual machines in a data center”, master’s thesis, university of oslo, department of informatics, Oslo
9.
Zurück zum Zitat Korf RE (1995) “From approximate to optimal solutions: a case study of number partitioning,” in IJCAI Korf RE (1995) “From approximate to optimal solutions: a case study of number partitioning,” in IJCAI
11.
Zurück zum Zitat Kratica J, Kojic J, Savic A (2014) Two metaheuristic approaches for solving multidimensional two-way number partitioning problem. Comput Oper Res 46:59–68MathSciNetCrossRefMATH Kratica J, Kojic J, Savic A (2014) Two metaheuristic approaches for solving multidimensional two-way number partitioning problem. Comput Oper Res 46:59–68MathSciNetCrossRefMATH
12.
Zurück zum Zitat Omslandseter RO (2020) Learning automata-based object partitioning with pre-specified cardinalities. Master’s thesis, University of Agder, Department of Information and Communication Technology, Grimstad, Norway Omslandseter RO (2020) Learning automata-based object partitioning with pre-specified cardinalities. Master’s thesis, University of Agder, Department of Information and Communication Technology, Grimstad, Norway
13.
Zurück zum Zitat Omslandseter RO, Jiao L, Oommen BJ (2021) “A learning-automata based solution for non-equal partitioning: partitions with common GCD Sizes,” in advances and trends in artificial intelligence. from theory to practice, ser. Lecture Notes in Computer Science, H. Fujita, A. Selamat, J. C.-W. Lin, and M. Ali, Eds. Springer International Publishing, pp 227–239 Omslandseter RO, Jiao L, Oommen BJ (2021) “A learning-automata based solution for non-equal partitioning: partitions with common GCD Sizes,” in advances and trends in artificial intelligence. from theory to practice, ser. Lecture Notes in Computer Science, H. Fujita, A. Selamat, J. C.-W. Lin, and M. Ali, Eds. Springer International Publishing, pp 227–239
14.
Zurück zum Zitat Omslandseter RO, Jiao L, Oommen BJ (2021) “Object migration automata for non-equal partitioning problems with known partition sizes,” in artificial intelligence applications and innovations, ser. ifip advances in information and communication technology, I. Maglogiannis, J. Macintyre, and L. Iliadis, Eds. Springer International Publishing, pp 129–142 Omslandseter RO, Jiao L, Oommen BJ (2021) “Object migration automata for non-equal partitioning problems with known partition sizes,” in artificial intelligence applications and innovations, ser. ifip advances in information and communication technology, I. Maglogiannis, J. Macintyre, and L. Iliadis, Eds. Springer International Publishing, pp 129–142
15.
Zurück zum Zitat Omslandseter RO, Jiao L, Liu Y, Oommen BJ (2022) User Grouping and Power Allocation in NOMA Systems: A Novel Semi-supervised Reinforcement Learning-based Solution,’’ in Pattern Analysis and Applications. Springer, London, pp 1–17 Omslandseter RO, Jiao L, Liu Y, Oommen BJ (2022) User Grouping and Power Allocation in NOMA Systems: A Novel Semi-supervised Reinforcement Learning-based Solution,’’ in Pattern Analysis and Applications. Springer, London, pp 1–17
16.
Zurück zum Zitat John Oommen B, Ma DCY (1992) Stochastic automata solutions to the object partitioning problem. Comput J 35:A105–A120 John Oommen B, Ma DCY (1992) Stochastic automata solutions to the object partitioning problem. Comput J 35:A105–A120
17.
Zurück zum Zitat John Oommen B, Zgierski J (1993) A learning automaton solution to breaking substitution ciphers. IEEE Trans Pattern Anal Mach Intell 15:185–192CrossRef John Oommen B, Zgierski J (1993) A learning automaton solution to breaking substitution ciphers. IEEE Trans Pattern Anal Mach Intell 15:185–192CrossRef
18.
Zurück zum Zitat John Oommen B, Fothergill C (1993) Fast learning automaton-based image examination and retrieval. Comput J 36(6):542–553CrossRef John Oommen B, Fothergill C (1993) Fast learning automaton-based image examination and retrieval. Comput J 36(6):542–553CrossRef
19.
Zurück zum Zitat Pop PC, Matei O (2013) A genetic algorithm approach for the multidimensional two-way number partitioning problem, in Learning and Intelligent Optimization, ser. Lecture Notes in Computer Science, G. Nicosia and P. Pardalos, Eds Berlin, Heidelberg, Springer, pp 81–86 Pop PC, Matei O (2013) A genetic algorithm approach for the multidimensional two-way number partitioning problem, in Learning and Intelligent Optimization, ser. Lecture Notes in Computer Science, G. Nicosia and P. Pardalos, Eds Berlin, Heidelberg, Springer, pp 81–86
20.
Zurück zum Zitat Shirvani A (2018) Novel solutions and applications of the object partitioning problem, Ph.D. thesis Carleton University, School of Computer Science, Ottawa, Canada Shirvani A (2018) Novel solutions and applications of the object partitioning problem, Ph.D. thesis Carleton University, School of Computer Science, Ottawa, Canada
21.
Zurück zum Zitat Tasi L-H (1995) The modified differencing method for the set partitioning problem with cardinality constraints. Dis Appl Math 63(2):175–180MathSciNetCrossRefMATH Tasi L-H (1995) The modified differencing method for the set partitioning problem with cardinality constraints. Dis Appl Math 63(2):175–180MathSciNetCrossRefMATH
22.
Zurück zum Zitat (1974) Tsetlin, Automation theory and modeling of biological systems. Academic Press, google-Books-ID: 3wLEDm__bnsC (1974) Tsetlin, Automation theory and modeling of biological systems. Academic Press, google-Books-ID: 3wLEDm__bnsC
23.
Zurück zum Zitat Ung FM (2015) Towards efficient and cost-effective live migrations of virtual machines,Master’s thesis, Carleton University, Ottawa Ung FM (2015) Towards efficient and cost-effective live migrations of virtual machines,Master’s thesis, Carleton University, Ottawa
24.
Zurück zum Zitat Yazidi A, Granmo O-C, John Oommen B (2012) Service selection in stochastic environments: a learning-automaton based solution. Appl Intell 36(3):617–637CrossRef Yazidi A, Granmo O-C, John Oommen B (2012) Service selection in stochastic environments: a learning-automaton based solution. Appl Intell 36(3):617–637CrossRef
Metadaten
Titel
Learning automata-based partitioning algorithms for stochastic grouping problems with non-equal partition sizes
verfasst von
B. John Oommen
Rebekka Olsson Omslandseter
Lei Jiao
Publikationsdatum
06.02.2023
Verlag
Springer London
Erschienen in
Pattern Analysis and Applications / Ausgabe 2/2023
Print ISSN: 1433-7541
Elektronische ISSN: 1433-755X
DOI
https://doi.org/10.1007/s10044-023-01131-5

Weitere Artikel der Ausgabe 2/2023

Pattern Analysis and Applications 2/2023 Zur Ausgabe

Premium Partner