研究者詳細 - 武藤　佳恭

論文 - 武藤　佳恭

分割表示 211 件中 161 - 180 件目／全件表示 >>

A parallel improvement algorithm for the bipartite subgraph problem

Lee Kuo Chun, Funabiki Nobuo, Takefuji Yoshiyasu

IEEE Transactions on Neural Networks 3 （ 1 ） 139 - 145 1992年01月

ISSN 1045-9227

The authors propose the first parallel improvement algorithm using the maximum neural network model for the bipartite subgraph problem. The goal of this NP-complete problem is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that the algorithm finds a solution within 200 iteration steps and the solution quality is superior to that of the best existing algorithm. The algorithm is extended for the K-partite subgraph problem where no algorithm has been proposed.

Access to Document (DOI)

A Parallel Algorithm for Channel Routing Problems

Funabiki Nobuo, Funabiki Nobuo, Takefuji Yoshiyasu

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 11 （ 4 ） 464 - 474 1992年

ISSN 0278-0070

A parallel algorithm for channel routing problems is presented in this paper. The channel routing problem is very important in the automatic layout design of VLSI circuits and printed circuit boards. The problem is to route the given interconnections between two rows of terminals on a multilayer channel where the channel area must be minimized. Although several algorithms have been proposed for two-layer problems, two-Iayer-and-over-the-cell problems, and three-layer problems, the current advancement of VLSI chip technology allows us to use four layers composed of two metal layers and two polysilicon layers for routing in a chip. The goal of the proposed parallel algorithm is to find the near-optimum routing solution for the given interconnections in a short time. The algorithm is applied for the four-layer channel routing problems where it requires n × m × 2 processing elements for the n-netm-track problem. The algorithm has three advantages over the conventional algorithms: 1) it can be easily modified for accommodating more than four-layer problems, 2) it runs not only on a sequential machine but also on a parallel machine with maximally n ×m × 2 processors, and 3) the program size is very small. The algorithm is verified by solving seven benchmark problems where the algorithm finds routing solutions in a nearly constant time with n × m × 2 processors.

Access to Document (DOI)

A parallel algorithm for solving unfriendly beehive problems

Rofkar J. D., Takefuji Y.

Neurocomputing 4 （ 3-4 ） 167 - 179 1992年

ISSN 0925-2312

This paper presents a general purpose algorithm for solving the Unfriendly Beehive Game. The proposed algorithm will utilize an artificial neural network to solve the problem. The neural network will use a simple partial differential (motion) equation expressed in terms of its natural constraints. Each constraint within the equation represents a simple connection to an artificial neuron. Each connection strength (or synaptic strength) is weighted by multiplicative constants and summed together. The result is an input that is adjusted in the direction that decreases the error or conflict. Using this information, the system derives a simple binary state output in an attempt to solve the puzzle. Given an overall time slot in which to resolve all conflicts, the system iteratively strives to arrive at the state of the global minimum. The proposed algorithm will be able to solve a variety of real-world problems, including: facility layouts for maximizing productivity and safety, classroom assignment for minimizing pupil conflict, crop and plant placement for maximizing yields, and chemical placement within shipping boxes to reduce the possibility of chemical interactions.

Access to Document (DOI)

A parallel algorithm for scheduling problem based on Hopfield model for the automated synthesis of digital systems

Nourani-Dargiri Mehrdad, Papachristou Christos A., Takefuji Yoshiyasu

910 1992年

Summary form only given. A novel scheduling approach has been developed based on the deterministic Hopfield model for high-level synthesis. The model uses a four-dimensional neural network architecture to schedule the operations of a dataflow graph and maps them to specific functional units. Neural network-based scheduling is achieved by formulating the scheduling problem in terms of an energy function and by using the motion equation corresponding to the variation of energy. The algorithm searches the scheduling space in parallel and finds the optimal schedule. The main contribution of the present work is an efficient scheduling algorithm under time and resource constraints. The algorithm is based on moves in the scheduling space, which correspond to moves towards the equilibrium point (lowest energy state) in the dynamic system space. The neurons' motion equation is the heart of this guided movement mechanism and guarantees that the state of the system always converges to the lowest energy state.

A neural network model for traffic controls in multistage interconnection networks

Funabiki Nobuo, Takefuji Yoshiyasu, Lee Kuo Chun

898 1992年

