基于混合遗传算法的订单生产调度在机车车辆行业中的应用

机车车辆行业作为典型的面向订单的机械制造企业,优化的生产调度方法能提高订单的准时交货,缩短产品的生产周期,提高企业的市场竞争力。订单生产调度问题是典型的NP-hard问题。遗传算法(Genetic Algorithms)为求具有多个约束的复杂问题提供了有效的方法。但是遗传算法的局部搜索能力比较差,在解决订单生产调度问题中存在着明显的不足。本文引入了局部搜索能力很强的禁忌搜索算法,用遗传算法和禁忌搜索算法相结合的混合遗传算法来解决机车车辆行业中面向订单生产调度问题。     

启发式遗传算法求解两两组合测试用例集

针对两两组合测试用例集的生成问题,在有效地结合了两两组合测试问题本身的特点基础上,提出了一种基于动态解空间的启发式遗传算法(HGA)。详细分析了测试用例生成过程,根据其解空间的动态变化在传统遗传算法中加入了启发算子,使得HGA算法可以快速地搜索出当前局部优化的测试用例。实验结果表明,HGA算法在完全覆盖参数两两组合的前提下有效地减少了测试用例的数量,并且具有较快的迭代速度。     

基于窗口的印刷车间作业动态调度研究

为了解决实际印刷车间突发设备故障和紧急插单问题,采用滚动窗口技术结合遗传算法的方法,建立适合实际印刷车间生产的动态再调度模型;设定若干印品订单、机器设备的加工工序以及各工序加工时间、工序约束条件等,以订单的最大最小加工时间和再调度的偏离度为多目标优化,采用周期与事件混合驱动策略,将滚动窗口再调度机制和遗传算法相结合进行流程设计和编码,构建印刷车间再调度模型;采用标准问题FT06和FT01验证了文章设计的模型算法的有效性和可行性;运行程序,模拟正常加工时紧急插单和机器故障突发时,系统生产新的调度计划即调度甘特图,仿真结果表明该动态调度模型可以用于印刷作业的正常排产调度,在遇突发状况时可生成稳定、符合交货日期的再调度方案。     

求解背包问题的贪心遗传算法及其应用

分析了文献[2]中求解背包问题(KP)的混合遗传算法(HGA)所采用的贪心变换方法缺陷;重新定义了贪心变换的概念,并给出了一种新的且更高效的贪心变换方法,将此方法与遗传算法相结合得到一种新的混合遗传算法,称之贪心遗传算法(简记GGA).利用GGA得出了文献[2,4]中一个著名KP问题实例的目前最好结果;同时,对于文献[7]中的KP问题实例和一个随机生成的KP问题实例,将GGA算法与求解KP问题的最有效算法HGA算法进行对比计算,结果表明GGA算法远远优于HGA算法.     

基于加速度信号和进化RBF神经网络的人体行为识别*

针对基于加速度信号的人体行为识别,采用递阶遗传算法(HGA)训练径向基函数(RBF)神经网络,获得满意的识别正确率.设计适应度函数,利用四分位数间距改进HGA中参数基因的交叉方式,给出自动确定子代生成区域的方法,省去以往同类算法中的经验性设定,并结合算术交叉选择优秀子代,然后对比均匀变异和非均匀变异子代的适应值,实现对RBF网络结构和参数的联合优化.在基于加速度信号的行为识别系统中,与基本HGA和其他常用的训练方法相比,文中算法训练的RBF分类器可获得更低的输出误差和更高的测试样本识别正确率.     

智能交通系统中的公交运营优化调度研究

城市公交系统是一个巨系统,其相关的模型和方法都非常复杂,为此,本文引入了高性能计算来提高智能算法的优化质量和收敛速度。有机结合遗传算法GA(Genetic Algorithm)和禁忌搜索法TS(Tabu Search)两者优点,构成混合遗传算法HGA(Hybrid Genetic Algorithm)。针对公交车辆调度现状及所处的运营环境,运用HGA的智能化特征,进行了公交车辆智能调度研究。研究表明,基于GA-TS的混合遗传算法优化公交车辆运营调度,能够有效地改善原有公交车辆运营调度的不足,提高动态运营决策效率和服务质量。     

基于改进型遗传算法的热轧生产计划调度系统

针对热轧型钢生产计划编制的约束条件复杂、易延误交货期、不易寻求最优解等问题,采用面向可拆分订单的批策略思想建立了新的生产计划模型,并针对新模型改进了遗传算法,提出了拆分染色体遗传算法.结合某钢铁企业实例,在建立基于批决策与批调度热轧数学模型、列举实际生产约束条件之后,阐明了此种新算法的应用过程,并且通过不同的订单数据进行模拟计算和结果比较,证明了该模型及算法得出的生产计划可节省生产时间、降低设备调度、减少交货延误,以此来指导热轧型钢的生产,可切实提高企业利润率.     

