This paper develops planar circuit filters consisting of arbitrarily-shaped conductor patches and slots on a conductor-backed dielectric substrate, which are designed by an optimization technique based on the genetic algorithm. The developed filter has multiple resonators and their mutual couplings in the limited space by using both sides of the substrate, so that its compactness is realized. We first demonstrate the effectiveness of the present filter structure from some design samples numerically and experimentally. Then as a practical application, we design compact UWB filters, and their filter characteristics are verified from the measurements.

In this paper, a new algorithm called TGA is introduced which defines the concept of time more naturally for the first time. A parameter called TimeToLive is considered for each chromosome, which is a time duration in which it could participate in the process of the algorithm. This will lead to keeping the dynamism of algorithm in addition to maintaining its convergence sufficiently and stably. Thus, the TGA guarantees not to result in premature convergence or stagnation providing necessary convergence to achieve optimal answer. Moreover, the mutation operator is used more meaningfully in the TGA. Mutation probability has direct relation with parent similarity. This kind of mutation will decrease ineffective mating percent which does not make any improvement in offspring individuals and also it is more natural. Simulation results show that one run of the TGA is enough to reach the optimum answer and the TGA outperforms the standard genetic algorithm.

In an undirected graph, the feedback vertex set (FVS for short) problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic. The FVS has applications to several areas such that combinatorial circuit design, synchronous systems, computer systems, VLSI circuits and so on. The FVS problem is known to be NP-hard on general graphs but interesting polynomial solutions have been found for some special classes of graphs. In this paper, we present an O(n2.68 + γn) time algorithm for solving the FVS problem on trapezoid graphs, where γ is the total number of factors included in all maximal cliques.

Recent works on MIMO receiver design were mainly focused on sphere decoding, which provides a trade-off between the performance and complexity by suitably choosing the “radius” or the number of candidates in the search space. Meanwhile, another approach, called poly-diagonalization and trellis detection, has been proposed to compromise the complexity and performance. In this paper, we compare various MIMO receiver algorithms in terms of both performance and complexity. The performance is evaluated in a frequency selective fading channel environment on the basis of orthogonal frequency division multiplexing with channel coding, for which the generation of soft decision values is crucial. The simulations show that the poly-diagonalization approach matches the performance of sphere decoding at similar computational complexity.

We study problems in computational geometry from the viewpoint of adaptive algorithms. Adaptive algorithms have been extensively studied for the sorting problem, and in this paper we generalize the framework to geometric problems. To this end, we think of geometric problems as permutation (or rearrangement) problems of arrays, and define the "presortedness" as a distance from the input array to the desired output array. We call an algorithm adaptive if it runs faster when a given input array is closer to the desired output, and furthermore it does not make use of any information of the presortedness. As a case study, we look into the planar convex hull problem for which we discover two natural formulations as permutation problems. An interesting phenomenon that we prove is that for one formulation the problem can be solved adaptively, but for the other formulation no adaptive algorithm can be better than an optimal output-sensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a kd-tree.

In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.

A two-dimensional filter for photonic label recognition system using time-to-space conversion and delay compensation was designed using Genetic-Algorithms (GA). For four-bit Binary Phase Shift Keying (BPSK) labels at 160 Gbit/s, contrast ratio of the output for eight different labels was improved by optimization of two-dimentional filtering. The contrast ratio of auto-correlation to cross-correlation larger than 2.16 was obtained by computer simulation. This value is 22% larger than the value of 1.77 with the previously reported system using matched filters.

Base station (BS) cooperation is a promising technique to suppress co-channel interference for cellular networks. However, practical limitations constrain the scale of cooperation, thus the network is divided into small disjoint BS cooperation groups, namely clusters. A decentralized scheme for BS cluster formation is proposed based on efficient BS negotiations, of which the feedback overhead per user is nearly irrelevant to the network size, and the number of iteration rounds scales very slowly with the network size. Simulations show that our decentralized scheme provides significant sum-rate gain over static clustering and performs almost the same as the existing centralized approach. The proposed scheme is well suited for large-scale cellular networks due to its low overhead and complexity.

Let T be a tree with n nodes, in which each edge is associated with a length and a weight. The density-constrained longest (heaviest) path problem is to find a path of T with maximum path length (weight) whose path density is bounded by an upper bound and a lower bound. The path density is the path weight divided by the path length. We show that both problems can be solved in optimal O(n log n) time.

For optimization problems with irregular and complex multimodal landscapes, Estimation of Distribution Algorithms (EDAs) suffer from the drawback of premature convergence similar to other evolutionary algorithms. In this paper, we propose an adaptive niching EDA based on Affinity Propagation (AP) clustering analysis. The AP clustering is used to adaptively partition the niches and mine the searching information from the evolution process. The obtained information is successfully utilized to improve the EDA performance by using a balance niching searching strategy. Two different categories of optimization problems are used to evaluate the proposed adaptive niching EDA. The first one is solving three benchmark functional multimodal optimization problems by a continuous EDA based on single Gaussian probabilistic model; the other one is solving a real complicated discrete EDA optimization problem, the HP model protein folding based on k-order Markov probabilistic model. Simulation results show that the proposed adaptive niching EDA is an efficient method.

This paper presents an approach for improving proximity and diversity in multiobjective evolutionary algorithms (MOEAs). The idea is to discover new nondominated solutions in the promising area of search space. It can be achieved by applying mutation only to the most converged and the least crowded individuals. In other words, the proximity and diversity can be improved because new nondominated solutions are found in the vicinity of the individuals highly converged and less crowded. Empirical results on multiobjective knapsack problems (MKPs) demonstrate that the proposed approach discovers a set of nondominated solutions much closer to the global Pareto front while maintaining a better distribution of the solutions.

