>Что значит "оптимизация полным перебором" и "оптимизация с половинными делениями" ?
это я не смог внятно сформулировать. Суть примерно такая: пусть у нас есть сто каких-то однобитовых признаков, влияющих на выживаемость. пусть есть естественные мутации, по 1 в каждом поколении.
оптимизация полным перебором: 1. меняем 1 бит 2. сравниваем два варианта до и после изменения, более успешный ставляем 3. повторяем начиная с п1
половинным делением: 1. берем 2 организма, у каждого меняем 1 бит 2. режем код каждого пополам, сшиваем половинки 3. проверяем сразу 4 варианта 4. более успешный оставляем
Навскидку, для нахождения оптимума надо в первом случае перебрать около 2^100 поколений а во втором надо порядка 100 поколений
или, то же самое, но опять в другой формулировке: при бесполом размножении у каждого существа один предок который был на 1 мутацию лучше предка предка. итого, чтоб набрать 1024 мутации надо около 1024 поколений
при половом размножении у каждого существа 2 предка, 4 пра-предка, 8 пра-пра-пра предков и 1024 предка в 10, а не в 1024 поколении. итого, для выбора из 1024 вариантов получается не цепочка из 1024 поколений, а дерево из 9-10 уровней.
третья формулировка: это задача оптимизации, или поиска локального экстремума гладкой функции. Искать его можно полным перебором всего диапазона входных значений, а можно более изощренными способами. Кнут, Дейкстра, алгоритмика, оценка сложности алгоритмов, итп.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2012-06-28 03:12 pm (UTC)это я не смог внятно сформулировать. Суть примерно такая:
пусть у нас есть сто каких-то однобитовых признаков, влияющих на выживаемость.
пусть есть естественные мутации, по 1 в каждом поколении.
оптимизация полным перебором:
1. меняем 1 бит
2. сравниваем два варианта до и после изменения, более успешный ставляем
3. повторяем начиная с п1
половинным делением:
1. берем 2 организма, у каждого меняем 1 бит
2. режем код каждого пополам, сшиваем половинки
3. проверяем сразу 4 варианта
4. более успешный оставляем
Навскидку, для нахождения оптимума надо в первом случае перебрать около 2^100 поколений
а во втором надо порядка 100 поколений
или, то же самое, но опять в другой формулировке:
при бесполом размножении у каждого существа один предок который был на 1 мутацию лучше предка предка. итого, чтоб набрать 1024 мутации надо около 1024 поколений
при половом размножении у каждого существа 2 предка, 4 пра-предка, 8 пра-пра-пра предков и 1024 предка в 10, а не в 1024 поколении. итого, для выбора из 1024 вариантов получается не цепочка из 1024 поколений, а дерево из 9-10 уровней.
третья формулировка:
это задача оптимизации, или поиска локального экстремума гладкой функции. Искать его можно полным перебором всего диапазона входных значений, а можно более изощренными способами. Кнут, Дейкстра, алгоритмика, оценка сложности алгоритмов, итп.