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

на правахлукопнен

I Стасенко Леонид Александрович

Разработка и исследование генетических и эволюционных алгоритмов на графах

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

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

( степени кандидата технических наук

>

Таганрог - 2003

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

университете

доктор технических наук, доцент Курейчик В.В. доктор технических наук, с.н.с. Фоминых И.Б. доктор технических наук, профессор, Еремеев А.П. кандидат технических наук, доцент Тарасов В.Б.

Федеральное государственное унитарное предприятие "Таганрогский научно-исследовательский институт связи" (ФГУП "ТНИИС")

Защита диссертации состоится 30 октября 2003г. в_ час. _ мин. в

конференц-зале на заседании диссертационного совета Д 217.031.01 при государственном учреждении «Российский научно-исследовательский институт информационных технологий и систем автоматизированного проектирования» по адресу 129090, Москва, ул. Щепкина, д. 22.

С диссертацией можно ознакомиться в библиотеке ГУ «РосНИИТиАП» Минпромнауки РФ.

Автореферат разослан _сентября 2003 г.

Научный руководитель: Научный консультант: Официальные оппоненты:

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

Ученый секретарь диссертационного совета, к.т.н.

-г-

Виньков М.М.

Чоо?' А

Общая характеристика работы

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

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

• Разработка и исследование алгоритмов анализа данных на основе генетического поиска.

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

• Построение архитектур генетического поиска и модифицированных генетических операторов, ориентированных на решение оптимизационных графовых задач.

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

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

а) разработаны принципы разбиения графов на части и размещение графов на плоскости на основе поисковых и генетических алгоритмов;

б) определена процедура построения «жадных» стратегий для решения оптимизационных графовых задач;

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

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

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

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

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

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

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

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных работах, проводимых в Таганрогском государственном радиотехническом университете: грант РФФИ № 01-01-00044 «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук № 02-01-01275 «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов»; госбюджетная работа по заказу Минобразования РФ Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».

Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском государственном радиотехническом университете в цикле практических занятий по курсам «Методы оптимизации, дискретная математика и теория алгоритмов»

Апробация работы, основные теоретические и практические результаты работы докладывались и обсуждались на научной международной научно-технической конференции «Интеллектуальные САПР» (г.Дивноморск, 2001, 2002 г.), на международной конференции IEEE «Прикладные интеллектуальные системы» (г.Дивноморск, 2002г.), на научных семинарах Северо-Кавказкого научного центра высшей школы (г. Ростов-на-Дону, Таганрог, 2001, 2002г.), а также на научных семинарах Рос НИИ информационных технологий и автоматизации проектирования Минпромнауки России.

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

Структура и обьем диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 180 стр., а также 84 рис., список литературы из 105 наименований, 2 стр. приложений и актов об использовании.

Содержание работы

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

В первой главе рассмотрены проблемы решения оптимизационных задач (ОЗ) на графах, основные из которых относятся к классу NP - полных проблем. Дана постановка ОЗ на графах. Математическая модель оптимизационной задачи содержит целевую функцию (ЦФ), ограничения и граничные условия. Приведен модифицированный алгоритм общей стратегии решения ОЗ на графах. Время работы такого алгоритма на входе длины п составляет не более 0(nk) для некоторой константы к, не зависящей от длины входа.

Оптимизационная задача разбиения (размещения) графа на части состоит в отыскании такого разбиения (размещения) из множества возможных разбиений (размещений) некоторого графа G, при котором минимизируется некоторая величина К (L(G)), являющаяся целевой функцией разбиения (размещения), и при этом учитываются все поставленные в задаче ограничения.

Задача о построении пути коммивояжера является NP-полной. Пусть задан полный граф G=(X,U), где |Х| =п - множество вершин (города), |U|=m -множество ребер (возможные пути между городами). Требуется найти перестановку ф из элементов множества X, такую, что ЦФ стремится к минимуму.

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

Раскраска графа связана с построением независимых или внутренне устойчивых подмножеств, а также с определением клик графа. Если две любые вершины подмножества X' графа G=(X,U), Х'сХ, не смежные, то оно

называется внутренне устойчивым. Подмножество Ч', с X графа 0=(Х,и) называется максимальным внутренне устойчивым подмножеством или независимым, если добавление к нему любой вершины х,сХ делает его не внутренне устойчивым. Подмножество *Р„ будет независимым, если

\/д:( £ ^Ддг, 14^= 0). (1.1)

Обратной для построения независимого подмножества является задача построения клик графа. Подмножество из максимального числа смежных между собой вершин в графе называется кликой. Временная сложность существующих алгоритмов в лучшем случае О(п), в самом худшем случае 0(п!). В среднем для реальных графов 0(п2) - 0(п3).

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

