# 離散アルゴリズム特論2課題
20R4126:山崎一希

## 遺伝的アルゴリズムの基礎

### 遺伝的アルゴリズムの概観
遺伝的アルゴリズム（以下GA）：　ある範囲内で定義されている変数 $x$ の関数 $f(x)$ の最大値あるいは最小値を与える $x$ の値を、高速に求めるための最適化・探索アルゴリズムの一種
GAのアイデア：　遺伝子をもつ仮想的な生物の集団を計算機内に設定し、予め定めた環境に適応している個体が、子孫を残す確率が高くなるよう世代交代シミュレーションを実行し、遺伝子及び生物集団を進化させる

### 関数$f(x)$の最大値を検出するプログラム

main()
{
        int  x,  xmax,  max;
        int  x1=0, x2=255;
        xmax=x1;  max=f(xmax);
        for (x=x1+1; x<=x2; x++)
           if (f(x)>max) {
              xmax=x; max=f(xmax);
           }
}

### 全探索の計算不可能
- 高い精度　→　探索空間の増大 →　計算量の増大
- 実用上、解けない問題（NP困難な問題等）は多い
- 探索空間を効率よく探索し、実用上の最適解を速やかに発見する方法が必要
- ニューラルネットワーク、強化学習法、発見的探索法など様々な方法が提案されている
- ここでは、遺伝的アルゴリズムだけを取り上げる

### GAの基本的考え方
- 探索空間の複数個の探索点を同時に探索する
- 各探索点＝遺伝子をもつ仮想的な生物
- 各個体に対し環境との適応度が計算される
- 非常に高い適応度の個体を見つける

## 単純GAのアルゴリズム(SGA)
- 仮想生物と環境の設定
（１）染色体と遺伝子型の決定
個体の染色体を決定する。染色体は複数の遺伝子から構成される。
個々の個体の染色体の内部的表現を遺伝子型という。
0と1の並びであるビット列を用いる方式が多い
（２）表現型の設定
上記の遺伝子型をもつ各個体の実体に相当する表現型を決定する。
通常、表現型＝遺伝子型で十分
（３）環境との適応度の計算方法の決定
適応度（fitness）は、探索空間中の探索点を各個体と見なしたとき、その点における評価値に相当。
適応度は、各個体が生存の可能性という面からみて、どの程度優れているかを表す尺度である

### 単純GAの処理手順
手順１　初期生物集団の発生
手順２　各個体の適応度の計算
手順３　淘汰および増殖の実行
手順４　遺伝子型の交差の実行
手順５　突然変異の実行
手順６　生物集団の評価。評価基準を満たしている場合、終了する。満たしていない場合、手順２に戻る

#### 手順１　初期生物集団の発生
- 通常、初期の生物集団は乱数を用いてランダムに発生させる
- 探索空間になんらかの予備知識がある場合、評価値の高い部分を中心に生物集団を発生させる
- 例：　乱数の場合　
　　　　　$Gi = rnd(n)$, $n$は自然数

#### 手順2　各個体の適応度の計算
- 生物集団中の各個体の環境との適応度 $f(Ii)$ を、予め決めた計算方法に基づいて計算する

#### 手順3　淘汰および増殖の実行
- 各個体に対し、次世代に選択される確率は
$P(Ii) = f(Ii) / (f(I1) + f(I2) + … + f(In))$
- ルーレット方式：　適応度に比例した選択確率

#### 手順4　遺伝子型の交差の実行
- 生成された次世代の$ｎ$個の個体の中から、二つの個体のペアを$M$組だけランダムに選択し、それぞれに対し、交差（crossover）を実行する
- 交差が生じる確率を交差率（crossover rate）という
- 単純GAは1点交差を用いる。二つの個体の遺伝子型をランダムな位置で部分的に入れ替える操作

遺伝子型の1点交差の例
探索空間において、現在の探索点とは少し異なる位置に、新しい探索点を生成させることに相当

#### 手順５　突然変異の実行
- 突然変異（mutation）：　各個体の遺伝子に相当する各ビットを突然変異率の生起確率で、0を1、あるいは1を0に変更する操作
- 例：突然変異前：　　　0110 1110　⇒ 突然変異後：　　　0010 1111
- 探索の観点から見れば、現在の探索点から大きく離れた場所に探索点を発生させること
- 局所的な最適解にとらわれそうになったとき、そこから脱出する働き
- 突然変異率を大きくしすぎると、親の形質の遺伝特徴が失われ、ランダム探索になってしまう恐れ
- 通常、突然変異率は0.1 ～ 5% 程度

局所的最適解にとらわれる例

#### 手順６　生物集団の評価
- 生成された次世代の生物集団が進化シミュレーションを終了するための評価基準を満たしているかどうか、調べる。
- 代表的な評価基準
（１）生物集団中の最大の適応度があるしきい値より大きくなった
（２）生物集団全体の平均適応度があるしきい値より大きくなった
（３）世代交代回数に対する生物集団の適応度の増加率が、あるしきい値以下の世代が一定期間以上の長い間続いた
（４）世代交代の回数が、予め定めた回数に到達した

### 単純GAの特徴
- 単純GAは次の三つの基本操作
（１）生殖（reproduction）：　適応度に比例した個体の生存の可能性の決定
（２）交差（crossover）：　二つの個体の遺伝子の部分的な入れ替え
（３）突然変異（mutation）：　遺伝子のランダムな変更
- 実用上、探索困難な最適解も速やかに見つけることが多い
- 理論的な解釈が困難。パラメータの設定（生物集団の個体総数、交差率、突然変異率など）

## スキーマタ定理
- GAに関する理論的解析は非常に少ない
- スキーマタ定理　GAを体系化したJ.H. Holland によって提唱されたGAの基本定理
- 遺伝子型中の注目している遺伝子の並びが、進化シミュレーションにおいてどのような生存の確率をもつのかを求める指針
- スキーマタ（schemata, 単数形はschema）：アルファベットにdon’t care 記号 * を加えた文字列の集合
- 例　$S = *0011*01 = {00011001, 10011001, 00011101, 10011101}$
- スキーマタＳの次数（order） $O(S)$
$O(S) = (全長 L) – ( * の数)$
- スキーマタＳの構成長(defining length)$σ(S)$
$σ(S) = ( Sの最左と最右の非 * の記号間の距離)$
- 上記の例では、$O(S) = 6, σ(S) = 6$ である
- 交差と突然変異がなく個体総数Nが一定のときは、スキーマタ$Ｓ$の世代交代での平均増加率$Ｒ$は
$R = N * f(S) / {f(G1) + f(G2) + … + f(GN)}$
　　ただし、$f(S)$はスキーマタ$Ｓ$の中ですべてのスキーマタに対する適応度の平均
- 例：
$$
f(S) = {f(00011001) + f(10011001)
+ f(00011101) + f(10011101)}/4
$$

