Применение адаптивных алгоритмов определения экстремальных множеств графов при решении оптимизационных задач автоматизированного проектирования ЭВА

Материалы Международной конференции “Интеллектуальные САПР”

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

Каждая вершина представляется строкой из к выходных нейронов. Выход одного и только одного из нейронов равен единице (все остальные равны нулю). Этот равный единице выход нейрона показывает порядковый номер подмножества, в которое помещается данная вершина.

Таким образом, выходной вектор является бинарным и содержит кп выходов. Входной вектор X также является бинарным и содержит п (п-1) входов (п (п-1) -

). , , -ния о структуре связей между вершинами х( в графе О. Каждой вершине х( соответствует строка из п входов. Если на вход ] строки 1 подается единица, то это значит, что х( связано с х^ ребром.

Итак, на первом этапе конструируется нейронная сеть. Конструкция нейронной сети определяется параметрами п, к и пу для у=1,2,...,к . На втором этапе осуществляется обучение нейронной сети с помощью генетического алгоритма для поиска значений связей между нейронами и функций активации.

Проведенные экспериментальные исследования показали, что около 80% решений оказались оптимальными.

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

УДК 621.3.06

В.А. Литвиненко

ПРИМЕНЕНИЕ АДАПТИВНЫХ АЛГОРИТМОВ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ МНОЖЕСТВ ГРАФОВ ПРИ РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ЭВА

Рассматривается класс алгоритмов с параметрической адаптацией для определения экстремальных множеств графов [1-3] таких, как максимальные внутренне , , .

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

, -тимизационных задач конструкторского проектирования ЭВА - получать решения

Известия ТРТУ

Тематический выпуск

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

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

ЛИТЕРАТУРА

1. Лите иненко В А. Адаптивные алгоритмы определения экстремальных множеств графов / Ивестия ТРТУ. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТРТУ, 2000. 2(16). С.186-189.

2. Калашников В.А.,Литеиненко В.А. К вопросу определения семейств клик графа. 30. Intern. Wiss. Koll. TH llmenau Vortragsreihe.1985. C.41-44.

3. Литеиненко BA. Методы определения семейств клик графа / Методы и программы решения оптимизационных задач на графах и сетях. Часть 2. Теория. Алгоритмы. Новоси-бирск,1982. C.90-92.

УДК 681.3.01

Angelika Martirosyan, Dina Vishnyakova

THE SYSTEM OF ELECTRONIC COMMERCE. INTERNET - SHOP

Nowadays, Internet becomes necessary part of everybody’s life.

Now, there are few people who can argue with fact that computers based on computers technology define level and pace of development of modern civilization.

Majority of companies and firms can’t imagine their work without using World Wide Web.

Earlier, Network was used only for transferring the information or for sending emails. But now decides more difficult problems of portioned access to resources. About three years ago were created shells, which can support functions of network searching and access to portioned resources, to electronic archives. Internet becomes more popular in business world.

What attracts companies and firms in WWW? The answers are simple. Unique database of Internet, possibility to provide the improved interaction between their own subdivisions, speed of connection, are attract clients and companies. Internet is available to enterprises and private citizens.

With the increasing number of organizations and companies of different property categories in Russia, appears such problem as efficient choice of producers and consumers. The decision of this problem is a development of the system of searching of necessary goods for consumers.