This paper presents new encoding methods for the binary genetic algorithm (BGA) and new converting methods for the real-coded genetic algorithm (RCGA). These methods are developed for the specific case in which some parameters have to be searched in wide ranges since their actual values are not known. The oversampling effect which occurs at large values in the wide range search are reduced by adjustment of resolutions in mantissa and exponent of real numbers mapped by BGA. Owing to an intrinsic similarity in chromosomal operations, the proposed encoding methods are also applied to RCGA with remapping (converting as named above) from real numbers generated in RCGA. A simple probabilistic analysis and benchmark with two ill-scaled test functions are carried out. System identification of a simple electrical circuit is also undertaken to testify effectiveness of the proposed methods to real world problems. All the optimization results show that the proposed encoding/converting methods are more suitable for problems with ill-scaled parameters or wide parameter ranges for searching.
Neelakantam VENKATARAYALU Yeow-Beng GAN Le-Wei LI
Numerical Stability of the Finite Element/Finite Difference Time Domain Hybrid algorithm is dependent on the hybridization mechanism adopted. A framework is developed to analyze the numerical stability of the hybrid time marching algorithm. First, the global iteration matrix representing the hybrid algorithm following different hybridization schemes is constructed. An analysis of the eigenvalues of this iteration matrix reveals the stability performance of the algorithm. Thus conclusions on the performance with respect to numerical stability of the different schemes can be arrived at. Further, numerical experiments are carried out to verify the conclusions based on the stability analysis.
In many electromagnetic field problems, matrix equations were always deduced from using the method of moment. Among these matrix equations, some of them might require a large amount of computer memory storage which made them unrealistic to be solved on a personal computer. Virtually, these matrices might be too large to be solved efficiently. A fast algorithm based on a Toeplitz matrix solution was developed for solving a bordered Toeplitz matrix equation arising in electromagnetic problems applications. The developed matrix solution method can be applied to solve some electromagnetic problems having very large-scale matrices, which are deduced from the moment method procedure. In this paper, a study of a computationally efficient order-recursive algorithm for solving the linear electromagnetic problems [Z]I = V, where [Z] is a Toeplitz matrix, was presented. Upon the described Toeplitz matrix algorithm, this paper derives an efficient recursive algorithm for solving a bordered Toeplitz matrix with the matrix's major portion in the form of a Toeplitz matrix. This algorithm has remarkable advantages in reducing both the number of arithmetic operations and memory storage.
Hiromitsu AOYAMA Hiroyuki ARAI
MBF (Microwave Beam Forming) antennas are beam forming antennas that perform pattern control in RF, for a low-cost design suitable for mobile terminals. An MBF antenna has only a single output port, since this antenna consists of an array antenna, microwave phase shifters, and a power combiner. Because of this simple configuration, MBF antennas cannot adopt conventional beam forming algorithms that require both phase and amplitude control, and signal observation of each antenna element. In this paper, mutual coupling matrix estimation and null forming methods are presented for MBF antennas. It is shown that the mutual coupling matrix can be estimated by changing the antenna weight instead of signal observation of each antenna element. It is also shown that phase-only null forming, including mutual coupling effect, can be done by the optimum phase perturbations. Numerical and experimental results show the performance of these algorithms.
Vincenzo ERAMO Marco LISTANTI Nicola CAIONE Igor RUSSO Giuseppe GASPARRO
Routing protocols are a critical component in IP networks. Among these, the Open Shortest Path First (OSPF) has been a widely used routing protocol in IP networks for some years. Beside dedicated hardware, a great interest on routing systems based on open software is raising among Internet Service Providers. Many open source implementations of this protocol have been developed, among which GNU Zebra is one of the most complete. In this paper we perform a study of the performances of the Shortest Path First computation in GNU Zebra, as prescribed by the Internet Engineering Task Force, and we provide a comparison between a Cisco 2621 access router and a PC-based router equipped with routing software GNU Zebra. Moreover we describe a set of modifications made on the GNU Zebra code in order to optimize some processes, whose algorithms were not efficient and whose experimental measures had showed a lack of optimization, thus finally obtaining performances better than the one measured on commercial systems.
Shin-ichiro KAWANO Shin-ichi NAKANO
In this paper we give an algorithm to generates all series-parallel graphs with at most m edges. This algorithm generate each series-parallel graph in constant time on average.
Sayaka KAMEI Hirotsugu KAKUGAWA
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate a self-stabilizing distributed approximation for the minimum k-dominating set (KDS) problem in general networks. The minimum KDS problem is a generalization of the well-known dominating set problem in graph theory. For a graph G = (V,E), a set Dk
A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.
"Can one walk to infinity on Gaussian primes taking steps of bounded length?" We adopted computational techniques to probe into this open problem. We propose an efficient method to search for the farthest point reachable from the origin, which can be parallelized easily, and have confirmed the existence of a moat of width k =, whereas the best previous result was k = due to Gethner et al. The amount of computation needed for k = is about 5000 times larger than that for k =. A refinement of Vardi's estimate for the farthest distance reachable from the origin is proposed. The proposed estimate incorporates discreteness into Vardi's that is based on percolation theory.
In this paper, the false-peaks problem of the conventional correlation-based video tracking is investigated using a simple mathematical analysis. To reduce the false detection problem, a selective-attention correlation measure is proposed. The problem with the conventional correlation measures is that all pixels in the reference block image are equally treated in the computation of the correlation measures irrespective of target or background pixels. Therefore, the more the reference block image includes background pixels, the higher probability of false-peaks is introduced due to the correlation between the background pixels of the reference block and those of the input search image. The proposed selective-attention correlation measure has different consideration according to target and background pixels in the matching process, which conform with the selective-attention property of human visual system. Various computer simulations validated these analyses and confirmed that the proposed selective-attention measure is effective to reduce considerably the probability of the false-peaks.
Nowadays, customers spend much time and effort in finding the best suitable goods since more and more information is placed on-line. To save their time and effort in searching the goods they want, a customized recommender system is required. In this paper we present an improved neighbor selection algorithm that exploits a graph approach. The graph approach allows us to exploit the transitivity of similarities. The algorithm searches more efficiently for set of influential customers with respect to a given customer. We compare the proposed recommendation algorithm with other neighbor selection methods. The experimental results show that the proposed algorithm outperforms other methods.
Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE
The (k + δ)-edge-connectivity augmentation problem for a specified set of vertices ((k + δ)ECA-SV) is defined as follows: "Given an undirected graph G =(V,E), a specified set of vertices Γ
Bum-Jik LEE Jin-Bae PARK Young-Hoon JOO
A new interacting multiple model (IMM) algorithm using intelligent input estimation (IIE) is proposed for maneuvering target tracking. In the proposed method, the acceleration level for each sub-model is determined by IIE-the estimation of the unknown target acceleration by a fuzzy system using the relation between the residuals of the maneuvering filter and the non-maneuvering filter. The genetic algorithm (GA) is utilized to optimize a fuzzy system for a sub-model within a fixed range of target acceleration. Then, multiple models are represented as the acceleration levels estimated by these fuzzy systems, which are optimized for different ranges of target acceleration. In computer simulation for an incoming anti-ship missile, it is shown that the proposed method has better tracking performance compared with the adaptive interacting multiple model (AIMM) algorithm.
Hua ZHENG Shingo OMURA Jiro UCHIDA Koichi WADA
In this paper, we focus on the problem that in an ad hoc network, how to send a message securely between two users using the certificate dispersal system. In this system, special data called certificate is issued between two users and these issued certificates are stored among the network. Our final purpose on this certificate dispersal problem is to construct certificate graphs with lower dispersability cost which indicates the average number of certificates stored in each node in an ad hoc network. As our first step, when a certificate graph is given, we construct two efficient certificate dispersal algorithms for strongly connected graphs and directed graphs in this paper. We can show that for a strongly connected graph G =(V, E) and a directed graph H =(V ′, E ′), new upper bounds on dispersability cost on the average number of certificates stored in one node are O(DG +|E|/|V|) and O(pG dmax +|E ′|/|V ′|) respectively, where DG is the diameter of G, dmax is the maximum diameter of strongly connected components of H and pG is the number of strongly connected components of H. Furthermore, we give some new lower bounds for the problem and we also show that our algorithms are optimal for several graph classes.
Network survivability is one of the most pivotal issues in optical WDM networks. In particular, if a conduit is cut, approximately 16 terabits per millisecond can be lost in recent technology. A huge loss even by a single conduit failure fatally damages the performance and operation of the whole network. In this paper, we propose a new heuristic algorithm, called the Generalized Minimum-Cost (GMC) selection algorithm, to choose a pair of working and backup path which firstly minimizes total number of required wavelengths of working and backup path and secondly distributes lightpath request traffic into whole network links, if there are several pairs to require the same number of minimum wavelengths, in order to achieve load-balancing effect. GMC selection algorithm contains several formulas to get Working and Backup path Reservation Cost (WBRC) which can be obtained through heuristic GMC function. By using WBRC, our GMC selection algorithm achieves superior performance compared to the current Combined Min-Cost (CMC) selection algorithm and random selection algorithm in terms of the amount of wavelength consumption and blocked lightpath requests, especially on the relatively less-connected New Jersey LATA and 28-node US networks. Furthermore, we suggest a maximum number of non-blocked lightpath requests against single link failure in simulated networks for network operators to consider acceptable maximum traffic on their networks, so that they can provide 100% restoration capability in a single link failure without lightpath request blocking. We also analyze the complexity of the GMC selection algorithm and verify that the complexity of the GMC selection algorithm is lower than that of the CMC selection algorithm if the number of lightpath requests is sufficiently large.
Nobuo FUNABIKI Jun KAWASHIMA Toru NAKANISHI Kiyohiko OKAYAMA Teruo HIGASHINO
The wavelength-division multiplexing (WDM) technology has been popular in communication societies for providing very large communication bands by multiple lightpaths with different wavelengths on a single optical fiber. Particularly, a double-ring optical network architecture based on the packet-over-WDM technology such as the HORNET architecture, has been extensively studied as a next generation platform for metropolitan area networks (MANs). Each node in this architecture is equipped with a wavelength-fixed optical-drop and a fast tunable transmitter so that a lightpath can be established between any pair of nodes without wavelength conversions. In this paper, we formulate the optical-drop wavelength assignment problem (ODWAP) for efficient wavelength reuse under heterogeneous traffic in this network, and prove the NP-completeness of its decision problem. Then, we propose a simple heuristic algorithm for the basic case of ODWAP. Through extensive simulations, we demonstrate the effectiveness of our approach in reducing waiting times for packet transmissions when a small number of wavelengths are available to retain the network cost for MANs.
The aim of this work is to investigate the possibility of designing zero-knowledge identification schemes based on hard-on-average problems. It includes a new two-party identification protocol whose security relies on a discrete mathematics problem classified as DistNP-Complete under the average-case analysis, the so-called Distributional Matrix Representability Problem. Thanks to the use of the search version of the mentioned problem, the zero-knowledge property is formally proved by black-box simulation, and consequently the security of the proposed scheme is actually guaranteed. Furthermore, with the proposal of a new zero-knowledge proof based on a problem never used before for this purpose, the set of tools for designing cryptographic applications is enlarged.
Let G = (V,E) be a connected graph such that each edge e ∈ E and each vertex v ∈ V are weighted by nonnegative reals w(e) and h(v), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X1,X2,...,Xp of V and a set of p subtrees T1,T2,...,Tp such that each Ti contains Xi∪{r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in Ti and the weights of vertices in Xi. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X1,X2,...,Xp} of V and a set of p cycles C1,C2,...,Cp such that Ci contains Xi∪{r} so as to minimize the maximum cost of the cycles, where the cost of Ci is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p+1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p+1))-approximation algorithm to the MRCC with a metric (G,w).
The finite difference time domain (FDTD) method has been developed in tandem with the progress of computer technology since K. S. Yee applied it to the analysis of an electromagnetic problem in 1966. The FDTD method is widely recognized as a powerful computational tool for analyzing electromagnetic problems involving complex geometries, such as antennas, microwave and optical waveguides and interaction between antennas and the human body. The commercial electromagnetic simulators based on the FDTD are also being developed very actively because users are able to trace temporal electromagnetic behaviors and to easily obtain a practical level of accuracy. However, the user must understand the principle of the method in order to use the simulator efficiently. In this paper, the basic concept and the principle of the FDTD method are reviewed for beginners, including graduate course students, rather than specialists in this discipline. Several recent topics concerning electromagnetic and antenna problems are also introduced.
An efficient computational Zero-Knowledge Proof of Knowledge whose security relies on the NP-completeness of the Independent Set Problem is presented here. The proposed algorithm is constructed from a bit commitment scheme based on the hardness of the Discrete Logarithm Problem, which guarantees the fulfillment of soundness, completeness and computational zero-knowledge properties, and allows avoiding the use of the Graph Isomorphism Problem, which is present in every known Zero-Knowledge Proofs for the Independent Set Problem.