Вопрос или проблема
Предположим, у вас есть популяция из N особей с фитнесом 1, 2, . . . , N (т.е. все особи имеют уникальные значения фитнеса). Предположим, вы многократно применяете отбор в турнире без замены с размером турнира s = 2 к этой популяции, не осуществляя кроссоверов, мутаций и замены.
Другими словами, вы запускаете генетический алгоритм только с отбором. После определенного числа поколений вы получите популяцию, состоящую из N копий одного и того же индивидуума.
Можете ли вы оценить количество поколений, необходимых для достижения этого?
Является ли ответ просто log(n) ?
Сложность одного поколения будет O(N/2). Чтобы сделать всю популяцию одинаковой, вам потребуется N поколений. Мой ответ будет O(N**2).
Вы также можете оценить временную сложность, фактически измеряя время выполнения и усредняя его.
Если вы не проводите кроссовер, мутацию или замену, то вы просто выбираете лучших из своих особей.
Ответ или решение
Вопрос о том, сколько поколений потребуется для достижения популяции, состоящей из N одинаковых особей, при использовании только селекции в генетическом алгоритме, требует внимательного анализа.
Описание проблемы
Ваша популяция состоит из N индивидуумов с уникальными значениями приспособленности от 1 до N. Мы применяем турнирный отбор без замещения с размером турнира s=2, что означает, что мы будем случайным образом выбирать пары индивидуумов и сохранять того, у кого выше приспособленность. Этот процесс повторяется, пока вся популяция не станет однородной, то есть пока все N особей не станут копиями одной и той же особи.
Анализ процесса
-
Турнирный отбор: Каждую итерацию отбора мы выбираем два случайных индивидума. Поскольку у нас N индивидуумов с уникальными значениями приспособленности, для каждого отбора вероятностно выбран будет индивидуум с более высокой приспособленностью, что создаёт предвзятость в сторону более сильных особей.
-
Результаты отбора: При каждом турнире наиболее приспособленный индивидуум выбирается, а менее приспособленный исключается из следующего поколения. Этот процесс будет продолжаться до тех пор, пока не останется только один индивидуум в популяции.
Оценка числа поколений
Каждый раз, когда мы проводим отбор, мы уменьшаем разнообразие нашей популяции, приближая ее к состоянию, где остается только один вид. Чтобы оценить количество поколений, необходимых для полного слияния в одну особь, рассмотрим следующие моменты:
- В начале у нас есть N уникальных индивидуумов.
- После первого поколения с вероятностью высокопригодного индивидума, количество различных индивидуумов сокращается, однако остаётся несколько разных.
- Количество селекций в одном поколении составляет O(N/2), что довольно эффективно.
Оценка конвергенции
Наиболее критическим моментом является то, как быстро мы можем сократить количество уникальных индивидуумов:
- Для каждого турнира выбор осуществляется случайным образом, что создает вероятность выбора наилучшего индивидума по сравнению с остальными.
- Таким образом, в каждом поколении мы будем между собой сравнивать индивидуумы, но не можем гарантировать, что уникальность популяции будет сокращаться линейно.
По итогу, чтобы завершить процесс, и получить в итоге N идентичных индивидуумов, число поколений может быть оценено как O(N), что связано с необходимостью постоянно выбирать среди оставшихся индивидуумов.
Заключение
Таким образом, ответ на вопрос о количестве поколений, необходимом для того, чтобы достичь однородной популяции, составляет O(N). Это связано с тем, что процесс турнирного отбора, даже если и является эффективным, требует времени на постоянное уменьшение количества различных индивидуумов в популяции. Учитывая, что мы исследуем случайные отборы без полноценной замены или других генетических операций, общий вывод о O(N) является наиболее обоснованным.
Эта оценка прекрасна для понимания динамики селекции в рамках генетических алгоритмов и показывает, что даже простые механизмы могут требовать значительных временных затрат для достижения результата.