著者

仙石 浩明 吉原 郁夫

雑誌

全国大会講演論文集

巻号頁・発行日

vol.47, pp.233-234, 1993-09-27

被引用文献数

5

---

前回報告した遺伝的アルゴリズム(GA)による、巡回セールスマン問題(TSP)の解法の評価を行う。評価は、局所最適解から脱出するアルゴリズムとして代表的なシミュレーティッドアニーリング(SA)法と、最適解への収束頻度で比較することにより行う。実験には、最適解が既知である四つの問題を用いる。そのうち二つは今回提案する問題である。一つは最適解が極めて多く存在する問題であり、他方は最適解がごくわずかしか存在しないものである。

著者

仙石 浩明 吉原 郁夫 今川 徹三

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.1995, no.66, pp.19-26, 1995-07-19

参考文献数

4

被引用文献数

3

---

遺伝的アルゴリズム()は、探索が大域的、制約条件の変化に柔軟、などの長所があり、開発・保守工数を削減できるが、遺伝子コーディング法、交差方法などを問題毎に考案しなければならない。一方、従来から広く用いられてきたヒューリスティック探索法は、人手で解かれていたような問題を解く場合は、容易にアルゴリズムを作ることができる。しかし実問題に適用するには、より詳細な知識を組み込むなどのチューンアップが必須であり、開発・保守工数がかかるという短所がある。そこで、ヒューリスティック探索において探索木の分枝選択に優先順位を定め、この優先順位をGAで最適化する手法を提案する。本提案手法をバス仕業ダイヤ作成システムに応用し、実用上十分な仕業ダイヤ作成が可能となった。本システムは実際にダイヤ改正で使われた。Genetic Algorithms (GAs) have advantages in ability to search globally and flexibly, but we have to design the gene coding and the crossover method depending on each problem. On the other hand heuristic search algorithms are easy to develop and have been widely used to solve the problems, which have been conventionally solved manually, but for practical applications, we have to tune up the algorithms, for example, adding knowledge in detail, adjusting parameters, and so on. In this paper, we present a method using GA as an optimizer of the heuristic search. In our method, GA tunes the priorities of choosing branches in search tree, with which heuristic search algorithm can find optimal solutions. We apply our method to bus drivers scheduling systems. It can generate enough practical schedules, and is already used for revising drivers schedules.

著者

安永 守利 吉原 郁夫

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.88, no.5, pp.915-929, 2005-05-01

被引用文献数

17

---

VLSI実装基板において, 配線上を伝搬する超高速信号の信号品質を向上することが重要な課題となっている.特に, クロック信号はディジタル電子機器の基本同期信号であり, 高い信号品質が望まれる.本論文では, 信号品質を向上させるための新たな伝送線構造である「セグメント分割伝送線」を提案する.セグメント分割伝送線は, 独立した特性インピーダンスをもつ複数のセグメントからなる伝送線である.複数セグメントの特性インピーダンスの不整合により発生する反射ノイズを重畳することにより, 伝送線上の注目点における信号を整形し, 信号品質を向上することが特徴である.セグメント分割伝送線の設計では, 複数セグメントの特性インピーダンスの最適な組合せを求める必要がある.この設計のために, 遺伝的アルゴリズムを適用する.また, その効率的な進化を実現するための新たな交差方法である「部分空間交差法」を提案する.更に, この新たな交差法に基づく遺伝操作を用いたセグメント分割伝送線の設計支援システムを開発する.開発した設計支援システムを用いて実際の実装基板上のメモリモジュール配線を設計し, 従来手法との比較評価を行い, その有効性を示す.

著者

安永 守利 高見 知親 吉原 郁夫

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-II, 情報・システム, II-パターン処理 (ISSN:09151923)

巻号頁・発行日

vol.84, no.10, pp.2280-2292, 2001-10-01

被引用文献数

7

---

大量な画像データに対する高速な認識処理は, 産業の様々な分野で要求されている.我々は, 画像認識処理に内在している並列処理可能性に着目し, FPGA(Field Programmable Gate Array)の書換え可能性を利用した細粒度高並列な専用付加ハードウェアにより, 高速認識処理を実現しようと考えた.このために本論文では, 統計的パターン認識手法の一つであるParzen Window法をハードウェア化のために拡張することを提案する.この提案手法により, 画像パターンデータから直接パターン認識回路を生成することができる.これにより, サンプルパターン数と同数の並列度を有する専用回路が, 複雑な演算器等を使用せずに構成できる.したがって, 高速なパターン認識処理を小規模なハードウェアで実現できる.パターンデータを直接回路化することは, 対象問題ごとに異なる集積回路(1問題1品種)を最適設計することである.これは, 従来の方法, すなわちフォトマスクベースの集積回路(汎用1品種)を作成し問題の個別性にはソフトウェアで対応する方法とは根本的に異なる.このような個別対応の専用ハードウェアは, FPGAを利用することで実現できる.本論文では提案ハードウェアを試作し, 顔画像認識を題材に本方式の有効性を評価する.具体的には, 実験結果をニューロコンピュータや超並列計算機を用いた従来技術と比較し, 認識精度, 動作速度(認識処理時間), 回路規模の観点から評価する.その結果, 認識精度は従来手法とほぼ同程度(ベンチマークデータで95.8%)であったが, パーソナルコンピュータより2, 000倍以上高速で, 更に, ニューロコンピュータや超並列計算機より55〜125倍高速なナノ秒オーダの認識処理が可能なハードウェアを1ボードで実現することができた.

著者

仙石 浩明 吉原 郁夫

雑誌

全国大会講演論文集

巻号頁・発行日

vol.46, pp.305-306, 1993-03-01

被引用文献数

4

---

遺伝的アルゴリズム(Genetic Algorithm:GA)は生物進化のシステムをモデル化したものである。1975年にHollandによって提唱された。Grefenstetteが提案した遺伝子表現法および一点交叉法を用いると、GAで巡回セールスマン問題(Tyaveling Salesman Problem:TSP)が解けることから、近年GAが注目されている。ところがこの解法は収束が遅い。そこで本報告では、Grefenstetteの方法より高速に収束し、さらに最適解を高い確率で得ることが可能な、GAを用いたTSPの高効率探索アルゴリズムを提案する。