A novel strategy of pareto-optimal solution searching in multi-objective particle swarm optimization (MOPSO)

In multi-objective particle swarm optimization (MOPSO) algorithms, finding the global optimal particle (gBest) for each particle of the swarm from a set of non-dominated solutions is very difficult yet an important problem for attaining convergence and diversity of solutions. First, a new Pareto-optimal solution searching algorithm for finding the gBest in MOPSO is introduced in this paper, which can compromise global and local searching based on the process of evolution. The algorithm is implemented and is compared with another algorithm which uses the Sigma method for finding gBest on a set of well-designed test functions. Finally, the multi-objective optimal regulation of cascade reservoirs is successfully solved by the proposed algorithm.     

Matricial gradient for the least-squares residual and its application to optimal model fitting

To improve the model vector functions g_i ,-(t) or the model matrix M for L ₂ optimization and approximation of empirical data, the matricial gradient of the ordinary least-squares residual and the weighted least-squares residual is used. Acceleration and optimization of convergence is investigated. The optimal model fitting is also studied in the case of inequality constraint models and in the case of additional collocation point restrictions.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Characterization of analytic phase signals

In many cases, a real-valued signal χ(t) may be associated with a complex-valued signal a(t)e^iθ(t), the analytic signal associated with χ(t) with the characteristic properties χ(t) = a(t) cosθ(t) and H(a(·)cosθ(·))(t) = a(t)sinθ(t). Using such obtained amplitude-frequency modulation the instantaneous frequency of χ(t) at the time t₀ may be defined to be θ′(t₀), provided θ′(t₀) ≥ 0. The purpose of this note is to characterize, in terms of analytic functions, the unimodular functions F(t) = C(t) + iS(t),C²(t) + S² (t) = 1, a.e., that satisfy HC(t) = S(t). This corresponds to the case a(t) ≡ 1 in the above formulation. We show that a unimodular function satisfies the required condition if and only if it is the boundary value of a so called inner function in the upper-half complex plane. We also give, through an explicit formula, a large class of functions of which the parametrization C(t) = cosθ(t) is available and the extra condition θ′(t) ≥ 0, a.e. is enjoyed. This class of functions contains Blaschke products in the upper-half complex plane as a proper subclass studied by Picinbono in [1].     

Efficient handling of universally quantified inequalities

This paper introduces a new framework for solving quantified constraint satisfaction problems (QCSP) defined by universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and technology. We introduce a generic branch and prune algorithm to tackle these continuous CSPs with parametric constraints, where the pruning and the solution identification processes are dedicated to universally quantified inequalities. Special rules are proposed to handle the parameter domains of the constraints. The originality of our framework lies in the fact that it solves the QCSP as a non-quantified CSP where the quantifiers are handled locally, at the level of each constraint. Experiments show that our algorithm outperforms the state of the art methods based on constraint techniques. This paper is an extended version of a paper published at the SAC 2008 conference [15].     

Time-Bounded Kolmogorov Complexity and Solovay Functions

A Solovay function is an upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of computable Solovay functions by showing that for some constant c ₀ and all computable functions t such that c ₀ n??t(n), the time-bounded version K ^t of K is a Solovay function. By unifying results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if ?? _g =??2^?g(n) is Martin-Löf random. We obtain as a corollary that the Martin-Löf randomness of the various variants of Chaitin??s ?? extends to the time-bounded case in so far as $\Omega _{ \textnormal{K}^{t}}$ is Martin-Löf random for any t as above. As a step in the direction of a characterization of K-triviality in terms of jump-traceability, we demonstrate that a set A is K-trivial if and only if A is O(g(n)?K(n))-jump traceable for all computable Solovay functions g. Furthermore, this equivalence remains true when the universal quantification over all computable Solovay functions in the second statement is restricted either to all functions of the form K ^t for some function t as above or to a single function K ^t of this form. Finally, we investigate into the plain Kolmogorov complexity C and its time-bounded variant C ^t of initial segments of computably enumerable sets. Our main theorem here asserts that every high c.e. Turing degree contains a c.e. set B such that for any computable function t there is a constant c _t >0 such that for all m it holds that C ^t (B?m)??c _t ?m, whereas for any nonhigh c.e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C ^t (A?m)??logm+c. By similar methods it can be shown that any high degree contains a set B such that C ^t (B?m)??⁺ m/4. The constructed sets B have low unbounded but high time-bounded Kolmogorov complexity, and accordingly we obtain an alternative proof of the result due to Juedes et al. (Theor. Comput. Sci. 132(1?C2):37?C70, 1994) that every high degree contains a strongly deep set.     

A remark on the complexity of consistent conjunctive query answering under primary key violations

