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

На правах рукописи Полуян Анна Юрьевна ИССЛЕДОВАНИЕ И РАЗРАБОТКА БИОНИЧЕСКИХ МЕТОДОВ И АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ ТРАНСПОРТНОГО ТИПА Специальность 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) сij0; сjj=∞, (4) сij= сji, (5) сij+ сjkсik. (6) Ограничения (4)-(6) означают, что сij - расстояния должны быть неотрицательными, симметричными и удовлетворять неравенству треугольника для всех jN. В ходе сравнения существующих методов и алгоритмов решения задач об экстремальном пути и задачи коммивояжера, были показаны преимущества и недостатки каждого из этих методов. Из приведенных сравнительных результатов видно, что для нахождения экстремального пути на графе, предпочтительнее выбирать генетический и эволюционный алгоритмы, они значительно уменьшают ВСА и улучшают качество решений. Отмечено, что основным средством для повышения быстродействия и качества решений, является разработка совместных бионических и поисковых алгоритмов, позволяющих решать проблемы предварительной сходимости, получать наборы эффективных решений и среди них выбрать оптимальное. Во второй главе предложен новый подход к кодированию хромосомы для задачи об экстремальных путях. Он является наиболее простым в реализации и достаточно эффективным для решения задач данного типа и заключается в следующем. Каждому гену хромосомы ставится в соответствие определённый статус: фиксированный элемент (позиция элемента, который кодируется текущим геном, является постоянной). В процессе выполнения генетических операторов ген не меняет своего значения; свободный элемент (элемент, который не повторяется в пути, такие элементы размещаются в самую последнюю очередь). Статусы генов позволят наиболее эффективно производить процесс декодирования. При решении задач об экстремальных путях, эффективно используют стратегии, концепции, методы и механизмы эволюционного моделирования на основе бионического поиска. Приведены технологии формирования и преобразования популяции при переходе из одной генерации в другую, с использованием эволюционной адаптации на основе эволюций Дарвина или Ламарка, позволяющие находить оптимальные решения. Построены новые и модифицированные эволюционные и генетические операторы мутации, кроссинговера, сегрегации, инверсии, селекции, миграции, ориентированные на создание алгоритмов бионического поиска при решении задач транспортного типа, которые позволяют частично решать проблемы сходимости генетических алгоритмов и дают механизм синхронизации полученных решений на всех этапах поиска (оператор миграции), увеличивающие вероятность «выживания» альтернативных решений с лучшим значением ЦФ на 10% -15%. При разработки бионического алгоритма, предложена адаптивная стратегия работы модифицированного оператора рекомбинации (МОР). Пути выполнения рекомбинации разбиты на два этапа: 1. Исследование влияния изменения размера популяции на характеристики бионического поиска. 2. Разработка формулы изменения размера популяции на основе результатов, полученных на первом этапе. В результате решения первого этапа на основании экспериментальных данных, предложена следующая реализация общей стратегии адаптации размера популяции, использованием последовательности решета Эратосфена, позволяющая адаптироваться к характеристикам бионического поиска: N(t+1)= N(t)+( N(t)-KI)*z(t)/qN, KI=(1-p(xkt)*Rp, , , где KI – количество элитных особей, Rp – размер популяции, где N(t) – размер популяции в поколении t ; uk – k-й член последовательности решета Эратосфена; q(t) – направление изменения (увеличение или уменьшение) размера популяции в поколении t ; F(t) – значение целевой функции в популяции; k – количество поколений, в течение которых, направление q изменения размера популяции остается постоянным. При дальнейшей реализации алгоритма лучшие и отобранные элементы из родителей и потомков будут выбираться для формирования новой популяции. На основе разработанных операторов построена модифицированная базисная структура оптимизационного процесса, основанная на принципах бионического поиска для решений задач об экстремальных путях (рис.1). Ее преимущество состоит в том, что в ней все строительные блоки связаны с блоком адаптации, но и каждый из них может выполняется отдельно и (при необходимости) осуществляет взаимодействие с другими блоками. Блок адаптации предназначен для выбора и реализации различных стратегий и механизмов адаптации. Предназначение данного блока состоит в настройке и изменении порядка использования и применения различных генетических операторов и схем поиска. Результаты работы блока эволюционной адаптации оказывают непосредственное влияние на выбор эволюции Дарвина или Дарвина – Ламарка, так же на процесс перестройки текущей популяции альтернативных решений и создания на ее основе новой популяции. Определяющими эволюцию, служат модифицированные операторы мутации, реализующиеся под действием естественного отбора. Взаимодействие бионического поиска с эвристическим алгоритмом позволяет производить адаптацию наборов параметров и фокусировать наилучшие решения. Проводимая сортировка текущей популяции альтернативных решений позволяет повысить эффективность бионического поиска за счет большей структурированности множества альтернативных решений и дает возможность регулировать направление поиска. Таким образом, появляется дополнительный инструмент для самоадаптации и настройки параметров бионического поиска. Рис. 1. Модифицированная базисная структура оптимизационного процесса для задачи об экстремальном пути Блок анализа неперспективных решений собирает и анализирует решения, получаемые в процессе выполнения бионического поиска. В результате проведенного анализа полученные решения сортируются. К неперспективным решениям применяется эволюционный алгоритм, с целью улучшения качества решений. На основе модифицированной базисной структуры оптимизационного процесса и модифицированных генетического и эволюционного алгоритмов, разработан параллельный бионический алгоритм с моделью островов (рис. 2), так как он наиболее полно позволяет использовать ресурсы современных многоядерных микропроцессоров, при применении которых можно разделить и запараллелить этапы вычислений, связанных с выполнением бионического алгоритма в одной из подпопуляций решений. Рис. 2. Структурная схема параллельного бионического алгоритма для задачи об экстремальном пути Построенная структурная схема параллельного бионического алгоритма для нахождения экстремального пути, обеспечивает поддержку следующих действий: анализ решаемой задачи и построение математической модели; создание начальных популяций альтернативных решений на основе результатов выполнения п. 1 и выбора стратегии формирования начальной популяции; разбиение популяции на четыре части; применение методов бионического поиска в соответствие с выбранным критерием оценки качества решений к полученным подпопуляциям: реализация быстрого эволюционного поиска (использование оператора мутации); выполнение генетического поиска (использование различных генетических операторов); адаптация полученных решений к внешней среде на основе метаэволюции (использование оператора миграции), переход к следующей генерации; провести анализ полученных данных, в случае если критерий останова достигнут; вывод лучших решений. Как указывалось выше, генетические алгоритмы и эволюционные алгоритмы образуют бионический поиск (БП). Отметим, что периодически в каждой итерации БА можно проводить различные изменения в перспективных, неперспективных и в других решениях. Временная сложность алгоритма лежит в пределах O(n2). Миграция определяет качество поиска и эффективность алгоритма. Частая миграция приводит к обмену потенциально полезным генетическим материалом, но в этом случае отрицательным эффектом является увеличение затрат на обмен информацией. Это наиболее существенно при топологии связей, в которой каждая популяция обменивается со всеми другими. Для повышения скорости необходимо найти баланс между уровнем миграции и качеством решения. Для этого предлагается ввести уровень миграции следующим образом: если значение целевой функции не меняется или ухудшилось за последние t поколений, то развитие подпопуляции не приводит к появлению лучших решений, в таком выполняется миграция. Приведена технология преобразования популяции при переходе из одной итерации поиска в другую, позволяющая закреплять оптимальные решения, на основе использования разработанного оператора миграции. Третья глава посвящена решению задачи коммивояжера на основе бионического поиска. Проведен анализ и выбор модели представления решения задачи. Представление задачи коммивояжера в виде матрицы смежности дает возможность анализировать шаблоны (решения), которые применимы для n-размерной оптимизации. Шаблоны, определенные в терминах единственной опре­деленной позиции, соответствуют естественным строи­тельным блокам, то есть элементам для задачи коммивояжера. Создание начального множества решений происходит по принципу «дробовика» т.е. подразумевается случайный выбор альтернатив из всей области решений задачи коммивояжера. Разработаны новые и модифицированные генетические операторы, ориентированные на решения задачи коммивояжера. На основании проведенных тестов, бионические алгоритмы, построенные на основе стандартных генетических операторов, не гарантируют нахождение оптимального решения. В связи с этим для нахождения оптимальных решений используются предложенные генетические операторы, увеличивающие вероятность «выживания» альтернативных решений с лучшим значением ЦФ на 10% - 15%. Приведем процедуру построения модифицированного оператора миграции. Одной из важных проблем является определение необходимого оптимального количества хромосом из подпопуляций для миграции при работе параллельного бионического алгоритма, от количества хромосом зависит время и экономичность работы алгоритма, для этого предлагается использовать формулу отбора необходимой численности хромосом: где n – количество отобранных хромосом для миграции; ∆ - предельная ошибка выборки, представляет собой предел, которым ограничена сверху абсолютная величина ; - среднеквадратичное отклонение; t – коэффициент, определяемый по таблице Лапласа, Ф(t)=р, где р – заданная вероятность оператора миграции, определяемая лицом принимаемым решение. Проведенные тесты показывают, что использование модифицированного оператора миграции, позволяет сократить время работы алгоритма. Выполнение бионического поиска осуществляется на основе комбинированной стратегии «эволюция – поиск – эволюция». Структурная схема алгоритма бионического поиска для решения задачи коммивояжера представлена на рис. 3, где МГА ЗК и ЭА ЗК – модифицированный генетический алгоритм задачи коммивояжера и эволюционный алгоритм задачи коммивояжера. Разработанный бионический алгоритм, основан на использовании методов эволюционного моделирования, усовершенствованного бионического поиска для решения задачи коммивояжера. В данном алгоритме используются идеи совместной эволюции, выбор моделей эволюции (использование микро-, макро-, метаэволюции), адаптации к внешней среде, а так же иерархическое управление генетическим и эволюционным поиском, локальный поиск решений на основе поисковых методов и «жадной» стратегии. Основная особенность модифицированного генетического алгоритма состоит в том, что анализируется не одно решение, а некоторое подмножество квазиоптимальных решений. Построенный генетический алгоритм ликвидирует имеющиеся пересечения в маршрутах, используя оператор инверсии, а также применяет к каждой хромосоме операцию разнообразия. Операция разнообразия вносит некоторые изменения в отдельную хромосому. Модифицированного генетический алгоритм поддерживает такую архитектуру генетического поиска, при которой целенаправленное изменение применяется ко всем вновь созданным хромосомам. Эволюционные алгоритмы в основном ориентированы на работу с оператором мутации. Инструментом адаптации является конкуренция между всеми хромосомами за возможность включения в следующую популяцию. «Жадные» стратегии, основанные на знаниях о задаче коммивояжера, улучша­ют скорость сходимости, однако часто препятствуют выхо­ду из локальных минимумов. Существует несколько путей избежать этой ситуации: изменить архитектуру БА или же не помещать такие решения в популяцию. Для повышения эффективности эволюционного и модифицированного генетического алгоритмов, разработаны усовершенствованные генетические операторы, для реализации бионического и параллельного бионического поиска. Основным способом повышения скорости работы бионического алгоритма является распараллеливание. Популяция разделяется на несколько различных частей, которые впоследствии развиваются параллельно и независимо. То есть скрещивание происходит только между членами одной части. На каком-то этапе работы происходит обмен особями между частями популяции, на основе модифицированного оператора мутации. И так может продолжаться до завершения работы алгоритма. На основании бионического алгоритма для решения задачи коммивояжера на рис.4 представлена схема алгоритма параллельного бионического поиска для решения задачи коммивояжера, где БП1, БП2 – бионические поиски для частей популяций. Рис.4. Схема алгоритма параллельного бионического поиска для решения задачи коммивояжера В четвёртой главе описаны задачи и цели вычислительного эксперимента. Составлен комплекс программ на основе разработанных алгоритмов решения задач об экстремальном пути на графе, который реализован на языке С++ под Windows ХР. Эксперименты проводились на ЭВМ типа IBM PC с процессором Pentium 4. Графический интерфейс пользователя программного комплекса представлен на рис. 5. Рис. 5. Графический интерфейс пользователя программного комплекса На тестовых примерах проведены экспериментальные исследования по данным алгоритмам. Определены области эффективного применения каждого алгоритма в зависимости от управления процессом бионического поиска. На рис. 6, 7 приведены гистограммы эффективности работы бионического и параллельного бионического алгоритма по сравнению с известными методами. Из гистограмм видно, что при размерностях задачи 500N2). Рис. 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 заданий) Цель заданий — проверка усвоения знаний и получение навыка применения этих знаний для решения практических задач в области криптографических...