Enhancing the performance of hybrid genetic algorithms by differential improvement

A differential improvement modification to Hybrid Genetic Algorithms is proposed. The general idea is to perform more extensive improvement algorithms on higher quality solutions. Our proposed Differential Improvement (DI) approach is of rather general character. It can be implemented in many different ways. The paradigm remains invariant and can be easily applied to a wider class of optimization problems. Moreover, the DI framework can also be used within other Hybrid metaheuristics like Hybrid Scatter Search algorithms, Particle Swarm Optimization, or Bee Colony Optimization techniques.     

A series of approximation algorithms for the acyclic directed steiner tree problem

Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[n ^polylogn ] no polynomial-time algorithm can guarantee better than (lnk)/4-approximation, wherek is the number of terminals. In this paper we give anO(k ^ε)-approximation algorithm for any ε>0. This result improves the previously knownk-approximation. This research was supported in part by Volkswagen-Stiftung and Packard Foundation.     

Optimal visibility algorithms for binary images on the hypercube

Consider an×n binary image. Given a directionD, the parallel visibility problem consists of determining for each pixel of the image the portion that is visible (i.e., not obstructed by any other black pixel of the image) in directionD from infinity. A related problem, referred to as point visibility, is to compute for each pixel the portion that is visible from a given pointp. In this paper, we deriveO(logn) time SIMD algorithms for each of these two problems on the hypercube, where one processor is assigned to every pixel of the image. Since the worst case communication distance of two processors in an ²-processor hypercube is 2 logn, it follows that both of the above algorithms are asymptotically optimal.This paper summarizes a preliminary version [Ref. 1] and short note on a possible improvement [Ref. 2] presented at the 1988IFIP WG 10.3. Working Conference on Parallel Processing and 1988Allerton Conference on Communication, Control and Computing, respectively. The first and third authors' research are partially supported by the Natural Sciences and Engineering Research Council of Canada.     

A heuristic to accelerate in-situ permutation algorithms

In-situ permutation algorithms permute an array of n items without using a second array. Little space is needed when one proceeds permuting along a cycle. Thus, those algorithms first search for one element called the leader on each cycle of the permutation. Then they move the items cycle by cycle. A great fraction of the runtime is spent with testing whether elements are leaders. We present a simple-to-implement heuristic to accelerate the search for leaders and present performance gains for randomly chosen permutations on three algorithms.     

Experimental comparison and application of various parameter-adaptive control algorithms

Various recursive parameter estimation algorithms and controller design procedures can be combined to build up parameter-adaptive control algorithms. Two parameter estimation methods and six control algorithms have been selected, taking into account good convergence properties and small computational expense and regarding the conditions for closed-loop identification. The resulting 12 parameter-adaptive control algorithms are compared and tested with a process computer in on-line operation with analog simulated stable and unstable processes for stochastic disturbances and step changes of the reference signal. The results are very promising. In many cases a good control performance is achieved. As a priori knowledge only the sampling time, the process model order and time delay and in some cases a weighting factor for the process input signal are required. Some parameter-adaptive control algorithms with good properties are applied to digital adaptive control of an air heater. Conclusions are given for the selection of parameter-adaptive control algorithms, depending on the type of process and its disturbances.The adaptive control algorithms may be applied for adaptive control of constant and time variant, linear and weakly non-linear stable and unstable processes with process computers or micro computers or for self-tuning of control algorithms or tuning of conventional analog PID controllers, if external disturbances act on the loop.     

A framework for and empirical study of algorithms for traffic assignment

Traffic congestion is an issue in most cities worldwide. Transportation engineers and urban planners develop various traffic management projects in order to solve this issue. One way to evaluate such projects is traffic assignment (TA). The goal of TA is to predict the behaviour of road users for a given period of time (morning and evening peaks, for example). Once such a model is created, it can be used to analyse the usage of a road network and to predict the impact of implementing a potential project. The most commonly used TA model is known as user equilibrium, which is based on the assumption that all drivers minimise their travel time or generalised cost. In this study, we consider the static deterministic user equilibrium TA model.The constant growth of road networks and the need of highly precise solutions (required for select link analysis, network design, etc.) motivate researchers to propose numerous methods to solve this problem. Our study aims to provide a recommendation on what methods are more suitable depending on available computational resources, time and requirements on the solution. In order to achieve this goal, we implement a flexible software framework that maximises the usage of common code and, hence, ensures comparison of algorithms on common ground. In order to identify similarities and differences of the methods, we analyse groups of algorithms that are based on common principles. In addition, we implement and compare several different methods for solving sub-problems and discuss issues related to accumulated numerical errors that might occur when highly accurate solutions are required.     

Optimal algorithms for the average-constrained maximum-sum segment problem

Given a real number sequence A=(a₁,a₂,…,an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A(i,j)=(ai,ai+1,…,aj) that maximizes _∑i?k?jak subject to . In this paper, we give an O(n)-time algorithm for the case where the average upper bound is ineffective, i.e., U=∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω(nlogn) even if the average lower bound is ineffective, i.e., L=−∞.     

A comparison of multiobjective depth-first algorithms

Many real world problems involve several, usually conflicting, objectives. Multiobjective analysis deals with these problems locating trade-offs between different optimal solutions. Regarding graph search problems, several algorithms based on best-first and depth-first approaches have been proposed to return the set of all Pareto optimal solutions. This article presents a detailed comparison between two representatives of multiobjective depth-first algorithms, PIDMOA* and MO-DF-BnB. Both of them extend previous single-objective search algorithms with linear-space requirements to the multiobjective case. Experimental analyses on their time performance over tree-shaped search spaces are presented. The results clarify the fitness of both algorithms to parameters like the number or depth of goal nodes.     

加权编码遗传算法线性函数能力分析

引入基因座系数作为基因座上一阶模式适应度差别的衡量指标;通过基因座系数和一阶积木块的对应关系,分析了线性加权编码用于线性函数编码时生成一阶积木块的能力。分析结果给出了基因座系数的一个上限与加权值的关系,结果同时表明,为保证计算精度,无论加权值如何变化,总有部分基因座上的基因座系数接近于1,因此在相当部分的搜索子空间中搜索随机性强、效率低。     

A comparative analysis of various least-squares identification algorithms

The purpose of this paper is to clarify the relations and to provide some selection guides among several time-series identification algorithms that appear in the literature under different names but which are essentially least-squares identification algorithms where only the numerical solution of the least-squares estimation problem is different. Such algorithms are, apart from the batch and the sequential forms of direct least-squares, the PARCOR (partial correlation) algorithm, (which may be in the Durbin, the Levinson or the autocorrelation form), the lattice or the ladder algorithm, also known as the Markel-Gray algorithm, the square-root algorithm, the equation-error algorithm, and related algorithms.Further to the above, we shall discuss why certain such algorithms differ in performance from the direct least-squares forms, in terms of convergence, convergence-rate, computational effort (speed) per iteration, and in terms of robustness to computational errors, such as arise when using short word-length computers.     

Metaheuristic algorithms for approximate solution to ordinary differential equations of longitudinal fins having various profiles

Differential equations play a noticeable role in engineering, physics, economics, and other disciplines. Approximate approaches have been utilized when obtaining analytical (exact) solutions requires substantial computational effort and often is not an attainable task. Hence, the importance of approximation methods, particularly, metaheuristic algorithms are understood. In this paper, a novel approach is suggested for solving engineering ordinary differential equations (ODEs). With the aid of certain fundamental concepts of mathematics, Fourier series expansion, and metaheuristic methods, ODEs can be represented as an optimization problem. The target is to minimize the weighted residual function (error function) of the ODEs. The boundary and initial values of ODEs are considered as constraints for the optimization model. Generational distance and inverted generational distance metrics are used for evaluation and assessment of the approximate solutions versus the exact (numerical) solutions. Longitudinal fins having rectangular, trapezoidal, and concave parabolic profiles are considered as studied ODEs. The optimization task is carried out using three different optimizers, including the genetic algorithm, the particle swarm optimization, and the harmony search. The approximate solutions obtained are compared with the differential transformation method (DTM) and exact (numerical) solutions. The optimization results obtained show that the suggested approach can be successfully applied for approximate solving of engineering ODEs. Providing acceptable accuracy of the proposed technique is considered as its important advantage against other approximate methods and may be an alternative approach for approximate solving of ODEs.     

On the complexity of preflow-push algorithms for maximum-flow problems

We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n ² m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs inO(n ² m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n ² m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms.Research performed while the author was a Ph.D. student at Cornell University and was partially supported by the Ministry of Education of the Republic of Turkey through the scholarship program 1416.     

A comparison of three shadow volume algorithms

This paper describes and compares three different approaches to computing shadows. Each is based on the idea of shadow volumes: basic algorithm, Shadow Volume BSP Tree algorithm, and Shadow Tiling, based on 2D space subdivision. Binary Space Partition trees are used to organise the polygons in the scene in a front-toback order from the point of view of the light source, and then shadows on a polygon are computed by clipping the polygon to the shadow volumes of polygons closer to the light source. The three algorithms differ in their approach to minimising the number of comparisons of a polygon with the shadow volumes of its predecessors, and one of the algorithms represents the total shadow volume itelf by a BSP tree. The algorithms are compared analytically and statistically.     

A comparison of three string matching algorithms

Three string matching algorithms—straightforward, Knuth-Morris-Pratt and Boyer-Moor—re examined and their time complexities discussed. A comparison of their actual average behaviour is made, based on empirical data presented. It is shown that the Boyel-Moore algorithm is extremely efficient in most cases and that, contrary to the impression one might get from the analytical results, the Knuth-Morris-Pratt algorithm is not significantly better on the average than the straightforward algorithm.     

Robustness of deadlock avoidance algorithms for sequential processes

Although deadlock avoidance issue has attracted much attention and has been extensively studied, most of the existing results assume reliable machines. This assumption makes it difficult to apply existing deadlock avoidance algorithms to real manufacturing systems with unreliable machines. This paper presents the results to apply an existing deadlock avoidance algorithm to systems with unreliable machines by analyzing the robustness of the deadlock avoidance algorithm. Sequential production processes are considered in this paper, and Petri Net is adopted as the tool for modeling and analysis of the sequential processes. Different types of tolerable machine failures under which liveness property can be preserved are characterized. Computational complexity of the proposed algorithm is analyzed.     

Parallel algorithms for minimal spanning trees of directed graphs

The main results of this paper are efficient parallel algorithms, MSP and LOCATE, for computing minimal spanning trees and locating minimal paths in directed graphs, respectively. Algorithm MSP has time complexityO(log³ n) usingO(n ³/logn) processors, while LOCATE has time complexityO(logn) usingO(n ²) processors. Algorithm MSP is derived from sequential algorithms, when the unbounded parallelism model is used.     

A comparison of two parallel algorithms for the symmetric eigenproblem

Two algorithms for the eigensolution of real symmetric matrices [8] are discussed. The first is a variant of the classical Jacobi method and the second is also based on orthogonal transforms. Both algorithms may be readily expressed in forms which allow the power of SIMD (single instruction multiple data) machines to be exploited. The performances of the algorithms on the ICL DAP (distributed array processor) and the CRAY-1 are compared.     

A comparison of algorithms for vertex normal computation

We investigate current vertex normal computation algorithms and evaluate their effectiveness at approximating analytically computable (and thus comparable) normals for a variety of classes of model. We find that the most accurate algorithm depends on the class and that for some classes, none of the available algorithms is particularly good. We also compare the relative speeds of all algorithms.