論文

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.

The commenters point out that their parallel algorithm provides the maximum planar subgraph, and they compare it to the maximal planar subgraph provided by R. Jayakumar et al. (ibid., vol. 8, pp. 257-267, Mar 1989) in the above-mentioned paper. The space-time product complexity is also compared.

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.

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.

A parallel algorithm based on neural networks for solving sorting problems is presented. The proposed algorithm uses O(n2) processing elements called binary neurons, where n is the number of unsorted elements. It requires two and only two iteration steps, while the conventional parallel sorting algorithm using (On) processors proposed by F. T. Leighton (1984) requires the computation time O(log n). A set of simulation results substantiates the proposed algorithm. The hardware system based on the proposed parallel algorithm is also presented.

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.

A novel neural network parallel algorithm for sorting problems is presented. The proposed algorithm using O(n2) processors requires only two steps, and does not depend on the size of the problem, while the conventional parallel sorting algorithm using O(n) processors by F. T. Leighton (1984) needs the computation time O(log n2). A set of simulation results substantiates the proposed algorithm. The hardware system based on the proposed parallel algorithm is also presented.

A parallel algorithm for estimating the secondary structure of an RNA molecule is presented in this paper. The mathematical problem to compute an optimal folding based on free-energy minimization is mapped onto a graph planarization problem. In the planarization problem we want to maximize the number of edges in a plane with no two edges crossing each other. To solve a sequence of n bases, n(n - 1)/2 processing elements are used in our algorithm.

A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph of the number of possible base pairs), not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. The simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid, than previously proposed structures.

Principles of operation and basic building blocks of artificial neural networks are described. Deterministic components, comprising variable linear conductance devices and components used for processing elements, are discussed. These devices are analyzed using SPICE. The reasons for using simple analog circuits rather than digital circuits are examined.

A parallel algorithm for tiling with polyominoes is presented. The tiling problem is to pack polyominoes in a finite checkerboard. The algorithm using l × m × n processing elements requires O(1) time, where l is the number of different kinds of polyominoes on an m × n checkerboard. The algorithm can be used for placement of components or cells in a very large-scale integrated circuit (VLSI) chip, designing and compacting printed circuit boards, and solving a variety of two- or three-dimensional packing problems.

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.

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.

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.

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.

This paper presents a parallel algorithm for time-slot 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.

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

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 n2 × 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 n2 × m processors. The algorithm was verified by 1100 simulation runs with the network size from 102 × 7 to 502 × 27. The simulation results show that the algorithm can find a solution in nearly constant time with n2 × m processors.

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.

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.