The deterioration of signal integrity (SI) due to the skin effect and dielectric loss has been one of the most serious problems in the printed circuit board (PCB) trace since the clock frequency exceeded several hundred MHz. It is expected that the same problem will occur due to the same causes when the frequency exceeds several GHz in global and very long interconnects in very-large-scale integration (VLSI) and in silicon interposers. Currently, in PCBs, this problem is typically overcome by using either passive equalizers based on lumped-element circuits or active equalizers. Unfortunately, however, those equalizers are not suitable for VLSI interconnects in terms of power consumption and parasitic elements. In this paper, we apply a passive equalizer based on distributed-element circuits to global interconnects in VLSIs and silicon interposers; furthermore, we propose a design methodology for this. We fabricate a scale-up prototype of the proposed equalizer and demonstrate that the SI is improved; compared with a conventional interconnect, the jitter is reduced by 55.5%, and the eye height is increased by 75%.

This paper proposes a novel crossover operator for solving large-scale traveling salesman problems (TSPs) by using a Hybrid Genetic Algorithm (HGA) with Lin-Kernighan heuristic for local search and we tentatively name Zoning Crossover (Z-Cross). The outline of Z-Cross is firstly to set a zone in the travelling area according to some rules, secondly to cut edges connecting cities between inside and outside the zone, thirdly to exchange edges inside the zone of one parent and those of the other parent, and lastly to reconnect sub-tours and isolated cities, which come about in the 3rd step mentioned above, so as to construct a new tour of TSP. The method is compared with conventional three crossovers; those are the Maximal Preservative Crossover, the Greedy Sub-tour Crossover and the Edge Recombination Crossover, and evaluated from the viewpoints of tour quality and CPU time. Ten benchmarks are selected from the well-known TSP website of Georgia Institute of Technology, whose names are xqf131, xqg237, ..., sra104815. The experiments are performed ten times for each crossover and each benchmark and show that the Z-Cross succeeds in finding better solution and running faster than the conventional methods. Six benchmarks with size from 39,603 to 104,815 cities are selected from the TSP website and challenged the records of tour lengths. The Z-Cross betters the record of the problem rbz43748 and approaches to solutions less than only 0.02% over the known best solutions for five instances.

This correspondence describes a hybrid genetic algorithm (GA) to find high-quality solutions for the traveling salesman problem (TSP). The proposed method is based on a parallel implementation of a multipopulation steady-state GA involving local search heuristics. It uses a variant of the maximal preservative crossover and the double-bridge move mutation. An effective implementation of the Lin-Kernighan heuristic (LK) is incorporated into the method to compensate for the GA's lack of local search ability. The method is validated by comparing it with the LK-Helsgaun method (LKH), which is one of the most effective methods for the TSP. Experimental results with benchmarks having up to 316228 cities show that the proposed method works more effectively and efficiently than LKH when solving large-scale problems. Finally, the method is used together with the implementation of the iterated LK to find a new best tour (as of June 2, 2003) for a 1904711-city TSP challenge.

Distortion of the waveform on printed circuit board (PCBs) is a serious problem in higher-frequency signals transmission. To overcome this problem, we have already proposed segmental transmission line (STL). The STL divides transmission lines into multiple segments with different line widths, those are adjusted to reshape the signal waveform by superposition of reflected waves occurring at segment boundaries. In the previous work, we reshaped the waveform at only one point in the transmission line connected with a device at a time. This paper expands the method to reshape the waveform at two points of the devices at a time. We design a DIMM (dual in-line memory module) clock-line for high-speed computers using our new method, and show effectiveness of the method.

Waveform distortion is a serious problem in higher-frequency signals on printed circuit boards (PCB). In order to overcome this problem, the segmental transmission line (STL) has already been proposed. However, the STL requires segments of wide-range widths. The wide-range line-width impedes higher optimization of waveforms and it also causes cost-increment in the PCB manufacturing. In this paper, we propose a novel STL with variable length segments in order to overcome the difficulties in previous work. We also develop a design methodology using a GA to determine the parameters for the proposed STL. We apply our new STL to the clock line in the actual PCB, and show its effectiveness compared with the previously proposed STL.

