武藤 佳恭

生物が環境に適応するということは, 各生物の構造や初期状態を決定する「進化」と, その状態から徐々に修正する「学習」によって, 環境により適する状態へと遷移することである。本研究では, エージェントが学習や進化を行なう場合にどのようなメカニズムで行なえば動的環境に適応し得るかを明らかにする。

複数のエージェシトが協調して, 調和を保ちつつタスクの達成を実現するマルチエージェトシステムが現在注目されている。この場合, 各エージェントは自律的に自らの行動をコントロールすることが必要となる。ネットワーク上で自律的に行動するエージェントを前提とした場合, エージェント間の競合状態の発生が予想され, そのような場合に交渉が必要となる。通常の人間の交渉過程においては時間的コストが暗黙のうちに考慮されていると考 えられる。プログラムとして実現されるエージェント間の交渉においても, 同様の枠組を適用することが有効であると考えられる。プログラムを用いた交渉において, そのプロセスを実行するための計算機資源の利用もコストに含めることが適当であると考えられる。本研究では, 時間と資源コスト概念に基づいたエージェント間交渉のフレームワークを提示する。

市民の社会生活に占める情報通信インフラの役割が拡大し、そのようなインフラに対する不法な操作または妨害が社会に与える影響はますます大きくなることが予想される。このような社会における新しい国際紛争あるいはテロリズムの形態としてのInformation Warfareの出現について予測し、それに伴う倫理的および政策的な課題にっいて論じている。

近年のコンピューター・ネットワーク利用の普及により, ユーザーの要求にしたがって自律的にネットワーク上を移動しながら各種処理を実現するモバイル・エージェントの実用化への期待が高まっている。マルチプラットフォームに対応したJava^<TM>言語利用環境の普及とそのオブジェクト転送機能の実現は, このようなモバイルエージェントの利用の基盤としての要件を備えていると考えられる。本研究ではJava^<TM>言語を用いた分散オブジェクト環境上に, モバイル・エージェント機能を実現するための基盤環境を構築し, オープンなネットワーク上でモバイル・エージェントを利用するためのフレームワークとして, 計算機資源の利用に応じた課金システムのモデルを示す。また, このモデルを用いた利用市場のシミュレーションを行いその有効性に関する検証を行っている。

制約条件問題の代表的なものであるN Queen問題を拡張し, 多次元空間表現における制約条件問題のモデルとして, X次元N Queen問題を提案する。問題の解決には, N Queen問題で有効性が確認されているニューラルネットワークの手法を用いる。多次元空間における制約充足問題の解決は, 多数の制約条件を充足しなければならない問題解決の有効な一例と成り得る。

近年のWWWの普及により, Internet上には膨大な数のWWWサーバが存在している。1つのWWWサーバには通常, 複数のWWWページが存在し, WWWクライアントの通信要求に対して, たえずサービスを提供している。WWWサーバ上の複数のコンテンツは, 複数のコンテンツ所有者によって作成される場合が多く, 所有者は各自の端末でコンテンツを作成し, 何らかの手段を使って, WWWサーバにファイルを転送しなければならなかったり, WWWページ間のリンクを張り替えたい場合などは各所有者間のネゴシエーションが必要となる。このようなWWWコンテンツ作成手順は手間が掛かかり, WWWコンテンツ所有者の作業負荷を増大させる原因になるとともに, 情報発信の遅延を発生させる要因ともなる。そこで本論文では, コンテンツ所有者とWWWサーバ管理者に課せられる上記のような作業を代行するエージェントを提案する。

A parallel algorithm for solving meeting schedule problems is presented in this paper where the problem is NP-complete. The proposed system is composed of two maximum neural networks which interact with each other. One is an M x S neural network to assign meetings to available time slots on a timetable where M and S are the number of meetings and the number of time slots, respectively. The other is an M x P neural network to assign persons to the meetings where P is the number of persons. The simulation results show that the state of the system always converges to one of the solutions. Our empirical study shows that the solution quality of the proposed algorithm does not degrade with the problem size.

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N x N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.

