BAIS: A Bayesian Artificial Immune System for the effective handling of building blocks

Significant progress has been made in theory and design of Artificial Immune Systems (AISs) for solving hard problems accurately. However, an aspect not yet widely addressed by the research reported in the literature is the lack of ability of the AISs to deal effectively with building blocks (partial high-quality solutions coded in the antibody). The available AISs present mechanisms for evolving the population that do not take into account the relationship among the variables of the problem, potentially causing the disruption of high-quality partial solutions. This paper proposes a novel AIS with abilities to identify and properly manipulate building blocks in optimization problems. Instead of using cloning and mutation to generate new individuals, our algorithm builds a probabilistic model representing the joint probability distribution of the promising solutions and, subsequently, uses this model for sampling new solutions. The probabilistic model used is a Bayesian network due to its capability of properly capturing the most relevant interactions among the variables. Therefore, our algorithm, called Bayesian Artificial Immune System (BAIS), represents a significant attempt to improve the performance of immune-inspired algorithms when dealing with building blocks, and hence to solve efficiently hard optimization problems with complex interactions among the variables. The performance of BAIS compares favorably with that produced by contenders such as state-of-the-art Estimation of Distribution Algorithms.     

Wireless network design via 3-decompositions

We consider some network design problems with applications for wireless networks. The input for these problems is a metric space (X,d) and a finite subset UX of terminals. In the Steiner Tree with Minimum Number of Steiner Points (STMSP) problem, the goal is to find a minimum size set SX−U of points so that the unit-disc graph of S+U is connected. Let Δ be the smallest integer so that for any finite VX for which the unit-disc graph is connected, this graph contains a spanning tree with maximum degree Δ. The best known approximation ratio for STMSP was Δ−1 [I.I. Măndoiu, A.Z. Zelikovsky, A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points, Information Processing Letters 75 (4) (2000) 165–167]. We improve this ratio to (Δ+1)/2+1+ε.In the Minimum Power Spanning Tree (MPST) problem, V=X is finite, and the goal is to find a “range assignment” on the nodes so that the edge set contains a spanning tree, and ∑_vVp(v) is minimized. We consider a particular case {0,1}-MPST of MPST when the distances are in {0,1}; here the goal is to find a minimum size set SV of “active” nodes so that the graph (V,E₀+E₁(S)) is connected, where , and E₁(S) is the set the edges in with both endpoints in S. We will show that the (5/3+ε)-approximation scheme for MPST of [E. Althaus, G. Calinescu, I. Măndoiu, S. Prasad, N. Tchervenski, A. Zelikovsky, Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks, Wireless Networks 12 (3) (2006) 287–299] achieves a ratio 3/2 for {0,1}-distances. This answers an open question posed in [E. Lloyd, R. Liu, S. Ravi, Approximating the minimum number of maximum power users in ad hoc networks, Mobile Networks and Applications 11 (2006) 129–142].     

A note on path bipancyclicity of hypercubes

