Автореферати та дисертаційні роботи

Permanent URI for this collectionhttps://ena.lpnu.ua/handle/ntb/2995

Browse

Subject: search.filters.subject.decomposition

Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Математичне та програмне забезпечення для розв’язування задачі комівояжера великих розмірностей
    (Національний університет "Львівська політехніка", 2011) Кутельмах, Роман Корнелійович
    The Traveling Salesman Problem (TSP) is extensively applied in transportation systems, automated design, testing and manufacturing of integrated circuits, printed circuit boards, laser cutting of plastics and metals, as well as in protein structure research, continuous line drawings, X-ray crystallography and a number of other fields. A significant feature of such problems is their large-scale complexity amounting to over a million points for many of them. The TSP is viewed as an intractable combinatorial problem (discrete optimization), referred to the class of NP-hard problems due to its factorial computational complexity. The computational complexity of existing effective methods is not lower than O(N2), which makes them inappropriate for large scale and very large scale problems. Therefore there is a need for developing methods and an application software system for solving such problems. In order to achieve high computing performance, appropriate for complicated large-scale problems, this dissertation presents a set of specialized decomposition methods adapted to specific types of input data structures and an application software system that enables solving real TSPs, as well as modelling, exploring and integrating new methods. The following tasks were done: the different types of TSP such as uniform and clustered were classified, high quality heuristic methods were chosen as basic, methods of finding the initial solution as well as it’s optimization for large scale TSP with their adaptation to the structure of input data were developed. Software for solving large scale TSP was developed. Experimental investigations of the developed methods were done as well as the comparative analysis of the results and estimated their effectiveness in terms of quality and solving time. Existing methods has been improved as well as new decomposition methods for finding initial solution and solution optimization have been developed. The problem is solved in several steps: partitioning of the input set of points into smaller subsets (≈ 500-2000 points), finding partial high-quality solutions for them within small time frames, merging them into the whole initial solution, and further solution optimization. Developed methods have computational complexity very close to linear. According to the experimental results, the proposed decomposition approaches provide substantial reduction in the run time in comparison with the currently best heuristic Lin-Kernighan-Helsgaun algorithm. Quality loss is negligible. Problem instances up to 107 points were investigated. Developed mathematical methods provided the possibility to develop special software system “VRP Modeler” for large scale TSP solving and experimental research, in which with the purpose of organization of effective calculations it is computer-integrated in the unique complex known existing and developed decomposition methods. Software is developed by author independently in Microsoft Visual Studio 2008 IDE on C++ programming language with the use of methods of the object-oriented programming. Dissertation job performances were applied in the educational process of software department of the Lviv National Polytechnic University and also in the “AR-TRANS” and “SEA Electronics” companies. Developed software system "VRP Modeler" for solving large scale TSP, which is a special software that allows to solve real travelling salesman problems, model, explore and integrate new methods. The methods and tools for clustering of input data, building macroroute, finding the initial solution and its optimization can be applied to a wide range of applications, which used the TSP and those close to it: VLSI optimization, systems and networks on a crystal (SoC and NoC), optimizations of production processes, vehicle routing problems, continuous line drawings et al.В диссертационной работе рассмотрена задача коммивояжера больших размерностей, широко применяемая в транспортных системах, автоматизированном проектировании, тестировании и изготовлении интегрированных схем, производстве печатных плат и других отраслях. Развиты существующие и разработаны новые декомпозиционные методы, в которых задача решается за несколько этапов: разбиение входного множества точек на подмножества ограниченой размерности (≈ 500-2000 точек), для которых получаются высококачественные частичные решения с небольшими временными затратами; сшивания частичных решений в начальное решение, и его улучшение разработанными методами локальной оптимизации. Разработана прикладная программная система "VRP Modeler" для решения ЗК больших размерностей, которая является специальным программным обеспечением, что позволяет решать реальные задачи коммивояжера, их моделировать, исследовать и интегрировать новые методы. Разработанные методы и программные средства кластеризации входных данных, построения макромаршрута, нахождения начального решения и его оптимизации можно применять для широкого круга прикладных задач, где используется ЗК и близкие к ней.У дисертаційній роботі розглянуто задачу комівояжера великих розмірностей, яка має широке прикладне застосування в транспортних системах, автоматизованому проектуванні, тестуванні та виготовленні інтегрованих схем, виробництві друкованих плат та інших галузях. Розвинуто відомі та розроблено нові декомпозиційні методи, в яких задача розв’язується за декілька етапів: розбиття вхідної множини точок на підмножини обмеженої розмірності (≈ 500-2000 точок), для яких отримуються високоякісні часткові розв’язки з невеликими часовими затратами; зшивання часткових розв’язків у початковий розв’язок, та його покращення розробленими методами оптимізації. Розроблено прикладну програмну систему “VRP Modeler” для розв’язування ЗК великих розмірностей, яка є спеціальним програмним забезпеченням, що дає змогу розв’язувати реальні задачі комівояжера, їх моделювати, досліджувати та інтегрувати нові методи. Розроблені методи та програмні засоби кластеризації вхідних даних, побудови макромаршруту, знаходження початкового розв’язку та його оптимізації можна застосовувати для широкого кола прикладних задач, де використовується ЗК та близькі до неї.
  • No Thumbnail Available
    Item
    Розв’язання задач функціональної компоновки і верифікації при проектуванні конструктивів цифрової апаратури
    (Національний університет "Львівська політехніка", 2010) Білаль Раді А’Ггель Аль-Забі
    В дисертації отримав свій подальший розвиток метод оптимальної (паралельної) редукції стосовно задач функціональної декомпозиції схем і верифікації проектних рішень на етапі проектування конструктивів цифрової (радіоелектронної) апаратури. Особливу увагу приділено шляхам розв’язання центральної з розглянутих задач – встановленню еквівалентності схем. В роботі досліджено два типи моделей для розв’язання задач: графові і теоретико-множинні, що мають ієрархічну структуру, яка дозволяє вибирати необхідний степінь деталізації опису схем, представлених як описом множини елементів, класифікацією яких встановлюється існування необхідних умов еквівалентності схем, так і описом множини ланцюгів, по якому визначається степінь перекриття схем, що дозволило вирішити такі задачі функціональної компоновки, як типізація і покриття схем підсхемами із заданого набору. Для графових моделей схем запропоновано нові алгоритми встановлення ізоморфізму графів і пошуку в графі ізоморфних підграфів на основі формування ізоморфних бінарних дерев редукції графових моделей. Диссертация посвящена разработке методов, моделей и алгоритмов установления эквивалентности схем с целью их использования при решении задач функциональной компоновки и верификации результатов проектирования. Исследованы существующие методы решения задач, включая решение задачи установления изоморфизма графов. Обосновано использование метода оптимальной редукции, имеющего полиномиальную вычислительную сложность, что является существенным ввиду NP-полного характера решаемых задач. Метод оптимальной редукции получил своё дальнейшее развитие применительно к задачам установления изоморфизма графов и функциональной декомпозиции схем; он позволяет, в отличие от других методов, за счёт параллелизма процесса редукции алгоритмически решать задачи типизации и выделения в графе изоморфных подграфов. Усовершенствованы теоретико-множественные и графовые модели элементов и схем, а также впервые предложена и реализована модель схемы в виде множества цепей, каждая из которых описана регламентированным кортежом параметров, что, в отличие от существующих моделей позволяет установить степень перекрытия пары схем. Предложен алгоритм установления изоморфизма простих графов, который, в отличие от существующих, для уменьшенияи нструментальной погрешности метода исследует как изоморфизм пары графов, так и их дополнений, что оказалось эффективным, в том числе, и для регулярних структур. Для установления изоморфизма графов (мультиграфов, сетей) использованы инварианты в виде бинарных деревьев оптимальной редукции, что позволяет свести задачу установления изоморфизма графов к задаче установления изоморфизма их деревьев редукции. Для решения задачи типизации обоснован и предложен алгоритм выделения в графе изоморфных подграфов с весовой функцией на вершинах, значение которой опредиляется предварительной классификацией элементов схем. Приводится формальная постановка задачи установления эквивалентности схем и путие её решения. Исследованы и развиты теоретико-множественные модели схем на основе описаний множества элементов и множестав цепей, каждое из которых имеет несколько уровней, отличающихся детализацией представления элементов и цепей схем на основе типов элементов и типов задействованных контактов элементов. Разработаны и реализованы классификаторы элементов и цепей, позволяющие установить наличие необходимых условий решения поставленных задач и степень взаимного перекрытия двух схем. Разработано и описано информационное обеспечение для решения поставлених задач.In dissertation the method of optimal (parallel) reduction has got the further development applying to the tasks of scheme functional decomposition and verification of project decisions on the stage of digital (radio and electronic) devices construction design. The special attention is paid to ways of decision of central of the examined tasks − setting the scheme equivalence. Two types of tasks decision models are studied in the work: (a) graph and (b) theoretic-and-set which have a hierarchical structure and allow choosing necessary degree of scheme description detalization presented by description of elements set, classification of which is set the existence of necessary terms of scheme equivalence as well as description of chains set by which the degree of scheme covering is determined. This has allowed the decision of the following tasks of functional decomposition: typification and coverage of scheme with subscheme from a given set. For the scheme’s graph models the new algorithms of isomorphousness of graph setting and selection of isomorphous subgraphs in the graph are offered on the base of isomorphous binary trees of graph models reduction forming.