Barcode design by evolutionary computation

This paper proposes a method for generating 2-dimensional barcode incorporated some illustrations inside of the code without detracting machine-readability and stored information. We formulate the task that finding appropriate positions, scales, and angles of illustrations, photographs, logos or other image items put in QR code as an optimization problem. By using evolutionary computation algorithm, the proposed system can find positions in which given image items can be merged without damaging machine-readability. QR code is trademarked by Denso Wave, inc. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Solving equations by hybrid evolutionary computation techniques

Evolutionary computation techniques have mostly been used to solve various optimization and learning problems. This paper describes a novel application of evolutionary computation techniques to equation solving. Several combinations of evolutionary computation techniques and classical numerical methods are proposed to solve linear and partial differential equations. The hybrid algorithms have been compared with the well-known classical numerical methods. The experimental results show that the proposed hybrid algorithms outperform the classical numerical methods significantly in terms of effectiveness and efficiency     

Providing an appropriate search space to solve the fatigue problem in interactive evolutionary computation

The user fatigue problem in interactive evolutionary computation (IEC) is a complex and interesting issue. If the IEC search space is created from the experience or knowledge of domain experts rather than from users values, it causes two potential problems which lead to fatigue problems in IEC: 1) inefficiency and 2) boredom. Therefore, we propose a customer values-based IEC model, solving the fatigue problem by avoiding the potential problems. A case study involving the design of mineral water bottles was used to verify the anti-fatigue capability of the users when using the proposed model. For comparison with the traditional domain knowledge-based model, we built two IEC systems, a customer values-based system and a traditional system, and conducted a user burden test and a system efficiency test over a two-week period. The results of both tests show that our proposed system performed better than the traditional system in designing mineral water bottles. Fang-Cheng Hsu, Ph.D.: He received his M.S. degree from Tamkang University, Taiwan, in 1985 and Ph.D. degree from Department of Information Management, National Central University, Taiwan, in 2000. He is an associate professor of Information Management at Aletheia University in Taiwan. Prior to this, he was on the faculty at Tamsui Oxford College. His current research interests include interactive evolutionary computation and evolutionary computation-based decision support systems. Peter Huang: He received his B.A. degree from Department of Information Management, Aletheia University, Taiwan, in 1997, and M.B.A. degree from Graduate Institute of Management Science, Aletheia University, Taiwan, in 2003. He is on staff at Information Technology Total Services and is a part-time lecturer at Aletheia University. His current research interests are decision analysis and interactive evolutionary computation.     

新型模拟进化计算

提出了一种新的模拟进化计算,它模仿新宇宙进化理论中膨胀、收缩两种模式交互作用,推动宇宙进步的过程。膨胀操作提高了种群的多样性和进化算法克服局部收敛的能力,收缩操作吸取了不同群体的优良特性,改善了算法的计算效率,实验结果表明该范式是有效的。     

Redundant representations in evolutionary computation

This paper discusses how the use of redundant representations influences the performance of genetic and evolutionary algorithms. Representations are redundant if the number of genotypes exceeds the number of phenotypes. A distinction is made between synonymously and non-synonymously redundant representations. Representations are synonymously redundant if the genotypes that represent the same phenotype are very similar to each other. Non-synonymously redundant representations do not allow genetic operators to work properly and result in a lower performance of evolutionary search. When using synonymously redundant representations, the performance of selectorecombinative genetic algorithms (GAs) depends on the modification of the initial supply. We have developed theoretical models for synonymously redundant representations that show the necessary population size to solve a problem and the number of generations goes with O(2(kr)/r), where kr is the order of redundancy and r is the number of genotypic building blocks (BB) that represent the optimal phenotypic BB. As a result, uniformly redundant representations do not change the behavior of GAs. Only by increasing r, which means overrepresenting the optimal solution, does GA performance increase. Therefore, non-uniformly redundant representations can only be used advantageously if a-priori information exists regarding the optimal solution. The validity of the proposed theoretical concepts is illustrated for the binary trivial voting mapping and the real-valued link-biased encoding. Our empirical investigations show that the developed population sizing and time to convergence models allow an accurate prediction of the empirical results.     

