Наближені алгоритми розв'язання задачі про багатовимірний ранець

Б. И. Юхименко, Н. П. Волкова

Анотація



Робота присвячена створенню комбінаторних алгоритмів розв'язання багатовимірної задачі про ранці. Показана актуальність проблеми. Дан невеликий історичний аналіз досліджень і публікацій комбінаторних алгоритмів дискретної оптимізації. Звернуто увагу на складність обчислень при вирішенні такого роду завдань. Припущено використовувати наближені алгоритми. В роботі наведені три способи отримання наближених рішень, розроблених на ідеях жадібного алгоритму, генетичного алгоритму мурашиної колонії, а також деякого комбінованого підходу. Сутність алгоритмів полягає в тому, що конкретизація компонент вектора рішень слідує сформованої пріоритетної черзі. Відповідно до неї присвоюється значення <<1>> поки це допустимо. Отримана послідовність залежить від використаної ідеї. Значення цільової функції (рекорд) отриманого рішення є основою відсіювання варіантів при його поліпшенні. Саме поліпшення здійснюється через подвійний підхід комбінаторних алгоритмів. Наведено числовий приклад.

Ключові слова


комбінаторні методи, наближене рішення, багатовимірна задача про ранці, жадібний алгоритм, мурашина колонія, рекорд, відсіювання

Повний текст:

PDF

Посилання

  • Поки немає зовнішніх посилань.