多目标0-1规划问题的蜂群算法

针对多目标0-1规划问题,本文给出一种新型的智能优化算法——蜂群算法进行求解,并通过实例验证,与遗传算法、蚁群算法和元胞蚁群算法作了相应比较。就多目标0-1规划问题而言,蜂群算法能得到更多的Pareto解,说明了蜂群算法在解决该类问题上的有效性。     

0-1背包问题的蜂群优化算法

在项目决策与规划、资源分配、货物装载、预算控制等工作中,提出了0-1背包问题.0-1背包问题是组合优化中的典型NP难题,根据群集智能原理,给出一种基于蜂群寻优思想的新算法—蜂群算法,并针对0-1背包问题进行求解.经实验仿真并与蚁群算法计算结果作对比,验证了算法在0-1背包问题求解上的有效性和更快的收敛速度.     

非线性0-1规划问题的混沌粒子群算法

针对非线性0-1规划问题,提出了一种混沌粒子群优化算法.该算法利用罚函数法将非线性0-1规划问题处理为无约束的0-1规划问题,引入了混沌策略来初始化种群,增加其多样性,为预测算法是否出现早熟现象,采用了适应度方差.数值实验表明,提出的算法是求解非线性0-1规划问题的一种有效且可行的全局优化算法.     

多目标0-1规划的萤火虫算法

针对于多目标0-1规划问题,给出一种新型的智能优化算法-萤火虫优化算法对其进行求解,并在计算机上予以实现.经一系列算例测试,并与其它智能算法进行比较,算法能获得较多的非劣解,表明算法可行有效,可求解实际应用中的相应问题.     

基于人工蜂群算法的非线性系统模型参数估计

将人工蜂群算法用于非线性系统模型的参数估计,通过对谷氨酸菌体生长模型的参数估计进行验证,并与人工神经网络、遗传算法和微粒群算法的优化结果进行了比较.仿真试验结果表明:人工蜂群算法对非线性系统模型的参数估计精度高于人工神经网络、遗传算法和微粒群算法的参数估计精度,为非线性系统模型参数估计提供了一种有效的途径.     

元胞人工蜂群算法及其在0-1规划问题中的应用

针对人工蜂群算法早熟收敛问题,基于元胞自动机原理和人工蜂群算法,提出一种元胞人工蜂群算法.该算法将元胞演化和人工蜂群搜索相结合,利用元胞及其邻居的演化提高了种群多样性,避免陷入局部最优解.经一系列典型0-1规划问题实例的仿真实验和与其他算法对比,验证了本算法的效果和效率,获得了满意的结果.     

遗传-人工蜂群融合算法及其Markov收敛性分析

本文研究了遗传算法易发生"早熟"以及人工蜂群算法在搜索初期寻优速度慢的问题.基于将遗传算法与人工蜂群算法融合以实现二者互补的思想,提出遗传-人工蜂群融合算法(G-ABCA),利用马尔可夫理论对其收敛性进行了理论分析,证明其适应度函数值序列(即优化解满意值序列)是单调且收敛的,并利用四个经典的多峰测试函数对遗传-人工蜂群融合算法、改进的遗传算法以及人工蜂群算法进行了对比实验分析,结果表明:遗传-人工蜂群融合算法不仅收敛,而且其寻优性能显著优于其它两种算法.     

非线性0-1规划问题的元胞灰狼优化算法

针对非线性0-1规划求解问题,基于元胞自动机原理和改进的灰狼算法,提出一种元胞灰狼优化算法.首先,为了避免基本灰狼算法种群分布的随机性问题,利用佳点集理论对灰狼种群进行初始化,增强算法种群的多样性,提高算法的全局收敛速度;其次,针对基本灰狼算法的开发和探索能力平衡能力差的问题,利用自适应精英学习策略分别对算法中的参数α、灰狼与猎物的距离进行修正,实现灰狼算法的全局搜索速度和开发探索能力的最优均衡性;最后,将元胞自动机的演化规则与次优解β灰狼位置以及第三优解δ灰狼位置进行更新,利用元胞及其邻居增强搜索过程的多样性和分布性,实现灰狼算法的全局优化能力;并选用14个典型的非线性0-1规划问题算例进行仿真解算,并将解算结果与其它算法进行比较,结果表明:该算法对大规模复杂问题求解的平均运行时间少10%左右,且具有较快的收敛速度、较多的最优解集和较好的全局寻优能力.     

N车探险问题的一种ε-近似度的近似算法

本文探讨了一类N车探险问题的近似算法,首先通过建模将N车问题转变为一个等价的非线性0-1混合整数规划问题,进而将该非线性0-1混合整数规划问题转化为一个一般的带约束非线性规划问题,并用罚函数的方法将得到的带约束非线性规划问题化为相应的无约束问题.我们证明了可通过求解该无约束非线性规划问题得到原N车问题的ε-近似度的近似解,并设计了-个收敛速度为二阶的迭代箅法,文章最后给出算法实例.     

多气源天然气管网运行优化问题的混合整数规划模型及其算法

