Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
?ком алгоритме - это строки фиксированной длины. Наиболее распространенным является представление в виде деревьев.
Деревом будем называть направленный граф, в котором каждая последующая вершина связанна с одной и только одной предыдущей. Вершины дерева являются элементами одного из двух множеств:
Множество всех возможных внутренних вершин дерева называется функциональным множеством .
Множество всех возможных внешних вершин дерева называется терминальным множеством .
Элементы функционального множества обычно являются рабочими блоками программы (процедурами, функциями), элементы терминального множества - входными данными (переменными и константами). Пример дерева в методе ГП представлен на рис. 8.
Рис. 8. Пример решения в методе ГП.
Объединение функционального и терминального множеств назовем универсальным множеством .
Для решения поставленной задачи методом генетического программирования множества и должны удовлетворять следующим требованиям:
Замкнутость. Для обеспечения замкнутости любой элемент из множества должен принимать в качестве аргумента любой элемент множества .
Например, множество не является замкнутым, так может привести к делению на нуль.
Достаточность. Для обеспечения достаточности элементы множества должны быть выбраны таким образом, чтобы можно было бы решить поставленную задачу.
Пользователь метода генетического программирования должен знать или предполагать некоторую композицию элементов функционального и терминального множеств, которая должна дать решение поставленной задачи. Следует отметить, что существуют задачи, для которых такие композиции точно известны (например, задачи, использующие булевы переменные).
2.2.2Общая схема метода генетического программирования, применение основных генетических операторов
Общая схема метода генетического программирования представлена ниже:
1.Генерируем начальную популяцию одним из методов выращивания, использую элементы множеств и .
.На шаге вычисляем пригодность решений в популяции .
.Применяем операторы селекции, клонирования, скрещивания и мутации к поколению и формируем новую популяцию .
.Стоп, если допустимое решение найдено, иначе и переходим к шагу 2.
Рассмотрим шаги алгоритма подробней.
Для инициализации популяции используются следующие методы выращивания деревьев (решений в пространстве поиска):
Полный метод (full method).
Задается глубина дерева . В вершины на глубине () случайным образом выбираются элементы из функционального множества . На глубине выбираются элементы из терминального множества . Т.о. получается полное дерево глубины .
Метод выращивания (grow method).
Задается глубина дерева . В вершины на глубине () случайным образом выбираются элементы из функционального множества или из терминального множества (в этом случае рост текущей ветви заканчивается). На глубине выбираются элементы из терминального множества . Т.о. выращивается дерево глубины не больше, чем .
Комбинированный метод (ramped half and half).
Часть популяции выращивается полным методом, другая - методом
роста [51].
Функция пригодности (fitness function) является оценкой приспособленности индивида к окружающей среде. Пригодность является движущей силой в естественном отборе Дарвина. Аналогично, функция пригодности в генетическом программировании является основанием для создания следующих поколений решений. Более приспособленные решения должны иметь большее значение функции пригодности, менее приспособленные - меньшее значение. Обычно функция пригодности принимает положительные значения.
Оператор селекции - оператор, посредством которого индивиды выбираются для порождения потомков. Селекция обеспечивает возрастание среднего значения функции пригодности по популяции. Наиболее приспособленные особи должны выбираться с большей вероятностью для сохранения своих генов в следующем поколении. Схемы селекции, применяемые в методе ГП аналогичны схемам селекции, применяемым в ГА.
Существует две схемы скрещивания в методе генетического программирования: стандартное скрещивание (standard crossover) и одноточечное скрещивание (one-point crossover).
Стандартное скрещивание осуществляется следующим образом. Выбираются родительская пара. У каждого из родителей выбирается точка скрещивания (дуга в графе). Родители обмениваются генами (поддеревьями), находящимися ниже точки скрещивания. Полученная пара является потомками.
Пример стандартного скрещивания (рис. 9):
Рис. 9. Пример стандартного скрещивания в методе генетического программирования.
При одноточечном скрещивании у родительской пары выбирается общая точка скрещивания, далее скрещивание осуществляется по стандартной схеме. Общая точка выбирается в общей области деревьев родителей, получаемой наложением одного дерева на другое начиная с корня.
Пример одноточечного скрещивания (рис. 10). Жирной линией отмечены связи, которые могут быть выбраны в качестве общей точки скрещивания:
Рис. 10. Пример одноточечного скрещивания в методе генетического программирования.
Мутация состоит из выполнения (обычно небольших) изменений в значениях одного или нескольких генов в хромосоме. Мутация применяется с очень низкой вероятностью . Однако существует ряд задач, решаемых с помощью метода ге?/p>