論文 - 武藤　佳恭

Comment on "The facility layout problem"

Bharitkar Sunil, Tsuchiya Kazuhiro, Takefuji Yoshiyasu

European Journal of Operational Research 75 （ 1 ） 233 - 234 1994年05月

ISSN  0377-2217

　概要を見る

<p>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].</p>

• Access to Document (DOI)

A Parallel Algorithm for Traffic Control Problems in Three-Stage Connecting Networks

Funabiki N., Takefuji Y.

Journal of Parallel and Distributed Computing 20 （ 2 ） 236 - 240 1994年02月

ISSN  0743-7315

　概要を見る

<p>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.</p>

• Access to Document (DOI)

Modified Hopfield-Tank neural networks applied to the 'unitized' maximum flow problem

Munakata Toshinori, Takefuji Yoshiyasu, Johansson Henrik

IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 41 （ 2 ） 174 - 177 1994年02月

ISSN  1057-7122

　概要を見る

<p>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 n²-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.</p>

• Access to Document (DOI)

Constrained optimization with use of two-dimensional maximum neurons

Yip Percy P C, Takefuji Yoshiyasu

  4667 - 4671 1994年

　概要を見る

<p>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.</p>

Job-shop scheduling based on modified tank-hopfield linear programming networks

Foo Simon Y., Takefuji Yoshiyasu, Szu Harold

Engineering Applications of Artificial Intelligence 7 （ 3 ） 321 - 327 1994年

ISSN  0952-1976

　概要を見る

<p>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.</p>

• Access to Document (DOI)

Parallel algorithm for broadcast scheduling problems in packet radio networks

Funabiki Nobuo, Takefuji Yoshiyasu

IEEE Transactions on Communications 41 （ 6 ） 828 - 831 1993年06月

ISSN  0090-6778

　概要を見る

<p>A parallel algorithm based on an artificial neural network model for broadcast scheduling problems in packet radio networks is presented. The algorithm requires n × m processing elements for an n-node-m-slot radio network problem. The algorithm is verified by simulating 13 different networks.</p>

• Access to Document (DOI)

Neural network approach to topological via-minimization problems

Funabiki Nobuo, Takefuji Yoshiyasu

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 12 （ 6 ） 770 - 779 1993年06月

ISSN  0278-0070

　概要を見る

<p>Topological via-minimization (TVM) algorithms in two-layer channels based on the artificial neural network model are presented in this paper. TVM problems require not only assigning wires or nets between terminals without an intersection to one of two layers, but also a minimization of the number of vias, which are the single contacts of nets between two layers. The goal of our algorithms is to embed the maximum number of nets without an intersection. Two types of TVM problems are examined: split rectangular TVM (RTVM) problems and split circular TVM (CTVM) problems. Our algorithms require 3 n processing elements for the n-net split RTVM problems, and 5 n processing elements for the n-net split CTVM problems. The algorithms were verified by solving seven problems with 20 to 80 nets. The algorithms can be easily extended for more-than-two-layer problems.</p>

• Access to Document (DOI)

Comparisons of seven neural network models on traffic control problems in multistage interconnection networks

Funabiki Nobuo, Takefuji Yoshiyasu, Lee Kuo Chun

IEEE Transactions on Computers 42 （ 4 ） 497 - 501 1993年04月

ISSN  0018-9340

　概要を見る

<p>This paper presents performance comparisons of seven neural network models on traffic control problems in multistage interconnection networks. The decay term, three neuron models, and two heuristics were evaluated. The goal of the traffic control problems is to find conflict-free switching configurations with the maximum throughput. Our simulation results show that the hysteresis McCulloch-Pitts neuron model without the decay term and with two heuristics has the best performance.</p>

• Access to Document (DOI)

A parallel multi-layer channel router on the HVH model

Funabaki Nobuo, Takefuji Yoshiyasu

Parallel Computing 19 （ 1 ） 63 - 77 1993年

ISSN  0167-8191

　概要を見る

<p>With the advancement of the silicon technology multi-layered VLSI circuits and PCBs (printed circuit boards) have been widely used. Based on the neural network model this paper presents the first parallel algorithm for multi-layer channel routing problems on the HVH model which minimize wiring areas in VLSI circuits and PCBs. The algorithm requires n × m × 2s processing elements for the n-net-m-track-3s-layer problem. The algorithm not only runs on a sequential machine but also on a parallel machine with maximally n × m × 2s processors. The algorithm is verified by solving seven benchmark problems where it finds better solutions than the existing algorithms for 6-12-layer problems in nearly constant time on a parallel machine.</p>

