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

Содержание.

Введение.

1. Обзор и анализ алгоритмов решения задачи Штейнера для этапов трассировки соединений ЭВА.

1.1 Постановка задачи глобальной трассировки СБИС.

1.2 Постановка задачи построения дерева Штейнера для этапа глобальной трассировки СБИС.

1.3 Обзор и анализ алгоритмов построения дерева Штейнера для этапа глобальной трассировки.

Выводы.

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

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

2.2 Разработка модифицированной схемы блока параллельного эволюционного поиска.

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

Выводы.

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

3.1 Описание комбинированного генетического алгоритма СотЬЮА.

3.2 Выбор методики кодирования.

3.3 Разработка алгоритма создания начальной популяции.

3.4 Описание алгоритма ускоренного поиска ортогональных деревьев Штейнера РТВвА.

3.5 Теоретические оценки разработанных алгоритмов.

Выводы.

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

4.1 Краткое описание программной и аппаратной среды.

4.2 Цель экспериментального исследования.

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

4.4 Результаты экспериментальных исследований разработанного алгоритма СотЫва.

4.5 Результаты экспериментальных исследований разработанного алгоритма РТЕЮА.

Выводы.

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

Роль ЭВМ неизмеримо возросла благодаря достижениям последних лет в области микроэлектроники, что позволило решать такие задачи разработки и производства радиоэлектронной аппаратуры, которые по техническим и экономическим соображениям были совершенно нереальны прежде. Так, применение интегральных схем позволило на один—два порядка повысить плотность компоновки в единице объема, увеличить быстродействие радиоэлектронной аппаратуры, поднять надежность ее работы и приблизительно в десять раз уменьшить стоимость радиоэлектронных устройств. Указанные характеристики значительно улучшились с появлением больших интегральных схем (БИС). С точки зрения реализации устройств на интегральных схемах оптимальным является выполнение их на одном типе ячеек с одинаковой конфигурацией соединений между ячейками, т. е. построения этих устройств в виде однородных ЦВС. ЦВС, реализованные на базе БИС, позволяют решить такие важные вопросы создания дискретных устройств, как высокая универсальность, технологичность изготовления, гибкость, надежность, эффективность функционирования.

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

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

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

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным JI.A. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина M.JI. о целесообразном и оптимальном поведении стохастических автоматов, НеймаркЮ.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

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

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

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

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

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

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

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

В этой связи, тема работы, связанная с разработкой нового алгоритма трассировки схем, при проектировании СБИС, использующего методы генетического поиска в комбинации с другими итерационными методами, позволяющего сократить время поиска решений в задачах большой размерности, и в то же время повысить качество получаемых решений за счёт адаптивной архитектуры, является АКТУАЛЬНОЙ.

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

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

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

2. Разработка и анализ методов решения задачи Штейнера для этапа глобальной трассировки.

3. Создание модифицированных генетических операторов и процедур (кроссинговер, мутация, селекция).

4. Построение алгоритма формирования начальной популяции.

5. Создание структуры и принципов кодирования и декодирования хромосомы.

6. Разработка процедуры оценки и качества (целевой функции).

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

МЕТОДЫ ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска.

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

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

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

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

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

2. Алгоритмы и программное обеспечение для решения задачи построения дерева Штейнера для этапа глобальной трассировки СБИС, которые позволяют уменьшить длину соединительных проводников при проектировании СБИС.

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

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

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

Научные результаты, полученные в диссертационной работе Калашникова P.C., использовались в х/д НИР 12305 по теме «Исследование алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений».

АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международной научно-технической конференции «Интеллектуальные САПР(САО-2002)» (г. Геленджик, 2002 г.), на Международной научно-технической конференции «Интеллектуальные CAQP(CAD-2004)» (г. Геленджик, 2004 г.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 8 печатных работ.

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

Диссертационная работа состоит из введения, четырёх глав,

Выводы

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

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

Алгоритм тестировался на бенчмарках каталога 81ет1лЬ. В ряде тестов разработанный алгоритм РТВвА показал результаты сходные с известными оптимальными решениями при значительном сокращении времени работы.

Заключение

В результате выполненных теоретических и практических

4,- исследований по теме диссертационной работы реализованы следующие положения:

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

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

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

4. Разработана программная среда, позволяющая исследовать влияние динамических параметров при эволюционном моделировании. При создании программы использовалась среда разработки Borland С++ Builder™ Enterprise Suite Version 5.0, что позволило обеспечить удобный интерфейс пользователя и визуализацию работы алгоритмов.

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

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

3. А.Г.Трифонов "Постановка задачи оптимизации и численные методы ее решения" http://www.nnspu.rU/MatlabRu/optimiz/bookl/l.asp.htm

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

5. Фогель JL, Оуэне А., Уолш М. Искусственный интеллект иэволюционное моделирование. М.: Мир, 1969. 230 с.

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

7. Holland J.H. Adaptation in natural and artifical systems. Ann Arbor: Univ. of Michigan Press, 1975. 183 p.

8. Редько В.Г. Эволюционная биокибернетика // "Компьютерра". 1999, март, N11. Интернет адрес: http://www.computerra.ru/1999/l 1/27.html

9. Гладков Л.А, Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. Под ред. В.М. Курейчика. М: ФИЗМАТЛИТ, 2004. - 402

10. Ren-Hung Hwang, Wei-Yuan Do, Shyi-Chang Yang. Multicast Routing Based on Genetic Algorithms. Journal of Information Science and Engineering 16,885-901 (2000)

11. Xianwei zhou. Genetic algorithm for stochastic optimal control traffic assignment problem,proceedings of neural networks and brain on international conference in 1998, 305-3

12. Jones J., Harris F. A Genetic Algorithm for the Steiner Minimal Tree Problem. University of Nevada.http://www.cs.unr.edu/~fredh/papers/conf/agaflsmtp/paper/doc 1 .ps.gz

13. M. Hanan, "On Steiner's problem with rectilinear distance," SIAM J. Appl. Math., vol 14, pp. 255-265, 1966.

14. I.I. Mandoiu, V.V. Vazirani, and J.L. Ganley, "A New Heuristic for Rectilinear Steiner Trees", IEEE Transactions on CAD 19 (2000), pp. 11291139

15. Zhou Xianwei, Chen Changjia, Zhu Gang. A Genetic Algorithm for Multicasting Routing Problem. School of Electronic and Information Engineering, Northern Jiaotong University , Beijing, 100044

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

17. Львовский E.H. Статистические методы построения эмпирических формул: Учеб.пособие для втузов. М., Высшая школа, 1988. 239 е.: ил.

18. Митропольский А.К. Техника статистических вычислений. М., Наука., 1971.576 е.: ил.

19. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие. / Под общ. ред. Останина А.Н. Минск.: Вышэйшая школа., 1989. 218 с.: ил.

20. Адлер Ю.П. Введение в планирование эксперимента. М., Металлургия, 1969. 157 е.: ил.

21. Michael J. Alexander and Gabriel Robins, "New Performance-Driven FPGA Routing Algorithms", Proceedings of ACM/SIGDA Design Automation Conference, June1995.

22. J.E. Beasley, " OR-Library: distributing test problems by electronic mail," J . 0-1, Res, Sot., vol. 41, pp 1069-1072,1990.

23. Richard K. Belew and Michael D. Vose, editors, Foundations of Genetic AZgorithms 4, Morgan Kaufman, 1993.

24. Lance Chambers, editor, PracticaZ Handbook of Genetic AZgorithms, Vol. 1, CRC Press, 1995,

25. H.L. Christensen, R.L. Wainwright and D.A. Schoenefeld, "A Hybrid Algorithm for The Point to Multipoint Routing Problem",Proceedings of the 1997 ACM Symposium on Applied Computing, ACM Press, 1997, pp 263268.

26. A.L. Corcoran and R.L. Wainwright, "Using LibGA to Develop Genetic Algorithms for Solving Combinatorial Optimization Problems", Practical Handbook of Genetic Algorithms, Vol. 1, Lance Chambers, ed., CRC Press, 1995, pp 143 172.

27. Louis Anthony Cox, Jr., Lawrence Davis and Yuping Qiu, "Dynamic Anticipatory Routing In Circuit-Switched Telecommunications Networks", Handbook of Genetic AZgorithms, Lawrence Davis, ed., Van Nostrand Reinhold, 1991, pp 124- 143.

28. L. Davis, editor, Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.

29. Henrik Esbensen, "Finding (Near-) Optimal Steiner Trees in Large Graphs", Proceedings of the Sixth International Conference on Genetic Algorithms, Morgan Kaufmann Publishers,Inc., 1995, pp 485 492.

30. D. Goldberg, Genetic Algorithms in Search, Optimization,and Machine Learning, Addison-Wesley, 1989.

31. Melaine Mitchell, An Introduction to Genetic Algorithms,The MIT Press, 1996.

32. L. Darrell Whitley, editor, Foundations of Genetic Algorithms 2, Morgan Kaufman, 1993.

33. A. Gibbons. Algorithmic Graph Theory. Cambridge University Press, New York, NY, 1985.

34. M. Gondran and M. Minoux. Graphs and Algorithms. John Wiley, New York, NY, 1984.

35. T. C. Hu. Optimum communication spanning trees. SIAM Journal on Computing, 3(3):188-195,1974.

36. A. Kershenbaum. Telecommunications Network Design Algorithms. McGraw-Hill, New York, NY, 1992.

37. J. W. Moon. Various proofs of cayley's formula for counting trees. In F. Harary, editor, A Seminar on Graph Theory, pages 70 {78. Holt, Rinehart,and Winston, New York, NY, 1967.

38. C. C. Palmer and A. Kershenbaum. Two algorithms for finding optimal communications spanning trees. Technical Report (report number unassigned), IBM T. J. Watson Research Center,P.O. Box 704, Yorktown Heights, NY, 1993.

39. M. J. Alexander and G. Robins, "New performance-driven FPGA Routing Algorithms", IEEE Transactions on CAD of Integrated Circuits and Systems, Vol. 15, No. 12, pp. 1505-1517, December 1996.

40. A. B. Kahng, and G. Robins, "A New Class of Iterative Steiner Tree Heuristics With Good Performance",IEEE Transactions on Computer-Aided Design, 11 (7), 1992, pp. 893-902.

41. C. S. Helvig, G. Robins, and A. Zelikovsky, "Improved Approximation Bounds for the Group Steiner Problem",In Proc. Conference on Design Automation and Test in Europe, pages 406—413, 1998.

42. John R. Koza, Genetic Programming, MIT Press, 1992

43. David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

44. M. Hanan, "On Steiner's problem with rectilinear distance," SIAM J. Appl. Math., vol 14, pp. 255-265, 1966.

45. S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor, "The rectilinear Steiner arborescence problem",Algorithmica, vol 7. pp. 277-288, 1992.

46. I.I. Mandoiu, V.V. Vazirani, and J.L. Ganley, "A New Heuristic for Rectilinear Steiner Trees", IEEE Transactions on CAD 19 (2000), pp. 11291139

47. J. S. Salowe and D. M. Warme, "An Exact Rectilinear Steiner Tree Algorithm", in Proc. IEEE Intl. Conf. on Computer Design, Cambridge, MA, October 1993, pp. 472-475

48. Frederick Harris, Jr. Parallel Computation of Steiner Minimal Trees. PhD Dissertation, Department of Computer Science, Clemson University, Clemson, South Carolina, 1994.

49. Jennifer Ludwick. A Parallel and Genetic Approach to the Steiner Tree Extraction Problem. Masters Paper, Department of Computer Science, Clemson University, Clemson, South Carolina, 1996.

50. P. Berman and V. Raimayer. Improved Approximations of the Steiner Tree Problem. Journal of Algorithms, vol. 17, no. 3, pp. 381-408, Nov. 1994.

51. K. Kalpakis and A.T. Sherman. Probabilistic Analysis of an Enhanced Partitioning Algorithm for the Steiner Tree Problem in Rd. Networks, vol. 24, no. 3, pp. 147-56, May 1994.

52. S. Chopra. Comparison of Formulations and a Heuristic for Packing Steiner Trees in a Graph. Annual of Operations Research, vol. 50, pp. 143-71, Sept. 1994.

53. D. Bertsekas and R. Gallager, Data Networks.Englewood Cliffs, NJ: Prentice Hall, 1992.

54. K.Bharath-Kumar and J.M. Jaffe, Routing to multiple destinations in computer networks. IEEE Trans. Commun., Vol. COMM-31, No.3.,1983, 343-351.

55. M. R. Garey and D. S. Johnson, Computers and intractability. New York, Freeman, 1979.

56. G. N. Rouskas, Multicast routing with end-to-end delay and delay variation constraints. IEEE Journal on selected areas in communications, No.3.,1997,346-156.

57. H. Esbensen, Computing near-optimal solutions to the steiner problem in a graph using a genetic algorithm. Networks, Vol.26,1995, 173-185.

58. Xianwei zhou, Genetic algorithm for stochastic optimal control traffic assignment problem, proceedings of neural networks and brain on international conference in 1998, 305-309

59. D.B. Fogel. Evolutionary Computation. New York. NY: IEEE Press, 1995.

60. Goldberd David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989, 412 p.

61. J. Koza. Genetic Programming: on the Programming of Computers my Means of Natural Selection, Cambridge, MA: MIT Press, 1992.

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

63. Д.И. Батищев. Генетический алгоритм решения экстремальных задач. Нижний Новгород, Нижегородский государственный университет имени Н.И.Лобачевского, 1995.

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

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

66. V.M. Kureichik, L.A. Zinchenko. Evolutionary adaptation in the modeling of nonlinear electrical circuits. Proceedings NOLTA 2000, Dresden, 17-21 September, 2000, v.l, p. 221-224.

67. Корнеев B.B., Гареев А.Ф. и др. Базы данных. Интеллектуальная обработка информации. М. Нолидж, 2000. 352 с.

68. Г.Е. Колосов. Об одной задаче управления численностью популяции. .//Изв. РАН. Теории и системы управления под № 2, 1995.

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

70. Д.И. Батищев, Т.С. Кулакова, Д.Е. Шапошников. Применение эволюционно-генетических алгоритмов САПР. //Всерос. совещ.семинар "Мат. обеспеч. высок, технол. в техн. обр. и мед.", Воронеж, 35 ноября, 1994.: Тез. докл. 1994, - с.125-126.

71. В.М. Курейчик. Генетические алгоритмы. Состояние. Проблемы. Перспективы. //Изв. РАН. Теории и системы управления под № 1, 1999. с. 144-160.

72. В.М. Курейчик. Учебное пособие «Методы генетического поиска». Часть 1.Таганрог, 1998, ТРТУ.

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

74. F. Herrera, М. Lozano. Adaptive Genetic Algorithms, based on Fuzzy Techniques. Proc. Of IPMU'96, Granada, Spain, 1996, p. 775-780.

75. R. Subbu, A. Anderson, P.P. Bonissone. Fuzzy Logic Controlled Genetic Algorithms versus Tuned Genetic Algorithms. Proc. IEEE Int. Symp. On Intelligent Control, NIST, Maryland, 1998.

76. Ю.А. Абилов, P.A. Алиев, И.М.Насиров. Генетический алгоритм с групповым выбором и направленной мутацией. //Изв. РАН. Теории и системы управления № 5, 1997. с. 96-99.

77. J. Е. Beasley. Or-library: distributing test problems by electronic mail. Journal of OperationalResearch, 41, 1990.

78. J. E. Beasley. A heuristic for euclidean andrectilinear steiner problems. European journalof Operational Research, 58:284-292, 1992.

79. M. Zachariasen D. Warme, P. Winter. Exact algorithms for plane steiner tree problems: a computational study. Technical Report DIKUTR-98/11, University of Copenhagen, 1998.

80. P. Winter F. K. Hwang, D. S. Riochards. The Steiner tree problem. Elsevier Science Publishers В. V., 1992.

81. M. Garey and D. Johnson. Computers and Intractability: a guide to NP-Completeness.Freeman, 1979.

82. D. E. Goldberg. Genetic algorithms in search,optimization and machine learning. Addison Wesley, 1989.

83. W. F. Chow J. Soukup. Set of test problems for the minimum length connectoin networks.

84. L. Kou, G. Markowvksi, and L. Berman. A fast algorithm for steiner tress. Acta Informática, 15, 1982.

85. M. Mitchell. An introduction to Genetic Algorithms. MIT Press, 1996.

86. J. Plesnik. A bound for the steiner tree problem in graphs. Math. Slovaca, 31, 1981.95 .V. J. Rayward-Smith. The computation of nearly minimal steiner tress in graphs. Int. J. Educ. Sci. Techmol., 14, 1983.

87. P. Winter. Steiner problems in networks: a survey. Networks, 17, 1987.

88. A. Z. Zelikovsky. A 11/6- approximation algorithm for the network steiner problem. Algorithmica, 9:463-470,1993.

89. M. H. Ammar, S.Y. Cheung and C.M. Scoglio, Routing Multipoint Connections Using Virtual Paths in an ATM Network. IEEE INFOCOM '93, The Conference on Computer Communications Proceedings Vol.1 (1993) 95-105.

90. A. Balakrishnan, T.L. Magnanti and P. Mirchandani, Modeling and Heuristic Worst- Case Performance Analysis of the Two-Level Network Design Problem. ManagementScience 40 (1994) 847-867.

91. J. E. Beasley, Algorithm for the Steiner Problem in graphs. Networks 14(1984) 147-169

92. J. E. Beasley, An SST-based Algorithm for the Steiner Problem in Graphs. Networks 19(1989) 1-16.

93. J. Chakrapani and J. Skorin-Kapov, Massively Parallel Tabu Search for the Quadratic Assignment Problem. Annals of Operations Research 41 (1993)327-342.

94. R. Clark and M. Ammar, Providing Scalable Web Service Using Multicast Delivery.Proceeding of the Second International Workshop on Services in Distributed and Net-worked Environments, IEEE Comp. Soc. Press (1995) 19-26.

95. S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C.-G. Liu and L.Wei, An Architecture for Wide-Area Multicast. Computer Communication Review 24-4 (1994) 126-135.

96. R. Dionne and M. Florian, Exact and Approximate Algorithms for Optimal Network Design. Networks 9 (1979) 37-59.

97. K. A. Dowsland, Hill-Climbing, Simulated Annealing and the Steiner Problem in Graphs. Engineering Optimization 17 (1991) 91-107.

98. C. W. Duin and A. Volgenant, Reduction Tests for the Steiner Problem in Graphs.Networks 19 (1989) 549-567.

99. H. Esbensen, Computing Near-Optimal Solutions to the Steiner Problem in a Graph Using a Genetic Algorithm. Networks 26 (1995) 173185.

100. M. R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H.Freeman and company editions (1971).

101. M. Gendreau, A. Hertz and G. Laporte, A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science 40 (1994) 1276-1290.

102. J. Kadirire and G. Knight, Comparison of Dynamic Multicast Routing Algorithms for Wide-Area Packet-Switched ATM Networks. IEEE Conference on Computer Commu-nications 1 (1995) 212-219.

103. J.-F. Larochelle, A Tabu Search Heuristic for the Steiner Tree Problem in Graphs. Master Thesis Ecole Polytechnique de Montreal (1995) 105 p.

104. F. Glover, Future Paths for Integer Programming and Links to Articial Intelligence. Computer and Operations Research 13 (1986) 533-549.

105. F. Glover, Tabu Search-Part I. ORSA Journal on Computing 1 (1989) 190-206.

106. F. Glover, Tabu Search-Part II. ORSA Journal on Computing 2 (1990) 4-32.

107. F. Glover, E. Taillard and D. de Werra, A User's Guide to Tabu Search. Annals of Operations Research 41 (1993) 3-28.

108. P. Hansen and B. Jaumard, Algorithms for the Maximum Satisability Problem. RUT-COR Research Report 43-87, Rutgers, New Brunswick NJ (1986).

109. A. Hertz, Finding a Feasible Course Schedule Using Tabu Search. Discrete Applied Mathematics 35 (1992) 255-270.

110. Лебедев Б.К. Адаптация в САПР. Монография. Таганрог: Изд-во ТРТУ, 1999,160 с.

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

112. Naveed Sherwani. Algorithms for VLSI physical design automation. Second Edition. Kluwer Academic Publishers, Boston / Dordrecht / London, 1995, 53 8p.

113. J.M. Ho, G. Vijayan , and С. К . Wong. A new approach to the rectilinear Sterner tree problem. IEEE Transactions on Computer Aided Design, 9(2): 185-193, February 1985.

114. C.Chang, M.Sarrafzadeh and C.K.Wong. A powerful global router: Based on sterner min-max trees. Proceedings of IEEE International Conference on Computer-Aided Design, pages 2-5, November 7-10 1989.

115. Калашников Р.С. Повышение эффективности генетического поиска. Перспективные информационные технологии и интеллектуальные системы. 4(20)2004, с 43-45.

116. Курейчик В.В., Калашников P.C. Построение ортогонального дерева Штейнера модифицированным методом.// Известия ТРТУ, Таганрог, ТРТУ. 2004. № 3, стр.86-89.

117. Калашников P.C. Построение дерева Штейнера модифицированным методом.// Известия ТРТУ, Таганрог, ТРТУ. — 2003 №2, стр 311-312.

118. Калашников P.C. Построение ортогонального дерева Штейнера методом областей. Перспективные информационные технологии и интеллектуальные системы. №22, 2005, стр 36-40.

119. Калашников P.C. Построение дерева Штейнера методом генетического поиска. Перспективные информационные технологии и интеллектуальные системы. №22, 2005, стр 54.

120. SteinLib Testsets, http://elib.zib.de/steinlib/steinlib.php