まとめ

は，行動時の参照相手を決定するときの距離計算である．CAPSOでは，3.1.3で述 べたように，各粒子が他の全粒子との距離計算を行う．そのため，距離計算の時間 が最も計算時間に影響するだけでなく，粒子数の増加は計算時間を大幅に増加させ ることになる．さらに，評価関数の計算は，3.2.1で決定した標準的なパラメータで は1度で新たな状態を2つ生成する可能性があり，既存のPSOより多少増加する．

しかしながら，既存のPSOは，gbestとlbestを用いた両モデルともに，粒子数と繰 り返し数を増加させるだけでは探索性能を向上させることが困難である．300次元 のRastrigin関数において，lbestモデルPSOの粒子数を500，繰り返し回数を5,000 に変更し，CAPSOと同じく約4分間計算を行った．その結果，30回試行して得ら れた最良解の評価値の平均は2146.431，最良値は1917.891まで改善された．しかし ながら，表3.4，3.5より，探索性能の大きな改善は行われておらず，CAPSOとの 差は大きいままであった．この結果より，CAPSOは，高次元，かつ複雑な問題に おいて，少ない粒子数で高い探索性能を発揮できると考えられる．したがって，問 題に応じた検証は必要であるが，少ない粒子数で有効な解を探索できる計算効率を 持つ手法の枠組みとしての有効性が期待される．

また，本章の実験より，CAPSOを実問題へ適用する際に，いくつか留意すべき 点も明らかとなった．まず，粒子の行動における距離計算の時間である．本章では，

手法の探索性能を中心に有効性を検証していたことから，全粒子間の距離を計算す ることとしていた．その結果，既存のPSOと比較して大幅な計算時間の増加を招く だけでなく，粒子数を増やすことが困難となっている．したがって，探索性能に対 する影響を考慮した計算時間の短縮を図る必要がある．次に，CAPSOの解探索は，

粒子群の収束と発散を考慮してパラメータを設定する必要がある．これは，GAや PSOと共通して問題に応じて検討が必要な課題である．本章で検討した標準的なパ ラメータは，大域探索を重視した設定である．そのため，適用問題によっては群の 収束を妨げる可能性があることから，さらなる検討が必要と考えられる．また，こ のようなパラメータの検討に加えて，粒子の行動ルールへ適用問題の知識を組み込 んだ有効性も必要である．CAPSOの拡張性や改良のしやすさは，粒子の行動ルー ルへ適用問題の知識を組み込む際に有効であると考えられる．したがって，問題に 応じた拡張も含めた有効性の検証を行っていく．

参考文献

[1] Glover, F. and Laguna, M.: TABU SEARCH, Kluwer Publishers, 1997.

[2] 安田恵一郎，神内宏幸，石亀篤司：近接最適性原理に基づく相互作用を用いた 組合わせ最適化手法，日本機械学会第8回最適化シンポジウム2008講演論文 集，pp.75-80，2008．

[3] 柳浦陸憲，茨木俊秀：組合せ最適化-メタ戦略を中心として-，朝倉書店，2001．

[4] Kennedy, J. and Eberhart, R.C.: Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks IV, pp.1942-1948, 1995.

[5] 安田恵一郎，石亀篤司：非線形計画アルゴリズム–実用的観点から．システム制 御情報学会誌，Vol.50，No.9，pp.14-19，2006．

[6] 筒井茂義：アントコロニー最適化手法，計測と制御，Vol.47，No.6，pp.466-472，

2008．

[7] Karaboga, D. and Alay, B.: A survey algorithms simulating bee swarm intelli-gence,Artif Intell Rev, DOI10.1007/s10462-009-9127-4, 2009.

[8] 相吉英太郎，安田恵一郎（編著）：メタヒューリスティクスと応用，電気学会，

オーム社，2007．

[9] 山口晃歓，岩崎信弘，安田恵一郎：最良解情報を用いた適応型Particle Swarm Optimization，電気学会論文誌C，Vol.126，No.2，pp.270-276，2006．

