Please enable JavaScript.
Coggle requires JavaScript to display documents.
Генетические алгоритмы - Coggle Diagram
Генетические алгоритмы
Базовые принципы ГА
А. Имеется некоторая задача, ее решение – новое знание, которое является логическим следствием значений параметров, описывающих данную задачу.
Б. В ГА обрабатываются не сами параметры задачи, а их закодированная форма в виде хромосом.
В. На множестве хромосом определяется целевая функция приспособляемости, оценивающая уровень приспособленности д/каждой хромосомы.
Г. Решение задачи ищется в закодированном виде, обладающих наиболее высокими значениями целевой функции приспособляемости.
Д. При поиске решения используется только целевая функция без ее производных и какой-либо другой дополнительной информации.
Е. Поиск решения происходит не из одной точки (хромосомы), а из некого их множества.
Ё. Порождение нового поколения хромосом осуществляется на основе вероятностных механизмов выбора, а не детерминированности.
Стандартный (классический) ГА
-
-
-
Проверка условия остановки ГА (достижение наивысших значений функции приспособленности, малые изменения функции приспособленности, по времени, по количеству поколений)
-
Генерация нового поколения хромосом на основе оператором скрещивания (кроссинговер, кроссовер) и мутации
-
ГА. Операторы
- Селекция – метод рулетки
Пусть заданы n-хромосом xi, i=1..n
fi(xi) – степень приспособленности хромосомы
- нормированная степень приспособленности
= PS(xi) - Вероятность выбора хромосомы в следующую популяцию
- Оператор скрещивания – одноточечное
xi, i=1..k – множество хромосом
Разбиваем его на пары (случайным образом) Количество пар – k//2 Д/каждой пары хромосом верно 0,5<= PC <=1
- Оператор мутации
Для каждой хромосомы определяется вероятность её мутации 0<= Pm <=0,1
Одноточечная мутация
Определяется локус мутируемого гена, данному гену приписывается значение, отличного от предыдущего
Терминология.
Ген (свойство, знак, детектор) – атомарный элемент генотипа (набор хромосом, характеризует особь)
-
-
Аллель – значение конкретного гена, определяющее свойство организма
Генотип - набор хромосом, характеризует особь
Фенотип – набор внешних свойств, соответствующих данному генотипу. В формализме ГА фенотип – декодированная из хромосом структура, описывающая реальные параметры задачи.
-
-