V. M. Kurejchik, B. K. Lebedev, O. B. Lebedev O. B. Lebedev

One of widely demanded problems of integer programming is the problem of the partitioning to be considered in a combinatory direction of the theory of graphs. Existing algorithms of partitioning are divided into two classes: constructive and iterative [1]. The first class is characterized by relative speed, but during too time poor quality of the decision. A lack is frequent hit in a local optimum («a local hole»). Recently for the decision of various "difficult" problems the ways based on application of methods of an artificial intellegence are even more often used. At the heart of the majority of these algorithms the ideas borrowed in the nature, and also base postulates of universality and the fundamental nature, inherent in self-organizing of natural systems lay. One of new directions of such methods are multi-agents methods of intellectual optimization which are based on modeling of collective intelli-gence. Let it is given graph G (X, U), where Х - set of tops, |X| = n, U - set of edges. It is necessary to break set X into two nonempty and not crossed subsets X1 and X2, X1X2 =X, X1 X2 =, Xi . On formed knots (blocks, components) are imposed restrictions: |X1 | = n1, |X2 | = n2, n1 + n2 = n. Criterion of optimization is number of communications F between X1 and X2. The purpose of optimization is minimization of criterion F. In this work, the partitioning problem is represented in the form of adaptive system, on the basis of integration of evolutionary and ant approaches to decision search. New technologies, principles and mechanisms of the decision of a problem partitioning based on modeling of processes of adaptive behavior of ant colony are offered. The new approach, algorithms and techniques of control by process of evolutionary search of the decision on the basis of mechanisms of collective alternative adaptation are described. Search of the decision of a problem of partitioning carries out ant algorithm on the full graph of decisions R (X, E), where E - set of all edges of the full graph connecting set of tops X. Modeling of behavior of ants in a partitioning problem is connected with distribution pheromone on edges of graph R. Search of decisions is the iterative process. Each iteration t includes three stages. At the first stage the ant finds the decision, at the second stage postpones pheromone, at the third stage is carried out pheromone evaporations. In the work, it is used cyclic (ant-cycle) method of ant systems. In this case phero-mone are postponed by the agent on edges after full formation of the decision. For the decision of problems of the big dimension and reception of better decisions the combined approach consisting in adaptive control by process of partitioning by means of ant algorithm is offered. The general scheme of multistage process of redistribution of tops between knots consists in the following. On each step to knots X1 and X2, it is allocated for redistribution of a subset of tops X*1X1 and X*2  X2. The residual set of tops unites in one top x01 =X1 \X*1, x02 =X2 \X*2. In new statement, the initial problem of partitioning of set X is considered as a problem of distribution of set X * = X*1X*2 between knots X1 and X2, and is primary in knot X1 the top x01 is included, and the top x02 is included in knot X2. The problem in new statement dares by means of the partitioning considered above ant algorithm. For representation of the initial formulation of a problem in the form of the adaptive system based on ideas of collective behavior, following problems are solved. Formation of models of environment and objects of adaptation; formation of the local purposes of objects of adaptation and the global purpose of collective; working out of alternative conditions of object of adaptation, structure of the trained automatic machine of adaptation (AA) and mechanisms of transitions АА; working out of a technique of development of operating signals of encouragement or punishment in the course of work of adaptive algorithm; working out of the general structure of process of adaptive search. For realization of the mechanism of adaptation to each object xiX the adaptation automatic machine ai, modeling behavior of object of adaptation in the environment is compared. Automatic machine adaptation is made by self-training in the course of its functioning. Hybrid inherently the algorithm of partitioning has been realized in language С ++. Experimental study was spent on the computer of type IBM PC/AT. Testing was made on benchmarks 19s, PrimGA1, PrimGA2. The results obtained at use of the hybrid approach, on the average on 2 % it is better than the results received by purely ant algorithm of partitioning. In comparison with existing algorithms improvement of results on 5 % is reached. On the average program start is provided with findings of the decision differing from optimum less than on 0,5 %. The considered algorithm can be used as basic procedure at a multilevel paradigm of partitioning of the graph or the hypergraph on n parts.