Image segmentation using evolutionary computation

Image segmentation denotes a process by which a raw input image is partitioned into nonoverlapping regions such that each region is homogeneous and the union of any two adjacent regions is heterogeneous. A segmented image is considered to be the highest domain-independent abstraction of an input image. The image segmentation problem is treated as one of combinatorial optimization. A cost function which incorporates both edge information and region gray-scale uniformity is defined. The cost function is shown to be multivariate with several local minima. The genetic algorithm, a stochastic optimization technique based on evolutionary computation, is explored in the context of image segmentation. A class of hybrid evolutionary optimization algorithms based on a combination of the genetic algorithm and stochastic annealing algorithms such as simulated annealing, microcanonical annealing, and the random cost algorithm is shown to exhibit superior performance as compared with the canonical genetic algorithm. Experimental results on gray-scale images are presented     

网格计算及其在进化计算中的应用

提出了一种将网格技术应用于进化算法的计算模式。这种计算模式使用规则与规则集共同演变的模式,实现了数据挖掘技术中的分类。它利用网格计算技术的优势,提高了以往复杂的数据挖掘技术的能力和效率。     

Tree search and quantum computation

Traditional tree search algorithms supply a blueprint for modeling problem solving behaviour. A diverse spectrum of problems can be formulated in terms of tree search. Quantum computation, namely Grover’s algorithm, has aroused a great deal of interest since it allows for a quadratic speedup to be obtained in search procedures. In this work we consider the impact of incorporating classical search concepts alongside Grover’s algorithm into a hybrid quantum search system. Some of the crucial points examined include: (1) the reverberations of contemplating the use of non-constant branching factors; (2) determining the consequences of incorporating an heuristic perspective into a quantum tree search model.     

Multiobjective evolutionary computation for supersonic wing-shapeoptimization

This paper discusses the design optimization of a wing for supersonic transport (SST) using a multiple-objective genetic algorithm (MOGA). Three objective functions are used to minimize the drag for supersonic cruise, the drag for transonic cruise, and the bending moment at the wing root for supersonic cruise. The wing shape is defined by 66 design variables. A Euler flow code is used to evaluate supersonic performance, and a potential flow code is used to evaluate transonic performance. To reduce the total computational time, flow calculations are parallelized on an NEC SX-4 computer using 32 processing elements. The detailed analysis of the resulting Pareto front suggests a renewed interest in the arrow wing planform for the supersonic wing     

Identification of cohesive crack fracture parameters by evolutionary search

This paper is concerned with the application and performance of two evolutionary search techniques to identify the parameters characterizing mode I cohesive crack models. In particular, genetic-based heuristic schemes, implemented via a classical genetic algorithm and also as a differential evolution process, are considered. Actual experimental data are used to assess the schemes for both piecewise linear and nonlinear softening models. The results of these two adaptive algorithms are also compared with the performance of a previously proposed local optimization approach involving formulation of the inverse problem as a mathematical program with equilibrium constraints.     

一种新的基于进化计算的聚类算法

聚类是数据挖掘领域的重要研究内容之一。针对遗传聚类算法较好的稳定性与粒子群优化算法较强的局部搜索能力,在交叉、变异算子后叠加粒子群优化算子的方法实现了二者的结合,提出了GAPSO聚类算法,既保持了遗传算法的稳定性与泛化性的优势,又发挥了PSO算法收敛效率高的特点。通过对10组二维空间上的聚类样本进行实验研究显示,GAPSO聚类算法在收敛效率上显著优于GA聚类算法,在稳定性上优于PSO聚类算法。     

Evolving Nash-optimal poker strategies using evolutionary computation

This paper focuses on the development of a competitive computer player for the one versus one Texas Hold’em poker using evolutionary algorithms (EA). A Texas Hold’em game engine is first constructed where an efficient odds calculator is programmed to allow for the abstraction of a player’s cards, which yield important but complex information. Effort is directed to realize an optimal player that will play close to the Nash equilibrium (NE) by proposing a new fitness criterion. Preliminary studies on a simplified version of poker highlighted the intransitivity nature of poker. The evolved player displays strategies that are logical but reveals insights that are hard to comprehend e.g., bluffing. The player is then benchmarked against Poki and PSOpti, which is the best heads-up Texas Hold’em artificial intelligence to date and plays closest to the optimal Nash equilibrium. Despite the much constrained chromosomal strategy representation, simulated results verified that evolutionary algorithms are effective in creating strategies that are comparable to Poki and PSOpti in the absence of expert knowledge.     

