基于蜂群遗传算法的一维优化下料问题

针对一维下料优化问题,提出了基于蜂群遗传算法的优化求解方案.具体做法是,以实数表示的各零件长度的一个排列作为一个染色体,其中每个零件的长度作为基因;根据自然界蜂群生物学原理设置了两个种群,一个种群主要用于全局搜索,另一个种群主要用于局部搜索;采用最优个体交叉策略;遗传算子包括联赛选择算子,顺序交叉算子,2-交换变异算子和抑制算子.仿真实验结果表明,该算法逼近理论最优值,而且收敛速度快,较好地解决了一维下料问题.     

遗传算法在无重复规格一维下料优化中的应用

在对无重复规格一维下料优化问题数学模型分析的基础上,提出了基于改进遗传算法的优化下料方案求解方法.具体做法是,以实数表示的各零件长度的一个排列作为一个染色体,对一个可能解进行编码,其中的每个零件长度为一个基因;同时,为了便于遗传算子的设计,对染色体的基因进行分段,同一段上的基因表示它们截自同一原材料;通过基于基因分段的杂交、变异获得优化解.实验结果表明该算法是解决无重复规格一维下料问题的可行算法.     

基于改进遗传算法的机器人路径规划

文中提出一种基于改进遗传算法的移动机器人路径规划方法,将复杂的二维编码问题简化为一维编码问题,优化改进标准遗传算法的选择算子和交叉算子,引入路径规划特定的遗传算子(修正算子),最后以移动机器人行走路径最短作为适应度函数进行遗传优化.此算法克服了标准遗传算法的早熟收敛、运算结果稳定性差等问题,提高遗传算法的进化效率.仿真实验结果验证了该算法在移动机器人路径规划中的可行性和有效性,以及规划结果的稳健性.     

求解TSP的启发式顺序交叉算子

旅行商问题是经典的NP难组合优化问题之一.在用遗传算法求解旅行商问题时,顺序交叉算子是一种较为常用的遗传交叉算子.使用顺序交叉算子时的交叉点位置是随机指定的,不能反映关键遗传信息,导致算法执行效率较低.在顺序交叉算子的基础上,提出了一种启发式顺序交叉算子.该算子结合顺序交叉算子和启发式算法以得到双亲中交叉点位置,保留了双亲中关键的城市顺序信息.该算子改善了使用顺序交叉算子执行效率低的问题.实验结果表明了该算子的有效性.     

铁路输送中平车装载问题的模型与算法

分析了铁路运输中的平车装载问题，借鉴了First Fit算法的思想，并引入条件变异算子，提出了求解平车装载问题的一种改进遗传算法，给出了该改进遗传算法编码方法、遗传算子改进方案和适应度函数的定义，该算法能有效地解决初始群体和进化过程中的无效染色体和早熟问题，并用实例验证了该算法的有效性。     

圆片下料并行遗传算法的设计与实现

针对制造行业中的圆片下料问题,为了在合理的计算时间内使材料的利用率尽可能高,提出并行遗传下料算法（PGBA）,以下料方案的材料利用率作为优化目标函数,将下料方案作为个体,采用多线程的方式对多个子种群并行进行遗传操作。首先,在并行遗传算法的基础上设计特定的个体编码方式,采用启发式方法生成种群的个体,以提高算法的搜索能力和效率,避免早熟现象的发生;然后,采用性能较好的遗传算子进行自适应的遗传操作,搜索出一种近似最优的下料方案;最后,通过多种实验验证算法的有效性。结果表明,与启发式算法相比,PGBA的计算时间有所增加,但材料利用率得到了较大的提高,能有效提高企业的经济效益。     

软件开发项目中任务调度的混沌遗传算法

考虑了软件开发任务的可拆分特性，针对其调度问题提出了最小化项目总周期的优化模型，并提出了一种混沌遗传算法用于求解该模型,该算法的变异算子采用一维Logistic映射作为混沌变异模型，利用混沌系统的漂移特性改善种群的多样性,给出了算法基于任务优先级的编码方案、任务单元解码规则以及遗传算子的设计方法．通过仿真实例验证了模型和算法的有效性．     

基于三链混合遗传算法的贴片机贴装过程优化

