On using deterministic functions to reduce randomness in probabilistic algorithms

We show the existence of nonuniform schemes for the following sampling problem: Given a sample space with n points, an unknown set of size n/2, and s random points, it is possible to generate deterministically from them s + k points such that the probability of not hitting the unknown set is exponentially smaller in k than 2^−s. Tight bounds are given for the quality of such schemes. Explicit, uniform versions of these schemes could be used for efficiently reducing the error probability of randomized algorithms. A survey of known constructions (whose quality is very far from the existential result) is included.     

Characterization and design of out-of-ecliptic trajectories using deterministic crowding genetic algorithms

This paper investigates the application of Deterministic Crowding Genetic Algorithms to the characterization and design of special trajectories in the spatial circular restricted three-body problem with the Sun and the Earth as the primary gravitational bodies. These trajectories are characterized by large displacements normal to the Sun–Earth ecliptic plane. This attribute renders them particularly suitable for space-borne infrared observatories, because the normal component of motion results in a significantly reduced noise from the interplanetary (zodiacal) dust and a concomitant reduction in the necessary size of the optical collecting area. The characterization process yields three new types of trajectories with large normal displacement. By using the results of the characterization process, we continue with genetic algorithms-based trajectory design, which yields promising results in terms of reduction of the zodiacal dust noise.     

Mixed deterministic and probabilistic networks

The paper introduces mixed networks, a new graphical model framework for expressing and reasoning with probabilistic and deterministic information. The motivation to develop mixed networks stems from the desire to fully exploit the deterministic information (constraints) that is often present in graphical models. Several concepts and algorithms specific to belief networks and constraint networks are combined, achieving computational efficiency, semantic coherence and user-interface convenience. We define the semantics and graphical representation of mixed networks, and discuss the two main types of algorithms for processing them: inference-based and search-based. A preliminary experimental evaluation shows the benefits of the new model.     

遗传算法中自适应方法的比较和分析

分析了前人提出的具有代表性的自适应遗传算法,使用23个测试函数对SGA和3种AGA进行实验比较,讨论并总结出各种AGA的优劣所在,为新研究理念的提出提供基础,也为工业应用提供一个参考标准.实验结果表明,基于聚类分析的AGA在算法性能上较其它自适应遗传算法更优,具有很高的实用价值和发展前景.     

Acceleration of cellular automata algorithms using genetic algorithms

The following problem is solved: Given a Cellular Automaton with continuous state space which simulates a physical system or process, use a Genetic Algorithm in order to find a Cellular Automaton with discrete state space, having the smallest possible lattice size and the smallest possible number of discrete states, the results of which are as close as possible to the results of the Cellular Automaton with continuous state space. The Cellular Automaton with discrete state space evolves much faster than the Cellular Automaton with continuous state space. The state spaces of two Cellular Automata have been discretized using a Genetic Algorithm. The first Cellular Automaton simulates the two-dimensional photoresist etching process in integrated circuit fabrication and the second is used to predict forest fire spreading. A general method for the discretization of the state space of Cellular Automata using a Genetic Algorithm is also presented. The aim of this work is to provide a method for accelerating the execution of algorithms based on Cellular Automata (Cellular Automata algorithms) and to build a bridge between Cellular Automata as models for physical systems and processes and Cellular Automata as a VLSI architecture.     

Tracking performance optimizations for deterministic and stochastic references via moving-average precompensator

A technique for designing moving-average precompensators that give the minimization of a tracking performance cost function while tracking either deterministic or stochastic reference inputs is presented. For deterministic reference inputs, the cost function is an infinite-time horizon quadratic sum of the dynamically weighted tracking error and dynamically weighted control input. For stochastic reference inputs, the sum of the variances of the dynamically weighted tracking error and dynamically weighted control input is minimized. The two types of cost function are shown to be equivalent and the same design technique is used for both. The precompensator is intended to be designed for use in cascade with a control system which has already been designed, possibly without regard to tracking. The minimization of the cost function is enhanced by increasing the number of terms in the precompensator above the minimum necessary to keep the cost finite. A simulation example is presented showing how performance improvements over pole-placement and error transfer function zero-placement controllers may be achieved.     

Improving swarming using genetic algorithms

The verification of temporal properties against a given system may require the exploration of its full state space. In explicit model checking, this exploration uses a depth-first search and can be achieved with multiple randomized threads to increase performance. Nonetheless, the topology of the state space and the exploration order can cap the speedup up to a certain number of threads. This paper proposes a new technique that aims to tackle this limitation by generating artificial initial states, using genetic algorithms. Threads are then launched from these states and thus explore different parts of the state space. Our prototype implementation is 10% faster than state-of-the-art algorithms on a general benchmark and 40% on a specialized benchmark. Even if we expected a decrease in an order of magnitude, these results are still encouraging since they suggest a new way to handle existing limitations. Empirically, our technique seems well suited for “linear” topology, i.e., the one we can obtain when combining model checking algorithms with partial-order reduction techniques.

     

