Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
A hybrid algorithm class for combinatorial optimization problems solving is considered. The class is named the H-method and built on the basis of synthesis of the accelerated probabilistic simulation algorithm (G-algorithm) and the modified discrete downhill simplex method. Algorithms for segment an...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/127656 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| _version_ | 1856543349487435776 |
|---|---|
| author | Hulianytskyi, L. F. Gobov, D. A. |
| author_facet | Hulianytskyi, L. F. Gobov, D. A. |
| author_sort | Hulianytskyi, L. F. |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2018-04-11T11:12:54Z |
| description | A hybrid algorithm class for combinatorial optimization problems solving is considered. The class is named the H-method and built on the basis of synthesis of the accelerated probabilistic simulation algorithm (G-algorithm) and the modified discrete downhill simplex method. Algorithms for segment and half-interval building in the permutation space are proposed and proved. They are used for quadratic assignment problem solving. The computational experimental results are given, which demonstrate a high efficiency of the developed algorithms in comparison with some known algorithms. |
| first_indexed | 2025-07-17T10:23:44Z |
| format | Article |
| id | journaliasakpiua-article-127656 |
| institution | System research and information technologies |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:23:44Z |
| publishDate | 2018 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| spelling | journaliasakpiua-article-1276562018-04-11T11:12:54Z Application of the H-method to solving combinatorial optimization problems on permutations Использование Н-метода для решения задач комбинаторной оптимизации на перестановках Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках Hulianytskyi, L. F. Gobov, D. A. A hybrid algorithm class for combinatorial optimization problems solving is considered. The class is named the H-method and built on the basis of synthesis of the accelerated probabilistic simulation algorithm (G-algorithm) and the modified discrete downhill simplex method. Algorithms for segment and half-interval building in the permutation space are proposed and proved. They are used for quadratic assignment problem solving. The computational experimental results are given, which demonstrate a high efficiency of the developed algorithms in comparison with some known algorithms. Предложен класс гибридных алгоритмов решения задач комбинаторной оптимизации (H-метод), построенный на основе синтеза алгоритма ускоренного вероятностного моделирования (G-алгоритм) и модифицированного дискретного метода деформированных многогранников. Обоснованы алгоритмы построения отрезков и полуинтервалов в пространстве перестановок для решения квадратичной задачи о назначениях. Приведены результаты вычислительного эксперимента, которые демонстрируют эффективность разработанных алгоритмов в сравнении с некоторыми известными. Запропоновано клас гібридних алгоритмів розв’язання задач комбінаторної оптимізації (H-метод), який побудовано на основі синтезу алгоритму прискореного ймовірнісного моделювання (G-алгоритм) та модифікованого дискретного методу деформованих багатогранників. Обґрунтовано алгоритми побудови відрізків та напівінтервалів у просторі перестановок для розв’язання квадратичної задачі про призначення. Наведено результати обчислювального експерименту, що демонструють ефективність розроблених алгоритмів у порівнянні з деякими відомими. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-04-02 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/127656 System research and information technologies; No. 2 (2007); 74-86 Системные исследования и информационные технологии; № 2 (2007); 74-86 Системні дослідження та інформаційні технології; № 2 (2007); 74-86 2308-8893 1681-6048 uk http://journal.iasa.kpi.ua/article/view/127656/122423 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Hulianytskyi, L. F. Gobov, D. A. Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_alt | Application of the H-method to solving combinatorial optimization problems on permutations Использование Н-метода для решения задач комбинаторной оптимизации на перестановках |
| title_full | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_fullStr | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_full_unstemmed | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_short | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_sort | застосування н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| url | http://journal.iasa.kpi.ua/article/view/127656 |
| work_keys_str_mv | AT hulianytskyilf applicationofthehmethodtosolvingcombinatorialoptimizationproblemsonpermutations AT gobovda applicationofthehmethodtosolvingcombinatorialoptimizationproblemsonpermutations AT hulianytskyilf ispolʹzovanienmetodadlârešeniâzadačkombinatornojoptimizaciinaperestanovkah AT gobovda ispolʹzovanienmetodadlârešeniâzadačkombinatornojoptimizaciinaperestanovkah AT hulianytskyilf zastosuvannânmetodudlârozvâzannâzadačkombínatornoíoptimízacíínaperestanovkah AT gobovda zastosuvannânmetodudlârozvâzannâzadačkombínatornoíoptimízacíínaperestanovkah |