На правах рукописи

Наумова Ольга Анатольевна

КОМБИНИРОВАННЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ

ОДНОМЕРНОЙ УПАКОВКИ

Специальность 05.13.17 – теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Москва — 2013

Работа выполнена на кафедре «Прикладная математика и моделирование систем» федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный университет печати (МГУПечати) имени Ивана Федорова».

Научный руководитель: доктор технических наук, профессор Ульянов Михаил Васильевич

Официальные оппоненты: Сметанин Юрий Геннадиевич, доктор физико-математических наук, старший научный сотрудник, ведущий научный сотрудник Вычислительного центра РАН имени академика А.А. Дородницына Ковшов Евгений Евгеньевич, доктор технических наук, профессор, заведующий кафедрой «Управление и информатика в технических системах» МГТУ «СТАНКИН»

Ведущая организация: Институт радиоэлектроники и информационных технологий Нижегородского государственного технического университета имени Р.Е. Алексеева

Защита состоится «04» апреля 2013 г. в 1230 часов на заседании диссертационного совета Д 212.147.03 при Московском государственном университете печати имени Ивана Федорова (127550, г. Москва, ул.

Прянишникова, 2А).

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Московский государственный университет печати имени Ивана Федорова»

Автореферат разослан «» _ 2013 г.

Ученый секретарь Диссертационного совета Д 212.147. д.т.н., профессор В.Н. Агеев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

программных систем для новых информационных технологий» паспорта специальности 05.13.17 — «Теоретические основы информатики»

(технические науки).

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

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

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

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

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

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

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

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

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

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

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

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 статьях, опубликованных в журналах Перечня ВАК. Получено Свидетельство о государственной регистрации программы для ЭВМ.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Введение содержит обоснование актуальности, научной и практической значимости диссертационной работы.

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

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

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

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

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

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

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

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

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

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

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

Под термином «комбинированный алгоритм» понимается совместное использование (комбинация) нескольких алгоритмов с различными ресурсными характеристиками при решении задачи для конкретного входа.

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

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

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

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

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

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

В рамках теоретического анализа получены формулы полного и уникального числа обращений к строкам структуры на первом этапе выполнения алгоритма:

где mn1 min k 'n1, vn 1 ; R – все k 'n i1, i2,..., in1 для равных V i1,i2, кроме максимальных. В формулах (1) и (2):

Также получена функция трудоемкости волнового алгоритма:

где вид функции f n,V, k, * определяется порогом переключения. Функция трудоемкости может быть использована для прогнозирования временной эффективности волнового алгоритма.

Численные эксперименты подтвердили ожидаемое превосходство волнового алгоритма над базовыми. Результаты приведены на рисунках 3–8.

На рисунках ниже по оси ординат указано значение трудоемкости исследуемых алгоритмов или время выполнения программной реализации в миллисекундах. Значение V =1000 — объем упаковки, n — число типов грузов, а k — параметр, показывающий соразмерность общего объема и среднего объема по типам грузов.

Рис. 3. Зависимости трудоемкостей от параметра k.

Рис. 4. Зависимости трудоемкостей от числа типов грузов, n 3,7.

Рис. 5. Сравнение трудоемкостей табличного и волнового алгоритмов для Рис. 6. Зависимости временных эффективностей от параметра k.

Рис. 7. Зависимости временных эффективностей алгоритмов Рис. 8. Сравнение временной эффективности табличного и волнового Сокращение трудоемкости волнового алгоритма относительно лучшего из базовых в среднем составило 73,72%. Сокращение времени работы волнового алгоритма относительно лучшего из базовых в среднем составило 44,62%. Другими словами, волновой алгоритм в среднем выполняет в 4, раза меньше базовых операций и в среднем работает в 2 раза быстрее, чем наиболее эффективный из пары табличный — рекурсивный для текущего входа.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ Комбинированный алгоритм решения задачи одномерной упаковки:

статически-адаптивный подход // Проблемы полиграфии и издательского дела. 2008. №2. С. 67–82.

2. Наумова О.А., Ульянов М.В. Теоретическое определение числа уникальных обращений волнового алгоритма решения задачи одномерной упаковки к строкам структуры данных // Автоматизация и современные технологии. 2009. №4. С. 14–21.

3. Наумова О.А., Ульянов М.В. Классификация методов построения алгоритмических систем // Вычислительные технологии. 2011. Т. 16, № 1. С.

105–118.

4. Гиряева А.Н., Наумова О.А. Детальный анализ трудоемкости табличного алгоритма упаковки // Материалы международной научно-технической конференции «Информационные технологии и системы ИСТ-2008» — Нижний Новгород: НГТУ, 2008, С. 218–219.

5. Наумова О.А., Ульянов М.В., Яковлев И.А. Прогнозирование временных оценок для табличного алгоритма решения задачи оптимальной упаковки на основе функции трудоемкости // Бизнес-Информатика 2008. №3(5). С. 37–46.

6. Наумова О.А., Ульянов М.В. Комбинированный и волновой алгоритмы решения задачи упаковки: принципы построения и особенности // БизнесИнформатика. 2009. №2(8). С. 27–33.

7. Наумова О.А. Теоретическое определение числа уникальных обращений волнового алгоритма решения задачи одномерной упаковки к строкам структуры данных (тезисы доклада) // Материалы XV международной научно-технической конференции «Информационные технологии и системы ИСТ-2009» — Нижний Новгород: НГТУ, 2009, С. 290–291.

8. Наумова О.А. Классификация комбинированных компьютерных алгоритмов по типу определения алгоритмов по типу определения порога переключения (тезисы доклада) // Труды 52-й Всероссийской научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть IX. Инновации и высокие технологии — М.:

МФТИ, 2009. — 166 с. С. 25-27.

9. Наумова О.А., Ульянов М.В. Алгоритмические системы: классификация и методы построения // Программные информационные системы:

Межвузовский сборник научных трудов. Рязань: РГРТУ, 2010. 152 с. С. 74–79.

10. Наумова О.А., Ульянов М.В. Классификация алгоритмических систем на основе результатов кластеризации и классификации данных (тезисы доклада) // Материалы XVI международной научно-технической конференции «Информационные технологии и системы ИСТ-2010» — Нижний Новгород:

НГТУ, 2010. С. 318–319.

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

12. Наумова О.А. Волновой алгоритм решения задачи одномерной оптимальной по стоимости упаковки (тезисы доклада) // Материалы XVII международной научно-технической конференции «Информационные технологии и системы ИСТ-2011» — Нижний Новгород: НГТУ, 2011. С. 337.

13. Наумова О.А. Решение задачи упаковки построением алгоритмической системы (тезисы доклада) // Труды 54-й Всероссийской научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе». Инновации и высокие технологии — М.: МФТИ, 2011. — 112 с. С. 32-33.

Патенты, свидетельства на программы для ЭВМ 1. Медведев А.С., Наумова О.А., Подойницына Н.П., Репкина Н.Н., Сухов В.В., Щеглов В.А. «Ведение оперативной базы данных активных планов полётов в комплексе средств автоматизации»: Свидетельство о государственной регистрации программы для ЭВМ № 2012615176 // Федеральная служба по интеллектуальной собственности. — 08.06.2012.