Integrating Tabu Search in Particle Swarm Optimization for the Frequency Assignment Problem

In this paper, we address one of the issues in the frequency assignment problem for cellular mobile networks in which we intend to minimize the interference levels when assigning frequencies from a limited frequency spectrum. In order to satisfy the increasing demand in such cellular mobile networks, we use a hybrid approach consisting of a Particle Swarm Optimization(PSO) combined with a Tabu Search(TS) algorithm. This approach takes both advantages of PSO efficiency in global optimization and TS in avoiding the premature convergence that would lead PSO to stagnate in a local minimum. Moreover, we propose a new efficient, simple, and inexpensive model for storing and evaluating solution's assignment. The purpose of this model reduces the solution's storage volume as well as the computations required to evaluate thesesolutions in comparison with the classical model. Our simulation results on the most known benchmarking instances prove the effectiveness of our proposed algorithm in comparison with previous related works in terms of convergence rate, the number of iterations, the solution storage volume and the running time required to converge to the optimal solution.

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.

Simulated annealing algorithm for detecting graph isomorphism

Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.

Searching a Polygonal Region by Two Guards

We study the problem of searching for a mobile intruder in a polygonal region P by two guards. The objective is to decide whether there should exist a search schedule for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of P continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal O（n） time algorithm to determine the two-guard searchability in a polygon, and an O（n log n ＋ m） time algorithm to generate a search schedule, if it exists, where n is the number of vertices of P and m （≤ n^2） is the number of search instructions reported.

Searching a Polygonal Region by a Boundary Searcher

This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O（n） time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O（n log n ＋ I） time algorithm for generating a search schedule if it exists, where I （〈 3n^2） is the number of search instructions reported. Our results improve upon the previously known O（n^2） time and space bounds.

Test sequencing problem arising at the design stage for reducing life cycle cost

Previous test sequencing algorithms only consider the execution cost of a test at the application stage. Due to the fact that the placement cost of some tests at the design stage is considerably high compared with the execution cost, the sequential diagnosis strategy obtained by previous methods is actually not optimal from the view of life cycle. In this paper, the test sequencing problem based on life cycle cost is presented. It is formulated as an optimization problem, which is non-deterministic polynomial-time hard （NP-hard）. An algorithm and a strategy to improve its computational efficiency are proposed. The formulation and algorithms are tested on various simulated systems and comparisons are made with the extant test sequencing methods. Application on a pump rotational speed control （PRSC） system of a spacecraft is studied in detail. Both the simulation results and the real-world case application results suggest that the solution proposed in this paper can significantly reduce the life cycle cost of a sequential fault diagnosis strategy.

Authenticated Group Key Agreement Protocol Based on Twist Conjugacy Problem in Near-Rings

Nowadays some promising authenticated group key agreement protocols are constructed on braid groups, dynamic groups, pairings and bilinear pairings. Hence the non-abelian structure has attracted cryptographers to construct public-key cryptographic protocols. In this article, we propose a new authenticated group key agreement protocol which works in non-abelian near-rings. We have proved that our protocol meets the security attributes under the assumption that the twist conjugacy search problem（TCSP） is hard in near-ring.

Distributed exact Grover’s algorithm

Distributed quantum computation has gained extensive attention.In this paper,we consider a search problem that includes only one target item in the unordered database.After that,we propose a distributed exact Grover’s algorithm(DEGA),which decomposes the original search problem into■n/2■parts.Specifically,(i)our algorithm is as exact as the modified version of Grover’s algorithm by Long,which means the theoretical probability of finding the objective state is 100%;(ii)the actual depth of our circuit is 8(n mod 2)+9,which is less than the circuit depths of the original and modified Grover’s algorithms,1+8■π/4√2^(n)■and 9+8■π/4√2^(n)-1/2■,respectively.It only depends on the parity of n,and it is not deepened as n increases;(iii)we provide particular situations of the DEGA on MindQuantum(a quantum software)to demonstrate the practicality and validity of our method.Since our circuit is shallower,it will be more resistant to the depolarization channel noise.

Subspace-based identification of discrete time-delay system

We investigate the identification problems of a class of linear stochastic time-delay systems with unknown delayed states in this study. A time-delay system is expressed as a delay differential equation with a single delay in the state vector. We first derive an equivalent linear time-invariant(LTI) system for the time-delay system using a state augmentation technique. Then a conventional subspace identification method is used to estimate augmented system matrices and Kalman state sequences up to a similarity transformation. To obtain a state-space model for the time-delay system, an alternate convex search(ACS) algorithm is presented to find a similarity transformation that takes the identified augmented system back to a form so that the time-delay system can be recovered. Finally, we reconstruct the Kalman state sequences based on the similarity transformation. The time-delay system matrices under the same state-space basis can be recovered from the Kalman state sequences and input-output data by solving two least squares problems. Numerical examples are to show the effectiveness of the proposed method.