自律系システム、適応系システム、調和系システムなどのインテリジェントシステムの設計構成において、ニューラルネットワーク、遺伝的アルゴリズムなどに代表される適応アルゴリズムの有効性がさまざまな研究成果により指摘されている。一方、生体系に内在するインテリジェントシステムである免疫系についての工学的応用に関する可能性及びその有効性は十分に議論されているとは言えない。

　本稿では,免疫システムの抗原の認識機構、抗体の記憶機構、抗原の排除機構に着目し, その工学問題に対する有効性を検討するために, マルチエージェントシステムに対する最適化問題の一例である分業巡回セールスマン問題(n-Traveling Salesman Problem; 以後, nTSP)へ適用し、アルゴリズムの性能、特徴について検討する。

　巡回セールスマン問題TSPはNP-hardに分類される問題の複雑さとその応用範囲の広さからさまざまな解法による検討がなされてきた。しかし今日の大規模複雑な工学的諸問題への対応には各エージェント間の協力による効率良く問題を解決を行なうマルチエージェントシステムなどのより強力な問題解決法が求められている。そこでTSPにおけるエージェント数をn人に拡張したnTSP問題を設定し、マルチエージェント型アルゴリズムの性能評価の基準問題として位置付ける。

　nTSPは本質的に各セールスマンに対する都市配分とその最短経路探索という2面性を持つ。これらの2面性は相互に関連しているため個別に逐次的に解くことが困難であるという特徴を持つ。免疫システムでは動的な環境に対する適応能力が期待されるためこの種の問題に対し有効な問題解決手法であると考えられる．

図１：nTSPの概念図

２.１　nTSPの定式化

　以下に本稿で使用する記号及び関数を説明する.

n	セールスマン数
m	都市数
dij	都市iから都市jへの距離
(xi, yi)	各都市位置の座標
Si	セールスマンi
PSi	セールスマンiのパス
Plank	1巡回計画

nTSPにおいて目的は各セールスマンのパス（都市を巡回する順序）の合計（コスト）を最小化するようなプランを作成することである。付随する制約条件は