混合流水车间插单重调度的超启发式遗传算法

针对带有紧急订单的混合流水车间插单重调度问题,提出了一种双层编码的超启发式遗传算法。针对混合流水车间具有的订单排序和机器选择的双决策特征,在算法低层设计双层编码方案,在个体中表示订单排序和机器选择两类信息,对应一个唯一调度解,进而提出了12种排序和选择启发式对个体进行迭代优化;在算法高层采用自适应遗传算法,用来确定订单排序启发式和机器选择启发式的操作组合以及各组合执行的次序,并设计了自适应变异算子来优化算法的有效性。大规模数据实验的结果表明,所提算法具有很好的求解质量和求解效率。     

基于混合遗传算法的自动组卷问题的研究

针对遗传算法(GA)容易出现未成熟收敛和进化后期计算效率低的问题,提出了一种基于混合遗传算法(HGA)的智能组卷算法.将自适应遗传算法(AGA)与位爬山法相结合,提高组卷性能.在进化前期采用AGA进行全局寻优,增强GA的收敛速度同时避免GA的未成熟收敛.在进化后期启动位爬山法增强AGA的局部搜索能力.试验结果表明,HGA相对于AGA在有效性、稳定性和计算效率三方面都有较大提升,更能有效解决自动组卷问题,具有较好的使用性能和实用性.     

混合遗传算法及与标准遗传算法对比研究

文章详尽地阐述了1996年Pham和Jin提出的一种运用改进繁殖机制的遗传模型,称为混合遗传算法(HGA,HybridGeneticAlgorithm),并对HGA和GA(GeneticAlgorithm)的效能进行了对比性分析。理论与实验结果表明混合遗传算法收敛性明显快于标准遗传算法。     

A hybrid genetic algorithm that optimizes capacitated vehicle routing problems

This study primarily focuses on solving a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) capable of practical use for manufacturers. The proposed HGA has three stages. First, the nearest addition method (NAM) was incorporated into sweep algorithm (SA) that simultaneously accounts for axial and radius relationships among distribution points with the depot to generate a well-structured initial chromosome population, rather than adopting either the NAM OR SA alone. Second, response surface methodology (RSM) was employed to optimize crossover probability and mutation probability via systematic experiments. Finally, an improved sweep algorithm was incorporated into the GA, producing a stir over gene permutations in chromosomes that enhance the exploration diversity of the GA, thereby avoiding convergence in a limited region, and enhancing the search capability of the GA in approaching a close-to-optimal solution. Furthermore, an elitism conservation strategy holding superior chromosomes to replace inferior chromosomes was also performed. As the proposed HGA is primarily used to solve practical problem, benchmark problems with fewer than 100 distribution points from an Internet website were utilized to confirm the effectiveness of the proposed HGA. A real case regarding the mission of local active distribution from armed forces in Taiwan details the analytical process and demonstrates the practicability of the proposed HGA to optimize the CVRP.     

A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem

This paper considers the job-shop problem with release dates and due dates, with the objective of minimizing the total weighted tardiness. A genetic algorithm is combined with an iterated local search that uses a longest path approach on a disjunctive graph model. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. Previous studies on genetic algorithms for the job-shop problem point out that these algorithms are highly depended on the way the chromosomes are decoded. In this paper, we show that the efficiency of genetic algorithms does no longer depend on the schedule builder when an iterated local search is used. Computational experiments carried out on instances of the literature show the efficiency of the proposed algorithm.     

An effective evolutionary algorithm for the practical capacitated vehicle routing problems

The evolutionary algorithms are extensively adopted to resolve complex optimization problem. Genetic algorithm (GA), an evolutionary algorithm, has been proved capable of solving vehicle routing problems (VRPs). However, the resolution effectiveness of GA decreases with the increase of nodes within VRPs. Normally, a hybrid GA outperforms pure GA. This study attempts to solve a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) that is practical for use by manufacturers. The proposed HGA involves three stages. First, a diverse and well-structured initial chromosome population was constructed. Second, response surface methodology (RSM) experiments were conducted to optimize the crossover and mutation probabilities in performing GA. Finally, a combined heuristics containing improved insertion algorithm and random insertion mutation operator was established to stir over gene permutations and enhance the exploration capability of GA diversely. Furthermore, an elitism conservation strategy was implemented that replace inferior chromosomes with superior ones. As the proposed HGA is primarily used to solve practical problems, benchmark problems involving fewer than 100 nodes from an Internet website were utilized to confirm the feasibility of the proposed HGA. Two real cases one for locally active distribution and another for arms part transportation at a combined maintenance facility, both involving the Taiwanese armed forces are used to detail the analytical process and demonstrate the practicability of the proposed HGA for optimizing the CVRP.     

求解多维0—1背包问题的混合遗传算法