- 分母は個体全体の平均適応度を表している
- 交差によってスキーマタが分断される確率$R_c$
$Rc = Pc*σ(S)/(L-1), 0<= Pc <=1$, 交配率
時刻$t$ においてスキーマタ$Ｓ$に属する遺伝子型を持つ個体数の期待値を$P(S, t)$ とする
突然変異率が$Pm$のとき、スキーマタが突然変異しない確率は $(1-Pm) O(S)$ である
- 交差と突然変異は独立なので次式が成り立つ

$P(S, t+1)$
$>= P(S, t) f(S)/f’|1-Pcσ(S)/(L-1)| (1-Pm)^O(S)$
$～　P(S, t) f(S)/f’|1-Pcσ(S)/(L-1) – O(S)Pm|$
ただし、f’= {f(G1) +f(G2) + … +f(GN)}/N
$N$: 個体総数

- ここで、突然変異率$Pm$が１より十分小さいとして、$(1-Pm)^O(S)$をテイラー展開して2次の項以下を省略
- 不等号は、交差及び突然変異によって生じる他のスキーマタからの流入分などの高次項を省略した
- 遺伝的アルゴリズムの基本定理
- 構成長σ(S)が短く、次数O(S)が低く、平均適応度f’より高い適応度を示すスキーマタＳが次の世代で生き残る
- スキーマタ定理は、適応度が高い、短いスキーマが遺伝子型中に存在する場合、そのスキーマは交差によって分断される可能性が低く、世代交代につれてその数を増やしていくことを示している
- このようなスキーマを積み木（building block）と呼ぶ
- 積み木仮説：　進化シミュレーションにおいて、このような積み木が何種類も組み合わせることで高い適応度をもつ優れた個体が生成されるであろう

## 遺伝的アルゴリズムの拡張
- 淘汰・増殖の規則の拡張
　（１）個体の適応度の大きさの順位に応じて、次世代の個体として選択される可能性を予め決めて表にしておく方法。
　　例：　1位の確率0.4、2位の確率0.25、
　　　　　　3位の確率0.15、…
　（２）現在の世代において、適応度が最大の個体を必ず次世代に残す　→　エリート保存型戦略という
　（３）生物集団の一定の割合を淘汰する方式

### エリート保存型戦略

### 生物集団の一定の割合を淘汰する方式

### 遺伝的アルゴリズムの拡張
- 交差オペレータの拡張
（１）　2点交差（two-point crossover）
遺伝子の並びである遺伝子型を1列の記号列としてではなく、最後の記号と最初の記号が連結されたリング状にする。2点の交差位置をランダムに設定し、リングを２つのセグメントに分割する。各部分を入れ替えて、子孫の遺伝子の並びを生成する。
（２）　多点交差（multi-point crossover）
2点交差からの拡張である。2点交差と同様に遺伝子の並びをリングとして扱う。そして複数の位置でリングを分断する。交差位置の数が奇数の場合、親Ａと親Ｂのセグメントを交互に挟むことができないため、交差位置の数が偶数である必要。
（３）　セグメント交差（segmented crossover）
交差位置の総数を可変とする場合の多点交差である。セグメント交差では、セグメントの切り替え比率Rsを指定する。
例：$Rs=0.2$ のとき、任意のビットが部分的なセグメントの終わりのビットになる確率が0.2となる。
長さ$L$の遺伝子型に対し、切り替え比率Rsでセグメント交差を行う場合、セグメントの長さの期待値は$1/Rs$で、セグメントの個数の期待値は$RsL$である
（４）　一様交差（uniform crossover）
子孫の個体の各遺伝子が親Ａの対応する遺伝子になる確率 $p$ を予め決める交差オペレータ。そのとき、親Ｂの対応する遺伝子になる確率は$1-p$ である。
$p = 0.5$ の場合が多い
親A中のL個の遺伝子のうち、$p*L$ 個、及び親Bの$(1-p)*L$ 個の遺伝子が子孫に継承される。
例：　
$Ga = {11111111}, Gb = {00000000}$
$Gab = {10011100}$
（５）　シャッフル交差（shuffle crossover）
交差前の遺伝子型のビット列をランダムに並べ替えた後、交差を実行するオペレータ。
交差位置の数と無関係なため、1点交差、多点交差やセグメント交差などとの併用が可能
例：　ｎ点シャッフル交差（n-point shuffle crossover）
（６）　ブレンド交差（blended crossover）
個体の遺伝子型が連続値を表す場合、両親の値の中間の値を子孫の遺伝子型にする交差
例：　$親Aの遺伝子型Gaの値 = 255 = {11111111}$
$親Bの遺伝子型Gbの値 = 1 = {00000001}$
とすると、子孫の遺伝子型
$Gabの値 = (255 + 1)/2 = 128 = {10000000}$

- どの交差オペレータが適切であるか、GAを適用する問題、遺伝子型の定義、適応度の求め方などと密接に関連している
- 計算理論に基づいた解析が必要
- 特定な問題に対し、実験を重ねて試験錯誤的な経験蓄積は大事
- 突然変異規則の拡張
突然変異の役割が、交差によって生成される遺伝子型に多様性を持たせること
代表的な拡張は、突然変異率を可変にし、進化の進行状況に応じて変化する
例:　生物集団の進化が順調に進んでいる場合、通常の低い生起確率に抑えておく。一方、生物集団の適応度の増加率が減少し、局所解に陥ったと判断すれば、突然変異率を大きくし、脱出の可能性を上げる。

- 適応度のスケーリング（scaling）の導入
導入理由
　　（１）進化シミュレーションの開始時に、生物集団にはまだ明確な方向性がなく、ばらばらな分布をしているため、適応度の値に対して寛容あるいは鈍感な淘汰を行うことが望まれる。
　　（２）進化シミュレーションの収束時に、より優れたものだけを注意深く選択する局所探索が必要になるため、適応度の値に対して厳密な淘汰を行う必要
　→　進化シミュレーションの進行状況に応じて、適応度の値の解釈の仕方を変える必要
ある個体 $Ii$ に対して計算した適応度の値 $f(Ii)$ を、ある関数 $g(Ii)$ に代入して求めた値 $f’(Ii)$ を個体 $Ii$ の淘汰及び増殖の計算に用いること
　　　　　　　$f’(Ii) = g(f(Ii))$
　　　例　線形関数
　　　　　$f’(Ii) = a f(Ii) + b$, ただし、$a, b$ は定数
　　　　ベキ乗関数
　　　　 $f’(Ii) = f(Ii)^k$, ただし、$k$ は定数

線形スケーリングの例

## 単純GAのコーディング
* 単純GAのＣプログラミング言語による具体的な例を示す
* 単純GAを関数の最大値探索問題に適用し、その有効性を確認する
### 単純GAの基本ライブラリ
* マクロ及び変数の設定（パラメータ設定）

#define POP_SIZE 20   /* 個体総数 */
#define G_LENGTH 8    /* 遺伝子型の長さ */
#define C_RATE  0.6     /* 交差率（0～1） */
#define M_RATE  0.02   /* 突然変異率（0～1） */

* 各個体の遺伝子型を保存する変数として、次の2次元配列geneを用いる

