Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типа тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Полуян, Анна Юрьевна

• Полуян, Анна Юрьевна
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Полуян, Анна Юрьевна

Введение

Глава 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) размерностях задачи.

Список литературы диссертационного исследования кандидат технических наук Полуян, Анна Юрьевна, 2010 год

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.