为提高贴片机的生产效率,对贴片机贴装过程中的元器件拾取贴放顺序进行优化,提出了一种改进的三链混 合遗传算法。该算法将传统遗传算法中的两条链增加为三条链,并采用了启发式改进遗传算子。实验结果表明,改进的三链 混合遗传算法能够减少种群数目,提高优化效率和优化效果,从而提高算法的全局搜索能力。该算法在多数情况下能够搜索 到优于传统遗传算法的解。     

遗传算子的分析

阐述了遗传算法的特点,分析了遗传算法中选择算子、交叉算子和变异算子的特性,讨论了不同遗传算子对算法最优结果的获得所起的作用,提出了改善算法性能的措施,并设计了切实可行的选择算子、交叉算子和变异算子。模拟结果表明,遗传算法能在较短的时间内提供优化解,为解决复杂的优化问题提供了可行方案。     

一种用于矩形排样优化的改进遗传算法

矩形排样优化属于NPC问题,在工业界有着广泛的应用,如布料切割、金属下料和新闻组版等。提出了一种基于环形交叉算子和环形变异算子的自适应遗传算法,并将改进的自适应遗传算法和IBL启发式布局算法相结合,有效地解决了矩形排样优化问题。对比实验结果表明,环形交叉算子和环形变异算子对遗传算法是有效的,所提出的改进混合自适应遗传算法能够在一个较短的时间内找到满意解。     

一维下料问题的AB分类法

为了解决大规模的一维下料问题的计算困难, 根据一维下料问题的特点,把贪心算法和随机搜索技术有机地结合起来,利用随机搜索技术对贪心算法进行了有效的改进,提出了一种简单实用的AB分类法。 实验表明,该算法对规模较大的问题也能较快地获得问题最优解或精度较高的近似最优解。     

基于两阶段的分段单一矩形优化排样

为有效解决分段单一矩形优化排样问题,给出一个求解分段单一矩形优化排样问题的两阶段方法。第一阶段完成标准子段最佳排样方式求解,并将二维排样问题转化为一维下料问题,第二阶段使用适合于一维下料问题求解的算法完成板材最佳排样方式求解。使用该方法开发了一个单一矩形优化排样系统,该系统既可以解决分段单一矩形排样问题也可以解决其他类型的单一矩形优化排样问题。企业应用实例表明该方法是求解分段单一矩形优化排样问题的一个较为有效的方法。     

基于灾变遗传算法的数控冲床加工路径的优化

该文以数控冲床编辑与监控系统项目为背景,对数控冲床加工路径优化问题进行讨论。首先分析了数控冲床路径优化的基本原理,把加工路径优化抽象为TSP问题。然后采用效率较高的遗传算法对TSP问题进行求解,论述了遗传算法的具体实现。接下来为了解决遗传算法的容易陷入局部最优解的问题,加入了灾变算子来杀死当前的优质个体,使远离当前最优解的个体有充分的进化空间,从而使其跳出局部最优而更接近全局最优。最后对遗传算法和加入遗传算子的灾变遗传算法进行了比较分析,得出了灾变遗传算法在数控加工领域的更有优势的结论。     

A new evolutionary approach to cutting stock problems with and without contiguity

Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs.Scope and purposeThe one-dimensional cutting stock problem (CSP) is one of the classical combinatorial optimization problems. While most previous work only considered minimizing trim loss, this paper considers CSPs with two objectives. One is the minimization of trim loss (i.e., wastage). The other is the minimization of the number of stocks with wastage, or the number of partially finished items (pattern sequencing or contiguity problem). Although some traditional OR techniques (e.g., programming based approaches) can find the global optimum for small CSPs, they are impractical to find the exact global optimum for large problems due to combinatorial explosion. Heuristic techniques (such as various hill-climbing algorithms) need to be used for large CSPs. One of the heuristic algorithms which have been applied to CSPs recently with success is the genetic algorithm (GA). This paper proposes a much simpler evolutionary algorithm than the GA, based on evolutionary programming (EP). The EP algorithm has been shown to perform significantly better than the GA for most benchmark problems we used and to be comparable to the GA for other problems.     

A combined approach to the solution to the general one-dimensional cutting stock problem

