Разработка и исследование гибридных методов решения задач проектирования систем и устройств информатики, моделируемых графовыми моделями тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Старостин, Николай Владимирович

• Старостин, Николай Владимирович
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Старостин, Николай Владимирович

Введение.

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

1.1. Постановка и математическая формулировка задач оптимального проектирования.

1.2. Численные методы решения экстремальных задач на графе.

1.3. Способы хранения и эффективной обработки графовых моделей.

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

1.5. Цели и задачи исследования.

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

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

2.2. Представления решений задач на графах в виде списковых структур и перестановок

2.3. Базовая структура генетического алгоритма.

2.4. Формирование начальной популяции и генерация новых решений на основе генетических операторов "кроссовера" и "мутации".

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

2.6. Гибридный метод и особенности его практической реализации.

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

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

3.2. Операторы построения и контроля допустимости решений.

3.3. Эвристические алгоритмы локального улучшения получаемых текушлх решений

3.4. Вычислительный эксперимент на классе тестовых задач.

Глава 4. Решение задач оптимальной правильной раскраски графа.

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

4.2. Использование понятия "жадности" в операторах оценивания решений.

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

Глава 5. Модификация гибридного алгоритма для решения многокритериальных задач разбиения графа.

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

5.2. Модификация алгоритма для решения бикритериальной задачи разбиения графа.

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

5.4. Вычислительный эксперимент на классе тестовых задач.

Глава 6. Построение оптимальных и оптимально-компромиссных модульных схем с помощью гибридных методов оптимального проектирования.

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

6.2. Распределение непересекающихся цепей схемы регистра сдвига цифрового интегратора по минимальному числу слоев многослойной печатной платы

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

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

Аюуальность темы исследований

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

Еще один прием, который позволил сократить вычислительные затраты и соответственно увеличить размерность исследуемых графов, заключается в ведении элементов рандомизации. Данное направление дало толчок к развитию методов эволюционных вычислений (подкласс методов случайного поиска), что позволило построить универсальные и достаточно мощные алгоритмы для широкого класса графовых задач. У нас в стране разработкой такого типа алгоритмов занимались Л.А. Растригин, Ю.И. Неймарк, Б.П. Коробков, В.М. Курейчик, A.M. Мелихов, Л.С. Бернштейн, А.П. Рыжков, Г.И. Орлова, Я.Г. Дорфман, И.Л. Букатова, Д.Б. Юдин и другие.

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

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

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

Сначала идеи генетики при решении задач оптимизации использовались для адаптации алгоритма оптимизации. Например, в работах Ю.И. Неймарка предлагался подход, связанный с адаптацией коллектива автоматов, оптимизирующих дискретный объект. Начиная с работ Холланда (1975) и Де Янга, генетическими алгоритмами стали называть алгоритмы, моделирующие природную эволюцию в пространстве оптимизируемых параметров, а не в пространстве параметров алгоритма поиска. Однако в нашей стране эти идеи не нашли пока должного внимания, хотя за рубежом проходит множество конференций посвященных эволюционным вычислениям и генетическим алгоритмам, выпускаются монографии и учебники, издаются бюллетени и журналы.

Цель работы

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

Научная новизна

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

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

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

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

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

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

Для повышения эффективности предлагаемого подхода в общую структуру гибридного метода включены такие специальные операторы, как: 1) операторы коррекции недопустимых решений задачи, основанных на балансовых и конструктивных приемах перевода как отдельных, так и групп вершин из подграфов с избыточной размерностью в недостроенные подграфы; 2) структурные операторы воспроизводства новых решений, работающих не в пространстве А:-ичных структур, а непосредственно с допустимыми решениями задачи, и способных конструировать новые допустимые разбиения графа из фрагментов "родительских" решений; 3) операторы прижизненной адаптации, использующие приемы итерационных алгоритмов по обмену вершин из разных подграфов с целью локальной оптимизации структуры допустимых решений задачи; 4) операторы генетического всплеска, осуществляющие контроль за эффективностью поиска и способные оказывать влияние на генетическое разнообразие в текущей популяции посредством вовлечения в поиск новых случайным образом сформированных допустимых решений задачи.

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

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

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

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

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

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

