Главная » 2014 » Август » 20 » Скачать Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов. Емельянова, Татьяна бесплатно
06:54
Скачать Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов. Емельянова, Татьяна бесплатно
Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов
Диссертация
Автор: Емельянова, Татьяна Сергеевна
Название: Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов
Справка: Емельянова, Татьяна Сергеевна. Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов : диссертация кандидата технических наук : 05.13.01 / Емельянова Татьяна Сергеевна; [Место защиты: Юж. федер. ун-т] - Таганрог, 2009 - Количество страниц: 165 с. ил. Таганрог, 2009 165 c. :
Объем: 165 стр.
Информация: Таганрог, 2009
Содержание:
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1 СОСТОЯНИЕ ПРОБЛЕМЫ И АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
11 Классификация транспортных задач Транспортные задачи с ограничением по времени
12 Динамическая транспортная задача Проблема оценки динамической составляющей транспортной задачи
13 Анализ методов решения транспортных задач с ограничением по времени
14 Выводы
ГЛАВА 2 РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РЕШЕНИЯ ЛИНЕЙНЫХ ТРАНСПОРТНЫХ ЗАДАЧ БОЛЬШОЙ РАЗМЕРНОСТИ
21 Постановка транспортной задачи линейного программирования
22 Определение и основные свойства генетических алгоритмов
23 Структура генетического алгоритма
24 Конструирование начальной популяции
25 Операторы селекции
26 Оператор кроссинговера
27 Оператор мутации
28 Выводы
ГЛАВА 3 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ С ОГРАНИЧЕНИЕМ ПО ВРЕМЕНИ
31 Математическая постановка транспортной задачи с ограничением по времени
32 Структура разработанного генетического алгоритма
33 Кодирование решения
34 Оператор инициализации
35 Оператор кроссинговера
36 Операторы мутации
37 Фундаментальная теорема ГА
38 Оценка временной сложности алгоритма
39 Распараллеливание алгоритма для многоядерных систем
310 Применение разработанного ГА для решения динамической транспортной задачи с ограничением по времени
311 Выводы
ГЛАВА 4 ТЕСТИРОВАНИЕ И ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ
41 Описание тестовых моделей транспортных задач
42 Описание программной среды для тестирования алгоритма решения линейных транспортных задач и результаты экспериментов
43 Описание программной среды для тестирования алгоритма решения транспортных задач с ограничением по времени и результаты экспериментов
44 Исследование влияния динамической составляющей на решение транспортных задач с ограничением по времени
45 Выводы
Введение:
Актуальность работы
Транспортировка важная область жизнедеятельности человека. Перевозка людей и грузов (от пищевых до промышленных) — это неотъемлемая часть жизни современного человека. Так расходы на транспортировку различных видов грузов составляют в Великобритании -15%, во Франции — 9%, в Дании - 15% от общих национальных расходов [1]. Необходимость решения таких транспортных задач, с минимизацией издержек на перевозку, определяется большим экономическим эффектом при нахождении лучшего решения, т.к. это явно увеличивает прибыль предприятия. Применение компьютерных методов решения задач позволяет увеличить скорость принятия решений и повысить эффективность найденных решений. Поэтому требуются алгоритмы способные исполняться на массово доступных вычислительных средствах (персональных компьютерах и малых серверах). Разработка новых алгоритмов должна учитывать структуру вычислительных средств, на которых будут исполняться программы (реализующие данные алгоритмы). В настоящее время основные тенденции развития компьютерной техники таковы: за последние несколько лет резко снизился рост частоты процессоров, появилась возможность хранить в памяти огромные объемы информации. Снижение роста быстродействия процессоров произошло из-за достижения технологического предела нанометровых технологий, однако появилась возможность разместить на одном кристалле большее количество вычислительных элементов (процессорных ядер). Польза от использования этих ядер будет только в том случае, если исполняемая программа (и её алгоритм) является параллельным, в противном случае будет использоваться (работать) только одно ядро, а остальные будут простаивать. Известно, что классические алгоритмы не имеют возможности распараллеливания и имеют экспоненциальный рост времени выполнения от размерности задачи. Т.е. количество математических действий (команд) растет экспоненциально, а развитие процессорных элементов (увеличение тактовой частоты, уменьшение количества тактов выполнения команд, задержка на выборку данных из памяти) не компенсируют растущие (с увеличением размерности задачи) потребности классических алгоритмов. Точные методы решения транспортных задач (ТЗ), позволяют найти решение только для задач с малым количеством клиентов (т.е. до 50-ти клиентов [2]). Для решения задач большой размерности точные методы являются не эффективными в связи с их большими временными затратами. Однако, именно сейчас, требуется эффективные алгоритмы решения задач большой размерности, т.к. в настоящее время наблюдается процессы глобализации в экономике. В частности, это приводит к слиянию множества мелких и средних компаний в крупные корпорации, которые пытаются уменьшить издержки путем сокращения количества однотипных объектов инфраструктуры (складов, ремонтных мастерских и пр.) преобразовывая их в крупные объекты регионального значения. Что приводит к необходимости планирования транспортных операций с большим количеством клиентов, т.е. к ТЗ большой размерности. Таким образом, решение ТЗ большой размерности является актуальной задачей. Одним из классов ТЗ является ТЗ с ограничением по времени. Данный класс задач является сложным для решения, но необходимым и широко применяемым на практике. Моделью ТЗ с ограничением по времени описываются: банковские и почтовые доставки, перевозка людей, сбор промышленных и бытовых отходов, доставка продуктов, доставка топлива и материалов на предприятия. На настоящий момент в иностранной литературе предложено множество алгоритмов решения данного класса задач, к сожалению, в нашей стране методы транспортной логистики только начинают свое развитие. Практическим алгоритмам по решению ТЗ с ограничением посвящено множество работ следующих ученых: Solomon, Tompson, Psaraflis, Russell, Antes, Derigs, Cordone, Wolfer-Calv, Caseau, Laburthe, Braysy, Rochat, Taillard, Chiang,
Cordeau, Thangiah, Homberger, Gehring, Mester, Barkaoui, Csiszar, Van Henlenryck и др.
Важным недостатком этих алгоритмов, является то, что они не предназначены для решения задач с изменяющимся количеством запросов от клиентов, что актуально на сегодняшний день в связи с развитием средств мобильной связи, дающей возможность отслеживать маршрут автомобиля и передавать измененный маршрут. Эти возможности не учитываются в алгоритмах предложенных вышеперечисленными учеными. Поэтому задача разработки комплекса алгоритмов решения ТЗ с ограничением по времени и адаптация данного алгоритма к динамическому изменению запросов клиентов, представляется актуальной научной задачей.
Цель диссертации
Целью диссертационной работы является разработка комплекса алгоритмов интеллектуальной поддержки при принятии решений в транспортных системах, оценка и анализ их вычислительной сложности.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Проведение сравнительного анализа эффективности существующих методов решения ТЗ.
2. Построение генетических операторов отражающих специфику решаемой ТЗ (линейной или с ограничением по времени).
3. Разработка специального комбинированного генетического алгоритма (ГА) для решения статической ТЗ с ограничением по времени.
4. Разработка модифицированного ГА для решения динамической ТЗ.
5. Разработка программно-алгоритмических модулей для решения транспортных задач на основе разработанных алгоритмов, ориентированных на выполнение в многоядерных системах.
Научная новизна полученных в диссертации основных результатов заключается в следующем:
1. Предложены новые принципы построения генетических операторов для применения в ГА решения транспортных задач, на основе этих принципов разработаны новые схемы операторов инициализации и мутации.
2. Разработаны новые модификации ГА для решения статической и динамической транспортной задачи с ограничением по времени.
3. Предложен метод распараллеливания ГА для применения его в многоядерных системах, что позволило получить увеличение быстродействия.
Результаты выносимые на защиту
1. Генетические операторы для решения линейной транспортной задачи большой размерности (порядка 100x100).
2. Новый ГА и генетические операторы для решения транспортных задач с ограничением по времени.
3. Модифицированный ГА для решения динамической транспортной задачи, позволяющий реагировать на изменение (появление/удаление) запросов от клиентов при исполнении полученного решения, т. е. изменять решение в процессе его выполнения с целью уменьшения транспортных затрат.
4. Метод распараллеливания ГА ориентированный на выполнение разработанных алгоритмов на многоядерной вычислительной базе.
Практическая значимость
На основе разработанных алгоритмов создан программно-алгоритмический комплекс для решения транспортных задач с ограничением по времени. При построении программного комплекса использовался объектно-ориентированный язык С++ и среда разработки Microsoft Visual
С++ 6.0. Отладка и тестирование проводилось на ЭВМ типа IBM PC, с процессором AMD Athlon 64 Х2 5400+, 2.8 ГГц, ОЗУ 3ГБ. Отличительная особенность разработанного программного комплекса — это эффективное использование многоядерной вычислительной системы, что позволило сократить время решения транспортных задач в два раза.
Внедрение результатов работы
Основные результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском технологическом институте Южного федерального университета: в госбюджетной работе «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», в гранте РФФИ «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования». Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Прикладная информатика».
Методы исследования
В работе использовались методы системного анализа, исследования операций, линейного программирования, эвристические методы оптимизации, генетические алгоритмы.
Апробация работы
Основные результаты, полученные в ходе работы, докладывались и обсуждались на:
1. Всероссийских научных школах-семинарах молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки», Таганрог, 2007 и 2008 годы.
2. Международной научно-технической конференции «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD02008), Геленжик, 2008.
3. IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления», Таганрог, 2008.
4. Второй Всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления» (НСМВ-2008), Ульяновск, 2008.
5. XI Национальной конференции по искусственному интеллекту с международным участием (КИИ-08), Дубна 2008.
Публикации
Основные положения и результаты диссертационной работы опубликованы в 14 источниках, включающих 6 статей, 6 материалов конференций и семинаров, 2 свидетельства о регистрации программ. Две работы из них опубликованы в рецензируемом журнале из списка ВАК.
Объем и структура диссертации
Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 102 наименования и 6 приложений. Основной текст диссертации изложен на 150 страницах, включая 41 рисунок и 6 таблиц.
