多目标遗传算法及在过程优化综合中的应用

化工过程的多目标优化综合问题可归结为多目标混合整数非线性规划(MOMINLP)模型的求解,求解方法主要有数学规划法和多目标进化算法。以多目标遗传算法(MOGA)为代表的进化算法被认为是特别适合求解此类问题。遗传算法大多用于单目标问题的优化,近十几年来将遗传算法应用到多目标优化的研究得到了很大的发展。本文对多目标遗传算法的一些重要概念、发展历程进行了回顾。针对化工过程的模型特点,对MOGA在过程综合中的应用研究进行了讨论,并认为混合遗传算法应是求解此类问题的有效算法。     

一类整数性目标规划的遗传算法

本文给出了以惩罚函数法将约束优化问题转化为无约束优化问题的通用算法,提出了将遗传算法和惩罚函数法相结合用于求解整数性目标规划问题的具体方法。计算机数值仿真结果表明了该方法的有效性。     

一类带延迟策略的库存优化模型及其仿真

考虑一类带延迟策略的库存优化模型, 即二层整数规划问题。证明了该二层整数规划问题等价于约束单层整数规划问题。借助罚函数思想化约束整数规划问题为无约束整数规划问题, 再利用遗传算法进行求解。数值模拟表明所得数值结果与已有的数值结果相比,不仅使得供应链整体库存效益有较大提高, 并且对每个库存分点的最优库存量作了更为合理的调整。     

RCPSP中现金流优化问题的HGA方法

针对网络进度计划中财务方面对项目管理的影响 ,研究资源受限项目调度问题 (RCPSP)中网络现金流的优化问题。提出以网络净现值最大作为网络现金流优化的目标 ,建立了带有贴现率的非线性整数规划模型 ,采用遗传算法与模拟退火算法相结合的混合式遗传算法进行求解。仿真实例表明了方法的合理性和有效性。     

基于遗传算法的机场滑行调度优化策略

提出一种基于遗传算法的滑行调度优化策略。该策略首先用遗传算法确定各航班经过交叉点的顺序,再根据上一步得到的顺序求解具体的调度计划,并反复迭代以逐渐优化,直到得到最优解或满意解。相对于混合整数线性规划（MILP）模型而言,有效地提高了求解效率,减少了求解时间。     

求解0-1整数规划问题的混沌遗传算法*

针对一类特殊的0-1整数规划求解问题提出一种混沌遗传算法。该算法采用幂函数载波技术提高混沌搜索的充分性与遍历性,以混沌搜索算法得出的优化个体作为遗传算法的新群体进行交叉、变异等操作,提高种群质量,同时增加种群多样性,改善遗传算法的早熟问题。该算法被用于解决片上网络映射A3MAP(architecture-aware analytic mapping) 0-1整数规划问题。实验仿真证明,该算法的收敛速度和解的精度均优于A3MAP-GA。     

集装箱码头装卸桥调度优化模型与算法

研究装卸桥调度优化问题,以提高集装箱码头装卸效率。首先,建立了混合整数规划模型,模型充分考虑了集装箱装卸桥调度优化中的各种约束条件及特点。为了求解设计了基于遗传算法的求解方法,并且采用随机贪婪适应性搜索方法对算法进行改进。最后,通过实际算例对模型与算法的有效性进行了验证。     

个性化食谱智能优化系统

为提高食谱设计质量与效率,提出一种基于交互式进化计算的食谱智能优化方法.根据用户评价值和食谱菜品优化模型确定食谱样本隐式指标与显式指标;基于NSGA-Ⅱ算法获得食谱样本Pareto优化解.为使Pareto优化解更好兼顾用户偏好与营养均衡,引入指标均衡度指导进化.当指标均衡度较低时,采用遗传算法模块对显式指标单独进化,提高指标均衡性.用遗传算法最优解替换原优化结果中指标均衡度最低个体,改造Pareto前沿.以传统交互式遗传算法和食物交换法为对比方法,验证了该方法在个性化适应性、有效性和可用性等3个方面均优于对比方法.该方法为个性化食谱设计提供了一种智能化新思路.     

基于分布估计算法的单路口交通信号控制

针对遗传算法求解城市道路交叉口信号控制存在的主要问题,以四相位交叉路口为研究对象,建立了以信号周期内车辆延误总时间最短为目标函数,以各相位有效绿灯时间为控制变量的单路口交通信号优化模型.并分别以整数编码的PBIL算法和实数编码的EMNA算法两种典型分布估计算法求解单路口交通信号优化问题.仿真结果表明,与传统遗传算法相比,两种分布估计算法均可用更小的种群规模快速高效地求得最优解.     

基于微粒群算法的QoS组播路由算法

文章研究了带宽、延时、延时抖动约束最小代价的QoS组播路由问题,提出了一种基于微粒群优化(PSO)算法[2,5]来设计路由优化算法。该算法采用一种新的整数编码方案,将路由优化问题转化成准连续优化问题,并采用罚函数处理约束条件。给出了应用微粒群优化算法求解QoS组播路由问题的算例,并与遗传算法和改进后的遗传算法进行了比较。计算机仿真实验证明,该算法可以更有效地求得QoS组播路由问题的优化解,可靠性高。     

线性整数规划的分支限界解法及其MATLAB实现

