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

Информационные системы и технологии

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

зить персонажей с использованием анимации и специальных эффектов.

В виртуальных мирах существуют также модели, управляемые компьютером. Неигровые персонажи NPC (Non-Player Character) присутствуют в обучающей системе для создания динамической обстановки и видимости наличия учителей и обслуживающего персонала, без которых не обходится ни одна реальная школа.

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

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

I. O. Petrukhin

Samara State Aerospace University named after academician S.P. Korolyev (National Research University), Russia, Samara

DYNAMIC SIMULATION OF CHARACTERS AND CONTROL IN A VIRTUAL TRAINING SYSTEM «3DUCATION»

A model of different game and non-game characters and their control algorithms that are used in virtual learning system «3Ducation» personalization and management of trainees during the training is presented. Besides, the scene of the character selection is developed and integrated into the system that allows selecting an avatar and customizing its settings according to the wishes of a student.

© nerpyxHH H. O., 2012

УДК: 004.72

И. Б. Плесовских

Омский государственный университет имени Ф. М. Достоевского, Россия, Омск

ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПРОЕКТИРОВАНИЯ

ГЛОБАЛЬНЫХ СЕТЕЙ

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

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

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

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

(Решетневскце чтения

довольно большого количества научных работ. Обычно сеть оптимизируется по трем параметрам: стоимость, надежность и качество обслуживания. Если принимать во внимание только стоимость, то топологию сети удобно рассматривать как дерево. В этом случае основной задачей является нахождение минимального остовного дерева. Этот подход используется, например, в работах [1-3].

Если рассматривать надежность в качестве решающего фактора, то удобнее рассматривать топологию сети как граф. В таком случае многое зависит от того, что понимает под надежностью автор. Например, в работах [4 и 5] используется определение надежности, основанное на вероятности потери информации в результате передачи; в [6 и 7] же употребляется определение надежности, основанное на избыточности. Варианты представления конфигурации сети в виде хромосомы также могут различаться. Так в [4; 7] хромосома представляет собой бинарную строку фиксированной длины, а в [5] хромосома -строка переменной длины, состоящая из целых чисел.

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

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

Решаемая задача является многокритериальной. В предлагаемом алгоритме применен один из классических методов решения подобных задач - метод взвешенной функции. В данном генетическом алгоритме функция приспособленности F представляет собой сумму трех функций F1, F2 и F3 с различными весами:

F = klFl+ k2F2+ kзFз,

где kb k2, k3 - весовые коэффициенты; функция F\ вычисляет сумму весов дуг, входящих в минимальное остовное дерево графа; F2 - среднюю суммарную задержку при прохождении информации между двумя любыми вершинами графа; F3 определяет величину, обратную средней надежности передачи информации между двумя любыми узлами сети.

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

Библиографические ссылки

1. Chou H., Premkumar G., Chu C.-H. Genetic Algorithms for Communications Network Design - An Empirical Study of the Factors that Influence Performance // IEEE Transactions on Evolutionary Computation. 2001. 5(3). P. 236-249.

2. Elbaum R., Sidi M. Topological design of local-area networks using genetic algorithms // IEEE/ACM Transactions on Networking. 1996. 4(5). P. 766-778.

3. Palmer C., Kershenbaum A. An Approach to a Problem in Network Design Using Genetic Algorithms // Networks. 1995. 26(3). P. 151-163.

4. Kumar A., Pathak R., Gupta M., Gupta Y. Genetic algorithm based approach for designing computer network topology // Proc. of the 1993 ACM Conference on Computer Science. 1993. P. 358-365.

5. Dengiz B., Altiparmak F., Smith A. Local Search Genetic Algorithm for Optimal Design of Reliable Networks // IEEE Transactions on Evolutionary Computation. 1997. 1(3). P. 179-188.

6. Huang R., Ma J., Hsu D. A genetic algorithm for optimal 3-connected telecommunication network designs // Proc. of the 3-rd International Symposium on Parallel Architectures, Algorithms and Networks. P. 344-350.

7. Pierre S., Legault G. A genetic algorithm for designing distributed computer network topologies // IEEE Transactions on Systems, Man and Cybernetics, Part B. 1998. 28(2). P. 249-258.

I. B. Plesovskikh

Omsk State University named after F. M. Dostoyevsky, Russia, Omsk DESIGNING WAN USING GENETIC ALGORITHM

Genetic algorithm is the type of the heuristic algorithms; it can be used for topology optimization of computer networks. The genetic algorithm of designing WAN with optimal topology is considered. This algorithm takes into account such factors of network performance as reliability, speed of data transmitting and cost. Also results of using this algorithm in relation to small network are described.

© njiecoBCKHX H. E., 2012