Содержание к диссертации
Введение
ГЛАВА 1 Состояние проблемы и анализ методов решения транспортных задач 19
1.1 Классификация транспортных задач. Транспортные задачи с ограничением по времени 19
1.2 Динамическая транспортная задача. Проблема оценки динамической составляющей транспортной задачи 23
1.3 Анализ методов решения транспортных задач с ограничением по времени 27
1.4 Выводы 42
ГЛАВА 2 Разработка генетического алгоритма решения линейных транспортных задач большой размерности 44
2.1 Постановка транспортной задачи линейного программирования 44
2.2 Определение и основные свойства генетических алгоритмов 47
2.3 Структура генетического алгоритма 48
2.4 Конструирование начальной популяции 49
2.5 Операторы селекции 51
2.6 Оператор кроссинговера 53
2.7 Оператор мутации 57
2.8 Выводы 58
ГЛАВА 3 Генетический алгоритм решения транспортной задачи с ограничением по времени 60
3.1 Математическая постановка транспортной задачи с ограничением по времени 60
3.2 Структура разработанного генетического алгоритма 63
3.3 Кодирование решения 67
3.4 Оператор инициализации 69
3.5 Оператор кроссинговера 71
3.6 Операторы мутации 82
3.7 Фундаментальная теорема ГА 90
3.8 Оценка временной сложности алгоритма 91
3.9 Распараллеливание алгоритма для многоядерных систем 95
3.10 Применение разработанного ГА для решения динамической транспортной задачи с ограничением по времени 98
3.11 Выводы 103
ГЛАВА 4 Тестирование и экспериментальное обоснование разработанных алгоритмов 106
4.1 Описание тестовых моделей транспортных задач 106
4.2 Описание программной среды для тестирования алгоритма решения линейных транспортных задач и результаты экспериментов 112
4.3 Описание программной среды для тестирования алгоритма решения транспортных задач с ограничением по времени и результаты экспериментов 118
4.4 Исследование влияния динамической составляющей на решение транспортных задач с ограничением по времени 128
4.5 Выводы 136
Заключение 138
Список использованной литературы 140
Приложения 151
- Анализ методов решения транспортных задач с ограничением по времени
- Постановка транспортной задачи линейного программирования
- Структура разработанного генетического алгоритма
- Описание программной среды для тестирования алгоритма решения линейных транспортных задач и результаты экспериментов
Введение к работе
Актуальность работы
Транспортировка важная область жизнедеятельности человека. Перевозка людей и грузов (от пищевых до промышленных) — это неотъемлемая часть жизни современного человека. Так расходы на транспортировку различных видов грузов составляют в Великобритании -15%, во Франции - 9%, в Дании - 15% от общих национальных расходов [1]. Необходимость решения таких транспортных задач, с минимизацией издержек на перевозку, определяется большим экономическим эффектом при нахождении лучшего решения, т.к. это явно увеличивает прибыль предприятия. Применение компьютерных методов решения задач позволяет увеличить скорость принятия решений и повысить эффективность найденных решений. Поэтому требуются алгоритмы способные исполняться на массово доступных вычислительных средствах (персональных компьютерах и малых серверах). Разработка новых алгоритмов должна учитывать структуру вычислительных средств, на которых будут исполняться программы (реализующие данные алгоритмы). В настоящее время основные тенденции развития компьютерной техники таковы: за последние несколько лет резко снизился рост частоты процессоров, появилась возможность хранить в памяти огромные объемы информации. Снижение роста быстродействия процессоров произошло из-за достижения технологического предела нанометровых технологий, однако появилась возможность разместить на одном кристалле большее количество вычислительных элементов (процессорных ядер). Польза от использования этих ядер будет только в том случае, если исполняемая программа (и её алгоритм) является параллельным, в противном случае будет использоваться (работать) только одно ядро, а остальные будут простаивать. Известно, что классические алгоритмы не имеют возможности распараллеливания и имеют экспоненциальный рост времени выполнения от размерности задачи. Т.е.
количество математических действий (команд) растет экспоненциально, а развитие процессорных элементов (увеличение тактовой частоты, уменьшение количества тактов выполнения команд, задержка на выборку данных из памяти) не компенсируют растущие (с увеличением размерности задачи) потребности классических алгоритмов. Точные методы решения транспортных задач (ТЗ), позволяют найти решение только для задач с малым количеством клиентов (т.е. до 50-ти клиентов [2]). Для решения задач большой размерности точные методы являются не эффективными в связи с их большими временными затратами. Однако, именно сейчас, требуется эффективные алгоритмы решения задач большой размерности, т.к. в настоящее время наблюдается процессы глобализации в экономике. В частности, это приводит к слиянию множества мелких и средних компаний в крупные корпорации, которые пытаются уменьшить издержки путем сокращения количества однотипных объектов инфраструктуры (складов, ремонтных мастерских и пр.) преобразовывая их в крупные объекты регионального значения. Что приводит к необходимости планирования транспортных операций с большим количеством клиентов, т.е. к ТЗ большой размерности. Таким образом, решение ТЗ большой размерности является актуальной задачей. Одним из классов ТЗ является ТЗ с ограничением по времени. Данный класс задач является сложным для решения, но необходимым и широко применяемым на практике. Моделью ТЗ с ограничением по времени описываются: банковские и почтовые доставки, перевозка людей, сбор промышленных и бытовых отходов, доставка продуктов, доставка топлива и материалов на предприятия. На настоящий момент в иностранной литературе предложено множество алгоритмов решения данного класса задач, к сожалению, в нашей стране методы транспортной логистики только начинают свое развитие. Практическим алгоритмам по решению ТЗ с ограничением посвящено множество работ следующих ученых: Solomon, Tompson, Psaraftis, Russell, Antes, Derigs, Cordone, Wolfer-Calv, Caseau, Laburthe, Braysy, Rochat, Taillard, Chiang,
Cordeau, Thangiah, Homberger, Gehring, Mester, Barkaoui, Csiszar, Van Hentenryck и др.
Важным недостатком этих алгоритмов, является то, что они не предназначены для решения задач с изменяющимся количеством запросов от клиентов, что актуально на сегодняшний день в связи с развитием средств мобильной связи, дающей возможность отслеживать маршрут автомобиля и передавать измененный маршрут. Эти возможности не учитываются в алгоритмах предложенных вышеперечисленными учеными. Поэтому задача разработки комплекса алгоритмов решения ТЗ с ограничением по времени и адаптация данного алгоритма к динамическому изменению запросов клиентов, представляется актуальной научной задачей.
Цель диссертации
Целью диссертационной работы является разработка комплекса алгоритмов интеллектуальной поддержки при принятии решений в транспортных системах, оценка и анализ их вычислительной сложности.
Для достижения поставленной цели необходимо решить следующие задачи:
Проведение сравнительного анализа эффективности существующих методов решения ТЗ.
Построение генетических операторов отражающих специфику решаемой ТЗ (линейной или с ограничением по времени).
Разработка специального комбинированного генетического алгоритма (ГА) для решения статической ТЗ с ограничением по времени.
Разработка модифицированного ГА для решения динамической ТЗ.
Разработка программно-алгоритмических модулей для решения транспортных задач на основе разработанных алгоритмов, ориентированных на выполнение в многоядерных системах.
Научная новизна полученных в диссертации основных результатов заключается в следующем:
Предложены новые принципы построения генетических операторов для применения в ГА решения транспортных задач, на основе этих принципов разработаны новые схемы операторов инициализации и мутации.
Разработаны новые модификации ГА для решения статической и динамической транспортной задачи с ограничением по времени.
Предложен метод распараллеливания ГА для применения его в многоядерных системах, что позволило получить увеличение быстродействия.
Результаты выносимые на защиту
Генетические операторы для решения линейной транспортной задачи большой размерности (порядка 100x100).
Новый ГА и генетические операторы для решения транспортных задач с ограничением по времени.
Модифицированный ГА для решения динамической транспортной задачи, позволяющий реагировать на изменение (появление/удаление) запросов от клиентов при исполнении полученного решения, т. е. изменять решение в процессе его выполнения с целью уменьшения транспортных затрат.
Метод распараллеливания ГА ориентированный на выполнение разработанных алгоритмов на многоядерной вычислительной базе.
Практическая значимость
На основе разработанных алгоритмов создан программно-алгоритмический комплекс для решения транспортных задач с ограничением по времени. При построении программного комплекса использовался объектно-ориентированный язык C++ и среда разработки Microsoft Visual
C++ 6.0. Отладка и тестирование проводилось на ЭВМ типа IBM PC, с процессором AMD Athlon 64 Х2 5400+, 2.8 ГГц, ОЗУ 3ГБ. Отличительная особенность разработанного программного комплекса — это эффективное использование многоядерной вычислительной системы, что позволило сократить время решения транспортных задач в два раза.
Внедрение результатов работы
Основные результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском технологическом институте Южного федерального университета: в госбюджетной работе «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», в гранте РФФИ «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования». Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Прикладная информатика».
Методы исследования
В работе использовались методы системного анализа, исследования операций, линейного программирования, эвристические методы оптимизации, генетические алгоритмы.
Апробация работы
Основные результаты, полученные в ходе работы, докладывались и обсуждались на:
Всероссийских научных школах-семинарах молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки», Таганрог, 2007 и 2008 годы.
Международной научно-технической конференции «Интеллектуальные системы» (ATS'08) и «Интеллектуальные САПР» (CAD02008), Геленжик, 2008.
IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления», Таганрог, 2008.
Второй Всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления» (НСМВ-2008), Ульяновск, 2008.
XI Национальной конференции по искусственному интеллекту с международным участием (КИИ-08), Дубна 2008.
Публикации
Основные положения и результаты диссертационной работы опубликованы в 14 источниках, включающих 6 статей, 6 материалов конференций и семинаров, 2 свидетельства о регистрации программ. Две работы из них опубликованы в рецензируемом журнале из списка ВАК.
Объем и структура диссертации
Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 102 наименования и 6 приложений. Основной текст диссертации изложен на 150 страницах, включая 41 рисунок и 6 таблиц.
Содержание работы
Во введении отражена актуальность задач транспортного типа, сформулированы цели исследования, показана научная новизна работы.
В первой главе дано общее описание ТЗ и основные классы ТЗ получаемые из базовой ТЗ добавлением дополнительных ограничений. Особое внимание уделено ТЗ с ограничением по времени. Также описана динамическая ТЗ с ограничением по времени. В отличие от статической задачи, параметры которой известны до начала ее решения и не изменяются ни во время ее решения, ни во время выполнения, в динамической задаче условия задачи могут меняться во время обоих вышеперечисленных этапов.
ТЗ с ограничением по времени относится к классу iVP-трудных задач, точные методы решения для задач такого вида эффективны при малом количестве клиентов (т.е. до 50-ти клиентов [2]). Основные методы решения данной задачи с большим количеством клиентов - это эвристические и метаэвристические методы. Наилучшие результаты при решении тестовых задач дают гибридные алгоритмы, направляемые глобальной эвристикой (метаэвристикой), которая в свою очередь в процессе поиска на промежуточных этапах использует различные методы улучшения маршрута, основанные на методе локального поиска. Эффективными являются различные постоптимизационные процедуры, которые позволяют улучшить конкретное конечное решение. Приемы адаптации алгоритма к условиям текущей задачи (когда на различных этапах поиска применяются различные части алгоритма) тоже дают хорошие результаты.
Анализ результатов решения тестовых задач описанными известными эффективными методами выявил, что в данных алгоритмах нет баланса между количеством транспортных средств и общим пройденным расстоянием, уменьшение расстояния достигается значительным увеличением количества транспортных средств. Нет данных о применении этих алгоритмов для решения задач с запросами клиентов, изменяющимися в процессе выполнения решения, что особенно актуально в практических задачах. Все эти факторы послужили причиной разработки нового комплекса ГА для решения ТЗ.
Во второй главе представлен разработанный новый ГА для решения линейных ТЗ размерности порядка 100x100. Для данного ГА были разработаны новые ГО кроссинговера и инициализации, отражающие специфику матричного представления линейной ТЗ. Применение операторов (в частности оператора кроссинговера) адаптированных к виду ТЗ позволяет получать готовые допустимые решения-потомки из решений-родителей без дополнительных преобразований, только лишь с непосредственным применением оператора кроссинговера. Это позволяет значительно сократить вычислительные издержки алгоритма. Применение данных операторов позволяет на каждой итерации алгоритма не ухудшать (а до определенного количества итераций улучшать) общую целевую функцию (ЦФ) популяции решений, что является главной целью работы ГА. Т.е. среднее значение ЦФ уменьшается на каждой генерации ГА, пока не сходится к определенному значению, которое будет являться наилучшим для данной задачи. Исследования показали, что данный оператор кроссинговера эффективен только при больших (более 100) размерах популяции решений; при малых размерах популяции, применение одного оператора мутации, является более эффективным (по качеству получаемого решения и временным затратам). Однако представленный ГА направлен на решения именно задач большой размерности (матрица стоимостей порядка 100x100), где размер популяции решений достигает 1000; в этом случае применение данного оператора позволяет получить лучшее решение. Т.е. можно сделать вывод, что применения оператора кроссинговера, отражающего специфику представления конкретной ТЗ, является оправданным с точки зрения вычислительной простоты и качества получаемого решения.
Для начального построения популяции решений был выбран путь, в котором берется наиболее простой метод конструирования решения (в данном случае метод «северо-западного» угла) и адаптируется для применения в ГА. В данном случае в методе «северо-западного» угла, начальный элемент матрицы решений выбирался не по определенному
детерминированному правилу, а равновероятностным образом. Это позволило на первом этапе формирования популяции решений получить большое разнообразие решений при начале работы ГА. Обеспечение большого разнообразия в начальной популяции решений является важным условием успешной работы ГА. Предложенный оператор инициализации успешно справляется с этой задачей.
Исходя из всего вышесказанного, можно сделать следующие выводы. Представленный ГА вместе со специально разработанными ГО успешно решает линейные ТЗ большой размерности. Данный ГА позволяет найти достаточно хорошее решение за достаточно малое время. Время работы алгоритма линейно зависит от размерности задачи яхт. Приемы распараллеливания алгоритма позволяют уменьшить это время в 2, 3, 4-е и более раз в зависимости от количества процессорных ядер в системе.
В третьей главе представлены математическая модель ТЗ с ограничением по времени и новый ГА решения данной задачи, позволяющий работать как со статическими, так и с динамическими запросами клиентов.
Согласно [2, 3] математически ТЗ с ограничением по времени можно представить в виде графа
G = (N, А), . где: N- множество вершин, соответствующих набору клиентов (customers) (вершины 1,2, ..., п) и исходным депо (depot), в которых начинают и заканчивают свой маршрут все автомобили (вершины 0 и п+1); А - набор дуг, соединяющих вершины графа.
Введем обозначения:
С - множество клиентов, \С\ = п;
i,j — /-й и у'-й клиенты, / є С, j є С;
(і, j) є А — дуга, соединяющая z'-ю и у'-ю вершины графа; ф - спрос /-го клиента;
tij - время перемещения по дуге (/, j), состоящее из времени обслуживания клиента / и времени перемещения автомобиля от клиента і к клиентуу;
c,j — стоимость перемещения автомобиля от клиента і к клиенту j;
V — количество идентичных автомобилей грузоподъемностью q;
к — к-й автомобиль, к є V ;
[ait bj - «временное окно» (time window) - промежуток времени, в течение которого должен быть обслужен /-й клиент;
S,k - время прибытия к-го автомобиля к і-му клиенту; время отправления из депо для всех автомобилей равно 0 (т.е. Sok=0 VkeV);
Xif -переменная, принимающая значения {0,1} и характеризующая направление движения автомобиля: Х^ = 1 - от клиента / к клиенту у, Хук = О - в обратном направлении.
С учетом этих обозначений математическая формулировка ТЗ с ограничением по времени такова: необходимо минимизировать целевую функцию (1) при ограничениях (2)-(9) [2, 3]:
keV(,,j)eA
2S^=1,V/6C (2)
keV jeN
^d^X^q^keV (3)
ієС jeN
^Xk0j=l,VkeV (4)
jeN jeN
^ХІ+1=1,ЧкєУ (6)
2^(5*+^-5у')^0,У(/,у)є^У*єК (7)
я,.
X*e{0,\}MUJ)eA,VkeV. (9)
ЦФ (1) определяет цену всех маршрутов всех транспортных средств (общая цена транспортного плана). Ограничение (2) полагает, что каждый клиент обслуживается только одним транспортным средством и только один раз. Ограничение (3) определяет, что транспортное средство не может обслужить больше клиентов, чем позволяет его грузоподъемность. Ограничение (4) означает, что каждый автомобиль покидает депо один раз. Ограничение (5) показывает, что автомобиль может покинуть вершину И, только если он прибыл в эту вершину. Аналогично ограничению (4), ограничение (6) означает, что все транспортные средства возвращаются в депо, причем один раз. Это ограничение следует из ограничений (4) и (5). Ограничение (7) означает что, если автомобиль движется из вершины / ву, то время прибытия автомобиля в j не может быть меньше суммы времени прибытия автомобиля в пункт і (S, ) и времени движения автомобиля из пункта і в пункт j (ty). Ограничение (8) - это ограничение по времени, прибытие автомобиля к клиенту должно быть в пределах временного окна.
Основной особенностью разработанного алгоритма является использование дополнительного оператора мутации при «застаивании» процесса поиска, т.е. дополнительный оператор не используется в регулярном цикле работы алгоритма, а применяется лишь в том случае, когда лучшее значение ЦФ в популяции решений не изменялось в течение определенного (заранее заданного) количества итераций (Coiintst). Алгоритм заканчивает свою работу, если выполнено заданное максимальное количество итераций (N,-t) или если значение счетчика «застаивания» процесса поиска достигло определенного значения, рассчитываемого исходя из максимального количества итераций.
Разработаны и подробно описаны основные ГО алгоритма. Для оператора кроссинговера (ОК) определена вероятность выживания схемы PksfS) при применении данного оператора с вероятностью кроссинговера Рк.
PJS) = \-PkPd(S) = \-Pk-(\-Ps(S)) = \-Pk +Pk -PS(S) =
= і-л + ъ<—*—т п—-^—
+ PJ(S) + PS2(S)),
где a, J3 и N - параметры OK; у - количество закрепленных маршрутов в
шаблоне; Ps (S) и Ps (S) - вероятности, нелинейно зависящие от количества
закрепленных клиентов в маршрутах и от временных ограничений,
накладываемых на решение задачи. Оценить вероятности P^(S) и P2(S)
возможно только путем экспериментов.
Найдена вероятность выживания шаблонов при применении операторов мутации (ОМ) ОМ_1 и ОМ2. Данные вероятности соответственно равны:
Pl(S) = 1-Р1 -PX(S) = l-^-fl-P1^ = i-^1 +^1 P1(S) =
= l-Plm + Plm'f[(l-—.), vpnm + o(S)
где, P1 - вероятность применения ОМ_1; тик — параметры ОМ_1; o(S) -
количество закрепленных маршрутов в шаблоне.
P2(S) = \-P2-Pd(S) = \-P2(\-P2(S)) = l-P2 + P2 -P2(S) =
ms m u rn s m m s
= \-P2+P2 -11(1--^-), при К+ o(S)
"' 7=o N-i
где P2 — вероятность применения OM_2; К - параметр ОМ_2; N—
количество клиентов в задаче; o(S) - количество закрепленных клиентов в маршрутах в шаблоне.
В результате оценки временной сложности алгоритма было вычислено, что время работы алгоритма не хуже чем 0(п3).
Рассмотрен метод, позволяющий применять разработанный ГА к решению задач с динамическими запросами клиентов. Метод приводит задачу к серии статических подзадач, различающихся между собой начальными условиями и количеством клиентов, которых необходимо обслужить. Преимущество данного метода заключается в том, что основные
ГО остаются неизменными, для них лишь вводится дополнительный модуль инициализации решения начальными условиями. Данный модуль включается в оператор инициализации, используемый в операторах кроссинговера и мутации; сами же операторы кроссинговера и мутации остаются без изменения.
Предложен метод, позволяющий уменьшить время выполнения ГА за счет выполнения его многопроцессорной системой. Данный метод не требует применения специальной архитектуры генетического поиска и может применяться для простого последовательного ГА.
Количество запускаемых при решении задачи потоков равно количеству ядер процессора, во столько же раз и уменьшается время работы алгоритма. Т.е. на 2-ядерном процессоре и запуске второго дополнительного потока при создании начальной популяции и при выполнении главного цикла ГА время выполнения программы практически уменьшается в два раза. Дополнительные потоки не изменяют структуру ГА, а только дополняют ее. Программа автоматически запрашивает у системы количество процессорных ядер и запускает, если это возможно, дополнительные потоки.
В четвертой главе рассмотрена разработка программных модулей и тестовых систем для оценки практической ценности разработанных алгоритмов.
Эксперименты проводились для задач с различным расположением клиентов: равномерным (R), кластерным (С) и смешанным (RC) и различными по жесткости временными ограничениями класс 1 и 2.
Результаты экспериментов показывают, что разница полученных результатов с лучшими решениями в классе С2 составляет 0%; в классе С1 от 0% до 7,3%; в классе R1 от 0% до 2,3%; в классе R2 от 3,7% до 9,4%; в классе RC1 от 0,69% до 4,2%; в классе RC2 от 5,7% до 8,5% в решениях, где количество транспортных средств совпадает с лучшими решениями. В остальных решениях, где транспортных средств на одно больше, общее пройденное расстояние меньше, чем в исторически лучших решениях.
Описана тестовая система, которая эмулирует динамические запросы в течение выполнения (решения задачи) полученного промежуточного решения. Данная система состоит из следующих подсистем (модулей):
модуль получения текущего решения (МПТР) - получает запросы клиентов от модулей формирования статических и динамических запросов, текущее положение транспортных средств и формирует решение задачи.
модуль статических запросов - формирует и передает в МПТР запросы, которые известны заранее, до начала решения задачи в момент времени t = О, этот модуль работает только на начальном этапе;
модуль формирования динамических запросов - предает в МПТР запросы от клиентов, которые поступают уже в процессе выполнения-решения полученного на предыдущем этапе;
модуль выполнения текущего решения (МВТР) - выполняет текущее решение, полученное от МПТР, формирует и передает в МПТР текущее положение транспортных средств.
Работа системы происходит следующим образом. Некоторое количество запросов от клиентов, известно заранее - это статические запросы, на основе данных запросов МПТР формирует решение, которое передается на исполнение МВТР. Выполнение решения происходит до тех пор, пока не будут получены новые запросы клиентов или не будут отменены старые, как только это происходит, информация об изменении количества запросов передается в МПТР. МПТР запрашивает из МВТР текущее положение транспортных средств. При этом считается, что если транспортное средство движется к клиенту номер / то, оно должно обязательно обслужить данного клиента и начальным условием положения для данного транспортного средства будет являться клиент /. Таким образом, МПТР получает текущие положения для всех транспортных средств, которые будут являться начальными условиями для формирования нового текущего
решения. Формируется новое решение и передается на выполнение МВТР. Это продолжается до тех пор, пока все клиенты не будут обслужены или не истечет временной период выполнения решения (обслуживания клиентов). Следовательно, решение изменяется по мере изменения числа запросов с учетом текущего положения транспортных средств.
Тестирование и экспериментальное обоснование разработанного комплекса ГА для ТЗ доказали практическую эффективность разработанных ГА и целесообразность применения теоретических разработок на практике. Результаты тестов по задачам всех видов показали, что данный алгоритм, в отличие от других известных алгоритмов, дает решение, в котором количество транспортных средств и общее пройденное расстояние сбалансировано. Выражается это в том, что добавление нескольких транспортных средств приводит к значительному уменьшению общего пройденного расстояния и, как следствие, к уменьшению затрат на топливо и амортизацию транспортных средств, уменьшению нагрузки на водителей. Также можно отметить, что уменьшается и вероятность аварий, т.к. она тем выше, чем больше пройденное расстояние.
Результаты решения динамических ТЗ с ограничением по времени при имитации появления запросов в процессе выполнения решения показали, что общее пройденное расстояние получаемого решения увеличивается незначительно, даже при большом количестве динамических запросов.
В заключении изложены основные выводы и результаты диссертационной работы. В приложении даны копии свидетельств о регистрации программ и таблицы с результатами экспериментов.
Анализ методов решения транспортных задач с ограничением по времени
Методы решения ТЗ в целом и ТЗ с ограничением по времени можно разделить на точные (exact approaches), эвристические (heuristic aproaches) и метаэвристические (metaheuristics) [1-3,7]. Далее рассмотрим методы, применяемые при решении ТЗ с ограничением по времени, придерживаясь именно этой классификации. ТЗ с ограничением по времени относится к классу yVP-трудных задач; точные методы решения такого класса задач основаны на полном переборе всех возможных решений. Поэтому в связи с большими временными затратами данные методы применяются только для решения задач небольшой (количество клиентов меньше 50) размерности [1,6]. Обзор применения данных методов дан в литературе [2,29-32]. Т.к. данные методы не эффективны для решения задач большой размерности, то в данном обзоре они рассматриваться не будут, а основное внимание уделим эвристическим и метаэвристическим методам [33]. Такое разделение-достаточно условно, данные методы трудно разделить, потому что метаэвристические методы являются надстройкой над эвристическими [1]. Сравнение методов решения будет производиться по результатам решения тестовых задач Соломона [34-35], опубликованных в литературе [7, 36-38].
Эвристические методы. Большинство эвристических методов основано на следующей стратегии: конструирование начального решения (плана перевозок) и последующие попытки улучшения данного решения с использованием различных техник локального и глобального поиска [39]. Исходя из этого, сначала рассмотрим методы, используемые для построения начального решения, - эвристические методы конструирования маршрута (route construction heuristics). При построении начального решения (далее текущего маршрута) данные методы решают две ключевые задачи. Какого клиента, из числа ещё не обслуженных, выбрать для вставки в текущий маршрут? Как выбрать место вставки клиента в текущий маршрут? [2] Методы конструирования маршрута делятся на последовательные (строится один маршрут) и параллельные (одновременно строятся несколько маршрутов) [1-2, 7]. Суть данных методов состоит в следующем. Построение маршрута осуществляется путем последовательного добавления еще не обслуженных клиентов к текущему маршруту (вставки клиентов в текущий маршрут). Для инициализации каждого нового маршрута по некоторому критерию выбирается «первый» клиент (seed customer) из числа еще не обслуженных клиентов (un-routed customers) для включения его в текущий маршрут (partial route) [3]. Например, выбирается клиент, наиболее удаленный от точки начала маршрута - депо. Далее оставшиеся клиенты оцениваются по определенному критерию, согласно этому критерию выбирается лучший из них и добавляется к текущему маршруту. Добавление клиента к маршруту не должно нарушать ограничений задачи (временных ограничений, ограничений на грузоподъемность автомобиля). Если нет допустимых клиентов (не обслуженных клиентов, которых можно добавить к текущему маршруту без нарушения ограничений задачи), то начинается новый маршрут. Если все клиенты включены в маршруты и не осталось не обслуженных клиентов, то алгоритм завершается.
Приведем известный метод конструирования маршрута, предложенный Соломоном в 1987 году [34]. Инициализация маршрута начинается выбором первого клиента для включения в маршрут. Из числа еще не обслуженных клиентов выбирается либо клиент, наиболее удаленный от депо, либо клиент, которого нужно обслужить раньше всех (согласно ограничениям по времени). Затем каждый допустимый не обслуженный клиент и оценивается на предмет вставки его между любыми смежными клиентами текущего маршрута по двум критериям: cj(in,j) и c2(i, u,j); лучший клиент согласно этим критериям вставляется в маршрут между клиентами / иу.
Первый критерий определяет лучшее место вставки в текущий маршрут, т.е. клиентов / и j, между которыми будет вставлен клиент и, и состоит из оценки добавочного расстояния си(і, и, J) и времени c]2(i, u,j) при добавлении клиента и между клиентами / и j. Для каждого клиента и критерий су(7, и, j) вычисляется следующим образом:
Где diu, dUJ; dy - расстояния между клиентами і и и, и и j, і и j соответственно.
Второй критерий определяется для каждого клиента и при условии, что он будет вставлен на маршрут между клиентами / и j, определенными на основе первого критерия, следующим образом:
c2(i, u,j) =Xd0u - с j (і, u,j), \ 0. Вычислительная сложность алгоритма Соломона согласно [3] оценивается как 0(п). Данный алгоритм используется в последующих алгоритмах для их инициализации (например, для построения начального -опорного решения с целью его последующего улучшения - метод улучшения маршрута).
В 1993 году был предложен метод параллельного конструирования маршрута. Данный метод основан на описанном выше методе; отличие параллельного метода от последовательного в том, что оценка вставки каждого клиента в маршрут происходит не последовательно, а параллельно (одновременно), следовательно, время выполнения алгоритма сокращается [7]. На основе метода конструирования Соломона был разработан новый метод конструирования, который использовал новую эвристику для вставки клиентов (greedy look-ahead heuristic) [7]. Данный метод более затратен по временным ресурсам, но дает лучшее решение, чем метод Соломона в смысле целевой функции. В таблице 1.1 представлены результаты решения тестовых задач Соломона методами конструирования [7].
Постановка транспортной задачи линейного программирования
Цель данной главы - показать эффективность применения ГА к решению ТЗ, оценить достоинства и недостатки методики применения основных генетических операторов. Для достижения этой цели в данной главе будет разработан ГА для решения линейных ТЗ большой размерности, разработаны и применены основные ГО, специально ориентированные для работы с решением линейной ТЗ.
Сначала дадим математическую постановку линейной ТЗ или ТЗ линейного программирования согласно [69-71].
Для задач линейного программирования характерно, что:
показатель эффективности (целевая функция) L линейно зависит от ЭЛемеНТОВ РЄШЄНИЯХ;, Х2, ..., Хп\
ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно Xj, Х2, ..., хп.
Классическая ТЗ линейного программирования формулируется следующим образом. Имеется т пунктов отправления: Ah А2, ..., Ат, в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно а1г а2, ..., ат единиц. Кроме того, имеется п пунктов назначения: Bh В2, ..., Вп, подавших заявки соответственно на Ъ}, Ъ2, .... Ъп единиц товара.
Предполагается, что сумма всех заявок равна сумме всех запасов:
Известна стоимость су перевозки единицы товара от каждого пункта отправления At до каждого пункта назначения Bj. Таблица (матрица) стоимостей перевозки Су задана:
Требуется составить такой план перевозок, при котором все заявки были бы выполнены, и при этом общая стоимость всех перевозок была минимальной.
При такой постановке задачи показателем эффективности плана перевозок является стоимость , поэтому поставленную задачу точнее называют транспортной задачей по критерию стоимости.
Дадим этой задаче математическую формулировку. Обозначим Ху -количество груза, отправляемого из /-го пункта отправления А{ в у -й пункт назначения Bj (і = 1, ..., т; j = 1, ..., п). Неотрицательные переменные хц, Xj2, , хтп (число которых, очевидно, равно т п) должны удовлетворять следующим условиям:
суммарное количество груза, направляемого из каждого пункта отправления во все пункт назначения, должно быть равно запасу груза в данном пункте. Суммарное количество груза, доставляемое в каждый пункт назначения изо всех пунктов отправления, должно быть равно заявке, поданной данным пунктом;
суммарная стоимость всех перевозок, т. е. сумма величин ху, умноженных на соответствующие стоимости си, должна быть минимальной;
Однако, эти две задачи искусственно сводятся к задаче с правильным балансом [69].
Известно, что в задаче линейного программирования оптимальное решение достигается в одной из вершин области допустимых решений (ОДР), где, по крайней мере, к переменных обращаются в нуль. В данном случае для оптимального плана перевозок, по крайней мере, к = (т - \){п - 1) значений Ху должны быть равны нулю [70]. Для решения транспортных задач разработаны эффективные методы линейного программирования [70]. Однако все эти методы решает задачу путем частичного перебора множества всех положительных базисных решений. Количество всех базисных решений не превосходит[69]:
Данные типы алгоритмов являются экспоненциальными и имеют свойства экспоненциального роста времени выполнения от размерности задачи.
Далее будет представлен новый ГА для решения линейной ТЗ [72], который имеет линейную зависимость времени выполнения от количества входных переменных. Следовательно, асимптотика роста времени выполнения ГА при достаточно большой размерности задачи меньше, чем у алгоритмов линейного программирования. Если у одного алгоритма асимптотика роста меньше, чем у другого, то в большинстве случаев он будет эффективнее для всех входов, кроме совсем коротких [73]. Для представленного ниже ГА были разработаны новые операторы инициализации и кроссинговера отражающие специфику постановки линейной ТЗ. Далее будут рассмотрен ГА и подробно описаны все операторы, разработанные для данного ГА.
Структура разработанного генетического алгоритма
Генетические алгоритмы (ГА) являются случайно-направленными поисковыми методами и успешно применяются для решения задач транспортного типа [78-80]. В общем случае структура ГА состоит из оператора инициализации, кроссинговера и мутации.[74]. Далее приведен новый ГА решения ТЗ с ограничением по времени. В структуру данного ГА введен дополнительный оператор мутации, который позволяет расширить область поиска за счет введения в популяцию существенно новых решений. Это позволяет предотвратить преждевременную сходимость алгоритма и повысить качество получаемого решения [81-84].
Структура нового генетического алгоритма разработанного для решения ТЗ с ограничением по времени
Для пояснения работы разработанного ГА введем обозначения:
Nit - максимальное количество итераций алгоритма;
Np - размер популяции решений;
Pk - вероятность кроссинговера;
Рт - вероятность мутации;
F_Bestcur - ЦФ функция лучшего решения в популяции на данной итерации алгоритма;
F_Bestpiv - ЦФ функция лучшего решения в популяции на предыдущей итерации алгоритма;
Countst - количество итераций, в течение которых ЦФ лучшего решения в популяции не менялась. С учетом этих обозначений структура нового генетического алгоритма, разработанного для решения ТЗ с ограничением по времени, будет иметь вид.
1) Создаем популяцию решений размера Np. Для этого Np раз применяем оператор Инициализации.
2) Оцениваем ЦФ каждого решения в популяции.
3) Сортируем решения согласно ЦФ. Решения с меньшей ЦФ будут занимать первые позиции.
4) Присваиваем переменной / значение 0.
Присваиваем переменной Countst значение 0. Присваиваем переменной F_Bestcur значение 0. Присваиваем переменной F_Bestpn. значение 0.
5) Пока / меньше Nlt выполняем следующие действия.
Begin
6) Если Countst Nit I 5 переходи к пункту 14.
7) Присваиваем переменнойу значение 0. покау меньше Np выполняем следующие действия: begin
Выбираем решение с использованием оператора селекции. С вероятностью Рк применяем оператор кроссинговера. Полученное решение-потомок копируем в новую популяцию потомков
С вероятностью Рт применяем оператор мутации ОМ_1 к решению-потомку, полученному на предыдущем этапе.
Если Coimtst 10, то к решению-потомку применяем оператор мутации ОМ_2. end
8) Заменяем основную популяцию новой.
9) Оцениваем ЦФ каждого решения в популяции. 10) Сортируем решения согласно ЦФ. Решения с меньшей ЦФ будут занимать первые позиции.
11) Присваиваем переменной F_Bestcur значение ЦФ решения занимающего в популяции первую позицию (лучшее решение).
12) Если F_Bestcur = F_Bestprv, то увеличиваем значение переменной Countst на 1, т. е. Coimtst = Countst + 1.
13) Присваиваем переменной F_Bestprv значение F_Bestcur. End
14) Выход.
Существенная особенность данного алгоритма - это добавление второго оператора мутации. Этот оператор позволяет разнообразить популяцию новыми решениями в том случае, когда значение ЦФ лучшего решения в популяции не изменялось на протяжении определенного количества итераций, тем самым обеспечивая выход из локального минимума, с которым не может справиться первый оператор мутации.
Оценка временной сложности алгоритма будет произведена ниже после детального описания операторов, входящих в состав алгоритма.
На рисунке 3.1 приведена структурная схема работы алгоритма. Основными особенностями разработанного алгоритма является его простота, что будет отражено ниже в оценке сложности алгоритма, и использование дополнительного оператора мутации при «застаивании» процесса поиска, т.е. дополнительный оператор не используется в регулярном цикле работы алгоритма, а применяется лишь в том случае, когда лучшее значение ЦФ в популяции решений не изменялось в течение определенного (заранее заданного) количества итераций (Countst). Алгоритм заканчивает свою работу, если выполнено заданное максимальное количество итераций (Nit) или если значение счетчика «застаивания» процесса поиска достигло определенного значения, рассчитываемого исходя из максимального количества итераций.
Далее будут описаны специально разработанные или адаптированные для данного ГА основные генетические операторы: инициализации, кроссинговера, мутации, а также способ кодирования решения, применяемый в данном ГА.
Описание программной среды для тестирования алгоритма решения линейных транспортных задач и результаты экспериментов
В данном пункте будет описана программа, разработанная для тестирования ГА решения линейных ТЗ, представленного в Главе 2. Будут представлены и проанализированы результаты экспериментов по решению, с использованием данной программы, тестовых задач описанных выше. Программа написана на языке C++, среда разработки Microsoft Visual C++ б.О.Программа предназначена для запуска под операционными системами Windows 2000/XP/Vista. Главное окно программы показано на рисунке 4.7.
Свидетельство об официальной регистрации программы представлено в приложении 1.
Fte Edc view в Рис.4.7. Окно программы решения линейных ТЗ с использованием ГА (условие задачи slOdlO_l)
Программа позволяет с помощью меню Файл—Юткрыть или кнопки на панели инструментов U J открыть созданный ранее файл условия линейной ТЗ задачи. Визуализация файла происходит в главном окне программы, на рисунке 4.7 показано условие задачи slOdlO_l,название задачи отображается в заголовке окна программы, матрица стоимостей, вектор запасов товара (справа) и вектор заявок (снизу). Программа позволяет полностью задать все параметры ГА. В верхнем окне программы расположены поля, в которых в удобном для пользователя виде можно изменять параметры ГА и запустить на выполнение ГА, нажатием кнопки — И—I, для оценки влияния данных параметров на работу ГА и результат полученного решения. Для изменения доступны следующие параметры; размер популяции (поле Size POP.); оператор селекции (поле SELECTOIN) - элитный (Elite) или на основе колеса рулетки (Roulette); оператор кроссинговера (поле Crossover) - Crossover_l; вероятность оператора кроссинговера в % (поле CROSS %), вероятность оператора мутации в % (поле MUTAT %); количество итераций алгоритма (поле ITERATION). Основной целью экспериментов является исследовать влияние параметров ГА на работу ГА и оценить качество получаемого решения. Для этих целей в результате работы программы выводится график зависимости изменения ЦФ «лучшего» решения в популяции от номера итерации; найденное значение цены лучшего плана; время работы алгоритма (с), время выполнения одной итерации (с) и лучшее решение, найденное в процессе работы алгоритма. На рисунке 4.8 показано окно программы с результатами решения задачи, условия которой представлены на рисунке 4.7.
Окно программы решения линейных ТЗ с использованием ГА (результаты решения задачи sI0dI0_l)
График зависимости изменения ЦФ от номера итерации позволяет оценить динамику работы ГА, а выводимый результат оценить его качество.
Первый этап исследования поведения ГА состоит в подборе параметров для исходных задач, при которых алгоритм сходится наиболее близко в 3-х подряд запусках, к определенному заранее известному (при решении данной задачи другими алгоритмами) значению. Для поиска оптимального значения использовалась программа tora.exe, свободно распространяемая и прилагаемая и к книге [71]. Т.к. программа tora.exe позволяет решать матрицы, максимальный размер которых составляет 18x18, то именно этим размером были ограничены тестовые задачи, используемые в первом этапе. Для тестирования были взяты следующие тестовые задачи, полученные описанным выше способом: s5d5_l, s5d5_2, s5d5_3, s8d8_l, s8d8_2, s8d8_3, slOdlO_l, sl0dl0_2, slOdlO, sl2dl2_l, sl2dl2_2, sl2dl2_3, sl4dl4_l, sl4dl4_25 sl4dl4_3, sl6dl6_l, sl6dl6_2, sl6dl6_3, sl8dl8_l, sl8dl8_3, sl8dl8_4. Данные файлы, с помощью вспомогательной программы-конвертатора, были переведены в формат, с которым работает программа tora.exe и найденное в результате оптимальное решение использовалось как цель для разработанного ГА. По результатам запуска программы реализующей разработанный ГА выяснялось, при каких параметрах ГА (количество итераций и размер популяции) устойчиво сходится (в течение 3-х запусков подряд) к оптимальному или близкому к оптимальному значению. Также оценивалось время работы алгоритма. Основные характеристики ЭВМ, на которой проводились эксперименты следующие: процессор: AMD Athlon(tm) 64 Х2 2,10 ГГц; оперативная память: 2,00 ГБ. Данные, полученные в результате экспериментов, приведены в приложении 2.
