関数最適化問題を解く熱力学的遺伝アルゴリズムの有効性の検証～遺伝的アルゴリズムにおける多様性の測定と淘汰戦略への応用手法の研究～

Evaluation of Thermo-dynamical Genetic Algorithm to Solve the Function Optimization Problem—Diversity Measurement and its Application to Selection Strategies in Genetic Algorithms—
髙橋 良 （京都情報大学院大学）
Ryouei Takahashi（The Kyoto College of Graduate Studies for Informatics）

Abstract
In this paper, it is experimentally verified that TDGA (Thermo Genetic Algorithms) is effective insolving a function optimization problem using Genetic Algorithms, because of their sustainability of
population diversity and efficiency of searching for solutions. In our investigation, we measure thediversity of the population with the entropy defined in TDGA. We experimentally and quantitatively
verify the hypothesis that we can improve the ratio of searching for the optimum solution and theaccuracy of the solution by maintaining the diversity. TDGA is a selection strategy based on theminimum free energy principle in thermos-dynamics. In TDGA, we select individuals in the next
population from those candidates generated temporarily for the next generation to satisfy the above
principle. In applying the principle to GAs, we select them to make the average energy E a minimum
and the entropy H a maximum. In this investigation, TDGA and immune-GA are compared withsimple GA and GA with scaling windows from the viewpoint of sustainability of diversity of
population. The effectiveness of these four GA models is verified quantitatively by diversity
measurement. Furthermore, ten test functions are investigated in this report. They are well-known
De Jong’s five functions: F1, F2, F3, F4, and F5, and five well-known multimodal functions: Schaffer's
F6 function, Rastringin's function, Schwefel's function, Griewank's function, and Ackley's function.
Keywords: Genetic Algorithm; Diversity Measurement; TDGA; Immune-GA; BLX-α; Function
Optimization Problem■ 1．はじめにりがあることから，二点交叉（等）による単純な遺生命の進化を模した確率的な解探索モデルである

伝子交叉では，生成できる遺伝子構造パターンに限遺伝的アルゴリズム（Genetic Algorithm: GA）[1] は，りが生じる。このため，解の改善が見られず，局所組み合わせ最適化問題 [2] の解法として有効である

最適解に陥ってしまうことが多い。上記の問題を解ことは良く知られている。遺伝的アルゴリズムの課決するためには，集団の多様性を確保しながらかつ

題の 1 つは「比較的初期の世代で局所的に最適な解解探索効率を落とさない解探索法が必要となる。

に陥ってしまい，そこから脱出できず大域的に最適

本検討では，関数最小値探索問題を遺伝的アルゴな解を探索できなくなってしまう」という初期収束

リズムで解く場合に [5], [6]，集団の多様性を確保しの問題を解決することである [3]。初期収束が起こながら効率的探索を実現する方法として，TDGA

る原因は集団の多様性が確保されていないことであ(Thermo Dynamical Genetic Algorithms) による手る [4]。すなわち，様々な遺伝子構造を持った染色法 が 有 効 で あ る こ と を，immune-GA (immune

体が集団を構成していないことである。このような

32状態では，選択される親の遺伝子構造パターンに限

NAIS Journal

Genetic Algorithms) による手法と比較しながら，

実験により検証する。本実験では，集団の多様性をによる手法や単純 GA 手法やスケーリングウィンド

TDGA で定義されたエントロピーで定量的に測定す

ウ技法と集団の多様性制御の観点から，比較評価しる。
「集団の多様性を確保することにより，最適解た。そして，それ等の有効性を，多様性を測定する

探索率や探索解の精度を向上できる」という仮説を，ことにより，定量的に評価している。スケーリング

実験により，定量的に検証する [7]。TDGA は熱力

ウィンドウ技法は個体の適応度をその個体と何世代

学における自由エネルギー最小化の原理に基づく個

か前の最悪個体（最大関数値を持つ個体）の関数値

体選択法である [8]。そこでは，GA で生成した個体群の中から自由エネルギー F が最小となるように個の差として計算する方法である。当技法では各世代体群を選択する。それは，エントロピー H が最大となるように，
かつ平均エネルギー＜ E ＞が最小（目を確保している。尚，本検討の TDGA や immune-

的関数値が最適）となるように個体群を選択するこ上で動作する。

の終了時に個体の適応度を再計算し，集団の多様性
GA は，スケーリングウィンドウ技法を有する GAとである。immune-GA は Jerne の免疫システムの

上記の 4 つの世代交代モデルでは GA の二点交恒常性に関するイディオタイプネットワーク仮説に

叉で個体を生成するが，生成した個体群の多様性が
閾値以下になった時に，BLX-α を動作させ解探索

基づく最適化モデルである [9], [10]。そこでは，GAで生成した個体と抑制抗体間の染色体構造の類似度を調べ，類似度が高い場合に，その個体の生成を抑の局所化・集中化を実現する方式も併せて検討した。
BLX-α は親として選択した二個体の表現型を n 次止する。抑制抗体群は，互いに類似度の異なる適応

元実数空間内の二点（n 次元ベクトル）に変換し，度の高い（目的関数値が最適値に近い），多様な染色体構造を持った個体群であり，GA がこれまで生変換した 2 個の点を含む直方体内（探索空間の拡
張率 α=0.5）で，ランダムに解候補となる点を選択・成した個体群の中から逐次選択更新される。
一方，n 変数の関数最小値探索問題の場合，これ生成することで，生成する個体の染色体構造の多様性を確保する方法である。BLX-α による探索で多まで，遺伝子交叉演算に工夫をこらした BLX (Blend
Crossover)-α[11], [12] や SPX (Simplex Crossover)様性が閾値以上に向上した場合は，二点交叉法によ[13] が開発されている [14]。BLX-α や SPX 法は，親として選択したβ個（BLX-α では β ＝ 2，SPX

本実験での GA のベンチマークテストで使用される GA の広域探索法に戻す方式を検討した。
る関数は De Jong の標準関数 F1 から F5 と，良くでは β ＝ n+1）の個体を n 次元実数空間内の点（n次元ベクトル）に変換し，変換した β 個の点を含む知られた 5 つの多峰性関数 F6 から F10（Schaffer's

直方体内や（n+1）角形内で，ランダムに解候補とfunction, Griewank's function, Ackey's function）

なる個体を選択・生成する。この個体生成法は解のである [17]，[18]。

探索空間を拡げるので，生成個体の染色体構造の多様性を確保できると考えられる。その意味で，これ等の方法は遺伝子二点交叉等の GA による広域的な探索法を補う交叉法として有効であると期待される。実際，広域探索に遺伝子二点交叉，局所探索に
SPX 法を応用した Bee System [15] 等が提案され，そ の 有 効 性 が 実 験 で 検 証 さ れ て い る。 我 々 もBLX-α や SPX 法が，単純 GA やスケーリングウィ

F6 function, Rastringin's function, Schwefel's■ 2．前提条件
2-1 関数最適化問題
y を実数空間 R に値を取る従属変数，
xi(i=1, 2,…, n)を実数 R に値を取る n 個の独立変数とする関数 f は
y=f(x1,…, xn) と表現され，n 次元の実数の直積空間

ンドウ技法を有する GA [16] において，更に精度のRn から実数空間 R への写像を表す。関数 y=f(x1,…,xn) の最適化問題とは，関数 f の従属変数 y の最適値高い解が得られることを実験で検証できた。そこで

yopt =fopt（最小値 fmin または最大値 fmax）を実数空間 R

は，ルーレット方式 [3] で選択した二個体に対して
二点交叉法で生成した個体に BLX-α や SPX 法を適内で求めること，そして関数 f が最適値 fopt をとった時の n 個の独立変数 xi（i=1,2,・・・,n）の値 xi0

用して変換した実数値の近傍を集中的に解探索させnを n 個の実数の直積空間 Rn におけるある領域 R0（定ている。しかし，これ等の交叉演算のみでは集団の義域）内で求める問題である。De Jong は「遺伝的多様性を充分確保できないことを実験で確認した。

アルゴリズム（GA）のあるクラスに挙動に関する本検討では，TDGA による手法を immune-GA研究」というタイトルで博士論文を書いた。そこで

NAIS Journal33

は，関数最小値探索問題を GA で解く手法を検討し点データで近似される。そして，その近似値としてているが，その中で使用されたテスト関数が De
Jong の標準関数 F1 から F5 である。関数 f の最大求めた固定小数点データを交叉演算の結果生成した値探索問題に対する一般的解法が見つかれば，関数y=f(x1,・・・,xn) の最小値探索問題は，関数 f に− 1
を 掛 け た 関 数 z=g(x1,・・・,xn)= − f(x1,・・・,xn) の最大値探索問題に問題を帰着できるので，その解を求めることができる。

個体と解釈する。また，定義域を超えて解が求まった場合は，「xi0 を a で割った剰余− a」を解とする。
ここで− a としたのは，実数空間を定義域の周期 [ −a, a) で分割した時の開始点だからである。例えば，
精度 l=12 で求めた xi0 が xi0=3.126 で a=2.048 の場
xi0 は xi0=3.126 % 2.048 − 2.048=1.078 − 2.048=
合，− 0.97 と再計算される。

2-2 関 数最小値探索問題を遺伝的アルゴリズムで解く場合の個体の遺伝子型と表現型に関する前提
遺伝的アルゴリズムで関数 y=f(x1,・・・,xn) の最適用度設計

適応度はルーレット方式等で親となる個体を現世小値を求める時，解候補 (x1,・・・,xn) を個体 X として設計する。個体 X は染色体と適応度で特徴づ

代の集団の中から確率的に選択する時に使用されけられる。染色体は 0 か 1 かの値をとる二進固定

その値が高くなればなる程，親として選択されるる。

小数点データ列として設計する。この二進固定小数
点データ列は関数 f の n 個の独立変数 xi の値を表現

確率は大きくなる。

する (i=1,2,・・・,n)。複数変数の場合，二進固定