Теоретическая и практическая ценность работы

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

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

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

Апробация результатов

Результаты диссертации докладывались и обсуждались на Всероссийском совещании-семинаре "Математическое обеспечение высоких технологий в технике, медицине и образовании" (Воронеж, 1998г.), на Всероссийской научно-практической конференции "Компьютерная геометрия и графика" (Н.Новгород, 1998г.), на Всероссийской конференции "Интеллектуальные информационные системы " (Воронеж, 1999г.), на XII Международной конференции "Проблемы теоретической кибернетики" (Н.Новгород, 1999г.), на Всероссийской конференции "Интеллектуальные информационные системы" (Воронеж, 2000г.), на конференции "Вычислительная математика и кибернетика 2000" (Н.Новгород, 2000г.), IX и X юбилейной Всероссийской назЛно-практической конференции по графическим информационным технологиям и системам "КОГРАФ 2000" (Н.Новгород, 2000г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Струюура и объем работы

Работа состоит из введения, шести глав, заключения и списка литературы. Общий объем работы составляет 145 страниц. Список литературы составляет 163 наименования. Основные результаты излагаются в главах 2,3,4,5 и 6.

Краткое содержание работы

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

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

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

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

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

В §1.5 определяются основные цели и задачи исследования.

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

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

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

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

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

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

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

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

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

В §3.1 приводится постановка и символьное представление задачи в виде к-ичных строк фиксированной длины.

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

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

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

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

В §4.1 приводится постановка и символьное представление задачи в виде перестановок фиксированной длины.

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

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

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

В §5.1 приводится постановка бикритериальной задачи к-разбиения. Ставится задача построения области компромиссов и парето-границ для бикритериаль-ной модели. Вводится модификация символьной модели алгоритма для векторной функции приспособленности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

По теме диссертации опубликовано 13 работ, 2 работы направлена в печать. Основные результаты диссертации опубликованы в следующих работах: [76, 79, 80,81, 82,83,84, 153,154,155,156,157,158].

Заключение диссертации по теме «Теоретические основы информатики», Старостин, Николай Владимирович

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Старостин, Николай Владимирович, 2001 год

1. Ashcraft С, Liu J.W.H. Applications of Dulmage-Mendelsohn decomposition and network flow to graph bisection improvement. Technical Report CS-96-05, York University, Dept. of Computer Science, York University, North York, Ontario, Canada, August 1996

2. Aspvall В., Gilbert J. R. Graph coloring using eigenvalue decomposition, SIAM J. Alg. Disc. Meth., № 5, 1984, pp. 526-538

3. Baker J.E. Adaptive selection methods for genetic algorithms. In J.J. Grefenstette, editor. Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erl-baum Associates, 1985, pp. 101-111.

4. Barnard S.T., Simon H. D. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Concurreny: Practice and Experience, Vol. 6, 1994, pp. 101-117

5. Barnes E.R., Vannelli A, Walker J.Q. A New Heuristic for Partitioning the Nodes of a Graph. SIAM Joumal of Discrete Mathematics. Vol.1, Ш 3, 1988(aug), pp. 299-305

6. Bokhari S.H., Crockett T.W., Nicol D.M. Parametric binary dissection. Technical Report 93-39, Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, 1993

7. Boppana R. B. Eigenvalues and graph bisection: an average case analysis, in 28th Annual Symp. Found. Сотр. Sci, 1987, pp. 280-285

8. Bui T.N., Heigham C, Jones C, Leighton T. Improving the Performance of the Kemighan-Lin and Simulated Annealing Graph Bisection Algorithms. 26th рАС|. АСМЛЕЕЕ. 1989, pp. 775-778

9. Bui T.N., Moon B.R. Genetic algorithm and graph partitioning. IEEE Transactions on Computers, vol. 45, № 7,1996, pp. 841-855

10. Chan T.F., Ciarlet P., Szeto J.K., Szeto W.K. On the near optimality of the recursive spectral bisection method for graph partitioning. Manuscript, 1993(feb)

11. Chung Y.C., Yeh Y J., Liu J.S. A parallel dynamic load-balancing algorithm for solution-adaptive finite element meshes on 2D tori. Concurrency: Practice and Experience, Vol. 7, Ш 7, 1995, pp. 615-631

12. Ciarlet P., Lamour J., Lamour F. Recursive partitioning methods and greedy partitioning methods: a comparison on finite element graphs. Technical Report CAM 94-9, UCLA, 1994

13. Cohoon J.P., Martin W.N., Richards D.S. A muli-population genetic algorithm for solving the K-partition problem on hyper-cubes. Processing of the Fourth International Conference on Genetic Algorithms. San Mateo, GA: Morgan Kaufmann, 1991, pp.244-248

14. Cvetanovic Z. The Effects of Problem Partitioning, Allocation, and Granularity on the Performance of Multiple-Processor Systems. ШЕЕ Trans.Comp. Vol.C-36, № 4,1987, pp. 421432

15. Darema F., Kirkpatrick S., Norton V.A. Parallel Algorithms for Chip Placement by Simulated Annealing. IBM Joumal of Research and Development, vol.31, № 3, 1987(may), pp. 391-401

16. De Jong K.A. An analysis of the behavior of a class of genetic adaptive systems (Doctoral dissertation. University of Michigan). Dissertation Abstracts International, Vol. 36, № 10, 5140B (University Microfilms No. 76-9381), 1975

17. Devis L. Handbook of Genetic Algorithms, New York, Van Nostrand Reinhold, 1991

18. Dieckmann R., Frommer A., Monien B. Nearest neighbor load balancing on graph, bi G. Bilardi, G. Italiano, A. Piertracaprina, and G. Pucci, editors. Proceedings of the European

19. Symposium on Algorithms (ESA 98), volume 1461 of Lecture Notes in Computer Science, Springer, 1998, pp. 429-440

20. Diekmann R., Luling R., Monien B., Spraner C. Combining helpful sets and parallel simulated annealing for the graph-partitioning problem. Parallel Algorithms and Applications, vol. 8, 1996, pp. 61-84

21. Diekmann R., Monien B., Preis R. Using helpful sets to improve graph bisections. Technical Report TR-RF-94-008, Dept. ofComp. Science, University of Paderbom, 1994

22. Donath W.E., Hoffman A. J. Lower Bounds for the Partitioning of Graphs. {IBM} Journal of Research and Development, vol.17,1973, pp. 420-425

23. Dutt S. New faster Kemighan-Lin-type graph partitioning algorithms. In Proc. IEEE Intl. Conf. Computer-Aided Design, 1993, pp. 370-377

24. Ercal F., Ramanujam J., Sadayappan P. Task Allocation onto a Hypercube by Recursive Mincut Bipartitioning. Proceedings of the 3rd Hypercube Concurrent Computers and Applications Conference. Pasadena, CA. 1988(jan)

25. Faigle, U, and Schrade, R. Simulated Annealing Eine Fallstudie. Angewandte Informatik, № 6,1988(June), pp. 259-263

26. Farhat C. A simple and efficient automatic FEM domain decomposer. Computers and Structures, Vol. 28, № 5,1988, pp. 579-602

27. Farhat C, Lesoinne M. Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics. Internal J. Numer. Meth. Engrg., Vol. 36,№ 5,1993, pp.745-764

28. Fiduccia CM., Mattheyses R.M. A Linear-Time Heuristic for Improving Network Partitions. Proceedings of 19th Design Automation Conference. ACM/IEEE. Las Vegas, 1982Gun),pp. 175-181