In wireless sensor networks, preserving location privacy under successive inference attacks is extremely critical. Although this problem is NP-complete in general cases, we propose a dynamic programming based algorithm and prove it is optimal in special cases where the correlation only exists between p immediate adjacent observations.

The algebraic path problem (APP) is a general framework which unifies several solution procedures for a number of well-known matrix and graph problems. In this paper, we present a new 3-dimensional (3-D) orbital algebraic path algorithm and corresponding 2-D toroidal array processors which solve the nn APP in the theoretically minimal number of 3n time-steps. The coordinated time-space scheduling of the computing and data movement in this 3-D algorithm is based on the modular function which preserves the main technological advantages of systolic processing: simplicity, regularity, locality of communications, pipelining, etc. Our design of the 2-D systolic array processors is based on a classical 3-D2-D space transformation. We have also shown how a data manipulation (copying and alignment) can be effectively implemented in these array processors in a massively-parallel fashion by using a matrix-matrix multiply-add operation.

Evolvable hardware (EHW) is a new research field about the use of Evolutionary Algorithms (EAs) to construct electronic systems. EHW refers in a narrow sense to use evolutionary mechanisms as the algorithmic drivers for system design, while in a general sense to the capability of the hardware system to develop and to improve itself. Genetic Algorithm (GA) is one of typical EAs. We propose optimal circuit design by using GA with parameterized uniform crossover (GApuc) and with fitness function composed of circuit complexity, power, and signal delay. Parameterized uniform crossover is much more likely to distribute its disruptive trials in an unbiased manner over larger portions of the space, then it has more exploratory power than one and two-point crossover, so we have more chances of finding better solutions. Its effectiveness is shown by experiments. From the results, we can see that the best elite fitness, the average value of fitness of the correct circuits and the number of the correct circuits of GApuc are better than that of GA with one-point crossover or two-point crossover. The best case of optimal circuits generated by GApuc is 10.18% and 6.08% better in evaluating value than that by GA with one-point crossover and two-point crossover, respectively.

The minimum initial marking problem of Petri nets (MIM) is defined as follows: "Given a Petri net and a firing count vector X, find an initial marking M0, with the minimum total token number, for which there is a sequence δ of transitions such that each transition t appears exactly X(t) times in δ, the first transition is enabled at M0 and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.

In this letter we show that the dynamic optimal PCID allocation problem in LTE systems is NP-complete. Subsequently we provide a near-optimal solution using SON which models the problem using new merge operations and explores the search space using a suitable randomized algorithmic approach. Two feasible options for dynamic auto-configuration of the system are also discussed. Simulation results point out that the approach provides near-optimal auto-configuration of PCIDs in computationally feasible time.

In this letter we give a lower bound on the worst-case time complexity of Dijkstra's three-state mutual exclusion algorithm by specifying a concrete behavior of the algorithm. We also show that our result is more accurate than the known best bound.

Quantum computations have so far proved to be more powerful than classical computations, but quantum computers still have not been put into practical use due to several technical issues. One of the most serious problems for realizing quantum computers is decoherence that occurs inevitably since our apparatus are surrounded with environment and open systems. In this paper, we give some surveys on a variety of effects of decoherence in quantum algorithms such as Grover's database search and quantum walks, and we show how quantum algorithms work under decoherence, how sensitive they are against decoherence, and how to implement a robust quantum circuit.

Wireless ad hoc networks have fundamentally altered today's battlefield, with applications ranging from unmanned air vehicles to randomly deployed sensor networks. Security and vulnerabilities in wireless ad hoc networks have been considered at different layers, and many attack strategies have been proposed, including denial of service (DoS) through the intelligent jamming of the most critical packet types of flows in a network. This paper investigates the effectiveness of intelligent jamming in wireless ad hoc networks using the Dynamic Source Routing (DSR) and TCP protocols and introduces an intelligent classifier to facilitate the jamming of such networks. Assuming encrypted packet headers and contents, our classifier is based solely on the observable characteristics of size, inter-arrival timing, and direction and classifies packets with up to 99.4% accuracy in our experiments.

Nonnegative matrix factorization (NMF) and its extensions such as Nonnegative Tensor Factorization (NTF) have become prominent techniques for blind sources separation (BSS), analysis of image databases, data mining and other information retrieval and clustering applications. In this paper we propose a family of efficient algorithms for NMF/NTF, as well as sparse nonnegative coding and representation, that has many potential applications in computational neuroscience, multi-sensory processing, compressed sensing and multidimensional data analysis. We have developed a class of optimized local algorithms which are referred to as Hierarchical Alternating Least Squares (HALS) algorithms. For these purposes, we have performed sequential constrained minimization on a set of squared Euclidean distances. We then extend this approach to robust cost functions using the alpha and beta divergences and derive flexible update rules. Our algorithms are locally stable and work well for NMF-based blind source separation (BSS) not only for the over-determined case but also for an under-determined (over-complete) case (i.e., for a system which has less sensors than sources) if data are sufficiently sparse. The NMF learning rules are extended and generalized for N-th order nonnegative tensor factorization (NTF). Moreover, these algorithms can be tuned to different noise statistics by adjusting a single parameter. Extensive experimental results confirm the accuracy and computational performance of the developed algorithms, especially, with usage of multi-layer hierarchical NMF approach [3].