Наследование (генетический алгоритм)

В генетических алгоритмах наследование — это способность смоделированных объектов спариваться , мутировать (аналогично биологической мутации ) и передавать свои гены , решающие проблемы , следующему поколению , чтобы создать развитое решение конкретной проблемы. Выбор объектов, которые будут унаследованы в каждом последующем поколении , определяется функцией приспособленности , которая варьируется в зависимости от решаемой проблемы. ^[1]

Признаки этих объектов передаются через хромосомы способом, аналогичным биологическому воспроизводству . Эти хромосомы обычно представлены серией генов , которые, в свою очередь, обычно представляются с использованием двоичных чисел . Это распространение признаков между поколениями похоже на наследование признаков между поколениями биологических организмов . Этот процесс также можно рассматривать как форму обучения с подкреплением , поскольку эволюция объектов обусловлена передачей черт от успешных объектов, которые можно рассматривать как награду за их успех, тем самым продвигая полезные черты. ^[1]

Процесс

Как только новое поколение готово к созданию, все особи, добившиеся успеха и выбранные для воспроизводства, случайным образом объединяются в пары. Затем черты этих особей передаются посредством комбинации скрещивания и мутации. ^[1] Этот процесс состоит из следующих основных шагов:

Объедините удачные объекты в пары для спаривания.
Определите случайным образом точку пересечения для каждой пары.
Поменяйте местами гены после точки кроссовера в каждой паре.
Определите случайным образом, мутировали ли какие-либо гены в дочерних объектах.

После выполнения этих шагов для каждой используемой пары родительских объектов будут созданы два дочерних объекта. Затем, после определения успешности объектов в новом поколении, этот процесс можно повторить, используя тот новый объект, который оказался наиболее успешным. Обычно это повторяется до тех пор, пока не будет достигнуто желаемое поколение или не будет найден объект, соответствующий минимальному желаемому результату функции пригодности.

Хотя скрещивание и мутация являются общими генетическими операторами, используемыми при наследовании, существуют и другие операторы, такие как перегруппировка и колонизация-вымирание. ^{[ нужна ссылка ]}

Пример

Предположим, что эти две строки битов представляют признаки, передаваемые двумя родительскими объектами:

Объект 1: 1100011010110001
Объект 2: 1001100110011001

Теперь учтите, что точка пересечения случайно расположена после пятого бита:

Объект 1: 11000 | 11010110001
Объект 2: 10011 | 00110011001

Во время пересечения два объекта поменяют местами все биты после точки пересечения, что приведет к:

Объект 1: 11000 | 00110011001
Объект 2: 10011 | 11010110001

Наконец, на объектах моделируется мутация путем случайного переворачивания нуля или более битов. Если предположить, что десятый бит объекта 1 изменен, а второй и седьмой биты изменены для объекта 2, конечные дочерние элементы, созданные в результате этого наследования, будут следующими:

Объект 1: 1100000111011001
Объект 2: 1101110010110001

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с Рассел, Стюарт Дж.; Норвиг, Питер (1995). Искусственный интеллект: современный подход . Энглвуд-Хайтс, Нью-Джерси: Прентис-Холл.

Внешние ссылки

BoxCar 2D Интерактивный пример использования генетического алгоритма для построения двухмерных автомобилей.

[Stuart_Norvig_1995-1] Перейти обратно: ^а ^б ^с Рассел, Стюарт Дж.; Норвиг, Питер (1995). Искусственный интеллект: современный подход . Энглвуд-Хайтс, Нью-Джерси: Прентис-Холл.

[1]