Комбинированные алгоритмы решения задачи одномерной упаковки Наумова Ольга Анатольевна

Введение к работе

Актуальность работы. Задача одномерной оптимальной по стоимости упаковки, или задача о ранце, более полувека не оставляет равнодушными алгоритмистов всего мира. Безусловно, в первую очередь подобный интерес обусловлен многообразием практического приложения задачи. Помимо вопросов упаковки в явном виде (оптимальная загрузка судов, вагонов) задача одномерной упаковки применима к целому ряду финансово- экономических задач. Например, планирование инвестиций с максимальной выгодой. В то же время к задаче о ранце успешно сводится ряд задач логистики. Возросла актуальность применения и в технологических процессах — в настоящий момент поиск оптимальной упаковки является основой алгоритмов распределения дискового пространства и размещения элементов на микросхемах.

Специфика исследуемой задачи такова, что все алгоритмы ее решения делятся на два множества — эвристические быстрые алгоритмы и точные алгоритмы. В настоящее время отсутствуют быстрые точные алгоритмы решения для больших размерностей. Поэтому до сих пор актуальна разработка новых алгоритмов, отвечающих жестким требованиям как по точности, так и по временной эффективности.

Что касается комбинированных алгоритмов решения исследуемой задачи, то на данный момент этот подход, пожалуй, является наиболее перспективным способом разработки эффективных алгоритмов, так как сочетает достоинства и учитывает недостатки разработанных ранее алгоритмов.

Помимо практического интереса, высока теоретическая значимость поиска быстрых алгоритмов точного решения задачи упаковки. Это связано с вопросом о совпадении или вложении классов P и NP -сложности задач.

Степень разработанности проблемы. Фундаментальный вклад в исследование и развитие решений задачи о рюкзаке внесли зарубежные и отечественные ученые, среди которых Р. Беллман, Д. Б. Данциг, П. Колесар, Бабат Л.Г., Р.С. Барр, Д.Т. Росс, Корбут А.А., Курейчик В.М, Мухачева Э.А., Норенков И.П., Валеева А.Ф., Сигал И.Х., П. Тот, С. Мартелло, Д. Писингер, Р. Андоров и др.

Большинство известных работ посвящено решению бинарной упаковки. Стремительный рост производительности вычислительных средств и разработка новых методов решений позволили также добиться значительных успехов и для других постановок задачи о ранце. В частности, благодаря развитию теории нейронных сетей и параллельных вычислений сегодня активно исследуется многокритериальная упаковка.

В целом, при решении задачи упаковки, с алгоритмической точки зрения, актуальна, как разработка новых алгоритмов, так и повышение эффективности известных алгоритмов. Касательно методов решения — упор делается на приближенные алгоритмы: эвристические, генетические и их различные комбинации, в том числе и с точными алгоритмами.

Объектом исследования диссертационной работы являются точные алгоритмы решения задачи одномерной неограниченной упаковки, реализующие принцип динамического программирования.

Область исследования. Диссертационная работа выполнена в соответствии с п. 14 «Разработка теоретических основ создания программных систем для новых информационных технологий» паспорта специальности 05.13.17 — «Теоретические основы информатики» (технические науки).

Целью работы является разработка комбинированного алгоритма точного решения задачи одномерной оптимальной по стоимости упаковки и его сравнительный анализ с исходными схемами.

Методы исследования. В ходе диссертационного исследования был использован аппарат теории сложности вычислений, теории ресурсной эффективности компьютерных алгоритмов и теории планирования эксперимента.

Научная новизна диссертационной работы заключается в следующих положениях:

1. В теорию разработки эффективных алгоритмов введено новое понятие «алгоритмическая система».

2. Предложены оригинальные классификации алгоритмических систем и методов построения алгоритмических систем, ориентированные на повышение ресурсной эффективности алгоритмического обеспечения.

3. Разработан новый волновой алгоритм точного решения задачи одномерной оптимальной по стоимости упаковки, отличающийся от известных лучшими ресурсными характеристиками.

4. Проведен теоретический анализ волнового алгоритма, получено аналитическое выражение функции трудоемкости в среднем, что позволяет выполнять адекватное прогнозирование временной эффективности на реальных диапазонах длин входов.

