˜A‘±SA‚É‚¨‚¯‚éŽOŠp•ª•z‚Ì“K—p

第52回 月例発表会（2002年8月） 知的システムデザイン研究室 連続SA における三角分布の適用 伏見 俊彦

1 前回からの課題

• 三角分布モデルの他のテスト関数への適用 • 新しい近傍並列モデルの考案

2 今月の研究内容

2.1 三角分布を用いた SA の性能検証 SAの生成処理に三角分布を用いたモデルと，従来の一 様分布を用いたモデルの２つのモデルに対して，Rastri-gin以外の４つの テスト関数（ Rosenbrock, Griewank, Ridge, Schwefel）に適用し比較を行った．数値実験の結 果を Fig. 1∼Fig. 4 に示す．それぞれのグラフは縦軸 にエネルギー値，横軸に比較項目を示している． 㪩㫆㫊㪼㫅㪹㫉㫆㪺㫂 㪈㪅㪇㪇㪜㪄㪇㪏 㪈㪅㪇㪇㪜㪄㪇㪎 㪈㪅㪇㪇㪜㪄㪇㪍 㪈㪅㪇㪇㪜㪄㪇㪌 㪈㪅㪇㪇㪜㪄㪇㪋 㪈㪅㪇㪇㪜㪄㪇㪊 㪈㪅㪇㪇㪜㪄㪇㪉 㪈㪅㪇㪇㪜㪄㪇㪈 㪈㪅㪇㪇㪜㪂㪇㪇 㪘㫍㪼㫉㪸㪾㪼 㪤㪼㪻㫀㪸㫅 㪙㪼㫊㫋 㪫㫉㫀㪸㫅㪾㫃㪼㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 㪥㫆㫉㫄㪸㫃㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 Fig. 1 Rosenbrock関数 (２次元) 㪞㫉㫀㪼㫂㫎㪸㫅㫂 㪈㪅㪇㪇㪜㪄㪇㪍 㪈㪅㪇㪇㪜㪄㪇㪌 㪈㪅㪇㪇㪜㪄㪇㪋 㪈㪅㪇㪇㪜㪄㪇㪊 㪈㪅㪇㪇㪜㪄㪇㪉 㪈㪅㪇㪇㪜㪄㪇㪈 㪈㪅㪇㪇㪜㪂㪇㪇 㪘㫍㪼㫉㪸㪾㪼 㪤㪼㪻㫀㪸㫅 㪙㪼㫊㫋 㪫㫉㫀㪸㫅㪾㫃㪼㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 㪥㫆㫉㫄㪸㫃㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 Fig. 2 Griewank関数 (２次元) 㪩㫀㪻㪾㪼 㪈㪅㪇㪇㪜㪄㪇㪍 㪈㪅㪇㪇㪜㪄㪇㪌 㪈㪅㪇㪇㪜㪄㪇㪋 㪈㪅㪇㪇㪜㪄㪇㪊 㪈㪅㪇㪇㪜㪄㪇㪉 㪈㪅㪇㪇㪜㪄㪇㪈 㪈㪅㪇㪇㪜㪂㪇㪇 㪘㫍㪼㫉㪸㪾㪼 㪤㪼㪻㫀㪸㫅 㪙㪼㫊㫋 㪫㫉㫀㪸㫅㪾㫃㪼㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 㪥㫆㫉㫄㪸㫃㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 Fig. 3 Ridge関数 (２次元) Fig. 1∼Fig. 4 より，すべてのテスト関数において三 角分布を用いたモデルが一様分布モデルよりも良好な結 果を示していることがわかる． 㪪㪺㪿㪼㪽㪼㫃 㪇㪅㪇㪜㪂㪇㪇 㪈㪅㪇㪜㪄㪇㪋 㪉㪅㪇㪜㪄㪇㪋 㪊㪅㪇㪜㪄㪇㪋 㪋㪅㪇㪜㪄㪇㪋 㪌㪅㪇㪜㪄㪇㪋 㪍㪅㪇㪜㪄㪇㪋 㪎㪅㪇㪜㪄㪇㪋 㪏㪅㪇㪜㪄㪇㪋 㪐㪅㪇㪜㪄㪇㪋 㪘㫍㪼㫉㪸㪾㪼 㪤㪼㪻㫀㪸㫅 㪙㪼㫊㫋 㪫㫉㫀㪸㫅㪾㫃㪼㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 㪥㫆㫉㫄㪸㫃㩷㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅 Fig. 4 Schefel関数 (２次元) 2.2 近傍並列モデルの考案 従来より研究されている SA の並列モデルとしては温 度並列 SA などが挙げられるが，連続問題における SA では近傍構造が非常に重要であることが分かっている． つまり，各々の対象問題において，最適な近傍構造を得 ることができれば良好な結果を得ることができると考え られる．以上の理由より，近傍を並列化する手法を導入 し ，新たな並列 SA モデルを構築する． Fig. 5に考案する近傍並列モデルを示す．考案するモ デルでは，初期段階において複数のプロセスに異なる近 傍を与え，探索が進むに従い，良好な解を得ているプロ セスの近傍を採用することにより，システムが自律的に 最適な近傍を得ることができる． ⹏ଔ୯ SA SA SA SA หᦼ SA SA SA SA หᦼ ᦨㆡߥㄭற ೋᦼߩㄭற ᜰᢙ⊛ߦಽ㈩ n1 n2 n3 n4 100% 10% ᰴ๟ᦼߩㄭற▸࿐ عGAߦࠃࠆᠲ૞ ع⹏ଔ୯ࠍ↪޿ߚㆬᛯ Fig. 5 考案する近傍並列モデル 良好な解を得ているプ ロセスの近傍採択方法につい ては検討中であるが，近傍に評価値を用いる方法，また GA操作を組み込む手法なども検討に入れて進めていく 予定である．

3 今後の課題

連続問題において三角分布を用いたモデルの有効性を 確認することができたので，今後は三角分布モデルを近 傍並列に実装し ，性能検証を行う． 1