基于改进遗传算法的多机调度问题

遗传算法是解决多机调度组合优化问题最有效的方法之一,但由于其自身存在着一定的缺陷应用受到一定的限制.针对遗传算法的“早熟”和非均匀地在优化空间中搜索等缺陷,提出了一种自适应选择交叉概率、变异概率以及交叉位置非等概率选取的改进的遗传算法,并将其用于某钢管钢绳企业的多机调度问题,进行了仿真分析.     

一种改进的自适应遗传算法

针对IAGA自适应遗传算法存在的未成熟收敛问题,提出了一种改进的自适应遗传算法(NIAGA算法),根据自定义判别式判断群体是否出现了未成熟收敛趋势,由不同情况,分别采用宏观调控与微观处理两种方法来设置交叉概率Pc和变异概率Pm,以此促使算法摆脱未成熟收敛.仿真结果表明,新算法有效地改善了IAGA算法的未成熟收敛问题,显示出了更强的全局收敛性.     

用改进的遗传算法求解危险货物零担运输多目标配装问题

危险货物零担运输配装问题是铁路部门复杂而急需解决的实际问题.给出了多目标的数学规划模型,先对待装货物进行预处理,然后运用自适应的遗传算法对问题进行了求解,该算法中自适应杂交变异概率的应用提高了收敛速度.最后通过实例证明了该方法的可行性和有效性.     

二维恒定各向同性介质渗透系数反演的遗传算法

给出了利用遗传算法求解二维恒定各项同性介质渗透系数反演的一种新方法,该方法把参数反演问题转化为优化问题通过遗传算法求解.数值模拟结果表明:该方法具有精度高、收敛速度快、编程简单、易于计算机实现等优点,值得在实际工作采用.     

粒子群遗传混合算法求解考虑传输时间的FJSP

在某些生产制造场景中,工件在不同机器间的传输时间对车间调度的总拖期具有重要影响,本文基于此扩展了总拖期最小的柔性作业车间调度模型。针对问题模型的复杂性,采用粒子群优化算法和遗传算法的混合算法进行求解。在初始化过程以一定概率优选加工时间和传输时间短的机器并排除调度频繁的机器,使种群在保持多样性的前提下尽量选择优化结果好的个体;采用线性调整的方式动态改变交叉概率和变异概率的值,使种群在遗传算法的不同阶段具有不同的搜索强度;采用粒子群优化算法进行局部搜索,弥补了遗传算法局部搜索能力的不足。最后采用本文方法和其他方法求解柔性作业车间调度问题实例,并对比不同水平层次传输时间下的总拖期,验证了本文方法的有效性。     

概率因果模型结合改进遗传算法的核动力系统故障分析

将概率因果模型的似然函数作为遗传算法的适应函数,从而将复杂系统的故障诊断转化为最优问题,建立了一种将概率因果模型和遗传算法相结合的故障诊断方法,并利用改进算法与概率因果故障诊断模型对船用核动力装置进行故障诊断实例分析,分析结果对船用核动力装置故障诊断具有重要的指导意义,而改进遗传算法是进行船用核动力装置故障诊断有效而实用的方法。     

一种改进遗传算法在最大独立子集问题中的应用

最大独立子集问题是组合优化问题中的一个重要问题,该问题是一个NP难题,其目标是在一个环图中找到一个最大的独立子集.提出了一种改进的遗传算法来解决这个问题,用一种基于条件的遗传算子来代替通常的基于概率的遗传算子.实验结果表明提出的算法是有效的.     

基于存档策略的多目标优化的遗传算法及其收敛性分析

设计了一种用遗传算法求解多目标优化问题的有效方法——基于存档策略的多目标优化的遗传算法,并讨论了此算法的收敛性.首先给出档案的定义,设计出基于支配关系下的带有存档策略遗传算法,并通过算例检验了算法的有效性;然后引入了两档案间的距离的概念,在此距离定义的基础上证明了算法在概率意义下是收敛的.     

遗传算子的代数形式和概率特征

采用矩阵形式表示遗传操作过程 ,可为设计遗传算法程序提供简单的数学模型 .遗传操作的概率特征 ,揭示了遗传算子各自在遗传优化过程中的作用及相互关系 .     

油田注水系统拓扑布局优化的混合遗传算法

以投资最小为目标函数,建立了注水系统拓扑布局优化数学模型.根据模型特点,将优化问题分为两层,分别采用遗传算法和非线性优化方法进行求解.并对遗传算法的操作过程进行了改进,调整了适应函数,改进了交叉和变异操作,结合了模拟退火算法,在操作过程中使约束条件得到满足,减少了不可行解的产生,使遗传算法的优化性能得到了提高.优化算例说明了该方法的有效性.     

Heuristic approach on dynamic lot-sizing model for durable products with end-of-use constraints