对于多气源天然气管网运行优化问题,文章首先引入了刻画压缩机开关的0-1整数变量,并对非线性的管道压降方程进行了合理的松弛化处理,建立了更符合实际的非线性混合整数规划模型.其次,基于序列线性化的思想,设计了一种求解该模型的序列混合整数线性化算法.最后,在不同规模的天然气管网系统中进行了多方面的对比实验.实验结果表明,新模型及求解算法能够有效降低成本、减少压缩机能耗,并且所需求解时间大大减少.     

An inexact-restoration method for nonlinear bilevel programming problems

We present a new algorithm for solving bilevel programming problems without reformulating them as single-level nonlinear programming problems. This strategy allows one to take profit of the structure of the lower level optimization problems without using non-differentiable methods. The algorithm is based on the inexact-restoration technique. Under some assumptions on the problem we prove global convergence to feasible points that satisfy the approximate gradient projection (AGP) optimality condition. Computational experiments are presented that encourage the use of this method for general bilevel problems. This work was supported by PRONEX-Optimization (PRONEX—CNPq/FAPERJ E-26/171.164/2003—APQ1), FAPESP (Grants 06/53768-0 and 05-56773-1) and CNPq.     

考虑占位决策的围堵嫌犯模型

研究了2011年中国大学生数学建模竞赛B题的突发事件中交巡警对在逃嫌犯的围堵问题。不同于对该问题的以往的研究,本文考虑了交巡警在包围圈中可以占据某些路口,使得嫌犯不能通过这些被交巡警占据的路口,从而为形成包围圈的交巡警赢得更多时间。利用两篇相关文献的关于点截集判断的结论和考虑占位决策的建模方法,以不同的目标函数建立了考虑占位决策的围堵嫌犯问题的三个混合0-1非线性整数规划模型。通过选取部分线性约束和目标函数一起组合成混合0-1线性整数规划模型,设计了基于混合0-1线性整数规划方法的算法,并给出了算例。     

A scenario decomposition algorithm for 0–1 stochastic programs

We propose a scenario decomposition algorithm for stochastic 0–1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and nonlinear stochastic integer programming test problems are presented.     

A trust region algorithm for solving bilevel programming problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.     

灰色非线性约束规划的改进引力搜索算法求解

灰色非线性约束规划是灰色系统中一个重要的优化问题.为求解灰色非线性约束规划,给出了一种改进引力搜索算法的求解方法.实验结果表明改进引力搜索算法对求解灰色非线性约束规划可行有效.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

多目标0-1规划问题的元胞狼群优化算法研究

针对多目标0-1规划问题,首先基于元胞自动机原理和人工狼群智能算法,提出一种元胞狼群优化算法,该算法将元胞机的演化规则与嚎叫信息素更新规则、人工狼群更新规则进行组合,采用元胞及其邻居来增强搜索过程的多样性和分布性,使人工头狼在元胞空间搜索的过程中,增强了人工狼群算法的全局搜索能力,并获得更多的全局非劣解;其次结合多目标0-1规划模型对元胞狼群算法进行了详细的数学描述,定义了人工狼群搜索空间、移动算子、元胞演化规则和非劣解集更新规则,并给出了元胞狼群算法的具体实现步骤;最后通过MATLAB软件对3个典型的多目标0-1规划问题算例进行解算,并将解算结果与其它人工智能算法的结果进行比较,结果表明:元胞狼群算法在多目标0-1规划问题求解方面可获得更多的非劣解集和更优的非劣解,并具有较快的收敛速度和较好的全局寻优能力。     

Numerical Comparison of Augmented Lagrangian Algorithms for Nonconvex Problems

Augmented Lagrangian algorithms are very popular tools for solving nonlinear programming problems. At each outer iteration of these methods a simpler optimization problem is solved, for which efficient algorithms can be used, especially when the problems are large. The most famous Augmented Lagrangian algorithm for minimization with inequality constraints is known as Powell-Hestenes-Rockafellar (PHR) method. The main drawback of PHR is that the objective function of the subproblems is not twice continuously differentiable. This is the main motivation for the introduction of many alternative Augmented Lagrangian methods. Most of them have interesting interpretations as proximal point methods for solving the dual problem, when the original nonlinear programming problem is convex. In this paper a numerical comparison between many of these methods is performed using all the suitable problems of the CUTE collection.This author was supported by ProNEx MCT/CNPq/FAPERJ 171.164/2003, FAPESP (Grants 2001/04597-4 and 2002/00094-0 and 2003/09169-6) and CNPq (Grant 302266/2002-0).This author was partially supported by CNPq-Brasil and CDCHT-Venezuela.This author was supported by ProNEx MCT/CNPq/FAPERJ 171.164/2003, FAPESP (Grant 2001/04597-4) and CNPq.     

非线性比式和问题的全局优化算法

In this paper,a global optimization algorithm is proposed for nonlinear sum of ratios problem(P).The algorithm works by globally solving problem(P1) that is equivalent to problem(P),by utilizing linearization technique a linear relaxation programming of the (P1) is then obtained.The proposed algorithm is convergent to the global minimum of(P1) through the successive refinement of linear relaxation of the feasible region of objective function and solutions of a series of linear relaxation programming.Nume...