2-3-1 ス ケーリングウィンドウを持たない GA の小数点データ列は添え字の順番に変数分並べられる。この二進固定小数点データ列を遺伝子型と呼び，それが表現する各変数 xi の値を表現型と呼ぶ。二進固定小数点データの各 1 ビットを 1 つの遺伝子と 解 釈 す る。 遺 伝 子 列 長 L は 染 色 体 長 (chrom_size) と呼ばれ，定義域内における解の探索精度から決まる。xi の定義域が− a から＋ a で，各変数の探索の精度を l 個の遺伝子列で計算できる範囲とす
れば，解探索の精度は a/2l − 1 となる。すなわち，2l個の離散個のデータ xi= − a + k × a/2

l−1(k=0,1,・・・,

場合の適応度設計
GA がスケーリングウィンドウを持たない場合，適応度は個体の染色体構造に合わせ固定値を持つように一般的には設計される。すなわち個体 A と個体
B が同じ染色体構造を持つならば，世代を越えて，同じ適応度となるように設計する。関数最小値探索
問題の場合，関数最小値探索問題の場合，本検討では，適応度 F を F=1/（f ＋ α1）で計算する。α1 は f＋ α1 が正（＞ 0）となるような調整係数であり，プ
ログラム定数として与える。例えば f≧ 0 なら α1=1

2 − 1) の中から関数最小値を満たす xi の値を探索する。そして，染色体長 L は L=n × l と計算できる。

として設計した。

例えば De Jong の標準関数 F2 の独立変数 x1, x2 の定義域は− 2.048 ≦ x1, x2 ＜ 2.048 である。 ここで2-3-2 ス ケーリングウィンドウ技法による適応度

各変数の遺伝子列長 l を l=12 と設計すれば，解探ルーレット方式で適応度の大きさに応じて個体を選択する場合，個体 X の適応度 F（X）は正でなく

l

索の精度は 2.048/2= 1/1000 となる。そして各独立変数 xi に関して，4096=212 個の離散個の値 xi=
12 − 1− 2.048 + k × 1/1000 (i=1,2; k=0, 1, 2, ･･･,4095)の中から解を探索する。また l=13 と設計すれば，解探索の精度は I=12 の 2 倍となり 1/2000 となる。
この時，各独立変数 xi の解は 8192=213 個の離散値設計てはならない。本検討の事例でも見られるように一般にテスト関数 f は正の値も負の値もとる。このため，関数 f の最小値探索問題の解を求めるのに，関数 f に− 1 を掛けて g= − f(x1,・・・,xn) の最大値探

x i = − 2.048 + k × 1/2000 ( i =1,2; k =0, 1, 2,

索問題に変更して，その問題の解を求めようとしても，一般に「− f」は負の値をとるので，「− f」を･･･,8191) の中から探索する。
尚，BLX-α や SPX による交叉演算では独立変数

個体の適応度とすることはできない。従って W 世代
前の個体のうち「− f」が最悪値 ( 最小値 ) となる個

xi の解の探索空間を二進固定小数点で表現される離体 X0= (x10,・・・,xn0) の関数値「− fw(x10,・・・,xn0)」と現世代の個体 X=(x1,・・・,xn) の関数値「− f」と散空間から連続値を取る実数空間に拡張して求めるが，求めた実数解 xi0 は再び精度 l の二進固定小数

34

2-3

NAIS Journalの 差「 − f(x1,・・・,xn) ＋ fw(x10,・・・,xn0)」 を 個 体

X の適応度 F（X）とするスケーリングウィンドウ技法を検討することした。そうすれば個体 X の適応
度 F（X）は正となる。尚，この定義によりスケー

BLK-α による遺伝子交叉により集団の多様性が閾
値 β 以上に回復した場合，二点交叉法に戻している。

リングウィンドウ技法では同じ遺伝子構造でも世代

本遺伝子交叉オペレータ交代法は，二点交叉法により大域的探索を実現し，BLK-α によりある点の近が異なれば適応度が異なることがわかる。また淘汰傍において集中的・局所的探索を実現している。

圧が関数値の大きな個体にかかることを回避でき，
2-5集団の多様性を確保できる。

2-5-1
2-4

遺伝子交叉演算の拡張

スケーリングウィンドウ技法
機能

スケーリングウィンドウ技法は同じ染色体構造を二点遺伝子交叉等で生成した個体の中から多様性持った個体でも，その適応度を世代と共に変化させを考慮しつつ次世代の個体を選択する TDGA やることによって，集団の多様性を確保する方式であimmune-GA による解の探索手法は，遺伝的アルゴる。当技法は，ルーレット方式で適応度に応じて確

リズム (GA) の積み木仮説に基づく解探索手法を前提としている。L を染色体長とすると，TDGA や率的に親となる個体を選択する際に , 様々な遺伝子

immune-GA は，2 個の離散個の探索空間の中で，として生成される子供の遺伝子構造パターンを多く解を確率的に探索する。関数最小値探索問題に遺伝することがそのねらいである。これによって局所最的アルゴリズムを適用して解を探索する場合に，関適解に陥ることを回避する。

L

構造を持った個体が選択される確率を高くし，結果数の連続性を考慮して，関数の最小値を探索すれば，更に効率的な解探索が可能となる。本検討では，

2-5-2

TDGA や immune-GA による解の探索法を補う手

スケーリングウィンドウ技法は，関数最小値探索
問題の場合，W 世代前の個体のうち関数 f の値が最法として，ルーレット方式等で選択した二個体に対して，関数の連続性を考慮して，その二個体の近傍を解探索空間として解探索の局所化を図る遺伝子交叉演算オペレータとして BLK-α を検討した。
BLX-α は親として選択した二個体の表現型を n

スケーリングウィンドウ技法

悪値 ( 最大値 ) となる個体 X0 の関数値 fW(X0)= f(X0)と現世代の個体 X の関数値 f(X) との差を個体 X の
適応度 F(X) とする方法であり，以下の式で定式化される。

次元実数空間内の二点に変換し，変換した二点を含F ( X ) = fW ( X 0 ) − f ( X )(2)

む直方体内で，ランダムに解候補となる点を選択・生成する。α は各変数の探索空間の拡張率であり，従って，スケーリングウィンドウ技法では，同じ

本検討では α=0.5 とした。この探索空間の拡張によ構造を持った染色体でも，世代が異なると，異なっ

り，生成する個体の染色体構造の多様性を確保できる。BLX-α による方法の詳細は，以下の通りである。

た適応度となる。このスケーリングウィンドウ技法
により「適応度 F(X) を，染色体の構造のみによっ関数 y=f (x1,・・,xi,・・, xn) の最小値探索問題において，親となる二個体として X1= (x11,・・,x1i,・・,x1n)て決まる適応度固定法，例えば（関数値 f(X) ＋ α1）の逆数 F(X)=1/（f（X）+α1）とする方法，を用いると X2= (x21,・・,x2i,・・,x2n) が選択したとしよう。この時，解 (x1,・・,xi,・・,xn) を，以下で定義されると関数値の低いある特定の個体のみが親として選択

閉区間 (S1,・・,Si,・・, Sn) の中で，すなわち解 xi ∈Si として，
ランダムに探索する方法が BLX-α である。

GA で生成する個体群の多様性を確保できる。個体される傾向がある」という淘汰圧の課題を解決でき，

Si =[min(x1i,x2i) − α × |x1i − x2i|, max(x1i, x2i) +α ×の適用度の更新は，世代交代の度に行う。スケーリ
ングウィンドウサイズ W は GA の起動パラメータ|x1i − x2i|]，(i=1,2,・・・,n)

で与える。

(1)

本検討では，集団の多様性が閾値 β 以下になった時に大域的探索法である二点交叉法から局所探索法
である BLK-α に変更する遺伝子交叉オペレータ交

2-6

代 法 (Changing Crossover Operators)[19] を 検 討した。ここで β はプログラム定数であり，本実験でHpS 手法（Heterogeneous paring selection
method）は，親 A と遺伝子交叉させる親 B を，そは β ＝ (0.5 〜 0.9) × L と し た。 本 方 式 で は，の遺伝子構造の親 A との類似度 SAB が集団 P の親 A

2-6-1

HeSEA における個体選択法 HpS の応用
機能

NAIS Journal35

的に選択することで，二点交叉等の遺伝子交叉に■ 3．最小値探索問題を解く GA の基本的構造

よって生成される個体群の多様性を間接的に確保す

2 節で述べた y=f(x1,・・・,xn) の最適化問題（最との平均の類似度 SA より低い個体群の中から確率小値探索問題）を解く基本 GA の構造は以下の通り

る方式である。

である。TDGA と immune-GA はスケーリングウィ
2-6-2

ンドウ技法を具備した本 GA 上で構築している。

背景

HpS 手法は，遺伝子交叉の際，親 A と親 B を現世代の個体群の中から適応度の大きさに応じて確率

3-1

初期化処理

的に選択するルーレット方式による親の選択法を修正する方法として提案された。HpS 手法は，親 A とで特徴づけられる。

ペアとなる親 B を，親 A と染色体の構造が似ていな(1) 個体（染色体）群を集団サイズ分初期生成する。

い個体群の中から選択することで遺伝子交叉によっ一様乱数を用いて染色体を構成する遺伝子の値をて生成される個体群の多様性を確保することをねら

ランダムに生成する。遺伝子の値は 0 か 1 である。

いとしている。HpS 手法はもともと巡回セールスマン問題 (Traveling Salesman Problem: TSP) を解く

0 と 1 は対立遺伝子である。
(2) 生成した個体の適応度 F の計算

HeSEA (Heterogeneous Evolutionary Selection（ⅰ）個体の遺伝子型から表現型への変換と表現型

Evolutionary Algorithm) [4] で 開 発 さ れ た。 本 検が表す関数値を求める。

討の HpS 手法は，それを関数最大値探索向けに修正した手法である。

染色体を構成する遺伝子列に解釈を与える。関数
y=f（x1,x2，・・・,xn）の最小値探索問題の場合は独

2-6-3

立変数 xi の二進固定小数点データと解釈し，各個体 を 表 現 す る 染 色 体 の 具 体 的 な 遺 伝 子 列 の 値 cj