In [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97], the authors showed that any path in an n-cube with length of k, 2k2n−4, lies on a cycle of every even length from 2k to 2ⁿ inclusive. Base on Lemma 5 of that paper, they proved the subcase 2.2.1 of the main theorem of that paper. However, the lemma is false, therefore, we propose a lemma to replace that lemma. Therefore, the main result of [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97] is still correct.     

Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u,v∈V(G) are joined by a path of length l for all d_G(u,v)?l?|V(G)|-1, where d_G(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190-1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332-3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ_n, is almost panconnected except the path of length d_CQn(u,v)+1 for any two distinct vertices u,v∈V(CQ_n). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d_CQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,v in CQ_n. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.     

Latent classification models for binary data

One of the simplest, and yet most consistently well-performing set of classifiers is the naïve Bayes models (a special class of Bayesian network models). However, these models rely on the (naïve) assumption that all the attributes used to describe an instance are conditionally independent given the class of that instance. To relax this independence assumption, we have in previous work proposed a family of models, called latent classification models (LCMs). LCMs are defined for continuous domains and generalize the naïve Bayes model by using latent variables to model class-conditional dependencies between the attributes. In addition to providing good classification accuracy, the LCM has several appealing properties, including a relatively small parameter space making it less susceptible to over-fitting. In this paper we take a first step towards generalizing LCMs to hybrid domains, by proposing an LCM for domains with binary attributes. We present algorithms for learning the proposed model, and we describe a variational approximation-based inference procedure. Finally, we empirically compare the accuracy of the proposed model to the accuracy of other classifiers for a number of different domains, including the problem of recognizing symbols in black and white images.     

System supports for protocol and application adaptation in vertical handoffs

In overlay networks, the network characteristics before and after a vertical handoff would be drastically different. Consequently, in this paper, we propose an end‐to‐end based scheme to support protocol and application adaptation in vertical handoffs. First, we proposed a Vertical‐handoff Aware TCP, called VA‐TCP. VA‐TCP can identify the packet losses caused by vertical handoffs. If segments losses are due to vertical handoffs, VA‐TCP only retransmits the missing segments but does not invoke the congestion control procedure. Moreover, VA‐TCP dynamically estimates the bandwidth and round‐trip time in a new network. Based on the estimated bandwidth and round‐trip time, VA‐TCP adjusts its parameters to respond to the new network environment. Second, during a vertical handoff, applications also need to be adapted accordingly. Therefore, we design a programming interface that allows applications to be notified upon and adapt to changing network environments. To support our interface, we utilize the signal mechanism to achieve kernel‐to‐user notification. Nevertheless, signals cannot carry information. Thus, we implement the shared memory mechanism between applications and the kernel to facilitate parameters exchange. Finally, we also provide a handoff‐aware CPU scheduler so that tasks that are interested in the vertical‐handoff event are given preference over other processes to attain a prompt response for new network conditions. We have implemented a prototype system on the Linux kernel 2.6. From the experimental results, our proposed protocol and application adaptation mechanisms are shown to effectively improve the performance of TCP and applications during vertical handoffs. Copyright © 2008 John Wiley & Sons, Ltd.     

Strongly Hamiltonian laceability of the even k-ary n-cube

The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N − 2 joining each pair of vertices in the same partite set, where N = |V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n  2.     

Using a neural network for predicting the average grain size in friction stir welding processes

In the paper the microstructural phenomena in terms of average grain size occurring in friction stir welding (FSW) processes are focused. A neural network was linked to a finite element model (FEM) of the process to predict the average grain size values. The utilized net was trained starting from experimental data and numerical results of butt joints and then tested on further butt, lap and T-joints. The obtained results show the capability of the AI technique in conjunction with the FE tool to predict the final microstructure in the FSW joints.     

Dynamic Web Service discovery architecture based on a novel peer based overlay network

Service Oriented Computing and its most famous implementation technology Web Services (WS) are becoming an important enabler of networked business models. Discovery mechanisms are a critical factor to the overall utility of Web Services. So far, discovery mechanisms based on the UDDI standard rely on many centralized and area-specific directories, which poses information stress problems such as performance bottlenecks and fault tolerance. In this context, decentralized approaches based on Peer to Peer overlay networks have been proposed by many researchers as a solution. In this paper, we propose a new structured P2P overlay network infrastructure designed for Web Services Discovery. We present theoretical analysis backed up by experimental results, showing that the proposed solution outperforms popular decentralized infrastructures for web discovery, Chord (and some of its successors), BATON (and it’s successor) and Skip-Graphs.     

Defending passive worms in unstructured P2P networks based on healthy file dissemination

Propagation of passive worms in unstructured peer-to-peer (P2P) networks can result in significant damages and the loss of network security. This paper obtains the average delay for all peers in the entire transmitting process, and proposes a mathematical model for simulating unstructured P2P networks-based passive worms' propagation taking into account network throughput. According to the file popularity which follows the Zipf distribution, we propose a new healthy file dissemination-based defense strategy. Some parameters related to the propagation of passive worms are studied based on the proposed model. Finally, the simulation results verify the effectiveness of our model, which can provide an important guideline in the control of passive worms in unstructured P2P networks.