Генетические алгоритмы
Основные понятия и определения
Генетические алгоритмы
Механизм генетического наследования. В каждой клетке любого животного содержится вся генетическая информация особи. Эта информация записана в виде набора молекул ДНК, каждая из которых представляет собой цепочку из молекул нуклеотидов четырех типов: А, T, Ц, Ж. Собственно информацию несет порядок следования нуклеотидов в ДНК.
Таким образом, генетический код особи - это длинная строка, где используются четыре символа: А, Т, Ц, Ж. В животной клетке каждая молекула ДНК окружена оболочкой. Такое образование называется хромосомой.
Каждое врожденное качество особи (цвет глаз, наследственные болезни, тип волос и т. д.) кодируются определенной частью хромосомы, которая называется геном этого свойства.
Различие значения гена называется аллелями.
При размножении особи происходит слияние двух родительских клеток, и их ДНК взаимодействуют, образуя ДНК потомка.
Основной способ взаимодействия кроссовер-скрещение. При кроссовере ДНК предков делится на две части, а затем обменивается своими половинами. При наследовании возможны мутации, в результате которых могут измениться некоторые гены в клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны они, скорее всего, сохранятся в данном виде. При этом произойдет скачкообразное повышение приспособляемости вида.
Генетические алгоритмы – это последовательность управляющих действий и операций моделирующие эволюционные процессы на основе аналогов механизмов информационного наследования и естественного отбора.
Генетические алгоритмы на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции.
В Генетических алгоритмах свойства объектов значениями полей, введенными в запись, названной хромосомой.
В генетических алгоритмах оперируют хромосомами, относящимися к множествам объектов- популяции.
имитация генетических принципов - вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новое поколение объектов на основе оценки цел. функциии, что ведет к эволюционному улучшению значению цел. функции F (функция полезности) от поколения к поколению.
Для поиска оптимального решения используются так же методы, которые в отличие от Генетических алгоритмов оперируют не с множеством хромосом, а с единственной хромосомой.
Так метод локального дискретного поиска основан на случайном изменении отдельных пар в значение генов в хромосоме, такие изменения называются мутацией.
После очередной мутации оценочное значение функции F и результат мутации сохраняются с некоторой вероятностью, зависящей от полученного значения F.