Как работает поиск новинок?

16

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

rcpinto
источник

Ответы:

7

Как объяснено в ответе на этот вопрос AI SE , GA являются скорее «удовлетворительными», чем «оптимизаторами» и не стремятся исследовать «отдаленные» области пространства поиска. Скорее, население имеет тенденцию группироваться в регионах, которые являются «довольно хорошими» в соответствии с функцией пригодности.

Напротив, я полагаю, что мышление заключается в том, что новизна обеспечивает своего рода динамическую приспособленность, стремящуюся оттолкнуть население от ранее открытых районов.

NietzscheanAI
источник
6

Поиск новизны выбирает «новое поведение», в зависимости от предметно-зависимого определения новизны. Например, новизна в области решения лабиринтов может быть «исследована разница маршрута». В конце концов, сети, которые проходят все возможные маршруты через лабиринт, будут найдены, и вы сможете выбрать самый быстрый. Это будет работать намного лучше, чем наивная «цель», например, расстояние до цели, что может легко привести к локальной оптиме, которая никогда не решит лабиринт.

От отказа от целей: эволюция через поиск новизны в одиночку (выделено мной):

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

micimize
источник