DEVELOPMENT OF A GENETIC ALGORITHM FOR FINDING APPROXIMATE SOLUTIONS TO THE CONTACT NUMBER PROBLEM

Abstract

The contact number problem is one of the pressing issues in combinatorial optimisation and discrete geometry, which has important theoretical and practical significance. The article determines the relevance of this problem and justifies the need to apply approximate computational methods for its study in Euclidean spaces of arbitrary dimension. In addition, the geometric formulation of the problem is closely related to the analysis of the mutual arrangement of vectors and angular constraints between them, and therefore the article analyses the representation of the contact number problem through α-admissible systems of vectors and establishes a connection between these systems and configurations of tangent spheres.

The limitations of classical (traditional) analytical methods necessitate the search for alternative approaches to solving the given problem. The article proves the possibility and effectiveness of using ε-close systems of vectors with integer coordinates to find approximate solutions. Modern widespread evolutionary methods allow for the effective exploration of large spaces of admissible configurations. The article proposes a genetic algorithm in which the criterion of optimality is the minimisation of the maximum cosine of the angle between the vectors of the system. In this case, the computational implementation of the proposed approach in practical application is of considerable importance. In addition, the article investigates the software implementation of the algorithm and the basic mechanisms of population evolution, in particular reproduction, mutation, extinction, and evolutionary leaps.

Moreover, the effectiveness of the method is confirmed by the results of numerous experiments. This article presents the results of computational experiments for low- and medium-dimensional spaces and shows the possibility of generalising the approach for a wide class of combinatorial optimisation problems. It seems that further development of the topic is related to improving the performance and analytical capabilities of the algorithm. Therefore, the article outlines prospects for further research, in particular the use of parallel computing, analysis of population structure, and means of visualising results.