Deterministic VLSI block placement algorithm using Less Flexibility First principle

In this paper,a simple while effective deterministic algorithm for solving the VLSI block placement problem is proposed considering the packing area and interconnect wiring simultaneously.The algorithm is based on a principle inspired by observations of ancient professionals in solving their similar problems.Using the so-called Less Flexibility First principle,it is tried to pack blocks with the least packing flexibility on its shape and interconnect requirement to the empty space with the least packing flexibility in a greedy manner.Experimental results demonstrate that the algorithm,though simple,is quite effective in solving the problem.The same philosophy could also be used in designing efficient heuristics for other hard problems,such as placement with preplaced modules,placement with L/T shape modules,etc.     

Unparsing expressions with prefix and postfix operators

Unparsing is the problem of transforming an internal representation of a program into an external, concrete syntax. In conjunction with prettyprinting, it is useful for generating readable programs from internal representations. If the target language uses prefix and postfix operators, the problem is nontrivial. This paper shows how to unparse expressions using a simple, bottom-up tree walk, which keeps track of the least tightly binding operator not enclosed by parentheses. During the tree walk, this operator is compared with the operator of the parent expression, and parentheses are inserted based on the precedence, associativity, and fixity (infix, prefix, or postfix) of the two operators. The paper is a literate program. It includes code for the unparser and for its inverse parser, both of which can handle operators of dynamically chosen precedence and associativity. Supporting such operators is useful for languages like ML, in which programmers may assign precedence and associativity to their own functions. © 1998 John Wiley & Sons, Ltd.     

一种改进的集成电路模块有效布局算法

改进了一种求解集成电路模块布局问题的启发式算法。以边界矩形周长最小为目标,设计了模块的优先序列,并在布局过程中动态调整,重新设计布局优先度,并简化模块的占边动作,重写占角动作,对模块布局放置的多个可能位置进行比较,并将其放置在优先度最高的适当区域。经实例测试,结果表明该算法简洁高效,面积利用率有较大提高。     

基于分布式遗传算法的水质传感器布置优化研究

水质传感器优化布置是指在城镇配水管网中最优位置布置水质传感器对污染物进行检测,从而达到监测预警的目的,其本质是一类大规模离散组合优化问题。首先从数学上对该问题进行分析,论证了其具有NP-Complete特性;然后针对该问题计算开销大等特点,提出了基于Spark云计算模型的分布式遗传算法;最后以一个典型的复杂配水管网为对象进行实验,仿真结果表明,所提出的算法不仅具有搜索速度快、精度高等优点,而且还具有较好的线性加速比。     

Micro-scale truss optimization using genetic algorithm

This paper describes the development of a genetic algorithm that is capable of optimizing the mass of micro-scale trusses. Belonging to the group of periodic cellular materials, micro-scale trusses are characterized by the creation of a base cell with a pattern that is repeated in space until a global structure is obtained. Investigation in this field has generally been focused on the design of base cells and their resistance once the final structure is obtained. In this project we have attempted to optimize each individual cell and in particular its elements according to the loads and boundary conditions applied to the global structure. With this objective, we defined a dichotomic search algorithm that establishes a set of cross-sectional areas suitable for the micro-scale truss, formulated the penalty coefficient for the over-sized elements, and studied the clones and rebirth process in order to avoid stagnation of the genetic algorithm. The cell elements used in this project were equal to or less than to 1 mm long, with a cross-sectional area in the order of 10^− 9 m².     

基于模糊遗传算法的埋入式电阻热布局优化

针对标准遗传算法优化埋入式电阻热布局存在的过早收敛等问题,通过设计适应度函数、采用模糊逻辑控制器自适应调整交叉概率和变异概率,以及对长时间未进化的种群实施局部灾变等措施维持种群多样性,使算法最终收敛于全局最优解.仿真结果表明,该算法能够更好地抑制早熟收敛,算法优化布局结果的温度分布更平均,并通过热成像仪对实验样件进行温度分布测试验证了算法的有效性.     

利用改进遗传算法优化PID参数

为了改善单纯遗传算法早熟收敛与寻优能力不足的问题,将粒子群算法引入遗传算法变异操作中,提出了一种基于遗传算法与粒子群算法的组合算法。将改进的遗传算法应用于PID控制器参数优化中,通过仿真实验表明,新算法效果明显优于单纯遗传算法,能有效克服早熟收敛现象、降低随机性初始种群的影响、提高算法收敛精度,具有良好的收敛性和寻优能力。     

基于小生境遗传算法的分类优化方法

