ОПТИМИЗАЦИЯ  ТОПОЛОГИИ  ЛОКАЛЬНО-ВЫЧИСЛИТЕЛЬНОЙ  СЕТИ,  ИСПОЛЬЗУЯ  ЭВРЕСТИЧЕСКИЕ  МЕТОДЫ

Набиев  Ильназ  Ильгизович

магистрант,  ИТПЭВС,  КНИТУ  им.  А.Н.  Туполева-КАИ,  РФ,  Республика  Татарстан,  г.  Казань

E -mail:  lovemusic_92@mail.ru

Минегалиева  Миляуша  Маулитовна

студент,  кафедра  общей  математики,  КФУ,  РФ,  Республика  Татарстан,  г.  Казань

Гизатуллин  Зиннур  Марселевич

научный  руководитель,  канд,  техн.  наук,  доцент,  ИТПЭВС,  КНИТУ  им.  А.Н.  Туполева-КАИ,  РФ,  Республика  Татарстан,  г.  Казань

На  сегодняшний  день  в  мире  существует  более  130  миллионов  компьютеров  и  более  80  %  из  них  объединены  в  различные  информационно-вычислительные  сети,  начиная  от  малых  локальных  сетей  в  офисах  до  глобальных  сетей  типа  Internet.  Всемирная  тенденция  к  объединению  компьютеров  в  сети  обусловлена  рядом  важных  причин,  таких  как  ускорение  передачи  информационных  сообщений,  возможность  быстрого  обмена  информацией  между  пользователями,  получение  и  передача  сообщений  (факсов,  электронной  почты  и  т.  п.),  не  отходя  от  рабочего  места,  возможность  мгновенного  получения  любой  информации  из  любой  точки  земного  шара,  а  также  обмен  информацией  между  компьютерами  разных  производителей,  работающих  под  управлением  различного  программного  обеспечения  [1,  3].

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

Абоненты  ЛВС  могут  быть  соединены  между  собой  носителем  информации  (например,  кабельной  сетью)  в  виде:  -шины;  -кольца;  -звезды;  -петли;  -дерева;  -гибридное  [2].

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

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

Фитнес  функция  (целевая  функция)  имеет  вид:

    (1)

где:  матрица  чисел,  где  ,  представляющих  собой  вес  ребра  (стоимость  прокладки  кабеля  в  у.  е.)  между  вершинами  x_i,  x_j.

Дополнительные  ограничения:

1.    —  вес  ребра  —  неотрицательное  число;

2.    —  все  вершины  графа  соединены  между  собой;

3.    —  нет  петель;

4.    —  симметричная  матрица.

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

Данный  алгоритм  реализуется  в  программе  DELPHY.7. 

Описание  используемых  процедур.

Создаем  начальную  популяцию  случайно,  при  помощи  функции  Random.  Процедура  Randomize  используется  вместе  с  функцией  Random.  Она  устанавливает  генератор  случайных  чисел  в  его  последовательность  из  232  псевдослучайных  чисел. 

Выбор  родительских  пар  происходит  последовательно,  а  именно  первая  особь  скрещивается  со  второй,  третьей  и  т.  д.  в  основной  конфигурации.  А  в  модифицированной,  выбор  родительских  пар  происходит  методом  аутбридинга.  Первая  особь  записывается  в  переменную  «osob1»,  а  вторая  в  «osob2». 

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

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

Интерфейс  программы  приведен  на  рисунке  1.

Рисунок  1.  Интерфейс  программы

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

Таблица  1. 

Результаты  исследований  эффективности  алгоритма

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

Вероятность  скрещивания  в  обоих  вариантах  обратно  пропорционально  значению  целевой  функции.  Значение  ЦФ  принимает  наименьшее  значение  при  вероятности  скрещивания  =  0,3  в  первом  варианте,  и  =0,9  во  втором.  Минимальное  значение  скорости  сходимости  алгоритма  достигается  при  вероятности  скрещивания,  в  первом  варианте  =  0,1,  во  втором  варианте  =  0,1  и  1.

ЗАКЛЮЧЕНИЕ

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

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

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

1.Исаев  С.В.,  Популярно  о  генетических  алгоритмах  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  «www.algolist.manual.ru» 

2.Курейчик  В.М.,  Лебедев  Б.К.,  Лебедев  О.К.  Поисковая  адаптация:  теория  и  практика.  М:  Физматлит,  2006.  —  С.  272.  —  ISBN  5-9221-0749-6

3.Goldberg  David  E.,  Genetic  algorithms  in  search,  optimization,  and  machine  learning.  Addison-Wesley  Publishing  Company,  2002.