unsigned char gene [POP_SIZE] [G_LENGTH];

ここで、`gene[i][j] : i+1番目（0<=i<=POP_SIZE-1）`の個体の遺伝
子型の、左からj+1番目（0<=j<=G_LENGTH-1）のビット
* 各個体の適応度を記憶する変数として、次の1次元配列fitnessを用いる

double fitness [POP_SIZE];

ここで、`fitness[i] : i+1番目（0<=i<=POP_SIZE-1）`の個体の適応度（通常0～1の実数）

* 単純GAの三つの基本操作：生殖、交差、突然変異
* 生殖オペレータ
　　ファイル名： `SGA_REPR.C (SGA Reproductionの略)`
　　含まれる関数： `sga_reproduction`
関数　`void sga_reproduction (gene, fitness, new_gene, new_fitness, pop_size, g_length)`
引数
　　`unsigned char *gene;` 現世代の個体の遺伝子型へのポインタ
　　`unsigned char *new_gene;` 次世代の個体の遺伝子型へのポインタ
　　`double *fitness;` 現世代の個体の適応度へのポインタ
　　`double *new_fitness;` 次世代の個体の適応度へのポインタ
　　`int pop_size, g_length;` 個体総数，個体の遺伝子型の長さ
　戻り値：　なし
　機能：　現世代の個体の遺伝子型とそれらの適応度をそれぞれ配列gene, fitnessに代入後，この関数を呼ぶと、新しい個体を選択した後、それらの個体の遺伝子型と適応度をそれぞれ配列new_gene, new_fitnessに代入する

使用例：

　#include”sga_repr.c”
  unsigned char gene[POP_SIZE] [G_LENGTH], 
                     new_gene[POP_SIZE] [G_LENGTH];
  double fitness[POP_SIZE], new_fitness[POP_SIZE];
   ………………………
  sga_reproduction (gene, fitness, new_gene, new_fitness, POP_SIZE, G_LENGTH);

注意：　適応度に関するソーティングは行っていない。また、乱数発生の関数によりルーレット方式を実現している

* SGA_REPR.Cのテストプログラム
ファイル名：　TST_SRPR.C　（test of sga reproductionの 略）
機能：関数sga_reproductionの動作確認
乱数の初期化には、randomize() を用いており、ヘッダtime.h を用いる

* 交差オペレータ
　ファイル名：　`SGA_CROS.C (SGA Crossoverの略)`
含まれる関数：　`sga_crossover`
　関数　`void sga_crossover (gene, pop_size, g_length, c_rate)`
　引数
　　　`unsigned char *gene;` 現世代の個体の遺伝子型へのポインタ
　　　`int pop_size, g_length;` 個体総数、個体の遺伝子型の長さ
　　 `double c_rate;` 交差率（0～1の実数）
　戻り値：　なし
　機能：　現世代の個体の遺伝子型geneに対する1点交差を実行し、新しい個体の遺伝子型に変更する。個体を個体番号0から順に二つずつペアにし、それぞれ1点交差させる。なお、交差させるかどうかは交差率で決定する
使用例：

　#include”sga_cros.c”
  unsigned char gene [POP_SIZE] [G_LENGTH];
   ………………………………
  sga_crossover (gene, POP_SIZE, G_LENGTH, C_RATE);

注意：　個体番号は適応度によるソーティングを行っていない。関数`sga_reproduction`を実行した直後のもの。
`sga_crossover` におけるペアの生成方法

* SGA_CROS.C のテストプログラム
　ファイル名：　TST_SCRS.C
　機能：　関数`sga_crossover` の動作確認
　実行結果例
* 突然変異オペレータ
　ファイル名　SGA_MUT.C
　含まれる関数　`sga_mutation`
　関数　`void sga_mutation (gene, pop_size, g_length, m_rate)`
　引数
　　`unsigned char *gene;`
`int pop_size, g_length;`
`double m_rate;`
　戻り値　なし
　機能：　現世代の個体の遺伝子型geneに対する突然変異を実行し、新しい個体の遺伝子型に変更する
　使用例：

　#include”sga_mut.c”
  unsigned char gene[POP_SIZE] [G_LENGTH];
  …………………………
  sga_mutation (gene, POP_SIZE, G_LENGTH, M_RATE);

注意：　この関数は`sga_crossover`を実行後、直ちに実行すること
* SGA_MUT.Cのテストプログラム
　　ファイル名　TST_SMUT.C
　　機能　関数sga_mutationの動作確認
* 実行結果の例

### その他の基本ライブラリ
* 遺伝子型の初期化オペレータ
　ファイル名　INIT_GEN.C
　含まれる関数　`initialize_gene`
　関数　`void initialize_gene (gene, pop_size, g_length)`
　引数：
　　`unsigned char *gene;`
`int pop_size, g_length;`
　戻り値：　なし
　機能：　生物集団中の各個体の遺伝子型geneの要素を乱数によって0または1に等確率で設定する
使用例：

　#include”init_gen.c”
  unsigned char gene [POP_SIZE] [G_LENGTH];
  ……………………………
  initialize_gene (gene, POP_SIZE, G_LENGTH);

乱数について、下記の二つの関数を用いた
　　`void randomize()`: 乱数発生ルーチンの初期化
　　`int random(n)`: 0～n-1の整数の乱数生成

### グラフィックスについて
* プログラムの実行経過及び実行結果の可視化
* グラフィックス関連の関数の使用
* 簡易グラフィックスライブラリの例：　
　　`#include”graphics.h”`
* 含まれる主な機能
　　g_init: グラフィックスの初期化、描画準備
　　g_pset: 点の描画
　　g_line: 直線の描画
　　g_circle: 円の描画
　　g_rectangle: 長方形の描画
　　g_cls: グラフィック画面の消去
　　g_text: グラフィック画面への文字表示
　　g_pget: 点の色の取得
* それぞれの関数の使い方

#### 関数： void g_init()
引数：　なし
戻り値：　なし
機能：　グラフィックスの初期化
使用例：　g_init();

#### 関数：　void g_line(x1, y1, x2, y2, col)
引数：　int x1, y1, x2, y2, col;
戻り値：　なし
機能：　グラフィック座標(x1, y1)と(x2, y2)を結ぶ直線を、パレット番号colの色で表示する
使用例：　g_line (0, 0, 100, 100, 3);

#### 関数：　void g_circle (cx, cy, rx, ry, col)
引数：　int cx, cy, rx, ry, col;
戻り値：　なし
機能：　グラフィック座標 (cx, cy) を中心とし、x方向半径 rx, y方向半径 ryとする円をパレット番号col の色で表示する
使用例：　g_circle (100, 100, 20, 30, 5);

#### 関数：　void g_rectangle (x1, y1, x2, y2, col, fill)
引数：　int x1, y1, x2, y2, col, fill;
戻り値：　なし
機能：　グラフィック座標 (x1, y1) を左上の点、(x2, y2) を右下の点とする矩形をパレット番号 col の色で表示する
fill=0 のとき、矩形の外郭線だけを描き、fill=1のとき、矩形の内部をcol色で塗りつぶす
使用例：　g_rectangle (0, 0, 200, 100, 5, 0);
　　　　　g_rectangle (100, 100, 300, 300, 6, 1);