Motion fairing using genetic algorithms

In this paper, we solve the motion smoothing problem using genetic algorithms. Smooth motion generation is essential in the computer animation and virtual reality area. The motion of a rigid body in general consists of translation and orientation. The former is described by a space curve in three-dimensional Euclidean space while the latter is represented by a curve in the unit quaternion space. By adopting the geometric approach, the smoothness of both translation data and orientation data is measured from the strain energy perspective and a nonlinear optimization problem is formulated that aims to minimize the weighted sum of the strain-energy and the sum of the squared errors. A hybrid algorithm that combines genetic algorithms and local search schemes is deployed to solve this optimization problem and the experiments show that both smoothness and shape preservation of the resulting motion can be achieved by the proposed algorithm.     

Shape analysis using genetic algorithms

This paper introduces a novel methodology for shape discrimination by combining pattern recognition techniques such as morphological processing with concepts from artificial intelligence and machine learning such as genetic algorithms (GAs). High-performance shape discrimination operators, defined as variable structuring elements and sequenced as program forms, are derived using GAs. The population of operators, iteratively evaluated according to an performance index corresponding to shape discrimination ability, evolves into an optimal set of operators using the evolutionary principles of genetic search. Experimental results are included to illustrate the feasibility of our novel methodology for developing robust shape analysis methods.     

Dimensionality reduction using genetic algorithms

Pattern recognition generally requires that objects be described in terms of a set of measurable features. The selection and quality of the features representing each pattern affect the success of subsequent classification. Feature extraction is the process of deriving new features from original features to reduce the cost of feature measurement, increase classifier efficiency, and allow higher accuracy. Many feature extraction techniques involve linear transformations of the original pattern vectors to new vectors of lower dimensionality. While this is useful for data visualization and classification efficiency, it does not necessarily reduce the number of features to be measured since each new feature may be a linear combination of all of the features in the original pattern vector. Here, we present a new approach to feature extraction in which feature selection and extraction and classifier training are performed simultaneously using a genetic algorithm. The genetic algorithm optimizes a feature weight vector used to scale the individual features in the original pattern vectors. A masking vector is also employed for simultaneous selection of a feature subset. We employ this technique in combination with the k nearest neighbor classification rule, and compare the results with classical feature selection and extraction techniques, including sequential floating forward feature selection, and linear discriminant analysis. We also present results for the identification of favorable water-binding sites on protein surfaces     

Order acceptance using genetic algorithms

This paper uses a genetic algorithm to solve the order-acceptance problem with tardiness penalties. We compare the performance of a myopic heuristic and a genetic algorithm, both of which do job acceptance and sequencing, using an upper bound based on an assignment relaxation. We conduct a pilot study, in which we determine the best settings for diversity operators (clone removal, mutation, immigration, population size) in connection with different types of local search. Using a probabilistic local search provides results that are almost as good as exhaustive local search, with much shorter processing times. Our main computational study shows that the genetic algorithm always dominates the myopic heuristic in terms of objective function, at the cost of increased processing time. We expect that our results will provide insights for the future application of genetic algorithms to scheduling problems.     

Machine-component grouping using genetic algorithms

One major problem in cellular manufacturing is the grouping of component parts with similar processing requirements into part families, and machines into manufacturing cells to facilitate the manufacturing of specific part families assigned to them. The objective is to minimize the total inter-cell and intra-cell movements of parts during the manufacturing process. In this paper, a mathematical model is presented to describe the characteristics of such a problem. An approach based on the concept of genetic algorithms is developed to determine the optimal machine-component groupings. Illustrative examples are used to demonstrate the efficiency of the proposed approach. Indeed, the results obtained show that the proposed genetic approach is a simple and efficient means for solving the machine-component grouping problem.     

遗传算法编码方案比较*

对具体问题设计合理的编码方案是遗传算法的应用难点之一,目前尚无统一的解决方法。在着重分析和比较二进制编码、实数编码、矩阵编码、树型编码和量子比特编码的基础上,总结出这些常用的遗传算法编码方案的原理、优缺点、适用范围和应用趋势等规律,并进一步探讨了遗传算法编码方案未来的研究方向。     

Rendering algorithms for deterministic fractals

Heavy computation requirements have inhibited the application of fractal technology, but new algorithms for coding and displaying iterated function system fractals are achieving real-time performance in software. We discuss the standard rendering algorithms and introduce a variation that performs a minimal number of arithmetic operations when constructing an approximate fractal. In addition, we describe novel extensions that let us render gray-scale and color fractal images     

Two-dimensional packing problems using genetic algorithms

This paper presents a technique for applying genetic algorithms for the two-dimensional packing problem. The approach is applicable to not only convex shaped objects, but can also accommodate any type of concave and complex shaped objects including objects with holes. In this approach, a new concept of a two-dimensional genetic chromosome is introduced. The total layout space is divided into a finite number of cells for mapping it into this 2D genetic algorithm chromosome. The mutation and crossover operators have been modified and are applied in conjunction with connectivity analysis for the objects to reduce the creation of faulty generations. A new feature has been added to the Genetic Algorithm (GA) in the form of a new operator called compaction. Several examples of GA-based layout are presented.     

