유전자 알고리즘의 시간 복잡도

유전자 알고리즘의 시간 복잡도를 계산할 수 있습니까?유전자 알고리즘의 시간 복잡도

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

피트니스 : Davies–Bouldin index

출처

2012-02-05 Maggie

이렇게 작성된 것처럼 대답하기에는 너무 모호합니다. 피트니스를 어떻게 평가합니까? 어떻게 유전자를 결합하고 있습니까? 종결 조건은 무엇입니까? – templatetypedef

@templatetypedef 종료 조건은 1000 세대입니다. 믿을 수 있습니다. –

cs stackexchange에서이 주제에 대한 논문 링크가 있습니다 : https://cs.stackexchange.com/questions/7793/time-complexity-of-genetic-algorithms – bmaddy

밤은이 O 같은 (P의 * G의 *의 O (피트니스) * ((PC * O (크로스 오버)) + (Pm * O (돌연변이))))

IE 복잡도는 항목 수에 비례하고, ge nerations 및 생성 당 계산 시간

P, G, PC 및 PM 정말로 단순화하는 것이 일정한 경우 O (O (헬스) * (O (돌연변이) + O (크로스 오버)))

출처

2012-02-05 02:04:05

경우에 돌연변이 함수, 교차 함수 및 적합성 함수가 알려진 시간이 걸리는 한 큰 세대는 O (1) - 일정한 시간이 걸리는 한 세대 수와 인구 크기는 일정합니다.

큰 오가 N 세대와 몇 세대의 M에 대해 무엇이 될 것인지 묻는다면, 그것은 다르다. 그러나 모든 변수를 미리 아는 곳에서 말한 것처럼, 입력에 대해 일정합니다.

출처

2012-02-05 02:18:54 Kane

유전자 알고리즘의 계산 시간과 계산 복잡성을 계산할 수 있습니까?

예, Luke & 케인의 대답은 (경고와 함께) 작동 할 수 있습니다.

그러나 대부분의 유전자 알고리즘은 본질적으로 혼돈입니다. 따라서 O()를 계산하는 것이 유용하고 오도 될 가능성이 낮습니다.

런타임 복잡성을 측정하는 더 좋은 방법은 실제로 런타임과 평균을 측정하는 것입니다.

출처

2012-03-15 20:18:26 Ray

유전 알고리즘은 혼돈이 아니며 확률 적입니다. 복잡성은 유전 연산자, 구현 (전반적인 복잡성에 매우 큰 영향을 미칠 수 있음), 개인 및 인구의 표현, 그리고 분명히 적합 기능에 달려 있습니다. 일반적인 선택 (포인트 변이, 1 포인트 크로스 오버, 룰렛 휠 선택)을 감안할 때 유전자 알고리즘의 복잡성은 O (g (nm + nm + n))이고 g는 세대 수, n은 인구 수, m은 개인. 따라서 복잡성은 O (gnm)의 순서로 나타납니다.
이것은 응용 프로그램에 따라 달라지는 피트니스 기능을 무시하는 이유입니다.

출처

2012-05-03 02:56:47

유전자 알고리즘의 시간 복잡도

답변

관련 문제