对于多分类问题,大多是经二分类器组合进行训练的,在分类类别多、特征维数高时,存在识别准确率不高和训练速度较慢的问题。将超球支持向量机应用到多类问题,为每个类建立一个超球体模型,通过多个超球体划分样本空间。采用改进的基于排挤的小生境遗传算法(improved crowding niche genetic algorithm,ICNGA)进行特征选择,为不同的目标类别寻找最优的特征子集,优化超球支持向量机的输入。利用UCI标准数据集的数值实验表明,在分类数据类别较多、特征维数较高时,经过ICNGA特征选择之后的多超球支持向量机的识别准确度更好,非常适合解决类别数多、特征维数高的分类问题。     

Stacking sequence optimization with genetic algorithm using a two-level approximation

We propose a new method for laminate stacking sequence optimization based on a two-level approximation and genetic algorithm (GA), and establish an optimization model including continuous size variables (thicknesses of plies) and discrete variables (0/1 variables that represent the existence of each ply). To solve this problem, a first-level approximate problem is constructed using the branched multipoint approximate (BMA) function. Since mixed-variables are involved in the first-level approximate problem, a new optimization strategy is introduced. The discrete variables are optimized through the GA. When calculating the fitness of each member in the population of GA, a second-level approximate problem that can be solved by the dual method is established to obtain the optimal thicknesses corresponding to the each given ply orientation sequence. The two-level approximation genetic algorithm optimization is performed starting from a ground laminate structure, which could include relatively arbitrarily discrete set of angles. The method is first applied to cylindrical laminate design examples to demonstrate its efficiency and accuracy compared with known methods. The capacity of the optimization strategy to solve more complex problems is then demonstrated using a design example. With the presented method, the stacking sequence in analytical tools can be directly taken as design variables and no intermediate variables need be adopted.     

Fuzzy multiobjective optimization of truss-structures using genetic algorithm

In this paper, a method for solving fuzzy multiobjective optimization of space truss with a genetic algorithm is proposed. This method enables a flexible method for optimal system design by applying fuzzy objectives and fuzzy constraints. The displacement, tensile stress, fuzzy sets, membership functions and minimum size constraints are considered in formulation of the design problem. An algorithm was developed by using MATLAB programming. The algorithm is illustrated on 56-bar space truss system design problem and the results are discussed.     

Development of a genetic algorithm for component placement sequence optimization in printed circuit board assembly

This paper describes the development and evaluation of a custom application exploring the use of genetic algorithms (GA) to solve a component placement sequencing problem for printed circuit board (PCB) assembly. In the assembly of PCB’s, the component placement process is often the bottleneck, and the equipment to complete component placement is often the largest capital investment. The number of components placed on a PCB can range from few to hundreds. As a result, developing an application to determine an optimal or near-optimal placement sequence can translate into reduced cycle times for the overall assembly process and reduced assembly costs. A custom application was developed to evaluate the effectiveness of using GA’s to solve the component placement sequencing problem. A designed experiment was used to determine the best representation and crossover type, crossover rate, and mutation rate to use in solving a component sequencing problem for a PCB consisting of 10 components being placed on a single-headed placement machine. Three different representations (path, ordinal, and adjacency) and six appropriate crossover types (partially mapped, ordered, cycle, classical, alternating edges, and heuristic) were evaluated at three different mutation rates and at 11 crossover rates. Two algorithm response variables, the total distance traveled by the placement head and the algorithm solution efficiency (measured as number of generations and algorithm solution time) were used to evaluate the different GA applications. The combination of representation and crossover type along with mutation rate were found to be the most significant parameters in the algorithm design. In particular, path representation with order crossover was found to produce the best solution as measured by the total distance traveled as well as the solution generation efficiency. Increasing the mutation rate led to slightly improved solutions in terms of head travel, but also resulted in increased solution time.     

Adaptive knot placement using a GMM-based continuous optimization algorithm in B-spline curve approximation

One of the key problems in using B-splines successfully to approximate an object contour is to determine good knots. In this paper, the knots of a parametric B-spline curve were treated as variables, and the initial location of every knot was generated using the Monte Carlo method in its solution domain. The best km knot vectors among the initial candidates were searched according to the fitness. Based on the initial parameters estimated by an improved k-means algorithm, the Gaussian Mixture Model (GMM) for every knot was built according to the best km knot vectors. Then, the new generation of the population was generated according to the Gaussian mixture probabilistic models. An iterative procedure repeating these steps was carried out until a termination criterion was met. The GMM-based continuous optimization algorithm could determine the appropriate location of knots automatically. A set of experiments was then implemented to evaluate the performance of the new algorithm. The results show that the proposed method achieves better approximation accuracy than methods based on artificial immune system, genetic algorithm or squared distance minimization (SDM).     