Во второй главе автор рассмотрел, модифицировал и построил пять основных моделей (видов) эволюции.

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

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

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

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

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

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

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

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

В генетических алгоритмах (ГА) предварительно анализируется множество входных параметров оптимизационной задачи на графах и находится множество альтернативных решений, которое называется популяцией. Каждое решение кодируется как последовательность конечной длины в некотором алфавите. ГА работает до тех пор, пока не будет получено решение заданного качества или будет выполнено заданное количество генераций, или на некоторой генерации возникнет преждевременная сходимость, когда найден локальный оптимум. В отличие от других методов оптимизации ГА, как правило, анализируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями ЦФ.

Предлагается модифицированный ГА, состоящий из трех основных блоков. В первом блоке - препроцессоре производится создание одной или некоторого множества начальных популяций. Второй блок реализует четыре этапа: выбор представления решения; разработка операторов случайных, направленных и комбинированных изменений; определение законов выживания решений; рекомбинация. Третий блок - постпроцессор, управляет генетическим поиском, реализуя основные принципы: целостности; дополнительности; неточности управления неопределенностью; соответствия; разнообразия путей развития; единства и противоположности порядка и хаоса; совместимости и разделительности; иерархичности; «Бритвы Оккама»; гомеостаза.

Генетический алгоритм состоит из: совокупности пространства поиска О; целевой функции; генетических операторов; схемы эволюции популяции хромосом (альтернативных решений). Формально ГА опишем:

ГА=(Р°, N. Р°„ и ЦФ, I, в, ГО, Б, Я, ФР, Р>) (2.1)

где Р°=( Р°1, Р°2,..., Р°ы) - исходная популяция; I - критерий остановки ГА; N -размер популяции; Р^ - хромосома (альтернативное решение задачи); Ь -длина хромосомы; ЦФ - целевая функция; О- число генераций; ГО -генетические операторы; 8 - селекция (отбор); Я - редукция популяции; ФР -функция рекомбинации; Р1 - популяция на ]-ом шаге генерации.

Селекция (оператор репродукции (ОР)) - это процесс, посредством которого хромосомы, имеющие высокое функциональное значение, получают большую возможность для репродукции. Эффективна стратегия селекции, которая создает возможность перехода из одной подобласти альтернативных решений области поиска в другую. При случайном выборе частоты Я образование альтернативных решений не зависят от ЦФ хромосом и определяются численностью популяции Ы: гА

"N(N-1)' (2Л)