A parallel algorithm for solving meeting schedule problems is presented in this paper where the problem is NP-complete. The proposed system is composed of two maximum neural networks which interact with each other. One is an M×S neural network to assign meetings to available time slots on a timetable where M and S are the number of meetings and the number of time slots, respectively. The other is an M×P neural network to assign persons to the meetings where P is the number of persons. The simulation results show that the state of the system always converges to one of the solutions and that the solution quality of the proposed algorithm does not degrade with the problem size.

本論文では、快適なサイバー社会を迎えるためには近い将来日本はどのような課題を克服しなければいけないか、6つのインフラストラクチャの観点から述べる。また、どのようなコンピュータが一般大衆に使われるか予測しながら、3つの重要なソフトウエア技術について説明する。

A near-optimum parallel algorithm for solving PLA folding problems is presented in this paper where the problem is NP-complete and one of the most fundamental problems in VLSI design. The proposed system is composed of n X n neurons based on an artificial two-dimensional maximum neural network where n is the number of inputs and outputs or the number of product lines of PLA. The two-dimensional maximum neurons generate the permutation of inputs and outputs or product lines. Our algorithm can solve not only a simple folding problem but also multiple, bipartite, and constrained folding problems. We have discovered improved solutions in four benchmark problems over the best existing algorithms using the proposed algorithm. © 1996 IEEE.

A balloon net model is introduced and demonstrated for discovering improved solutions in one of unsolved problems in geometry which is referred to as a problem of `Spreading points in a square'. How should n points be arranged in a unit square so that the minimum distance between them is the greatest? Note that d(n) is the greatest possible minimum distance between n points in a unit square. Exact results are known for n≤9 and n = 14, 16, 25, and 36. Many investigators including Schaer, Meir, Kirchner, Wengerodt, Goldberg, Schluter, Valette and others have studied this geometrical problem for many years. The best known result is summarized in the book of `Unsolved Problems in Geometry' (H.T. Croft. K.J. Falconer and R.K. Guy/1991). We have found improved solutions for n = 13 and n = 15 by the proposed algorithm.

In December 1994, Japanese single-member constituency system for the House of Representatives was established where Japan is divided into three hundred constituencies. A single representative will be elected from each constituency. Zoning three hundred constituencies was accomplished by hand calculators in Japan where zoning the constituencies is a very elaborate task because several constraints must be satisfied. This paper presents a neural computing approach for automatically zoning constituencies. Our method was examined by using 25 Tokyo constituencies. Ideally, the weight of a single vote in a certain population to elect a representative should be equal to that of the other constituencies. Based on the established rule, the ratio of the lightest weight to the heaviest weight must be within two. Our result shows that our ratio is 1.28 while the current (official) ratio is 1.47.

The no-three-in-line problem is one of unsolved problems in number theorem. The goal of the no-three-in-line problem is to locate 2N points on an N × N squares array where no three points are in line. The proposed algorithm uses N hysteresis McCulloch-Pitts neurons as the processing elements for the N × N array problem. Our neural network algorithm has discovered several different solutions for up to N = 25. © 1995. 2

Multi-layer channel routing is one of cumbersome jobs in automatic layout design of VLSI chips and PCBs. As VLSI chips have been used in every field of electrical engineering, it becomes more important to reduce the layout design time. With the advancement of the VLSI technology, four-layer problems can be treated and the algorithms for more than four-layer problems will be demanded in the near future. Proposed algorithm can treat 2 × n-layer problems in parallel. In this paper, the algorithm is introduced and implemented on a multiprocessor system. By minimizing the communication overhead and load unbalance between processors, the performance with 8 processors is improved by between 6 and 6.5 times compared with the sequential version. © 1995.

This paper investigates the scaling properties of neural networks for solving job-shop scheduling problems. Specifically, the Tank-Hopfield linear programming network is modified to solve mixed integer linear programming with the addition of step-function amplifiers. Using a linear energy function, our approach avoids the traditional problems associated with most Hopfield networks using quadratic energy functions. Although our approach requires more hardware (in terms of processing elements and resistive interconnects) than a recent approach by Zhou et al. [2], the neurons in the modified Tank-Hopfield network do not perform extensive calculations unlike those described by Zhou et al. © 1995.

