Решение задачи повышения надежности резервирования
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
µго скрещивания. Наиболее распространенными среди операторов селекции являются операторы пропорциональной и турнирной селекции.
Оператор пропорциональной селекции также известен как рулеточный отбор. Принцип этого отбора состоит в следующем: особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. Запуская рулетку, выбираем особей для дальнейшего скрещивания. Математически, это выглядит так: если событие A = i-ая особь выбрана, f - функция приспособленности, P - вероятность наступления события, то P(A) = .
Смысл оператора турнирной селекции состоит в следующем: из популяции случайным образом выбирается определенное количество особей, среди которых выбирается лучшая, которая затем будет участвовать в скрещивании. Повторяется эта операция столько раз, сколько необходимо для формирования новой популяции.
Очевидно, что в результате использования этих операторов в следующем этапе скрещивания будут участвовать в основном наиболее приспособленные особи.
4.4 Скрещивание (кроссовер)
На этом этапе особи, выбранные на этапе селекции, с заданной вероятностью Pc подвергаются оператору скрещивания. Существует много вариантов реализации скрещивания. Наиболее известные из них: одноточечный кроссовер, двухточечный кроссовер и равномерный кроссовер.
При одноточечном кроссовере случайным образом выбирается точка кроссовера - индекс вектора, которым представлена особь. Обозначим этот индекс через k. Пусть в скрещивании принимают участие две особи-родителя и . Тогда в результате скрещивания будут получены особи-потомки
, .
Схематично это выглядит так:
11011010010110
11011100010101
При двухточечном кроссовере действует тот же принцип, что и при одноточечном кроссовере, только обмен частями векторов идет не от точки k до n, а от k1 до k2, где k1, k2 - точки двухточечного кроссовера:
,
.
Схематично это представляется так:
11011010010110
11101010001110
В равномерном кроссовере каждый бит первого потомка случайным образом наследуется от одного из родителей; второму потомку достается бит другого родителя.
4.5 Мутация
После завершения этапа скрещивания полученные особи с определенной вероятностью подвергаются мутации. Существуют различные варианты мутации: одноточечная мутация, инверсия и транслокация.
При одноточечной мутации каждый бит с определенной вероятностью подвержен изменению. Схематично это можно представить так:
1010010v1010110
При инверсии выбираются два индекса k1 и k2 (k1 < k2), затем биты с индексами k1,…, k2-1 располагаются в обратном порядке, т.е. если была особь , то после мутации она имеет вид . Схематично это выглядит так:
1011210010v v1000-11110
При транслокации происходит перенос части вектора в другой сегмент этого же вектора:
1110011-1001111
4.6 Формирование новой популяции.
Существуют различные подходы к формированию новой популяции: можно в новую популяцию включать только особей-потомков, либо включать двух лучших особей среди родителей и их потомков. Также существует подход, при котором стараются сделать новую популяцию как можно разнообразнее. Еще один подход, который называется принципом элитизма, заключается в том, чтобы в новую популяцию всегда входили несколько лучших особей родителей, что не даст потерять наиболее приспособленных индивидов.
5. Генетический алгоритм решения задачи выбора вариантов резервирования компонентов стендовой информационно-управляющей системы
1-й этап. Представление данных.
Хромосома, представляющая неизвестную матрицу X, задается с помощью строкового кодирования. Суть кодирования заключается в следующем: экземпляр популяции - это строка длиною n (n - размерность задачи), в которой на i-м месте стоит j[1..3], если . Таким образом решение (фенотип) будет записано как троичная строка: x=(1,1,2,3,2,3,2) (генотип).
2-й этап. Генерация начальной популяции.
Первая популяция создаётся случайным образом из L различных троичных строк длиной n. Дополнительно (с целью улучшения генетического материала) в первую популяцию можно ввести строки, представляющие собой приближенные решения задач по обоим критериям в отдельности.
3-й этап. Оценка особей популяции по критерию приспособленности.
1) Для каждого решения в популяции вычисляется вектор целей , по которому далее определяется скалярное значение функции приспособленности.
) Из текущей популяции выбирается множество недоминируемых внутри этой популяции решений, они запоминаются и временно выбрасываются из рассмотрения.
) Далее ищется множество недоминируемых вариантов в усеченном множестве, и исключаются они. Эта процедура проделывается до тех пор, пока все варианты не будут исключены из популяции.
) Теперь все строки ранжируются: принадлежащие последнему исключённому множеству получают ранг 1, предпоследнему ранг 2. Строки, первыми выброшенные из рассмотрения, получают самый высокий ранг. Внутри каждого исключенного множества все варианты решения имеют одинаковый ранг.
) Далее, в отдельности для каждой группы строк одного ранга, происходит назначение оценок приспособленности. Предположим, ранг k имеет m строк. Тогда строка, сумма евклидовых расстояний от которой до остальных строк данного ранга максимальна, получит оценку k+(m-1)/m.
Ст