На правах рукописи
Емельянова Татьяна Сергеевна
РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ
РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ МЕТОДОВ
05.13.01 – системный анализ, управление и обработка информации
(вычислительная техника и информатика)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Таганрог – 2009
Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге.
Научный руководитель: доктор технических наук, профессор
Курейчик Виктор Михайлович
Официальные оппоненты: доктор технических наук, профессор
Ковалев Сергей Михайлович
(РГУПС, г.Ростов-на-Дону)
кандидат технических наук, доцент
Родзин Сергей Иванович
(Технологический институт Южного
федерального университета в г.Таганроге)
Ведущая организация: Российский научно-исследовательский
институт управления на железнодорожном транспорте МПС России Ростовский филиал.
Защита состоится «25» июня 2009 г. в 14:20 на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, г.Таганрог, пер. Некрасовский, 44, ауд. Д-406.
С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.
Автореферат разослан «23» мая 2009 г.
У ченый секретарь
диссертационного совета Д 212.208.22,
доктор технических наук, профессор Целых А.Н.
Актуальность работы
Логистика важная область жизнедеятельности человека. Перевозка людей и грузов (от пищевых до промышленных) – это неотъемлемая часть жизни современного человека. Необходимость решения транспортных задач, с минимизацией издержек на перевозку, определяется экономическим эффектом при нахождении лучшего решения, т.к. это увеличивает прибыль предприятия. Применение компьютерных методов решения задач позволяет увеличить скорость принятия решений и повысить эффективность найденных решений. Поэтому требуются алгоритмы способные исполняться на массово доступных вычислительных средствах (персональных компьютерах и малых серверах). Разработка новых методов должна учитывать структуру вычислительных средств, на которых будут исполняться программы, реализующие данные алгоритмы. В настоящее время основные тенденции развития компьютерной техники таковы: за последние несколько лет резко снизился рост частоты процессоров, появилась возможность хранить в памяти огромные объемы информации. Снижение роста быстродействия процессоров произошло из-за достижения технологического предела нанометровых технологий, однако появилась возможность разместить на одном кристалле большее количество вычислительных элементов (процессорных ядер). Польза от использования этих ядер будет только в том случае, если исполняемая программа (и её алгоритм) является параллельным, в противном случае будет использоваться (работать) только одно ядро, а остальные будут простаивать. Известно, что классические алгоритмы не имеют возможности распараллеливания и имеют экспоненциальный рост времени выполнения от размерности задачи. Т.е. количество математических действий (команд) растет экспоненциально, а развитие процессорных элементов (увеличение тактовой частоты, уменьшение количества тактов выполнения команд, задержка на выборку данных из памяти) не компенсируют растущие (с увеличением размерности задачи) потребности классических алгоритмов. Точные методы решения транспортных задач (ТЗ), позволяют найти решение только для задач с малым количеством клиентов (т.е. до 50-ти клиентов). Для решения задач большой размерности точные методы являются не эффективными в связи с их большими временными затратами. Однако, именно сейчас, требуется эффективные алгоритмы решения задач большой размерности, т.к. в настоящее время наблюдается процессы глобализации в экономике. Это приводит к необходимости планирования транспортных операций с большим количеством клиентов, т.е. к ТЗ большой размерности. Таким образом, решение ТЗ большой размерности является актуальной задачей. Одним из классов ТЗ является ТЗ с ограничением по времени. Данный класс задач является сложным для решения, но необходимым и широко применяемым на практике. Моделью ТЗ с ограничением по времени описываются: банковские и почтовые доставки, перевозка людей, сбор промышленных и бытовых отходов, доставка продуктов, доставка топлива и материалов на предприятия. На настоящий момент в литературе предложено множество алгоритмов решения данного класса задач. Практическим алгоритмам по решению ТЗ с ограничением посвящено множество работ следующих ученых: Solomon, Tompson, Psaraftis, Russell, Antes, Derigs, Cordone, Wolfer-Calv, Caseau, Laburthe, Braysy, Rochat, Taillard, Chiang, Cordeau, Thangiah, Homberger, Gehring, Mester, Barkaoui, Csiszár, Van Hentenryck и др.
Важным недостатком этих алгоритмов, является то, что они не предназначены для решения задач с изменяющимся количеством запросов от клиентов, что актуально на сегодняшний день в связи с развитием средств мобильной связи, дающей возможность отслеживать маршрут автомобиля и передавать измененный маршрут. Поэтому задача разработка комплекса алгоритмов решения ТЗ со статическими и динамическими запросами клиентов является актуальной научной задачей.
Цель диссертации
Целью диссертационной работы является разработка комплекса методов и алгоритмов интеллектуальной поддержки при принятии решений в транспортных системах.
Для достижения поставленной цели необходимо решить следующие задачи:
Проведение сравнительного анализа эффективности существующих методов решения ТЗ.
Разработка специального комбинированного генетического алгоритма (ГА) для решения статической ТЗ с ограничением по времени.
Построение генетических операторов отражающих специфику решаемой ТЗ (линейной или с ограничением по времени).
Разработка модифицированного ГА для решения динамической ТЗ.
Разработка программно-алгоритмических модулей для решения транспортных задач на основе разработанных алгоритмов, ориентированных на выполнение в многоядерных системах.
Научная новизна полученных в диссертации основных результатов заключается в следующем:
Разработаны новые модификации ГА для решения статической и динамической транспортной задачи с ограничением по времени.
Предложены новые принципы построения генетических операторов для применения в ГА решения транспортных задач. На основе этих принципов разработаны новые схемы операторов инициализации и мутации.
Предложен метод распараллеливания ГА для применения его в многоядерных системах, что позволило получить увеличение быстродействия.
Результаты выносимые на защиту
Генетические операторы для решения линейной транспортной задачи большой размерности (порядка 100×100 ).
Новый ГА и генетические операторы для решения транспортных задач с ограничением по времени.
Модифицированный ГА для решения динамической транспортной задачи, позволяющий реагировать на изменение (появление/удаление) запросов от клиентов при исполнении полученного решения, т. е. изменять решение в процессе его выполнения с целью уменьшения транспортных затрат.
Метод распараллеливания ГА ориентированный на выполнение разработанных алгоритмов на многоядерной вычислительной базе.
Практическая значимость
На основе разработанных методов и алгоритмов создан программно-алгоритмический комплекс для решения транспортных задач с ограничением по времени. При построении программного комплекса использовался объектно-ориентированный язык С++ и среда разработки Microsoft Visual C++ 6.0. Отладка и тестирование проводилось на ЭВМ типа IBM PC, с процессором AMD Athlon 64 X2 5400+, 2.8 ГГц, ОЗУ 3ГБ. Отличительная особенность разработанного программного комплекса – это эффективное использование многоядерной вычислительной системы, что позволило сократить время решения транспортных задач в два раза по сравнению с одноядерной системой.
Внедрение результатов работы
Основные результаты диссертационной работы использованы в госбюджетных и
хоздоговорных работах, проводимых в Таганрогском технологическом институте Южного федерального университета: в госбюджетной работе «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», в гранте РФФИ «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования». Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Прикладная информатика».
Методы исследования
В работе использовались методы системного анализа, исследования операций, линейного программирования, эвристические методы оптимизации, генетические алгоритмы.
Апробация работы
Основные результаты, полученные в ходе работы, докладывались и обсуждались на:
Всероссийских научных школах-семинарах молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки», Таганрог, 2007 и 2008 годы.
Международной научно-технической конференции «Интеллектуальные системы» (AIS’08) и «Интеллектуальные САПР» (CAD02008), Геленджик, 2008.
IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления», Таганрог, 2008.
Второй Всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления» (НСМВ-2008), Ульяновск, 2008.
XI Национальной конференции по искусственному интеллекту с международным участием (КИИ-08), Дубна 2008.
Публикации
Основные положения и результаты диссертационной работы опубликованы в 14 источниках, включающих 6 статей, 6 материалов конференций и семинаров, 2 свидетельства о регистрации программ. Две работы из них опубликованы в рецензируемом журнале из списка ВАК.
Объем и структура диссертации
Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 102 наименования и 6 приложений. Основной текст диссертации изложен на 150 странице, включая 41 рисунок и 6 таблиц.
Содержание работы
Во введении отражена актуальность задач логистики транспортного типа, сформулированы цели исследования, показана научная новизна работы.
В первой главе дано общее описание ТЗ и основные классы ТЗ получаемые из базовой ТЗ добавлением дополнительных ограничений. Особое внимание уделено ТЗ с ограничением по времени. Также описана динамическая ТЗ с ограничением по времени. В отличие от статической задачи, параметры которой известны до начала ее решения и не изменяются ни во время ее решения, ни во время выполнения, в динамической задаче условия задачи могут меняться во время обоих вышеперечисленных этапов. На рисунке 1 представлена классификация ТЗ.
|
Рис.1. Классификации ТЗ
| ТЗ с ограничением по времени относится к классу NP-трудных задач, точные методы решения для задач такого вида эффективны при малом количестве клиентов (т.е. до 50-ти клиентов). Основные методы решения данной задачи с большим количеством клиентов – это эвристические и метаэвристические методы. Наилучшие результаты при решении тестовых задач дают гибридные алгоритмы, направляемые глобальной эвристикой (метаэвристикой), которая в свою очередь в процессе поиска на промежуточных этапах использует различные методы улучшения маршрута, основанные на методе локального поиска. Эффективными являются различные постоптимизационные процедуры, которые позволяют улучшить конкретное конечное решение и приемы адаптации алгоритма к условиям текущей задачи (когда на различных этапах поиска применяются различные части алгоритма).
Анализ результатов решения тестовых задач описанными известными методами выявил, что в данных алгоритмах нет баланса между количеством транспортных средств и общим пройденным расстоянием, уменьшение расстояния достигается значительным увеличением количества транспортных средств. Нет данных о применении этих алгоритмов для решения задач с запросами клиентов, изменяющимися в процессе выполнения решения, что особенно актуально в практических задачах. Все эти факторы послужили причиной разработки нового комплекса ГА для решения ТЗ.
Во второй главе представлен разработанный новый ГА для решения линейных ТЗ размерности порядка 100×100. Для данного ГА были разработаны новые ГО кроссинговера и инициализации, отражающие специфику матричного представления линейной ТЗ. Применение операторов (в частности оператора кроссинговера), адаптированных к виду ТЗ, позволяет получать готовые допустимые решения-потомки из решений-родителей без дополнительных преобразований, только лишь с непосредственным применением оператора кроссинговера. Это позволяет сократить вычислительные издержки алгоритма. Применение данных операторов позволяет на каждой итерации алгоритма не ухудшать (а до определенного количества итераций улучшать) общую целевую функцию (ЦФ) популяции решений, что является главной целью работы ГА. Т.е. среднее значение ЦФ уменьшается на каждой генерации ГА, пока не сходится к определенному значению, которое будет являться наилучшим для данной задачи. На рисунке 2 показана динамика изменения ЦФ популяции решений для задачи размерностью 100x100 при размере популяции 800 особей.
|
Рис.2. График зависимости ЦФ лучшего решения в популяции от номера итерации.
| Исследования показали, что данный оператор кроссинговера эффективен только при больших (более 100) размерах популяции решений; при малых размерах популяции, применение одного оператора мутации, является более эффективным (по качеству получаемого решения и временным затратам). Представленный ГА направлен на решения именно задач большой размерности (матрица стоимостей порядка 100×100), где размер популяции решений достигает 1000; в этом случае применение данного оператора позволяет получить лучшее решение. Т.е. можно сделать вывод, что применения оператора кроссинговера, отражающего специфику представления конкретной ТЗ, является оправданным с точки зрения вычислительной простоты и качества получаемого решения.
Для начального построения популяции решений был выбран путь, в котором берется наиболее простой метод конструирования решения (в данном случае метод «северо-западного» угла) и адаптируется для применения в ГА. В данном случае в методе «северо-западного» угла, элемент матрицы решений выбирался не по определенному детерминированному правилу, а равновероятностным образом. Это позволило на первом этапе формирования популяции решений получить большое разнообразие решений при начале работы ГА. Обеспечение разнообразия в начальной популяции решений является важным условием успешной работы ГА. Предложенный оператор инициализации обеспечивает необходимое разнообразие решений в популяции на начальном этапе работы алгоритма.
Результаты решения тестовых задач размера от 5×5 до 18×18 показали, что решение, полученное разработанным алгоритмом, при подборе параметров ГА, совпадает с оптимальным решением. При решении тестовых задач порядка 100×100 решение улучшалось в среднем на 35% от начального решения, при этом время решения задачи увеличивалось пропорционально размерности задачи n×m.
|
