Как видно из рисунка 3, дополнительные потоки не изменяют структуру ГА, а только дополняют ее. Программа автоматически запрашивает у системы количество процессорных ядер и запускает, если это возможно, дополнительные потоки. Пример работы потока представлен на рисунке 4. Количество запускаемых при решении задачи потоков равно количеству ядер процессора. В холе экспериментов при выполнении на 2-ядерном процессоре и запуске второго дополнительного потока при создании начальной популяции и при выполнении главного цикла ГА время выполнения программы практически уменьшалось в два раза. Это подтверждалось теоретическими расчетами, поскольку доля не распараллеленного кода достаточно мала. Согласно формуле Амдала, которая иллюстрирует ограничение роста производительности системы с увеличением количества вычислителей (в данном случае процессорных ядер) полученное увеличение быстродействия вычисляется по формуле  , где  – доля последовательных вычислений,  – количество процессорных ядер. При  ,  . В настоящее время практически все новые процессоры имеют многоядерную архитектуру, и данный факт неуместно игнорировать при разработке новых алгоритмов, в связи с чем, и была разработана эффективная многопоточная архитектура ГА.
В четвертой главе рассмотрена разработка программных модулей и тестовых систем для оценки практической ценности разработанных алгоритмов. Эксперименты проводились для тестовых задач Соломона с различным расположением клиентов: равномерным (R), кластерным (C) и смешанным (RC) и различными по жесткости временными ограничениями класс 1 и 2, общее количество задач 56. В каждой задаче одно депо и 100 клиентов. Для каждого клиента заданы 7-мь величин: номер клиента, координата X, координата Y, запрос количества товара в условных единицах, нижняя граница временного окна, верхняя граница временного окна, время, в течение которого, происходит обслуживание клиента. Границы временного окна показывают промежуток времени, в который может быть обслужен соответствующий клиент. Если транспортное средство пришло к клиенту до начала нижней границы временного окна, то оно должно ожидать пока не подойдет время обслуживание, что будет вносить задержку (увеличивать время простоя) транспортного средства. При перемещении от одного клиента к другому время перемещения в данных тестовых задачах берется равным расстоянию между клиентами, т.е. скорость транспортных средств считается постоянной. Первичная цель при решении данных задач – минимизировать общее количество транспортных средств. Вторичная минимизировать общее пройденное расстояние. Третья цель минимизировать время простоя транспортных средств.
Результаты экспериментов показывают, что разница полученных результатов с лучшими решениями в классе С2 составляет 0%; в классе С1 от 0% до 7,3%; в классе R1 от 0% до 2,3%; в классе R2 от 3,7% до 9,4%; в классе RС1 от 0,69% до 4,2%; в классе RС2 от 5,7% до 8,5% в решениях, где количество транспортных средств совпадает с лучшими решениями. В остальных решениях, где транспортных средств на одно больше, общее пройденное расстояние меньше, чем в исторически лучших решениях.
Известно что, исторически лучшие решения найдены различными алгоритмами, т.е. нет алгоритма который хорошо решает задачи всех классов, поэтому для оценки качества получаемого решения используют сравнение общего количества транспортных средств и суммарного пройденного расстояния. В таблице представленной ниже приведено сравнение этих данных, для разработанного алгоритма и для других известных алгоритмов. Решения для сравнения были подобраны таким образом, чтобы комплексно оценить полученные решения, как количество транспортных средств, так и общее пройденное расстояния, т.к. эти две переменные являются критериями оптимальности полученных решений. Важно было не только решение, при котором количество транспортных средств минимально, но и решение
при котором получено минимальное пройденное расстояние, баланс между количеством транспортных средств и расстоянием.
Автор алгоритма и год
|
Количество машин
|
Общее расстояние
|
Рассель (Russell), 1995.
|
424
|
65827
|
Кордон (Cordone), 1998.
|
422
|
58481
|
Касеу (Caseau), 1999.
|
420
|
58927
|
Ви Кит (Wee Kit) и др. 2001.
|
432
|
57265
|
Хомбергер (Homberger) и др. 2001.
|
406
|
57641
|
Джанг (Jung) и др. 2002.
|
486
|
54779
|
Бент (Bent) и др. 2004.
|
405
|
57273
|
Хомбергер (Homberger) и др. 2005.
|
405
|
57308
|
Босилье (Le Bouthillier) и др. 2005.
|
407
|
57412
|
Цисзар (Csiszár) 2007.
|
405
|
58239
|
Разработанный ГА, 2009
|
420
|
55970
|
Результаты закрашенные серым разработанный алгоритм превосходит как по количеству транспортных средств, так и по общему пройденному расстоянию (т.е. в разработанном алгоритме данные величины меньше). Видно, что решение, полученное с помощью тестируемого алгоритма, имеет наименьшее пройденное расстояние из опубликованных алгоритмов и хотя количество транспортных средств больше, чем у некоторых алгоритмов, однако нет алгоритма, который бы получил меньшее общее расстояние при равном или меньшем количестве транспортных средств. Даже алгоритмы с большим количеством транспортных средств имеют большее суммарное пройденное расстояние, кроме алгоритма Джанга (Jung) 2002. Но, если взять за основу алгоритм Бента в котором достигается оптимальное решение по количеству транспортных средств и общему пройденному расстоянию и сравнить с алгоритмами, в которых пройденное расстояние меньше, а количество транспортных средств больше, то видно, что в алгоритме Ви Кита при увеличении транспортных средств на 27 (6%) получаем уменьшение расстояния всего на 0.014%, а в алгоритме Джанга при увеличении транспортных средств на 81 (20%) получаем уменьшение расстояния на 4%, в разработанном ГА при увеличении количества машин всего на 15 (3.7%) получаем уменьшение расстояния на 2.3%. Следовательно, можно сделать вывод, что разработанный ГА дает наилучшие решения с точки зрения баланса между количеством транспортных средств и общим пройденным расстоянием. Эта особенность данного алгоритма позволяет использовать его для поддержки принятия решений в интеллектуальных системах. На практике выгодно использовать немного больше транспортных средств, если при этом будет сокращаться время их использования (уменьшаться пройденное ими расстояние). Это позволит уменьшить расходы на горюче-смазочные материалы и на амортизацию автотранспорта.
Описана тестовая система, которая эмулирует динамические запросы в течение выполнения (решения задачи) полученного промежуточного решения. Структура тестовой системы представлена на рисунке 5.
|
Рис.5.Тестовая система для проверки алгоритмов решения динамических ТЗ.
|
Данная система состоит из следующих подсистем (модулей):
модуль получения текущего решения (МПТР)– получает запросы клиентов от модулей формирования статических и динамических запросов, текущее положение транспортных средств и формирует решение задачи.
модуль статических запросов – формирует и передает в МПТР запросы, которые известны заранее, до начала решения задачи в момент времени t = 0, этот модуль работает только на начальном этапе;
модуль формирования динамических запросов – предает в МПТР запросы от клиентов, которые поступают уже в процессе выполнения решения полученного на предыдущем этапе;
модуль выполнения текущего решения (МВТР) – выполняет текущее решение, полученное от МПТР, формирует и передает в МПТР текущее положение транспортных средств.
Работа системы происходит следующим образом. Некоторое количество запросов от клиентов, известно заранее – это статические запросы, на основе данных запросов МПТР формирует решение, которое передается на исполнение МВТР. Выполнение решения происходит до тех пор, пока не будут получены новые запросы клиентов или не будут отменены старые, как только это происходит, информация об изменении количества запросов передается в МПТР. МПТР запрашивает из МВТР текущее положение транспортных средств. При этом считается, что если транспортное средство движется к клиенту номер i то, оно должно обязательно обслужить данного клиента и начальным условием положения для данного транспортного средства будет являться клиент i. Таким образом, МПТР получает текущие положения для всех транспортных средств, которые будут являться начальными условиями для формирования нового текущего решения. Формируется новое решение и передается на выполнение МВТР. Это продолжается до тех пор, пока все клиенты не будут обслужены или не истечет временной период выполнения решения (обслуживания клиентов). Следовательно, решение изменяется по мере изменения числа запросов с учетом текущего положения транспортных средств.
Результаты решения динамических ТЗ с ограничением по времени при имитации появления запросов в процессе выполнения решения показали, что общее пройденное расстояние получаемого решения увеличивается незначительно, даже при большом количестве
динамических запросов. Для задач с количество динамических запросов 90% общее пройденное расстояние увеличивается на 15% по сравнению со статическими задачами.
Тестирование и экспериментальное обоснование разработанного комплекса ГА для ТЗ доказали практическую эффективность разработанных ГА и целесообразность применения теоретических разработок на практике. Результаты тестов по задачам всех видов показали, что данный алгоритм, в отличие от других известных алгоритмов, дает решение, в котором количество транспортных средств и общее пройденное расстояние сбалансировано. Выражается это в том, что добавление нескольких транспортных средств приводит к значительному уменьшению общего пройденного расстояния и, как следствие, к уменьшению затрат на топливо и амортизацию транспортных средств, уменьшению нагрузки на водителей. Разработанный алгоритм позволяет работать с динамическими запросами клиентов, что позволяет изменять решение в процессе его выполнения при получении новых запросов клиентов, таким образом, чтобы максимально сократить транспортные издержки.
В заключении изложены основные выводы и результаты диссертационной работы. В приложении даны копии свидетельств о регистрации программ, таблицы с результатами экспериментов и акты о внедрении результатов диссертационной работы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
Разработан ГА для решения транспортной задачи с ограничением по времени. Разработаны и модифицированы ГО. Анализ оценки времени работы нового ГА для решения транспортной задачи с ограничением по времени показал, что зависимость времени работы алгоритма от размерности задачи составляет O(n3).
Разработаны новые ГО отражающие специфику матричного представления линейной ТЗ. Оценка времени работы ГА для решения линейных транспортных задач показала пропорциональную зависимость от размерности задачи O(n).
Разработана процедура распараллеливания ГА с учетом применения данного алгоритма на многоядерных системах, которая позволяет сократить время выполнения алгоритма.
На основе предложенных алгоритмов разработаны программно-алгоритмические модули решения транспортных задач, отличающиеся тем, что позволяют эффективно использовать многоядерную вычислительную систему.
Анализ результатов экспериментов показал, что разработанный ГА дает наилучшие решения с точки зрения баланса между количеством транспортных средств и общим пройденным расстоянием.
Предложена модификация ГА для решения ТЗ с ограничением по времени с динамическими запросами клиентов. Для задач с количество динамических запросов 90% общее пройденное расстояние увеличивается на 15% по сравнению со статическими задачами.
Публикации по теме диссертации:
I. Публикации в центральных изданиях, включенных в перечень периодических изданий ВАК РФ
Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи. // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТРТУ, 2007. №1(73). – С. 65-70.
Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи с ограничением по времени. // Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТТИ ЮФУ, 2008. №4(81). – С. 45-50.
II Свидетельства о регистрации программ на ЭВМ
Курейчик В.М., Емельянова Т.С. Программа решения линейных транспортных задач с использованием специального генетического алгоритма // свидетельство об официальной регистрации программы для ЭВМ № 2007613932 от 14.09.2007.
Курейчик В.М., Емельянова Т.С. Программа решения транспортных задач с ограничением по времени с использованием комбинированного генетического алгоритма // свидетельство о государственной регистрации программы для ЭВМ №2009610013 от 11.01.2009.
III. Публикации в других изданиях
Емельянова Т.С. Применение генетических алгоритмов для решения транспортной задачи линейного программирования. // Перспективные информационные технологии и интеллектуальные системы. – Таганрог: Изд-во ТРТУ, 2006. №3(27). – С. 15-29.
Емельянова Т.С. Решение транспортных задач с использованием генетических методов. // Сборник трудов Всероссийской научной школы-семинара молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». – 2007. Таганрог: Изд-во ТТИ ЮФУ. С. 82-87.
Емельянова Т.С. Анализ методов решения нелинейных транспортных задач. // Перспективные информационные технологии и интеллектуальные системы. – Таганрог: Изд-во ТРТУ, 2007. №1(29). – С. 38-49.
Емельянова Т.С. Эвристические и метаэвристические методы решения динамической транспортной задачи. // Перспективные информационные технологии и интеллектуальные системы. – Таганрог: Изд-во ТРТУ, 2007. №3(31). – С. 33-43.
Емельянова Т.С. Разработка программы для решения транспортных задач с ограничением по времени на основе генетических алгоритмов. // Сборник трудов Всероссийской научной школы-семинара молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». – 2008. Таганрог: Изд-во ТТИ ЮФУ. С. 76-81.
Емельянова Т.С. Генетический алгоритм решения транспортной задачи с ограничением по времени. // Перспективные информационные технологии и интеллектуальные системы. – Таганрог: Изд-во ТРТУ, 2007. №4(32). – С. 43-59.
Емельянова Т.С. Модифицированный генетический алгоритм для решения транспортных задач с ограничением по времени. // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS’08) и «Интеллектуальные САПР» (CAD02008) – М.: Физматлит, 2008, Т.1. С. 41-46.
Емельянова Т.С. Генетические алгоритмы решения транспортных задач. // Тезисы докладов IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления». – Таганрог: Изд-во ЮФУ – 2008. С. 150-151.
Емельянова Т.С. Решение эталонных транспортных задач с кластерным расположением клиентов с использованием генетических методов. // Сборник научных трудов второй всероссийской научной конференции с международным участием нечеткие системы и мягкие вычисления (НСМВ-2008): (г. Ульяновск, 27-29 октября, 2008 г.). – Ульяновск: Изд-во УлГТУ, 2008, С. 194-201.
Курейчик В.М., Емельянова Т.С. Решение транспортных задач с использованием комбинированного генетического алгоритма. // Искусственный интеллект. Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008 (28 сентября - 3 октября 2008 г., г. Дубна, Россия). Труды конференции. Т.1 – М.: Физматлит, 2008. С. 158-164.
Личный вклад автора в работах [3]-[4] состоит в следующем, разработка операторов генетического алгоритма, программирование, отладка и тестирование программы; в работе [14] модификация оператора инициализации, разработка новых операторов кроссинговера и мутации.
|