[10] 矢澤一行，田村健一，安田恵一郎，元木誠，石亀篤司：相互作用と適応化を考慮 したクラスタ構造型Particle Swarm Optimization，電気学会論文誌C，Vol.131，

No.5，pp.943-950，2011．

[11] 平岡創土，岡本卓，相吉英太郎：繰り返し型探索指針によるParticle Swarm Optimizationの改良，電気学会論文誌C，Vol.128，No.7，pp.1143-1153，2008．

[12] 石井良尚，岡本卓，相吉英太郎：大域的持続探索のための非同期世代交代型 Particle Swarm Optimization，電気学会論文誌C，Vol.131，No.3，pp.626-634，

2011．

[13] 村田秀樹，安田恵一郎，相吉英太郎：非線形散逸項を有するParticle Swarm Optimization法の提案，電気学会論文誌C，Vol.127，No.5，pp.787-792，2007．

[14] Shi, Y., Liu, H., Gao, L. and Zhang, G.: Cellular particle swarm optimization, Information Sciences, Vol.181, pp.4460-4493, 2011.

[15] 増田和明，栗原謙三：全体最良解更新状況に応じた探索特性調整機構をもたせた 新型Particle Swarm Optimizationモデル，電気学会論文誌C，Vol.130，No.4，

pp.573-579，2010．

[16] Wolpert, D. H. and Macready, W. G.: No Free Lunch Theorems for Search, Technical Report SFI-TR-95-02-010, Santa Fe, NM, 1995.

[17] Kobayashi, Y. and Aiyoshi, E.: Integer Value Combinatorial Optimization Al-gorithm Using Multi-Agent, SICE 2002. Proceedings of the 41st SICE Annual Conference, Vol.5, pp.3145-3150, 2002.

[18] Tanese, R.: Distributed Genetic Algorithms, Proc. 3rd International Confer-ence on Genetic Algorithms, pp.434-439, 1989.

[19] Manderick, B. and Spiessens, P.: Fine-Grained Parallel Genetic Algorithms, Proc. 3rd International Conference on Genetic Algorithms, pp.428-433, 1989.

[20] 矢口航太，田村健一，安田恵一郎，石亀篤司：近接最適性原理の定量的評価に 基づく組合せ最適化手法，電気学会論文誌C，Vol.133，No.6，pp.1218-1228，

2013．

[21] Wolfram, S.: Universality and Complexity in Cellular Automata, Phisica, Vol.10D, pp.1-35, 1984.

[22] Nakatsu, K., Furuta, H., Takahashi, K., Ishibashi, K. and Ando, K.: Multi-Agent Optimization Method Focused on Individual Evolution, 9th World

Congress on Structural and Multidisciplinary Optimization (WCSMO-9), CD-ROM, Shizuoka, Japan, 2011.

[23] Furuta, H., Nakatsu, K., Takahashi, K., Ishibashi, K. and Uchida, M.: An Efficient Optimal Restoration Scheduling Method of Damaged Lifeline Network Using Multi-Agent Optimization,Proceedings of the 25th KKCNN Symposium on Civil Engineering, pp.447-450, Busan, Korea, 2012.

[24] 加藤恭義，光成友奇，築山洋：セルオートマトン法−複雑系の自己組織化と超 並列処理−，森北出版株式会社，1998．

[25] 伊庭斉志：複雑系のシミュレーション−Swarmによるマルチエージェント・シ ステム−，コロナ社，2007．

[26] 高玉圭樹：マルチエージェント学習−相互作用の謎に迫る−，コロナ社，2003年．

第 4 ^{章 セルオートマトン} PSO ^の改良

本章では，提案手法であるセルオートマトンPSO（CAPSO）の実用性を高める ための改良について述べる．まず，3章の数値実験で述べた問題点とその解決方法 について述べる．次に，実問題への適用可能性を示すために，ナップサック問題へ

適用し，CAPSOの有効性を検証する．その際，CAPSOの問題点に対する改良を実

装した手法を用いて数値実験を行う．さらに，複数の制約条件を有する問題，およ び多目的最適化問題のテスト問題に対してCAPSOを適用し，様々な問題に対する 適用可能性を示す．