文章研究一类典型的组合优化问题——多维０－１背包问题,提出了在简单遗传算法（ＳＧＡ）中加入局部搜索机制的混合遗传算法（ＨＧＡ）来求解该类问题,并在大量数值实验的基础上,将ＨＧＡ与传统的求解方法及ＳＧＡ进行了比较,实验的结果表明,该算法具有一定的优越性。     

A hybrid approach using genetic and fruit fly optimization algorithms for QoS-aware cloud service composition

This paper addresses the QoS-aware cloud service composition problem, which is known as a NP-hard problem, and proposes a hybrid genetic algorithm (HGA) to solve it. The proposed algorithm combines two phases to perform the evolutionary process search, including genetic algorithm phase and fruit fly optimization phase. In genetic algorithm phase, a novel roulette wheel selection operator is proposed to enhance the efficiency and the exploration search. To reduce the computation time and to maintain a balance between the exploration and exploitation abilities of the proposed HGA, the fruit fly optimization phase is incorporated as a local search strategy. In order to speed-up the convergence of the proposed algorithm, the initial population of HGA is created on the basis of a heuristic local selection method, and the elitism strategy is applied in each generation to prevent the loss of the best solutions during the evolutionary process. The parameter settings of our HGA were tuned and calibrated using the taguchi method of design of experiment, and we suggested the optimal values of these parameters. The experimental results show that the proposed algorithm outperforms the simple genetic algorithm, simple fruit fly optimization algorithm, and another recently proposed algorithm (DGABC) in terms of optimality, computation time, convergence speed and feasibility rate.     

基于粒子群位移转移的混合遗传算法及其应用

基于粒子群位移转移的思想,改变遗传算法的变异规则,提出了一种新的混合遗传算法。利用3个benchmark函数测试了新的混合算法的性能,并将测试结果与标准遗传算法进行了比较。提出了一种多阶段半方差投资选择模型,并将混合算法应用在多阶段半方差投资选择问题的求解上。     

启发式遗传算法及其应用

1.引 言 在科学实践、工程技术和日常生活中,人们常常会遇到大量的、各式各样的最优化问题.最优化方法在近几十年里获得了巨大的发展,但目前很多方法不同程度上还存在着一些不足之处.尤其是最终所求得的大多为局部最优解,并不是全局最优解.而近年来得到蓬勃发展的遗传算法其本质是一种求解问题的高效并行全局搜索方法.它能在搜索过程中自动获取和     

Hybrid genetic algorithm approach for precedence-constrained sequencing problem

The objective of precedence-constrained sequencing problem (PCSP) is to locate the optimal sequence with the shortest traveling time among all feasible sequences. Various methods for effectively solving the PCSP have been suggested. This paper proposes a new concept of hybrid genetic algorithm (HGA) with adaptive local search scheme in order that the PCSP should be effectively solved. By the use of the adaptive local search scheme, the local search is automatically adapted into the loop of genetic algorithm. Two types of the PCSP are presented and analyzed to compare the efficiency among the proposed HGA approach and other competing conventional approaches. Finally, it is proved that the proposed HGA approach outperforms the other competing conventional approaches.     

A vehicle routing problem solved by using a hybrid genetic algorithm

The main purpose of this study is to find out the best solution of the vehicle routing problem simultaneously considering heterogeneous vehicles, double trips, and multiple depots by using a hybrid genetic algorithm. This study suggested a mathematical programming model with a new numerical formula which presents the amount of delivery and sub-tour elimination. This model gives an optimal solution by using OPL-STUDIO(ILOG CPLEX). This study also suggests a hybrid genetic algorithm (HGA) which considers the improvement of generation for an initial solution, three different heuristic processes, and a float mutation rate for escaping from the local solution in order to find the best solution. The suggested HGA is also compared with the results of a general genetic algorithm and existing problems suggested by Eilon and Fisher. We found better solutions rather than the existing genetic algorithms.     

Metaheuristics and exact methods to solve a multiobjective parallel machines scheduling problem

This paper deals with a multiobjective parallel machines scheduling problem. It consists in scheduling n independent jobs on m identical parallel machines. The job data such as processing times, release dates, due dates and sequence dependent setup times are considered. The goal is to optimize two different objectives: the makespan and the total tardiness. A mixed integer linear program is proposed to model the studied problem. As this problem is NP-hard in the strong sense, a metaheuristic method which is the second version of the non dominated sorting genetic algorithm (NSGA-II) is proposed to solve this problem. Since the parameters setting of a genetic algorithm is difficult, a fuzzy logic controller coupled with the NSGA-II (FLC-NSGA-II) is therefore proposed. The role of the fuzzy logic is to better set the crossover and the mutation probabilities in order to update the search ability. After that, an exact method based on the two phase method is also developed. We have used four measuring criteria to compare these methods. The experimental results show the advantages and the efficiency of FLC-NSGA-II.