MATHEMATICAL MODELS AND INFORMATION TECHNOLOGIES OF LAYOUT SYNTHESIS OF SPHERICAL CONFIGURATIONS

Abstract

The concept of layout synthesis of optimal configurations is introduced in the article. Under the tasks of layout synthesis it means the formation of a set of geometric objects in such a mutual arrangement that would satisfy the given relations (constraints, properties) and would deliver an extremum to a certain quality criterion. One problem of finding the optimal configuration of geometric objects of spherical shape is considered. The problem is to find such an arrangement of set of spheres without their mutual overlaps, so that their spherical shell is minimal. For this problem, several equivalent mathematical models are given. Since the problem is NP-complete, methods are considered for solving it, based on the search and improvement of local minima.

To find one local minimum, it can be used any method of non-linear optimization. In this paper it is used an open system IPOPT for solving optimization problems, using the methods of internal points to search for a local minimum.

To search for a local minima, there are used several approaches. The first of them is based on the application of the  space expansion method. This method consists in finding a local minimum for a problem with constant radii, and then at the resulting point, a transition to a model with variable radii is made, in which the initial values of the radii of the circles change in a certain range in a random way. After that, the local search is performed again, and so many times. This approach allows for a directed search of a local minima, improving the solution.

The second approach is based on a multiple search for a local minima using a genetic algorithm.

The third approach is an interactive and uses human intuition. After obtaining some solution, the result is displayed in a graphical editor and the researcher can change the mutual position of objects, after which one of the automatic methods is applied. It is necessary that initial position objects do not be feasible. 

When solving a problem, it is necessary to ensure interaction between different stages of the solution. To do this, it is need to repeatedly convert geometric information from one form to another. Information technologies for the transformation of geometric information in the process of solving the problem are proposed.

An example of a numerical solution is given.