Metaheuristic Algorithms For The Search Of Splitting Systems

An (m,t) splitting system is a pair of (X, B) where m and t are integers and0 < t≤m,X is a ?nite set of points and |X| = m, B is a collection of subsets ofX called blocks, for every and |Y | = t,there exists a block B ? B suchthat B∩Y = [t/2].If every block B ? B has the size of [m/2], it is a uniformsplitting system.In this paper we present some metaheuristic algorithms for the search of uni-form splitting systems with t = 3.The main algorithms involved during the searchprocess are Tabu Search (TS) and Simulated Annealing (SA),we also apply GreedyRandomized Adaptive Search Procedure (GRASP) to construct the initial solutionso as to reduce the search time.This paper gives detailed pseudo codes.We have programmed for the algorithms,and have done some experimentsto verify the validities of these algorithms.The analysis for the results are alsogiven.At the end of the paper,we give the searching results,the minimum number ofblocks for uniform splitting systems with t = 3.Compared with the results gottenby constructing method on some references,the results of this paper have someimprovements.This means metaheuristic algorithms are very e?ective in solvingproblems of this kind.