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

Задачи транспортного типа занимают особое место в классе приоритетных направлений исследования информационных технологий, так как решение транспортных задач имеет актуальное значение в промышленности, на транспорте, в системах связи и других отраслях народного хозяйства.

Сегодня практически невозможно обеспечить требуемое потребителями качество обслуживания и эффективность транспортных операций без применения информационных систем и программных комплексов для анализа, планирования и поддержки принятия коммерческих решений. Благодаря разработке эффективных методов решения задач транспортного типа, стали развиваться информационные системы и технологии, обеспечившие возможность автоматизации типовых операций в транспортных процессах, для организации товародвижения на технологическом рынке транспортных услуг.

Основное место среди прикладных задач транспортного типа, занимают задачи построения транспортных маршрутов, которые позволяют до минимума сократить пробег транспортных средств или минимизировать затраты на перевозку грузов. Маршрутизация перевозок — это наиболее совершенный способ организации потоков грузов с предприятий, оказывающий существенное влияние на ускорение оборота транспорта при рациональном и эффективном его использовании.

Для решения задач, связанных с построением транспортных маршрутов, автором в качестве основы диссертационного исследования использовался вариант определения оптимального пути, опирающийся на методы бионического поиска. Это в полной мере относится к задачам об экстремальном пути на графе и задачи коммивояжера, исследуемым в диссертации.

Для данного класса комбинаторных задач, отсутствуют эффективные классические методы и алгоритмы решения. Эти задачи характеризуются конечным, но весьма большим числом возможных решений. Их можно поставить как задачи целочисленного программирования, но и в этом случае отсутствуют эффективные алгоритмы.

Поэтому, разработка методов и алгоритмов для решения задач транспортного типа, осуществляющаяся на протяжении многих лет, является по прежнему, актуальной проблемой.

Все методы решения задач можно разделить на две группы: точные и эвристические.

К точным методам относятся метод ветвей и границ, метод неявного перебора и др. В этих методах выполняется сокращения объема перебора за счет построения оценок, позволяющих опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Эти алгоритмы весьма просты для понимания, легко программируются на ЭВМ, обладают простой математической структурой. К сожалению, они имеют существенный недостаток — экспоненциальную временную сложность. Существуют и другие точные методы решения комбинаторных задач, но все они имеют низкую эффективность.

Отдельной категорией среди эвристических методов выделяются приближенные методы, использующие случайный поиск. Приближенные алгоритмы дают решения «близкие» к оптимальным. Для большинства практических задач достаточно получить хорошее приближенное решение за приемлемое время. Методы, применяемые для построения алгоритмов такого типа, сильно зависят от специфики задачи. Одной из тенденций, увеличения производительности ЭВМ, является построение многопроцессорных вычислительных систем, которые распараллеливают процесс обработки информации. Но детерминированные методы, не позволяют эффективно использовать вычислительную мощность ЭВМ. Отсюда возникает необходимость разработки параллельных алгоритмов решения задач.

В связи с этим, с целью снижения временной сложности алгоритмов (ВСА), актуальным является разработка последовательных и параллельных бионических алгоритмов для решения задач об экстремальных путях. В них применяются случайные правила поиска, что позволяет избежать локальные «ловушки» [1,2]. Бионический поиск, с точки зрения преобразования информации — это последовательное преобразование одного конечного нечеткого множества альтернативных решений в другое [2]. Само преобразование называется алгоритмом поиска или генетическим алгоритмом (ГА). В основе ГА лежит случайный направленный или комбинированный поиск. Такие методы и алгоритмы эффективно используют информацию, накопленную в процессе эволюции, для получения квазиоптимальных и оптимальных решений [3,4]. Их широкое применение обусловлено тем, что они имеют меньшую временную сложность и позволяют получать приемлемые для практики решения. Поэтому, исследование и разработка методов и алгоритмов последовательного и параллельного бионического поиска для решения рассматриваемого класса задач транспортного типа, является актуальной научной задачей, представляющей практический интерес.

Моделирование бионических процессов в естественных и искусственных системах в настоящее время связано с созданием новых моделей и методов, направленных на решение сложных проблем. Для решения задач транспортного типа на основе бионического поиска, разработаны новые структурные схемы и алгоритмы, модифицированы базисные структуры оптимизационного процесса, которые позволяют расширить область поиска решений без увеличения времени работы и сократить преждевременную сходимость алгоритмов.

Наиболее известные работы в области теории оптимизации на графах принадлежат A.A. Зыкову, Г. М. Адельсону — Вельскому, В. Н. Буркову, Н. Кристофидесу, Ю. М. Ермольеву, Р. Д. Басаскеру, Ф. Харари, К. Бержу, Э. Дейкстре, Р. Флойду, Д. К. Замбицкому, О. Ope, Т. Саати, Д. Р. Фалкерсону, JI.Р.Форду.

Развитие эволюционных подходов к решению оптимизационных задач в значительной мере определяется работами M.JI. Цетлина, JL Фогеля (L J. Fogel),.

Г. Шефеля (H. Schwefel), Дж. Холланда (Holland John H.), JI. Девису (L. Devis), Д. Гольдберга (D. Goldberg), B.M. Курейчика, Д. И. Батищева, В. В. Емельянова, JI.C. Берштейна, И. П. Норенкова, В. В. Курейчика, Ю. Р. Цоя и др.

Цель диссертационной работы состоит в исследовании и разработке новых и модифицированных последовательных и параллельных бионических алгоритмов для решения задач транспортного типа, основанных на принципах эволюционной адаптации, позволяющие получать эффективные по качеству результаты за приемлемое время работы алгоритма.

Достижение указанной цели предполагает решение следующих основных задач:

1. Исследовать математические модели, адекватно отражающие сущность задач транспортного типа, провести анализ и сравнительную характеристику существующих методов решения задач.

2. Разработать модифицированные базисные структуры оптимизационного процесса для моделирования бионического поиска.

3. Разработать системный подход к решению задач транспортного типа, с использованием модифицированных и вновь созданных эволюционных и генетических операторов, адаптированных к требованиям решаемой задачи и установить наиболее эффективные параметры вычислительного процесса.

4. Построить модифицированные эволюционные и генетические алгоритмы для реализации последовательного и параллельного бионического поиска.

5. Разработать комплекс программ на основе последовательных и параллельных бионических алгоритмов, провести экспериментальные исследования разработанных алгоритмов, а также их сравнение с известными алгоритмами.

Методы исследований. Для постановки и решения задач в диссертационной работе используются элементы теории множеств, теории графов, теории алгоритмов, теории эволюционного моделирования, методы генетического и бионического поиска и адаптации.

Научная новизна заключается в следующем:

1. Для моделирования бионического поиска предложена модифицированная базисная структура оптимизационного процесса, основанного на принципах эволюционной адаптации, позволяющая сокращать область поиска допустимых значений. Предложенные схемы отличаются от известных по структуре построения и учетом вариации параметров. Разработана стратегия адаптации размера популяции (оператор рекомбинации) в процессе работы бионического алгоритма, которая отличается тем, что для формирования новой популяции разработана формула на основе последовательности решета Эратосфена, позволяющая адаптироваться к характеристикам бионического поиска.

2. Построены модифицированные архитектуры последовательного и параллельного бионического поиска, на основе эволюционных стратегий, позволяющие получать эффективные по качеству решения за приемлемое время работы. Предложенные архитектуры, отличаются от известных по построению, параллелизмом, реализующим различные схемы миграций на основе модификаций модели островов и тем, что позволяют устанавливать наиболее эффективные параметры вычислительного процесса.

3. Предложены генетические операторы, ориентированные на задачи транспортного типа, отличающиеся от известных по построению и тем, что они основаны на знаниях о решаемых задачах, которые позволяют частично решать проблемы сходимости генетических алгоритмов и дают механизм синхронизации полученных решений на всех этапах поиска (оператор миграции).

4. На основе генетических операторов, построены модифицированные генетические и эволюционные алгоритмы бионического поиска, которые увеличивают вероятность «выживания» альтернативных решений с лучшим значением ЦФ. Отличительная особенность предлагаемого алгоритма состоит не только в построении, но и в возможности корректировки популяции (изменение порядка хромосом — переранжирование, удаление или добавление особей) в диалоговом режиме работы комплекса программ.

Решение поставленных задач позволяет вынести на защиту следующие научные результаты:

• Новые и модифицированные структурные схемы и алгоритмы последовательного и параллельного бионического поиска решения задач транспортного типа, основанные на принципах эволюционной адаптации.

• Приведен процесс преобразования размера популяции при переходе из одной итерации в другую в процессе работы бионического алгоритма.

• Модифицированные эволюционные и генетические алгоритмы, основанные на «жадных» стратегиях и эвристиках, позволяющие частично решать проблемы предварительной сходимости алгоритмов.

