A Graph-based Ant System and its convergence

A general framework for solving combinatorial optimization problems heuristically by the Ant System approach is developed. The framework is based on the concept of a construction graph, a graph assigned to an instance of the optimization problem under consideration, encoding feasible solutions by walks. It is shown that under certain conditions, the solutions generated in each iteration of this Graph-based Ant System converge with a probability that can be made arbitrarily close to 1 to the optimal solution of the given problem instance.     

A simple framework for real-time cryptographic protocol analysis with compositional proof rules

A real-time process algebra, enhanced with specific constructs for handling cryptographic primitives, is proposed to model cryptographic protocols in a simple way. We show that some security properties, such as authentication and secrecy, can be re-formulated in this timed setting. Moreover, we show that they can be seen as suitable instances of a general information flow-like scheme, called timed generalized non-deducibility on compositions (tGNDC), parametric w.r.t. the observational semantics of interest. We show that, when considering timed trace semantics, there exists a most powerful hostile environment (or enemy) that can try to compromise the protocol. Moreover, we present a couple of compositionality results for tGNDC, one of which is time dependent, and show their usefulness by means of a case study.     

Ant algorithms and simulated annealing for multicriteria dynamic programming

The paper presents a comparison of ant algorithms and simulated annealing as well as their applications in multicriteria discrete dynamic programming. The considered dynamic process consists of finite states and decision variables. In order to describe the effectiveness of multicriteria algorithms, four measures of the quality of the nondominated set approximations are used.     

A Distributed Ant Algorithm for\protect Efficiently Patrolling a Network

We consider the problem of patrolling—i.e. ongoing exploration of a network by a decentralized group of simple memoryless robotic agents. The model for the network is an undirected graph, and our goal, beyond complete exploration, is to achieve close to uniform frequency of traversal of the graphs edges. A simple multi-agent exploration algorithm is presented and analyzed. It is shown that a single agent following this procedure enters, after a transient period, a periodic motion which is an extended Eulerian cycle, during which all edges are traversed an identical number of times. We further prove that if the network is Eulerian, a single agent goes into an Eulerian cycle within 2|E|D steps, |E| being the number of edges in the graph and D being its diameter. For a team of k agents, we show that after at most 2( 1 + 1/k) |E|D steps the numbers of edge visits in the network are balanced up to a factor of two. In addition, various aspects of the algorithm are demonstrated by simulations.     

Memory-based adaptive partitioning (MAP) of search space for the enhancement of convergence in Pareto-based multi-objective evolutionary algorithms

A new algorithm, dubbed memory-based adaptive partitioning (MAP) of search space, which is intended to provide a better accuracy/speed ratio in the convergence of multi-objective evolutionary algorithms (MOEAs) is presented in this work. This algorithm works by performing an adaptive-probabilistic refinement of the search space, with no aggregation in objective space. This work investigated the integration of MAP within the state-of-the-art fast and elitist non-dominated sorting genetic algorithm (NSGAII). Considerable improvements in convergence were achieved, in terms of both speed and accuracy. Results are provided for several commonly used constrained and unconstrained benchmark problems, and comparisons are made with standalone NSGAII and hybrid NSGAII-efficient local search (eLS).     

A running time analysis of an Ant Colony Optimization algorithm for shortest paths in directed acyclic graphs

In this paper, we prove polynomial running time bounds for an Ant Colony Optimization (ACO) algorithm for the single-destination shortest path problem on directed acyclic graphs. More specifically, we show that the expected number of iterations required for an ACO-based algorithm with n ants is for graphs with n nodes and m edges, where ρ is an evaporation rate. This result can be modified to show that an ACO-based algorithm for One-Max with multiple ants converges in expected iterations, where n is the number of variables. This result stands in sharp contrast with that of Neumann and Witt, where a single-ant algorithm is shown to require an exponential running time if ρ=O(n−1−ε) for any ε>0.     

Extended stochastic gradient identification algorithms for Hammerstein–Wiener ARMAX systems

An extended stochastic gradient algorithm is developed to estimate the parameters of Hammerstein–Wiener ARMAX models. The basic idea is to replace the unmeasurable noise terms in the information vector of the pseudo-linear regression identification model with the corresponding noise estimates which are computed by the obtained parameter estimates. The obtained parameter estimates of the identification model include the product terms of the parameters of the original systems. Two methods of separating the parameter estimates of the original parameters from the product terms are discussed: the average method and the singular value decomposition method. To improve the identification accuracy, an extended stochastic gradient algorithm with a forgetting factor is presented. The simulation results indicate that the parameter estimation errors become small by introducing the forgetting factor.     

Persistency of excitation, sufficient richness and parameter convergence in discrete time adaptive control

The main result of this paper is to give new techniques for deriving explicit conditions on the exogenously specified reference trajectory to guarantee parameter convergence for a class of either single-input single-output or multi-input multi-output discrete time adaptive control schemes. Other interesting results are relations between persistently exciting signals and sufficiently rich signals.     

Ant colony search algorithms for optimal polygonal approximation of plane curves

This paper presents a new polygonal approximation method using ant colony search algorithm. The problem is represented by a directed graph such that the objective of the original problem becomes to find the shortest closed circuit on the graph under the problem-specific constraints. A number of artificial ants are distributed on the graph and communicate with one another through the pheromone trails which are a form of the long-term memory guiding the future exploration of the graph. The important properties of the proposed method are thoroughly investigated. The performance of the proposed method as compared to those of the genetic-based and the tabu search-based approaches is very promising.