Summary form only given, as follows. A neural network model for traffic controls in multistage interconnection networks is discussed. The goal of the neural network model is to find conflict-free traffic flows to be transmitted among given I/O traffic demands in order to maximize the network throughput. The model requires n² processing elements for the traffic control in an n × n multistage interconnection network. The model runs not only on a sequential machine but also on a parallel machine with maximally n² processors. The model was verified by solving ten 32 × 32 network problems.

A neural network model for finding a near-maximum clique

Funabiki Nubuo, Takefuji Yoshiyasu, Lee Kuo Chun

Journal of Parallel and Distributed Computing 14 （ 3 ） 340 - 344 1992年

ISSN 0743-7315

A parallel algorithm based on the neural network model for finding a near-maximum clique is presented in this paper. A maximum clique of a graph G is a maximum complete subgraph of G where any two vertices are adjacent. The problem of finding a maximum clique is NP-complete. The parallel algorithm requires n processing elements for an n-vertex graph problem. The algorithm is verified by solving 230 different graph problems. The simulation results show that our computation time on a Macintosh IIfx is shorter than that of two better known algorithms on a Cray 2 and an IBM 3090 while the solution quality is similar. The algorithm solves a near-maximum clique problem in nearly constant time on a parallel machine with n processors.

Access to Document (DOI)

Neural computing in discovering RNA interactions

Takefuji Yoshiyasu, Ben-Alon Dora, Zaritsky Arieh

BioSystems 27 （ 2 ） 85 - 96 1992年

ISSN 0303-2647

High-order RNA structures are involved in regulating many biological processes; various algorithms have been designed to predict them. Experimental methods to probe such structures and to decipher the results are tedious. Artificial intelligence and the neural network approach can support the process of discovering RNA structures. Secondary structures of RNA molecules are probed by autoradiographing gels, separating end-labeled fragments generated by base-specific RNases. This process is performed in both conditions, denaturing (for sequencing purposes) and native. The resultant autoradiograms are scanned using line-detection techniques to identify the fragments by comparing the lines with those obtained by 'alkaline ladders'. The identified paired bases are treated by either one of two methods to find the foldings which are consistent with the RNases' 'cutting' rules. One exploits the maximum independent set algorithm; the other, the planarization algorithm. They require, respectively, n and n² processing elements, where n is the number of base pairs. The state of the system usually converges to the near-optimum solution within about 500 iteration steps, where each processing element implements the McCulloch-Pitts binary neuron. Our simulator, based on the proposed algorithm, discovered a new structure in a sequence of 38 bases, which is more stable than that formerly proposed.

Access to Document (DOI)

Neural network computing for knight's tour problems

Takefuji Yoshiyasu, Lee Kuo Chun

Neurocomputing 4 （ 5 ） 249 - 254 1992年

ISSN 0925-2312

Access to Document (DOI)

Neural network based algorithm for the scheduling problem in high-level synthesis

Nourani Mehrdad, Papachristou Christos, Takefuji Yoshiyasu

341 - 346 1992年

This paper presents a new scheduling approach for high-level synthesis based on a deterministic modified Hopfield model. Our model uses a four dimensional neural network architecture to schedule the operations of a data flow graph (DFG) and maps them to specific functional units. Neural Network-based Scheduling (NNS) is achieved by formulating the scheduling problem in terms of an energy function and by using the motion equation corresponding to the variation of energy. The algorithm searches the scheduling space in parallel and finds the optimal schedule. The main contribution of this work is an efficient parallel scheduling algorithm under time and resource constraints appropriate for implementing on a parallel machine. The algorithm is based on moves in the scheduling space, which correspond to moves towards the equilibrium point (lowest energy state) in the dynamic system space. Neurons' motion equation is the core of this guided movement mechanism and guarantees that the state of the system always converges to the lowest energy state.

Comments on 'O(n²) algorithms for graph planarization' by R. Jayakumar et al.

Takefuji Yoshiyasu, Lee Kuo Chun, Cho Yong Beom

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 10 （ 12 ） 1582 - 1583 1991年12月

ISSN 0278-0070

Access to Document (DOI)

An artificial hysteresis binary neuron

Takefuji Y., Lee K. C.

Biological Cybernetics 64 （ 5 ） 353 - 356 1991年03月

ISSN 0340-1200

