Разделы: ТелекоммуникацииРазмещена 21.06.2014. Последняя правка: 20.06.2014.
Просмотров - 8157
Генетический алгоритм как метод оптимизации поиска кратчайших путей в телекоммуникационных сетях
Митрошина Наталья Олеговна
бакалавр
Сибирский Государственный Университет Телекоммуникаций и Информатики
студент
Научный руководитель: Шувалов Вячеслав Петрович, доктор технических наук, профессор, заведующий кафедрой передачи дискретных сообщений и метрологии (ПДС и М), Сибирский государственный университет телекоммуникаций и информатики
Аннотация:
В статье приведено исследование генетического алгоритма как метода оптимизации поиска наикратчайших путей в телекоммуникационных сетях. Разобрана общая логика алгоритма, представлен пошаговый механизм генерации путей.
Abstract:
The article considers the Genetic Algorithm as the routing optimization method of the shortest path search in telecommunications networks. It contains the analysis of general principles of the algorithm and includes the stepwise mechanism of path generation.
Ключевые слова:
генетический алгоритм; оптимизация; маршрутизация; селекция; скрещивание; мутация
Keywords:
genetic algorithm; optimization; routing; selection; crossover; mutation
УДК 004.023
Введение
При организации сетей одной из основных задач является распределение потоков информации по кратчайшим путям. Под такими путями понимаются пути передачи информации, кратчайшие по времени передачи или протяженности, или пути с минимальными помехами, числом задействованных узлов, стоимостью и т.п. Таким образом, оптимизация путей проводится по различным технико-экономическим критериям, и выбранные пути должны обеспечивать при заданных требованиях наиболее эффективное использование линий и узлов связи. Одним из алгоритмов, применяюющихся для оптимизации поиска кратчаййших маршрутов, является генетический алгоритм.
Актуальность
Генетический алгоритм относится к классу эвристических алгоритмов и является достаточно молодым и весьма перспективным направлением в области оптимизации и моделирования. В отечественной литературе этот метод недостаточно освещается, наблюдается недостаток информации и сведений о его функционировании в контексте задач для телекоммуниционных сетей. Для написания данной статьи была проведена работа с современной зарубежной литературой, что позволило представить новые сведения о механизме работы данного алгоритма.
Цели, задачи Основной целью данной статьи стало изучение принципов работы алгоритма, его логики и возможности примения в рамках телекоммуникационных сетей. Задачей явилось поэтапное рассмотрение действия алгоритма.
Материалы и результаты исследования
Генетический алгоритм (ГА) является особым видом стохастического метода поиска, в котором биологическая эволюция лежит в основе методики решения задачи. Область поиска для ГА называется популяцией, элементами которой являются хромосомы. Алгоритм начинается со случайной выборки совокупности допустимых решений из всей популяции. Каждая хромосома при этом уже является сама по себе решением. Качество решения определяется степенью приспособленности каждой хромосомы. ГА использует методику адаптивного эвристического поиска, которая выбирает совокупность наилучших решений среди всей популяции. Операции селекции, скрещивания и мутаций позволяют получить новые особи – потомков. Более приспособленные хромосомы переходят в следующее поколение. Менее сильные особи имеют меньшие шансы на это перемещение. Процесс повторяется до момента получения наиболее приспособленного решения задачи. Выходит, что средняя приспособленность популяции возрастает с каждой итерацией, таким образом, большее число итерации дает лучший результат.
Постановка задачи. Сеть представляется в виде связного графа G = (V, E) с N узлами. За метрику оптимизации принимается стоимость пути между узлами. Результирующая стоимость определяется как сумма стоимостей каждого участка между узлами, т.н. хопа (hop). Цель – отыскать между исходящим узлом Vsrc и узлом назначения Vdest путь с минимальной стоимостью, где узлы Vsrc и Vdest принадлежат множеству вершин V.
Создание маршрутной таблицы.На этом этапе выполняется генерация всех возможных путей от заданного узла ко всем остальным в пределах сети. На начальном этапе в качестве хромосом рассматривается n случайно выбранных путей. Величина n определяет численность популяции. Эти хромосомы и служат первым поколением.
Генерация оптимальных путей.На этом шаге отыскивается оптимальный путь. Пусть стоимость одного участка равна x. Исходящий узел получает m хромосом.
а) Вычисляется приспособленность для каждой хромосомы:
Конечная стоимость пути:
Приспособленность = количество хопов стоимость одного хопа.
Число хопов равно числу промежуточных узлов, через которые пролегает рассматриваемый путь, а конечная стоимость пути есть сумма стоимостей всех участков данного пути.
б) Выбирается две родительских хромосомы (по определенном методу селекции, в данном примере по правилу рулетки).
в) Выполняется скрещивания с вероятностью Рcros.
г) Выполняется мутация с вероятностью Pmut.
д) Потомки заносятся в популяцию. Хромосома с наихудшей приспособленностью исключается.
е) Если условие завершения алгоритма не выполняется, то выполняется переход к новому поколению. Иначе путь резервируется на период времени t, в секундах, и данные по нему передаются в узел назначения.
ж) По истечении периода t, [с] путь обновляется для получения информации о текущем состоянии динамической сети.
Селекция. Особенностью ГА является процедура выбора родителей для следующего поколения. В данной рассмотрении используется правило рулетки, по которому выбор производится на основании величины приспособленности конкретной особи по отношению к величинам приспособленности остальных особей. Подобно разделению колеса рулетки на сектора членам популяции с более высокой приспособленностью будут соответствовать «большие сектора», а значит, они будут чаще выбираться, чем особи с низкой приспособленностью.
Скрещивание.Процедура скрещивания объединяет части родительских хромосом, что приводит к появлению потомков, чей генетический материал на какую-то долю идентичен родительскому. В основном различают два вида скрещивания – одноточечное и многоточечное. В первом случае выбирается только одна точка скрещивания, в которой обе родительские структуры разрываются на два сегмента. Затем соответствующие сегменты различных родителей склеиваются с образованием двух генотипов потомков (рисунок 1). Во втором случае происходит поочередный обмен генетическим материалом.
Рисунок 1 - Реализация одноточечного скрещивания
Часто при использовании ГА для маршрутизации образуются циклы. Для их предотвращения прибегают к усовершенствованным методикам многоточечного скрещивания, например, частично отображаемое скрещивание (Partially Mapped Crossover (PMX)).
Рассмотрим две строки:
Родитель А: 4 8 7 | 3 6 5 | 1 10 9 2
Родитель Б: 3 1 4 | 2 7 9 | 10 8 6 5
Сначала происходит отображение родителя Б на родителя А: 3 и 2, 6 и 7, 5 и 9 меняются местами. Затем родитель А отображается на родителя Б: происходит замена 2 на 3, 7 на 6, 9 на 5.В конечном итоге появляются следующие потомки:
Потомок А: 4 8 6 | 2 7 9 | 1 10 5 3
Потомок Б: 2 1 4 | 3 6 5 | 10 8 7 9
Каждый потомок содержит служебную информацию, частично определяемую его родителями. Полученное потомство должно быть утверждено. Подтверждение выполняется сопоставлением потомства со всеми возможными маршрутами. Если потомство принадлежит всем возможным путям, то вычисляется его приспособленность и выполняется переход к следующей операции. В противном случае потомство отбрасывается.
Мутация.В результате скрещивания может образоваться дегенеративная популяция. С целью предотвращения этого выполняется мутация. Процедура мутации может быть реализована различными операциями. В данном примере выбран метод вставки. При вставке узел вставляется на случайно выбранную позицию в строке. Это делается по причине того, что в процессе скрещивания узел с оптимального пути может быть исключен. При использовании вставки его можно вернуть. По завершении мутации новому поколению необходимо пройти ту же процедуру подтверждения, что и в скрещивании.
Критерий остановки.Этот критерий обеспечивает сходимость алгоритма. Отсутствие изменений в приспособленности популяции и стопор в образовании поколений служит достаточным условием для завершения алгоритма. Задается большое число поколений, что позволяет алгоритму выявить, с какого поколения не будет заметного улучшения в приспособленности хромосом. Вторым критерием остановки служит достижение хромосомой определенного уровня приспособленности. После получения оптимального решения данные начинают передаваться по полученному пути. Ввиду возможных изменений в топологии сети (добавлении или отказе некоторых узлов) оптимальный путь может не быть наикратчайшим, а сеть должна обновляться каждые t секунд с образованием новых путей (в случае необходимости) [1].
Выводы
Очевидно, что генетические алгоритмы, являясь молодым направлением, представляют большой интерес для специалистов по оптимизации. На настоящий момент можно говорить о том, что данные алгоритмы составляют сильную конкуренцию другим алгоритмам оптимизации при решении многих сложных задач. Необходимо отметить их особую практическую значимость.
ГА эффективны в задачах, характеризующихся сложностью математических моделей. Характер данных моделей сильно усложняет использование более привычных методов оптимизации, таких как динамическое или линейное программирование, метод ветвей и границ. Кроме того, с помощью ГА решаются задачи отыскания оптимальных решений, осуществляется прогнозирование, упорядочение.
Заключение
В ходе рассмотрения ГА удалось достигнуть поставленных цели и задач. Рассмотрена логика метода и его механизм в целом. Дана оценка его практическому применению.
Библиографический список:
1 Rakesh Kumar, Mahesh Kumar. Global Journal of Computer Science and Technology / Vol. 10 Issue 11 (Ver. 1.0) October 2010. - pp. 8 – 12.
Рецензии:
7.07.2014, 18:02 Каменев Александр Юрьевич
Рецензия: Одного источника явно мало для научной статьи, тем более - для обзорной. Не хватает математического аппарата, используемого в теории генетических алгоритмов. Мало иллюстративного материала. Статья требует серьезной доработки с последующим повторным рецензированием. К печати на данном этапе не рекомендуется.
Комментарии пользователей:
Оставить комментарий