Введение к работе
Актуальность темы. Задачи транспортного типа занимают особое место в классе приоритетных направлений исследования информационных технологий, так как решение задач данного типа имеет актуальное значение в промышленности, на транспорте, в системах связи и других отраслях народного хозяйства.
Сегодня практически невозможно обеспечить требуемое потребителями качество обслуживания и эффективность транспортных операций без применения информационных систем и программных комплексов для анализа, планирования и поддержки принятия коммерческих решений. Благодаря разработке эффективных методов решения задач транспортного типа, стали развиваться информационные системы и технологии, обеспечившие возможность автоматизации типовых операций в транспортных процессах, для организации товародвижения на технологическом рынке транспортных услуг.
О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 таблиц.