Asynchronous and implicitly parallel evolutionary computation models

This paper presents the design and the application of asynchronous models of parallel evolutionary algorithms. An overview of the existing parallel evolutionary algorithm (PEA) models and available implementations is given. We present new PEA models in the form of asynchronous algorithms and implicit parallelization, as well as experimental data on their efficiency. The paper also discusses the definition of speedup in PEAs and proposes an appropriate speedup measurement procedure. The described parallel EA algorithms are tested on problems with varying degrees of computational complexity. The results show good efficiency of asynchronous and implicit models compared to existing parallel algorithms.     

Biclustering of expression data with evolutionary computation

Microarray techniques are leading to the development of sophisticated algorithms capable of extracting novel and useful knowledge from a biomedical point of view. In this work, we address the biclustering of gene expression data with evolutionary computation. Our approach is based on evolutionary algorithms, which have been proven to have excellent performance on complex problems, and searches for biclusters following a sequential covering strategy. The goal is to find biclusters of maximum size with mean squared residue lower than a given /spl delta/. In addition, we pay special attention to the fact of looking for high-quality biclusters with large variation, i.e., with a relatively high row variance, and with a low level of overlapping among biclusters. The quality of biclusters found by our evolutionary approach is discussed and the results are compared to those reported by Cheng and Church, and Yang et al. In general, our approach, named SEBI, shows an excellent performance at finding patterns in gene expression data.     

Embodiment of evolutionary computation in general agents

Holland's Adaptation in Natural and Artificial Systems largely dealt with how systems, comprised of many self-interested entities, can and should adapt as a whole. This seminal book led to the last 25 years of work in genetic algorithms (GAs) and related forms of evolutionary computation (EC). In recent years, the expansion of the Internet, other telecommunications technologies, and other large scale networks have led to a world where large numbers of semi-autonomous software entities (i.e., agents) will be interacting in an open, universal system. This development cast the importance of Holland's legacy in a new light. This paper argues that Holland's fundamental arguments, and the years of developments that have followed, have a direct impact on systems of general network agents, regardless of whether they explicitly exploit EC. However, it also argues that the techniques and theories of EC cannot be directly transferred to the world of general agents (rather than EC-specific) without examination of effects that are embodied in general software agents. This paper introduces a framework for EC interchanges between general-purpose software agents. Preliminary results are shown that illustrate the EC effects of asynchronous actions of agents within this framework. Building on this framework, coevolutionary agents that interact in a simulated producer/consumer economy are introduced. Using these preliminary results as illustrations, areas for future investigation of embodied EC software agents are discussed.     

Fixed-outline floorplanning using robust evolutionary search

Typical floorplanning concerns a series of objectives, such as area, wirelength, and routability, etc., with various aspect ratios of modules in a free-outline regime. However, in a hierarchical design flow for very large ASICs and SoCs, a floorplan can be completely useless for a situation where its outline is dissatisfied. In this paper, we study the fixed-outline floorplanning problem that is more applicable to the hierarchical design style. We develop an efficient algorithm based on robust evolutionary search and achieve substantially improved success rate. We also propose a new approach to handle soft modules to further adjust the generated floorplan to fit into the prescribed chip outline. The effectiveness of our methods is demonstrated on several large cases of MCNC and GSRC benchmarks.     

分布式计算中的搜索树技术研究

面向范例的分布式计算是一种新型分布式计算环境,它基于移动代理系统使用范例来实现分布式计算.这些范例提供了用于通信的下层结构,应用程序员只需通过图形界面来提供明确的应用功能.该分布式计算环境支持5个公共范例:任务包范例、搜索树范例、继承编程范例、有限差范例以及个体仿真范例.以搜索树范例为例,描述了搜索树的基本结构,并对其进行分布式实现,阐明了面向范例的分布式计算的具体实现方法.