In this article a combined method for the solution to the general one-dimensional cutting stock problem (G1D-CSP) is proposed. The main characteristic of G1D-CSP lies in that all stock lengths can be different. The new approach combines two existing methods: sequential heuristic procedure (SHP) and branch-and-bound. The algorithm based on the proposed method leads to almost optimal solutions, which are substantially better than the solutions of known methods at the expense of slightly increased time complexity, which is still low. So, the new method is suitable for all sizes of the problem. A comparison with the SHP is presented.     

基于蜂群遗传算法的0-1背包问题

针对0-1背包问题,本文提出了基于蜂群遗传算法的优化求解方案。该算法包括两个种群,一个主要用于全局搜索,另一个主要用于局部搜索;每个个体采用二进制编码;采用最优个体交叉策略;对当前解的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止;不符合约束条件的解采用诱变因子指导变异处理;遗传算子包括单点交叉算子、简单变异算子、主动进化算子和抑制算子。本算法充分发挥了遗传算法的群体搜索和全局收敛的特性,快速地并行搜索,有效地克服了经典遗传算法容易陷入局部最优问题。数值实验表明,该算法在求解0-1背包问题中取得了较好的效果,同样可以应用于其它的组合优化问题。     

An integrated algorithm for cutting stock problems in the thin-film transistor liquid crystal display industry

The cutting stock problem (CSP) is a critical issue in the manufacturing of thin film transistor liquid crystal display (TFT-LCD) products. Two manufacturing processes are utilized in this industry: (1) various TFT-LCD plates are cut from a glass substrate based on cutting patterns, and (2) the number of glass substrates required to satisfy customer requirements is minimized. The current algorithm used to select the cutting pattern is defined as a mixed integer program (MIP). Although the current MIP method yields an optimal solution, but the computation time is unacceptable when the problem scale is large. To accelerate the computation and improve the current method, this study proposes an integrated algorithm that incorporates a genetic algorithm, a corner arrangement method, and a production plan model to solve CSPs in the TFT-LCD industry. The results of numerical experiments demonstrate that the proposed algorithm is significantly more efficient than the current method, especially when applied to large-scale problems.     

改进PSO算法在二维下料问题中的研究

粒子群优化（PSO）算法是一种基于集群智能的进化计算方法,在该方法中粒子通过追随自己找到的最优解和种群最优解完成优化。文章将PSO算法应用到三角形优化下料问题的研究中,给出了具体的实施流程,为了提高PSO算法的收敛精度,避免早熟现象的产生,对PSO进行了改进,提出一种启发式PSO算法。通过对三角形的优化下料进行仿真,仿真结果显示改进后的启发式粒子群优化算法在收敛效果和材料的利用率方面均有显著的提高。     

An Innovative Genetic Algorithm for a Multi-Objective Optimization of Two-Dimensional Cutting-Stock Problem

This paper addressed an important variant of two-dimensional cutting stock problem. The objective was not only to minimize trim loss, as in traditional cutting stock problems, but rather to minimize the number of machine setups. This additional objective is crucial for the life of the machines and affects both the time and the cost of cutting operations. Since cutting stock problems are well known to be NP-hard, we proposed an approximate method to solve this problem in a reasonable time. This approach differs from the previous works by generating a front with many interesting solutions. By this way, the decision maker or production manager can choose the best one from the set based on other additional constraints. This approach combined a genetic algorithm with a linear programming model to estimate the optimal Pareto front of these two objectives. The effectiveness of this approach was evaluated through a set of instances collected from the literature. The experimental results for different-size problems show that this algorithm provides Pareto fronts very near to the optimal ones.     

基于局部搜索和遗传算法的激光切割路径优化

为了缩短激光加工时间,提高加工效率,提出了一种新的局部搜索法与遗传算法相结合的激光切割路径优化算法。该算法从加工轮廓中提取节点,通过局部搜索法对节点进行局部路径优化,再运用的遗传算法求得近似最优解,遗传算法中的选择算子改进为基于相对适应度的轮盘赌选择算子。详细介绍了算法的原理及实现,通过编程仿真证明该算法与传统的遗传算法相比具有良好的优化效果,可明显缩短加工路径,减少加工时间,提高加工效率。