где (3-коэффициент селекции, принимающий в зависимости от условий внешней среды значение 1,2,3. Существуют две основных стратегии. В первой предпочтение отдается парам хромосом с близкими и высокими значениями ЦФ. Во второй - хромосомам, со значениями ЦФ сильно отличающимися между собой. Таким образом, оператор репродукции моделирует естественный отбор.

Оператор кроссинговера (ОК) - в основном бинарная операция. Схематически одноточечный ОК показывает преобразование двух хромосом и частичный обмен информации, используя точку разрыва, выбранную случайно. Оператор мутации (ОМ) выбирает элемент (группу элементов) в хромосоме и обменивает его (их) на другой элемент (группу). Модификациями ОМ являются оператор инверсии (ОИ), оператор транслокации (ОТ) и оператор сегрегации (ОС). В работе построены новые различные модели генетических операторов, ориентированные на решение задач на графах. Кроме рассмотренных ГО важным в ГА является технология анализа и преобразования популяции при переходе из одной генерации в другую. Это реализует функция рекомбинации (ФР). Она определяет, как новая генерация хромосом будет построена из родителей и потомков.

Модифицированную базисную струюуру простого генетического алгоритма для решения 03 на графах запишем:

1. Препроцессор

2. Создание начальной популяции решений для ОЗ на графах.

3. Моделирование популяции (определение ЦФ для каждой хромосомы).

4. Выполнение различных ГО и рекомбинация родителей и потомков для создания новой генерации.

5. Редукция, т.е. приведение размера популяции к заданному виду.

6. Постпроцессор.

7. Реализация новой генерации.

8. Конец работы алгоритма.

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

Для решения оптимизационных задач на графах рассмотрен и модифицирован ряд основных простейших методов поиска: последовательный; дихотомии; Фибоначчи; в глубину; в ширину; с возвращением; «горизонта»; «жадных» стратегий.

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

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

Для определения глобального минимума ЦФ в оптимизационных задачах на графах автор предлагает:

• использовать комбинированные методы поиска и генетические алгоритмы;

• учитывать знания о решаемых задачах;

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

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

Для повышения качества решений 03 на графах, автор ввел ряд основных стратегий взаимодействия поисковых методов и ГА: стратегия «поиск - эволюция»; стратегия «эволюция - поиск»; стратегия «поиск -эволюция - поиск»; стратегия «эволюция - поиск - эволюция»; «поиск - поиск - эволюция - эволюция»; «эволюция - поиск - эволюция - поиск». Это позволяет соединять входы блоков поиска с выходами п! способами, что дает возможность расширять просмотр пространства поиска допустимых решений. Такие стратегии решения 03 на графах в отличие от существующих позволяют во многих случаях выходить из локальных оптимумов.

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

Задачей разбиения графа С=(Х,и) является нахождение такой совокупности частей, чтобы число соединительных ребер графа С удовлетворяло заданному критерию оптимальности

Целью оптимизации является К—ипт. В отличие от существующих алгоритмов разбиения графа предлагается генетический алгоритм разбиения графа на части на основе описанных моделей эволюции. Схема алгоритма состоит из двух частей. В первой части в зависимости от внешней среды реализуются различные модели эволюции. Во второй части строится новая (текущая) популяция решений, т.е. определяется заданное подмножество разбиений В|, В2, ..., Вк (к < в). Далее собираются и анализируются неперспективные решения задачи разбиения, реализуются стратегии адаптации, а также порядок использования и применения различных ГО. Здесь осуществляется построение новой популяции решений. Предложенная схема ГП позволяет варьировать размер популяции, менять модели эволюции от генерации к генерации, быстрее находить локально-оптимальные результаты.

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

л л

(3.1)

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

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

Определена асимптотическая трудоемкость алгоритма. Пусть Np -размер популяции, Nn - число полученных потомков, Ng - число генераций генетического алгоритма.

Т « [aNp tp + ßN„ t„ +y(Np + Nn) te ] N0, (3.2)

где tp - трудоемкость построения одной хромосомы в популяции; tn -трудоемкость генерации одного потомка; tc - трудоемкость построения кластеров, а, ß, у - коэффициенты определяющие параметры генетического поиска. Следовательно, временная сложность алгоритма ориентировочно составляет 0(пг) для одной генерации. С увеличением числа генераций при генетическом поиске время решения оптимизационной задачи разбиения повышается, но это повышение незначительное и может быть компенсировано получением множества локально-оптимальных решений.

Основная цель алгоритмов размещения вершин графов в заданной области минимизировать общую суммарную длину ребер графа. Общая длина всех ребер графа определяется по формуле:

L(0)-IJzduc,r (3.3)

Здесь L(G) - общая суммарная длина ребер графа; c,j - количество ребер соединяющих вершины х-, и Xj; dy - расстояние между элементами х„ Xj на заданной плоскости; п - число вершин графа. Рассмотрены модифицированные генетические алгоритмы, позволяющие минимизировать L(G) (L(G) ->min). В качестве ЦФ выбирается выражение (3.3). Выходными данными будут позиции назначения для каждой вершины. В качестве ограничений выбираются следующие условия. Для каждого X; е X назначается только одна позиция q, е Q. Соответственно каждой позиции q, е Q соответствует одна вершина х, е X. Размещение вершин графа на плоскости и

в линейке с оптимизацией выражения 3.3. заключается в использовании стратегий «поиск - эволюция»; «эволюция - поиск» и т.п.

Приведена стратегия «горизонта» для размещения вершин графов в области заданной конфигурации. Это метод поиска квазиоптимальных решений, заключающийся в ограничении глубины просмотра в каждой точке дерева решений. Он позволяет достигать промежуточной цели, а затем оценивает дальнейшие возможности и продолжает или усовершенствует процесс поиска. ВСА и точность получения результата находятся как бы в противоречии, так как увеличение горизонта просмотра приводит к качественным результатам за большее время. Определена ориентировочная трудоемкость алгоритма: T=[Nptp + Np(t ом+ t0H+

toc+ U)o]N0. (3.4)

здесь tp - трудоемкость построения одной хромосомы в популяции; t0M, t0„, t«, tOT, to™ toy, tOB - трудоемкость соответствующих генетических операторов, о -глубина горизонта, Nq - число генераций, Np - размер популяции.

Для распараллеливания процесса генетического поиска построена схема многопопуляционного генетического алгоритма. Здесь имеется тормозная обратная связь, которая служит для остановки ГП. Особенность в том, что связи между блоками нет. Сами блоки в группе образуют полный граф. Такая сеть позволяет генерировать сложные динамические режимы поведения ГА, направленные на исследование нерассмотренных частей области допустимых решений. Сложность описанных алгоритмов размещения является полиномиальной величиной. Для одной генерации временная сложность алгоритма лежит в пределах 0(п2) - 0(п3).

Для определения пути коммивояжера требуется найти перестановку <р из вершин графа множества X, такую что ЦФ :

UO(<p)=R(<p( 1 ),q>(n))+I{R(cp(i),cp(i+l ))}->min. (3.5)

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

генетические операторы; использовать различные обратные связи для изменения параметров генетического поиска. Использование совместных моделей эволюции и внешней среды регламентирует и управляет таким процессом генетического поиска. Временная сложность описанных алгоритмов является полиномиальной величиной и лежит в пределах О(п) -0(п3).

Для задачи раскраски графа предлагается совместить жадные и последовательные эвристики с ГА. Структура гибридного ГА для задачи раскраски графа, содержит блоки моделей совместной эволюции, установления баланса, адаптации к внешней среде, иерархического управления генетическим поиском, построения порядка из хаоса, локального поиска, модифицированных генетических операторов на основе комбинированных методов. Временная сложность алгоритма такого класса лежит в пределах 0(п2) - 0(п3).

Описаны алгоритмы построения семейства независимых подмножеств (НП). Вначале предварительно произведем упорядочивание вершин по возрастанию начиная с наименьшей локальной степени. Основным ГО при построении независимых подмножеств, является оператор кроссинговера и его различные модификации. Описано пять стратегий построения независимых подмножеств. Одна из них состоит в построении независимых строительных блоков на две, три, четыре и так далее вершин с дальнейшим объединением этих строительных блоков. Другая - предусматривает нахождение всех независимых подмножеств, в которые входит первая рассматриваемая вершина с дальнейшим анализом других вершин на предмет создания новых НП. Третья стратегия предусматривает последовательный анализ всех вершин графа в упорядоченном списке до получения семейства НП. Четвертая стратегия использует просмотр нескольких ветвей дерева решений с возвратом на основе заданной глубины горизонта. Пятая стратегия является комбинацией первых четырех. Временная сложность алгоритма построения, семейства независимых подмножеств лежит в пределах 0(п) - 0(п4).

Для определения семейства клик графа предложена схема поиска, основанная на комбинированной стратегии (поиск в глубину, «жадная» и метод горизонта). Здесь производится просмотр дерева решений графа с обходом тупиковых путей и фиксацией клик графа. Временная сложность алгоритма в лучшем случае О(п), в самом худшем случае 0(п!). В среднем для реальных графов 0(п2) - 0(п3).

Задача определения паросочетаний в графах относится к NP-полным проблемам. Пусть G=(X,U) - неорграф. Паросочетанием называется подмножество ребер Mcll, не имеющих общих концов. Причем каждое ребро u.eU смежно одному ребру из М. Максимальное паросочетание (МПС) - это паросочетание М, содержащее максимально возможное число ребер. Для нахождения МПС в двудольном графе используется специальная матрица смежности. Строки матрицы соответствуют вершинам Хь а столбцы вершинам Xj ■ На пересечении строк и столбцов ставится значение 1 или 0 в зависимости от наличия или отсутствия соответствующего ребра. Такая модель требует в 4 раза меньше ячеек памяти для представления матрицы в ЭВМ. Это особенно существенно при анализе графов на сотни тысяч вершин.

Предлагается следующая эвристика. В матрице R ищется диагональ с наибольшим числом элементов. Если таких диагоналей несколько, то выбирается любая. Главная диагональ, полностью заполненная элементами, соответствует МПС. Суммарное число единиц соответствует суммарному числу ребер МПС. Каждая единица главной диагонали определяет ребро МПС. Данная методика может быть применена и для графов, не являющихся двудольными. Для этого необходимо в графе выделить максимально двудольную часть. Для нее определить МПС, а затем на основе агрегации и применения ГО построить МПС для произвольного графа. Отметим, что для построения МПС можно использовать жадную стратегию. Временная сложность алгоритма в лучшем случае O(nm), в самом худшем случае 0(п!). В среднем для реальных графов 0(п2) - 0(п3), где п- число вершин, а т- число ребер графа.

В четвертой главе приведены количественные и качественные оценки разработанных алгоритмов. Описаны экспериментальные исследования приведенных алгоритмов. Произведено сравнение разработанных алгоритмов с существующими. Программная подсистема по исследованию задач на графах и их процедур выполнена в виде комплекса программных средств, состоящих из различных программных модулей. При этом выходными параметрами являются: время работы алгоритмов, стабильность алгоритма, лучшее решение, достигнутое в процессе работы. При построении комплекса программ использовались пакеты Borland С++, Builder, Visual С++. Эксперименты для параллельного и последовательного генетического поиска проводились на ЭВМ типа IBM PC, с процессором Intel Pentium IV, AMD Atlon A(0) 1500 МГц, ОЗУ 512 Мб, жёсткий диск 40 Гб.

Произведены экспериментальные исследования поведения целевой функции в зависимости от размера популяции. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов задач на графах. Это позволило улучшить работу алгоритмов по сравнению с известными методами по качеству от 10% до 25%, в зависимости от вида задач на графах. Для рассмотренных тестовых задач ВСА в лучшем случае « 0(ап2), а в худшем случае - 0(рп4).

Основные результаты работы

Основные результаты работы сформулированы следующим образом.

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

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

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

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

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

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

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

Публикации по теме диссертационной работы

1. Стасенко Л.А. Использование жадных стратегий для решения графовых задач // Перспективные информационные технологии и интеллектуальные системы, №3 (11), 2002, с.88-89.

2. Курейчик В.В., Стасенко Л.А. Применение генетических алгоритмов для решения оптимизационных задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 3 (11), 2002, с. 13-19.

3. Стасенко Л.А. Применение методов одномерного поиска для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 4(12), 2002, с.69-71.

4. Курейчик В.В., Стасенко Л.А. Построение моделей эволюции для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 4 (12), 2002, с.14-21.

5. Стасенко Л.А. Основные принципы генетического поиска для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 1 (13), 2003, с. 15-18.

6. Курейчик В.В., Курейчик В.М., Стасенко Л.А. Построение и анализ эволюционного алгоритма определения паросочетаний графа. //Сборник трудов Международного научно-практического семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М.: Наука. Физматлит, 2003 с. 89-95.

В работах, опубликованных в соавторстве, автору принадлежат следующие результаты: в [2] - стратегии генетического поиска, схема параллельного поиска при решении оптимизационных задач на графах; в [4] - построение синтетической модели эволюции; в [6] - алгоритм определения паросочетаний графа.

»16546

\а<=>3-А

Отпечатано в типографии Таганрогского государственного радиотехнического университета ГСП 17А6 г. Таганрог, 28, ул. Энгельса, 1. Тираж 100 экз.

Содержание.

Введение.

Глава 1. Анализ оптимизационных алгоритмов на графах.

1.1. Постановка оптимизационных задач на графах.

1.2. Исследование алгоритмов разбиения и размещения графов.

1.3. Анализ алгоритмов определения пути коммивояжера.

1.4. Раскраска, построение клик и независимых подмножеств графов.

Выводы

Глава 2. Использование перспективных технологий эволюционного моделирования для решения задач на графах.

2.1. Построение моделей эволюций.

2.2. Разработка концепции генетического, поиска для графовых задач.

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

2.4. Построение новых архитектур генетического поиска.

Выводы

Глава 3. Разработка комбинированных генетических алгоритмов для решения задач на графах.

3.1. Построение генетических алгоритмов разбиения графов.

3.2. Разработка генетических алгоритмов размещения вершин графов.

3.3. Анализ генетического алгоритма определения пути коммивояжера.

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

3.5. Построение и анализ эволюционного алгоритма определения паросочетаний графа.

Выводы

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

4.1. Основные задачи построения программного обеспечения для решения графовых задач.

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

Выводы

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

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

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

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

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

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

Комбинированные алгоритмы при незначительном увеличении времени позволяют получать локально оптимальный результат.

Одним из подходов создания комбинированных методов является использование технологии эволюционного моделирования. Она включает ряд новых концепций и стратегий. Например, «эволюция - поиск»; «поиск — эволюция»; «поиск - поиск - эволюция - эволюция»; «поиск - эволюция -поиск», «эволюция - поиск - эволюция» «эволюция — поиск - эволюция — поиск» и т.п. Они реализуются различными поисковыми и генетическими алгоритмами.

Основой технологии эволюционного моделирования, являются генетические алгоритмы. Генетические алгоритмы - эффективная оптимизационная технология, которую будем применять для решения различных задач на графах. Она основана на моделировании процессов селекции и генетических преобразований в биологии. Причем основой этой технологии является «выживание сильнейших», что выполняется путем исключения «неэффективных» элементов (альтернативных решений задач на графах) и оставления оптимальных или квазиоптимальных решений [18-38].

Большой вклад в разработку и исследование методов решения задач на графах и теорию эволюционного моделирования внесли Д.И.Батищев, Л.С.Берштейн, И.Л.Букатова, В.А.Горбатов, А.А.Зыков, В.В.Емельянов, В.М.Курейчик, А.Н.Мелихов, И.П.Норенков, Л.А.Растригин, К.Берж, Д.Гольдберг, Ж.Грефенстетте, Л.Дэвис, Т.Кормен, Н.Кристофидес, О.Оре, И.Чамберс, Ф. Харари, Д.Холланд, и многие другие.

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

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

ЦЕЛЬЮ ДИССЕРТАЦИОННОЙ РАБОТЫ является разработка эволюционных методов и генетических алгоритмов для решения графовых задач. Достижение указанной цели предполагает решение следующих основных задач:

1. Разработка и исследование алгоритмов анализа данных на основе генетического поиска.

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

3. Построение архитектур генетического поиска и модифицированных генетических операторов, ориентированных на решение оптимизационных графовых задач.

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

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:

1. разработаны принципы разбиения графов на части и размещение графов на плоскости на основе комбинации поисковых и генетических алгоритмов;

2. определена процедура построения «жадных» стратегий для решения оптимизационных задач на графах;

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

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

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

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ результатов диссертационной работы определяется созданием комплекса программ и алгоритмов для решения задач на графах, позволяющих использовать разработанные математические модели, стратегии, методы и эвристики, отвечающие конкретным конструкторским и технологическим задачам. Программы реализованы на языке С++ под WINDOWS. Проведенные экспериментальные исследования, показали преимущество комбинированных поисковых и генетических алгоритмов для решения оптимизационных задач на графах по сравнению с существующими методами. Разработанные методы и алгоритмы решения графовых задач позволяют получать не одно, а набор оптимальных, или квазиоптимальных результатов. Время получения лучших результатов решения графовых задач соответствует полиномиальному времени, которого требуют итерационные алгоритмы.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические - результаты диссертационной работы использованы в госбюджетных работах, проводимых в Таганрогском государственном радиотехническом университете: грант РФФИ № 01-01-00044 «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук № 02-01-01275 «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов»; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».

Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском государственном радиотехническом университете в цикле практических занятий по курсам «Методы оптимизации, дискретная математика и теория алгоритмов».

АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на научной международной научно-технической конференции «Интеллектуальные САПР» (г. Дивноморск, 2001, 2002 гг.), на международной конференции IEEE «Прикладные интеллектуальные системы» (г. Дивноморск, 2002г.), на научных семинарах Северо-Кавказкого научного центра высшей школы (г. Ростов-на-Дону, Таганрог, 2001, 2002 гг.), а также на научных семинарах Рос НИИ информационных технологий и автоматизации проектирования Минпромнауки России.

ПУБЛИКАЦИИ. Результаты диссертации отражены в 6 печатных работах.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Работа содержит 175 стр., а также 84 рис., список литературы из 105 наименований, 2 стр. приложений и актов об использовании.

Основные результаты работы сформулированы следующим образом.

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

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

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

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

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

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

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

Заключение

1. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. М.: МЦМО,2000.

2. Горбатов В.А. Основы дискретной математики. М.: Высшая школа, 1987.

3. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир Д 978.

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

5. Харари Ф. Теория графов. М.: Мир,1977.

6. Зыков А.А. Основы теории графов. М.: Наука, 1987.

7. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

8. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

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

10. Иванов Б.Н. Дискретная математика. М.: Лаборатория базовых знаний, 2001.

11. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1983.

12. Панадимитриу X., Стайниц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1983.

13. Нечепуренко М.И. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб. отд-ние,1990.

14. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

15. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: Изд-во СГУ, 1993.

16. Курейчик В.М. Дискретная математика 4.2. Элементы теории графов. Таганрог: Изд-воТРТУ, 1997.

17. Курейчик В.М. Дискретная математика Ч.З. Оптимизационные задачи на графах. Таганрог: Изд-во ТРТУ, 1998.

18. Дубинин Н.П. Избранные труды, Т.1. Проблемы гена и эволюции. -М.: Наука, 2000.

19. Моисеев Н.Н. Алгоритмы развития. -М.: Наука, 1987.

20. Пригожин И., Стенгерс И. Порядок из хаоса. -М.: Прогресс, 1986.

21. Курейчик В.В. Эволюционные методы решения оптимизационных задач. Монография. -Таганрог: Изд-во ТРТУ, 1999.

22. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.l, Washington,US A, CRC Press, 1995.

23. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.2, Washington,US A, CRC Press, 1995.

24. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.3, Washington,US A, CRC Press, 1999.

25. Holland John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

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

27. Goldberg David Е. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

28. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991.

29. Курейчик В.М. Генетические алгоритмы: Монография. -Таганрог: Изд-во ТРТУ, 1998.

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

31. Букатова И.Л. Эволюционное моделирование и его приложения. М.:Наука, 1994.

32. Rastrigin L.A. Random Search in Evolutionary Computations. Proceedings 1st International conf., Evolutionary Computation and Its Application, EvCA 96, Moscow, 1996, pp.135-143.

33. Koza J.R. Genetic Programming. Cambridge/MA:MIT Press, 1998.

34. Zebulum R.S., Pacheco M.C., Vellasco M. Evolutionary Electronics. Automatic Design of Electronic Circuits and Systems by Genetic Algorithms. CRS PRESS, 2002.

35. Genetic Algorithms in Optimizations, Simulation and Modeling. Ed. J. Stendex, E. Hilelbrand and J. Kingdom. IOS PRESS, 1994.

36. Haupt Randy L., Haupt Sue Ellen. Practical Genetic Algorithms. John Willey Ysons, INC, CANADA, 1998.

37. Курицкий Б.Я. Оптимизация вокруг нас. Л.: Машиностроение, 1989.

38. Карелин В.П., Родзин С.И. УМП по методам математического программирования (поисковой оптимизации). Таганрог: Изд-во ТРТУ, 1999.

39. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Изд-во ВГУ, 1997.

40. Курейчик В.В., Стасенко Л.А. Применение генетических алгоритмов для решения оптимизационных задач на графах. // Перспективныеинформационные технологии и интеллектуальные системы, № 3 (11), 2002, с.13-19.

41. Стасенко JI.A. Применение методов одномерного поиска для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 4(12), 2002, с.69-71

42. Кини P.JL, Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981.

43. Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных Странах. М.: Логос,2000.

44. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. М.: Синтег,1998.

45. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных ИС. Ростов-на-Дону: Изд-во РГУ, 1999.

46. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. М.: Энергоатомиздат, 1987.

47. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.

48. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемких изделий. CALS-технологии. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

49. Морозов К.К. и др. Методы разбиения схем РЭА на конструктивно законченные части. М.: Советское радио, 1978.

50. Kernighan В., Lin S. An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech.J., vol 49, Feb 1970, pp. 291-307.

51. Fiduccia C., Mattheyses R. A linear time heuristics for improving network partitions. Proceedings 19th ACM/IEEE Design automation conference, 1982, pp. 175-181.

52. Sherwani Naveed. Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.1. Стр. 169

53. Saab. Y. A new effective and efficient multi-level partitioning algorithm. Proceedings Design, Automation and Test in Europe Conference 2000, Paris, France, 27-30 March 2000, pp.112-116.

54. Grefenstette J, Gopal G, Rosmaita В., D. van Gucht. Genetic algorithms for the traveling salesman problem. Proc. Intern. Conf. of Genetic Algorithms and their applications. John Grefenstette, ed. New Jersey, 1987. pp. 160-165.

55. Oliver L, Smith D., and Holland J.R. A study of permutation crossover operators on the traveling salesman problem. Proc. of the Second International Conf. on Genetic Algorithms, pp. 224-230.

56. Kureichik V.M., Miagkikh V. Some New Features in Genetic Solution of the TSP. Proceedings of the second International conference, Plymouth UK, 1996.pp.

57. Стасенко Л.А. Использование «жадных» стратегий для решения графовых задач // Перспективные информационные технологии и интеллектуальные системы, №3(11), 2002, с.88-89.

58. Курейчик В.В. Построение и анализ генетических алгоритмов раскраски графа на основе моделей искусственных систем// Труды международного конгресса ICAI-2001, Искусственный интеллект в 21-веке. М.: Физмалит, 2001,с.665-675

59. Курейчик В.В., Стасенко Л.А. Построение моделей эволюций для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 4 (12), 2002, с. 14-21.

60. Редько В.Г. Эволюционная кибернетика. -М.: Наука, 2001.

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

62. Тарасов В. Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002.

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

64. Осыка А.В. Экспериментальное исследование зависимости скорости сходимости генетического алгоритма от его параметров// Известия АН. Теория и системы управления, 1997.№5, с. 100-111.

65. Скурихин А.Н. Генетические алгоритмы// Новости искусственного интеллекта, М., №4,1995,с.6-46.

66. Приходченко Н.Н., Шкурат Т.П. Основы генетики человека. Ростов-на-Дону: Феникс, 1997.

67. Genetic Algorithms and Evolution Strategy in Engineering and Computer Science. Editid by D. Quagliarella and et all. John Wiley & Song, NY, USA, 1998.

68. Курейчик B.B., Смирнова O.B. Генетические операторы в задаче компоновки схем ЭВА. // Перспективные информационные технологии и интеллектуальные системы, № 4 (8), 2001, с.41-46.

69. Алексеев О.В. и др. Автоматизация проектирования радиоэлектронных средств. М.: Высшая школа,2000.

70. Ботвинник М.М. О решении неточных переборных задач. М.: Советское радио, 1979.

71. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988

72. Берштейн Л.С., Боженюк А.В. Введение в теорию нечетких графов. Таганрог. Изд-во ТРТУ, 1999.

73. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа// Известия АН. Теория и системы управления, № 5, 1999, с.79-87.

74. Пайтген Х.О., Рохтер П.Х. Красота фракталов. М.: Мир, 1990

75. Кроновер P.M. Фракталы и хаос в динамических системах. Основы теории. М.: Постмаркет,2000.

76. Лоскутов А.Ю. Синергетика и нелинейная динамика: новые подходы к старым проблемам. Синергетика// Труды семинара. Том 3. М.: Изд-во МГУ, 2000 с.204-224.

77. Дульнев Г.Н. Введение в синергетику. СПб.: Изд-во «Проспект», 1998.

78. Колесников А.А. Основы теории синергетического управления. М.: Фирма «Испо- Сервис»,2000.

79. Курейчик В.М., Курейчик В.В. Об установлении порядка в моделях искусственных систем. // Известия ТРТУ, № 5, Таганрог, 2001, с.43-59.

80. Курейчик В.М., Курейчик В.В. Фрактальный алгоритм разбиения графа // Известия АН. Теория и системы управления, № 4, 2002, с.65-75.

81. Смирнова О.В. Построение генетических операторов, основанных на дихотомическом разбиении // Известия ТРТУ, № 4, Таганрог, 2002, с.134-135.

82. Стасенко Л.А. Основные принципы генетического поиска для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 1 (13), 2003, с.27-31.

83. Potts C.I., Giddens T.D., Yadav S.B. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial selection. IEEE Trans, on Systems, Man and Cybernetics, v.24, No.l, 1994, pp. 73 86.

84. Shahookar K.,Mazumder P. A Genetic Approach to standard Cell Placement Using Meta-Genetic Parameter Optimization. IEEE Trans, on CAD, v.9, No.5, 1990, pp. 500-511.

85. Cohoon J.P., Paris W.D. Genetic Placement, IEEE Trans, on CAD, v.6, No 6, November, 1987. pp. 956 964.

86. Kling R.M., Banerjee P.: Placement by Simulated Evolution. IEEE Trans, on CAD, Vol.8, No.3, 1989. pp. 245-256.

87. Kling R.M. and Banerjee P. Empirical and Theoretical Studies of the Simulated Evolution Method applied to standard Cell Placement. IEEE Trans, on CAD, Vol.10, No. 10, 1991. pp. 1303-1315.1. Стр. 172

88. Курейчик В.М., Курейчик В.В. Генетический алгоритм размещения графа // Известия АН. Теория и системы управления № 5, 2000. с. 67-74.

89. Paris W. GENIF: A new placement Algorithms. Thesis (ms) University of Virginia, USA, 1989.

90. Mayer M. Parallel GA for the DAG Vertex spelling problem. Thesis, Univesity of Missouri, USA, 1993.

91. Комарцова JI.Г., Максимов • А.В. Нейрокомпьютеры. М.: Изд-во МГТУ,2002.

92. Таха, Хэмди А., Введение в исследование операций. М.: Издательский дом «Вильямс»,2001.

93. Литвиненко В.А., Логинов В.А. К вопросу применение метода параметрической адаптации для задачи определения клик графа// Известия ТРТУ, № 3, Таганрог, 1999, с.301-302.

94. Литвиненко В.А. Адаптивные алгоритмы на графах // Известия ТРТУ, № 2, Таганрог, 2000, с. 186-189.

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

96. Курейчик В.В., Курейчик В.М., Стасенко Л.А. Построение и анализ эволюционного алгоритма определения паросочетаний графа. //Интегрированные модели и мягкие вычисления в ИИ. М.: Физматлит, 2003, с.41-47.

97. Wolfe G., Wong J.L. and Potkonjak M.Watermarking Graph Partitioning Solutions. IEEE Transactions on CAD of Integrated Circuits and systems, V. 21, №10, October 2002, pp. 1196 1204

98. Mak W.K. Mic Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. -//-V.21, №4, april 2002, pp. 491 - 496

99. Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices. -//-V.19, №2, February 2002, pp. 267 271

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

101. Sul., Buntine., Newton A.R. and Peters B.B. Learning as Applied to Stochastic Optimization for Standard Cell Placement. -//-V. 20, №4, april 2001, pp. 516-527

102. Tsuya A., Tanaka A. A Fractal representation of city distribution using renormalization coordinates proceedings. 2001 Int. symposium on nonlinear theory and its applications, Miyagi, Japan, 2001, pp.319-322.

103. Cordone R., Ferrandi F., Scinto D. and Calvo Wolfler.An Efficient Heuristic Approach to solve the Unate Covering Problem. -//-V. 20, №12, gecember 2001, pp. 1377-1388.