類似度の定義(A) 個体 A と個体 X の類似度 SAX
個体 A と個体 X の類似度 SAX を，個体 A と個体 X
で同じ j 番目の遺伝子座にある遺伝子の値 Aj と Xj が集団は個体群から成る。各個体は染色体と適応度(j=1,2,…,L) から関数 f の値を計算して求める。ここで L は 2.2 節で定義した遺伝子列長である。これ
以 降， 個 体 X =（x1,x2，・・・,xn） と そ の 染 色 体
x (c1 , c2 ,  , cL ) は必要のない限り区別をつけないこ
一致する（Aj ＝ Xj）となる遺伝子数 αAX の染色体長 
L に対する割合 r ＝ αAX /L として定義する ( j=1, 2,・
・
・,
ととする。
L)。例えば A=(0,0,1,0,1,0,0,1), X=(1,0,0,1,0,0,0,0) と適応度計算法はスケーリングウィンドウ技法の場

すると，染色体長 L は 8 となる。2 番目，6 番目，7番目の遺伝子座の対立遺伝子の値は A と X で一致し合とそうでない場合で異なる。
（ⅱ）適応度 F の計算ているので αAX ＝ 3 となる。この時 r は r= 3/8=0.375と計算される。SAX=SXA である。

スケーリングウィンドウ技法の場合(B) 集団 P の個体 A との類似度 SA
集団 P が N 個体から成る時，集団 P の個体 A との類似度 SA を，個体 A を除いた集団 P の全ての個
体 Ij の個体 A との類似度 SAIj の平均値とする。すな
わち S A NSj 1, A I j

AI j/( N  1) として定義する。

2-6-4

HpS のアルゴリズム(A) ステップ 1・・親 A を，ルーレット方式で確率的に選択する。

