Решение задачи повышения надежности резервирования с помощью эволюционного моделирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ивания будут получены особи-потомки
,
.
Схематично это выглядит так:
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. Генетический алгоритм решения задачи выбора вариантов резервирования компонентов стендовой информационно-управляющей системы
-й этап. Представление данных.
Хромосома, представляющая неизвестную матрицу X, задается с помощью строкового кодирования. Суть кодирования заключается в следующем: экземпляр популяции - это строка длиною n (n- размерность задачи), в которой на i-м месте стоит j[1..3], если . Таким образом решение (фенотип) будет записано как троичная строка: x=(1,1,2,3,2,3,2) (генотип).
-й этап. Генерация начальной популяции.
Первая популяция создаётся случайным образом из L различных троичных строк длиной n. Дополнительно (iелью улучшения генетического материала) в первую популяцию можно ввести строки, представляющие собой приближенные решения задач по обоим критериям в отдельности.
3-й этап. Оценка особей популяции по критерию приспособленности.
1) Для каждого решения в популяции вычисляется вектор целей , по которому далее определяется скалярное значение функции приспособленности.
)Из текущей популяции выбирается множество недоминируемых внутри этой популяции решений, они запоминаются и временно выбрасываются из рассмотрения.
)Далее ищется множество недоминируемых вариантов в усеченном множестве, и исключаются они. Эта процедура проделывается до тех пор, пока все варианты не будут исключены из популяции.
)Теперь все строки ранжируются: принадлежащие последнему исключённому множеству получают ранг 1, предпоследнему ранг 2. Строки, первыми выброшенные из рассмотрения, получают самый высокий ранг. Внутри каждого исключенного множества все варианты решения имеют одинаковый ранг.
)Далее, в отдельности для каждой группы строк одного ранга, происходит назначение оценок приспособленности. Предположим, ранг k имеет m строк. Тогда строка, сумма евклидовых расстояний от которой до остальных строк данного ранга максимальна, получит оценку k+(m-1)/m.
Строка со второй по величине суммой расстояний получит оценку k+(m-2)/m. Строка с минимальной суммой расстояний до остальных особей данного ранга будет иметь оценку k.
Такой подход к оцениванию экземпляров популяции настраивает алгоритм не только на поиск недоминируемых решений (любая недоминируемая строка будет иметь оценку выше любой доминируемой), но и на поддержание разнообразия популяции (удаленные точки получают более высокие оценки), что обеспечивает лучшую аппроксимацию парето-оптимального множества.
-й этап. Отбор(селекция).
В качестве процедуры селекции будем использовать стандартные механизмы пропорционального или турнирного отбора, и чем выше у индивида оценка приспособленности, тем вероятнее она попадет в родители следующего поколения.
5-й этап. Скрещивание и мутация.
Для создания новых особей-потомков может использоваться любая стандартная мутация и любой из классических операторов скрещивания (одноточечный, двухточечный, равномерный кроссовер), дополненные процедурой исправления недопустимых решений. Недопустимыми решения могут оказаться только за счет невыполнения ограничения. Это можно подкорректировать, исправив несколько координат в соответствующей строке (например, случайным образом значение 3 исправить на 2 или 1, либо значение 1 исправить на 2) . Такие исправления позволят уменьшить левую часть этого ограничения. Они проводятся до тех пор, пока это ограничение не будет выполнено.
-й этап. Критерий прекращения работы.
В качестве рекорда хранится множество недоминируемых за все время заботы алгоритма вариантов. Как критерий остановки вычислений используется следующая проверка: если за послед