Structural pattern recognition using genetic algorithms

This paper presents a genetic algorithm (GA) based optimization procedure for the solution of structural pattern recognition problem using the attributed relational graph representation and matching technique. In this study, candidate solutions are represented by integer strings and the population is randomly initialized. The GA is employed to generate a monomorphic mapping. As all the mapping constraints are not enforced during the search phase in order to speedup the search, an efficient pose clustering algorithm is used to eliminate spurious matches and to determine the presence of the model in the scene. The performance of the proposed approach to pattern recognition by subgraph isomorphism is demonstrated using line patterns and silhouette images.     

采用半初始化和概率扰动策略改进的遗传算法

针对遗传算法在函数寻优过程中收敛速度慢、易陷入局部最优解的问题,提出一种采用半初始化和概率扰动策略改进的遗传算法DIAGA。首先,通过引入概率扰动策略增加了算法迭代后期的种群多样性,采用半初始化从根本上改变了算法在全局最优解比较过程中的局限性;然后利用马尔可夫链理论证明了DIAGA的收敛性;最后,对六个标准测试函数进行仿真测试。仿真实验结果表明,提出的DIAGA有效摆脱了局部收敛,在搜索精度、收敛速度上具有明显优势,就多维测试函数而言,寻优精度提高了约29%。     

Dynamic vehicle routing using genetic algorithms

Many difficult combinatorial optimization problems have been modeled as static problems. However, in practice, many problems are dynamic and changing, while some decisions have to be made before all the design data are known. For example, in the Dynamic Vehicle Routing Problem (DVRP), new customer orders appear over time, and new routes must be reconfigured while executing the current solution. Montemanni et al. [1] considered a DVRP as an extension to the standard vehicle routing problem (VRP) by decomposing a DVRP as a sequence of static VRPs, and then solving them with an ant colony system (ACS) algorithm. This paper presents a genetic algorithm (GA) methodology for providing solutions for the DVRP model employed in [1]. The effectiveness of the proposed GA is evaluated using a set of benchmarks found in the literature. Compared with a tabu search approach implemented herein and the aforementioned ACS, the proposed GA methodology performs better in minimizing travel costs. Franklin T. Hanshar is currently a M.Sc. student in the Department of Computing and Information Science at the University of Guelph, Ontario, Canada. He received a B.Sc. degree in Computer Science from Brock University in 2005. His research interests include uncertain reasoning, optimization and evolutionary computation. Beatrice Ombuki-Berman is currently an Associate Professor in the Department of Computer Science at Brock University, Ontario, Canada. She obtained a PhD and ME in Information Engineering from University of The Ryukyus, Okinawa, Japan in 2001 and 1998, respectively. She received a B.Sc. in Mathematics and Computer Science from Jomo Kenyatta University, Nairobi, Kenya. Her primary research interest is evolutionary computation and applied optimization. Other research interests include neural networks, machine learning and ant colony optimization.     

遗传算法在货运车辆优化调度中的应用

本文在阐述了遗传算法基本理论和车辆优化调度基本理论的基础上,进一步论述了遗传算法在一般车辆优化调度中的应用。参考近年来遗传算法应用于车辆优化调度的一些文献,对应用于不同情况下货运车辆优化调度的遗传算法进行了总结和分析。最后对本文进行总结,并对未来的遗传算法在货运车辆优化调度中的应用提出了发展趋势。     

Testing real-time systems using genetic algorithms

The development of real-time systems is an essential industrial activity whose importance is increasing. The most important analytical method to assure the quality of real-time systems is dynamic testing. Testing is the only method which examines the actual run-time behaviour of real-time software, based on an execution in the real application environment. Dynamic aspects like the duration of computations, the memory actually needed, or the synchronization of parallel processes are of major importance for the correct function of real-time systems and have to be tested. A comprehensive investigation of existing software test methods shows that they mostly concentrate on testing for functional correctness. They are not suited for an examination of temporal correctness which is essential to real-time systems. Very small systems show a wide range of different execution times. Therefore, existing test procedures must be supplemented by new methods, which concentrate on determining whether the system violates its specified timing constraints. In general, this means that outputs are produced too early or their computation takes too long. The task of the tester is to find the inputs with the longest or shortest execution times to check whether they produce a temporal error. If the search for such inputs is interpreted as a problem of optimization, genetic algorithms can be used to find the inputs with the longest or shortest execution times automatically. The fitness function is the execution time measured in processor cycles. Experiments using genetic algorithms on a number of programs with up to 1511 LOC and 843 integer input parameters have successfully identified new longer and shorter paths than had been found using random testing or systematic testing. Genetic algorithms are able therefore to check large programs and they show considerable promise in establishing the validity of the temporal behaviour of real-time software.