(a) 生成した個体の中で最悪関数値（関数 f の最大
値 fmax(0)=f(Xmax(0)） を 値 に 持 つ 個 体
X max (0)  ( xmax .1 (0), xmax .2 (0),  , xmax .n (0)) を 探 索 す る。 こ こ

で fmax(0) 中の 0 や Xmax(0) 中の 0 は現世代 t が初期世代を示す（t=0）。関数最悪値管理テーブル T にス
ケーリングウィンドウサイズ W 世代数分，最悪値
fmax(0) とその値を実現する個体 Xmax(0) の染色体をコピーする。
(b）W 世代前の世代の中で探索した解の中での最悪
値 fw(Xmax) = fmax(0 − W)=f (Xmax(0 − W )) と現世代の(B) ステップ 2・・親 A の交叉対象となる個体 B を，
その類似度 SAB が集団 P の個体 A との類似度 SA

個体 Xi の関数値 f(Xi) との差 fw(Xmax) − C × f(X i) を個体 X i の適応度 F(Xi) として計算する。C は，適応より小さな個体，すなわち，SAB ≦ SA を満たす
個体 B をランダムに選択する。

度 F(Xi）＞ 0 となるための調整係数でありプログラ
ム定数として与える。調整係数 C はテスト関数によ
り異なる。

36

NAIS Journalスケーリングウィンドウを使わない場合
個体 X の適応度 F(X) は関数値 f(X) によって決または SPX の遺伝子交叉演算である。SPX では関数が n 個の独立変数を持つ時，①にて親として選択しり，世代を越えて固定となる。
次式で F(X ) を定義する。

た (n+1) 個の点の中から (δ+1) 個の点をランダムに選択可能とし，選択した (δ+1) 個の点を含む拡大率

F(X)= 1/（ f (X) ＋ α1）>0
ここで，α1 は調整係数で固定値である。
(3) 世代毎の統計情報出力
生成した個体群の関数値の平均，現世代で探索した個体のうち最良適応度を持つ個体の関数値（世代内最小関数値），これまでの世代で探索した個体のR の拡張 (δ+1) 角形の領域内で次世代の個体をランダムに選択する。このδはプログラム起動パラメー
タとして与える。δ は，2 〜 n の値をとり得る。実験では δ=2 または n とした。
（ⅱ）局所探索法：BLK-α

内，最良適応度を持つ個体の関数値（世代間最小関集団の多様性が閾値 β 以下になった時，k 点交叉または SPX から BLK-α の遺伝子交叉演算に交替す数値），計算時間，集団の多様性を計算して出力する。

る。BLK-α による遺伝子交叉演算の結果，集団の多様性が閾値β以上に回復したら二点交叉または

3-2

終了条件判定以下のいずれかの条件を満たした時に，ジョブを終了する。
（ⅰ）最大観測世代数（M）に達した場合。この数
値 M は プ ロ グ ラ ム 定 数 で あ り， 実 験 で は
10,000 とした。
（ⅱ）探索解の改良がある世代数（G）間，見られない場合。この数値 G はプログラム定数であり，実験では 200 とした。
（ⅲ）集団の多様性（D）が数世代に亘って変化しない場合。この数値 D はプログラム定数であり，実験では 5 とした。

SPX の遺伝子交叉演算に戻す。
(3) 突然変異
生成した二個体のある遺伝子の on/off の値を確率 Pm で反転させる。反転する遺伝子座はランダムに決定する。
(4) 淘汰
生成した子二個体と親の二個体，合わせて四個体の中から次世代の個体を 1 つ選択する。先ず，四個体の関数値を計算する。以下の二つの場合に分けて個体を選択する。
親と子のトーナメントを行う場合
上記四個体の中で最も関数値の小さな個体を次世代の個体として選択する。

3-3

次世代の個体の生成処理

集団サイズ分以下を繰り返す。
(1) 選択
two-point crossover または BLX-α の場合親となる二個体 A と B をルーレット方式またはHpS 法で現世代の個体の中から選択する。ルーレッ
ト方式では親 A と親 B を両方とも適応度の大きさ

親と子のトーナメントを行なわない場合
生成した二個体のうち関数値の小さな個体を次世代の個体として選択する。
3-4

世代交代処理（t － 1 世代→ t 世代）(1) 3-3 で成した次世代（t 世代）候補個体で現世代（t − 1 世代 ) の個体を generation-gap 分入れ替えに応じて確率的に選択する。HpS 法 [4] では親 Aをルーレット方式で選択する。親 B は , 親 A との類る。その際，古い個体の方から先に，新しい個体に似度 SAB が集団 P の親 A との類似度 SA より小さな(2) 3-3 で生成した個体の適応度を求める。

個体の中からランダムに選択する。類似度について（ⅰ）各個体を実現する染色体の具体的な遺伝子列の値から関数 f の値を計算して求める。

は 2-6-3 節で定義している。
(2) 遺伝子交叉
選択した親に対して確率 Pc で遺伝子交叉を行な入れ替える。

スケーリングウィンドウ技法の場合（ⅱ）最悪値管理テーブル T において，k − 1 世代

として以下の二種類のオペレータを集団の多様性を前の最悪個体とその関数値を k 世代前の最悪個体とその関数値で入れ替える（k= W, W − 1,

観測して自動的に切り替える。
（ⅰ）広域探索法：k 点交叉，SPX…, 2, 1)。現世代において最悪関数値（関数 fの 最 大 値 fmax(0)） を 持 つ 個 体 β を 探 索 する。

い，子供を二個体生成する。遺伝子交叉オペレータ

k 点交叉による方法。本実験では k=2 である。ま

最悪値管理テーブル T において現世代 (k=0）

NAIS Journal37

の最悪個体 T(0) を個体 β で入れ替える。
（ⅲ）W をスケーリングウィンドウサイズとする。
この時，W 世代前の世代の中で探索した解の中での最悪値 fmax(t-W) と個体 Xi の関数値 f(Xi)と の 差 fmax(t − W) ー C × f(Xi) を 個 体 Xi の 適
応度 F(Xi) として計算する。この時，全ての個体 Xi について適応度 F(Xi）＞ 0 となるように調整係数 C の値を決める。調整係数 C はプ
ログラム定数として与える。
適応度固定方式の場合
個体 Xi の適応度 F (Xi) は世代をこえて固定値であり，F (Xi)=1/( f (Xi ) ＋ α1) で計算する。F (Xi) ＞ 0 となるように調整係数 α1 の値を決める。調整係数 α1はプログラム定数として与える。
(3) 集団の評価と統計情報出力

上記にて，chrom_size は染色体長 L のことであり。
N は集団 P の集団サイズ（個体数）であり， N 0j は
集団 P の中で第 j 番目の遺伝子の値が 0 となる個体
jの数であり， N1 は集団 P の中で第 j 番目の遺伝子の値が 1 となる個体の数である。従って， N 0 ＋ N1
j
＝ N となる。 p0 は集団 P の中で第 j 番目の遺伝子のj
値が 0 となる確率であり， p1 は集団 P の中で第 j 番jj

目の遺伝子の値が 1 となる確率である。従って， p0
jj＋ p1 =1 となる。エントロピー Hj は，確率分布｛ p0，jp1j｝から決定されるシャノンのエントロピーである。

■

5．力 学的遺伝アルゴリズム（TDGA）による関数最小値探索問題の解法の性能改善

5-1

ねらい

生成した個体群の関数値の平均，現世代で探索し遺伝的アルゴリズム（GA）の早期収束の問題をた個体のうち最良適応度を持つ個体の関数値（世代

解決するためには，染色体構造の異なる個体がバラ内最小関数値），これまでの世代で探索した個体のンス良く集団内に混在している必要がある。集団の内，最良適応度を持つ個体の関数値（世代間最小関多様性を維持しながら最適解探索を効率的に続行す数値），計算時間，集団の多様性を計算して出力する。

る有効な手法として，熱力学的遺伝アルゴリズム(4) 3-2 の処理に戻る。

（TDGA）が開発された。TDGA は，各世代で GA■ 4．集団 P の多様性を測る尺度 Hが一括生成した個体群の中から，自由エネルギー最小化の原理を満たすように個体を逐次取捨選択する手法である。

本研究における集団 P の多様性を測る尺度 H はTDGA のエントロピーに由来する。TDGA を利用して組み合わせ最適化問題を解く時，エントロピー
H は問題対応に異なった解釈を与えなくてはならな

5-2 熱力学的遺伝アルゴリズム（TDGA）の考え方
5-2-1 自由エネルギー F の最小化
TDGA は自由エネルギー最小化の原理に基づくい。これまで，巡回セールスマン問題 (TSP) を解
く GA においてエントロピー H の解釈事例が紹介

個体選択方式である。そこでは，集団の多様性をエントロピー H として明確に測定し，自由エネルギーされている。この事例を参考にして，関数最小値探索問題を GA で解く場合，集団 P のエントロピー

F を最小とするように個体を選択する。自由エネル

H を，以下の式で定義した。この式は，染色体を構

ギー F は，集団の平均エネルギー＜ E ＞を最小化
しかつエントロピー H を最大化するための尺度で成する第 j 番目の遺伝子座にある遺伝子の値の確率あり以下の式で定義される。エントロピー H は集分布から計測されるシャノンのエントロピー情報量
Hj の総和としてエントロピー H を定義することを団の多様性を測る尺度である。
F ＝＜ E ＞− T × H

示している。

(6)

T はシミュレーテッドアニーリング手法における温度のことであり，調整係数である。
5-2-2

温度パラメータ T の調整法
温度パラメータ T はシミュレーテッドアニーリ

ング機能における温度のことであり，集団 P が熱平衡状態に達する度に，高温から低温に徐々に温度を下げて，解探索を収斂させる働きを持つ。その際，温度の減少率を r とする。すなわち，t 世代目の温38

NAIS Journal

Fig.1. Implementation of TDGA to solve the function optimization problem.

度 T を T ＝ Tt，平均エネルギー＜ E ＞を＜ E ＞＝
Et，エントロピー H を H=Ht，これまでの最小エネ
ルギーを Emin，最小エントロピーを Hmin と表した時，Et ≧ Emin, Ht ≧ Hmin を満たしたならばシステムは熱平衡状態に達したとして，t+1 時の温度 T を T ＝
Tt+1 ＝ r × Tt と減少させる。本実験では，温度の減少率 r ＝ 0.9 〜 0.999 とした。

｜ Y ｜ / ｜ X ｜とする。α は GA の起動パラメータであり，実験では 1/2 または 1/3 とした。そこでは，
先ず，Y= φ（空集合）として，X 中で適合度の最も高い（関数最小化問題の場合は関数値の最も小さな）個体を Y に追加することから始める。次に，追加することにより自由エネルギー F が最小となるような個体を X から選択し，逐次 Y に追加する。
＜注意＞

5-3 TDGA の遺伝的アルゴリズムの手続きの中で
の位置づけ
5-3-1

①図 1 にて TDCONST=(1+β)＝1/α である。
②オリジナルの TDGA では，各世代の開始時，現

TDGA のアルゴリズムを組み込む対象とな世代の個体群の中から重複個体を取り除き，取りる遺伝的アルゴリズム除いた個体群を対象として TDGA を適用してい本 検 討 で は， ス ケ ー リ ン グ ウ ィ ン ド ウ 方 式る。しかし，我々の実験では，この関数最小値探（Grefenstette のメタ GA で検討された GA パラメー

索問題の場合，局所解への収束速度が速くなりすタ）で適応度を動的に管理する GA 上で TDGA をぎた。このため，本検討では，重複個体の取り除実現している。

きを行わないこととした。従って，TDGA で生成する個体の数（集団サイズ× TDCONST）は5-3-2

TDGA のアルゴリズム（図 1（Fig.1）参照のこと）

世代を越えて一定とした。
③ TDGA の最初のステップにて適応度の最も高い

TDGA では，遺伝的アルゴリズム（GA）で生成した次世代の個体群候補 X の中から関数値が小さ個体を次世代の個体として選択するが，その際，くかつ集団の多様性を最大とするような個体群 Y を
次世代の個体群として選択する。その選択率を α=

異なる染色体構造を持つ個体を次世代の個体とその最大適応度個体と同じ適応度を持つ個体でして選択する。

NAIS Journal

39

④本検討では，以下の温度制御機能を，オリジナルの TDGA 機能に追加している。

集団の収束性と多様性に大きな影響を与える。単に，二個体のうち優秀な個体のみ残す（間引き），親の「集団が以下の条件を満たした時，多様性が損なわれたとして，温度を T(t+1) ＝ r1 × T(t) と上げる。

方が子より適応度が高ければ，子を捨てて親を残す

そ の 時 の 温 度 係 数 が r1 で あ る。 本 実 験 で は
r1=1.001 とした。

ため，局所最適解に陥ることがある。集団の多様性(new_entropy Ht<minimum_entropy)
new_entropy：新しい世代 t のエントロピー Ht ，す方法が免疫遺伝アルゴリズム（immune-GA）でminimum_entropy：これまでの世代で求めたエント
ロピーの最小値 Hmin」

タイプネットワークによる免疫システムの恒常性に

5-4 関数最小値探索問題への TDGA のカスタマイズ
TDGA で定義された自由エネルギー F を求める

6-2 人工的免疫システム（Artificial Immune System）

ために必要な平均エネルギー＜ E ＞とエントロピー
H の解釈は組み合わせ最適化問題によって異なる。

オタイプネットワークに基づく情報処理システムの関数最小値探索問題はそれぞれを以下のように解釈

疫システムでは抗原に対する免疫抗体が生成され，する。

抗原をその抗体が排除している。免疫抗体は他の免等の淘汰処理では，集団の多様性を考慮していないの維持を考慮して，次世代の個体選択に工夫をこらある。Immune-GA は Jerne の提案したイディオ関する仮説に基づく最適化モデルである。

人工的免疫システムは Jerne の提案したイディことである。イディオタイプネットワークとは「免疫抗体の抗原として働く。これによってある特定の
5-4-1

平均エネルギー＜ E ＞
本検討では，標準関数 f の最小値探索問題を，関抗体が抗体集団を占めることを回避し，様々な抗原

数 f に− 1 を掛け，関数 g=β − f の最大値探索問題
として問題を変換して解く。β は定数である。関数いる。」という免疫システムの恒常性に関する仮説

g の値が大きければ大きいほど適応度は高く設定し①抗原の認識機能，②抗体の再構成機能，③抗体なければならない。一方，自由エネルギー最小化の原理で解を求める場合，平均エネルギー＜ E ＞は，の抑制機能，④排除に利用した抗体（抑制抗体）の適応度が高くなればなる程小さくなるように設計さ
れなければならない。従って関数値 f( x ) を各個体に対して柔軟に対処可能な免疫システムを実現してである。人工的免疫システムは以下の機能から成る。

記憶機能，⑤抗体による抗原の排除機能
6-3 人工的免疫システムの関数最小値探索問題をのエネルギーとして定義することとした。

そして集団 P を構成する個体 の関数値 f( x ) の平解く遺伝的アルゴリズム（GA）の中でのカス均値を平均エネルギー＜ E ＞と定義し，それは以i=1, 2,…,N であり，下の式で定式化される。ここで，本研究では人工的免疫システムの機能（上述①〜⑤）を以下のように関数最適値探索問題を解く GA

N は集団サイズである。

の 中 で 実 現 す る。 当 GA は TSP を 解 く immune-







＜ E ＞ =( f( x1 ) + f( x2 )... +f( xN ))/N

(7)

タマイズ

GA[7] の改良版である。そこでは，①抗原を関数最適値探索問題，抗体をその最適解候補の独立変数（個体）と解釈する。② GA の選択・遺伝子交叉・突然

5-4-2

エントロピー H

関数最小値探索問題を GA で解く場合のエントロ
ピー H の解釈は第 4 節で述べたので割愛する。

■

6．免 疫遺伝アルゴリズム（immune-GA）による関数最小値探索問題を解く GA の性能改善

6-1

40

ねらい

変異機能により抗体を再構成する。本実験では GAの遺伝子交叉演算オペレータとしてテスト関数 F1〜 F10 の最小値探索問題を解く遺伝子交叉演算オ
ペレータ OPs を使用する。当オペレータは Twopoint Crossover または BLX-α で二個体生成する。
このオペレータ自身は関数に依存しない。関数に依存するのは適合度計算に関わる部分のみである。③集団の多様性を確保するため，遺伝子交叉オペレー

遺伝的アルゴリズム（GA）で生成した個体を，タで生成した抗体を排除する機能，④排除に使用し次世代の個体として選択するか否かを決めることはた抑制抗体群（サプレッサ細胞）の更新管理を行う

NAIS Journal

機能。⑤最適解を探索するまで②③④を繰り返す。

決定する方法と他のジョブで生成した染色体ファイ

本 人 工 的 免 疫 シ ス テ ム を Immune Genetic

ルを引き継ぐ方法がある。前者は遺伝子の値としてAlgorithm（Immune-GA） と 呼 ぶ。immune-GA

0 か 1 の値が等確率で決定される。後者の場合は解

では，次世代の個体を一つ一つ追加する際に，集団の収束がある程度進んだ染色体集合を引き継ぐことの多様性をチェックし，それを維持するように，適を仮定しているため，染色体構造の分布に偏りが見応度の高い個体を追加・選択する。

られる。このため，本手続き 6-6-1 でサプレッサ細胞が生成される確率が高いのは後者の場合であり，6-4

抗体 v と抗体 w の類似度（affinity）αv,w の定義

前者の場合はその確率が低い。

生成した抗体のうち，これまで生成した抗体との類似度が高い抗体を排除するのが immune-GA で

6-6-2

immune operation の実行

GA の遺伝子交叉操作により個体を生成し，生成ある。
抗体 v と抗体 w の類似度（affinity）αv,w は同じ遺伝子座にある抗体 v と抗体 w の遺伝子の値が一致した個体に突然変異操作を施す度に，生成した個体

している遺伝子数 η の全遺伝子数（染色体長）L に対する割合 η/L として定義する。例えば v の遺伝子

以下の immune-operation により判断する。これに型が (00010111)，w の遺伝子型が (10101100) ならば，染色体長 L=8 であり，v と w で遺伝子の値が収束速度を向上させる。

一致している遺伝子座は 2 番目の ’0’ と 6 番目の ’1’の 2 つであり η ＝ 2 となる。この時，類似度 αv,w ＝2/8=0.25 となる。この定義は TSP を解く HpS[4]と同じである。
6-6

免疫 operation の詳細

6-6-1

初期サプレッサ細胞の生成

初期抗体を GA の染色体として生成後に以下を行

を次世代の個体（抗体）候補として残すか否かを，より，集団の多様性を確保しつつかつ，最適解への(a) 抗体ｖの抗原に対する効用を関数値 g（v）（GAの適応度（fitness）相当値）として計算する。
(b) サプレッサ細胞の更新処理・・関数値の高い構造の異なる抗体をサプレッサ細胞として記憶する。
・サプレッサ細胞 w より適応度 ( 関数値 g(v)) が高い，または適応度が同じでも類似度のみが異なる抗体 v は，サプレッサ細胞に追加更新する。
・過去のサプレッサ細胞に今期のサプレッサ細胞を追加することにより人口サイズ以上のサプう。

レッサ細胞になった場合は，適応度の低い過去①抗体 v の抗原に対する関数値 g(v)（g(v) ＋ β（β>0）
が GA の適応度 fitness 相当となる）を計算する。

のサプレッサ細胞を削除する。

②サプレッサ細胞を形成する。
・抗体 v と抗体 w の類似度（affinity）αv,w を計算
する
・抗体 v と類似する抗体の集団に占める割合 Cvを計算する。v と w との類似度 αv,w が閾値 TAC1以上の個体 w の全個体中に占める割合（数の比）を Cv とする。
・Cv がある閾値 TC 以上になれば，それを記憶し，サプレッサ細胞とする。
・尚，サプレッサ細胞のサイズは最大人口サイズとする。
・同一構造を持った抗体がすでにサプレッサ細胞(c) 抑制処理（類似抗体の排除）・・多様性を確保するために，既に生成された抗体と類似する抗体の生成を抑制する。
以下の 3 通りの場合を考える。
( 場合 1) 個体（抗体）v がサプレッサ細胞群 S に属するあるサプレッサ細胞 w より適応度が低い（関数値 g(v) が大きい）場合，以下の 2 つの場合を考える。
( 場合 1-1) あるサプレッサ細胞 w との類似度 αv,w がTC1 以上の個体（抗体）v の生成を抑止する。
( 場合 1-2) 全てのサプレッサ細胞 w との類似度 αv,w
が TC1 以下の個体（抗体）v は次世代の個体候補として残す。

にある時，その抗体をサスプレッサ細胞に追加( 場合 2) 生成された抗体 v があるサプレッサ細胞 w

しない。

と同一構造個体の場合で，かつ次世代の個体群候補＜留意点＞
初期抗体を GA で生成する方法としては，染色体の各遺伝子の 0/1 の値を一様乱数によりランダムにの 1 つとしてまだ暫定プール中に記憶されていな
い場合，次世代の個体群候補として残す。
( 場合 3) 生成された抗体 v があるサプレッサ細胞 w

NAIS Journal41

と同一構造個体の場合で，かつ次世代の個体群候補の 1 つとして既に暫定プール中に記憶されていたる。これ等のことを考慮して，抗体 v の生存の期待値 ev を以下の式で定義する。

場合，以下の 3 つの場合を考える。尚，以下に述べる閾値 THRESHOLD は GA 起動パラメータとし

ev＝g(v)×S0 (1/ 
i 1

て与える。

v , wi)(8)( 場合 3-1) サプレッサ細胞 S の平均関数値が閾値
THRESHOLD ×（これまでの最良解の関数値 (best-

上式は，ev を抗体 v との類似度 αv,wi が閾値 TAC2
以上のサプレッサ細胞 wi について，その類似度 αv,wifunction value)）以下の場合は，次世代の個体群候補として残す。世代が早期の段階では平均適応度が低を関数値 g(v) に掛け合わせた数値として定義する
ことを示している。S0 は抗体 v との類似度 αv,wi がいので，重複して生成された個体でも残存確率を高閾値 TAC2 以上のサプレッサ細胞 wi の数である。

くし，解への収束を早める。世代が早期の段階は収束性重視となる。

＜注意事項＞
g(v) が負のため，ev とサプレッサセルの平均 Avg( 場合 3-2) サプレッサ細胞 S の平均関数値が閾値
THRESHOLD ×（これまでの最良解の関数値 (best-（S）は負となる。αv,w は 0 から 1 の値をとる。従って，
ev が Avg（S）の TC2 倍より低い時に抗体 v の生成

function value)）以上の場合は，その生成を抑止し，次世代の個体群候補から削除する。世代が後期の段を抑制するためには，v と w の類似度の逆数 1/αv,wi
を f(v) に掛け合わせてそれを ev の定義としなくて階は平均適応度が高いので，重複した個体の残存確はならないことに注意する。同様に TC2 は 1 以上率を低くし，集団の多様性を重視する。世代の後期でなくてはならない。

の段階は多様性重視となる。
＜注意事項＞
6-4 節で述べたように，関数の平均値（Avg(g)）
やこれまでの最良解の関数値 (best-function value sofar） は 一 般 に 負 の 値 を と る た め，Avg(g) が bestfunction value の閾値 TH 倍以上か否かで集団の収束■ 7．実験とその結果
7-1

テスト関数

テスト関数は F1 から F10 の 10 個の関数である。
詳細は 7-6 と付録を参照のこと。

が始まったことを判断するためには TH の値を 1 以上にする必要がある。

実験環境(d) 淘汰 (selection)・・適応度が低く，かつ互いに数 値 実 験 は， 主 に，Dell Precision T3500，

類似度の高い抗体が生成されることを回避して，

Intel(R) Xeron (R) CPU W3680，3.33 GHz，6GB

解探索速度を向上させる。

RAM, Windows 10 上で試験を行なった。システム

当プロセスではプロセス (c) で生成を抑制されなかった抗体に対して，次期世代の生存期待値 ev を

開 発 言 語 は C 言 語 で あ る。C 言 語 の 処 理 系 は計算し，ev が閾値（サプレッサ細胞 S の平均関数値
Avg（S）の TC2 倍）以下となれば，その抗体の生ムである。

成を抑止し，次世代の個体群候補から削除する。抗体 v の生存の期待値 ev は次のように設計する。

7-3

抗体 v との類似度が大きい個体が多ければ多い
程，抗体 v の生存の期待値 ev は小さくなるようにした。そして，最適解の探索効率と解の探索精度と設計する。また，抗体 v の関数値 g(v) が高い程抗体 v の生存の期待値 ev は大きくなるように設計す(1) Non-Scaling GA(Non-SW)・・スケーリングウィ

る。また，関数値 g(v) が正の値をとる場合は g(v)− δ が負の値を取るように調整係数（δ ＞ 0）を選

(2) Scaling Window GA(SW-GA)・・スケーリング

択する。この調整係数 δ はプログラム定数として与え る。 そ し て g(v) − δ を 改 め て 関 数 g(v) と お き，

(3) Immuune-GA with scaling window・・スケー

関数値 g(v) が負となるようになるようにテスト関(4) TDGA with scaling window・・スケーリング数の適応度設計等に工夫がされていることを仮定す

42

7-2

NAIS Journal

Microsoft Visual C++ 2010 デベロプメントシステ

評価対象 GA以下の 4 つの GA モデルを，C プログラムで実現
多様性維持機能を比較評価した。
ンドウ技法を持たない単純 GA
ウィンドウ技法を有する GA
リングウィンドウ技法を有する Immune-GA
ウィンドウを有する TDGATable 1. Results of evaluation of TDGA, immune-GA, Scaling Window GA and non-Scaling GA through ten test functions.
Test
Function

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

GA modelsRatio ofoptimum
trialsRelative error

Best minimum
value

Ave.
gen.

Ave.
initial div.

Ave.
best
div.

Ave. final
div.

Non-SW*

15/15

0

0

13

29.93

27.24

0

SW-GA**

15/15

0

0

15

29.93

26.87

0

Immune-GA

15/15

0

0

16

29.93

26.54

0

TDGA

15/15

0

0

13

29.79

27.83

23.93

Non-SW

13/15

0.000000033334167

0

23

25.93

9.62

0

SW-GA

12/15

0.000009016607500

0

22

25.93

10.79

0

Immune-GA

13/15

0.000002087760417

0

27

25.93

12.26

0

TDGA

13/15

0.000273394880000

0

40

25.79

17.9

9.42

Non-SW

15/15

0

- 30
- 30

19

49.88

26.77

4.18

- 30

18

49.88

25.38

1.18

21

49.88

28.79

3.94

SW-GA

15/15

0

Immune-GA

15/15

0

TDGA

15/15

0

- 30

22

49.62

19.97

2.97

Non-SW

2/15

0.020768388371756

0.007090033793755

608

239.42127.85125.22

SW-GA

2/15

0.014790146973541

0.006202866585284

532

239.42125126.56

Immune-GA

2/150.019095658949756

0.007374419566332

600

239.42126.57126.22TDGA

4/15

0.013520268602822

0.006378799132664

666

238.24220.02181.75

Non-SW

15/15

0.000000000000575

0.998003837795203

17

33.92

13.73

0

SW-GA

15/15

0.000000000000575

0.998003837795203

17

33.92

13.19

0

Immune-GA

15/150.000000000942441

0.998003837794628

13

33.92

18.2

0.08

TDGA

15/15

0.000000000000575

0.998003837795203

77

33.73

17.21

4.87

Non-SW

15/15

0

0

7

15.96

12.86

0

SW-GA

15/15

0

0

7

15.96

11.94

0

Immune-GA

15/15

0

0

7

15.96

13.84

0

TDGA

15/15

0

0

6

15.88

15.31

4.86

Non-SW

0/15

11.75761412915560

5.969921589175300

156

279.34

18.1

0

SW-GA

0/15

9.967152137000000

4.975318872000000

149

279.3420.1

0Immune-GA

0/15

8.159139807873520

3.980137279018880

165

279.34

27.46

0.48

TDGA

12/15

1.525963631000000

0.000077496800000

359

277.95

85.52

13.72

Non-SW

15/15

0.006237505352
0.006237505352-4189.822635218985

43

99.77

18.47

0

-4189.822635218985

45

99.77

16.18

0

-4189.822635218985

45

99.77

19.79

0

SW-GA

15/15

Immune-GA

15/150.006237505352

TDGA

15/15

0.006237505352-4189.822635218985

132

99.31

64.44

49.23

Non-SW

7/15

0.115743947894937

0.032507253194352

61

109.73

26.72

0

SW-GA

6/15

0.111482000275566

0.032507253194352

57

109.7331.64

0Immune-GA

8/15

0.143519178881590

0.046797078163841

67

109.73

21.44

0

TDGA

14/15

0.063024064593111

0.032507253194352

99

109.2

63.27

12.48

Non-SW

13/15

0.163432156222627

0

27

59.86

36.13

0

SW-GA

14/15

0.081716078111313

0

25

59.86

37.41

0

Immune-GA

15/15

0

0

30

59.86

43.54

0

TDGA

15/15

0

0

32

59.59

50.99

1.9

NAIS Journal

43

7-4

GA 起動パラメータの組み合わせである。

上記の 4 つの GA モデルの各々について，以下(3) 最良関数最小値 (Best minimum value): 最良モデの GA 起動パラメータの組み合わせ毎に，一様乱数

ルが見つけた関数の最小値。最良モデルとは，の初期値＝ 1 〜 15 とした 15 回の独立な試験を行

15 回の独立な各々の試験の中で見つけた関数のなった。一様乱数の初期値が異なれば，最適解候補

最小値の中で最も小さな最小値を見つけたモデとなる各独立変数の初期値が異なり，試験の独立性

ルのこと。

を保証できる。
(1) 集団サイズ Table1 は⑤の場合のまとめである。
① 30

② 60

③ 120

④ 240

(4) 平均世代番号 (Average number of generations(Ave.
gen.)): 15 回の独立な各々の試験において，関数⑤ 300の最小値を見つけるのに要した世代番号の平均(2) Scaling windowsize
Table1 は 7 の場合のまとめである。

値(5) 平均計算時間 ( 単位：sec.): 15 回の独立な各々2か3か7(3) 親選択法の試験において，関数の最小値を見つけるのにTable1 は②の場合のまとめである。

① Roulette 方式② HpS 方式

要したコンピュータ計算時間の平均値(6) 多様性の平均初期値 (Average initial diversity (Ave.

(4) 交叉演算法① Two-point-crossover 法② Two-point-crossover ＋ BLX- α法

initial div.)): 15 回の独立な各々の試験において，初期世代に生成した個体群の多様性の平均値(7) 多様性の平均最良値 (Average best diversity (Ave.

Two-point-crossover（大域探索）から BLX-α（局best div.: =Div.opt)): 15 回の独立な各々の試験にお所探索）への遺伝子交叉オペレータの交替は集団の多様性（TDGA のエントロピー H）が閾値 β=L × 0.9，

いて，関数の最小値を見つけた世代開始時の個または β ＝ L × 0.5 以下になった時とした。集団の多様性 H が閾値 β 以上に回復したら，再び BLX-α(8) 多様性の平均最終値 (Average final diversity (Ave.
final div.)): 15 回の独立な各々の試験において，から Two-point-crossover に遺伝子交叉オペレータ
を 交 替 す る。 こ こ で L は 染 色 体 長 で あ る。 尚，

ジョブを停止した世代終了時の個体群の多様性

α=0.5 である。

体群の多様性

7-6

実験結果

実験結果を表 1 にまとめる。
7-5

評価項目

(1) 最適解探索率 (Ratio of optimum trials (Ropt)): 15 回の独立な試験の中で最適解（関数最小値）を探索できた回数 M の割合のこと。Ropt ＝ M/15 で性の平均初期値を四捨五入して得られることに注意計算する。最適解（関数最小値）はテスト関数

一様乱数で決定されるからである。例えばテスト関の形がわかり易い場合はすぐにその値がわかる。

数 F1 の多様性の平均初期値は 29.93 であるが，小しかし，遺伝アルゴリズムで探索可能な解は，染色体長を L とすれば，2L 個の離散値であり，数点以下を四捨五入して 30 となる。この値は F1の個体の染色体長 L=10 ビット× 3 に一致している。

探索の範囲が限られる。従って染色体長 L が短以下に実験結果を要約する。
尚，テスト関数 f の特徴や観測精度の説明ならびせよ。何故なら染色体を構成する遺伝子の on/off はい場合は，探索の範囲に，理論的な最適解が含まれない場合がある。その場合は，染色体長 Lにそのグラフを付録として追加した。本検討では，の精度で見つけ得る解の中で最も関数の値が小関数最小値探索問題は関数に− 1 を掛けて関数最さな値を最適解と呼ぶ。最適解とは，関数の従大値探索問題に変換して問題を解いている。このた

属変数の値と，それを実現する独立変数の値のめ，各テスト関数 f に− 1 を掛けた関数のグラフことをいう。
(2) 相対誤差 (Relative Error(ER)): 15 回の独立な試験

g= − f を以下に描いている。
(1) D e Jong’s test function F1: Parabola (sphere

で探索した関数最小値の平均値−最適最小値。
最適最小値は 7-6 節で説明されるが，それは理論的または実験的に計算して求められた最小値

44

表では，Two point Crossover + BLX-α（α=0.5）の場合の実験結果をまとめた。染色体長 L は多様

NAIS Journalfunction) (unimodal: single peak) (see Fig. A.1)
3

＜定義式＞ z  f ( x1 , x2 , x3 )   xi
i 12

Fig. A.1

Inverted De Jong test function F1: parabola.

＜定義域＞− 5.12 ≦ xi ＜ 5.12 (i=1, 2, 3)＜染色体長 L ＞ 30 (bit)=10 (bit) × 3 ( 変数 )＜最適最小値＞ xi=0 (i=1, 2, 3) の時，F1 は最小値

Fig. A.2 Inverted De Jong Test Function F2: Rosenbrock’s saddle.
5＜定義式＞ z = f ( x1 , x2 , x3 , x4 , x5 ) = ∑ xi 
i =1＜定義域＞− 5.12 ≦ xi ＜ 5.12 (i=1, 2, 3, 4, 5)

0 をとる。

＜染色体長＞ 50 (bit) =10 (bit) × 5 ( 変数 )＜実験結果＞ 表 1 から 4 つの GA モデルの各々に＜最適最小値＞閉区間 [-5.12,-5.01] に属する数値のついて最適解探索率 Ropt が 100% (=15/15) である

うち上記精度のもと GA で探索可能な 12 個の離散ことがわかる。

値｛-5.12, -5.11, -5.10,...,-5.01｝のいずれかの値を
各 xi (i=1, 2, 3, 4, 5) が取った時に，F3 は最小値 -30＜説明＞ De-Jong の標準関数 F1: parabola は 3 個の独立変数 x1，x2，x3 の二乗和を求める関数である。
式の形から，x1 ＝ 0，x2 ＝ 0，x3 ＝ 0 の値をとったをとる。

時に最小値 0 をとることがすぐわかる。関数 F1 の＜実験結果＞表 1 から 4 つの GA モデルの各々について最適解探索率 Ropt が 100% (=15/15) であるこ

最小値探索問題は GA の解探索性能を評価する上でとがわかる。

最も入門的な問題である。尚，各独立変数の値の観＜説明＞ De Jong の標準関数 F3: Step Function
は，xi を 越 え な い 最 大 の 整 数 ⌊ xi ⌋ ＝ floor(xi) を 5

測間隔は 5.12 × 2 /2 =0.01 である。
(2) D e Jong’s test function F2: Rosenbrock's saddle
10(unimodal): (see Fig. A.2)
2

＜定義式＞ z = f ( x1 , x2 ) = 100( x1 − x2 ) + (1 − x1 )22

＜定義域＞− 2.048 ≦ xi ＜ 2.048 (i=1, 2)

つ足した整数である。ここで ⌊ ⌋ はガウス記号である。例えば，⌊-5.12⌋ ＝− 6,⌊5.12⌋ ＝ 5,⌊5⌋ ＝ 5 となる。従って F3 の最小値は ⌊ xi ⌋= − 6 をとった時でその値は− 30 である。他の関数にない特徴は，最適解を持つ点が唯一つではなく，複数の点（先の議＜染色体長＞ 26 (bit) =13 (bit) × 2 ( 変数 )論から 125 個となる）で最適値を取ることである。

＜最適最小値＞ x1=1, x2=1 の時 F2 は最小値 0 をとる。

点は 5 つの独立変数をその要素とするベクトルで＜実験結果＞表 1 から 4 つの GA モデルの各々について最適解探索率 Ropt が 80% (=12/15) 以上であある。各独立変数の値の観測間隔は 5.12 × 2 /210

ることがわかる。
＜ 説 明 ＞ De-Jong の 標 準 関 数 F2: Rosenbrock’s
saddle は 2 個の独立変数 x1 と x2 があり x1 の二乗とx2 の差の二乗を 100 倍した数値と（1 − x1）の二=0.01 である。
(4) D e Jong’s test function F4: Quadratic with noise(unimodal): (see Fig. A.4)30

・・, x30 )  ixi  GAUSS (0,1)＜定義式＞ z  f ( x1 , x2 ,・
4i 1乗を和した数値を求める関数である。式の形から
x1=1, x2=1 の時に最小値が 0 であることはすぐわか
るが，2 変数の関係で F2 の最小値が求まるので
GA にとっては問題を解くことがやや難しい。各独立変数の値の観測間隔は 2.048 × 2 /213 =0.005 である。De Jong の論文では，解の探索精度を，0.001
刻みで，24=12 ビット× 2 変数を染色体長としている。本検討では解の精度を 2 倍に向上させた。
(3) De Jong’s test function F3: Step function (unimodal):(see Fig. A.3)

Fig. A. 3. Inverted, two-dimensional version of De Jong
Test Function F3: Step function.

NAIS Journal

45

Fig. A. 4 Inverted, two-dimensional version of De Jong
Test Function F4: Quadratic with Noise.

注意：ガウス分布に従って発生する雑音が負の場合，変数の値の観測間隔は 1.28 × 2 /28 =0.01 である。

符号を変えて正とする。

＜ガウス分布に従って発生する乱数の発生法＞＜定義域＞− 1.28 ≦ xi ＜ 1.28 (i=1, 2,..., 30)＜染色体長＞ 240 (bit) =8 (bit) × 30 ( 変数 )＜最適最小値＞全ての xi (i=1, 2,..., 30) が xi ＝ 0 で，かつ雑音 =0.0 の時に，F4 は最小値 0 をとる。
＜実験結果＞
F4 による評価では，探索した関数値が 0.01 以下の時に最適解を探索したモデルであると判断した。
表 1 から 4 つの GA モデルの各々について最適解
探索率 Ropt が 27% (=4/15) 以下であることがわかる。
しかしながら 4 つのモデルの中で TDGA モデルが解 の 相 対 誤 差 ER の 値 が 最 も 小 さ く そ の 値 は46

Fig. A. 5 Inverted, two-dimensional version of De Jong
Test Function F5: Shekel’s foxholes.

以下の 2 つから選択可能とした。
・中心極限定理による方法
・Box Müller 法 (cos 型または sin 型 )(5) D e Jong’s test function F5: Shekel’s foxholes(multimodal: multiple peaks): (see Fig. A.5)
< 定義式 >

25
1
1
[
]1
z
f ( x, y)   j 1500
j  ( x  a[ j ])6  ( y  b[ j ])6＜定義域＞ − 65.536 ≦ x , y ＜ 65.536＜染色体長＞ 34 (bit) =17 (bit) × 2 ( 変数 )＜最適最小値＞我々の実験では (x, y)= ( − 31.9785,

0.01352 であった。この理由は TDGA が最適解探
索時に集団の多様性 Div.opt を 220 以上確保できてい− 31.9785) の 時 に 最 小 値 0.998003837794628 をたのに対し，他のモデルは最適解探索時に集団の多様性 Div.opt を 130 以下しか確保できていなかった＜実験結果＞ F5 による評価では，探索した関数値からである。この結果は集団の多様性を確保することが解の探索精度の向上をもたらすことを示していあると判断した。表 1 から 4 つの GA モデルの各々について最適解探索率 Ropt が 100% (=15/15) であるる。 更 に， ジ ョ ブ の 停 止 条 件 を 200 世 代 か らことがわかる。

10000 世代に延長し，10000 世代観測すると，4 つの GA モデルの各々について最適解探索率 Ropt が＜説明＞ De Jong の標準関数 F5: Shekel’s foxholes
は，25 個の二次元の特異点 a[j] × b[j] からの点 (x,y)

87% (=13/15) 以上になることを確認した。最適解の 6 乗誤差に点番号を足した数値の逆数の総和に探索率を向上できた理由は，各世代の終了時の集団

1/500 を和した数値の逆数をその値とする関数であの多様性を 50 以上確保できていたからと考えられる。F5 式は 25 個の特異点の値をとった時に極小る。尚，最適解探索効率が悪い理由は雑音が評価関点となる。多くの極小点をその値としてとることか数に含まれていたためである。

ら，当関数は多峰性関数と呼ばれている。極値を複＜説明＞ De-Jong の標準関数 F4: Quadratic with数持つので，その近傍から最小値を探索することはNoise は 30 個の「独立変数の 4 乗に変数番号を掛難しい。各独立変数の値の観測間隔は 65.536 × 2

けた数値」の総和で表現される信号と，平均値 0,/217 =0.001 である。

分散 1 のガウス分布に従って−∞から＋∞の実数＜ 点 a[j] × b[j](j=1,2,･･･,25) ＞ は 特 異 点 で あ り，

値を確率的に取る雑音 ( 乱数 ) の和である。尚 , ガ

fox holes と呼ぶ。その値は De Jong の博士論文のウス分布に従って発生する乱数が負の場合，符号をデータと同じであり，以下の値としている。

変えて正とする。関数の形から全ての独立変数 xi

a[25]={-32.0,-16.0,0.0,16.0,32.0,-32.0,-

が 0 をとった時最小値 0 となることはすぐわかる

16.0,0.0,16.0,32.0,-32.0,-16.0,0.0,16.0,32.0,-32.0,-が，雑音がある分問題が難しくなっている。各独立

16.0,0.0,16.0,32.0,-32.0,-16.0,0.0,16.0,32.0}

NAIS Journal

探索した。
が 0.998004 以下の時に最適解を探索したモデルで

Fig. A. 6

Inverted, Schaffer's F6 function.

Fig. A. 7

Inverted, two-dimensional version of Rastringin'sfunction.

b[25]={-32.0,-32.0,-32.0,-32.0,-32.0,-16.0,-16.0,-モデルは最適解探索時に集団の多様性 Div.opt を最大16.0,-16.0,-16.0, 0.0,0.0,0.0,0.0,0.0,16.0,16.0,16.0,

28 しか確保できていなかったことがわかる。この

16.0,16.0,32.0,32.0,32.0,32.0,32.0}(6) Schaffer's test function F6 (multimodal): (see Fig. A.6)

結果は，集団の多様性を確保することが最適解探索率 Ropt の向上をもたらすことを示している。

sin2 ( x2  y 2 )  0.5
f ( x, y ) 
0.5 ＜定義式＞ z 
(1  0.001  ( x2  y2 ))2＜定義域＞− 100 ≦ x , y ＜ 100＜染色体長＞ 16 (bit) =8 (bit) × 2 ( 変数 )＜最適最小値＞ x=y=0 の時，F6 は最小値 0 をとる。
＜実験結果＞表 1 から 4 つの GA モデルの各々について最適解探索率 Ropt が 100% (=15/15) であるこ

＜説明＞一般に α が実数の時，（1 − cosα）≧ 0 なので，関数 F7 の従属変数 z ≧ 0 となる。z=0 とな
るのは xi 2=0，かつ 1 − cos xi =0 の時であり，両方を満たすのは xi =0 の時であることがわかる。各独立変数の値の観測間隔は 5.12 × 2 /214=0.000625
である。
(8) Schwefel's test function F8 (multimodal): (see Fig.
A.8)とがわかる。
＜説明＞ α が実数の時，一般に sin(α) 関数は -1 か

x10 )
・
・,
< 定義式 > z  f ( x1 , x2 ,・

ら 1 の値をとるので，1 ≧ sin (α) ≧ 0 となる。従って Schaffer's F6 関数の場合，1 ≧ z=f(x,y) ≧ 0 と< 定義域 > − 500 ≦ xi ＜ 500 (i=1, 2, 3..., 10)

な っている。このこ と か ら，F8 が 0 と な る の は
x=0,y=0 の場合であることがすぐわかる。各独立変< 染色体長 >100 (bit) =10 (bit) × 10 ( 変数 )< 最 適 最 小 値 > 全 て の xi(i=1, 2,...,10) が数の値の観測間隔は 100 × 2 /28=0.78125 である。
(7) Rastringin's test function F7 (multimodal): (see Fig.

xi=420.968746 の 時，F8 は 最 小 値 − 4189.828873

2

i 1

i

i

をとる。
< 実験結果 > 表 1 は，染色体長が 100 ビットの精

A.7)
＜定義式＞

10

  x  sin( x )20度のもと，最小値− 4189.822635 を探索できたこz  f ( x1 , x2 ,・・・, x20 ) 10  20   ( xi  10  cos(2xi ))2

i 1＜定義域＞ − 5.12 ≦ xi ＜ 5.12 (i=1, 2,….., 20)＜染色体長＞ 280 (bit) =14 (bit) × 20 ( 変数 )とを示している。そして，4 つの GA モデルの各々について最適解探索率 Ropt が 100% (=15/15) である
ことがわかる。
染色体長が 100 ビットの精度のもとでは，GA で＜最適最小値＞ 全ての xi (i=1, 2,..., 20) が xi ＝ 0の時，F7 は最小値 0 をとる。
＜実験結果＞ F7 による評価では，探索した関数値
が 2 以下の時に最適解を探索したモデルであると判断した。表 1 から TDGA モデルのみが 2 以下の関数値を探索していることがわかる。そしてその最適 解 探 索 率 Ropt は 80% (=12/15) で あ っ た。 一 方，
表 1 から TDGA のみが最適解探索時に集団の多様性 Div.opt を 85 以上確保できていたのに対し，他のFig. A. 8 Inverted, two-dimensional version of Schwefel's
function.

NAIS Journal47

探 索 可 能 な 最 小 値 は 全 て の xi に つ い て
xi=420.8984375 の 時 で そ の 時 の F8 の 値 は −4189.822635 であることを実験で検証できる。従って，F8 に よ る 評 価 で は， 探 索 し た 関 数 値 が −4189.822635 の時に最適解を探索したモデルであると判断した。
全 て の xi (i=1, 2,...,10) に つ い て xi=420.968746の時，F8 は最小値− 4189.8288727243371 をとる
ことはよく知られている。染色体長が 100 ビットの精度のもとでは，全ての xi が xi=420.8984375 の時に GA は− 4189.8226352189849 の極小値を探索できることを実験で検証した。この数値の前後で観測可能な xi は 419.921875 と 421.875 であるが，そ の 時 の 関 数 値 は − 4188.4466107056924 と −4188.7922142631587 で

あ

り，

−

4189.822635218984900 よ り 大 き い。 そ し て，
xi=420.968746 は 観 測 可 能 点 xi=420.8984375 とxi=421.875 の区間に入っている。従って，関数の連続性より，極小値− 4189.8226352189849 を関数 F8 の最小値であると判断した。従って，F8 によ る 評 価 で は， 探 索 し た 関 数 値 が −4189.8226352189849 の時に最適解を探索したモデルであると判断した。表 1 は，4 つの GA モデルの各々が最小値− 4189.8226352189849 を探索できたこと，最適解探索率 Ropt が 100% (=15/15) である
ことを示している。
＜説明＞一般に α が実数の時，-1 ≦ sinα ≦ 1 なこと，z  f ( x1 , x2 ,・・・, x10 ) x
1 10 2 10xi   cos( i )  1
4000 i 1ii 1＜定義域＞ − 600 ≦ xi<600 (i=1, 2, 3..., 10)＜染色体長＞ 110 (bit) =11 (bit) × 10 ( 変数 )＜最適最小値＞全ての xi (i=1, 2,..., 10) について xi=0 の時，F9 は最小値 0 をとる。
＜実験結果＞ F9 による評価では，探索した関数値
が 0.1 以下の時に最適解を探索したモデルであると
判 断 し た。 表 1 か ら 4 つ の GA モ デ ル の う ち
TDGA のみが最適解探索率 Ropt が 93% (=14/15) であること，他の 3 つのモデルは 53% (=8/15) 以下であることがわかった。一方，表 1 から TDGA のみ
が最適解探索時に集団の多様性 Div.opt を 60 以上確保できていたのに対し，他のモデルは最適解探索時に集団の多様性 Div.opt を最大 32 しか確保できていなかったことがわかる。この結果は，集団の多様性を確保することが最適解探索率 Ropt の向上をもたらすことを示している。
2＜ 説 明 ＞ xi ≧0,1 

10xi cos( i ) ≧ 0, ≧ 0 な の で，i 1

F9 は正の値を取る。従って，F9 が 0 となるのは両不等式が 0 となる時であり，それを満たすのは xi＝ 0 の時であることがわかる。各独立変数 xi の値の観測間隔は 600 × 2 /211=0.5859375 である。
(10) Ackley's test function F10 (multimodal): (see Fig.
A.10)

10 個の変数 xi について│ xi │≦ 500（i=1,2・・・,10）なことから，Schwefel's function の従属変数 z の値

＜定義式＞ z  f ( x1 , x2 ,・・・, x10 ) 

域は，-5000<z<5000 となる。従って，従属変数 z は 20  exp( 0.2 

正負のいずれの値もとる。周期関数 sin を含んでいるので，F8 は複数の局所最小解を持つ。各独立変数の値の観測間隔は 500 × 2 /2 = 0.9765625 である。
(9) Griewank's test function F9 (multimodal): (see Fig.
10

A.9)

Fig. A. 9 Inverted, two-dimensional version of Griewank's
function.

48

＜定義式＞

NAIS Journal

1 10 2
1 10xi )  exp(  cos(2xi ))  20  e