• 各セールスマンのパスは出発都市(=最終都市)を同一とする.
• 出発都市を除く全ての都市は一人のセールスマンにのみ一度だけ訪問される。

  [目的関数]　min ( cost_k = Σf_d(P_Si) 　　　　　　(1)

式(１)で, P_SiはセールスマンS_iのパスで,出発都市と最終都市を除いたパスである. f_dはS_iの距離の総和を求める関数である.

[制約条件]　P_Si ∩ P_Sj = Φ, 　i ≠ j 　(∀ i, j)　(2)

式(２)はセールスマンiとjのパス上に都市の重複がないことを意味する制約条件である.

Plan_k =

ts	PS1	ts
ts	PS2	ts
：	：	：
ts	PSn	ts

式(３)の各行は各々のセールスマンのパスを表しているプランである. P_S1はセールスマンS₁のパスを意味する.

　免疫システムとは, 生体内に侵入する多種多様な未知の抗原に対応するために, 細胞遺伝子の再構築を行なって抗原に対応する抗体を産生し, 抗原を排除する生体監視防衛機構である.

図２：免疫システムの概念図

工学的応用の一例に森らによってモデル化された免疫アルゴリズム[1,2]がある。本稿ではそのアルゴリズムの基本構成に従う。

[Step 1] 抗原の認識

抗原を入力情報として認識する.

[Step 2] 初期抗体群の生成

記憶細胞から過去に有効であった抗体群を生成する.

[Step 3] 親和度の計算

抗原と抗体vの親和度ax_vと抗体vと抗体wの親和度ay_v,wを計算する.

[Step 4] 記憶細胞とサプレッサー細胞への分化

全ての抗体の濃度を計算し, 抗体vの濃度c_vが閾値Tcを越えた場合に, 抗体vを記憶細胞mに分化させる. また, 新しく分化した記憶細胞と同じ遺伝子を持つサプレッサー細胞sを分化させ, サプレッサー細胞との親和度が, 類似度の閾値以上の抗体を消滅させる.

[Step 5] 抗体産生の促進と抑制

次世代に残る抗体vの期待値e_vを計算し, 現世代の抗体の親和度の低いもののいくつかの抗体を消滅させる.

[Step 6] 抗体の産生

4で消滅させた抗体に変わる新しい抗体を, 乱数を用いてその遺伝子をランダムに決定することによって産生する. 以下, 世代があらかじめ設定した最終世代に達するまで3〜6を繰り返す.

　免疫アルゴリズムはその基本構成を(1)遺伝的アルゴリズムに基づく解の再構成(2)記憶細胞による有効解の記憶(3)サプレッサー細胞による記憶解の再探索の抑制とする。この構成によりGAの持つ強力な広域な探索能力に加え、有効解の再利用及び再探索の抑制による探索効率の上昇が期待される。以下に免疫アルゴリズムの処理手順とnTSPとの関係を示す(図３，図４)。

図３：免疫アルゴリズムの枠組み

図４：免疫アルゴリズムからみたnTSP

４.１　コーディング

　nTSPにIAを適用するためには, 問題の抗体を文字列表現しなければならない.

図５：nTSPの解のイメージ

図５は, 都市数m=10, セールスマン数n=3に置ける1プランの概念図を表している.

　1プランの情報を染色体（抗体）に記述する必要がある. GAによるTSPの一解法としてGrefenstetteによる順序表現[5]がある。nTSPでは抗体情報をnセールスマンに分割しなければならないためそのコーディング法に分割情報を加え拡張した。染色体に分割情報であるセパレータを加えたコーディング例が図６である。

図６：コーディング例

図６では、(1)各セールスマンのパス(P_Sn)とnセールスマンに分けるためのセパレータの位置を文字列表現し、(2)各セールスマンのパス部分（巡回経路部）を順序表現することでコーディングを施した例である。

４.２　各評価尺度の計算

　免疫アルゴリズムにおいては、適応度、類似度、濃度、期待値の4つの計算尺度を求める必要がある。以下にnTSPにおける評価尺度の計算式を定義する。

• 適応度　fitness_i = max_path - (work+penalty)

  max_path=fitness_iが負にならないような定数

  work = Σ f_d (P_Si)

  penalty = 巡回しないセールスマンに与えるpenalty定数

• 類似度　ay_v,w = (2つの抗体に共通する順路の都市数)/m
• 濃度　c_v = (類似度が閾値Tac1を越えた数)/pop_size
• 期待値　e_v = fitness_i × (1-ay_v,s) × (1-c_v)

  ay_v,s = 抗体vとサプレッサー細胞との類似度

５.１　実験1

　実験1では，nTSPに対しIAが有効に機能するかどうかを確認する．設定する問題は都市数12，セールスマン数4とし，都市配置は出発都市を中心に円周上に配置した．IAの各パラメータは以下のように設定した．

集団数	100
世代数	10000
記憶細胞の総数	50
サプレッサー細胞の総数	5
濃度の閾値	0.35
交叉確率	0.2
突然変異確率	0.02

また，遺伝子の再構成に使用するGAのオペレータは以下のように設定した．

• 交叉操作: 一点交叉
• 突然変異操作:
  • 巡回経路部: 遺伝子座_i=random(m-i-1)
  • セパレータ部: 遺伝子座_j=random(m-1)

図７は初期集団内のプランの一例であり，図８は8523世代後に得られた最適解である．

図７：初期集団内の一解

図８：IAにより得られた最適解

これらの図から，IAが適切なnTSPに対するプランを作成可能であると考えられる．この例ではセールスマンの巡回経路に対するサイズにばらつきが見られるが，これは適応度を最短経路条件のみとしたためであり，全セールスマンの負荷配分を均等にする必要がある場合には，この条件を適応度関数に加える必要がある．

５.２　実験2

　実験2では，IAの探索効率を評価するためにsimpleGAとの比較を行なった．比較に用いた問題はセールスマン数2，都市数10とし，ランダムな都市配置を30題用意した．また，GAの各パラメータは，以下のように設定した．各パラメータはIAのGA部と共通である．

初期集団	一定
集団数	50
交叉確率	0.2
突然変異確率	0.02

IAのパラメータ設定は，実験1と同様である．また，初期集団と記憶細胞に前問の最終世代の記憶を利用している．実験結果を図９に示す．

図９：GAとIAの効率比較

図９は，横軸に問題番号，縦軸に世代数をとり，boxがGA，lineがIAを示している．グラフから

[1]30題に対する準最適解探索までの世代数比較では，GA:IA=13:17でIAが優位である．

[2]各問題に要した世代数の総合計による比較では，GA=76695, IA=70515とIAが約6000世代分少ない．

ことが分かる．また，問題9，14では，IAがGAと比較して極めて早い世代で準最適解を獲得している．これはIAが過去に探索した候補解を記憶し，利用することで，類似性の高い問題に対して，効果的に準最適解を求めることができることによると考えられる．このことは，生体系における実際の免疫システムが一度記憶した抗原に対し適切に反応し，自己防衛を行なう行動様式に一致する．

　適応アルゴリズムの一手法である免疫アルゴリズムをnTSPへ適用し，その工学的応用に対する可能性について検討し，計算機実験によりその有効性について示した．特に，記憶機構を活用することで，動的環境における類似問題の繰り返し解決を必要とする課題に対して有効に機能すると考えられる．複数の問題解決器を基本とするマルチエージェント系の有効なアルゴリズムとしてのIAの利用が期待される．

[1]　森一之,築山誠,福田豊生,多様性を持つ免疫的アルゴリズムの提案と負荷割り当て問題への応用, T.IEE Japan,Vol.133-C, No.10, 1993.

[2]　森一之,築山誠,福田豊生,免疫アルゴリズムによる多峰性関数最適化,T.IEE Japan, Vol.117-C, No.5, 1997.

[3]　和田 健之介,和田 佳子,山登り飛び虫の進化と免疫システム論について,数理科学, NO.353, NOVEMBER, 1992

[4]　中村 友洋,角田 達彦,田中 英彦,分業セールスマン問題のニューラルネットワークによる解法, 人工知能 94-2, (1994, 6, 20)

[5]　J.Grefenstette, R.Gopal, B.J.Rosmaita and D.Van Gucht : Genetic Algorithms for the TravelingSales-man Problem,Proc. of ICGA '85, 16/168 (1985)