В. Е. Мешков, Прудий А. В



Скачать 44.56 Kb.
Дата26.07.2014
Размер44.56 Kb.
ТипЗадача
УДК 004.896:004.023

В.Е. Мешков, Прудий А.В.

Волгодонский институт сервиса (филиал) ЮРГУЭС, г. Волгодонск


Применение бионических методов на этапе синтеза топологии сети
Задача синтеза устройств с регулярной структурой может быть сведена к экстремальной задаче однокритериального выбора и, как следствие к решению экстремальной задачи переборного типа [2]. Следовательно, представляется возможным свести решение задачи синтеза топологии локальной вычислительной сети (ЛВС) к решению упомянутой экстремальной задачи переборного типа.

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

Алгоритмы трассировки сети на втором этапе проектирования представляют собой модифицированный базовый генетического алгоритм (ГА) [1].

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

В качестве базовых моделей для проектирования используются:


  • спецификация сети (например, модель OSI (Open System Interconnection);

  • базовая структурная единица – модель здания.

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

  1. Матрица связности (смежности) G= gij, где gij=1, если есть ребро, связывающее вершину ai с вершиной aj, и gij=0, если такого ребра нет;

  2. Матрица длин ребер (каналов связи) L=lij, где lij – расстояние от пункта ai до пункта aj;

  3. Матрица пропускных способностей (емкостей ребер) C=cij, где cij – максимальное число бит в секунду, которое может быть пропущено по ребру gij;

  4. Матрица стоимости S= sij , где sij – стоимость ребра между пунктами ai и aj.

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

Модель здания представлена в виде взвешенного, неориентированного, односвязного графа без петель. Основные элементы представления – это узел и ребро. Узел это точка на координатной плоскости, характеризующаяся двумя параметрами – координатами Х и У (вершина графа). Узлы и ребра образуют сложные объекты, такие, как стена (соединение двух узлов); дверь; помещение; коридор; компьютер; коммуникационное оборудование.

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

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

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

С точки зрения программной модели все элементы сети представляются объектами языка С#.

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

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

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

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

Отметим, что при таком механизме внесения мутаций требуется задать несколько большее, чем на обычных ГА число особей (примерно на порядок) и задавать около 3..5% вероятность мутации.

С учетом вышесказанного, при проектировании топологии сети следует применять стратегию проектирования «сверху – вниз».

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

Данный алгоритм является основой, на которой строятся все другие алгоритмы. Он также способен рекуррентно обращаться сам к себе.

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

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



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

  1. Курейчик, В. М. Генетические алгоритмы. Учебное пособие [Текст] / В. М. Курейчик, В. В Курейчик, Л. А. Гладков, под ред. В.М.Курейчика. - Изд 2-е., испр. и доп. М.: ФИЗМАТЛИТ., 2006г, – 320с.

  2. Мешков, В. Е. Решение задачи синтеза схем с регулярной структурой с применением эволюционных методов [Текст] / В. Е. Мешков, А. Н. Береза. // Радиоэлектроника, телекоммуникации, информационные технологии: Межвуз. сб. науч. трудов / Южно-Рос. гос. ун-т экономики и сервиса; Ред. кол.: Н.Н. Прокопенко и др. – Шахты: Изд-во ЮРГУЭС, 2004.-119 с.

  3. Мешков, В. Е. Решение задачи синтеза топологии ЛВС на основе эволюционных методов проектирования [Текст] / В. Е. Мешков, А. Н. Береза. // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS”05) и «Интеллектуальные САПР» (CAD-2005). Научное издание в 4-х томах.- М. ФИЗМАТЛИТ. 2005. Т4.- 256с.- ISBN 5-9221-0621-х.- с.120-126.

  4. Мешков, В. Е. Анализ структурных и схемотехнических решений на основе эвристического алгоритма [Текст] / В. Е. Мешков. // Информационные системы и технологии. Теория и практика: сб. науч. тр.: – Шахты: Изд-во ЮРГУЭС, 2008. – 186с

Похожие:

В. Е. Мешков, Прудий А. В iconМетодические разработки по самостоятельной внеаудиторной работе студентов
Тема: Плевра. Плевральные карманы. Границы легких и плевральных мешков. Средостение
В. Е. Мешков, Прудий А. В iconСборник научных трудов Под редакцией В. С. Чуракова Шахты Издательство юргуэс 2007
Р. Г. Зарипов, П. А. Зныкин, Э. Ф. Караваев, Д. Н. Козырев, А. В. Коротков, Т. П. Лолаев, В. Е. Мешков, Е. В. Мешкова, А. Г. Пархомов,...
В. Е. Мешков, Прудий А. В iconПрограмма на 2008 год маршрут
И. А. Бунин и М. М. Пришвин, художники В. Н. Мешков, Н. П. Ульянов, Н. Н. Жуков, композитор Т. Н. Хренников. Елецкая земля – прародина...
В. Е. Мешков, Прудий А. В iconПрофилактика гнойных послеоперационных осложнений у пациентов, получивших комбинированное лечение рака прямой кишки
Козлов С. В., Воздвиженский М. О., Савинков В. Г., Кутырева Ю. Г., Чамзинская Л. И., Мешков А. В., Гинзбург Л. Б., Фролов С. А.,...
В. Е. Мешков, Прудий А. В iconДля предотвращения образования воздушных мешков, всасывающий трубопровод установить с понижающим уклоном от 2
К бобышкам рубашки охлаждения присоединить трубопроводы для подвода и отвода охлаждающей жидкости
В. Е. Мешков, Прудий А. В iconРав Зеев Мешков №37. 03. 2003
Присутствие Всевышнего раскрылось через опустившийся с небес огонь; на горе Кармель жертва, принесенная пророком Элиягу, загорелась...
В. Е. Мешков, Прудий А. В iconРав Зеев Мешков
Б-ге”. Человек может молиться, обращаясь к Создателю мира, но при этом представлять себе, что Тв-рец обладает телом. И даже если...
В. Е. Мешков, Прудий А. В iconРав Зеев Мешков №35. 03. 2003
И собрал Моше все общество сыновей Израиля и сказал им: Вот слова, которые велел б-г исполнить: шесть дней пусть делается работа,...
В. Е. Мешков, Прудий А. В iconЖерар де Вилье Безумцы из Баальбека
Тот стоял на посту возле оборонительного сооружения из бетона и мешков с песком, воздвигнутого прямо посреди проспекта для защиты...
В. Е. Мешков, Прудий А. В iconРассказывалось о том, как выращивать по «20 мешков картошки с каждой сотки»
Так, народный опытник Пётр Матвеевич Пономарёв, которому и была посвящена работа, на протяжении двадцати с лишним лет получал по...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org