Временная сложность генетического алгоритма

Question

Можно ли рассчитать временную сложность генетического алгоритма?

These are my parameter settings:

    Population size (P) = 100
    # of Generations (G) = 1000
    Crossover probability (Pc) = 0.5 (fixed)
    Mutation probability (Pm) = 0.01 (fixed)

Спасибо

Обновлен:

 problem: document clustering
 Chromosome: 50 genes/chrom, allele value = integer(document index)
 crossover: one point crossover (crossover point is randomly selected)
 mutation: randomly change one gene
 termination criteria: 1000 generation

фитнес: индекс Дэвиса – Боулдина

Answer 1

разве это не что-то вроде O (P * G * O (Фитнес) * ((Pc * O (кроссовер)) + (Pm * O (мутация))))

IE сложность относительноколичество элементов, количество поколений и время вычислений на поколение

Если P, G, Pc и Pm постоянны, что действительно упрощается до O (O (пригодность) * (O (мутация) + O)(кроссовер)))

Answer 2

Если число поколений и размер популяции постоянны, пока ваша функция мутации, функция кроссовера и функция пригодности занимают известное количество времени, большое значение O (1) - это занимает постоянное количество времени .

Теперь, если вы спрашиваете, какой будет большой O для населения N и числа поколений M, это другое, но, как указано, когда вы заранее знаете все переменные, количество времени постоянная по отношению к вашему вводу.

Answer 3

Генетические алгоритмы не хаотичны, они стохастичны.Сложность зависит от генетических операторов, их реализации (которая может оказать очень существенное влияние на общую сложность), представления отдельных лиц и населения и, очевидно, от функции пригодности.При обычном выборе (точечная мутация, кроссовер в одну точку, выбор колеса рулетки) сложность Генетических Алгоритмов составляет O (г (нм + нм + n)) с g числом поколений, n размером популяции и m размером особей,Следовательно, сложность имеет порядок O (gnm)).
Это является причиной игнорирования функции пригодности, которая зависит от приложения.

Answer 4

Можно ли рассчитать время и сложность вычислений генетического алгоритма?

Да, ответ Люка и Кейна может сработать (с оговорками).

Однако большинство генетических алгоритмов по своей природе хаотичны. Так что вычисление O () вряд ли будет полезным, а хуже, вероятно, вводящим в заблуждение.

Существует лучший способ измерить временную сложность - путем фактического измерения времени выполнения и усреднения.