The Tank-Hopfield linear programming network is modified to solve job-shop scheduling, a classical optimization problem. Using a linear energy function, the approach described in this paper avoids the traditional problems associated with most Hopfield networks using quadratic energy functions. Although this approach requires more hardware (in terms of processing elements and resistive interconnects) than a recent approach by Zhou et al. (IEEE Trans. Neural Networks 2, 175-179, 1991) the neurons in the modified Tank-Hopfield network do not perform extensive calculations, unlike those described by Zhou et al. © 1994.

This note points to an error in the invited review of "The facility layout problem" by Andrew Kusiak and Sundaresh S. Heragu [4] as per their information of the solution quality of the Heuristic 1 technique presented by Burkard and Stratman [3]. © 1994.

Two new approaches called “graph unitization” are proposed to apply neural networks similar to the Hopfield-Tank models to determine optimal solutions for the maximum flow problem. They are: (1) n-vertex and n2-edge neurons on a unitized graph; (2) m-edge neurons on a unitized graph. Graph unitization is to make the flow capacity of every edge equal to 1 by placing additional vertices or edges between existing vertices. In our experiments, solutions converged most of the time, and the converged solutions were always optimal, rather than near optimal. © 1994 IEEE

Because of the internet online library systems, it is now possible to survey and to know what is going on in every research area and/or multi-disciplinary area. Unvortunately many Japanese investigators are not aware of the recent progress of the internet library systems. Several representative online library systems are introduced in this paper including Library of Congress in US, the FirstSearch database system, and the Uncover database system where a partial list of our neural computing books and papers for optimization and combinatorics is collected as an example survey.

A special neuron, which we call two-dimensional maximum neuron is proposed. This type of neuron can eliminate the row and column constraints that occur in many problems, such as the stable marriage problem. A parallel processing algorithm to find the stable marriage matching using the proposed two-dimensional maximum neurons is described and the result is now reported.

現在までに提案されている並列細密配線アルゴリズムのほとんどは、従来からある迷路法、線分探索法を並列化したものである。このため、並列計算機に実装した場合に高いプロセッサ利用率と高い台数効果を同時に得ることが難しい。本研究では、これらの条件を満たせるようにニューラルネットワークに基づく並列自動配線アルゴリズムを提案した。このアルゴリズムを並列計算機ATTEMPT-0上に実装したところ、PU数8台で最大5.3倍の高速化を達成した。

A parallel heuristic algorithm for traffic control problems in three-stage connecting networks is presented in this paper. A three-stage connecting network consists of an input crossbar switching stage, an intermediate crossbar switching stage, and an output crossbar switching stage. The goal of our algorithm is to quickly and efficiently find a conflict-free switching assignment for communication demands through the network. The algorithm requires n × m processing elements for the network composed of n input/output switches and m intermediate switches, where it runs not only on a sequential machine, but also on a parallel machine with maximally n × m processors. The algorithm was verified by 1100 simulation runs with the network size from 10 × 7 to 50 × 27. The simulation results show that the algorithm can find a solution in nearly constant time with n × m processors. © 1994 Academic Press, Inc. 2 2 2 2 2

This paper presents a parallel algorithm for timeslot assignment problems in TDM hierarchical switching systems, based on the neural network model. The TDM systems are operated. in repetitive frames composed of several Time-Slots. A Time-Slot represents a switching configuration where one packet is transmitted through an I/O line. The goal of our algorithm is to find conflict-free Time-Slot assignments for given switching demands. The algorithm runs on a maximum of n2×m processors for m-Time-Slot problems in n×n TDM systems. In small problems up to a 24×24 TDM system, the algorithm can find the optimum solution in a nearly constant time, when it is performed on n2×m processors. © 1994 IEEE

A parallel algorithm for the n-task-n-person assignment problem is presented in this paper. The proposed algorithm is based on the artificial neural network model where a large number of simple processing elements are used. Through a large number of simulation runs, it was empirically shown that the state of the system can converge to the solution within a hundred iteration steps regardless of the problem size n. The proposed algorithm using n processing elements requires computational bounds of a nearly O(1) time. 2

A near-optimum parallel algorithm for one-dimensional gate assignment problems is presented in this paper where the problem is NP-hard. The proposed system is composed of an n×n two-dimensional maximum neural network for (n+2)-gate assignment problems. Our algorithm has discovered the improved solution in the benchmark problem over the existing algorithms.