• Новые и модифицированные генетические операторы (кроссинговер, мутация, инверсия, селекция), для моделирования нахождения экстремального пути, увеличивающие вероятность «выживания» альтернативных решений с лучшим значением целевой функции.

Практическая ценность заключается в том, что проведенные исследования разработанных бионических алгоритмов решения задач транспортного типа, показали преимущество по сравнению с известными. Создан комплекс программ, моделирующих разработанные бионические алгоритмы решения задач об экстремальных путях. При построения комплекса программ использовались пакеты программ С++ Builder, Visual С++ под Windows ХР. Разработанные алгоритмы позволяют получать набор квазиоптимальных альтернативных результатов, полиномиальной временной сложностью.

Реализация результатов работы. Полученные результаты использованы при выполнении фундаментальных госбюджетных научно-исследовательских работ тематических планов 2003, 2004, 2005, 2006, 2008, 2009, 2010 годов Ростовской-на-Дону государственной академии сельскохозяйственного машиностроения (РГДСХМ) на кафедре «Прикладная математика и вычислительная техника» по темам: «Теория поисковой адаптации для решения избранных комбинированных задач оптимизации» № Г/Р 01.20.0308.394 (01.01.2003г. — 31.12.2004 г.) — «Теория интеллектуальных процедур поиска оптимальных решений» № Г/Р 012.00.50.55.01 (01.01.2005 г.- 31.12.2005 г.) — «Развитие теории канальной трассировки на основе эволюционного моделирования» № Г/Р 012.00.60.42.48 (1.01.2006г. — 31.12.2006 г.) — «Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования, сверхбольших интегральных схем (СБИС)» № Г/Р 1 201 051 299 (1.01.2008 -31.12.2009) — «Развитие теории бионического моделированиядля решения оптимизационных задач транспортного типа» (1.01.2010 — 31.12.2011). Материалы диссертации использованы в научно-исследовательских работах, выполненных по гранту № 10−01−481-а на тему: «Развитие теории и практики применения интеллектуальных методов в распределительных системах управления базами данных», финансируемому Российским фондом фундаментальных исследований (1.01.2010 — 31.12.11).

Разработанные бионические алгоритмы использовались в ФГУП Научно-исследовательском институте специальных информационно-измерительных систем (НИИ СИИС г. РостовнаДону) с 2004 — 2008 годы для решения задач оптимизации тестов, контроля и диагностики радиоэлектронной аппаратуры, выбора оптимального варианта обнаружения ошибок. Кроме того, результаты выполненных работ используются в учебном процессе в РГАСХМ при чтении лекций и проведении практических занятий по дисциплинам «Дискретная математика», «Программные средства САПР», «Вычислительная математика» и «Информатика». Акты об использовании прилагаются.

Апробация работы и публикации. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях: «Интеллектуальные системы» (А18−05, 06, 07, 08) и «Интеллектуальные САПР» (САБ-2005, 2006, 2007, 2008) (г. Геленджик, 2006 — 2008 гг.,), «Модели и алгоритмы для имитации физическо-химических процессов» (ТГПИ, Таганрог, 2008), Всероссийской научно-практической конференции с международным участием «Информационные технологии в профессиональной деятельности и научной работе» (г. Йошкар-Ола, 2008 г.). Материалы диссертационной работы вошли в четыре отчета по фундаментальным НИР: «Теория поисковой адаптации для решения избранных комбинированных задач оптимизации», «Теория интеллектуальных процедур поиска оптимальных решений», «Развитие теории канальной трассировки на основе эволюционного моделирования», «Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования, сверхбольших интегральных схем (СБИС)» и при решении задач оптимизации тестов, контроля и диагностики радиоэлектронной аппаратуры в НИИ СИИС. По материалам диссертации опубликовано 1 монография, 16 печатных работ, в том числе 5 статей в изданиях, входящих в «Перечень ведущих научных журналов и изданиях, выпускаемых в Российской Федерации», утвержденный ВАК.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка, включающего 100 наименований, изложенных на 156 страницах, и приложения, содержит 55 рисунков, 20 таблиц.

4.5. Выводы.

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