10 i 1
10 i 1＜定義域＞− 32 ≦ xi ＜ 32 (i=1, 2, 3..., 10)＜染色体長＞ 60 (bit) =6 (bit) × 10 ( 変数 )＜最適最小値＞全ての xi (i=1, 2,...,10) が xi =0 の時，
F10 は最小値 0 をとる。

Fig. A.10 Inverted, two-dimensional version of Ackley'sfunction.

＜実験結果＞表 1 から 4 つの GA モデル全体で最(d) TDGA with scaling window: 0.89 (=134/150)

適解探索率 Ropt が 95% (=(13+14+15+15)/(15 × 4))
であることがわかる。

上記の実験結果は，GA で関数最小値探索問題を解く時，BLX-α と二点交叉（two-point crossover）＜説明＞ F10 は，指数関数 y=ex=exp(x) の性質を利が協調しながら交叉演算を行なう場合の TDGA が用して GA がその最小値を実験的に導けるかという最も効率的な解探索を実現できること，実験では最適解探索率 Ropt が 0.89% (=134/150)) であったこと問題である。理論的に関数 F10 の最小値が 0 となる理由は，以下である。先ず，ex は単調増加関数であり，1=e なことから e は x が負の時 1 以下となる。
0x

1  exp( 0.2 

1 10 2
 xi )