#### 関数：　void g_cls ()
引数：　なし
戻り値：　なし
機能：　グラフィック画面を背景色で塗りつぶす
使用例：　g_cls ();

#### 関数：　void g_text (x, y, col, text)
引数：　int x, y, col;
　　　　char * text; 表示文字列へのポインタ
戻り値：　なし
機能：　グラフィック座標 (x, y) を左上の点として、文字配列 text 中の文字列を標準の大きさ、col 色で描く
使用例：

char text [100];
…………
text =“これは g_text のテストです。”;
g_text (100, 0, 15, text);

関数：　void int g_pget (x, y)
引数：　int x, y;
機能：　グラフィック座標 (x, y) の点の色 (0～15) を返す

int col;
…………
col = g_pget (100, 100);

* Ｃ言語による簡易グラフィックライブラリ
* ファイル名：　G_PKG.C
* 含まれる関数：　g_init, g_pset, g_line, g_circle, g_rectangle, g_cls, g_text, g_pget
* 動作確認のためのテスト結果

### 単純GAによる関数の最大値探索
* 関数生成ルーチン：　探索対象の関数を発生する
* ここで3つの関数形を発生する
* 探索用関数生成ルーチンNo. 1
　ファイル名： MAKE_F1.c
　含まれる関数：　make_function
　関数　void make_function (func, xmax)
　引数　double * func; 関数値の配列へのポインタ
　　　　　int xmax; 関数の変数の最大値（最小値０）
　戻り値　なし
　機能：　探索対象の関数の値(0.0～1.0)を代入する配列func[xmax] に関数値を代入する
　使用例：

　　#include “make_f1.c”
    #define XMAX 255
    double func [XMAX+1];
    …………
    make_function (func, XMAX);

注意：　xmax = 2^(G_Length) -1

* 探索用の関数生成ルーチンNo. 2
　ファイル名：　MAKE_F2.c
　含まれる関数：　make_function
　引数と機能はMAKE_F1.cと同様
* 探索用の関数生成ルーチンNo. 3
　ファイル名：　MAKE_F3.c
　含まれる関数：　make_function
　引数と機能はMAKE_F1.cと同様
* MAKE_F1.c : 放物線、MAKE_F2.c : 三つの三角関数の合成関数、MAKE_F3.c : 三角波状の関数
簡易グラフィックライブラリG_PKG.Cをインクルードして、関数生成の動作が確認できる
MAKE_F*.C のテストプログラム
　　ファイル名：　TST_MF.C
　　機能：　関数 make_function の動作確認
* グラフの表示ルーチン
　ファイル名：　G_GRPH.C
　含まれる関数：　g_draw_func,
g_init_grph,
g_plot_grph
#### 関数 void g_draw_func (func, xmax)
　引数：　double * func;
int xmax;
　戻り値：　なし
　機能：　探索対象のグラフ表示

#### グラフの表示ルーチン
　関数 void g_init_grph (func, xmax)
　引数：　double * func;
int xmax;
　戻り値：　なし
　機能：　画面及びグラフの初期化

#### 関数 void g_plot_grph (num, gene, fitness, pop_size, g_length, func, xmax, max_fit, m_f_old, avg_fit, a_f_old)
　引数：　省略
　戻り値：　なし
　機能：　世代交代に伴う、生物集団の最大適応度、平均適応度の推移のグラフの更新、生物集団の分布状態の表示などの処理を行う

* メインプログラム
　ファイル名：　SGA_1.C
　機能：　これまで紹介したライブラリ群を用いて、単純GAによる関数の最大値探索を行う。次の3つの関数が含まれる。
　int gene_to_pheno : 遺伝子型（ビット列）から表現型
　　　　　　　　　　　　　（座標）への変換
　void calc_fitness : 各個体の適応度の計算
　void generation : 世代交代の実行

