Cloud-based evolutionary algorithms: An algorithmic study

This paper presents a cloud-computing based evolutionary algorithm using a synchronous storage service as pool for exchange information among population of solutions. The multi-computer was composed of several normal PCs or laptops connected via Wifi or Ethernet. In this work the effect of how the distributed evolutionary algorithm reached the solution when new PCs was added was tested whether that effect also translates to the algorithmic performance of the algorithm. To this end different (and hard) problems was addressed using the proposed multi-computer, analyzing the effects that the automatic load-balancing and synchronization had on the speed of algorithm successful, and analyzing how the number of evaluation per second increases when the multi-computer includes new nodes. The measure used for the analysis was number of evaluation per second which was increased when the multi-computer includes new nodes. The algorithm solved the proposed problems and it was viable to run it in homogeneous or heterogeneous platforms. The experiments includes two problems and different configuration for the distributed evolutionary algorithm in order to check the results of the algorithm for several rates of information exchange with the selected storage service. Results shows that the system is viable with homogeneous or heterogeneous nodes and there is no significative differences for the synchronous storage services we have tested. But when the problem is harder, and the threads of the algorithm does not stop for each information exchange (migration of individual from one population to another one), the differences of using a specific service became significative in terms of success of the algorithm.     

The algorithmic complexity of mixed domination in graphs

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.     

Boundary properties of graphs for algorithmic graph problems

The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and vertexk-colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any k>3 there is a continuum of boundary classes for vertexk-colorability.     

An algorithmic approach to resolutions

We provide an algorithmic method for constructing projective resolutions of modules over quotients of path algebras. This algorithm is modified to construct minimal projective resolutions of linear modules over Koszul algebras.     

An algorithmic view of gene teams

Comparative genomics is a growing field in computational biology, and one of its typical problem is the identification of sets of orthologous genes that have virtually the same function in several genomes. Many different bioinformatics approaches have been proposed to define these groups, often based on the detection of sets of genes that are “not too far” in all genomes. In this paper, we propose a unifying concept, called gene teams, which can be adapted to various notions of distance. We present two algorithms for identifying gene teams formed by n genes placed on m linear chromosomes. The first one runs in O(mn log² n) and uses a divide and conquer approach based on the formal properties of gene teams. We next propose an optimization of the original algorithm, and, in order to better understand the complexity bound of the algorithms, we recast the problem in the Hopcroft's partition refinement framework. This allows us to analyze the complexity of the algorithms with elegant amortized techniques. Both algorithms require linear space. We also discuss extensions to circular chromosomes that achieve the same complexity.     

An algorithmic analysis of DNA structure

Bilinearity, complementarity and antiparallelism of the double stranded DNA structure are proved, in a general and abstract setting, as requirements of an efficient duplication algorithm for ‘mobile strings’.     

An algorithmic analysis of simulation strategies

Each discrete event simulation language incorporates a time control procedure to conduct timing management and next event selection. Each time control procedure embodies, and thus imposes, a strategy (approach, method) for next event selection- and thereby determines the world view of a language. The three generally recognized strategies are event scheduling, activity scanning and process interaction.This paper presents algorithmic formulations of the three strategies and their modeling routines, as well as detailed discussions and comparisons of the strategies. The algorithmic formulations serve to aid understanding by describing essential aspects of the strategies while excluding implementation details which are not strategy-dependent, and which tend to detract from the essential concepts.A significant practical application of the formulations is discussed. This consists of merging the algorithms for the event scheduling and process interaction strategies into one algorithm, which then served as a model for combining GPSS and GASP IV into a simulation system providing the individual capabilities of both language, and the capability to intermix GPSS and GASP within a single model.     

An algorithmic study in the vector model for Wireless Power Transfer maximization

Rapid technological advances in the domain of Wireless Power Transfer (WPT) pave the way for novel methods for power management in systems of wireless devices and recent research works have already started considering algorithmic solutions for tackling emerging problems. However, many of those works are limited by the system modelling, and more specifically the one-dimensional abstraction suggested by Friis formula for the power received by one antenna under idealized conditions given another antenna some distance away.Different to those works, we use a model which arises naturally from fundamental properties of the superposition of energy fields. This model has been shown to be more realistic than other one-dimensional models that have been used in the past and can capture superadditive and cancellation effects. Under this model, we define two new interesting problems for configuring the wireless power transmitters so as to maximize the total power in the system and we prove that the first problem can be solved in polynomial time. We present a distributed solution that runs in pseudo-polynomial time and uses various knowledge levels and we provide theoretical performance guarantees. Finally, we design three heuristics for the second problem and evaluate them via simulations.     

An algorithmic approach for fuzzy inference

To apply fuzzy logic, two major tasks need to be performed: the derivation of production rules and the determination of membership functions. These tasks are often difficult and time consuming. This paper presents an algorithmic method for generating membership functions and fuzzy production rules; the method includes an entropy minimization for screening analog values. Membership functions are derived by partitioning the variables into the desired number of fuzzy terms and production rules are obtained from minimum entropy clustering decisions. In the rule derivation process, rule weights are also calculated. This algorithmic approach alleviates many problems in the application of fuzzy logic to binary classification     

An algorithmic framework for network reconstruction

