Статья опубликована в рамках: XVIII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 18 марта 2014 г.)
Наука: Информационные технологии
Скачать книгу(-и): Сборник статей конференции
- Условия публикаций
- Все статьи конференции
дипломов
ОПТИМИЗАЦИЯ ТОПОЛОГИИ ЛОКАЛЬНО-ВЫЧИСЛИТЕЛЬНОЙ СЕТИ, ИСПОЛЬЗУЯ ЭВРЕСТИЧЕСКИЕ МЕТОДЫ
Набиев Ильназ Ильгизович
магистрант, ИТПЭВС, КНИТУ им. А.Н. Туполева-КАИ, РФ, Республика Татарстан, г. Казань
E -mail: lovemusic_92@mail.ru
Минегалиева Миляуша Маулитовна
студент, кафедра общей математики, КФУ, РФ, Республика Татарстан, г. Казань
Гизатуллин Зиннур Марселевич
научный руководитель, канд, техн. наук, доцент, ИТПЭВС, КНИТУ им. А.Н. Туполева-КАИ, РФ, Республика Татарстан, г. Казань
На сегодняшний день в мире существует более 130 миллионов компьютеров и более 80 % из них объединены в различные информационно-вычислительные сети, начиная от малых локальных сетей в офисах до глобальных сетей типа Internet. Всемирная тенденция к объединению компьютеров в сети обусловлена рядом важных причин, таких как ускорение передачи информационных сообщений, возможность быстрого обмена информацией между пользователями, получение и передача сообщений (факсов, электронной почты и т. п.), не отходя от рабочего места, возможность мгновенного получения любой информации из любой точки земного шара, а также обмен информацией между компьютерами разных производителей, работающих под управлением различного программного обеспечения [1, 3].
В производственной практике ЛВС играют очень большую роль. Посредством ЛВС в систему объединяются персональные компьютеры, расположенные на многих удаленных рабочих местах, которые совместно используют оборудование, программные средства и информацию. Рабочие места сотрудников перестают быть изолированными и объединяются в единую систему.
Абоненты ЛВС могут быть соединены между собой носителем информации (например, кабельной сетью) в виде: -шины; -кольца; -звезды; -петли; -дерева; -гибридное [2].
Целью данной работы является разработка программы для оптимизации топологии локально-вычислительной сети, используя генетический алгоритм и исследование эффективности алгоритма. Проводится реализация шинной топологии (моноканал). В сетях с шинной топологией для объединения компьютеров используется толстый и тонкий коаксиальный кабель.
Постановка задачи. Начинаем прокладывать кабель из определенной комнаты, посещая по 1 разу остальные комнаты в неизвестном порядке, где имеются компьютеры. Расстояния между комнатами известны. Необходимо обходить комнаты, чтобы путь был наикратчайшим.
Фитнес функция (целевая функция) имеет вид:
(1)
где: матрица чисел, где , представляющих собой вес ребра (стоимость прокладки кабеля в у. е.) между вершинами xi, xj.
Дополнительные ограничения:
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.
дипломов
Оставить комментарий