In previous work, we have proposed a parallel hybrid genetic algorithm (PHGA) which can find high quality solution from the mathematical viewpoint for the multiple protein sequence alignment. We present new improvements to the PHGA. Local alignment information is added to the weighted sum-of-pairs objective function to achieve better alignment from the biological viewpoint. We also extend our method to run in parallel on a cluster of machines instead of a multi-processor machine to speed it up.

Ensuring the signal integrity even under pico-second switching-time in PCBs (printed circuit boards) as well as in VLSI chips is one of the most important goals in a PCB design. To achieve the goal, we propose a novel methodology of the PCB trace design in which the traces are regarded as segmental-transmission-lines of individual impedances. Also, the impedances are optimized by minimizing signal distortions due to multiple reflections in the transmission lines through genetic algorithms. Our design system shows excellent experimental results which achieves almost ideal signal wave forms without any signal distortion.

Reconfigurable architecture for the probabilistic neural network (PNN) is proposed and the PNN hardware system is developed using FPGAs. In the system, preprocessing circuits as well as the PNN can be reconfigured adapting each task. Potential performance of the PNN cannot be brought out until the total reconfigurability including the preprocessing is achieved. The developed system shows high recognition accuracy with high processing speed for some image recognition tasks.

This paper presents a parallel hybrid genetic algorithm (GA) for solving sum-of-pairs multiple protein sequence alignment. The method is based on a multiple population GENITOR-type GA and involves local search heuristics. It is then extended to parallel to exploit the benefit of a multiprocessor system. Benchmarks from the BAliBASE library are used to validate the method.

Recently, many defect compensation methods have been proposed for feedforward neural networks implemented in hardware devices. However, there are few accurate quantitative comparisons with the performance of these defect compensation methods. In this paper, we compare the following three defect compensation methods; partial retraining (PR) scheme, whole network backpropagation (BP) retraining and FT (fault-tolerant) BP method. The BP algorithm and PR scheme retrain the neural network after defects have occurred. The FTBP method tries to obtain the weights those are robust for the defects. We can say that both the BP algorithm and PR scheme are cure-type compensation methods and the FTBP method is a precaution-type compensation method. We compare the average recognition rate, average training time and the generalization ability among these three methods in detail. The experiments show that the whole network retraining by the BP algorithm has the highest reliability on the XOR problem and face image recognition problem on the neural networks with a single broken link defect and two broken link defects.

Evolvable reasoning hardware and its genetic algorithm-based design methodology is proposed. In the evolvable reasoning hardware, each reasoning task's case database is transformed into truth tables, which are evolved to obtain generalization capability through genetic algorithms. Circuits are synthesized from the evolved truth tables. Because the parallelism in each task can be embedded directly in the circuits by the direct hardware implementation of the case database, the evolved reasoning hardware provides high speed reasoning with small circuit size. We develop a prototype of the reasoning hardware and apply it to the exon/intron boundary prediction that is one of the most important tasks in the genome informatics.

An extension of the kernel-based pattern recognition method using a genetic algorithm is proposed. The method is suited to evolvable pattern recognition hardware using FPGAs. In the conventional method one common kernel function is used in the superposition to make discrimination functions. In the extended method each region of the kernel function is optimized individually. For the kernel-region optimization we use a genetic algorithm to solve a large combinatorial problem almost impossible to solve using any brute-force search. A chromosome represents the kernel region in an n-dimensional pattern space, and each locus corresponds to one of the candidates (genes) for an edge length of the kernel region. We have applied the extended method to a sonar spectrum recognition problem and obtained a recognition accuracy of 83.9%, which is much higher than the 62.0% obtained using the conventional kernel-based method and is also better than 82.7% obtained using the nearest neighbor method and the 83.0% obtained using a neural network (backpropagation algorithm). We have analyzed the individually optimized kernel regions and shown that the GA process automatically extracts features in the patterns and embeds the features in the kernel regions.

