Решение задачи повышения надежности резервирования с помощью эволюционного моделирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
20,.">Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора , числом или неким другим объектом. В классических реализациях генетического алгоритма (ГА) предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения.
.">Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием функции приспособленности, в результате чего с каждым генотипом ассоциируется определённое значение (приспособленность), которое определяет, насколько хорошо фенотип им описываемый решает поставленную задачу.
), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор (селекция) лучших решений в следующее поколение.
Этот набор действий повторяется итеративно, так моделируется эволюционный процесс, продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий останова алгоритма. Таким критерием может быть:
нахождение глобального, либо субоптимального решения;
исчерпание числа поколений, отпущенных на эволюцию;
исчерпание времени, отпущенного на эволюцию.
Таким образом, можно выделить следующие этапы генетического алгоритма:
Создание начальной популяции
начало цикла
Отбор (селекция).
Скрещивание (кроссовер).
Мутация.
Формирование новой популяции.
Если условие останова не выполняется, то начало цикла, иначе
конец цикла
4.2 Создание начальной популяции
Один из вариантов задания начальной популяции - взятие случайных особей. Они могут быть очень плохими в смысле приспосабливаемости, однако в результате алгоритма они будут эволюционировать, тем самым в итоге давая хорошие показатели приспосабливаемости.
Другой вариант - взятие начальной популяции из предположительной области оптимума, что может несколько ускорить работу алгоритма.
Обозначим начальную популяцию через , где -ая особь (i=1,тАж,n), n - количество особей в популяции.
4.3 Отбор (селекция)
На каждой итерации с помощью вероятностного оператора отбора выбираются два решения-родителя для их последующего скрещивания. Наиболее распространенными среди операторов селекции являются операторы пропорциональной и турнирной селекции.
Оператор пропорциональной селекции также известен как рулеточный отбор. Принцип этого отбора состоит в следующем: особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. Запуская рулетку, выбираем особей для дальнейшего скрещивания. Математически, это выглядит так: если событие A = i-ая особь выбрана, f - функция приспособленности, P - вероятность наступления события, то P(A) = .
Смысл оператора турнирной селекции состоит в следующем: из популяции случайным образом выбирается определенное количество особей, среди которых выбирается лучшая, которая затем будет участвовать в скрещивании. Повторяется эта операция столько раз, сколько необходимо для формирования новой популяции.
Очевидно, что в результате использования этих операторов в следующем этапе скрещивания будут участвовать в основном наиболее приспособленные особи.
4.4 Скрещивание (кроссовер)
На этом этапе особи, выбранные на этапе селекции, с заданной вероятностью Pc подвергаются оператору скрещивания. Существует много вариантов реализации скрещивания. Наиболее известные из них: одноточечный кроссовер, двухточечный кроссовер и равномерный кроссовер.
При одноточечном кроссовере случайным образом выбирается точка кроссовера - индекс вектора, которым представлена особь. Обозначим этот индекс через k. Пусть в скрещивании принимают участие две особи-родителя и . Тогда в результате скре