A natural way for capturing uncertainty in the relational data model is by allowing relations that violate their primary key. A repair of such relation is obtained by selecting a maximal number of tuples without ever selecting two tuples that agree on their primary key. Given a Boolean query q, CERTAINTY(q) is the problem that takes as input a relational database and asks whether q evaluates to true on every repair of that database. In recent years, CERTAINTY(q) has been studied primarily for conjunctive queries. Conditions have been determined under which CERTAINTY(q) is coNP-complete, first-order expressible, or not first-order expressible. A remaining open question was whether there exist conjunctive queries q without self-join such that CERTAINTY(q) is in PTIME but not first-order expressible. We answer this question affirmatively.     

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight of satisfied constraints is maximized. We consider this problem and its variant Max AW CSP where the weights are allowed to be both positive and negative, and study how the complexity of the problems depends on the allowed constraint types. We prove that Max AW CSP over an arbitrary finite domain exhibits a dichotomy: it is either polynomial-time solvable or NP-hard. Our proof builds on two results that may be of independent interest: one is that the problem of finding a maximum H-colourable subdigraph in a given digraph is either NP-hard or trivial depending on H, and the other a dichotomy result for Max CSP with a single allowed constraint type.     

Periodic compensation of a class of decentralized systems with fixed modes

This paper first finds that the high frequency (ω) periodic controller suggested in Lee, Meerkov, and Runolfsson (1987) for fixed mode removal, and pole and zero placement, of a class of decentralized systems (A,B_i,C_i) all the strongly interconnected channels of which satisfy C_iB_i=0, causes large, O(ω), oscillations in the outputs. Next it proposes an alternative controller, a dual of the above, that achieves the compensation with oscillations of O(1) only.     

Test sets and checking words for homomorphism equivalence

Given a language L over an alphabet Σ and two homomorphisms g and h, defined on $\text{Σ}{}^1$, we want to decide whether or not g and h are equivalent on L, i.e., whether or not g(w) = h(w) holds for all words w in L. We prove the following results' for the case where Σ consists of two letters. Every language L possesses a finite subset L, such that, for any pair (g, h), g and h are equivalent on L if and only if they are equivalent on L₁. For every language L (with the exception of some trivial cases), there is a word w (not necessarily in L) such that, for any pair (g, h), g and h are equivalent on L if and only if g(w) = h(w). Our constructions are, in general, noneffective. Also some related notions are discussed in the paper.     

A fully parallel method for the singular eigenvalue problem

In this paper, a fully parallel method for finding some or all finite eigenvalues of a real symmetric matrix pencil (A, B) is presented, where A is a symmetric tridiagonal matrix and B is a diagonal matrix with b₁ > 0 and b_i ≥ 0, i = 2,3,…,n. The method is based on the homotopy continuation with rank 2 perturbation. It is shown that there are exactly m disjoint, smooth homotopy paths connecting the trivial eigenvalues to the desired eigenvalues, where m is the number of finite eigenvalues of (A, B). It is also shown that the homotopy curves are monotonic and easy to follow.     

Block-graph width

Let G be a class of graphs. A graph G has G-width k if there are k independent sets N₁,…,N_k in G such that G can be embedded into a graph H∈G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N_i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained.     

Relationship between the eccentric connectivity index and Zagreb indices

For a (molecular) graph, the first Zagreb index M₁ is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M₂ is equal to the sum of the products of the degrees of pairs of adjacent vertices. If G is a connected graph with vertex set V(G), then the eccentric connectivity index of G, ξ^C(G), is defined as, ∑_vi∈V(G)d_ie_i, where d_i is the degree of a vertex v_i and e_i is its eccentricity. In this report we compare the eccentric connectivity index (ξ^C) and the Zagreb indices (M₁ and M₂) for chemical trees. Moreover, we compare the eccentric connectivity index (ξ^C) and the first Zagreb index (M₁) for molecular graphs.     

A Model for Minimizing Active Processor Time

We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job J _i has an integer length ? _i as well as a set T _i of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can schedule up to B jobs at a timeslot t so long as it is “active” at t. The goal is to schedule all the jobs in the fewest number of active timeslots. The machine consumes a fixed amount of energy per active timeslot, regardless of the number of jobs scheduled in that slot (as long as the number of jobs is non-zero). In other words, subject to ? _i units of each job i being scheduled in its feasible region and at each slot at most B jobs being scheduled, we are interested in minimizing the total time during which the machine is active. We present a linear time algorithm for the case where jobs are unit length and each T _i is a single interval, assuming that jobs are given in sorted order. For general T _i , we show that the problem is NP-complete even for B=3. However when B=2, we show that it can be efficiently solved. In addition, we consider a version of the problem where jobs have arbitrary lengths and can be preempted at any point in time. For general B, the problem can be solved by linear programming. For B=2, the problem amounts to finding a triangle-free 2-matching on a special graph. We extend the algorithm of Babenko et al. (Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120–129, 2010) to handle our variant, and also to handle non-unit length jobs. This yields an \(O(\sqrt{L} m)\) time algorithm to solve the preemptive scheduling problem for B=2, where L=∑ _i ? _i . We also show that for B=2 and unit length jobs, the optimal non-preemptive schedule has active time at most 4/3 times that of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length.     

A theoretical limit for safety verification techniques with regular fix-point computations

