著者

飯村 伊智郎 伊藤 登志也 中山 茂

出版者

一般社団法人 システム制御情報学会

雑誌

システム制御情報学会論文誌 (ISSN:13425668)

巻号頁・発行日

vol.19, no.2, pp.84-86, 2006-02-15

参考文献数

5

被引用文献数

1

著者

飯村 伊智郎 池端 伸哉 中山 茂

出版者

情報知識学会

雑誌

情報知識学会誌 (ISSN:09171436)

巻号頁・発行日

vol.13, no.2, pp.1-17, 2003

参考文献数

17

被引用文献数

8 3

---

遺伝的アルゴリズム(genetic algorithm : GA)には,集団内で同じ個体が急増するなどして,集団の多様性が失われてしまう過剰収束という好ましくない現象が生じ得る.一旦過剰収束が起こると交叉はその機能を失い,GAによる探索が殆ど意味のないものになってしまう.この過剰収束を回避して多様性を維持することが,GAを適用する際の重要なポイントとなる.本論文では,まず,並列GAの実装形態として,柔軟な分散並列処理の構築を提供し得るオブジェクト共有空間を用いた実装を提案する.次に,できる限り単純な仕組みで過剰収束を回避する手法として,並列GAにおけるノアの箱舟戦略を提案し実験によりその有用性を明らかにする.この手法は,進化の停滞した部分集団の個体の殆どを探索解空間から新たに迎え入れた個体群と入れ換えるものであり,非同期に均質個体を淘汰し集団の多様性減少に制限をかけることで過剰収束を回避する.

著者

飯村 伊智郎 松留 貴文 中西 達哉 中山 茂

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:09151915)

巻号頁・発行日

vol.J88-D1, no.4, pp.900-905, 2005-04-01

---

ランダム選択機構を有する AS rank( AS rankRS)の各アリであるマルチエージェントに対して,非一様な個性を導入し,フェロモン情報に対する追従性に優劣をもたせたACOとして AS indi を提案する.51都市配置のeil51. tspを用いた実験に対してのみ調べたものであるが,この AS indi は,従来の AS rankRS で期待できなかった最短な平均巡回路長と最多な最適解発見回数を同一のパラメータ値(エージェント数)で満足させ得ることが明らかになった.

著者

中山 茂 飯村 伊智郎 松尾 翠 前薗 正宜

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.47, no.8, pp.2625-2635, 2006-08-15

参考文献数

21

被引用文献数

5

---

量子コンピュータは,量子重ね合わせ状態や量子干渉効果,量子もつれ状態などの量子力学的原理を利用した計算モデルである.量子もつれ状態は,従来の古典的コンピュータでは実現しにくいものであるが,量子重ね合わせ状態や量子干渉効果は既存のアルゴリズムでも容易に取り入れることができる考え方である.この量子計算アルゴリズムなどに応用されている量子系の干渉効果を模擬した干渉交叉と呼ばれる手法を従来の遺伝的アルゴリズム(古典的GA)の遺伝的オペレータに組み込んだ量子風遺伝的アルゴリズム(量子風GA)に関する研究が,Narayanan らによって比較的都市数の少ない巡回セールスマン問題に対して行われ,古典的GA と比較してより少ない世代数で最適解の探索に成功している.そこで,本論文では,従来の研究よりもより問題規模の大きいTSPLIB の5 つの都市配置を対象として,干渉交叉の対象となる親個体の選択法や局所探索を新たに導入し詳細に実験を行い,古典的GA と量子風GA とを比較検討した.その結果,量子風GA は,最適解発見率および平均探索世代数の観点で,古典的GA に比べ優れた性能を有することが,対象とした5 つの都市配置に関して分かった.さらに,局所的な探索改善を目的とする2-Opt 法には,量子風GA の特徴である干渉交叉による探索世代数の削減効果をさらに向上させる効果があることが分かった.Quantum computer is a computation model using quantum mechanical principle such as quantum superposition state, quantum interference effect and quantum entanglement state. Quantum entanglement state is not achieved easily with conventional classical computers. However, quantum superposition state and quantum interference effect are an idea that can be easily adapted even by conventional algorithms. Quantum-inspired genetic algorithm (quantum-inspired GA) was proposed by Narayanan, et al. The quantum-inspired GA is a new GA having a technique called "interference crossover" (IX), which imitates quantum interference effect, embedded in genetic operators of a conventional GA (classical GA). The quantum-inspired GA succeeded in the search for an optimal solution in a less number of generations compared with the classical GA in the case that the number of cities of a TSP is comparatively little. In this paper, we have made comparative study of a classical GA and a quantum-inspired GA by considering selection methods of parent individuals for the IX, a local search, and experimenting in detail on five problems of TSPLIB, which are larger scale than a problem used in a previous study. As a result, we have confirmed in the five TSPs that search ability of the quantum-inspired GA is superior to the classical GA in the viewpoints of "discovery rate of the optimal solution" and "average number of generations for search". Furthermore, it should be noted that 2-Opt method improves the reduction effect of "average number of generations for search" of the quantum-inspired GA.

著者

飯村 伊智郎 伊藤 登志也 濱口 孝治 中山 茂

出版者

The Society of Instrument and Control Engineers

雑誌

計測自動制御学会論文集 (ISSN:04534654)

巻号頁・発行日

vol.41, no.9, pp.772-774, 2005

被引用文献数

2

---