• Access to Document (DOI)

O(1) approximate parallel algorithm for the n-task-n-person assignment problem

Cho Yong Beom, Kurokawa Takakazu, Takefuji Yoshiyasu, Kim Hwa

  1503 - 1505 1993年

　概要を見る

<p>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.</p>

Near-optimum parallel algorithm for one-dimensional gate assignment problems

Tsuchiya Kazuhiro, Takefuji Yoshiyasu

  1499 - 1502 1993年

　概要を見る

<p>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.</p>

CMOS analog/digital circuit of the hysteresis McCulloch-Pitts neuron for Ramsey numbers

Cho Yong Beom, Tsuchiya Kazuhiro, Takefuji Yoshiyasu

Analog Integrated Circuits and Signal Processing 2 （ 4 ） 313 - 322 1992年11月

ISSN  0925-1030

　概要を見る

<p>A parallel algorithm for finding Ramsey numbers is presented where analog/digital CMOS circuits for the hysteresis McCulloch-Pitts binary neuron are described. The hysteresis McCulloch-Pitts binary neuron model is used in order to suppress the oscillatory behaviors of neural dynamics so that the convergence time is shortened. The proposed algorithm using the hysteresis McCulloch-Pitts binary neuron found five Ramsey numbers. The analog CMOS sigmoid circuit with variable gain controls has been fabricated and tested using the SAC data acquisition board interfaced with a TMS 32010 processor. Hysteresis can be implemented by the positive feedback in the fabricated CMOS analog circuit.</p>

Quantitative measurement of two-component pH-sensitive colorimetric spectra using multilayer neural networks

Lin Chii Wann, LaManna Joseph C., Takefuji Yashiyasu

Biological Cybernetics 67 （ 4 ） 303 - 308 1992年08月

ISSN  0340-1200

　概要を見る

<p>The purpose of this research was to develop a noise tolerant and faster processing approach for in vivo and in vitro spectrophotometric applications where distorted spectra are difficult to interpret quantitatively. A PC based multilayer neural network with a sigmoid activation function and a generalized delta learning rule was trained with a two component (protonated and unprotonated form) pH-dependent spectrum generated from microspectrophotometry of the vital dye neutral red (NR). The network makes use of the digitized absorption spectrum between 375 and 675 nm. The number of nodes in the input layer was determined by the required resolution. The number of output nodes determined the step size of the quantization value used to distinguish the input spectra (i.e. defined the number of distinct output steps). Mathematic analysis provided the conditions for which this network is guaranteed to converge. Simulation results showed that features of the input spectrum were successfully identified and stored in the weight matrix of the input and hidden layers. After convergent training with typical spectra, a calibration curve was constructed to interpret the output layer activity and therefore, predict interpolated pH values of unknown spectra. With its built-in redundant presentation, this approach needed no preprocessing procedures (baseline correction or intensive signal averaging) normally used in multicomponent analyses. The identification of unknown spectra with the activities of the output layer is a one step process using the convergent weight matrix. After learning from examples, real time applications can be accomplished without solving multiple linear equations as in the multiple linear regression method. This method can be generalized to pattern oriented sensory information processing and multi-sensor data fusion for quantitative measurement purposes.</p>

• Access to Document (DOI)

An artificial maximum neural network

Takefuji Yoshiyasu, Lee Kuo Chun, Also Hideo

Biological Cybernetics 67 （ 3 ） 243 - 251 1992年07月

ISSN  0340-1200

　概要を見る

<p>A maximum neuron model is proposed in order to force the state of the system to converge to the solution in neural dynamics. The state of the system is always forced in a solution domain. The artificial maximum neural network is used for the module orientation problem and the bipartite subgraph problem. The usefulness of the maximum neural network is empirically demonstrated by simulating randomly generated massive nstances (examples) in both problems. In randomly generated more than one thousand instances our system always converges to the solution within one hundred iteration steps regardless of the problem size. Our simulation results show the effectiveness of our algorithms and support our claim that one class of NP-complete problems may be solvable in a polynomial time.</p>

• Access to Document (DOI)

Optimization neural networks for the segmentation of magnetic resonance images

Amartur S. C., Piraino D., Takefuji Y.

IEEE Transactions on Medical Imaging 11 （ 2 ） 215 - 220 1992年06月

ISSN  0278-0062

　概要を見る