Теоретическая значимость. Предложенные классификации позволяют не только систематизировать имеющиеся ныне решения, использующие совместное применение нескольких алгоритмов, но и разрабатывать новые комбинированные алгоритмические решения и комбинированные алгоритмы. Показано, что разработанный новый волновой алгоритм точного решения задачи одномерной оптимальной по стоимости упаковки имеет лучшие по сравнению с аналогами ресурсные характеристики.

Практическая значимость диссертационной работы определяется следующими положениями:

4. 1. Предложенные классификации являются удобным инструментом выбора и разработки алгоритмических систем.

   2. Разработанный с использованием предложенных классификаций комбинированный алгоритм обладает лучшими ресурсными характеристиками по сравнению с базовыми алгоритмами, а его

   программная реализация — лучшими временными характеристики.

   Основные положения, выносимые на защиту:

   4. 2. 1. Понятие «алгоритмическая система».

         2. Классификация алгоритмических систем.

         3. Классификация методов построения алгоритмических систем.

         4. Новый волновой алгоритм точного решения задачи одномерной оптимальной по стоимости упаковки.

         Достоверность и обоснованность научных положений и выводов обеспечивается корректным использованием базовых методов исследования и математического аппарата. Достоверность результатов работы подтверждается сравнительным анализом существующих подходов к решению поставленной задачи, а также результатами экспериментальных исследований.

         Реализация результатов работы. Временная эффективность предложенного волнового алгоритма в среднем вдвое выше, чем у базовых алгоритмов. Подобное улучшение ресурсных характеристик позволило использовать волновой алгоритм в системе реального времени. С помощью волнового алгоритма реализуется одна из функций программного модуля «Ведение оперативной базы данных активных планов полетов в комплексе средств автоматизации» (ВОБДАПП) в составе комплекса средств автоматизации управления воздушным движением в режиме реального времени. На разработанный модуль в Федеральной службе по интеллектуальной собственности получено Свидетельство о государственной регистрации программы для ЭВМ № 2012615176 от 08.06.2012.

         Апробация работы. Основные научные и практические результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

         — международная научно-техническая конференция «Информационные технологии и системы», НГТУ, Нижний Новгород (ИСТ-2008, ИСТ-2009, ИСТ-2010, ИСТ-2011).

         II и III Всероссийская студенческая научно-техническая конференция «Прикладная информатика и математическое моделирование», МГУП, Москва, 2008, 2009.

         52-я и 54-я Всероссийская научная конференция «Современные проблемы фундаментальных и прикладных наук», МФТИ, Москва, 2009, 2011.

         XI Международная конференция по математическому моделированию и информационным технологиям «YM-2010», ИВТ СО РАН, Новосибирск, 2010.

         научная школа-семинар «Задачи системного анализа, управления и обработки информации», МГУП, Москва, 2009.

         Публикации. Основное содержание диссертационной работы изложено в 13 публикациях, в том числе — в 3 статьях, опубликованных в журналах Перечня ВАК. Получено Свидетельство о государственной регистрации программы для ЭВМ.

         Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения, списка литературы и двух приложений. Общий объем работы — 134 страницы. Список литературы включает 107 источников.

         Похожие диссертации на Комбинированные алгоритмы решения задачи одномерной упаковки

         

         Модифицированные эволюционные алгоритмы и программные решения задачи ортогональной упаковки объектовЧеканин, Владислав Александрович

         

         Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходовКорчевская Оксана Валериевна

         

         Разработка и исследование нейросетевых алгоритмов решения задач навигации интеллектуальными мобильными агентами в нестационарных средахПриемко Андрей Анатольевич

         

         Итерационные методы и алгоритмы решения задачи сильной отделимостиЕршова, Арина Владимировна

         

         Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходеКосовская, Татьяна Матвеевна

         Нейросетевые алгоритмы для решения задач кодирования изображений с использованием технологии CUDAНгуен Виет Хунг

         

         Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типаПолуян, Анна Юрьевна

         Разработка эволюционных алгоритмов для решения задач теории расписаний в условиях неопределенностиРодькина, Маргарита Борисовна

         Разработка и исследование моделей и алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединенийОрлов Николай Николаевич

         

         Полиномиальные алгоритмы для решения комбинаторных задач размещений прямоугольников Вяткина Кира Вадимовна