This paper proposes a distributed parallel processing of Queen Ant Strategy named "AS_queen" which imitated an ant society which a queen ant governs. It is noted that the proposed processing method satisfies "shortening of average time for search" and "improvement of searching ability" at the same time in the seventy-six cities' configuration of TSPLIB.

著者

池水 孝幸 小野 智司 森重 綾太 中山 茂 飯村 伊智郎

出版者

Japan Society for Fuzzy Theory and Intelligent Informatics

雑誌

知能と情報 (ISSN:13477986)

巻号頁・発行日

vol.22, no.6, pp.804-817, 2010

---

アントコロニー最適化法(ACO)は,蟻の群による採餌行動を模擬したメタヒューリスティクスであり,巡回セールスマン問題,スケジューリング問題など多くの組合せ最適化問題でその有効性が確認されている.近年,0-1整数計画問題(0-1IP)にACOを適用するBinary Ant Colony Optimization(BACO)と呼ばれる方式が提案されている.BACOではACOと同様,探索領域の集中化,多様化を調整する方式を採り入れることで探索性能の改善が期待できるものの,これまでの研究では,集中化,多様化を積極的に調整するBACOが提案されていない.本研究では,女王蟻戦略AS<SUB>queen</SUB>をBACOに組み入れたBAS<SUB>queen</SUB>を提案する.BAS<SUB>queen</SUB>は,グループ化された働き蟻の集団により多様な探索を行い,女王蟻が働き蟻に指令を送ることで探索領域の多様化,集中化を調整するため品質の高い解の発見が期待できる.0-1ナップザック問題を対象として実験を行い,提案するBAS<SUB>queen</SUB>が,他のBACOアルゴリズム,焼き鈍し法,粒子群最適化法などよりも高い探索性能を示すことを確認した.

著者

中山 茂 前薗 正宜 飯村 伊智郎 小野 智司

出版者

一般社団法人 システム制御情報学会

雑誌

システム制御情報学会論文誌 (ISSN:13425668)

巻号頁・発行日

vol.20, no.11, pp.454-456, 2007-11-15 (Released:2011-10-13)

参考文献数

6

被引用文献数

1

著者

飯村 伊智郎 中山 茂

出版者

一般社団法人 システム制御情報学会

雑誌

システム制御情報学会論文誌 (ISSN:13425668)

巻号頁・発行日

vol.24, no.4, pp.97-99, 2011 (Released:2011-07-15)

参考文献数

6

被引用文献数

3 6

著者

飯村 伊智郎 加藤誠巳

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.35, no.12, pp.2831-2841, 1994-12-15

被引用文献数

6 2

---

近年車載ナビゲーション・システムの普及が著しいが、目的地までの最適経路を提供するものは少ない。最適経路を算出するためには道路ネットワーク・データを必要とするが、例えば(財)日本デジタル遺路地図協会の作成した目本全国の基本遺路は約23万個のノード、約52万本のリンクより成り、その経路探索用データのデータ容量は約8MBと大きく、ディスクヘのアクセス・読み込み時間、探索を実行するために必要なRAM領域,ならびにCPU時間が増大し、実用に耐えなくなることがある。従来からこれらの問題点を解決するためいくつかの方法が提案されているが、種々の問題点があった。本論文では日本全国の道路ネットワークを復数個の領域に分割し、任意の2つの領域間の最適経路を算出するために必要にして十分な領域の集合をオフラインで算出してテーブル化することにより上述の問題点を解決している。このようなルックアップ・テーブルを用いることそれ自体は審易に考え得るところであるが、本論文ではこれを日本全国の道路網に対し実際に適用した場合について、実用的な領域分割数を明らかにすると共に、領域分割の仕方として郡レベルの行政区域に分割すると、テーブル作成に要する時間を多少なりと減少させるのに有利であることを示している、すなわち郡レベルの行政界は一般に河川や山脈等の地形的特性と密接な関係を有していることが多く、このような行政区界を横切る道路は少ないと考えられるためである。本論文ではこのように領域分割の仕方に一つの示唆を与えると共に、ここで採用したルックアップ・テーブル法により探索頒域を限定した経路探索法が、やはり最適経路を与えることが保証されている従来のDijkstra法およびA*アルゴリズムと比較し、総所要時間および必要とするRAM容量の面で現用のハードウェァの下では大幅に有利であることを示している。

著者

森山 賀文 飯村 伊智郎 中山 茂

出版者

情報文化学会

雑誌

情報文化学会誌 = Journal of the Japan Information-culture Society (ISSN:13406531)

巻号頁・発行日

vol.14, no.2, pp.6-10, 2008-12-05

参考文献数

9

被引用文献数

1

---

組合せ最適化問題とは,数多くの組合せの中から最適な解を求める問題であるが,問題の規模によっては現実的な時間内に厳密な解を求めることが困難となる場合がある。このような厳密な解を求めることが現実的に困難になるとき,準最適解を可能な限り高速に求める近似的解法が用いられる。その一つとしてアントコロニー最適化(Ant Colony Optimization: ACO)が知られている。しかしながら,ACOの最も基本的なAnt System(AS)を実装する場合でも,アリの群知能に関する知識が必要であり,それらをシミュレートするために煩雑なコーディング作業をプログラム開発者が行う必要がある。そこで本論文では,そのコーディングの煩雑さを軽減し,一般ユーザでもASを容易に適用できる環境構築を目的として,ACOのためのAnt言語を提案する。提案するAnt言語を巡回セールスマン問題に適用した結果,プログラムのステップ数とファイルサイズの大幅な削減ができ,コーディングの煩雑さを軽減することができた。