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

• Автор: Емельянова, Татьяна Сергеевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Таганрог
• Количество страниц: 165 с. : ил.

СОДЕРЖАНИЕ
СОДЕРЖАНИЕ.
ВВЕДЕНИЕ.

ГЛАВА 1 СОСТОЯНИЕ ПРОБЛЕМЫ И АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ

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

1.2 Динамическая транспортная задача. Проблема оценки динамической составляющей транспортной задачи

1.3 Анализ методов решения транспортных задач с ограничением по времени.

1.4 Выводы
ГЛАВА 2 РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РЕШЕНИЯ ЛИНЕЙНЫХ ТРАНСПОРТНЫХ ЗАДАЧ БОЛЬШОЙ РАЗМЕРНОСТИ

2.1 Постановка транспортной задачи линейного программирования

2.2 Определение и основные свойства генетических алгоритмов.

2.3 Структура генетического алгоритма.
2.4 Конструирование начальной популяции.
2.5 Операторы селекции
2.6 Оператор кроссинговера
2.7 Оператор мутации
2.8 Выводы
ГЛАВА 3 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ С ОГРАНИЧЕНИЕМ ПО ВРЕМЕНИ
3.1 Математическая постановка транспортной задачи с ограничением но времени.
3.2 Структура разработанного генетического алгоритма
3.3 Кодирование решения.
3.4 Оператор инициализации
3.5 Оператор кроссинговера
3.6 Операторы мутации.
3.7 Фундаментальная теорема ГА
3.8 Оценка временной сложности алгоритма
3.9 Распараллеливание алгоритма для многоядерных систем.
3. Применение разработанного ГА для решения динамической транспортной задачи с ограничением по времени.
3. Выводы
ГЛАВА 4 ТЕСТИРОВАНИЕ И ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ.
4.1 Описание тестовых моделей транспортных задач
4.2 Описание программной среды для тестирования алгоритма решения линейных транспортных задач и результаты экспериментов.
4.3 Описание программной среды для тестирования алгоритма решения транспортных задач с ограничением по времени и результаты экспериментов
4.4 Исследование влияния динамической составляющей на решение транспортных задач с ограничением по времени.
4.5 Выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


ЦФ уменьшается на каждой генерации ГА, тюка не сходится к определенному значению, которое будет являться наилучшим для данной задачи. Исследования показали, что данный оператор кроссинговера эффективен только при больших (более 0) размерах популяции решений; при малых размерах популяции, применение одного оператора мутации, является более эффективным (по качеству получаемого решения и временным затратам). Однако представленный ГА направлен па решения именно задач большой размерности (матрица стоимостей порядка 0x0), где размер популяции решений достигает ; в этом случае применение данного оператора позволяет получить лучшее решение. Т.е. ТЗ, является оправданным с точки зрения вычислительной простоты и качества получаемого решения. Для начального построения популяции решений был выбран путь, в котором берется наиболее простои метод конструирования решения (в данном случае метод «северо-западного» угла) и адаптируется для применения в ГА. Это позволило на первом этапе формирования популяции решений получить большое разнообразие решений при начале работы ГА. Обеспечение большого разнообразия в начальной популяции решений является важным условием успешной работы ГА. Предложенный оператор инициализации успешно справляется с этой задачей. Исходя из всего вышесказанного, можно сделать следующие выводы. Представленный ГА вместе со специально разработанными ГО успешно решает линейные ТЗ большой размерности. Данный ГА позволяет найти достаточно хорошее решение за достаточно малое время. Время работы алгоритма линейно зависит от размерности задачи п* т. Приемы распараллеливания алгоритма позволяют уменьшить это время в 2, 3, 4-е и более раз в зависимости от количества процессорных ядер в системе. В третьей главе представлены математическая модель ТЗ с ограничением по времени и новый ГА решения данной задачи, позволяющий работать как со статическими, так и с динамическими запросами клиентов. G = (N, А), . V- множество вершин, соответствующих набору клиентов (customers) (вершины 1, 2, . А - набор дуг, соединяющих вершины графа. Xjf -переменная, принимающая значения {0> /} и характеризующая направление движения автомобиля: XtJk = 1 - от клиента / к клиенту у, Ху - О - в обратном направлении. I d,Zxl,? ZX^-'ZX^O. VheC. St