<p>The application of the Hopfield neural network for the multispectral unsupervised classification of MR images is reported. Winner-take-all neurons were used to obtain a crisp classification map using proton density-weighted and T₂-weighted images in the head. The preliminary studies indicate that the number of iterations needed to reach 'good' solutions was nearly constant with the number of clusters chosen for the problem.</p>

• Access to Document (DOI)

Functional-link net computing

Pao Yoh Han, Takefuji Yoshiyasu

Computer 25 （ 5 ） 76 - 79 1992年05月

ISSN  0018-9162

　概要を見る

<p>A system architecture and a network computational approach compatible with the goal of devising a general-purpose artificial neural network computer are described. The functionalities of supervised learning and optimization are illustrated, and cluster analysis and associative recall are briefly mentioned.</p>

• Access to Document (DOI)

Neural network parallel computing for BIBD problems

Kurokawa Takakazu, Takefuji Yoshiyasu

IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 39 （ 4 ） 243 - 247 1992年04月

ISSN  1057-7130

　概要を見る

<p>Neural network parallel computing for balanced incomplete block design (BIBD) problems is presented. A design in which all the blocks contain the same number of varieties, and all the varieties occur in the same number of blocks, is called a block design. A block is said to be incomplete if it does not contain all the varieties. If a design is balanced, it is called a balanced incomplete block design. Two methods for BIBD problems have been proposed. One uses the notion of the finite fields, and the other uses the notion of the difference sets. In general, the conventional algorithms are only able to solve the problems that satisfy an affine plane or a finite projective plane. The proposed algorithm is able to solve BIBD problems regardless of the condition of an affine plane or a finite projective plane. The proposed algorithm was verified by simulation runs. The simulation results demonstrated that the number of iteration steps for the system to converge to the solution increases slightly with the problem size.</p>

• Access to Document (DOI)

A parallel string search algorithm

Takefuji Yoshiyasu, Tanaka Toshimitsu, Lee Kuo Chun

IEEE Transactions on Systems, Man and Cybernetics 22 （ 2 ） 332 - 336 1992年03月

ISSN  0018-9472

　概要を見る

<p>A new parallel processing algorithm for solving string search problems is presented. The proposed algorithm uses O(m × n) processors where n is the length of a text and m is the length of a pattern. It requires two and only two iteration steps to find the pattern in the text, while the best existing parallel algorithm needs the computation time O(loglog n).</p>

• Access to Document (DOI)

Neural network parallel algorithm for clique vertex-partition problems

Funabiki Nobuo, Takefuji Yoshiyasu, Lee Kuo Chun, Cho Yong Beom

International Journal of Electronics 72 （ 3 ） 357 - 372 1992年03月

ISSN  0020-7217

　概要を見る

<p>A parallel algorithm based on a neural network model for solving clique vertex-partition problems in arbitrary non-directed graphs is presented in this paper. A clique of a graph G = (V, E) with a set of vertices V and a set of edges E is a complete subgraph of G where any pair of vertices is connected with an edge. A clique vertex-partition problem of a graph G is to partition every vertex in V into a set of disjointed cliques of G. The clique vertex-partition problem with the minimum number of cliques in an arbitrary graph is known to be NP-complete. The algorithm requires nm processing elements for the n vertex m partition problem. A total of 10 different problems with 8 vertex to 300 vertex graphs were examined where the algorithm found a solution in nearly constant time. The circuit diagram of the neural network model is also proposed in this paper.</p>

Generalized maximum neural network for the module orientation problem

Lee Kuo Chun, Takefuji Yoshiyasu

International Journal of Electronics 72 （ 3 ） 331 - 355 1992年03月

ISSN  0020-7217

　概要を見る

<p>Several neuron models and artificial neural networks have been intensively studied since McCulloch and Pitts proposed the simplified neuron model in 1943. In this paper a generalized maximum neural network for parallel computing is introduced to solve the module orientation problem which belongs to the class of NP-complete problems. The goal of the module orientation problem in VLSI circuits or printed circuit boards is to minimize the total wire length by flipping each module with respect to its vertical and/or horizontal axes of symmetry. The circuit diagram of the generalized maximum neural network is shown and compared with the best known algorithm proposed by Libeskind-Hadas and Liu. The theoretical/empirical convergence analysis is discussed where a massive number of simulation runs were performed using more than one thousand instances. As far as we have observed the behavior of the proposed system, it converges within O(1) time regardless of the problem size and it performs better than the best known algorithm in terms of the solution quality and the computation time.</p>