Genetic Lloyd-Max アルゴリズムによる TMO 生成

階層型のLloyd-Max法を用いることにより大域解に近いTMOを得られるが、更に適す るTMOを求めるために、遺伝的アルゴリズムを利用したGenetic Lloyd-Maxアルゴリズ ム[9]を用いて TMO を得る。遺伝的アルゴリズムとは進化的アルゴリズムの一つであり、

各々の解を遺伝子に見立て、それらにランダムな操作を行い、偶然生まれた優秀な個体を 残し淘汰を行う。これを反復して行い近似解を求める。Genetic Lloyd-Max アルゴリズム においては個体はpartitionに対応する。図3.5にその処理フローを示す。

図3.5 Genetic Lloyd-Max アルゴリズムのメインフローチャート

決められた個体数、N個の異なるpartitionを用意し、それらからN/2個のペアを作る。こ れらのペアに対し、交差率として設定した確率で交差処理を行う。

交差処理では、親となる2つのpartitionをそれぞれ同じ個所で切断し、組み替えた個体 を生成し、それらを子個体として候補に加える。その処理概念図を図3.6(a)に示す。

図3.6(a) 交差処理

切断を行う個所は、図3.6の例の様に組み替えを行った場合にそれらの子個体がインデッ クスに対して単純増加する様な個所に限られる。例えば、図3.6(b)で示される個所で組み替 えを行った場合、子個体2が単純増加で無くなるため、この様な交差処理は許可されない。

図3.6(b) 不正な交差処理

交差処理を終えると、元々のN個の親個体に加え、0~N個の子個体が生成される。以降 の処理にはこの親子関係は考慮されず、N~2N個の個体群として扱われる。

次にこれらの各々の個体に対し、突然変異操作を行う。突然変異操作はpartitionの各要 素に対して独立に行われ、変異率として設定した確率で、その要素を増加、もしくは減少

させる方向へ 1 変化させる。ここでも、partition の隣り合う要素が同一となる、0~1023 の範囲を逸脱するなど、結果として不正なpartitionとなる様な操作は禁止される。

突然変異を行った後は、それぞれの個体のMSEを算出し、淘汰処理に入る。淘汰操作は、

N 個の個体を次世代へ残し、他を捨て去る操作であり、その選択法にはルーレット選択、

ランキング選択などが挙げられる。

・ルーレット選択

ルーレット選択では、各々の個体のMSEが低ければ低いほどその個体が次世代に残る確 率が高くなる様確率を定め、その確率に基づいて選択する方法である。この方法では優秀 な個体が必ずしも次世代に残るとは限らず、偶然性が生まれるが、個体間のMSEの格差が 激しい場合には結局優秀な個体に生存確率が偏ってしまう。

・ランキング選択

ランキング選択では、N～2N個の個体群をMSEの小さい順にソートし、予め順位に応 じて決めておいた確率でルーレット選択と同様に選択する手法である。この手法ではMSE の格差に生存確率が依存しない為、偶然性が相対的に高くなる。

表3.2に選択法としてルーレット選択を用いた場合での、世代別のエリート個体（その世 代の中で最もMSEが低い個体）のMSEを示している。入力としては図3.3(a)の信号を、

親個体群の数Nとしては16を、交差率には0.6、要素毎の突然変異率を0.01に設定し、

初期個体には先述の階層型Lloyd-Max TMOを含め、残りをランダムに生成した。

表3.2 世代数（反復数）とMSEの関係例

Gen. 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 MSE 0.6949 0.6942 0.6940 0.6939 0.6938 0.6937 0.6937 0.6921 0.6916 0.6913

階層型Lloyd-Mac TMOのMSEは0.6969であるが、10000世代を経て、その個体群の中

のエリート個体のMSEは0.6913まで低下している。