10 i 1

ま た，e=e1 ＝ 2.718・・，-1 ≦ cosx ≦ 1 な こ とから，以下の不等式が成立することがわかる。

を示している。そして，10 個の良く知られたテスト関数を用いた実験により，集団の多様性を確保することが結果として最適解探索率 Ropt を向上させる
ことに繋がることを示した。

■ 8．結論と今後の課題
関数最小値探索問題を遺伝的アルゴリズムで解く

1 10e  exp(  cos(2xi ))10 i 1

場合に，集団の多様性を TDGA におけるエントロ

従って，F10 は正の値をとることがわかる。F10

ことにより，最適解探索率や探索解の精度を向上でが最小値 0 となるのは，両不等式にて等号が成立する場合であり，それは xi が 0 の場合であることきる」という仮説を，De Jong の 5 つの標準関数がわかる。各独立変数 xi の値の観測間隔は 32 × 2

準テスト関数を用いた実験により，定量的に検証し/2 =1 である。

た。集団の多様性を確保しながら効率的探索を実現

6

ピーで定量的に測定し，「集団の多様性を確保すると 5 つの多峰性関数を含む良く知られた 10 個の標する方法として，TDGA による手法が有効である
7-7

実験結果のまとめ10 個のテスト関数を用いた実験結果を最適解探
索効率 (Ropt) の観点から以下にまとめる。相対誤差