Multi-objective optimization of sensor array using genetic algorithm

A multi-objective optimization method using genetic algorithm was proposed for sensor array optimization. Based on information theory, selectivity and diversity were used as the criteria for constructing two objective functions. A statistic measurement of resolving power, general resolution factor, and visual inspection were used to evaluate the optimization results with the aid of principal component analysis. In each Pareto set, most nondominated solutions had better statistics than the combination using all potential sensors. Also the principal component plots showed that different vapor classes were generally better separated after optimization. The experiment results indicated that the proposed method could successfully identify a set of Pareto optimal solutions of small size; and most optimized sensor arrays provided input with improved quality, i.e. better separation of target analytes. The running time for implementing the multi-objective optimization was satisfactory.     

Multi-objective reliability optimization for dissimilar-unit cold-standby systems using a genetic algorithm

A genetic algorithm approach is used to solve a multi-objective discrete reliability optimization problem in a k dissimilar-unit non-repairable cold-standby redundant system. Each unit is composed of a number of independent components with generalized Erlang distributions arranged in a series–parallel configuration. There are multiple component choices with different distribution parameters available for being replaced with each component of the system. The objective of the reliability optimization problem is to select the best components, from the set of available components, to be placed in the standby system in order to minimize the initial purchase cost of the system, maximize the system MTTF (mean time to failure), minimize the system VTTF (variance of time to failure) and also maximize the system reliability at the mission time. Finally, we apply a genetic algorithm with double strings using continuous relaxation based on reference solution updating (GADSCRRSU) to solve this multi-objective problem, using goal attainment formulation. The results are also compared against the results of a discrete-time approximation technique to show the efficiency of the proposed GA approach.     

Process industry scheduling optimization using genetic algorithm and mathematical programming

This article addresses the problem of scheduling in oil refineries. The problem consists of a multi-product plant scheduling, with two serial machine stages—a mixer and a set of tanks—which have resource constraints and operate on a continuous flow basis. Two models were developed: the first using mixed-integer linear programming (MILP) and the second using genetic algorithms (GA). Their main objective was to meet the whole forecast demand, observing the operating constraints of the refinery and minimizing the number of operational changes. A real-life data-set related to the production of fuel oil and asphalt in a large refinery was used. The MILP and GA models proved to be good solutions for both primary objectives, but the GA model resulted in a smaller number of operational changes. The reason for this is that GA incorporates a multi-criteria approach, which is capable of adaptively updating the weights of the objective throughout the evolutionary process.     

Gene selection using hybrid particle swarm optimization and genetic algorithm

Selecting high discriminative genes from gene expression data has become an important research. Not only can this improve the performance of cancer classification, but it can also cut down the cost of medical diagnoses when a large number of noisy, redundant genes are filtered. In this paper, a hybrid Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) method is used for gene selection, and Support Vector Machine (SVM) is adopted as the classifier. The proposed approach is tested on three benchmark gene expression datasets: Leukemia, Colon and breast cancer data. Experimental results show that the proposed method can reduce the dimensionality of the dataset, and confirm the most informative gene subset and improve classification accuracy.     

Structural topology optimization using a genetic algorithm with a morphological geometric representation scheme

This paper describes a versatile methodology for solving topology design optimization problems using a genetic algorithm (GA). The key to its effectiveness is a geometric representation scheme that works by specifying a skeleton which defines the underlying topology/connectivity of a structural continuum together with segments of material surrounding the skeleton. The required design variables are encoded in a chromosome which is in the form of a directed graph that embodies this underlying topology so that appropriate crossover and mutation operators can be devised to recombine and help preserve any desirable geometry characteristics of the design through succeeding generations in the evolutionary process. The overall methodology is first tested by solving ‘target matching’ problems—simulated topology optimization problems in each of which a ‘target’ geometry is first created and predefined as the optimum solution, and the objective of the optimization problem is to evolve design solutions to converge towards this target shape. The methodology is then applied to design two path-generating compliant mechanisms—large-displacement flexural structures that undergo some desired displacement paths at some point when given a straight line input displacement at some other point—by an actual process of topology/shape optimization.     

基于DSM的复杂产品开发流程优化遗传算法

为减少产品开发过程中的返工迭代,提出一种基于设计结构矩阵(DSM)理论的多目标流程优化遗传算法.通过优化任务执行顺序,减少产品开发过程中的返工以压缩进度和降低成本.该优化算法是一种改进的遗传(GA)算法,在适应度函数中考虑了时间和费用两个指标;在选择、交叉、变异算子中采用了优解保持策略.仿真结果表明,对于高任务耦合度的产品开发项目,该优化算法能使开发时间压缩30%～40%,费用降低7%～2O%.