A fast method of GP based model building for time series prediction is proposed. The method involves two newly-devised techniques. One is regarding determination of model parameters: only functional forms are inherited from their parents with genetic programming, but model parameters are not inherited. They are optimized by a backpropagation-like algorithm when a child (model) is newborn. The other is regarding mutation: nodes which require a different number of edges, can be transformed into different types of nodes through mutation. This operation is effective at accelerating complicated functions e.g. seismic ground motion. The method has been applied to a typical benchmark of time series and many real world problems.

In this paper, we present a new genetic-algorithm-based design methodology for reasoning VLSI chips, called as LoDETT (logic design with the evolved truth table). In LoDETT, each task's case database is transformed into truth tables, which are evolved to obtain generalization capability (i.e. rules behind the past cases) through genetic algorithms. Digital circuits are synthesized from the evolved truth-tables. Parallelism in each task can be embedded directly in the circuits by the direct hardware implementation of the case database. We applied LoDETT to the English pronunciation reasoning (EPR) problem, resulting in a GATalk chip. A GATalk chip has been designed with about 270K gates, and its reasoning time is about 100 ns for each phoneme. A prototype of the GATalk chip has been implemented using Xilinx XC4010 FPGA chips. It achieved a reasoning accuracy of 81.9% which is almost the same accuracy as NETTalk in neural networks and MBRTalk in parallel AI.

We discuss a general method to forecast movements of the chaos. The method is based on functions of multi layer neural networks and a recurrent representation of functions. We are sure that forecasting of the chaos is an important problem. Movements of the chaos are extremely complex, and similar to natural phenomena. The forecasting for the chaos has been studied based on the embedding theory. They are called "one-step prediction". The embedding theory is effective and useful, and the results are accurate. But we wish to know long-term futures in practical objects. We need to take one step forward from the embedding theory. Our target is the long-term forecasting.

A method for building time series prediction model using genetic programming is proposed. The construction of prediction models consists of two stages. The first stage composes the most appropriate functional form with genetic programming. The second stage fixes optimal parameters involved in the composite function with a backpropagation-like algorithm. The second stage can be recognized as a local search, which is a powerful tool to accelerate the evolving speed of GP and GA. The method is applied to typical time series and some real world prediction problems. Results of computer generated chaotic time series were compared to those of neural network based and autoregressive predictions. The superiority of the proposed method is demonstrated in the results of these experiments.

An evolutionary design methodology for sonar spectrum recognition chip is proposed and the prototype chip is developed. In the design, sonar spectrum data are transformed to truth-tables and the truth-tables are evolved to obtain generalization capability by using genetic algorithms. Digital circuits are designed by synthesizing the evolved truth-tables. Parallelism in the data can be embedded in the circuits directly by this direct hardware implementation technique of the sonar spectrum data. The circuit size of the developed chip was 4,134 gates, and this was small enough to be implemented onto a standard FPGA (field programmable gate array) chip. Operation speed of the chip was less than 1.0 micro-second per spectrum. Moreover the chip achieved the recognition accuracy of 91.7%, which was higher than those in the backpropagation and the k-NN algorithm.

In this paper, we propose a parallel backpropagation algorithm using the genetic algorithm to reduce the learning time to reach the optimal solution. Genetic algorithm is used in parallel previous to the parallel backpropagation regarding the set of weights in the feedforward neural network as chromosomes, and well-evolved chromosomes (sets of excellent initial weights) are used in the parallel backpropagation. Performance of the proposed algorithm was evaluated experimentally in 5-bit and 8-bit parity problems using the massively parallel computer CP-PACS. The learning speeds were about 3 times and about 7 times faster than those of the simple parallel backpropagation in the 5-bit and the 8-bit parity problems, respectively.

This paper proposes a multi-modal neural network model composed of a pre-processing module and a post-processing module in order to enhance the nonlinear characteristics of neural networks. The pre-processing module is made of Chebyschev polynomials and transforms input data into spectra. The post-processing module is made of multilayer neural network and associates according to the spectral inputs generated by the pre-processing module. Fundamental experiments upon pattern recognition and functional approximation and experiments applying the method to a control problem result that the method enable one to build small scale neural model for nonlinear systems and to perform learning in shorter time.