По поводу отличий поиска от случайного блуждания копирую сюда мнение знакомого мне ещё по Корку бывшего коллеги Кена Брауна, (теперь уже) профессора информатики в UCC. Вот что он ответил мне на мой вопрос:
Под термином 'random walk' имеется в виду достаточно простой процесс без оценивания качества. У нас есть пространство с топологией и введённой на нём метрикой (функция расстояния для любой пары точек) [имеется в виду метрическое пространство, то есть топологическое пространство, на котором введена метрика; практически имеются в виду правила конструирования оператора соседства в точке пространства, а также правила вычисления расстояния между любыми двумя точками пространства —
mns2012]. Мы стартуем из заданной точки и итеративно выбираем следующую точку. Выбор делается с помощью распределения вероятностей, введенного для данной топологии и метрики. Мы передвигаемся в выбранную точку. Процесс повторяется.Для случайного блуждания мы могли бы посчитать вероятность:
- покрытия всего пространства за определенное время;
- достижения заданной фиксированной точки пространства.
Что касается локального поиска, он включает оценку качества на каждой итерации, а также может включать наложение ограничений или преференций при оценке качества локальных модификаций решения задачи.
Касательно аргументации gpuccio. Он утверждает, что эффект отбора на практике проявляется только при условии достаточно ощутимого селективного преимущества: то есть мутации должны закрепиться по популяции или, по крайней мере, распространиться на значительную часть популяции. Дрейф противодействует распространению (закреплению) полезных мутаций по популяции. Поэтому селективное преимущество должно быть значительным, чтобы перебороть влияние дрейфа. Поэтому, видимо, gpuccio и утверждает, что, в значительной степени, эволюция — это случайное блуждание по параметрическому пространству. Отбор на практике слабочувствителен, он зацепится только тогда, когда селективное преимущество способно преодолеть некоторый статистический барьер, то есть противодействие случайного отбора. Просматривать всё пространство нет необходимости, однако блуждание должно просмотреть достаточно состояний для того, чтобы всё это работало не на бумаге, а на практике. Вот об этом, по замечанию gpuccio, и говорит М. Бихи.
