遺伝的アルゴリズムの時間複雑度

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 

は、フィットネス：Davies–Bouldin index

Answer 1

はそれをO（P * G * O（フィットネス）*（（Pcは* O（クロスオーバーのようなものをイマイチ））+（Pm * O（突然変異）））））

IE複雑さは項目の数に比例し、ge nerationsと世代あたりの計算時間

P、G、PC、及びPmが本当に単純化する定数である場合にはO（O（ビジネス）*（O（突然変異）+ O（クロスオーバー）））

Answer 2

場合にあなたの突然変異関数、交叉関数、およびフィットネス関数が既知の時間量を要する限り、世代数および母集団サイズは一定です。大きなOはO（1）です - 一定の時間がかかります。

ここで、Nの母集団とMの世代について、大きなOが何であるかを尋ねると、それは異なっていますが、すべての変数を前もって知っているところでは、あなたの入力に対して一定です。

Answer 3

遺伝的アルゴリズムの時間と計算の複雑さを計算することは可能ですか？

はい、ルーン&ケーンの答えが働くことができます（警告付き）。

しかし、ほとんどの遺伝的アルゴリズムは本質的に混沌です。したがって、O（）を計算することは、おそらく誤解を招くおそれがあります。

実行時間と平均を実際に測定することによって、時間の複雑さを測定するより良い方法があります。

Answer 4

遺伝的アルゴリズムは混沌ではなく、確率論的です。 複雑さは、遺伝的演算子、それらの実装（全体的な複雑さに非常に大きな影響を及ぼす可能性がある）、個体と集団の表現、および明らかにフィットネス機能に依存する。 遺伝的アルゴリズムの複雑さはO（g（nm + nm + n））であり、世代数をg、母集団サイズをm、母集団サイズをmとすると、通常の選択（点突然変異、一点交叉、ルーレットホイール選択）個人したがって、複雑さはO（gnm）のオーダである）。
これは、アプリケーションに依存するフィットネス機能を無視するためです。