2. Проведены экспериментальные исследования разработанных алгоритмов на тестовых примерах. По результатам экспериментов, даны рекомендации по варьированию входных параметров для бионических алгоритмов и их операторов, обеспечивающих возможность получения набора локально — оптимальных решений: ОК для задачи о кратчайшем пути должны быть в пределах 0,7−0,8, для задачи коммивояжера — 0,6 — 0,7- вероятность ОМ для задачи о кратчайшем пути — 0,4, для задачи коммивояжера 0,3 — 0,4, ОМГ — 0,7. При данных значениях параметров, обеспечиваются наилучшие условия для нахождения оптимального решения.

3. Экспериментальные исследования бионического и параллельного бионического поиска показали, что наиболее качественные решения получены для задачи о кратчайшем пути при числе итераций N0= 1000 и размере популяции 1Чр от 400 до 500, а для задачи коммивояжера при N0 — 1500, Кр=500.

4. Бионические и параллельные бионические алгоритмы для решения задач об экстремальном пути, показали преимущество по качеству решения, по сравнению с существующими методами на 10% - 15%. Управление процессом бионического и параллельного бионического поиска, позволяет находить оптимальные параметры и повысить качество решений на 15% - 20%. Параллельный бионический алгоритм улучшил решение задачи на 12% - 20% при больших размерностях задачи (п>1500).

5. Временная сложность разработанных бионических алгоритмов не выходит за пределы полиномиальной зависимости, и определяется как: 0(аМ2).

Заключение

.

В результате выполненных теоретических и практических исследований получены следующие результаты:

1. Определены основные направления области использования задач транспортного типа, которые могут быть представлены в виде моделей задач об экстремальном пути на графе. Исследованы математические модели задач транспортного типа, адекватно отражающие сущность задач, проведен анализ и сравнительная характеристика существующих методов решения задач об экстремальном пути и задачи коммивояжера. Отмечены достоинства, недостатки и перспективы развития этих алгоритмов. Предложен новый подход к кодированию решений, учитывающий статусы генов, который достаточно эффективный для решения задач об экстремальных путях.

2. Предложенны новые и модифицированные эволюционные и генетические операторы мутации, кроссинговера, сегрегации, инверсии, селекции, миграции, для решения задач транспортного типа, которые увеличивают вероятность «выживания» альтернативных решений с лучшим значением ЦФ на 10% - 15%. Разработана модифицированная базисная структура оптимизационного процесса, основанная на принципах бионического поиска и структурная схема параллельного бионического поиска, преимущество которых, состоит в том, что все строительные блоки связаны как с блоком адаптации, предназначенным для выбора и реализации различных стратегий и механизмов адаптации, так и между собой.

3. Построены модифицированные алгоритмы бионического и параллельного бионического поиска с применением адаптации, в которых предложена совместная реализация эволюций Дарвина и Ламарка, эволюционная адаптация, предназначенная для выбора и реализации различных стратегий и механизмов адаптации. Разработаны модифицированные генетические и эволюционные алгоритмы основанные на «жадных» стратегиях и эвристиках, ориентированные на решение задач транспортного типа, которые позволяют получать оптимальные результаты за приемлемое время работы алгоритма.

Разработана реализация общей стратегии адаптации размера популяции, позволяющая адаптироваться к характеристикам бионического поиска.

•у.

Временная сложность разработанных алгоритмов составляет 0(аГЧ).

4. Разработан комплекс программ на основе бионического и параллельного бионического поиска. Экспериментальные исследования параллельного бионического алгоритма показали, что наиболее качественные решения были получены при числе итераций N0= 1000 и размере популяции ^ от 400 до 500, для задачи об экстремальном пути, и при N0 = 1500, = 500 для задачи коммивояжера. По результатам экспериментов, для каждого алгоритма и операторов даны рекомендации оптимальных параметров, обеспечивающих возможность получения набора локально — оптимальных решений: вероятность оператора кроссинговера для задачи об экстремальном пути должны быть в пределах 0,7−0,8, для задачи коммивояжера — 0,6 — 0,7- вероятность оператора мутации для задачи об экстремальном пути — 0,4, для задачи коммивояжера 0,3 — 0,4, оператора миграции — 0,7. При данных значениях параметров обеспечиваются наилучшие условия для нахождения оптимального решения.

5. Бионические и параллельные бионические алгоритмы для решения задач транспортного типа показали преимущество по качеству решений, по сравнению с существующими методами на 10% - 15%. Управление процессом бионического и параллельного бионического поиска, позволяет находить оптимальные параметры и повысить качество решений ориентировочно на 15% - 20%. Параллельный бионический алгоритм улучшил решение задачи на 12% -20% при больших (п>1500) размерностях задачи.