A hysteresis binary McCulloch-Pitts neuron model is proposed in order to suppress the complicated oscillatory behaviors of neural dynamics. The artificial hysteresis binary neural network is used for scheduling time-multiplex crossbar switches in order to demonstrate the effects of hysteresis. Time-multiplex crossbar switching systems must control traffic on demand such that packet blocking probability and packet waiting time are minimized. The system using n×n processing elements solves an n×n crossbar-control problem with O(1) time, while the best existing parallel algorithm requires O(n) time. The hysteresis binary neural network maximizes the throughput of packets through a crossbar switch. The solution quality of our system does not degrade with the problem size.

Access to Document (DOI)

Artificial neural networks for four-coloring map problems and K-colorability problems

Takefuji Yoshiyasu, Lee Kuo Chun

IEEE Transactions on Circuits and Systems 38 （ 3 ） 326 - 333 1991年03月

ISSN 0098-4094

The computational energy required for solving a four-coloring map problem is determined. A parallel algorithm for solving the problem based on the McCulloch-Pitts binary neuron model and the Hopfield neural network, is presented. It is shown that the computational energy is always guaranteed to monotonically decrease with the Newton equation. A 4 × n neural array is used to color a map of n regions, where each neuron is a processing element that performs according to the proposed Newton equation. The capability of this system is demonstrated for a large number of simulation runs. The parallel algorithm is extended for solving the K-colorability problem.

Access to Document (DOI)

A Parallel Algorithm for Allocation of Spare Cells on Memory Chips

Funabiki Nobuo, Takefuji Yoshiyasu

IEEE Transactions on Reliability 40 （ 3 ） 338 - 346 1991年

ISSN 0018-9529

In manufacturing memory chips, Redundant Random Access Memory (RRAM) technology has been widely used because it not only provides repair of faulty cells but also enhances the production yield. RRAM has several rows and columns of spare memory cells which are used to replace the faulty cells. The goal of our algorithm is to find a spare allocation which repairs all the faulty cells in the given faulty-cell map. The parallel algorithm requires In processing elements for the n x n faulty-cell map problem. The algorithm is verified by many simulation runs. Under the simulation the algorithm finds one of the near-optimum solutions in a nearly constant time with 0(n) processors. The simulation results show the consistency of our algorithm. The algorithm can be easily extended for solving rectangular or other shapes of fault map problems. Reader Aids - Purpose: Present a new algorithm Special math needed for explanations: Probability Special math needed to use results: None Results useful to: Reliability theoreticians and analysts.

Access to Document (DOI)

A maximum neural network for the max cut problem

Lee Kuo Chun, Takefuji Yoshiyasu, Funabiki Nobuo

379 - 384 1991年

The max cut problem, one of the NP-complete problems, was chosen to test the capability of an artificial neural network. The algorithm based on the maximum neural network was tested by 1000 randomly generated examples, including up to 300 vertex problems. The simulation result shows that the proposed parallel algorithm using the maximum neural network generates better solutions than Hsu's algorithm within one hundred iteration steps, regardless of the problem size.

Analog maximum neural network circuits using the switched capacitor technique

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

1906 - 1911 1991年

A parallel neural network computing for the maximum clique problem

Lee Kuo Chun, Funabiki Nobuo, Cho Y. B., Takefuji Yoshiyasu

905 - 910 1991年

A novel computational model for large-scale maximum clique problems is proposed and tested. The maximum clique problem is first formulated as an unconstrained quadratic zero-one programming and it is solved by minimizing the weight summation over the same partition in a newly constructed graph. The proposed maximum neural network has the following advantages: (1) coefficient-parameter tuning in the motion equation is not required in the maximum neural network while the conventional neural networks suffer from it; (2) the equilibrium state of the maximum neural network is clearly defined in order to terminate the algorithm, while the existing neural networks do not have the clear definition; and (3) the maximum neural network always allows the state of the system to converge to the feasible solution, while the existing neural networks cannot guarantee it. The proposed parallel algorithm for large-size problems outperforms the best known algorithms in terms of computation time with much the same solution quality where the conventional branch-and-bound method cannot be used due to the exponentially increasing computation time.

A neural network approach to broadcasting in multihop packet radio networks

Funabiki Nobuo, Takefuji Yoshiyasu, Lee Kuo Chun, Cho Yong Beom, Kurokawa Takakazu, Aiso Hideo

2540 - 2545 1991年