讨论了计算机算法中分支限界法对于线性整数规划问题的解决思想,通过MATLAB中提供的优化函数,实现了快速解决线性整数规划的问题,同时改进了对于此类问题的计算量巨大和编制程序困难的问题,使用了堆栈而不是递归,节约了计算中的资源.编制的MATLAB线性整数规划的程序,可以编译成C/C 实现和COM组件.     

基于单纯形法和局部枚举解混合整数线性规划问题

提出了一种基于单纯形法和局部枚举求解整数线性规划问题的新方法。它通过单纯形法得到松弛问题的最优解并确定变量以及目标函数取值范围,然后基于目标函数,进行局部枚举,从而得到其整数线性规划问题的最优解,与现有方法比较,新解法简单,计算量少,尤其是对于大规模整数线性规划问题,计算量少体现地更明显。     

An Isometric Surface Method For Integer Linear Programming * *Supported by the R&D base on advanced manufacturing technology,Academia Sinica

Based on the isometric plane method for linear programming, an algorithm for integer linear programming is proposed in this paper. The algorithm can quickly obtain the optimal integer point simultaneously using isometric planes and cutting planes derived from polyhedral-cones, rounded-minimal-balls and second-rounded-balls at the highest vertex and its neighboring vertices.     

A parametric analysis of linear integer programming problems

Parametric programming may be utilized to obtain restrictions to linear programming relaxations to linear integer programming problems. The purpose of such approaches is to reduce the size of the subproblems that appear subsequent to solving the relaxed linear programming problem. The optimal dual variables to the linear programming problem provide information regarding the difference between the continuous linear programming optimal objective function value and that of the integer linear programming objective function value.     

A note on “event-based MILP models for resource-constrained project scheduling problems”

Recently, new mixed integer linear programming formulations for the resource-constrained project scheduling problem were proposed by Koné et al. [3]. Unfortunately, the presentation of the first new model (called start/end-based formulation SEE) was not correct. More precisely, a set of necessary constraints representing the relative positioning of start and end events of activities was unintentionally omitted in the paper although it was present in the integer program used for the computational experiments. After presenting a counterexample showing the incorrectness, we provide a disaggregated and an aggregated variant of the set of necessary constraints, the disaggregated formulation yielding in theory a better linear programming relaxation. We present computational results showing that although the linear programming relaxations of both formulations yield equivalently poor lower bounds, the disaggregated formulation shows in average a better performance for integer solving of a well-known set of 30-activity instances.     

考虑库区吊机能力的板坯倒垛问题的建模与优化方法研究

研究了钢铁企业板坯库的板坯倒垛(Slab stack shuffling, SSS)问题. 与以往研究倒垛问题不同, 考虑了板坯存储各库区吊机能力的实际限制. 对该问题通过考虑实际约束, 以总倒垛次数最小为目标函数建立了非线性整数规划模型. 基于对问题特征的分析, 分别针对轧制项目间是否存在共同可选板坯的两种情况, 将模型变换为线性整数规划模型. 另外, 利用提出的问题性质, 降低了模型的求解复杂性. 实验结果表明, 对于实际的问题规模, 基于该线性整数规划模型的优化方法能有效地求得问题的最优解.     

MATLAB程序设计在化学计量学中的应用

MATLAB是美国MathWorks公司自80年代中期推出的适用于科学和工程计算的数学软件。它优秀的数值计算能力、卓越的数据可视化能力和简洁的程序语言编写使其很快在数学软件中脱颖而出。本文通过化学计量学中的两个多元校正为例，简要介绍了MATLAB程序设计在化学计量学计算中的应用。     

An Integer Linear Programming Problem with Multi-Criteria and Multi-Constraint Levels: a Branch-and-Partition Algorithm

In this paper, we propose a branch-and-partition algorithm to solve the integer linear programming problem with multi-criteria and multi-constraint levels (MC-ILP). The procedure begins with the relaxation problem that is formed by ignoring the integer restrictions. In this branch-and-partition procedure, an MC linear programming problem is adopted by adding a restriction according to a basic decision variable that is not integer. Then the MC-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the constraint parameter for a regular MC linear programming problem. We use parameter partition to divide the (λ, γ) space for integer solutions of MC problem. The branch-and-partition procedure terminates when every potential basis for the relaxation problem is a potential basis for the MC-ILP problem. A numerical example is used to demonstrate the proposed algorithm in solving the MC-ILP problems. The comparison study and discussion on the applicability of the proposed method are also provided.     

Computer-based algorithms for multiple criteria and multiple constraint level integer linear programming

This paper investigates algorithm development and implementation for multicriteria and multiconstraint level (MC²) integer linear programming problems. MC² linear programming is an extension of linear programming (LP) and multiple criteria (MC) linear programming and a promising computer-aided decision technique in many applications. Here, we present two of the most recent techniques, the MC² branch-and-partition algorithm and the MC² branch-and-bound algorithm, to solve MC² integer linear programs. We describe the design and implementation of a C++ software library for these approaches, and then conduct a comparison study in terms of computational efficiency and complexity through a series of empirical tests.     

Exact procedures for solving the discrete ordered median problem

The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U, editors. Operations Research Proceedings 2000, Berlin: Springer, 2001. p. 71–76), who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems.