遺伝アルゴリズムの符号化モード


転載は出典を明記してください
遺伝アルゴリズムの実現には6つの主な要因がある:パラメータの符号化、初期種群の設定、適応度関数の設計、遺伝操作、アルゴリズム制御パラメータの設定、制約条件の処理.パラメータの符号化は,一つの問題の実行可能な解をその解空間から遺伝アルゴリズムが処理できる探索空間に変換する変換方法である.BTW,復号化は符号化の逆過程である.符号化問題は遺伝アルゴリズムの鍵であり,変異演算子と交差演算子はいずれも符号化方法の影響を受けるため,符号化問題は遺伝計算の効率に大きく影響した.一般的な符号化方法は、バイナリ符号化、グレイ符号化、浮動小数点数符号化、マルチパラメータカスケード符号化、マルチパラメータクロス符号化などである.エンコーディングの評価ポリシー:完全性、健全性、非冗長性
1.バイナリコード
定義:バイナリ符号化方法は、個体遺伝子型がバイナリ符号化シンボル列である二値シンボルセット{0,1}を用いる.バイナリ符号化シンボル列の長さは,問題が要求する解の精度に関係する.メリット:
  • 簡単です.符号化も復号化も非常に便利で迅速です.
  • 交差と変異が便利です.
  • は、最小文字セット符号化の原則に合致する.

  • 欠点:
  • は連続関数の最適化問題に適しておらず,局所探索能力が劣っている.連続した数値の間には海明距離が大きいという問題がある場合がある.例えば、63および64に対応するバイナリは、それぞれ0111111および1000000である.(連続値に対応する2進数7桁はすべて異なる)高精度の問題では,変異後に最適解から遠ざかる場合があり,表現型が不安定である.

  • ケース:f(x)、x∈[0023]があると仮定し、定長バイナリ符号化を採用し、シリアル000101111は175を代表し、符号化精度は1である.
    2.グレイコード
    定義:グレイ符号化は、その連続する2つの整数に対応する符号化の間に1つの符号ビットだけが異なり、残りの符号ビットは完全に同じである.バイナリコードからグレイコードへの変換式は、次のとおりです.
       gm =  bm
    
       gi = b(i+1)⊕bi ,i=m-1,m-2,…2,1
    

    グレイコードからバイナリへの変換式は、次のとおりです.
       bm = gm
    
       bi = b(i+1)⊕gi, i=m-1,m-2,…2,1
    

    利点:-アルゴリズムのローカル検索能力を向上させた-交差と変異を容易にした.-最小文字セット符号化の原則に合致する.ケース:コード比較:原コードバイナリグレイコード0 000 000 000 1 001 2 010 011 3 011 0104 100 110 5 101 6 110 101 7 111 100
    3.浮動小数点数符号化
    定義:個体遺伝子値はある範囲の実数で表される.符号化長は、決定変数の個数に等しい.利点:-精度が高く、連続変数の問題に適しています.海明の崖問題を避けた.-比較的広い範囲を表す数値に適用され、空間の大きい一連の計算探索に適している-計算の複雑さを低減し、効率を向上させる-遺伝アルゴリズムと古典的な最適化方法の混合使用を容易にする-問題に対する専門知識の設計を容易にする知識型遺伝演算子-複雑な決定変数制約条件を処理しやすい.最適化問題の組合せに適したケース:最適化問題に5つの変数があり、各変数の変化範囲が異なると仮定します.ここで、X={5.30,5.20,4.70,3.40,4.80}は遺伝子型であり、対応する表現型はx={5.30,5.20,4.70,3.40,4.80}である.
    4.配列コード
    定義:配列符号化は主にいくつかの特殊な問題に対して行われる.有限集合の要素を中心に並べます.集合内にm個の要素があれば、mがあります!個の配列の組み合わせ.利点:−NPhard問題ではmが大きく,貧挙法が失効し,この場合遺伝アルゴリズムを用いることができる.ケース:よくある応用は旅行者(TSP)問題、ジョブスケジューリング(job-scheduling)問題、リソーススケジューリング(resource-scheduling)問題などです.
    5.2倍体符号化
    定義:生物二倍体遺伝子遺伝方式をシミュレートした.染色体内には同じ形状情報が含まれている.二倍体生物は遺伝子型から表現型まで一定の顕著性がある.異なる等位遺伝子は異なる表現特徴を示した.ケース:遺伝子型AaBbCCddがあると仮定し、A aは等位遺伝子である.A,aは目の色を表し,Aは茶色,aは青色,AAは茶色,aaは青色,Aaは顕隠性の場合によって発色する.
    未完待機.