Скачать 290.55 Kb.
|
На правах рукописи Полуян Анна Юрьевна ИССЛЕДОВАНИЕ И РАЗРАБОТКА БИОНИЧЕСКИХ МЕТОДОВ И АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ ТРАНСПОРТНОГО ТИПА Специальность 05.13.17 – теоретические основы информатики Автореферат диссертации на соискание ученой степени кандидата технических наук Ростов-на-Дону 2011 Работа выполнена в институте энергетики и машиностроения Донского государственного технического университета Научный руководитель: Заслуженный деятель науки РФ доктор технических наук, профессор Чернышев Юрий Олегович Официальные оппоненты: Доктор технических наук, профессор Ромм Яков Евсеевич Заслуженный деятель науки РФ доктор технических наук, профессор Безуглов Дмитрий Анатольевич Ведущая организация: Ростовский государственный университет путей сообщения (РГУПС), г. Ростов-на-Дону Защита диссертации состоится « 18 » февраля 2011 г. в 1420 на заседании диссертационного совета Д.212.208.21 Южного федерального университета по адресу: пер. Некрасовский, 44, ГСП-17А, г. Таганрог, Ростовская область, 347928, аудитория Д-406. С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: ул. Пушкинская, 148, г. Ростов-на-Дону, 344400. Автореферат разослан « 15 » января 2011 г. Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: пер. Некрасовский, 44, ГСП-17А, г. Таганрог, Ростовская область, 347928, диссертационный совет Д 212.208.21. Ученый секретарь диссертационного совета Д 212.208.21
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Задачи транспортного типа занимают особое место в классе приоритетных направлений исследования информационных технологий, так как решение задач данного типа имеет актуальное значение в промышленности, на транспорте, в системах связи и других отраслях народного хозяйства. Сегодня практически невозможно обеспечить требуемое потребителями качество обслуживания и эффективность транспортных операций без применения информационных систем и программных комплексов для анализа, планирования и поддержки принятия коммерческих решений. Благодаря разработке эффективных методов решения задач транспортного типа, стали развиваться информационные системы и технологии, обеспечившие возможность автоматизации типовых операций в транспортных процессах, для организации товародвижения на технологическом рынке транспортных услуг. Оcнoвнoe мecтo среди прикладных задач транспортного типа, зaнимaют зaдaчи построения транспортных мapшpyтoв, кoтopыe пoзвoляют дo минимyмa coкpaтить пpoбeг тpaнcпopтныx средств или минимизиpовать зaтpaты нa пepeвoзкy гpyзoв. Маршрутизация перевозок — это наиболее совершенный способ организации потоков грузов, оказывающий существенное влияние на ускорение оборота транспорта при рациональном и эффективном его использовании. Для решения задач, связанным с построением транспортных маршрутов, автором в качестве основы диссертационного исследования использовался вариант определения наилучшего маршрута, опирающийся на методы бионического поиска. Это в полной мере относится к задачам об экстремальном пути и задачи коммивояжера, исследуемые в диссертации. Решение данных задач невозможно без использования математических методов и вычислительной техники, а возникающие при этом вычислительные сложности обусловлены большой размерностью задач. В связи с этим применение классических методов решения задач данного типа с экспоненциальной временной сложностью становится неэффективным из-за необходимости обработки очень больших объемов информации. Одной из тенденций, увеличения производительности ЭВМ, является построение многопроцессорных вычислительных систем, которые распараллеливают процесс обработки информации. Поэтому методы, использующие последовательный принцип решения задач, не позволяют эффективно использовать вычислительную мощность ЭВМ. Отсюда возникает необходимость разработки алгоритмов, адаптированных к требованиям решаемой задачи. В связи с этим, с целью снижения временной сложности алгоритма (ВСА), актуальным является разработка последовательных и параллельных бионических алгоритмов для решения задач транспортного типа. Такие алгоритмы эффективно используют информацию, накопленную в процессе эволюции, позволяют оперативно проводить анализ полученных результатов, исследовать влияние различных ограничений на получаемый результат, сокращают время поиска квазиоптимальных и оптимальных решений. Их широкое применение обусловлено тем, что они позволяющих решать проблемы предварительной сходимости алгоритма и получать наборы эффективных решений. Поэтому, исследование и разработка методов и алгоритмов бионического поиска и параллельного бионического поиска для решения рассматриваемого класса задач транспортного типа, является актуальной научной задачей, представляющей практический интерес. Цель диссертационной работы состоит в исследовании и разработке новых и модифицированных алгоритмов последовательного и параллельного бионического поиска для решения задач транспортного типа. Основные задачи исследования. Для достижения поставленной цели решены следующие задачи:
Методы исследований. Для постановки и решения задач в диссертационной работе используются элементы теории множеств, теории графов, теории алгоритмов, теории эволюционного моделирования, методы генетического поиска и адаптации. Научная новизна результатов исследования заключается в следующем:
4. На основе генетических операторов, построены модифицированные генетические и эволюционные алгоритмы бионического поиска, которые увеличивают вероятность «выживания» альтернативных решений с лучшим значением ЦФ. Отличительная особенность предлагаемых алгоритмов состоит не только в построении, но и в возможности корректировки популяции (изменение порядка хромосом – переранжирование, удаление или добавление особей) в диалоговом режиме работы комплекса программ. К числу наиболее важных научных результатов диссертации относятся:
Практическая ценность диссертационной работы заключается в том, что проведенные исследования разработанных бионических алгоритмов решения задач транспортного типа, показали преимущество по качеству решений в сравнении с известными методами. Разработан комплекс программ для решения задач об экстремальном пути и задачи коммивояжера. Комплекс программ реализован на языке С++ под Windows ХР. Эксперименты проводились на ЭВМ типа IBM PC с процессором Pentium 4. Разработанные алгоритмы позволяют получать набор квазиоптимальных альтернативных результатов, полиномиальной временной сложностью. Достоверность полученных в диссертации результатов обусловлена корректной постановкой задач, применением строгих математических методов, сопоставлением результатов, полученных экспериментальным путем, с результатами других исследователей. Реализация и внедрение результатов работы. Полученные результаты использованы при выполнении фундаментальных госбюджетных научно-исследовательских работ тематических планов 2003, 2004, 2005, 2006, 2008, 2009 годов Ростовской-на-Дону государственной академии сельскохозяйственного машиностроения (РГАСХМ) на кафедре “Прикладная математика и вычислительная техника” (“ПМ и ВТ”) по темам: “Теория поисковой адаптации для решения избранных комбинированных задач оптимизации” (01.01.2003г. - 31.12.2004г.); №1.6.05: “Теория интеллектуальных процедур поиска оптимальных решений” (01.01.2005 г.- 31.12.2005 г.); №1.3.06: “Развитие теории канальной трассировки на основе эволюционного моделирования” (1.01.2006г. – 31.12.2006г.); № 1.3.08: “Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования сверхбольших интегральных схем (СБИС)” (1.01.2008 – 31.12.2009), «Развитие теории бионического моделирования для решения оптимизационных задач транспортного типа» (1.01.2010 – 31.12.2011). Материалы диссертации использованы в научно-исследовательской работе, выполняемой по гранту № 10-01-00481-а на тему: «Развитие теории и практики применения интеллектуальных методов в распределительных системах управления базами данных», финансируемой Российским фондом фундаментальных исследований (1.01.2010 – 31.12.11). Разработанные бионические алгоритмы использовались в ФГУП научно- исследовательского института специальных информационно–измерительных систем (НИИ СИИС г. Ростов-на-Дону). Кроме того, результаты выполненных работ используются в учебном процессе на кафедре “ВС и ИБ” при чтении лекций и проведении практических занятий по дисциплинам “Информатика”, “Вычислительная математика”, “Дискретная математика” и “Программные средства САПР”. Акты об использовании прилагаются. Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях: “Интеллектуальные системы” (AIS-05, 06, 07, 08) и “Интеллектуальные САПР” (CAD-2005, 2006, 2007, 2008) (г. Геленджик, 2005 - 2008 гг.,), “Модели и алгоритмы для имитации физическо-химических процессов” (ТГПИ, Таганрог, 2008), Всероссийской научно-практической конференции с международным участием “Информационные технологии в профессиональной деятельности и научной работе” (г. Йошкар-Ола, 2008г.). Материалы диссертационной работы вошли в четыре отчета по фундаментальным НИР: “Теория поисковой адаптации для решения избранных комбинированных задач оптимизации”, “Теория интеллектуальных процедур поиска оптимальных решений”, “Развитие теории канальной трассировки на основе эволюционного моделирования”, “Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования, сверхбольших интегральных схем (СБИС)” и при решении задач оптимизации тестового контроля и диагностики радиоэлектронной аппаратуры. Научные результаты опубликованы в 16 печатных работ, в том числе монография, 5 статей в периодических научных журналах, рекомендованных ВАК. Публикации. По материалам диссертации опубликовано 1 монография, 16 печатных работ, в том числе 5 статей в изданиях, входящих в «Перечень ведущих научных журналов и изданиях, выпускаемых в Российской Федерации», утвержденный ВАК. Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 100 наименований, изложенных на 156 страницах и приложения. Содержит 55 рисунков, 20 таблиц. КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертационной работы, сформулированы цели, даны основные научные результаты, выносимые на защиту, приведены сведения о практической значимости, апробации диссертационной работы, дано краткое содержание основных разделов диссертации. В первой главе рассмотрены основные проблемы и перспективы решения задач транспортного типа, приведены математические модели и алгоритмы решения задач данного типа. Задачи транспортного типа чаще всего встречаются при исследовании разнообразных процессов на транспорте и системах связи. Временные сложности, возникающие при решении данных задач, зачастую связаны с их большой размерностью. Рассмотрим граф, вершинам которого соответствуют производства или потребители продукции, а также пункты перевалки и просто развилки транспортных магистралей. Дуги соответствуют длинам отрезков дорог, транспортных магистралей, коммуникациям, автомобильным, водным или железнодорожным путям, расположенным на рассматриваемой территории, и связывают вершины графа. Тогда типичной задачей транспортного типа является задача нахождения некоторого маршрута (пути) из пункта А в пункт В. На допустимые маршруты может быть наложен ряд ограничений: вводят запрет на возврат к уже пройденному пункту или требование обхода всех пунктов с условием, что в каждом пункте можно побывать лишь один раз, или нахождение кратчайшего пути из пункта А и пункт В. Это в полной мере относится к задачам об экстремальном пути на графе и задачи коммивояжера. Решаемые в диссертационной работе задачи, могут быть сформулированы следующим образом. Пусть дан граф G=(X,U) дугам которого приписаны веса (стоимости), задаваемые матрицей . Задачи об экстремальном пути состоят в нахождении самого кратчайшего или самого длиннейшего пути от заданной начальной вершины до заданной конечной вершины , при условии, что такой путь существует. Элементы матрицы весов С могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным суммарным весом. Математическую модель задачи о кратчайшем пути можно записать в общем виде: (1) (2) Задача о максимальном (длиннейшем) пути сводится к задаче о кратчайшем пути на графе – достаточно изменить знаки дуг на противоположные. Для существования решения задачи о максимальном пути необходимо и достаточно отсутствия контуров положительной длины. К задачам поиска кратчайших или длиннейших путей или контуров, проходящих через все вершины графа относится задача коммивояжера (ЗК). Классическая постановка задачи о коммивояжере выглядит следующим образом: Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
Запишем математическому модель задачи коммивояжера. Путь коммивояжера может быть описан циклической перестановкой =(j1,j2,..,jn,j1), причём все j1..jn – разные вершины; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Задача состоит в том, чтобы найти такой путь, чтобы минимизировать функционал (3) сij0; сjj=∞, (4) сij= сji, (5) сij+ сjkсik. (6)
Рис. 2. Структурная схема параллельного бионического алгоритма для задачи об экстремальном пути Построенная структурная схема параллельного бионического алгоритма для нахождения экстремального пути, обеспечивает поддержку следующих действий:
реализация быстрого эволюционного поиска (использование оператора мутации); выполнение генетического поиска (использование различных генетических операторов);
Как указывалось выше, генетические алгоритмы и эволюционные алгоритмы образуют бионический поиск (БП). Отметим, что периодически в каждой итерации БА можно проводить различные изменения в перспективных, неперспективных и в других решениях. Временная сложность алгоритма лежит в пределах O(n2). Миграция определяет качество поиска и эффективность алгоритма. Частая миграция приводит к обмену потенциально полезным генетическим материалом, но в этом случае отрицательным эффектом является увеличение затрат на обмен информацией. Это наиболее существенно при топологии связей, в которой каждая популяция обменивается со всеми другими. Для повышения скорости необходимо найти баланс между уровнем миграции и качеством решения. Для этого предлагается ввести уровень миграции следующим образом: если значение целевой функции не меняется или ухудшилось за последние t поколений, то развитие подпопуляции не приводит к появлению лучших решений, в таком выполняется миграция. Приведена технология преобразования популяции при переходе из одной итерации поиска в другую, позволяющая закреплять оптимальные решения, на основе использования разработанного оператора миграции. Третья глава посвящена решению задачи коммивояжера на основе бионического поиска. Проведен анализ и выбор модели представления решения задачи. Представление задачи коммивояжера в виде матрицы смежности дает возможность анализировать шаблоны (решения), которые применимы для n-размерной оптимизации. Шаблоны, определенные в терминах единственной определенной позиции, соответствуют естественным строительным блокам, то есть элементам для задачи коммивояжера. Создание начального множества решений происходит по принципу «дробовика» т.е. подразумевается случайный выбор альтернатив из всей области решений задачи коммивояжера. Разработаны новые и модифицированные генетические операторы, ориентированные на решения задачи коммивояжера. На основании проведенных тестов, бионические алгоритмы, построенные на основе стандартных генетических операторов, не гарантируют нахождение оптимального решения. В связи с этим для нахождения оптимальных решений используются предложенные генетические операторы, увеличивающие вероятность «выживания» альтернативных решений с лучшим значением ЦФ на 10% - 15%. Приведем процедуру построения модифицированного оператора миграции. Одной из важных проблем является определение необходимого оптимального количества хромосом из подпопуляций для миграции при работе параллельного бионического алгоритма, от количества хромосом зависит время и экономичность работы алгоритма, для этого предлагается использовать формулу отбора необходимой численности хромосом: где n – количество отобранных хромосом для миграции; ∆ - предельная ошибка выборки, представляет собой предел, которым ограничена сверху абсолютная величина ; - среднеквадратичное отклонение; t – коэффициент, определяемый по таблице Лапласа, Ф(t)=р, где р – заданная вероятность оператора миграции, определяемая лицом принимаемым решение. Проведенные тесты показывают, что использование модифицированного оператора миграции, позволяет сократить время работы алгоритма. Выполнение бионического поиска осуществляется на основе комбинированной стратегии «эволюция – поиск – эволюция». Структурная схема алгоритма бионического поиска для решения задачи коммивояжера представлена на рис. 3, где МГА ЗК и ЭА ЗК – модифицированный генетический алгоритм задачи коммивояжера и эволюционный алгоритм задачи коммивояжера. Разработанный бионический алгоритм, основан на использовании методов эволюционного моделирования, усовершенствованного бионического поиска для решения задачи коммивояжера. В данном алгоритме используются идеи совместной эволюции, выбор моделей эволюции (использование микро-, макро-, метаэволюции), адаптации к внешней среде, а так же иерархическое управление генетическим и эволюционным поиском, локальный поиск решений на основе поисковых методов и «жадной» стратегии. Основная особенность модифицированного генетического алгоритма состоит в том, что анализируется не одно решение, а некоторое подмножество квазиоптимальных решений. Построенный генетический алгоритм ликвидирует имеющиеся пересечения в маршрутах, используя оператор инверсии, а также применяет к каждой хромосоме операцию разнообразия. Операция разнообразия вносит некоторые изменения в отдельную хромосому. Модифицированного генетический алгоритм поддерживает такую архитектуру генетического поиска, при которой целенаправленное изменение применяется ко всем вновь созданным хромосомам. Эволюционные алгоритмы в основном ориентированы на работу с оператором мутации. Инструментом адаптации является конкуренция между всеми хромосомами за возможность включения в следующую популяцию. «Жадные» стратегии, основанные на знаниях о задаче коммивояжера, улучшают скорость сходимости, однако часто препятствуют выходу из локальных минимумов. Существует несколько путей избежать этой ситуации: изменить архитектуру БА или же не помещать такие решения в популяцию. Для повышения эффективности эволюционного и модифицированного генетического алгоритмов, разработаны усовершенствованные генетические операторы, для реализации бионического и параллельного бионического поиска. Основным способом повышения скорости работы бионического алгоритма является распараллеливание. Популяция разделяется на несколько различных частей, которые впоследствии развиваются параллельно и независимо. То есть скрещивание происходит только между членами одной части. На каком-то этапе работы происходит обмен особями между частями популяции, на основе модифицированного оператора мутации. И так может продолжаться до завершения работы алгоритма. На основании бионического алгоритма для решения задачи коммивояжера на рис.4 представлена схема алгоритма параллельного бионического поиска для решения задачи коммивояжера, где БП1, БП2 – бионические поиски для частей популяций. Рис.4. Схема алгоритма параллельного бионического поиска для решения задачи коммивояжера В четвёртой главе описаны задачи и цели вычислительного эксперимента. Составлен комплекс программ на основе разработанных алгоритмов решения задач об экстремальном пути на графе, который реализован на языке С++ под Windows ХР. Эксперименты проводились на ЭВМ типа IBM PC с процессором Pentium 4. Графический интерфейс пользователя программного комплекса представлен на рис. 5. Рис. 5. Графический интерфейс пользователя программного комплекса На тестовых примерах проведены экспериментальные исследования по данным алгоритмам. Определены области эффективного применения каждого алгоритма в зависимости от управления процессом бионического поиска. На рис. 6, 7 приведены гистограммы эффективности работы бионического и параллельного бионического алгоритма по сравнению с известными методами. Из гистограмм видно, что при размерностях задачи 500 Рис. 6. Результат работы алгоритмов для задачи о кратчайшем пути Рис. 7. Результат работы алгоритмов для задачи коммивояжера В заключении сформулированы основные выводы и результаты диссертационной работы. В приложении приведены акты об использовании результатов диссертационной работы и приведено описание комплекса программ. |
Разработка и исследование алгоритмов решения транспортных задач с... Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге | Законов, закономерностей математики и отвечающих им методов расчета. Формирование базовой Применение основных понятий и методов математической логики и теории алгоритмов для решения конкретных задач | ||
Problems of transport type, optimizing problems, computer mathematical... В работе рассматривается технология построения компьютерных моделей оптимизационных задач транспортного типа в ms excel и проводится... | Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики | ||
Программное обеспечение для решения задач линейного программирования... Граничениями типа меньше или равно. Основой программы служит алгоритм симлекс метода с возможностью вывода результата в виде графического... | Тема урока: «Составление линейных программ для решения задач на применение... Повторить и обобщить знания о свойствах, типах, способах построения алгоритмов, этапах решения задач, о работе операторов input,... | ||
Диплом «Исследование и сравнение способов решения логических задач» Практическая часть. Разработка сайта и тестирующей программы | Отчет №3 о научно-исследовательской работе по теме: «Грид-технологии» Разработка методов эффективного решения задач обработки, хранения, передачи и защиты информации | ||
Исследование методов обработки электроэнцефалографических сигналов... Работа выполнена в таганрогском технологическом институте Южного федерального университетана на кафедре Радиоприёмных устройств и... | Реферат: Шайдуров А. Г. Исследование и разработка некоторых графических... Шайдуров А. Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению... | ||
Разработка и исследование алгоритмов распознавания изображений на... | Новосибирский государственный технический университет кафедра вычислительной техники Целью работы является: изучение методов решения задач нлп, особенностей, возникающих при использовании тех или иных методов решения;... | ||
Урок информатики в 9 классе Тема «Оператор цикла с параметром» Цель урока: закрепление навыков решения задач с использованием циклических алгоритмов, знакомство с циклом «Для…» | Разработка и исследование методов определения видимости полигонов... Целью диссертации является разработка метода, который бы позволил отрисовывать сцены, геометрическая сложность которых, в настоящее... | ||
Рефераты №3 (2012 г.) Разработка, исследование и реализация методов совершенствования теплообменных аппаратов турбоустановок | Решение теоретических задач (первая половина семестра, 7-8 заданий) Цель заданий — проверка усвоения знаний и получение навыка применения этих знаний для решения практических задач в области криптографических... |