こと，そして広域探索を GA の二点交叉で実現し，局所探索を BLX-α で実現する手法が有効であることを実験により検証した。今後，（１）離散空間で(ER) の観点からの実験結果のまとめについては割解を近似する際の解の精度の向上策，（２）拡張遺愛する。

伝子交叉オペレータ交替法の有効性の検証，（３）最適解探索効率 (Ropt) の観点からの 8 つの GA モデ

広域探索を SPX，局所探索を BLX-αで実現する場

ルの評価

合の仮説の検証を今後の課題とする。

(1) Two-point crossover 法 :0.46 (=278/(15 × 10 × 4))
内訳 :

後書き
本論文は，以下の論文 [19] の邦訳である。

(a) Non-Scaling GA: 0.37 (=56/150)(b) Scaling Window GA: 0.34 (=51/150)(c) I m m u n e - G A w i t h s c a l i n g w i n d o w : 0 . 4(=60/150)

謝辞
本 研 究 は JSPS 科 研 費

JP15K00347 の助成を受けたものです。ここに感謝致します。

(d) TDGA with scaling window: 0.74 (=111/150)
各々の関数に関する上記の内訳は割愛する。
(2) Two-point crossover + BLX- α ( α =0.5) 法 :0.78 (=466/(15 × 10 × 4))
内訳 : 以下は表 1 の要約である。
(a) Non-Scaling GA: 0.73 (=110/150)(b) Scaling Window GA: 0.73 (=109/150)(c) Immune-GA with scaling window: 0.75 (=113/150)

【参照文献】[1] J. H. Holland, Adaptation in Natural and Artificial
Systems, MIT Press, 1992.
[2] E . A a r t s a n d J . K . L e n s t r a , L o c a l S e a r c h i n
Combinatorial Optimization, Princeton University
Press, 2003.
[3] D. E. Goldberg, Genetic Algorithms in Search,
Optimization, and Machine Learning, AddisonWesley Publishing Company, Inc., 1989.

NAIS Journal49

[4] M.-K. Tsai, J.-M. Yang, Y.-F. Tsai, and C.-Y. Kao, An
E v o l u t i o n a r y A l g o r i t h m f o r L a r g e Tr a v e l i n g
Salesman Problems, IEEE Transactions on Systems,
Man, and Cybernetics- Part B. Cybernetics., Vol. 34,
No.4, pp. 1718 – 1729 (2004)[5] K. A. De Jong, An Analysis of the Behavior of aClass of Genetic Adaptive Systems, Doctoral
Dissertation, University of Michigan, January 1975.
[6] R. L. Haupt and S. E. Haupt, Practical Genetic
Algorithms, John Wiley & Sons, Inc., 2004.
[7] R. Takahashi, Quantitative Evaluation of Iterative
Extended Changing Crossover Operators to Solve theTraveling Salesman Problem, in Proceedings of 2014
10th International Conference on Natural
Computation (ICNC), pp. 235-244, IEEE, 2014.
[8] K. Maekawa, N. Mori, H. Tamaki, H. Kita and Y.
Nishikawa, A Genetic Solution for the Traveling
Salesman Problem by means of a Thermodynamical
Selection Rule , Proceedings of the 1996 IEEE
International Conference on Evolutionary
Computation (ICEC'96), pp. 529-534, 1996.
[9] K. Mori, M. Tsukiyama, and T. Fukuda, Applicationof an Immune Algorithm to Multi-Optimization
Problem, T. IEE Japan, Vol.117-C, No.5, pp.593-598,
1997 (in Japanese).
[10] J. Lu and M. Xie: Immune-Genetic Algorithm for
Tr a v e l i n g S a l e s m a n P r o b l e m , T R AV E L I N G
SALESMAN PROBLEM, THEORY ANDAPPLICATIONS, Edited by Donald Davendra,
Published by InTech, pp. 81-96, 2010.
[11] L. J. Eshelman and J. D. Schaffer, Real Coded
Genetic Algorithms and Interval-Schemata,Foundations of Genetic Algorithms 2, pp. 187-202,
Morgan Kaufmann, 1993.
[12] M. Takahashi and H. Kita, A Crossover Operator
Using Independent Component Analysis for RealCoded Genetic Algorithms, Proceedings of the 2001
IEEE Congress on Evolutionary Computation Seoul,pp.643-649, 2001.
[13] S. Tsutsui, M. Yamamura, and T. Higuchi, Multiparent Recombination with Simplex Crossover inReal Coded Genetic Algorithms, Proceeding of
Genetic and Evolutionary Computation Conference,
pp.657-664, ACM, 1999.

50

NAIS Journal[14] H. Kita, Up-to-date Genetic algorithm to solve the
combinatorial optimization problem, Tutorial on
Information Processing based on Probabilistic
Algorithm, Workshop on SMAPIP, 2003 (in Japanese).
[15] T. Sato and M. Hagiwara, Bee System: Finding
Solution by a Concentrated Search, T. IEE Japan,
Vol.118-C, No.5, pp.721-726, 1998 (in Japanese).
[16] J. J . Gr efens t et t e, Op t i m i zat i on of C ont rol
Parameters for Genetic Algorithms, IEEE Trans. on
Systems, Man, and Cybernetics, vol.SMC-16, no.1,
pp.122-128, 1986.
[17] J. M. Dieterich and B. Harkte, Empirical Review ofStandard Benchmark Functions Using Evolutionary
Global Optimization, Applied Mathematics, Vol. 3,
pp. 1552-1564, 2012.
[18] X.-S. Yang, Test Problems in Optimization, in:Engineering Optimization: An Introduction with
Metaheuristic Applications (Eds. X.-S. Yang) , John
Wiley & Suns, 2010.
[19] R. Takahashi, Empirical Evaluation of Changing
Crossover Operators to Solve Function Optimization
Problems , Proceedings of the 2016 IEEE Symposium
Series on Computational Intelligence(IEEE SSCI2016), pp.1-10, DOI: 10.1109/SSCI.2016.7850141,2016.

◆著者紹介

髙橋

良

Ryouei Takahashi

京都情報大学院大学教授。
博士（工学）（早稲田大学）。
早稲田大学大学院理工学研究科修士課程修了（数学専攻）。
早稲田大学理工学部数学科卒業（理学士）。
元八戸工業大学大学院教授。
元 NTT 情報流通プラットフォーム研究所勤務。
元 NTT 横須賀電気通信研究所勤務。