Помощь в написании студенческих работ
Антистрессовый сервис

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

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

В § 2.4 обсуждаются вопросы получения новых решений. В том числе сформулированы основные требования, предъявляемые к оператору формирования начальной популяции и приводятся ее алгоритмические реализации для различного типа представлений. Описываются алгоритмические аналоги классических операторов «кроссовера» и «мутации», в том числе ОХ-порядковый кроссовер и кроссовер, основанный на порядке… Читать ещё >

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

Содержание

  • Глава 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].

Заключение

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

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

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

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

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

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

Показать весь текст

Список литературы

  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. 421 432
  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. К., 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. АКТо внедрении в учебный хфоцесс результатов диссертационной работы Старостина Н. В. на соискание ученой степени кандидата технических наук
Заполнить форму текущей работой

Сессия? Спокойно!