* ユーザが指定すべきパラメータ
#include “make_f*.c”
#define POP_SIZE 15
#define G_LENGTH 8
#define C_RATE 0.2
#define M_RATE 0.02
世代交代を繰り返す回数を手入力で指定する。
実行結果例（F1）：
実行結果例（F2）：
実行結果例（F3）：
### 考察
* 関数の形状にそれほど影響を受けずに、単純GAによって関数の最大値が良好に探索されている
* 個体数や交差率、突然変異率などのパラメータの最適な値の検討は重要
* 今回の出力例は下記のパラメータになる
![](https://i.imgur.com/ktUbogy.png

### GAの実際の応用例
* GAは巡回セールスマン問題（TSP）、ナップザック問題などの組み合わせ最適化問題に適用する研究は多いが、計算理論の検証の意味合いが濃い
* ここで、工学分野での実際的な基礎的な応用例を紹介する。
　（１）　図形のパターンマッチング
　（２）　ニューラルネットワークの構造決定
　（３）　単純な人工生命
* これらの適用方法を参考にすれば、様々な応用問題に適用可能である

### 図形のパターンマッチング
* パターンマッチング：　図形の対応付けのこと
* 例えば、図の(a) に示す図形と相似な図形を(b)～(f)の中から探せ。（正解は(c)）
* 一般的に、図(a)に示すモデルの図形に相似な図形が、(b)の画像中のどこにあるかを決定せよ
* このような問題は人間にとっては容易だが、計算機にとって困難な場合が多い。時に瞬時に高精度の処理が必要な場合
* ２値相似図形の位置検出問題
２値モデル図形及びその図形に相似な図形を含む２値画像が与えられたとする。このとき、２値画像中のモデルに相似な図形の位置、大きさと回転角度を求めよ。
* GAを適用するため、問題の数学的な記述が必要
* モデル図形の表現
　　xy ２次元平面上のｎ個の点列P：
　　$P = { p1(x1, y1), p2(x2, y2), …, pn(xn, yn) }$
　　ただし、各点piの座標(xi, yi)は、Pの重心pcを原点とする相対座標

* モデル図形の相似図形の表現
　　モデルの重心pcをxy絶対座標の(xc, yc)に重ね、θだけ回転させてからM倍に拡大したときの点列$Q = { q1(s1, t1), q2(s2, t2), …, qn(sn, tn) }$とする。ただし、(sj, tj) は変換後の各点の絶対座標で
$sj = M (xj cosθ- yj sinθ) + xc$
$tj = M (xj sinθ+ yj cosθ) + yc$
マッチング度合の表現
　Qの各点が黒い点の個数をnbとすると、モデルと画像中の図形とのマッチング率$R = \frac{nb}{n}$で定義できる

* 図形のパターンマッチング問題の表現
モデルの点列Pと２値画像が与えられたとき、画像上に点列Pを様々な位置、大きさと回転角度で重ねて、マッチング率を求め、最大のRを与えるときの点列Pの重心pcの座標(xc, yc)、拡大倍率M、回転角度θを求める
* 最適化問題に同値
（定義域）４次元空間 (xc, yc, M, θ)において、（目的関数）マッチング率の最大値探索（最適化）問題

* GAの適用方法を考えよう
* 遺伝子型と表現型の設定
各個体Ik は遺伝子型Gkをもつものとする
$Gk = (xck, yck, Mk, θk)$
各個体Ik の表現型Hk はモデル図形の点列PをGkによって変換した後の図形
$Hk = {hk1(sk1, tk1), hk2(sk2, tk2), …, hkn(skn, tkn)}$
ただし、
$skj = Mk (xj cosθk – yj sinθk) + xck$
$tkj = Mk (xj sinθk + yj cosθk) + yck$

* 4次元探索空間の制約条件（簡単化のため）
　　xck = 0～63, （整数）
　　yck = 0～63, （整数）
　　Mk = 1
　　θk = 45*n, n = 0～7 （整数）
　　つまり、探索空間の大きさ
　　　　６４×６４×１×８＝２＾１５＝３２７６８
　　遺伝子型の長さ＝１５ビット
　Gk = 001…0 101…1 0…1
　　　　xck　yck　　θk

* 適応度の定義
各個体の環境への適応度はマッチング率を利用してもよいが、図形が少しずれただけで大きく変化する恐れ
この問題点の回避策として、現画像をぼかす処理を行う。現画像中の黒い点の明るさをLとし、白い点の明るさを0として、L段階に画像をぼかす（Lは整数の定数）

* 適応度の定義
$f(Ik) = Σj f(skj, tkj) / (L*n)$
* 遺伝オペレータの設定
ある世代の各個体の適応度を大きい順に並び替えた後、下位の一定の割合の個体を無条件に淘汰して消滅させる。そして、上位の個体からランダムに選んだ何組かのペアを２点交差させ、それぞれ２つの新しい個体を生成する。なお、個体総数を一定に保つ。
* コーディングについて
　（１）２点交差オペレータ
　　ファイル名：　two_cros.c
含まれる関数：　two_crossover
　　関数 void two_crossover (gene, g1, g2, g3, g4, g_length)
　　引数 unsigned char * gene; 現世代個体の遺伝子型へのポインタ
int g1, g2; 交差対象の２つの個体番号
　　 int g3, g4; 交差後の遺伝子代入の個体番号
　 int g_length;
　戻り値：　なし
　機能：　現世代の個体g1とg2の遺伝子に対する２点交差を実行後、得られた２つの遺伝子型を個体番号g3とg4の個体に代入する。
　（２） GAによるパターンマッチングのメインプログラム
　ファイル名：　Patmat.c
　機能：　これまでに述べた遺伝的方法で、三角形、四角形、円、不定形状の２値図形のパターンマッチングを行う。
* 実行例
　ユーザが指定すべきパラメータ

　　#define POP_SIZE  10　個体総数
    #define  S_RATE  0.4　　適応度下位の淘汰率
　　#define  M_RATE  0.01　突然変異率
　　#define  DEFOCUS_L  4　　現画像をぼかす段階数

　プログラムの処理過程は次の三段階
　　１）モデル図形の選択と生成
　　２）探索すべき原画像の作成
　　３）探索処理の実行

１）モデル図形の選択と生成
　　４種類の図形：　直角三角形、矩形、真円と楕円、不定形状
　　作成方法：　
　　直角三角形の直角な２辺の長さの比が乱数で設定。　
　　矩形の長辺と短辺の比率、また、真円と楕円の長半径と短半径の比率が、それぞれランダムに決定
不定形状は長さがランダムに変化する線分をある点を中心に３６０度回転させたとき、線分の端点が描く曲線として生成される
２）探索すべき原画像の作成
　　モデル図形の相似図形と、雑音としてのいくつかの直線と楕円、及び任意の雑音を加えることで原画像を作成
３）探索処理の実行
　　モデル図形と原画像中の相似図形との間のパターンマッチングのための探索処理を実行し、世代交代の回数を１２０回と固定。コンピュータの画面は次のように
構成される
実行結果例（モデル：直角三角形）
実行結果例（モデル：矩形）
実行結果例（モデル：楕円）
実行結果例（モデル：不定形状）
### 実行結果の考察
* ランダム探索は全く効果がない
* GAによる探索はいずれの図形に対しても効率よく探索ができたと言える
* GAの適用によって、形状にほとんど依存しない有効な探索が行える
* しかし、任意形状の相似図形の位置決定は図形の自由度が大きく、一般的に困難。
* GAの拡張や改良が必要
### 拡張版GAによるパターンマッチングの例
* すべてのパラメータが未知である相似図形
* １０回の実験結果を重ねて表示
* 世代交代１回あたりの探索点生成数は２０個
* １０回の実験のうち、７回において２５０世代以内で最適解に収束している
* 最良の場合の探索回数は　
２０×１４７＋５０（１回目）＝２９９０回

## 3.2　GAによるニューラルネットワークの構造決定
- 神経回路網の研究の歴史が古い
- 1957年、Rosenblattによってパーセプトロンモデルが提案
- 1980年代、Hopfieldモデル、Rumelhartらによる誤差逆伝播法など
- 神経細胞のモデル
- 入出力関数の例
　１）　しきい関数
　２）　シグモイド関数
- ユニットの接続方法
　１）　階層型ネットワーク
　２）　相互結合型ネットワーク
- GAの適用方法の分類
　１）　神経回路網の構造（接続方法の決定）
　２）　神経回路網の学習（重みの決定）
- 方法１：　構造を与えられ、GAで重みの学習
- 方法２：　構造も重みも、GAで学習
- 排他的論理和問題（XOR問題）への適用例
　〇　ニューロンの状態は単純しきい素子（０または１のみ）
　〇階層型のニューラルネットワーク
　　入力層、隠れ層、出力層で構成される。ニューロン　は入力層、隠れ層、出力層の順に通し番号が付けられる。番号が大きいニューランから小さいニューロンへの結合なし
　〇ニューロン間の重みは１、－１または０のいずれか
　〇各ニューロンの値を０に初期化
### 取り扱う神経回路網の例
### 神経回路網の結合状態を表す表
### 遺伝子型と表現型の設定
- 仮想生物＝神経回路網
- 遺伝子型＝神経回路網の重みの並び
- 前述の例では
　$Gi = {1 -1 0 0 1 -1 1 -1 0 1 -1 1 0 0 0 0 1 -1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 1}$
- 適応度の定義
$f(Ii) = m/n$
$m$ : 正解の回数
$n$ : 合計回数
### 遺伝オペレータの設定
- 現世代の個体群から、次世代の個体群を生成する方法として、適応度の下位一定の割合を淘汰し、上位の個体のペアの交差で子孫を作り個体総数を一定に保つ方法を採用
- 優秀な2つの個体から一様交差によって1つの子孫を生成
- 適応度上位の一定の割合の個体の中から親になる個体をランダムに選択
- 突然変異は子孫生成の際に1%～5%程度の低い生起確率で、遺伝子の1, -1, 0からそれぞれ別の要素にランダムに変更

### コーディングについて
- 一様交差オペレータ
ファイル名：　UNI_CROS.C
　関数　void uni_crossover (gene, g1, g2, g3, ratio1, g_length)
　引数　unsigned char * gene; 現世代の個体群
int g1, g2; 交差対象となる親の番号
　　　　　int g3; 交差後の遺伝子を代入すべき個体番号
　　　　　double ratio1; 各遺伝子に対する親g1の選択確率
　　　　　int g_length; 個体の遺伝子型のビット長
　戻り値：　なし
- 機能：　個体g1, g2の遺伝子型に対する一様交差を実行後、得られた一つの遺伝子型を個体番号g3の個体に代入する。この際に各遺伝子として、親g1の遺伝子を選択する確率をratio1で指定。親g2の遺伝子が選択される確率は1-ratio1になる。例： ratio1=0.5
- 動作確認のファイル　TST_UCRS.C （省略）
- GAによる神経回路網の構造決定のメインプログラム
　　ファイル名：　GA_NN.C
- 機能：　これまで述べた遺伝的方法を用いて、階層型神経回路網の構造設計を行う。

### 神経回路網の構造決定の実行例
- ユーザが指定すべきパラメータ

#define  POP_SIZE  25       個体総数
#define  S_RATE  0.4     適応度の下位淘汰率
#define  M_RATE  0.01   突然変異率

- 取り扱う問題：　排他的論理和（XOR問題）
- 対象とする入力―出力の組の総数：　４
- 入力層、中間層、出力層のニューロン数
　　入力層ニューロン＝２
　　中間層ニューロン＝５～１０
　　出力層ニューロン＝１
- 教師信号
　　{0, 0} → {0}, {0, 1} → {1}
{1, 0} → {1}, {1, 1} → {0}
- 画面の構成

## 3.3 単純な人工生命へのGAの応用

- 人工生命（Artificial Life: AL）
- 人工生命とは
- 厳密に定義することは困難であるが、進化を含めた生命現象を科学的にモデル化することを目的としている
- 人工生命の関連分野：　情報工学、電気・電子工学、制御工学、機械工学、生物学、遺伝学、医学、人間工学など、多岐にわたる
- 人工生命の研究テーマ
1. 生物の進化・遺伝のメカニズムのモデル化及び定式化
1. 生物進化のシミュレーションとその観察
1. 集団遺伝学のシミュレーションとその観察
1. 生物の免疫系や生殖系のモデル化
1. 進化の戦略とゲーム理論の計算論的考察
1. **環境適応型生物の情報工学的なモデル化**
1. 人工生物モデルの機械による実現とデモンストレーション
1. 脳機能の解明とそのハードウェアによる実現
1. 生体がもつ機能を実現するためのナノテク
- 人工生命の設定
1. 2次元平面上の矩形領域内に、生物1と生物2の2種類の人工生命がそれぞれ複数個存在する仮想世界
1. 生物1同士、あるいは生物2同士は交配し親の形質を受け継ぐ子孫を生成
1. 生物1と生物2両方とも、雌雄同体である。異なる種の生物の交配を禁止する
1. 生物は仮想世界中にランダムに生成される植物性食料、または他の生物の死骸である動物性食料を摂取することで生命を維持する。食料は両方の種の生物に共通
1. 個々の個体は内部エネルギーを持つ。食料摂取によって内部エネルギーが増加し、時間経過及び個体の移動や攻撃などの行動による運動に伴って減少する
1. 各個体の移動パターン、行動パターン、寿命その他の特質はそれぞれの遺伝子型で記述される
1. 内部エネルギーが0以下になった個体及び時間経過に伴って寿命が尽きた個体が消滅し、動物性食料に変化する
1. 植物性食料、動物性食料にも寿命に相当する有効時間の属性があり、時間経過に伴って有効時間を超えた食料は消滅する
- 人工生命が存在する仮想世界


- 仮想世界の状態変化
1. 生物1及び生物2に属する個体が、共通の食料の獲得を競合しながら、ある時は互いに攻撃し合う、あるときは交配して子孫を作ることで生物集団が時間的に変化していく
1. 仮想世界中の障害物の配置、食料の分布形状や量などを変化させながら世代交代シミュレーションを行う。どのような遺伝子型をもつ個体群が生成されるかを観察
- 個体 Ii の遺伝子型 Gi の定義
- Gi = Gi(SPi, SLi, VFi, TMi, CMi, LMi, CAi, CRi, SAi, DAi, LAi, EFi)
- 遺伝子Spi (Species number)：　種番号
- 値の範囲：0または1, ビット長：　1
- 意味：SPi = 0：生物1に属する生物, SPi = 1：生物2に属する生物
- 遺伝子SLi (Span of Life)：寿命
- 値の範囲：0～15, ビット長：　4
- 意味：寿命 = SL_MIN + SLi, SL_MIN: 寿命の最小値
- 遺伝子VFi (View Field)：視野

値の範囲：　0～3　　　　ビット長：　2
意味：　視野＝( 2 * (VFi + 1) + 1 )^2
　　　　　　　最小3×3、最大9×9
- 遺伝子TMi (Type of Movement)：　基本移動パターン
　　値の範囲：　0～3　　　　　ビット長：　2
　　意味：　TMi = 0, 1 ：　基本移動パターン1
　　　 TMi = 2 ：　基本移動パターン2
　　　 TMi = 3 ：　基本移動パターン3
- 遺伝子CMi (Characteristics of Movement)：　移動特性
　　ビット長：　3
　　意味：　指向指数（0：負、1：正）
　　第1ビット目：　同種の生物に対する指向
　　第2ビット目：　異種の生物に対する指向
　　第3ビット目：　食料に対する指向
- 遺伝子LMi (Loss by Movement)：　移動による消耗
値の範囲：　0または1　　　　ビット長：　1
　　意味：　消耗エネルギー　＝　LMi + 1
- 遺伝子CAi (Characteristics of Actions)：　行動特性
　　値の範囲：　0～7　　　　ビット長：　3
　　意味：　（攻撃、食料摂取、交配の優先順位）→
　　　CAi = 0, 1, 2 : (1, 2, 3), CAi = 3 : (1, 3, 2)
CAi = 4 : (2, 1, 3), CAi = 5 : (3, 1, 2)
CAi = 6 : (2, 3, 1), CAi = 7 : (3, 2, 1)
- 遺伝子CRi (Caprice Rate)：　気まぐれ率
　　値の範囲：　0～7　　　　　ビット長：　3
意味：　行動特性に従わない行動を行う確率
　　　　　　＝　CRi/7 × 100%
- 遺伝子SAi (Speed of Attack)：　攻撃速度
　　値の範囲：　0～7　　　　ビット長：　3
　　意味：　攻撃を行うスピードに関する定数
- 遺伝子DAi (Defensive Ability)：　防御力
　　値の範囲：　0～7　　　　ビット長：　3
　　意味：　敵からの攻撃に対する防御に関するパラメータ
- 遺伝子LAi (Loss by Attack)：　攻撃による消耗
　　値の範囲：　0～7　　　　　ビット長：　3
　　意味：　攻撃に伴う消耗エネルギーを求めるための定数
- 遺伝子EFi (Efficiency in eating Foods)：　食料摂取率
　　値の範囲：　0～15　　　　　ビット長：　4
　　意味：　食料摂取の際に得るエネルギーを計算するための定数
- 各個体 Ii は内部エネルギーEngy_i と年齢Age_iをもつ
- Engy_i = 0～100とし、個体出生時にはEngy_i =100とする。移動や攻撃に伴う運動によって値が減少し、食料摂取時に値が増加する。
- Age_i は時間経過に従って増加し、寿命を超えた場合は自然死したとみなし、動物食料に変更する。

### 世代交代シミュレーションの実行方法

1. 仮想世界における障害物の位置、植物性食料の時間に対する発生数（例：時間当たり一定量でランダム発生）などの設定を行う。
2. 初期個体群の遺伝子型を設定する（例：どんなビット列でも解釈不能な致死遺伝子にはならないため、ランダムに生成してもよい）。また、各個体の内部エネルギーEngy_i を70～99の値にランダムに設定し、年齢Age_i を0～SL_MIN-1 の値にランダムに設定する。
3. 生物1と生物2に属するすべての個体に対しランダムに通し番号をつけ、I_1 ～ I_N とする。Nは各世代における生物総数で世代交代につれて変化する。
4. 通し番号の順に次の2通りのいずれかとして、各個体の状態を変化させる。
- 移動：個体の位置を現在の位置から別の位置へ変化させる。
- 行動：次のいずれかを選択し実行させる
- 攻撃：別の個体に対する攻撃を行う
- 食料摂取：食料を摂取する
- 交配：同種の個体とともに子孫を生成する
- 注：個体の行動影響範囲内に別の個体や食料が存在しない場合、移動を選択する。それ以外の場合、行動を選択する。
5. 各個体の年齢Age_i を1だけ増加させ、その個体の寿命（= SL_MIN + SLi）を超えた場合消滅させる。
6. 各食料の新鮮度の値Frsh_i を1だけ増加させ、使用制限時間TL1またはTL2を超えた場合は消滅させる。
7. 世代数を1だけ増加する。予め指定された回数を超えた場合、または個体がすべて消滅した場合には処理を終了する。それ以外の場合は手順3に戻る。

### 個体の移動および行動の詳細

- (a) 個体の移動
- 個体の行動影響範囲内に他の個体または食料が存在しないとき、移動させる
- 各個体には図のように正方形状の視野があり、視野内の個体、食料、障害物の分布状態を知ることができる。視野の正方形の辺長は 2 (VFi + 1) + 1 である。
- 各個体は視野内の分布と自分自身の移動特性（CMi: 個体および食料に対する好み）に従って移動を決定する。
- 視野内の分布と移動特性が与えられたとき、移動方向を決定できる。そのために各個体を原点とする xy 座標系を作成する。
- 視野内に同種の生物Si(sx_i, sy_i) がNs個、異種の生物Dj(dx_j, dy_j)がNd 個、食料Fk(fx_k, fy_k)がNf 個、それぞれに対する移動特性が(sgn_1, sgn_2, sgn_3)とする。
- Sgn_m = -1 または 1。
- 次式で計算される座標を (x_t, y_t) を移動目標地点の座標にする。
- 
- 図に示す8方向のベクトルV1～V8の中で、ベクトルV(x_t, y_t)に最も近い角度のベクトルを選択し、個体の現在の座標をそのベクトルの終点に移動する。
- その個体の内部エネルギーEngy_i から(LMi + 1)だけを減じる。
- 
- 個体の視野内に他の個体または食料が何もない場合、その個体の基本移動パターンに従って行動する。基本移動パターンは下記の3種類がある
1. 基本移動パターン１（8方向ランダムウオーク）
1. 基本移動パターン２（上下左右4方向ランダムウオーク）
1. 基本移動パターン３（斜め4方向ランダムウオーク）
- 
- (b) 個体の行動
- 各個体の行動影響範囲内に他の個体または食料が存在する場合、個体を行動させる。その具体的な方法を紹介する
- 行動は攻撃、食料摂取、交配の3種で、その必要条件：
1. 攻撃：　行動影響範囲内に同種または異種の個体一つ以上存在
1. 食料摂取：　行動影響範囲内に食料が一つ以上存在
1. 交配：　行動影響範囲内に同種の個体が一つ以上存在
- 行動可能な候補は複数ある場合、個体の遺伝子 CAi （優先順位）によって決定される基本行動順位に従い行動選択
- 選択した行動で対象が複数存在するとき、その中の一つをランダムに選択
1. 攻撃：注目する個体 Ii が別の個体 Ij に攻撃を行ったとする。個体 Ii のAttack_i 量を計算する
- Engy_i (t) + SAi × 20/7 × rnd + DAi × 20/7 × rnd
- ただし　Engy_i (t) : 個体 Ii の内部エネルギー
- SAi : 攻撃速度を表す定数（0～7）
- DAi : 防御力を表す定数（0～7）
- rnd : 0～1の乱数
- 個体 Ij に対しても同様に Attack_j を計算し、Attack 量の大きい個体を勝者とする。個体 Ii を勝者とする場合、下記のように内部エネルギーを更新させる
- Engy_i (t+1) = Engy_i (t) – LAi * rnd
- Engy_j (t+1) = Engy_j (t) – 40 – LAj * rnd
- ただし、LAはそれぞれ個体の攻撃による消耗エネルギー
2. 食料摂取
- 注目個体 Ii の内部エネルギーは次のように増加させる。
- Engy_i (t+1) = Engy_i (t) + 40×(50 + EFi×50/15)/100
- ただし、EFi は個体 Ii の食料摂取効率（0～15）
- Engy_i (t+1) > 100 のとき、Engy_i (t+1) = 100 とする
3. 交配
- 注目個体 Ii が同種の個体 Ij と交配する場合、各自の内部エネルギー Engy_i, Engy_j をそれぞれ５だけ減少し、子孫の個体1個を作る。
- 子孫を発生させる位置は、親の行動影響範囲の論理和の領域内の1点とし、ランダムに選択。子孫の遺伝子型は親の個体の一様交差で決定する。子孫の内部エネルギーを100にする。また、子孫の遺伝子型の種番号SPi 以外の各遺伝子に対し低い生起確率で突然変異を行う。
- 
- GAによる人工生命のプログラム
- これまで紹介された設定に従い、基礎的な人工生命のシミュレーションを行うGAのプログラム
1. メインプログラム
- ファイル名： AL_GA.C
- 機能：これまで紹介した各種ライブラリをインクルードし、基礎的な人工生命のシミュレーションを行う
2. 仮想世界の設定ファイル
- メインプログラムを実行すると、仮想世界をランダムに作成するか、または予め作成した設定ファイルを読み込むかを尋ねてくる。
- 前者を選択する場合、生物１、生物２、食料、障害物がすべてランダムに矩形の仮想世界内に配置。実行ごとに異なる設定になる
- 後者を選択する場合、次のように予め仮想世界の設定ファイルを用意しなければならない
- 仮想世界の設定ファイル（テキスト型）
- 1番目のデータ：　仮想世界の横方向 (x) の大きさ wx
- 2番目のデータ：　仮想世界の縦方向 (y) の大きさ wy
- 3番目以降の wx×wy 個のデータ：　各 xy 座標における属性 P(x, y) （0～4の整数）
- 0：何も存在しない点
- 1：生物１が存在する点
- 2：生物２が存在する点
- 3：植物性食料が存在する点
- 4：障害物が存在する点
- 各データは空白、カンマ、改行のいずれかで区切る必要がある
- 
- 仮想世界を表す設定ファイルの内容
- 
- 人工生命のシミュレーションの実行例
- シミュレーションの画面構成
- 
- 左上：突然変異などのパラメータ
- 左下：現在の生物１と生物２の代表的な遺伝子型
- 右上：仮想世界の状態、生物１は◇、生物２は□、植物性食料は△、動物性食料は▲、障害物は■
- 右下：世代交代に伴う生物１と生物２の個体数
- 画面表示の例
- 
- 世代交代に伴う画面表示の推移の例
- 次のような遺伝子をもつ個体が優秀であると考えられる
- 寿命 SLi : 大　　　　　　　　　視野 VFi : 大
- 基本移動パターン TMi : １
- 移動特性 CMi : （1, 1, 1）　　運動による消耗 LMi : 0
- 行動特性 CAi : ０～２　　　　気まぐれ率 CRi : 小
- 攻撃速度 SAi : 大　　　　　　防御力 DAi : 大
- 攻撃による消耗 LAi : 小　　食料摂取効率 EFi : 大
- 
- 
- 
- 
- 
- 

## GAによる巡回セールスマン問題への応用

- 巡回セールスマン問題とは、定められた都市をすべて1回だけ訪れる最短のコースを求める
- GAを用いる場合、交差方法を工夫する必要はある
- 例：6都市のケースで、遺伝子型を都市の訪問順序とする
- CBDFAE : C→B→D→F→A→Eの順に訪問
- 1点交差で行う場合
- 親1： CBDF | AE →　子1：　CBDF | EC
- 親2： ADFB | EC　→　子2：　ADFB | AE 致死遺伝子
- 工夫された交差法
1. 順序表現（コーディングによる方法）
- 最初に都市をアルファベット順に並べた都市リストを作成する。次に、訪問順に並んだ都市がアルファベット順に並んだ都市リストの左から何番目にあるか調べて、その数字に置き換える。そして、都市リストからその都市を取り除く。この操作を繰り返す。
- 例：　最初に、都市をアルファベット順に並べる都市リスト　 ABCDEF (訪問順序：123456)

前述の親1　CBDFAE をコーディングしよう。

親1　　 都市リスト　　　     
CBDFAE ABCDEF 
3BDFAE ABDEF  
32DFAE ADEF 
322FAE AEF
3223AE AE
32231E E
322311 空

同様に、前述の親2をコーディングすると

親2　　 都市リスト    
ADFBEC ABCDEF 
1DFBEC BCDEF
13FBEC BCEF
134BEC BCE
1341EC CE
13412C C
134121 空

コーディングした後の親1と親2に対し、1点交差を行う

親1：　3223 | 11   →　子1：　3223 | 21
親2：　1341 | 21　 →  子2：　1341 | 11

子１と子２に対し、アルファベット表現に復元する

子1　　 都市リスト
322321 ABCDEF
C22321 ABDEF
CB2321 ADEF
CBD321 AEF
CBDF21 AE
CBDFEA 空

同様に、子２も下記のように復元できる
　 　子２：　134111 →　ADFBCE
致死遺伝子がなくなることがわかる。
　（２）部分一致交差（交差法による方法）
　　①　２つの個体において交差させる部分を決める。
　　②　対応するシンボルの組を作る。
　　③　2つの個体において、対応するシンボル同士を交換する。
- 

---

## GAの今後の展望

- GAの理論の確立
- だまし問題（局所解が多数存在）に対して、GAはあまり有効でない
- GAによって、どのような過程で、どのような原理に従って実用解が得られるか、どのようにすれば探索の効率が上がり、どのような問題に適用困難なのか
- GAの探索のメカニズムと効率の解明が重要
- 積木仮説は仮説であり、理論的に証明されていない
- 単純GAのスキーマタ定理があるが、拡張したGAは成立されない
- GAの応用例の蓄積
- 神経回路網の応用例の蓄積で、その有効性が広く認知されている
- GAも同様に、組み合わせ最適化問題や関数の最大値探索問題のほかに、ここで紹介した画像処理、ニューラルネットワーク、人工生命など、魅力ある応用あるいはデモンストレーションがもっと必要
- GAの応用分野とその例
- 設計問題
- VLSIのレイアウト設計
- コンピュータにおけるキャッシュシステム設計
- 通信ネットワーク
- エンジン設計
- IC設計
- デジタルフィルタ設計
- 形状設計
- ファジイ制御器設計
- スケジューリング問題
- 従業員とその仕事割り当て
- タスク割り当て（マルチプロセッサコンピュータ）
- ジョブショップスケジューリング　など
- 組み合わせ最適化問題
- ナップザック問題
- 自動車の経路最適化
- 巡回セールスマン問題
- 遺伝子情報解析
- 制御問題
- プロセス制御
- ロボット制御
- その他
- 遺伝的プログラミング（プログラムの自動生成）
- 画像復元
- 目標物検出
- システム同定
- タンパク質の構造推定、データベース検索、作曲など
- GAと従来手法との結合の検討
- GAは欠点もあり、過信するのが誤り
- GAの長所と短所をよく見極め、場合に応じて従来の手法と使い分ける柔軟な姿勢が大事
- GAの最適化
- GAのパラメータの数が多く、適切に決定する有効な方法論は存在しない
- GAのパラメータの最適な組を、１段上のレベルのGAで決定する　→　メタGAの考え方（非効率的、本質的な議論ではない）
- GAの高速化
- GAによる探索は、問題によっては長い計算時間が必要
- →　GAの計算時間の短縮を図る必要
- GAの処理を高速化するために、専用のハードウェア開発
- 並列計算機の適用
- 非ダーウィン進化説に基づくGA
- ダーウィン進化説は自然淘汰原理を基盤としている
- ダーウィン進化説以外の考え方を取り入れる可能
- 非GA的最適化手法の検討
- GAがあらゆる最適化手法の中で最良であると理論的に証明されていない
- 非GA的な方法による最適化の理論と応用への検討
- GA、非GAに捉われず、進化的な最適化あるいは探索の手法について、今後も検討を続ける必要