O(1) delta part computation technique for the quadratic assignment problem
The quadratic assignment problem is rightfully considered to be one of the most challenging problems of combinatorial optimization. Since this problem is NP-hard, the use of heuristic algorithms is the only way to find in a reasonable time a solution that is close to optimal. One of the most effecti...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2015
|
| Назва видання: | Системні дослідження та інформаційні технології |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/116059 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | O(1) delta part computation technique for the quadratic assignment problem / S.V. Podolsky, Yu.M. Zorin // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 112-121 . — Бібліогр.: 8 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-116059 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1160592017-04-19T03:02:24Z O(1) delta part computation technique for the quadratic assignment problem Podolsky, S.V. Zorin, Yu.M. Математичні методи, моделі, проблеми і технології дослідження складних систем The quadratic assignment problem is rightfully considered to be one of the most challenging problems of combinatorial optimization. Since this problem is NP-hard, the use of heuristic algorithms is the only way to find in a reasonable time a solution that is close to optimal. One of the most effective heuristic algorithms is the Robust Tabu Search, which is the basis of many subsequent metaheuristic algorithms. The paper describes a novel approach to scanning the neighborhood of the current solution that allows reducing by half the number of delta values that were required to be computed with complexity O(N) in most of the heuristics for the quadratic assignment problem. Using the correlation between the old and new delta values, obtained in this work, a new formula of complexity O(1) is proposed. The results obtained leads up to 25% performance increase as compared to such well-known algorithms as the Robust Tabu Search and others based on it. The formula obtained in this paper may be successfully applied to other heuristics using a full scan of the solution neighborhood. Квадратична задача про призначення по праву вважається однією із самих складних проблем комбінаторної оптимізації. У зв’язку з цим, знайти її розв’язок, близький до оптимального, за розумний час можна тільки з використанням евристичних алгоритмів. Однією з найбільш ефективних евристик є алгоритм Robust Tabu Search, який лежить в основі багатьох наступних метаэвристических алгоритмів. У роботі описано новий підхід до сканування околиці поточного розв’язку, який дозволяє зменшити наполовину число обчислень дельта-складових, які обчислювалися зі складністю O(N) у більшості метаэвристик, що застосовуються для розв’язку квадратичної задачі про призначення. Дослідження взаємозв’язку між колишніми й новими значеннями дельта-складових, дозволило отримати нову формулу складності O(1) для їхнього обчислення, що приводить до збільшення до 25% швидкодії алгоритму в порівнянні Robust Tabu Search у випадку задач великої розмірності. Формула, отримана в роботі, може бути успішно застосована в інших евритстиках, що використовують повне сканування околиці розв'язку. Квадратичная задача о назначениях по праву считается одной из самых сложных проблем комбинаторной оптимизации. В этой связи, найти ее решение, близкое к оптимальному, за разумное время можно только с использованием эвристических алгоритмов. Одной из наиболее эффективных эвристик является алгоритм Robust Tabu Search, который лежит в основе многих последующих метаэвристических алгоритмов. В работе описан новый подход к сканированию окрестности текущего решения, позволяю- щий уменьшить наполовину число вычислений дельта-составляющих, которые вычислялись со сложностью O(N) в большинстве метаэвристик, применяемых для решения квадратичной задачи о назначениях. Исследование взаимосвязи между прежними и новыми значениями дельта-составляющих, позволило получить новую формулу сложности O(1) для их вычисления, что приводит к увеличению до 25% быстродействия алгоритма по сравнению Robust Tabu Search в случае задач большой размерности. Формула, полученная в работе, может быть успешно применена в других эвристиках, использующих полное сканирование окрестности решения. 2015 Article O(1) delta part computation technique for the quadratic assignment problem / S.V. Podolsky, Yu.M. Zorin // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 112-121 . — Бібліогр.: 8 назв. — англ. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/116059 004.89:004.4 en Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем |
| spellingShingle |
Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем Podolsky, S.V. Zorin, Yu.M. O(1) delta part computation technique for the quadratic assignment problem Системні дослідження та інформаційні технології |
| description |
The quadratic assignment problem is rightfully considered to be one of the most challenging problems of combinatorial optimization. Since this problem is NP-hard, the use of heuristic algorithms is the only way to find in a reasonable time a solution that is close to optimal. One of the most effective heuristic algorithms is the Robust Tabu Search, which is the basis of many subsequent metaheuristic algorithms. The paper describes a novel approach to scanning the neighborhood of the current solution that allows reducing by half the number of delta values that were required to be computed with complexity O(N) in most of the heuristics for the quadratic assignment problem. Using the correlation between the old and new delta values, obtained in this work, a new formula of complexity O(1) is proposed. The results obtained leads up to 25% performance increase as compared to such well-known algorithms as the Robust Tabu Search and others based on it. The formula obtained in this paper may be successfully applied to other heuristics using a full scan of the solution neighborhood. |
| format |
Article |
| author |
Podolsky, S.V. Zorin, Yu.M. |
| author_facet |
Podolsky, S.V. Zorin, Yu.M. |
| author_sort |
Podolsky, S.V. |
| title |
O(1) delta part computation technique for the quadratic assignment problem |
| title_short |
O(1) delta part computation technique for the quadratic assignment problem |
| title_full |
O(1) delta part computation technique for the quadratic assignment problem |
| title_fullStr |
O(1) delta part computation technique for the quadratic assignment problem |
| title_full_unstemmed |
O(1) delta part computation technique for the quadratic assignment problem |
| title_sort |
o(1) delta part computation technique for the quadratic assignment problem |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| publishDate |
2015 |
| topic_facet |
Математичні методи, моделі, проблеми і технології дослідження складних систем |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/116059 |
| citation_txt |
O(1) delta part computation technique for the quadratic assignment problem / S.V. Podolsky, Yu.M. Zorin // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 112-121 . — Бібліогр.: 8 назв. — англ. |
| series |
Системні дослідження та інформаційні технології |
| work_keys_str_mv |
AT podolskysv o1deltapartcomputationtechniqueforthequadraticassignmentproblem AT zorinyum o1deltapartcomputationtechniqueforthequadraticassignmentproblem |
| first_indexed |
2023-10-18T20:26:48Z |
| last_indexed |
2023-10-18T20:26:48Z |
| _version_ |
1796150217048850432 |