Телефон: +7 (383)-202-16-86

Статья опубликована в рамках: XVIII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 18 марта 2014 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Набиев И.И., Минегалиева М.М. ОПТИМИЗАЦИЯ ТОПОЛОГИИ ЛОКАЛЬНО-ВЫЧИСЛИТЕЛЬНОЙ СЕТИ, ИСПОЛЬЗУЯ ЭВРЕСТИЧЕСКИЕ МЕТОДЫ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. XVIII междунар. студ. науч.-практ. конф. № 3(18). URL: http://sibac.info/archive/technic/3(18).pdf (дата обращения: 15.12.2019)
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

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

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

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

E -maillovemusic_92@mail.ru

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

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

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

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

 

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

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

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

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

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

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

 

    (1)

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

Таблица  1. 

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

№  эксп.

п/п

Вероятность  скрещивания

Показатель  качества  решения,  у.е.

Скорость  сходимости,  итерации

осн.

модиф.

осн.

модиф.

1

0,1

322

332

10

14

2

0,2

335

332

14

14

3

0,3

295

318

14

17

4

0.4

316

313

14

14

5

0.5

316

307

11

15

6

0,6

318

313

13

18

7

0,7

304

309

14

14

8

0,8

304

313

14

15

9

0.9

307

295

12

13

10

1

301

315

12

13

 

Рисунок  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. 

 

Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий