A Learning-Automata Based Solution for Non-equal Partitioning: Partitions with Common GCD Sizes

Abstract

The Object Migration Automata (OMA) has been used as a powerful tool to resolve real-life partitioning problems in random Environments. The virgin OMA has also been enhanced by incorporating the latest strategies in Learning Automata (LA), namely the Pursuit and Transitivity phenomena. However, the single major handicap that it possesses is the fact that the number of objects in each partition must be equal. Obviously, one does not always encounter problems with equally-sized groups (When the true underlying problem has non-equally-sized groups, the OMA reports the best equally-sized solution as the recommended partition.). This paper is the pioneering attempt to relax this constraint. It proposes a novel solution that tackles partitioning problems where the partition sizes can be both equal and/or unequal, but when the cardinalities of the true partitions have a Greatest Common Divisor (GCD). However, on attempting to resolve this less-constrained version, we encounter a few problems that deal with implementing the inter-partition migration of the objects. To mitigate these, we invoke a strategy that has been earlier used in the theory of automata, namely that of mapping the machine’s state space onto a larger space. This paper details how this strategy can be incorporated, and how such problems can be solved. In essence, it presents the design, implementation, and testing of a novel OMA-based method that can be implemented with the OMA itself, and also in all of its existing variants, including those incorporating the Pursuit and Transitivity phenomena. Numerical results demonstrate that the new approach can efficiently solve partitioning problems with partitions that have a common GCD.