A version of the dynamic lot-sizing (DLS) problem involving durable products with end-of-use constraints is analyzed in this paper. First, we mathematically formulate this problem, then certain properties are derived to construct the structure of the optimal solution. Next, based on these properties, a recursive optimization algorithm is proposed for a single-item problem. Moreover, an approximate algorithm is designed on the basis of the optimization algorithm, with linear computational complexity. A heuristic approach is proposed for solving the two-item DLS problem. The difficulty in solving this problem lies in its decomposition into item-level subproblems while ensuring the feasibility of the solution. The proposed technique aims to resolve this issue by combining the capabilities of Lagrangian relaxation to decompose the problem into smaller subproblems, and a genetic algorithm (GA) is used to update the Lagrangian multipliers. Further, the computational results obtained using the proposed approach are enumerated to demonstrate its effectiveness. Finally, the conclusion and remarks are given to discuss the possible future works.     

Solving sum of quadratic ratios fractional programs via monotonic function

In this paper, a branch-reduce-bound algorithm is proposed for globally solving a sum of quadratic ratios fractional programming with nonconvex quadratic constraints. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. The proposed algorithm is based on reformulating the problem as a monotonic optimization problem, and it turns out that the optimal solution which is provided by the algorithm is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiments are given to show the feasibility of the proposed algorithm.     

Global optimization for the generalized polynomial sum of ratios problem

In this paper, a new deterministic global optimization algorithm is proposed for solving a fractional programming problem whose objective and constraint functions are all defined as the sum of generalized polynomial ratios, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. The proposed algorithm is based on reformulating the problem as a monotonic optimization problem, and it turns out that the optimal solution which is provided by the algorithm is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and numerical examples are given to illustrate the feasibility and efficiency of the present algorithm.     

带投资约束且p不确定的推广p-中位问题

p-中位问题是设施选址中的一个经典模型,在交通、物流等领域有着广泛应用．在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题,并且加上总投资约束,使得此推广模型更加实用．针对此推广模型,提出三种启发式算法：简单启发式算法、变邻域搜索算法和改进的遗传算法．数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的．     

Sequencing by hybridization: an enhanced crossover operator for a hybrid genetic algorithm

This paper presents a genetic algorithm for an important computational biology problem. The problem appears in the computational part of a new proposal for DNA sequencing denominated sequencing by hybridization. The general usage of this method for real sequencing purposes depends mainly on the development of good algorithmic procedures for solving its computational phase. The proposed genetic algorithm is a modified version of a previously proposed hybrid genetic algorithm for the same problem. It is compared with two well suited meta-heuristic approaches reported in the literature: the hybrid genetic algorithm, which is the origin of our proposed variant, and a tabu-scatter search algorithm. Experimental results carried out on real DNA data show the advantages of using the proposed algorithm. Furthermore, statistical tests confirm the superiority of the proposed variant over the state-of-the-art heuristics.     

A general algorithm for solving Generalized Geometric Programming with nonpositive degree of difficulty

In this paper, a general algorithm for solving Generalized Geometric Programming with nonpositive degree of difficulty is proposed. It shows that under certain assumptions the primal problem can be transformed and decomposed into several subproblems which are easy to solve, and furthermore we verify that through solving these subproblems we can obtain the optimal value and solutions of the primal problem which are global solutions. At last, some examples are given to vindicate our conclusions.     

DISCRETE SINGULAR CONVOLUTION METHOD WITH PERFECTLY MATCHED ABSORBING LAYERS FOR THE WAVE SCATTERING BY PERIODIC STRUCTURES

A new computational algorithm is introduced for solving scattering problem in periodic structure. The PML technique is used to deal with the difficulty on truncating the unbounded domain while the DSC algorithm is utilized for the spatial discretization. The present study reveals that the method is efficient for solving the problem.     

Using genetic algorithm to solve dynamic cell formation problem

In this paper, solving a cell formation (CF) problem in dynamic condition is going to be discussed using genetic algorithm (GA). Previous models presented in the literature contain some essential errors which will decline their advantageous aspects. In this paper these errors are discussed and a new improved formulation for dynamic cell formation (DCF) problem is presented. Due to the fact that CF is a NP-hard problem, solving the model using classical optimization methods needs a long computational time. Therefore the improved DCF model is solved using a proposed GA and the results are compared with the optimal solution and the efficiency of the proposed algorithm is discussed and verified.     

A global optimization using linear relaxation for generalized geometric programming

Many local optimal solution methods have been developed for solving generalized geometric programming (GGP). But up to now, less work has been devoted to solving global optimization of (GGP) problem due to the inherent difficulty. This paper considers the global minimum of (GGP) problems. By utilizing an exponential variable transformation and the inherent property of the exponential function and some other techniques the initial nonlinear and nonconvex (GGP) problem is reduced to a sequence of linear programming problems. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (GGP) on a microcomputer.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.