29. Garvill F. Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph. SIAM J. Comput., 1972, vol. 1, Xo2,pp. 180-187

30. Geoffrion A M . Lagrangian relaxation and its uses in integer programming. Math. Programming Study 2,1974, pp. 82-114

31. Ghandrasekharam R., Subhramanian S., Chaudhury S. GAs for Node Partitioning Problem. IEEE Processing, Vol. 140, № 5,1993

32. Glover F. Tabu search part I,II. ORSA J. Comput, Vol. 1-2,1989(90), pp. 190-206,4-32

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

34. Hall K. M. An r-dimensional quadratic placement algorithm. Management Science, Vol. 17, 1970, pp. 219-229

35. Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs. In Proc. Super-computing'95,1995

36. Hendrickson B., Leland R. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J.Sci.Comput, Vol. 16, № 2, 1995, pp. 452-469

37. Ho C.T., Johnsson S.L. Embedding Meshes in Boolean Cubes by Graph Decomposition. J.Parallel and DistComput. Vol.8,1990, pp. 325-339

38. Holland J.H. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975

39. Hu T.E. Integer Programming and Network Flows. Addison-Wesley. Reading, 1969

40. Iwainsky, A., Canute, E., Taraszow, O., and Villa, A. Network Decomposition for the Optimization of Coimected Structures. Networks 16 (1986), pp. 205-235

41. Johnson D.E., Aragon C.R., McGoech L.A., Schevon C. Optimization by simulated annealing: an experimental evaluation; Part I, Graph Partitioning. Operations Research. Vol. 3 7, № 6, 1998, pp. 865-892

42. Kadluczka P., Wala K. Tabu search and genetic algorithms for the generalized graph partitioning problem. Control and cybernetics, vol. 24, № 4,1995, pp. 459-476

43. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, Vol. 20, № 1999, pp. 359-392

44. Kaiypis G., Kumar V. Analysis of multilevel graph partitioning. Technical Report 95-037, University of Minnesota, Department of Computer Science, 1995

45. Kemighan B.W., Lin S. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, vol.49, № 2,1970, pp. 291-307

46. Keyes D. E. Domain decomposition: A bridge between nature and parallel computers, in Adaptive, Multilevel and Hierarchical Computational Strategies, Amer. Soc. Mech. Eng., New York, 1992, pp. 293-334

47. Kirkpatrick, S. Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics 34 (1984), pp. 975-986

48. Kordes U.R. Formulation and solution of circuit card design problems through use of a graph methods. Advances in Electionic Circuit packaging. Vol.2, № 7,1962

49. Leland R., Hendrickson B. An empirical study of static load balancing algorithms. In Proc. Scalable High-Performance Comput. Conf., 1994, pp. 682-685

50. Lin S. Heuristic programming as an aid to network design. Networks 5, 1975, pp. 33-43

51. Miller G.L., Teng S.H., Thurston W., Vavasis S.A. Automatic mesh partitioning. In Graph Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and its Applications, Springer Verlag, Vol. 56 of, 1993, pp. 57-84

52. Moore, D. A Round-Robin Parallel Partitioning Algoritimi. Tech. Rep. 88-916, Cornell University, 1988

53. Ou C.W., Ranka S. Parallel remapping algorithms for adaptive problems. Technical Report CRPC-TR94506, Center for Research on Parallel Computation, Rice University, 1994

54. Ozturan C, deCougny H.L., Shephard M.S., Flaherty J.E. Parallel adaptive mesh refinement and redistribution on distributed memory computers. Computer Methods in Applied Mechanics and Engineering, Vol. 119,1994, pp. 123-137

55. Pothen A., Simon H.D. and Liou K.P. Partitioning Sparse Matrices with Eigenvectors of Graphs. Siam J. Matiix Anal. Appl. vol.11, № 3, 1990(jul), pp. 430-452

56. RoUand E., Pirkul H., Glover F. Tabu search for graph partitioning. Ann. Oper. Res., Vol. 63,1996, pp. 209-232

57. Saab Y., Rao V. Stochastic evolution: A fast effective heiuistic for some genetic layout problems. In Proc. 27th АСМЯЕЕЕ Design Automation Conf, 1990, pp. 26-31

58. Sadayappan P., Ercal F., Ramanujam J. Cluster Partitioning Approaches to Mapping Parallel Programs Onto a Hypercube. Department of Computer and Information Science, Ohio State University. 1988

59. Sanchis L.A. Multiple-Way Network Partitioning. IEEE Transactions on Computers. Vol.38, № 1, 1989(jan), pp. 62-81

60. Schaffer J.D. Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of an International Conference on GA and Their Applications, pp. 93-100.

61. Schloegel К., Karypis G., Кшпаг V. Multilevel diffusion schemes for repartitioning of adaptive meshes. Technical Report 97-013, University of Minnesota, Department of Computer Science, 1997

62. Simon H., Teng S.H. How good is recursive bisection. SIAM Journal on Scientific Computing, vol. 18, № 5, September 1997, pp. 1436-1445

63. Spielman D.A., Teng S.H. Spectral partitioning works: Planar graphs and finite element meshes. Technical Report CSD-96-989, U.C. Berkley, February 1996. extended abstract in Proc. 37. IEEE Conf Foundations of Сотр. Sci., 1996.

64. Suaris P., Kedem G. An algorithm for quadrisection and its application to standard cell placement, ШЕЕ Transactions on Circuits and Systems, № 35, 1988, pp. 294-303

65. Thune M. A partitioning strategy for explicit difference methods. Parallel Computing. Vol.15, № 1-3, 1990, pp. 147-154

66. Williams R.D. Performance of dynamic load balancing algorithms for unstructured mesh calculations. Concurrency: Practice and Experience, Vol. 3, № 5,1991, pp. 457-481

67. Абрайтис Л.Б. Алгоритм определения максимально связанных наборов элементов. Автоматика и вычислительная техника, 1970, № 5, с.40-47

68. Абрайтис Л.Б. Шимайтис А.П. Алгоритмы компоновки узлов и исследование их эффективности. Вычислительная техника, вьш.З, Том 2, Каунас, 1971, с.66-76

69. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995,64 с.

70. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984

71. Батищев Д.И., Кириллов СВ., Старостин Н.В. Дихотомическое разбиение мульти-графов. Воронеж. Тезисы докладов. Всероссийское совещание-семинар "высокие технологии в региональной информатике", 1998 г.

72. Батищев Д.И., Коган Д.И. Вьпшслительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский гос.университет, 1994

73. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизащм в САПР. Воронеж: Издательство Воронежского государственного университета, 1997

74. Батищев Д.И., Старостин Н.В, Дроздова Е.П. Экстремальные задачи правильной раскраски графа. Воронеж. Межвузовский сборник научных трудов "Прикладные задачи моделирования и оптимизации", 2000 г. Часть 2, стр. 49-60.

75. Батищев Д.И., Старостин Н.В. А:-разбиение графов. Вестник ННГУ "Математическое моделирование и оптимальное управление", ННовгород, 2000 г., стр. 37-25.

76. Батащев Д.И., Старостин Н.В. Оптимальное к-разбиение графов. Н.Новгород. Тезисы докладов. XII международная конференция "Проблемы теоретической кибернетики", 1999 г., стр.22-23.

77. Батищев Д.И., Старостин Н.В. Применение генетических алгоритмов к решению задачи дихотомического разбиения графа. Воронеж. Межвузовский сборник н. трудов "Оптимизация и моделирование в автоматизированных системах", 1998 г., стр.3 -10.

78. Батищев Д.И., Старостин Н.В. Способы повьппения эффективности генетического поиска оптимального АЛ-разбиения графа. Воронеж. Межвузовский сборник науч. трудов "Прикладные задачи моделирования и оптимизации", 2000 г. Часть 2, стр. 4-17.

79. Бернштейн Л.С., Селянкин В.В. О минимальном разрезании графов со взвешенными ребрами. Электронная техника. Сер.9. АСУ, 1976, вьш.4(20), с.96-106

80. Бершацский А.М. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: СГУ, 1983.

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

82. Бурков В.Н., Гроппен В.О. Решение задачи о минимальном разрезе в бисвязном орграфе алгоритмами типа ветвей и границ. Автоматика и телемех., 1974, Ks 9, с, 104-110

83. Бутыдьский Ю.Г., Брунченко A.B. Алгоритм разрезания двудольного графа для построения цифровых устройств на основе больших интегральных схем. Автоматика и вычислительная техника, 1976, № 4, с.72-76

84. Буш Р., Мостеллер Ф. Стохастические модели обучения. М.: Физматгиз, 1962

85. Визинг В.Г. Сводимость ряда задач теории графов к задаче о минимальной связке. Вычислительная математика и вычислительная техника, 1971, вьш.2, с.52-55

86. Гарусин МИ., Каплинский А.И. О формировании адаптивных алгоритмов оптимизации псевдобулевых функций на основе метода локального улучшения. Автоматика и телемеханика, 1976, № 9, с.96-104

87. Горинштейн Л.Л. О разрезании графов. Известия АН СССР. Техническая кибернетика, 1969, № 1, с. 79-85

88. Гринберг Э.Я., Илзиня И.Г. О раскраске вершин неориентированных графов. Автоматика и вычислительная техника. Рига. 1964, вьш.7, с. 143-153

89. Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи, М.: Мир, 1982.

90. Ершов A.n. Сведения задачи распределения памяти при составлении программ к задаче раскраски вершин графов. Докл. АН СССР, 1962, Т. 142, № 4, с.785-787

91. Загоруйко Н.Г., Скоробогатов В.А., Хворостов П.В. Вопросы анализа и распознавания молекулярных структур на основе общих фрагментов. Алгоритмы анализа структурной информации: Вычислительные системы. Новосибирск: ИМ СО АН СССР, 1984, вып. 103, с.26-50

92. Закраевский А.Д. и др. Приложения теории графов к задачам логического проектирования дискретных устройств. Исследования по прикладной теории графов. Новосибирск: Наука, 1986

93. Ивахненко А.Г. Самообучающиеся системы распознавания и автоматического управления. Киев.: Техника, 1969

94. Калниньш A.A. Раскраска графов за линейное число шагов. 1Сибернетика, 1971, № 4, с. 103-111

95. Кньпп A.A. Об эффективности итеративньгх алгоритмов в задачах разрезания. Автоматизация проектирования средств автоматизации и вычислительной техники. Саратов, 1976, с.21-32

96. Коган А.Я., Файнштейн И.А., Шейман М.В. Исследование и оптимизация систем программного обеспечения. Автоматика и вычисл. техника, 1976, № 2, с.55-63

97. Корбзпг A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

98. Коробков Б.П. Методы разрезания графов на минимально связанные подграфы и их использование в задачах адаптивной обработки информации. В кн.: Адаптация в вычислительных системах. Рига: Зинатне, 1978, вьш.4, с. 107-129

99. Коробков Б.П., Подкорьггов М.П. Рандомизированная оптимизация системы интерфейсных модулей. В кн.: Системы автоматизации научных исследований. Рига: Зи-натне, 1980, вьш.4, с.6-17

100. Коробков Б.П., Растригин Л.А. Методы структурной адаптащш в процессах управления сложным объектом. В кн.: Адаптация в системах обработки информации. Рига: Зинатне, 1977, с.3-21

101. Коробков Б.П., Растригин Л.А. Рандомизированные методы разрезания графов. Часть

102. Изв. АН СССР. Техническая кибернетика, № 3,1982, с. 163-172

103. Коробков Б.П., Растригин Л.А. Рандомизированные методы разрезания графов. Часть

104. Изв. АН СССР. Техническая кибернетика, № 4,1982, с. 120-126

105. Коробков Б.П., Растригин Л.А. Глобальный рандомизировакпный алгоритм разрезания графов. В кн.: Структурная адаптация многомашинных систем обработки информации, Рига; Зинатне, 1978, с.56-62

106. Коробков Б.П., Растригин Л.А. Метод адаптивного разрезания графов и его использование в задаче сегментации. В кн.: Системы автоматизации научных исследований. Рига: Зинатне, 1980, вьш.4, с.52-63

107. Коробков Б.П., Растригин Л.А. Рандомизированные алгоритмы агрегации графов. В сборнике "Адаптация в вычислительных системах". Рига: Зинатне, 1978, вьш.4, с.6-20

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

109. Курейчик В.М., Калашников В. А., Лебедев Б.К. Автоматизация проектирования печатных плат. Изд.ростовского университета, 1984,80 с.

110. Ландау И.Я. Применение ЦВМ для проектирования ЦВМ. М.: Энергия, 1974

111. Липатов Г.П. Теория графов и ее применение. М: Зинатне, 1986,32 с.

112. Ловас Л,, Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998

113. Магрупов Т.М. Графы, сети алгоритмы и из применения. Ташкент: Фан, 1990,120 с.

114. Магрупов Т.М., Арипджанов М.К., Юсупов СЮ. Разбиение цифровых устройств на большие интегральные схемы. Вопросы кибернетики, вьш.ПО, Ташкент; РИСО АН УзССР, 1980, с. 29-37

115. Максименков A.B., Щорс А.Л. Алгоритм сегментации машинных программ. Автоматика и телемеханика, 1976, № 5, с. 52-60

116. Марин Л.Ф., Бойченко Е.В., Сурначев Д.В., Шестопалова О.В. Государственная автоматизированная система "Выборы" по Москве (о решении задачи оптимальной нарезки избирательных округов). Ж.КомпьюЛог, № 4, М., 1997

117. Матюхин И.Я., Олейник Р.И. Алгоритмическое проектирование цифровых устройств. Вопросы радиоэлектроники, Сер. ЭВТ, вьт.8,1965, с.205-225

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

119. Методы и программы решения оптимизационных задач на графах и сетях. Ч. 1-2; Алгоритмы, программы, применения. Тез. докл. ПиШ Всесоюз. совещ., Улан-Удэ, Новосибирск; ВЦ СО АН СССР, 1982-1984

120. Моисеенко Г.В. Оптимальное разбиение систем на подсистемы. Автоматика и телемеханика, 1979, №7, с. 103-107

121. Морозов К.К., Мелихов АН., Бернштейн Л.С. Методы разбиения РЭА на конструктивно законченные части. М.: Советское радио, 1974,304 с.

122. Мухопад Ю.Ф., Федченко А.И., Попков В.К. Метод повьппения однородности постоянных запоминающих устройств. Автоматика и выч. техника, 1975, № 5, с.87-91

123. Неймарк Ю., Григоренко В., Рапоппорт А. Исследования одной модели коллективного поведения. Изв. ВУЗов. Радиофизика, 1970, № 8

124. Неймарк Ю., Григоренко В., Рапоппорт А Об оптимизащш независимыми детерминированными и стохастическими автоматами. В кн.; Прикладная математика и кибернетика. Горький; Изд-во ГГУ, 1967

125. Нечепуренко М.И. Прикладные задачи на графах и сетях. Новосибирск, 1981.

126. Орлова Г.И., Доффман Я.Г. Оптимальное деление графа на несколько подграфов. Известия АН СССР. Техническая кибернетика, 1972, № 1, с. 118-121

127. Остапенко А.Г. Анализ и синтез линейных радиоэлектронных цепей с помощью графов; Аналоговые и цифровые фильтры. М; Радио и связь, 1985,280 с.

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

129. Першин О.Ю. Алгоритм определения минимальной раскраски конечного графа. Изв. АН УзССР, Техническая кибернетика, 1973, № 6, с. 118-119

130. Петренко А.И. и др. Алгоритмы и методы решения задач технического проектирования электронной аппаратуры с помошью ЭВМ. Автоматизация проектирования в электронике; Республ.межведомственный шуч. техн. сборник, вьш.18,1978, с.3-9

131. Петренко А.И. Тетельбаум А.Я. К вопросу о разбиении большой интегральной схемы на подсхемы. Машинные методы проектир. электронных схем, 1975,273 с.

132. Пожов В.К. О решении некоторых задач на сверхбольших графах. Моделирование на вычислительных системах. СМ-3, Новосибирск; ВЦ СО АН СССР, 1982. с. 93-106

133. Попков В.К., Кауль СБ., Нечепуренко М.И. и др. Методы оптимизации структур зоновых сетей связи Новосибирск; ВЦ СО АН СССР, 1983

134. Прим Р.К. Кратчайпше связьшающие сети и некоторые обобщения. Киберн. сб. М.; Мир, 1961, ВЫП.2, с.95-107

135. Растригин Л.А. Адаптация сложных систем. Методы и приложения. Рига; Зинатне, 1981

136. Растригин Л.А. Случайный поиск в эволюционных вычислениях. В сб.; Обозрение Прикладной и промьшшенной математики, 1996, Том 3, № 5, с.688-705

137. Растригин Л.А, Статистические методы поиска. М.; Наука, 1968

138. Растригин Л.А., Рипа К. Автоматная теория слзАчайного поиска, Рига; Зинатне, 1973

139. Растригин Л.А., Самченко А. Использование механизмов эволюции для решения задач оптимизации. В кн.; Динамика систем. Динамика и управление. Горький; Изд-во ГГУ, 1984

140. Рейнгольд Э., Мивергельд Ю., Део М. Комбинаторные алгоритмы. Теория и практика М.; Мир, 1980

141. Роберте Ф.С Дискретные математические модели с приложениями к социальным, биологическим и экономическим задачам. М.; Наука, 1986

142. Рыжков А.П Алгоритм разбиения графа на мниимально связанные подграфы. Известия АН СССР. Техническая кибернетика, 1975, № 6, с. 122-128

143. Сандберг В.Ю. Эвристический алгоритм раскраски графа. Сб. НИИ Мат. Воронеж, ун-та, 1974, вьш.12, с. 58-64

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

145. Селютин ИМ. Разбиение микромодульных схем. Изв. Северо-Кавказ. Научный центр высшей школы. Сер. Технических наук, 1975, № 5, с. 13-18

146. Сешу С, Рид М.Б. Линейные графы и электрические цели. М.: Высш. шк., 1971

147. Скоробогатов В. А. О нахождении общих частей в семействах графов. Прикладные задачи на графах и сетях: Материалы Всесоюз. совещ. Новосибирск: ВЦ СО АН СССР, 1981, с. 117-132

148. Смолич Г.Г., Смолич Л.И. Алгоритмы разбиения множества веришн гиперграфа на максимально связные группы. Изв. АН СССР. Техн.кибернетика, 1981, № 4, с.216

149. Старостин НВ. Влияние локальной адаптации на сходимость генетического алгоритма. Воронеж. Тезисы докладов на Всероссийскую конференцию "Интеллектуальные информационные системы", 1999 г., стр. 17-18.

150. Старостин Н.В. Эволюционно-генетический подход для решения экстремальных задач на графах. ННовгород. ННГУ. Конференция "Вычислительная математика и кибернетика 2000", 2000 г. (ноябрь), стр. 64.

151. Старостин Н.В., Дроздова Е.П. Вьщеление двудольного графа. Воронеж. Тезисы докладов на Всероссийскую конференцию "Интеллектуальные информационные системы", 1999 г., стр. 72.

152. Старостин Н.В., Кириллов СВ. Проблемы визуализации выходных данных эволю-ционно-генетических вычислений для задачи разбиения графа. Воронеж. Труды Всероссийской конференции "Интеллектуальные информационные системы", 2000 г. (май). Часть 2, стр. 19.

153. Фещенко В.П., Матюшков Л.П. Итеращюнный алгоритм разрезания графа на к подграфов. Автоматизация проектирования сложных систем, Минск, 1976, вьш.2, с. 74-77

154. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969

155. Цьшкин ЯЗ. Основы теории обучающихся систем. М.: Наука, 1970

156. Шкурба В.В. Задача трех станков. М.: Наука, 1976

157. Юдин ДБ. Методы количественного анализа сложных систем. I. Изв. АН СССР. Сер тех киберн., № 1,1966, с.3-16

158. Утверждаю» crop по научной работе ННГУ2hyпрофт. Максимов Г. А.2000г.1. АКТо внедрении в учебный хфоцесс результатов диссертационной работы Старостина Н.В. на соискание ученой степени кандидата технических наук