Complexité temporelle de l'Algorithme Génétique
Est-il possible de calculer le temps de la complexité de l'algorithme génétique?
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)
Grâce
Mise à jour:
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
de remise en forme: Davies–Bouldin index
Comme l'écrit c'est beaucoup trop vague pour répondre. Comment évaluez-vous de remise en forme? Comment êtes-vous en combinant les gènes ensemble? Qu'est-ce que votre arrêt maladie?
La résiliation condition est de 1000 générations je crois
Il y a quelques liens vers les articles sur ce sujet au cs stackexchange: cs.stackexchange.com/questions/7793/...
La résiliation condition est de 1000 générations je crois
Il y a quelques liens vers les articles sur ce sujet au cs stackexchange: cs.stackexchange.com/questions/7793/...
OriginalL'auteur Maggie | 2012-02-05
Vous devez vous connecter pour publier un commentaire.
n'est-il pas quelque chose comme O(P * G * O(Fitness) * ((Pc * O(crossover)) + (H * O(mutation))))
C'est à dire la complexité est proportionnelle au nombre d'éléments, le nombre de générations et le temps de calcul par génération
Si P, G, Pc, et H sont des constantes qui simplifie vraiment à O( O(Fitness) * (O(mutation) + O(crossover)))
OriginalL'auteur Luke McGregor
Si le nombre de générations et de la taille de la population est constante, aussi longtemps que votre mutation de la fonction, la fonction de croisement, et la fonction de remise en forme prend une période de temps connue, le big o est O(1) - il prend un temps constant.
Maintenant, si vous demandez ce que le big O serait pour une population de N et un certain nombre de générations M, c'est différent, mais là où vous savez toutes les variables à l'avance, le temps est constante à l'égard de votre entrée.
OriginalL'auteur Kane
Les Algorithmes génétiques sont pas chaotiques, ils sont stochastiques.
La complexité dépend de la génétique des opérateurs, leur mise en œuvre (qui peut avoir un effet très important sur l'ensemble de la complexité), la représentation des individus et de la population, et, évidemment, sur la fonction de fitness.
Compte tenu de l'habitude choix (point de mutation, un point de croisement, de roue de roulette de sélection) les Algorithmes Génétiques complexité est O(g(nm + nm + n)) avec g le nombre de générations, n la taille de la population et m la taille des individus. Par conséquent, la complexité est de l'ordre de O(gnm)).
C'est la cause d'ignorer la fonction de remise en forme, qui dépend de l'application.
OriginalL'auteur Noah Ryan
Oui, Luke & Kane réponse peut travailler (avec des réserves).
Cependant, la plupart des algorithmes génétiques sont intrinsèquement chaotique. Pour le calcul de O() est peu susceptible d'être utile et pour le pire sans doute trompeuse.
Il y a une meilleure façon de mesurer la complexité du temps--le fait de mesurer le temps d'exécution et une moyenne de.
OriginalL'auteur Ray