A neural network model for broadcasting scheduling in multihop packet radio networks is presented. The problem of broadcast scheduling with a minimum number of time slots is NP-complete. The proposed neural network model finds a broadcasting schedule with a minimal number of time slots where it requires n processing elements for an n-node radio network. Fifteen different radio networks were examined where the neural network model found an m-time-slot solution in O(m) time with n processors.

A parallel algorithm for solving the 'Hip' games

Funabiki Nobuo, Takefuji Yoshiyasu

Neurocomputing 3 （ 2 ） 97 - 106 1991年

ISSN 0925-2312

A parallel algorithm for solving the 'Hip' games based on an artificial neural network model is presented in this paper. The game of 'Hip' is named because of the hipster's reputed disdain for 'squares'. The rule of the game is to place the counters on a checkerboard so that four of them do not mark the corners of a square. The square may be of any size and be tipped at any angle. Normally this game is played by two players, where the game on a six-by-six checkerboard is the maximum size for the solution. The solution means that every player can place all the counters on the checkerboard without violations. In other words, the goal of our algorithm is to find the pattern of a draw game between players where they should not mark the corners of a square. In order to enlarge the size of the checkerboard where a solution exists, we modified the game as n/2 players play on an n-by-n checkerboard where n is an even number. The proposed parallel algorithm requires m × n² processing elements for the m-player-n-by-n-checkerboard game to find the solution of the 'Hip' games. The algorithm is verified by solving six games where the size of the checkerboard is varied from 4 to 12.

Access to Document (DOI)

Quantitative measurement of two-component absorption spectra using multilayer semilinear neural networks

Lin C. W., LaManna J. C., Lee K. C., Takefuji Y.

Annals of Biomedical Engineering 19 （ 5 ） 615 - 616 1991年

ISSN 0090-6964

A PC-based multilayer neural network with sigmoid activation function, generalized delta learning rule and error back-propagation was trained with two individual components (protonated and unprotonated form) of pH dependent spectra between 400 and 700 nm generated from microspectrophotometry of Neutral Red (NR). The NR spectrum changes from one resembling the acid to one resembling the base as the solution's pH changes from acid to base. The number of nodes in the input layer was based on the degree of resolution required. The number of hidden layer units was related to the storage capacity and could be a function of maximum connection weight between input and the hidden layer. The number of output nodes determined the step size used to distinguish the input spectrum. Teaching patterns are binary encoded to compare to the activity in the output layer. Simulation results show that after successful convergence with the training spectra features of the input spectrum are separated and stored in the weight matrix of the input and hidden layers. A calibration curve can be constructed to interpret the output layer activity and therefore allow prediction of the pH. With its intrinsically redundant presentation, this novel approach to spectrophotometry needs no preprocessing procedures (baseline correction and extensive signal averaging) for spectral identification. Spectral distortion, e.g. due to light scattering effects, such as between phosphate buffer solutions and brain homogenates do not affect the outcome. This method was applied to the in vitro hippocampal slice preparation to measure anoxic pHi changes. The method can be generalized to adapt to any pattern oriented sensory information processing and multi-sensor fusion for quantitative measurement.

CMOS layout design of the hysteresis McCulloch-Pitts neuron

Kurokawa T., Lee K. C., Cho Y. B., Takefuji Y.

Electronics Letters 26 （ 25 ） 2093 - 2095 1990年12月

ISSN 0013-5194

A McCulloch-Pitts neuron is the simplified neuron model which has been successfully used for many optimisation problems. The neural network with the hysteresis property can suppress the oscillatory behaviours of neural dynamics so that the convergence time is shortened. In this paper, digital CMOS layout design of the hysteresis McCulloch-Pitts neuron is presented. Based on simulation results using the hysteresis McCulloch-Pitts binary neuron model, a 6-bit fixed point 2's complement arithmetic was adopted for the calculation of the input U of each neuron. Each neuron needs 204 transistors and requires a 399 λ × 368 λ layout area using the MOSIS scalable CMOS/bulk (SCMOS) VLSI technology with 2 μm rule of P well, double level metal. Layout design of the hysteresis McCulloch-Pitts neuron chip was completed, and fabrication of the chip and the design for the test circuit for the fabricated CMOS VLSI chip are underway at present.

　前のページ - 次のページ　

武藤 佳恭

論文 - 武藤 佳恭

武藤　佳恭

論文 - 武藤　佳恭