An automated analog circuit synthesis based on reuse of topological features of 'prototype circuits' is proposed. The prototype circuits are designed by humans and suggested to the synthesis system as hints of configurations of new analog circuits to be synthesized by the system. The connections of elements in analog circuits are not generally systematic, but they would have some similarities to a circuit which has similar behaviors or functionalities. In the proposed process, the information on circuit connections is stored as sub-circuits extracted from the prototype circuits. And then, genetic algorithm is used to search for an optimum combination of the sub-circuits that achieves the desired electronic specifications. The combinations of sub-circuits are performed with a novel technique where the terminals of the sub-circuits are shared. The capabilities of the proposed method are demonstrated through an example of the synthesis.
Tamami MARUYAMA Toshikazu HORI
This paper proposes the Vector Evaluated GA-ICT (VEGA-ICT), a novel design method that employs the Genetic Algorithm (GA) to obtain the optimum antenna design. GA-ICT incorporates an arbitrary wire-grid model antenna to derive the optimum solution without any basic structure or limitation on the number of elements by merely optimizing an objective function. GA-ICT comprises the GA and an analysis method, the Improved Circuit Theory (ICT), with the following characteristics. (1) To achieve optimization of an arbitrary wire-grid model antenna without a basic antenna structure, the unknowns of the ICT are directly assigned to variables of the GA in the GA-ICT. (2) To achieve a variable number of elements, duplicate elements generated by using the same feasible region are deleted in the ICT. (3) To satisfy all complex design conditions, the GA-ICT generates an objective function using a weighting function generated based on electrical characteristics, antenna configuration, and size. (4) To overcome the difficulty of convergence caused by the nonlinearity of each term in the objective function, GA-ICT adopts a vector evaluation method. In this paper, the novel GA-ICT method is applied to downsize sector antennas. The calculation region in GA-ICT is reduced by adopting cylindrical coordinates and a periodic imaging structure. The GA-ICT achieves a 30% reduction in size compared to the previously reported small sector antenna, MS-MPYA, while retaining almost the same characteristics.
A plasma display panel (PDP) represents gray levels by the pulse number modulation technique that results in undesirable dynamic false contours on moving images. Among the various techniques proposed for the reduction of dynamic false contours, the optimization of the subfield pattern can be most easily implemented without the need for any additional dedicated hardware or software. In this paper, a systematic method for selecting the optimum subfield pattern is presented. In the proposed method, a subfield pattern that minimizes the quantitative measure of the dynamic false contour on the predefined test image is selected as the optimum pattern. The selection is made by repetitive calculations based on a genetic algorithm. Quantitative measure of the dynamic false contour calculated by simulation on the test image serves as a criterion for minimization by the genetic algorithm. In order to utilize the genetic algorithm, a structure of a string is proposed to satisfy the requirements for the subfield pattern. Also, three genetic operators for optimization, reproduction, crossover, and mutation, are specially designed for the selection of the optimum subfield pattern.
Masanori NATSUI Takafumi AOKI Tatsuo HIGUCHI
This letter presents an efficient graph-based evolutionary optimization technique, and its application to the transistor-level design of multiple-valued arithmetic circuits. The key idea is to introduce "circuit graphs with colored terminals" for modeling heterogeneous networks of various components. The potential of the proposed approach is demonstrated through experimental synthesis of a radix-4 signed-digit (SD) full adder circuit.
Tianxu ZHAO Yue HAO Yong-Chang JIAO
An optimal allocation model for the sub-processing-element (sub-PE) level redundancy is developed, which is solved by the genetic algorithms. In the allocation model, the average defect density D and the parameter δ are also considered in order to accurately analyze the element yield, where δ is defined as the ratio of the support circuit area to the total area of a PE. When the PE's area is imposed on the constraint, the optimal solutions of the model with different D and δ are calculated. The simulation results indicate that, for any fixed average defect density D, both the number of the optimal redundant sub-circuit added into a PE and the PE's yield decrease as δ increases. Moreover, for any fixed parameter δ, the number of the optimal redundant sub-circuit increases, while the optimal yield of the PE decreases, as D increases.
Moritoshi YASUNAGA Taro NAKAMURA Ikuo YOSHIHARA Jung Hwan KIM
We propose the kernel-based pattern recognition hardware and its design methodology using the genetic algorithm. In the proposed design methodology, pattern data are transformed into the truth tables and the truth tables are evolved to represent kernels in the discrimination functions for pattern recognition. The evolved truth tables are then synthesized to logic circuits. Because of this data direct implementation approach, no floating point numerical circuits are required and the intrinsic parallelism in the pattern data set is embedded into the circuits. Consequently, high speed recognition systems can be realized with acceptable small circuit size. We have applied this methodology to the image recognition and the sonar spectrum recognition tasks, and implemented them onto the newly developed FPGA-based reconfigurable pattern recognition board. The developed system demonstrates higher recognition accuracy and much faster processing speed than the conventional approaches.
Jie ZHOU Yoichi SHIRAISHI Ushio YAMAMOTO Yoshikuni ONOZATO Hisakazu KIKUCHI
In this paper, we propose an approach to solve the power control issue in a DS-CDMA cellular system using genetic algorithms (GAs). The transmitter power control developed in this paper has been proven to be efficient to control co-channel interference, to increase bandwidth utilization and to balance the comprehensive services that are sharing among all the mobiles with attaining a common signal-to-interference ratio(SIR). Most of the previous studies have assumed that the transmitter power level is controlled in a constant domain under the assumption of uniform distribution of users in the coverage area or in a continuous domain. In this paper, the optimal centralized power control (CPC) vector is characterized and its optimal solution for CPC is presented using GAs in a large-scale DS-CDMA cellular system under the realistic context that means random allocation of active users in the entire coverage area. Emphasis is put on the balance of services and convergence rate by using GAs.
This paper presents an automatic synthesis method of active analog circuits that uses evolutionary search and employs some topological features of analog integrated circuits. Our system firstly generates a set of circuits at random, and then evolves their topologies and device sizing to fit an environment which is formed by the fitness function translated from the electrical specifications of the circuit. Therefore expert knowledge about circuit topologies and sizing are not needed. The capability of this method is demonstrated through experiments of automatic synthesis of CMOS operational amplifiers.
Yoshinori KISHIKAWA Shozo TOKINAGA
This paper deals with the approximation of multi-dimensional chaotic dynamics by using the multi-stage fuzzy inference system. The number of rules included in multi-stage fuzzy inference systems is remarkably smaller compared to conventional fuzzy inference systems where the number of rules are proportional to an exponential of the number of input variables. We also propose a method to optimize the shape of membership function and the appropriate selection of input variables based upon the genetic algorithm (GA). The method is applied to the approximation of typical multi-dimensional chaotic dynamics. By dividing the inference system into multiple stages, the total number of rules is sufficiently depressed compared to the single stage system. In each stage of inference only a portion of input variables are used as the input, and output of the stage is treated as an input to the next stage. To give better performance, the shape of the membership function of the inference rules is optimized by using the GA. Each individual corresponds to an inference system, and its fitness is defined by using the prediction error. Experimental results lead us to a relevant selection of the number of input variables and the number of stages by considering the computational cost and the requirement. Besides the GA in the optimization of membership function, we use the GA to determine the input variables and the number of input. The selection of input variable to each stage, and the number of stages are also discussed. The simulation study for multi-dimensional chaotic dynamics shows that the inference system gives better prediction compared to the prediction by the neural network.
Masahide ABE Masayuki KAWAMATA
This paper proposes distributed evolutionary digital filters (EDFs) as an improved version of the original EDF. The EDF is an adaptive digital filter which is controlled by adaptive algorithm based on evolutionary computation. In the proposed method, a large population of the original EDF is divided into smaller subpopulations. Each sub-EDF has one subpopulation and executes the small-sized main loop of the original EDF. In addition, the distributed algorithm periodically selects promising individuals from each subpopulation. Then, they migrate to different subpopulations. Numerical examples show that the distributed EDF has a higher convergence rate and smaller steady-state value of the square error than the LMS adaptive digital filter, the adaptive digital filter based on the simple genetic algorithm and the original EDF.
Hernan AGUIRRE Kiyoshi TANAKA Tatsuo SUGIMURA Shinjiro OSHITA
A halftoning technique that uses a simple GA has proven to be very effective to generate high quality halftone images. Recently, the two major drawbacks of this conventional halftoning technique with GAs, i.e. it uses a substantial amount of computer memory and processing time, have been overcome by using an improved GA (GA-SRM) that applies genetic operators in parallel putting them in a cooperative-competitive stand with each other. The halftoning problem is a true multiobjective optimization problem. However, so far, the GA based halftoning techniques have treated the problem as a single objective optimization problem. In this work, the improved GA-SRM is extended to a multiobjective optimization GA to simultaneously generate halftone images with various combinations of gray level precision and spatial resolution. Simulation results verify that the proposed scheme can effectively generate several high quality images simultaneously in a single run reducing even further the overall processing time.
Nyakoe George NYAUMA Makoto OHKI Suichiro TABUCHI Masaaki OHKITA
The ultrasonic wave is widely used for acquiring perceptual information necessary for indoor/outdoor navigation of mobile robots, where the system is implemented as a sound navigation and ranging system (sonar). A robot equipped with multiple ultrasonic sonars is likely to exhibit undesirable operation due to erroneous measurements resulting from cross-talk among the sonars. Each sonar transmits and receives a pulse-modulated ultrasonic wave for measuring the range and identifying its own signal. We propose a technique for generating pulse patterns for multiple concurrently operated ultrasonic sonars. The approach considers pulse-pattern generation as a combinatorial optimization problem which can be solved by a genetic algorithm (GA). The aim is to acquire a pulse pattern satisfying certain conditions in order to avoid cross-talk or keep the probability of erroneous measurement caused by cross-talk low. We provide a method of genotype coding for the generation of the pulse pattern. Furthermore, in order to avoid a futile search encountered when the conventional technique is used, we propose an improved genotype coding technique that yields considerably different results from those of the conventional technique.
Beatrice M. OMBUKI Morikazu NAKAMURA Zensho NAKAO Kenji ONAGA
This paper presents a genetic algorithm for designing at minimum cost a two-connected network topology such that the shortest cycle (referred to as a ring) to which each edge belongs does not exceed a given maximum number of hops. The genetic algorithm introduces a solution representation in which constraints such as connectivity and ring constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided thus resulting in increased efficiency. Experimental evaluation shows the effectiveness of the proposed GA.
This paper aims at improving effectiveness of previously proposed hybrid priority lists, {L*i=LdLsi}, that are applied in nonpreemptive 2-processor scheduling of general acyclic SWITCH-less program nets, where Ld and Lsi are dynamic and static priority lists respectively. Firstly, we investigate the effectiveness of Ld through experiments. According to the experimental results, we reconstruct Ld to propose its improved list L1d. Then analyzing the construction methodology of the static priority lists {Lsi}, we propose a substituted list L2d by taking into account of the factor: remaining firing numbers of nodes. Finally, we combine a part of L1d and L2d to propose a new priority list L**. Through scheduling simulation on 400 program nets, we find the new priority list L** can generate shorter schedules, close to ones of GA (Genetic Algorithm) scheduling that has been shown exceedingly effective but costing much computation time.
Jun INAGAKI Miki HASEYAMA Hideo KITAJIMA
This paper presents a method of determining a fitness function in a genetic algorithm for routing the shortest route via several designated points. We can search for the optimum route efficiently by using the proposed fitness function and its validity is verified by applying it to the actual map data.
ChangYoon LEE Mitsuo GEN Way KUO
In this paper, we examine an optimal reliability assignment/redundant allocation problem formulated as a nonlinear mixed integer programming (nMIP) model which should simultaneously determine continuous and discrete decision variables. This problem is more difficult than the redundant allocation problem represented by a nonlinear integer problem (nIP). Recently, several researchers have obtained acceptable and satisfactory results by using genetic algorithms (GAs) to solve optimal reliability assignment/redundant allocation problems. For large-scale problems, however, the GA has to enumerate a vast number of feasible solutions due to the broad continuous search space. To overcome this difficulty, we propose a hybridized GA combined with a neural-network technique (NN-hGA) which is suitable for approximating optimal continuous solutions. Combining a GA with the NN technique makes it easier for the GA to solve an optimal reliability assignment/redundant allocation problem by bounding the broad continuous search space by the NN technique. In addition, the NN-hGA leads to optimal robustness and steadiness and does not affect the various initial conditions of the problems. Numerical experiments and comparisons with previous results demonstrate the efficiency of our proposed method.
A minimum classification error formulation based on genetic algorithm is proposed for discriminative training of the bigram language model. Results of Chinese dialect identification were reported which demonstrate performance improvement with use of the genetic algorithm over the generalized probabilistic descent algorithm.
An automated method for cryptanalysis of DFT-based analog speech scramblers is presented through statistical estimation treatments. In the proposed system, the ciphertext only attack is formulated as a combinatorial optimization problem leading to a search for the most likely key estimate. For greater efficiency, we also explore the benefits of genetic algorithm to develop an estimation method which takes into account the doubly stochastic characteristics of the underlying keyspace. Simulation results indicate that the global explorative properties of genetic algorithms make them very effective at estimating the most likely permutation and by using this estimate significant amount of the intelligibility can be recovered from the ciphertext following the attack on DFT-based speech scramblers.
Barry SHACKLEFORD Etsuko OKUSHI Mitsuhiro YASUDA Hisao KOIZUMI Katsuhiko SEO Hiroto YASUURA
The problem of synthesizing a minimum-cost logic network is formulated for a genetic algorithm (GA). When benchmarked against a commercial logic synthesis tool, an odd parity circuit required 24 basic cells (BCs) versus 28 BCs for the design produced by the commercial system. A magnitude comparator required 20 BCs versus 21 BCs for the commercial system's design. Poor temporal performance, however, is the main disadvantage of the GA-based approach. The design of a hardware-based cost function that would accelerate the GA by several thousand times is described.
Ahmad CHELDAVI Gholamali REZAI-RAD
Based on genetic algorithm (GA) in this paper we present a simple method to extract distributed circuit parameters of a multiple coupled nonuniform microstrip transmission lines from it's measured or computed S-parameters. The lines may be lossless or lossy, with frequency dependent parameters. First a sufficient amount of information about the system is measured or computed over an specified frequency range. Then this information is used as an input for a GA to determine the inductance and capacitance matrices of the system. The theory used for fitness evaluation is based on the steplines approximation of the nonuniform transmission lines and quasi-TEM assumptions. Using steplines approximation the system of coupled nonuniform transmission lines is subdivided into arbitrary large number of coupled uniform lines (steplines) with different characteristics. Then using modal decomposition method the system of coupled partial differential equations for each step is decomposed to a number of uncoupled ordinary wave equations which are then solved in frequency-domain.