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

Полу ян Анна Юрьевна

ИССЛЕДОВАНИЕ И РАЗРАБОТКА БИОНИЧЕСКИХ МЕТОДОВ И АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ ТРАНСПОРТНОГО ТИПА

Специальность 05.13.17 - теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

о 3 023 2011

Ростов-на-Дону 2011

4843570

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

Научный руководитель:

Заслуженный деятель науки РФ доктор технических наук, профессор Чернышев Юрий Олегович

Официальные оппоненты:

Доктор технических наук, профессор Ромм Яков Евсеевич

Заслуженный деятель науки РФ доктор технических наук, профессор Безуглов Дмитрий Анатольевич

Ведущая организация:

Ростовский государственный университет путей сообщения (РГУПС), г. Ростов-на-Дону

Защита диссертации состоится « 18 » февраля 2011 г. в 1420 на заседании диссертационного совета Д.212.208.21 Южного федерального университета гю адресу: пер. Некрасовский, 44, ГСП-17А, г. Таганрог, Ростовская область, 347928, аудитория Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: ул. Пушкинская, 148, г. Ростов-на-Дону, 344400.

Автореферат разослан « 15 » января 2011 г.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: пер. Некрасовский, 44, ГСП-17А, г. Таганрог, Ростовская область, 347928, диссертационный совет Д 212.208.21.

Ученьш секретарь

диссертационного совета Д 212.208.21

доктор технических наук, /",' : Чернов Н.И.

профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.0В: "Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования сверхбольших интегральных схем (СБИС)" (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 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Тогда типичной задачей транспортного типа является задача нахождения некоторого маршрута (пути) из пункта А в пункт В. На допустимые маршруты может быть наложен ряд ограничений: вводят запрет на возврат к уже пройденному пункту или требование обхода всех пунктов с условием, что в каждом пункте можно побывать лишь один раз, или нахождение кратчайшего пути из пункта А и пункт В. Это в полной мере относится к задачам об экстремальном пути на графе и задачи коммивояжера.

Решаемые в диссертационной работе задачи, могут быть сформулированы следующим образом.

Пусть дан граф 0=(Х,и) дугам которого приписаны веса (стоимости), задаваемые матрицей С = [с;у ]. Задачи об экстремальном пути состоят в нахождении самого кратчайшего

или самого длиннейшего пути от заданной начальной вершины 5 е X до заданной конечной вершины (бХ, при условии, что такой путь существует. Элементы Сц матрицы весов С

могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в в не было циклов с отрицательным суммарным весом.

Математическую модель задачи о кратчайшем пути можно записать в общем виде:

X тт. (1)

(I =

2Х- Е *,>= |о,г*М, (2)

<г,у)6[/ \-\r-t

Задача о максимальном (длиннейшем) пути сводится к задаче о кратчайшем пути на графе - достаточно изменить знаки дуг на противоположные. Для существования решения задачи о максимальном пути необходимо и достаточно отсутствия контуров положительной длины.

К задачам поиска кратчайших или длиннейших путей или контуров, проходящих через все вершины графа относится задача коммивояжера (ЗК).

Классическая постановка задачи о коммивояжере выглядит следующим образом:

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

• маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

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

Запишем математическому модель задачи коммивояжера. Путь коммивояжера может быть описан циклической перестановкой ф=(Ь причём все ^...¡п - разные вершины;

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

£ = ДО = ->™П. (3)

к=1

су>0; с^=°о, (4)

<=Г сл> (5)

Су+ С^>С;к. (6)

Ограничения (4)-(6) означают, что с у - расстояния должны быть неотрицательными, симметричными и удовлетворять неравенству треугольника для всех ]е!Ч.

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

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

• фиксированный элемент (позиция элемента, который кодируется текущим геном, является постоянной). В процессе выполнения генетических операторов ген не меняет своего значения;

• свободный элемент (элемент, который не повторяется в пути, такие элементы размещаются в самую последнюю очередь).

Статусы генов позволят наиболее эффективно производить процесс декодирования.

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

Построены новые и модифицированные эволюционные и генетические операторы мутации, кроссинговера, сегрегации, инверсии, селекции, миграции, ориентированные на создание алгоритмов бионического поиска при решении задач транспортного типа, которые

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

При разработки бионического алгоритма, предложена адаптивная стратегия работы модифицированного оператора рекомбинации (МОР). Пути выполнения рекомбинации разбиты на два этапа:

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

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

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

N(1+1)= 1Ч(0+( Н(0-К1)*г(1)/ям К1=(1-р(хк1)*Яр,

\-l,F(t)>F(t + \)

,Л_ к,9(0 = <?('-!)

где KI - количество элитных особей, Rp - размер популяции, где N(t) - размер популяции в поколении t ; и* - к-й член последовательности решета Эратосфена; q(t) - направление изменения (увеличение или уменьшение) размера популяции в поколении t; F(t) - значение целевой функции в популяции; к - количество поколений, в течение которых, направление q изменения размера популяции остается постоянным.

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

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

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

Выход

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

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

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

Рис. 2. Структурная схема параллельного бионического алгоритма для задачи об экстремальном пути

и

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

1. анализ решаемой задачи и построение математической модели;

2. создание начальных популяций альтернативных решений на основе результатов выполнения п. 1 и выбора стратегии формирования начальной популяции;

3. разбиение популяции на четыре части;

4. применение методов бионического поиска в соответствие с выбранным критерием оценки качества решений к полученным подпопуляциям:

реализация быстрого эволюционного поиска (использование оператора мутации); выполнение генетического поиска (использование различных генетических операторов);

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

6. провести анализ полученных данных, в случае если критерий останова достигнут;

7. вывод лучших решений.

Как указывалось выше, генетические алгоритмы и эволюционные алгоритмы образуют бионический поиск (БП). Отметим, что периодически в каждой итерации БА можно проводить различные изменения в перспективных, неперспективных и в других решениях. Временная сложность алгоритма лежит в пределах 0(п2). Миграция определяет качество поиска и эффективность алгоритма. Частая миграция приводит к обмену потенциально полезным генетическим материалом, но в этом случае отрицательным эффектом является увеличение затрат на обмен информацией. Это наиболее существенно при топологии связей, в которой каждая популяция обменивается со всеми другими. Для повышения скорости необходимо найти баланс между уровнем миграции и качеством решения. Для этого предлагается ввести уровень миграции следующим образом: если значение целевой функции не меняется или ухудшилось за последние I поколений, то развитие подпопуляции не приводит к появлению лучших решений, в таком выполняется миграция.

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

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

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

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

алгоритма, для этого предлагается использовать формулу отбора необходимой численности хромосом:

l'a'

л'

где п - количество отобранных хромосом для миграции;

Д - предельная ошибка выборки, представляет собой предел, которым ограничена сверху абсолютная величина < А ; а - среднеквадратичное отклонение;

t - коэффициент, определяемый по таблице Лапласа, ®(t)=p, где р - заданная вероятность оператора миграции, определяемая лицом принимаемым решение.

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

Выполнение бионического поиска осуществляется на основе комбинированной стратегии «эволюция - поиск - эволюция». Структурная схема алгоритма бионического поиска для решения задачи коммивояжера представлена на рис. 3, где МГА ЗК и ЭА ЗК -модифицированный генетический алгоритм задачи коммивояжера и эволюционный алгоритм задачи коммивояжера.

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

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

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

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

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

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

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

Выход

Рис. 3 Структурная схема алгоритма бионического поиска для задачи коммивояжера

На основании бионического алгоритма для решения задачи коммивояжера на рис.4 представлена схема алгоритма параллельного бионического поиска для решения задачи коммивояжера, где БП1, БП2 - бионические поиски для частей популяций.

Вывод полученного результата

I

Конец

Рис.4. Схема алгоритма параллельного бионического поиска для решения задачи коммивояжера

В четвёртой главе описаны задачи и цели вычислительного эксперимента. Составлен комплекс программ на основе разработанных алгоритмов решения задач об экстремальном пути на графе, который реализован на языке С++ под Windows ХР. Эксперименты проводились на ЭВМ типа IBM PC с процессором Pentium 4. Графический интерфейс пользователя программного комплекса представлен на рис. 5.

иш

Я.

я

Г- ^

~и О. _ Ни

Чп

Ч,

я

■¿-in

Ч,

'V

ж

м:

"3

F В

Рис. 5. Графический интерфейс пользователя программного комплекса На тестовых примерах проведены экспериментальные исследования по данным алгоритмам. Определены области эффективного применения каждого алгоритма в зависимости от управления процессом бионического поиска. На рис. 6, 7 приведены гистограммы эффективности работы бионического и параллельного бионического алгоритма по сравнению с известными методами. Из гистограмм видно, что при размерностях задачи 500<п<1500, бионический алгоритм, показал наиболее качественные решения на 5%-10%, при размерностях задачи п>1500 параллельные бионические алгоритмы для решения задач транспортного типа показали преимущество по сравнению с существующими, по качеству решения на 15%-20%. Проведенные исследования подтвердили теоретические оценки временной сложности параллельного бионического алгоритма, которая составляет 0(аЫ2).

Рис. 6. Результат работы алгоритмов для задачи о кратчайшем пути

кол-во вершин графа

Рис. 7. Результат работы алгоритмов для задачи коммивояжера

В заключении сформулированы основные выводы и результаты диссертационной работы.

В приложении приведены акты об использовании результатов диссертационной работы и приведено описание комплекса программ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

4. Разработан комплекс программ на основе бионического и параллельного бионического поиска. Экспериментальные исследования параллельного бионического алгоритма показали, что наиболее качественные решения были получены при числе итераций Ng= 1 ООО и размере популяции Np от 400 до 500, для задачи об экстремальном пути, и при Ng = 1500, Np= 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) размерностях задачи.

Основные положения диссертации изложены в 16 работах, из них в изданиях, входящих в

перечень ВАК - 5 работ.

Работы, опубликованные в изданиях из перечня ВАК:

1. Касаткин Г.М., Таможникова А.Ю. Приближенное решение задачи о коммивояжере.// Известия ТРТУ. Таганрог. ТРТУ. - 2006. - № 8.

2. Чернышев Ю.О., Полуян А.Ю. Адаптивный генетический алгоритм для решения задачи оптимизации на основе стратегии элитизма..// Известия ТРТУ. Таганрог. ТРТУ. - 2008. - № 4.

3. Чернышев Ю.О., Белявский П.Г, Полуян А.Ю. Эволюционный подход к решению задачи о назначении через определение кратчайшего пути.// Известия ТРТУ. Таганрог. ТРТУ. - 2008. -№9.

4. Полуян А.Ю. Адаптивный генетический алгоритм задач оптимизации на основе стратегии элитизма. // Известия ТРТУ. Таганрог. ТРТУ. - 2008. - № 9.

5. Чернышев Ю.О., Полуян А.Ю. Решение задачи оптимизации на основе параллельного бионического поиска.// Известия ТРТУ. Таганрог. ТРТУ. - 2009. - № 4.

Публикации в других изданиях:

6. Таможникова А.Ю. Решение задачи о нахождении кратчайшего пути в графе с использованием генетического алгоритма. Труды международных научно-технических конференций «Интеллектуальные системы (IEE A1S'05)» и «Интеллектуальные САПР (CAD-2005)» Научное издание в 4-х томах. М.: Изд-во «Физматлит», 2005.- Т. 4.

7. Чернышев Ю.О., Посупонько Н.В., Таможникова А.Ю. Генетический алгоритм выбора оптимального варианта системы обнаружения ошибок по критерию достоверности. Труды международных научно-технических конференций «Интеллектуальные системы (IEE A1S'05)» и «Интеллектуальные САПР (CAD-2005)» Научное издание в 4-х томах. М.: Изд-во «Физматлит», 2005.- Т. 2.

8. Смирнова О.В. Таможникова А.Ю. Генетический алгоритм решения задачи коммивояжера.// Научные труды Ростовской-на-Дону Государственной академии сельскохозяйственного машиностроения: сборник научных трудов - Ростов н/Д, 2006.

9. Смирнова О.В. Таможникова А.Ю. Алгоритм решения задач коммивояжера с использованием эволюционных методов.// Безопасность жизнедеятельности. Охрана труда и окружающей среды: межвузовский сборник научных трудов /РГАСХМ. - Ростов н/Д, 2007. -Вып. 11.

10. Чернышев Ю.О., Полуян А.Ю., Демчук Г.В. Выбор оптимального варианта системы обнаружения ошибок по критерию достоверности. Труды международных научно-технических конференций «Интеллектуальные системы (IEE AIS'07)» и «Интеллектуальные САПР (CAD-2007)» М.: Изд-во «Физматлит», 2007.- Т. 2.

11. Чернышев Ю.О., Басова A.B., Полуян А.Ю. Решение задач транспортного типа генетическими алгоритмами. Монография. Ростов н/Д: Изд-во ЮФУ, 2008

12. Полуян А.Ю.Эволюционный подход к решению задач о нахождении кратчайшего пути в графе.// Информационные технологии в профессиональной деятельности и научной работе: сборник материалов всероссийской научно-практической конференции с международным участием / МГТУ. - Йошкар-Ола, 2008.-Т.2.

13. Смирнова О.В., Полуян А.Ю. Анализ алгоритмов для решения комбинаторных задач.// Безопасность жизнедеятельности. Охрана труда и окружающей среды; межвузовский сборник научных трудов /РГАСХМ. - Ростов н/Д, 2008.

14. Смирнова О.В., Полуян А.Ю. Эволюционный подход к выбору решения задач о нахождении кратчайшего пути в графе.// Новые технологии, конструкции и процессы производства: сборник научных трудов /РГАСХМ ГОУ. - Ростов н/Д, 2008.

15. Полуян А.Ю. Адаптивный генетический алгоритм для решения задач максимальном пути в графе на основе стратегии элитизма.// Модели и алгоритмы для имитации физическо-химических процессов: сборник материалов международной научно-технической конференции / ТГПИ. - Таганрог, 2008.

16. Чернышев Ю.О., Полуян А.Ю. Решение задачи о потоке минимальной стоимости на основе параллельного бионического поиска.// Сборник научных трудов «Проблемы создания информационных технологий» Вып.2, международное научно общественное объединение «МАИТ», М.: 2010.

В работах опубликованных в соавторстве, А.Ю. Полуян принадлежат следующие результаты: в [1] разработан приближенный метод решения задачи коммивояжера; в [2,3,7,8] разработаны модифицированные генетические алгоритмы и операторы для решения поставленных задач; в [5,9,13,14,16] разработаны алгоритмы последовательного и параллельного бионического поиска, на основе эволюционной адаптации, проведены сравнительные оценки полученных методов; в [11] исследованы математические модели задач транспортного типа, проведен анализ существующих методов и алгоритмов для решения задач данного типа, разработаны модифицированные генетический и эволюционный алгоритмы для решения задач о кратчайшем пути и коммивояжера.

Соискатель

А.Ю. Полуян

Подписано в печать 11.01.2011 г. Формат 60x84 '/к>- Бумага офсетная. Гарнитура Школьная. Печать офсетная. Усл. печ. л. 1,0. Уч. -изд. л. 1,0. Тираж 100 экз. Заказ № 1529.

Типография Южного федерального университета 344090, г. Ростов-на-Дону, пр. Стачки, 200/1, тел (863) 247-80-51.

Введение

Глава 1.

Математические модели задач транспортного типа и методы 15 их решения

1.1. Прикладные задачи транспортного типа как объект 15 математического моделирования

1.2. Математические модели и анализ классических алгоритмов 16 решения задач о кратчайшем и длиннейшем пути на графе

1.3. Математическая модель и алгоритмы решения 21 задачи коммивояжера

1.4. Анализ методов эволюционного моделирования

1.5. Выводы

Глава 2.

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

2.1. Построение решения задач 36 2.1.1. Кодирование решений задач

2.2. Стратегии формирования и развития начальной популяции

2.3. Построение модифицированных генетических операторов 43 для моделирования задачи нахождения экстремального пути

2.4. Организация процедур моделирования бионического и 58 параллельного бионического поиска

2.4.1. Разработка бионического алгоритма

2.4.2. Разработка модифицированной базисной структуры 68 оптимизационного процесса, основанной на принципах бионического поиска

2.4.3. Построение структурной схемы параллельного бионического алгоритма

2.5. Выводы

Глава 3.

Организация процедур моделирования бионического и параллельного бионического поиска для решения задачи коммивояжера

3.1. Анализ особенностей моделей

3.2. Моделирование начальной популяции "

3.3. Моделирование модифицированных генетических операторов 81 для решения задачи коммивояжера

3.4. Разработка структуры бионического поиска на основе 88 эволюционных стратегий

3.4.1. Построение модифицированного генетического алгоритма 92 для формирования бионического поиска

3.4.2. Разработка модифицированного эволюционного алгоритма

3.5. Построение структурной схемы параллельного бионического 96 поиска

3.6. Выводы

Глава 4.

Экспериментальное исследование программного комплекса, разработанных алгоритмов

4.1. Цель и средства экспериментальных исследований

4.2. Краткие сведения об инструментальной среде программного комплекса

4.3. Результаты экспериментальных исследований 109 задачи о кратчайшем пути

4.4. Результаты экспериментальных исследований 127 задачи коммивояжера

4.5. Выводы 143 Заключение 144 Список используемой литературы 146 Приложения

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

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

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

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

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

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

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

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

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

В связи с этим, с целью снижения временной сложности алгоритмов (ВСА), актуальным является разработка последовательных и параллельных бионических алгоритмов для решения задач об экстремальных путях. В них применяются случайные правила поиска, что позволяет избежать локальные "ловушки" [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г.); "Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования, сверхбольших интегральных схем (СБИС)" № Г/Р 01201051299 (1.01.2008 -31.12.2009); «Развитие теории бионического моделированиядля решения оптимизационных задач транспортного типа» (1.01.2010 - 31.12.2011). Материалы диссертации использованы в научно-исследовательских работах, выполненных по гранту № 10-01-00481-а на тему: «Развитие теории и практики применения интеллектуальных методов в распределительных системах управления базами данных», финансируемому Российским фондом фундаментальных исследований (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) размерностях задачи.

1. Курейчик, В.В. Эволюционные, синергетические и гомеостатические методы принятия решений Текст.: моногр./ В.В. Курейчик. Таганрог: Изд-во ТРТУ, 2001. - 221с.

2. Курейчик, В.М. Совместные методы квантового и бионического поиска Текст./ В.М. Курейчик // Интеллектуальные системы (IEE AIS'04). Интеллектуальные САПР (CAD-2004): тр. междунар. науч.-техн. конф./ ТРТУ. — М.: Физматлит, 2004. с. 12-19.

3. Koza, J.R. Genetic Programming. Cambridge: /MA. - MIT Press, 1998.-609p.

4. Курейчик, В.М. Генетические алгоритмы и их применение Текст.: моногр./ В.М. Курейчик. Таганрог: Изд-во ТРТУ, 2002. - 242с.

5. Емельянов, В.В. Теория и практика эволюционного моделирования Текст./ В.В. Емельянов, В.М. Курейчик, В.В. Курейчик. М: Физматлит, 2003.-432с.

6. Ахо, А. Построение и анализ вычислительных алгоритмов Текст./ А. Ахо. -М.: Наука, 1968. 386с.

7. Липский, В. Комбинаторика для программистов Текст. / В. Липский; пер. с пол. В.А. Евстигнеева, O.A. Логиновой М.: Мир, 1988.-200с.

8. Бурков, В.Н. Прикладные задачи теории графов Текст./ В.Н. Бурков, И.А. Горгидзе, С.Е. Ловецкий. Тбилиси: Мецниереба, 1974.-384с.

9. Гладков, Л.А. Оптимизация на основе методов гомеостатики, эволюционного развития и самоорганизации Текст./ Л.А. Гладков, Л.А. Зинченко, В.В. Курейчик, В.М. Курейчик. Таганрог: Изд-во ТРТУ, 2006. - 307с.

10. Mark W.K. Mic Cut Partitioning With Functional Replication for Technology // Mapped Circuits Using Minimum Area Over heed. - V.21, № 4, april 2002. - p. 491 - 496.

11. Гладков, Л.А. Методы генетического поиска Текст./ Л.А. Гладков-Таганрог: Изд-во ТРТУ, 2002.-122с.

12. Бернштейн, JI.С. Модели и методы принятия решений в интегрированных искусственных ' системах Текст./ Л.С. Бернштейн, В.П. Кармен, А.Н. Целых Ростов-н/Д: Изд-во Ростовский университет, 1999. — 120с.

13. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975. 21 Op.

14. Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. MA: Addison-Wesley, 1989. 412p.

15. Blickle, T. A Comparison of Selection Schemes used in Genetic Algorithms (2nd Edition)./ T. Blickle, L.Thiele. TIK-Report No. 11. — Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, 1995.

16. Цой, Ю.Р. К выбору размера популяции Текст./ Ю.Р. Цой, В.Г. Спицын // Интеллектуальные системы (IEE AIS'04). Интеллектуальные САПР (CAD-2004): тр. междунар. науч.- техн. конф./ ТРТУ. М.: Физматлит, 2004. - с.90-96

17. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика Текст./ Э. Рейнгольд, Ю. Нивергельт, Н. Део. М.: Мир, 1980. -476с.

18. Гладков, Л.А. Генетические алгоритмы Текст./Л.А. Гладков, В.М. Курейчик, В.В. Курейчик. Ростов н/Д: Ростиздат, 2004. - 395с.

19. Глушань, В.М. Графовые модели представления вычислительных алгоритмов Текст./ В.М. Глушань // Интеллектуальные системы (IEE AIS'03). Интеллектуальные САПР (CAD-2003): тр. междунар. науч.- техн. конф./ ТРТУ. М.: Физматлит, 2003. - с. 133-138

20. Курейчик, В.М. Генетические алгоритмы. Обзор и состояние Текст./ В.М. Курейчик // Новости искусственного интеллекта./ М.: Изд-во Российская ассоциация искусственного интеллекта, 1988. -№3.- с. 16-64

21. Kureichik, V.V. Genetic Algorithm. HG Текст./ V.V. Kureichik, V.M. Kureichik. Yerlag Konstans, 2004.

22. Practical Handbook of Genetic Algorithm. Editor I. Chambers Текст. Т 3. Washington, USA, CRC Press, 1995. - 501p.

23. Practical Handbook of Genetic Algorithm. Editor I. Chambers Текст. T 2. Washington, USA, CRC Press, 1999. - 659p.

24. Курейчик, В.М. Совместные методы квантового и бионического поиска Текст./ В.М. Курейчик // Труды конференций IEEE AIS'04, CAD-2004, M.: Физматлит, 2004. с. 12-19.

25. Мищенко, М.Н. Операторы мутации в эволюционных алгоритмах размещения Текст./М.Н. Мищенко/ЛТерспективные информационные технологии интеллектуальные системы. — Таганрог: Изд-во ТРТУ, 2003. № 4 (16). - с.130-135

26. Яблоков, В.А. Генетика Текст./ В.А. Яблоков М: Наука, 1980. -132с.

27. Курейчик, В.В. Об эволюционном подходе к проблеме принятия решений в неопределенных условиях Текст./В.В. Курейчик// Перспективные информационные технологии интеллектуальные системы. Таганрог: Изд-во ТРТУ, 2000. - № 3. - с. 55-57

28. Полуян, А.Ю. Адаптивный генетический алгоритм для решения задачи оптимизации на основе стратегии элитизма Текст./ А.Ю.

29. Полуян // Известия ЮФУ. Технические науки. Таганрог: Изд-во ТТИ ЮФУ, 2008. - № 9. - с.36-39

30. Эволюционные вычисления и генетические алгоритмы Текст. // Обозрение прикладной и промышленной математики / Сост. Гудман Э.Д., Коваленко А.П. М.: Изд-во ТВП, 1966.

31. Ope, О. Теория графов Текст./ О. Ope M.: Наука, 1968.

32. Дистель, Р. Теория графов Текст./ Р. Дистель. Новосибирск: Изд-во ин-та математики, 2002. — 336с.

33. Касаткин, Г.М. Приближенное решение о коммивояжере Текст./ Г.М. Касаткин, А.Ю., Таможникова // Известия ТРТУ. Темат. вып. «Интеллектуальные САПР». 2006. - № 8. - с. 131-135

34. Базы данных. Интеллектуальная обработка информации Текст./сост. В.В. Корнеев, А.Ф. Гареев, C.B. Васютин, В.В. Райх. — М.: Нолидж, 2000. 352с.

35. Хедрик, Ф. Генетика популяций Текст./ Ф. Хедрик. М: Техносфера, 2003. - 592с.

36. Кристофидес, Н. Теория графов. Алгоритмический подход Текст./ Н. Кристофидес М.: Мир, 1978. - 427с.

37. Кормен, Т. Алгоритмы: построение и анализ Текст./ Т. Кормен, И. Лейзерсон, Р. Риверст. М.: Изд-во МИМО, 2000.

38. Панадимитру, X. Комбинаторная оптимизация. Алгоритмы и сложность Текст./ X. Панадимитру, К. Стайниц. М.: Мир, 1977. - 512с.

39. Новиков, Ф.А. Дискретная математика для программистов Текст./ Ф.А. Новиков. СПб.: Питер, 2000. - 304с.

40. Зыков, A.A. Основы теории графов Текст./А.А.Зыков. М.: Наука, 1987.-382с.

41. Гуляев, В. А. Функциональный контроль цифровых систем. Алгебраический подход Текст./ В. А. Гуляев, В. В. Данилов, Н. В. Колесов, -Киев: Изд-во ИЭД 1983.

42. Йенсен, П. Потоковое программирование Текст./ П. Йенсен, Д. Барнес -М: Радио и связь, 1984. 392с.

43. Смирнова, О.В. Эволюционный подход к выбору решения задач о нахождении кратчайшего пути в графе Текст. / О.В. Смирнова, А.Ю. Полуян // Новые технологии, конструкции и процессы производства: сб. науч. тр. / РГАСХМ. Ростов н/Д, 2008. - с.45-47

44. Чернышев, Ю.О. Решение задач транспортного типа генетическими алгоритмами Текст.: моногр./ Ю.О. Чернышев, A.B. Басова, А.Ю. Полуян. Ростов н/Д: Изд-во ЮФУ, 2008. - 73с.

45. Смирнова, О.В. Алгоритм решения задач коммивояжера с использованием эволюционных методов Текст./ О.В. Смирнова, А.Ю. Полуян// Безопасность жизнедеятельности. Охрана труда и окружающей среды: межвуз. сб. науч. тр. /РГАСХМ. Ростов н/Д,2007. с.52-54

46. Смирнова, О.В. Генетический алгоритм решения задачи коммивояжера Текст./ О.В. Смирнова, А.Ю. Полуян// Научные труды Ростовской-на-Дону государственной академии сельскохозяйственного машиностроения: сб. науч. тр. / РГАСХМ. -Ростов н/Д, 2006. с.76-77

47. Гришухин, В.П. Алгоритмы ветвей и границ в задачах с булевыми переменными, оценка их эффективности Текст./ В.П. Гришухин // Экономика и мат. методы. -1976. Т. 24. — с.757-766

48. Гэри, М. Вычислительные машины и труднорешаемые задачи Текст./ М. Гэри, Д. Джонсон. М.: Мир, 1982. - 416с.

49. Растригин, JI.A. Случайный поиск — специфика, этапы истории и предрассудки Текст. / JI.A. Растригин // Вопросы кибернетики. — 1978.- Вып. 33.-C.3-16

50. Cong, J. Physical Model and Efficient Algorithms for Over-the-Cell Routing in Standard Cell Design/ J. Cong, B. Preas, C. Liu // IEEE Trans. Computer Aided Design.-1993- Vol. 12, № 5. -p.723-734

51. Адлер, Ю.П. Введение в планирование эксперимента Текст./ Ю.П. Адлер-М.: Металлургия, 1968.- 155с.

52. Емельянов, В.В. Модели искусственной жизни в оптимизационных задачах Текст./ В.В. Емельянов, В.П. Афонин // Интеллектуальные системы (А18'04). Интеллектуальные САПР (САБ'-2004): тр. междунар. науч.- техн. конф./ ТРТУ. М.: Физматлит, 2004. - с.39-47

53. Курейчик, В.М. Эволюционное моделирование с использованием динамических параметров Текст./ В.М. Курейчик, Л.А. Зинченко// Труды VII национальной конференции по искусственному интеллекту. М.: Физматлит, 2000. - с.516-523

54. Зинченко, Л.А. Алгоритмы численно — аналитического моделирования и средства программной поддержки САПР Текст./ Л.А. Зинченко Таганрог: Изд-во ТРТУ, 1999. - 194с.

55. Курейчик, В.М. Адаптация на основе самообучения Текст. / В.М.Курейчик, Б.К. Лебедев, О.Б. Лебедев, Ю.О. Чернышев. -РГАСХМ: Ростов н/Д, 2004. - 142с.

56. Эвоинформатика. Теория и практика эволюционного моделирования Текст./ сост. И.Л. Букатова — М.: Наука, 1991. — 206с.

57. Применение математических методов и ЭВМ. Планирование и разработка результатов эксперимента Текст.: учеб. пособие. -Минск: Высш. шк., 1989.

58. Лебедев, Б.К. Принципы построения виртуальных популяций Текст. / Б.К. Лебедев, О.Б. Лебедев // Известия ТРТУ. 2005. - № 9. - с.82-83

59. Ойхман, Е.Г. Графические системы для СМ ЭВМ Текст./ Е.Г. Ойхман. -М.: Наука, 1986. 192с.

60. Современная прикладная теория управления: Оптимизационный подход в теории управления. Таганрог: Изд-во ТРТУ, 2000. - 4.1. -400с.

61. Чернышев, Ю.О. Эволюционный подход к решению задачи о назначении через определение кратчайшего пути Текст./ Ю.О. Чернышев, П.Г. Белявский, А.Ю. Полуян // Известия ЮФУ. Техн. науки .-2008.- №9.

62. Форд, JT. Потоки в сетях Текст./ JI. Форд, Д. Фалкерсон. М.: Мир, 1966.-276с.

63. Михалевич, B.C. Исследование методов решения оптимизационных задач и их приложения Текст./ B.C. Михалевич, В.А. Трубин, Н.З. Шор. -М.: Кибернетика, 1981. Вып. №4. с.89-113

64. Волкович, B.JI. Модели и методы оптимизации надежности сложных систем Текст./ B.JI. Волкович, А.Ф. Волошин. Киев: Наукова Думка, 1993.-312с.

65. Карманов, В.Г. Математическое программирование Текст./ В.Г. Карманов. М.: Наука, 1986. - 288с.

66. Ермольев, Ю.М. Экстремальные задачи на графах Текст./ Ю.М. Ермольев, И.В. Мельник. Киев: Наукова Думка, 1968. - 174с.

67. Гришухин, В.П. Алгоритмы ветвей и границ в задачах с булевыми переменными, оценка их эффективности Текст./ В.П. Гришухин// Экономика и мат. методы. 1976. - Т 24. - Вып.4 - с.757-766

68. Caldwell, A.E. Optimal Portitioners and End Case Placers for Standard/ A.E. Caldwell, A.B. Kahng, I.L. Markov //Cell Layout.// 2000. V. 19, № 11.-p. 1304-1313

69. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Vav Nostrand Reinhold.- New York, 1991. p.385

70. Эволюционная эпистемология и логика социальных наук: Карл Попер и его критики Текст. / составит. Д.Л. Лахути, В.Н. Садовский, В.К. Финн. М: Эдиториал УРСС, 2000. - 464с.

71. Балюк, Л.В. Исследование влияния генетических алгоритмов на точность модели Текст./ Л.В. Балюк // Известия ТРТУ- 2003. -№2. с. 32-39

72. Васильев, В.И. Интеллектуальные системы управления с использованием генетических алгоритмов Текст./ В.И. Васильев, Б.Г. Ильясов // Приложение к журналу «Информационные технологии» 2000. - № 12. - 24с.

73. Глушань, В.М. Графовые модели представления вычислительных алгоритмов Текст./ В.М. Глушань // Интеллектуальные системы (IEE AIS'03). Интеллектуальные САПР (CAD-2003): тр. междунар. науч.- техн. конф./ ТРТУ. М.: Физматлит, 2003. - Т.2. - с. 133-138

74. Курейчик, В.В. Программная подсистема по исследованию оптимизационных задач на графах Текст./ В.В. Курейчик // Программные продукты и системы. 2002. - №1.

75. Чипига, А.Ф. Локальная оптимизация в операторах мутации генетических алгоритмов Текст./ А.Ф. Чипига, Ю. Ю. Петров //

76. Инфотелекоммуникационные технологии в науке, производстве и образовании: материалы I Междунар. науч.-техн. конф. -Ставрополь, 2006.

77. Kling, R.M. Placement by Simulated Evolution / R.M. Kling, P. Banerjee// IEEE Trans, on CAD, -1989,- Vol.8, No.3

78. Чернышев, Ю.О. Генетические алгоритмы размещения Текст./ Ю.О. Чернышев, В.В. Курейчик // XXII International School And Conference On Computer Aided Design, CAD-95. Gurzuff, 1995. -329c.

79. Chan, H.M. A genetic algorithm for macro cell placement. Technical report, Department of Electrical Engineering and Computer Science, University of Michigan, 1989

80. Lin, S.C. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997

81. Сигал, И.Х. Последовательность применения алгоритмов приближённого решения в комбинированном алгоритме решения задачи коммивояжера Текст./ И.Х. Сигал // Журнал вычислительной математики и математической физики. 1989. -Т.29, №11.

82. Костюк, Ю.Л. Эффективный алгоритм приближённого решения метрической задачи коммивояжера Текст. / Ю.Л. Костюк, С.А., Жихарев // Дискретный анализ и исследование операций. Серия 2. -2000.-Т. 7, №1

83. Ауэрбах, Ш. Проблемы мутагенеза Текст./ Ш. Ауэрбах; пер. с англ. Э.В. Гнездицкой, М.И. Маршак, Л.Г. Полукаровой; под ред. Шапиро Н.И. М.: Мир, 1978. - 463с.

84. Пушкарёва, Г.В. Генетическое программирование при автоматизированном проектировании управляющих программ для систем ЧПУ Текст./ Г.В. Пушкарёва // Сборник научных трудов НГТУ. 2004. -№1. - 67-72с.

85. Джеральд, Ф. Джойс Направленная молекулярная эволюция Текст./ Ф. Джойс Джеральд // В мире науки. 1993. - №.3 - с.32

86. Полуян, А.Ю. Параллельный бионический поиск для решения задач оптимизации Текст./А.Ю. Полуян// Безопасность жизнедеятельности. Охрана труда и окружающей среды: межвуз. сб. науч. тр. / РГАСХМ. Ростов н/Д, 2009.

87. Luger, G. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Fourth Edition. Addison-Wesley Publishing Company, 2002.

88. Воеводин, B.B. Математические модели и методы в параллельных процессах Текст./В.В. Воеводин. М.: Наука, 1986.

89. Теория поисковой адаптации для решения избранных комбинированных задач оптимизации Текст. : отчет о НИР/ РГАСХМ; рук. Чернышев Ю.О.; исп. Лебедев Б.К., Венцов H.H., Таможникова А.Ю. Ростов н/Д, 2003 - 2004. - № ГР 01.20.0308.394.

90. Теория интеллектуальных процедур поиска оптимальных решений Текст.: отчет о НИР. / РГАСХМ; рук. Чернышев Ю.О.; исп. Курейчик В.М., Лебедев Б.К., Таможникова А.Ю. Ростов н/Д, 2005.- №ГР 012.00.50.55.01.

91. Развитие теории канальной трассировки на основе эволюционного моделирования Текст.: отчет о НИР / РГАСХМ; рук. Чернышев Ю.О.; исп. Лебедев Б.К., Курейчик В.М., Венцов H.H., Таможникова А.Ю. Ростов н/Д, 2006. - № ГР 012.00.60.42.48.