Fragmentary Structures in Discrete Optimization Problems
- PDF / 115,441 Bytes
- 6 Pages / 594 x 792 pts Page_size
- 96 Downloads / 207 Views
FRAGMENTARY STRUCTURES IN DISCRETE OPTIMIZATION PROBLEMS I. V. Kozin,1† N. K. Maksyshko,1‡ and V. A. Perepelitsa1††
UDC 519.87
Abstract. The paper considers a combinatorial object (a fragmentary structure) and investigates the properties of this object. It is shown that a number of discrete optimization problems can be considered as optimization problems on a fragmentary structure. Optimization problem reduces to an unconditional combinatorial optimization problem on a set of permutations. Variants of algorithms to find approximate solutions for optimization problems of fragmentary structure are proposed. Keywords: discrete optimization, fragmentary structure, local algorithm, evolutionary algorithm, ant algorithm. INTRODUCTION For many classes of discrete optimization problems, algorithms of finding exact solution with polynomial labor input are unknown. Therefore, algorithms of finding approximate solutions with low computing complexity are of interest. The simplest algorithms of such type are various versions of greedy algorithms. Whitney [1] was the first to define the concept of greedy algorithm. For matroids, this simple algorithm always leads to optimal problem solution. Greedoids [2] and hereditary systems [3] are an extension of the concept of matroid. In hereditary systems, greedy algorithm not always leads to exact solution of the optimization problem. Generally, the solution that can be obtained by greedy algorithm may be as much as far from the optimal one. However, combining a greedy algorithm with stochastic methods allows obtaining approximate solutions that are rather close to optimal ones for low computing cost. In the present paper, we propose a description of fragmentary structures for which the concept of greedy algorithm is applicable and optimization problems on their basis. We will show that it is possible to represent the set of discrete optimization problems in the form of optimization problems on fragmentary structures. This makes it possible to develop the class of combined algorithms to find approximate solutions of optimization problems with low computing complexity. 1. FRAGMENTARY STRUCTURES AND THEIR PROPERTIES Definition 1. Fragmentary structure ( X , E ) on a finite set X is the set of its subsets E = { E1 , E 2 , K , E n } , where
E i Ì X is such that " E i Î E , E i ¹ Æ $ e Î E i , E i \ {e} Î E . We will call elements from set E feasible fragments. One-element feasible fragments are called elementary fragments. We will call a feasible fragment maximum one if it is not a subset of any of the feasible fragments. It is obvious that an empty set is a feasible fragment. It is possible to represent each fragmentary structure as an acyclic oriented graph whose vertices correspond to feasible fragments, two vertices are connected by an edge if respective feasible fragments differ in one element. Figure 1 shows examples of such graphs. 1
Zaporizhzhya National University, Zaporizhzhya, Ukraine, †[email protected]; ‡[email protected]; [email protected]. Translated from Kibernetika i Sis
Data Loading...