Models of biological systems and phenomena are of high scientific interest and practical relevance, but not always easy to obtain due to their inherent complexity. To gain the required insight, experimental data are provided and need to be interpreted in terms of models that explain the observed phenomena. In systems biology the framework of Petri nets is often used to describe models for the regulatory mechanisms of biological systems. The aim of this paper is to provide, based on results in Marwan et al. (2008) [1] and Durzinsky et al. (2008) [2], an algorithmic framework for the challenging task of generating all possible Petri nets fitting the given experimental data.     

An algorithmic approach to combining belief functions

Methods of combination are used to synthesize pieces of evidence of equal standing that represent different aspects of a specific system about which a diagnosis is to be made. Combination is distinct from consensus, when complete diagnoses rendered by different knowledge sources require synthesis, and conditionalization, where pieces of evidence to be synthesized have dissymmetric relationships to each other. The Dempster-Shafer Rule is the quintessential combination method. However, it has been criticized for its inability to handle inconsistent pieces of evidence and for the way it focuses the weight of evidence. This article presents an alternative combination method that is capable of handling inconsistent evidence and relates evidence focusing to the amount of information resident in pieces of evidence. The method is capable of combining belief functions. Future research should address extending the method to the combination of a broad class of imprecise probability functions. © 1996 John Wiley & Sons, Inc.     

An algorithmic framework of discrete particle swarm optimization

Particle swarm optimization (PSO) was originally developed for continuous problem. To apply PSO to a discrete problem, the standard arithmetic operators of PSO are required to be redefined over discrete space. In this paper, a concept of distance over discrete solution space is introduced. Under this notion of distance, the PSO operators are redefined. After reinterpreting the composition of velocity of a particle, a general framework of discrete PSO algorithm is proposed. As a case study, we illustrate the application of the proposed discrete PSO algorithm to number partitioning problem (NPP) step by step. Preliminary computational experience is also presented. The successful application shows that the proposed algorithmic framework is feasible.     

An algorithmic method in Painleve analysis of PDE

In this paper, a new algorithm is presented to decide whether the partial differential algebraic equation possesses Painleve property or not. Under the situation of not getting recursion relations, all resonance points are found. The symbolic computation is employed in all process. As a power tool, Wu-Ritt elimination method plays a important role in the process of testing the compatibility of resonance equations. The algorithm improves on the WTC method on the aspect of the computation.     

Global view on reactivity: switch graphs and their logics

The notion of reactive graph generalises the one of graph by allowing the base accessibility relation to change when its edges are traversed. Can we represent these more general structures using points and arrows? We prove this can be done by introducing higher order arrows: the switches. The possibility of expressing the dependency of the future states of the accessibility relation on individual transitions by the use of higher-order relations, that is, coding meta-relational concepts by means of relations, strongly suggests the use of modal languages to reason directly about these structures. We introduce a hybrid modal logic for this purpose and prove its completeness.     

An axiomatization of graphs

The magmoid of hypergraphs labelled over a finite doubly ranked alphabet, is characterized as the quotient of the free magmoid generated by this alphabet divided by a finite set of equations. Thus a relevant open problem, posed by Engelfriet and Vereijken, is being solved.Received: 27 April 2004, Published online: 14 October 2004     

An intelligent market making strategy in algorithmic trading

Market making (MM) strategies have played an important role in the electronic stock market. However, the MM strategies without any forecasting power are not safe while trading. In this paper, we design and implement a twotier framework, which includes a trading signal generator based on a supervised learning approach and an event-driven MM strategy. The proposed generator incorporates the information within order book microstructure and market news to provide directional predictions. The MM strategy in the second tier trades on the signals and prevents itself from profit loss led by market trending. Using half a year price tick data from Tokyo Stock Exchange (TSE) and Shanghai Stock Exchange (SSE), and corresponding Thomson Reuters news of the same time period, we conduct the back-testing and simulation on an industrial near-to-reality simulator. From the empirical results, we find that 1) strategies with signals perform better than strategies without any signal in terms of average daily profit and loss (PnL) and sharpe ratio (SR), and 2) correct predictions do help MM strategies readjust their quoting along with market trending, which avoids the strategies triggering stop loss procedure that further realizes the paper loss.     

An algorithmic method for increasing ADC fault resilience

A method for the transformation of algorithms of the operation of sequential ADCs into algorithms correcting faults in the discrete part of an ADC is presented. A graphical method for the determination of the operation conditions of discrete control devices (finite automata) of ADCs resilient to single-event upsets is applied. The properties of the behavior of a graph of a finite automaton for which the ADC realizes noise-immune approximation algorithms are formulated. Procedures for the construction of such graphs are presented.     

An algorithmic approach to discovering and provingq-series identities

An algorithmic method of producingq-series identities from any given power series is discassed. This recursive technique is then used to give new proofs of several classicalq-identities of Gauss and Rogers. Dedicated to the memory of John Knopfmacher, 1937–1999, the inventor of the Engel expansions for q-series. The first author was partially supported by National Science Foundation Grant DMS-9206993 and by The Centre for Applicable Analysis and Number Theory of the University of the Witwatersrand. He wishes to express his gratitude to the second author who provided the hospitality and support which made his participation possible This paper was presented at the fourth International Conference on Average-Case Analysis of Algorithms, Princeton, NJ, by the second author. Online publication September 6, 2000.