In computer aided verification, the reachability problem is particularly relevant for safety analyses. Given a regular tree language L, a term t and a relation R, the reachability problem consists in deciding whether there exist a positive integer n and terms t₀,t₁,…,tn such that t₀∈L, tn=t and for every 0?i<n, (ti,ti+1)∈R. In this case, the term t is said to be reachable, otherwise it is said unreachable. This problem is decidable for particular kinds of relations, but it is known to be undecidable in general, even if L is finite. Several approaches to tackle the unreachability problem are based on the computation of an R-closed regular language containing L. In this paper we show a theoretical limit to this kind of approaches for this problem.     

From time series to linear system—Part I. Finite dimensional linear time invariant systems

In the first part of this paper the definition of a dynamical system as simply consisting of a family of time series will be developed. In this context the notions of linearity, time invariance, and finite dimensionality will be introduced. It will be shown that a given family of time series may be represented by a system of (AR) equations: R_iw(t + l) + R_{l − 1}w(t + l − 1) + … + R₀w(t) = 0, or, equivalently, by a finite dimensional linear time invariant system: x(t + 1) = Ax(t) + Bu(t); y(t) = Cx(t) + Du(t); w = (u, y), if and only if this family is linear, shift invariant and complete (or, as is equivalent, closed in the topology of pointwise convergence). This yields a very high level and elegant set of axioms which characterize these familiar objects. It is emphasized, however, that no a priori choice is made as to which components of w are inputs and which are outputs. Such a separation always exists in any specific linear time invariant model. Starting from these definitions, the structural indices of such systems are introduced and it is shown how an (AR) representation of a system having a given behaviour can be constructed. These results will be used in a modelling context in Part II of the paper.     

Three-machine flowshop with two operations per job to minimize makespan

This work studies three variants of a three-machine flowshop problem with two operations per job to minimize makespan (F3/o = 2/C_max). A set of n jobs are classified into three mutually exclusive families A, B and C. The families A, B and C are defined as the set of jobs that is scheduled in machine sequence (M₁, M₂), (M₁, M₃) and (M₁, M₃), respectively, where (M_x, M_y) specifies the machine sequence for the job that is processed first on M_x, and then on M_y. Specifically, jobs with the same route (machine sequence) are classified into the same family. Three variants of F3/o = 2/C_max are studied. First, F3/GT, no-idle, o = 2/C_max, in which both machine no-idle and GT restrictions are considered. The GT assumption requires that all jobs in the same family are processed contiguously on the machine and the machine no-idle assumption requires that all machines work continuously without idle time. Second, the problem F3/GT, o = 2/C_max, in which the machine no-idle restriction in the first variant is relaxed, is considered. Third, the problem F3/no-idle, o = 2/C_max with the GT assumption in the first variant relaxed is considered. Based on the dominance conditions developed, the optimal solution is polynomially derived for each variant. These results may narrow down the gap between easy and hard cases of the general problem.     

Building exact computation sequences

Exact computation sequences are sequences of the form 〈L₀, A₀〉 →^S₁ 〈L₁, A₁〉 ⋯ →^S_n 〈L_n, ∅〉, where L₀ is a free algebra, A₀ is a set of conditional equations over L₀, S_i is a ‘step function’, L_i = S_i(L_i−1), and A_i = S_i(A_i−1). Each step function is the top-down reduction extesion of a set of confluent and noetherian rewrite rules. These sequences are used in solving the word problem for free algebras, since for any pair of terms t₁, t₂ ϵ L₀, t₁=_A0 t₂ iff S_n ∘ S_n−1 ∘ ⋯ ∘ S₁(t₁) = S_n ∘ S_n−1(t₂). We analyze properties of exact comput sequences such as: determining the relation between the sets 〈L_i-1, A_i−1〉 and S_i, and the output pair 〈L_i, A_i〉, and we present criteria for choosing the equations E_i in 〈L_i−1, A_i−1〉 which are used to generate the reductions S_i. We also give examples showing how to construct exact computation sequences for several axiom systems by applying the properties and the criteria presented in the article.     

Strong stability of the mono-tubular heat exchanger equation with output feedback

We investigate asymptotic behavior of the C₀-semigroup T(t) associated with the mono-tubular heat exchanger equation with output feedback by a perturbation method. It is shown that T(t) is bounded if a constraint is satisfied by the parameters and the spatial distribution function. Further, applying the Arendt-Batty-Lyubich-Vu theorem, a criterion is established to judge strong stability of T(t).     

An approximation method for high-order fractional derivatives of algebraically singular functions

The fractional derivative D^qf(s) (0≤s≤1) of a given function f(s) with a positive non-integer q is defined in terms of an indefinite integral. We propose a uniform approximation scheme to D^qf(s) for algebraically singular functions f(s)=s^αg(s) (α>−1) with smooth functions g(s). The present method consists of interpolating g(s) at sample points t_j in [0,1] by a finite sum of the Chebyshev polynomials. We demonstrate that for the non-negative integer m such that m<q<m+1, the use of high-order derivatives g⁽ⁱ⁾(0) and g⁽ⁱ⁾(1) (0≤i≤m) at both ends of [0,1] as well as g(t_j), t_j∈[0,1] in interpolating g(s), is essential to uniformly approximate D^q{s^αg(s)} for 0≤s≤1 when α≥q−m−1. Some numerical examples in the simplest case 1<q<2 are included.