几类非线性双层规划问题的混合遗传算法

针对几类具有特殊下层结构的非线性双层规划问题,提出了一种混合遗传算法。首先利用单纯形法的思想设计了新的杂交算子,使杂交个体与种群中好的个体组杂交,从而产生尽可能好的杂交后代;其次对每个相对固定的上层变量值x,通过计算下层最优解y来提高种群个体的可行性,并分析了下层最优解的计算误差对算法性能的影响;最后对于下层存在多个最优解的情况,通过求解一个单层规划,给出了下层最优解的选择方法。数值结果表明该算法是有效的。     

基于正交遗传算法的非线性两层规划问题解法

对于一类非线性两层规划问题,将下层规划分解成几个并列且独立的子问题。对于上层的每一个决策变量,求出下层各子问题的Karush-Kuhn-Tucker(K-K-T)稳定点,作为对上层决策的反应。针对上层问题,设计了自适应的正交遗传算法,并给出其全局收敛性证明。最后数值模拟验证了该算法的高效性及鲁棒性。     

Orthogonal genetic algorithm for solving quadratic bilevel programming problems

A quadratic bilevel programming problem is transformed  into a single level complementarity slackness problem by applying  Karush-Kuhn-Tucker (KKT) conditions. To cope with the complementarity  constraints, a binary encoding scheme is adopted for  KKT multipliers, and then the complementarity slackness problem  is simplified to successive quadratic programming problems,  which can be solved by many algorithms available. Based on 0−1  binary encoding, an orthogonal genetic algorithm, in which the orthogonal  experimental design with both two-level orthogonal array  and factor analysis is used as crossover operator, is proposed.  Numerical experiments on 10 benchmark examples show that the  orthogonal genetic algorithm can find global optimal solutions of  quadratic bilevel programming problems with high accuracy in a  small number of iterations.     

求解非线性双层规划问题的混合变邻域粒子群算法

针对非线性双层规划难以获得全局最优的问题,汲取粒子群算法的快速搜索能力及变邻域搜索算法的全局搜索优势,提出了求解非线性双层规划问题的混合变邻域粒子群算法.首先利用Kuhn-Tucker条件,将非线性双层规划转化为一个单层规划问题,然后由粒子群算法得到一个较优的群体,通过审敛因子判断陷入局部最优的粒子,并进一步利用变邻域搜索算法的全局搜索能力对陷入局部最优的粒子进行优化,从而得到全局最优.测试函数的仿真实验对比分析证明了该算法的有效性.     

Improved genetic algorithm for nonlinear programming problems

An improved genetic algorithm(IGA) based on a novel selection strategy to handle nonlinear programming problems is proposed.Each individual in selection process is represented as a three-dimensional feature vector which is composed of objective function value,the degree of constraints violations and the number of constraints violations.It is easy to distinguish excellent individuals from general individuals by using an individuals’ feature vector.Additionally,a local search(LS) process is incorporated into selection operation so as to find feasible solutions located in the neighboring areas of some infeasible solutions.The combination of IGA and LS should offer the advantage of both the quality of solutions and diversity of solutions.Experimental results over a set of benchmark problems demonstrate that IGA has better performance than other algorithms.     

一般两层非线性规划问题的模拟退火全局优化

提出了一种基于模拟退火算法求解一般两层非线性规划问题的全局优化策略.采用模拟退火算法è求解上层问题,用精确惩罚函数处理约束,保证了算法稳定迅速地收敛于全局最优解.为了提高算法的效率,对标准模拟退火算法采取了一些改进措施.下层的非线性规划问题则采用可变容差单纯型算法完成求解.所设计的组合算法思路清晰,编程简单,数值计算结果表明,该算法有着良好的全局收敛可靠性和较高的收敛速度,是求解一般两层非线性规划问题的一种有效算法.     

求解半向量双层规划问题的精确罚函数法

研究半向量双层规划问题的求解方法. 利用Benson’s方法及线性规划问题的对偶理论,将半向量双层规划问题转化为一个单层优化问题,同时提出了转化问题的偏静态条件定义. 基于此定义,构造了半向量双层规划的精确罚问题,得到了此类双层规划问题的最优性条件,并给出相应的求解方法. 最后通过一个数值例子表明了求解方法的可行性.     

二层线性规划的有效解

在容许集有界且二层线性规划存在最优解是相应双目标规划有效解的假设下,证明了有效最优解可在容许集的顶点达到。给出了二层线性规划的解的更为合理的有效化方法,并用算例对各种有效化方法所得的有效解进行了比较。     

基于递阶优化算法的一类两层规划问题的解法

提出一种基于分解协调的两级递阶结构优化算法来求解两层规划问题。通过设计解耦变量,两层规划问题被分解成若干相互独立的易于在结构的第一级求解的子问题。而结构的第二级是调整解耦变量使各子问题的解得以改善。算法以一种迭代的方式使第一级求得的子问题的解不断协调,最终达到两层规划的解。算例表明该算法是可行且有效的     

New partial cooperation model for bilevel programming problems

Partial cooperation models are studied for many years to solve the bilevel programming problems where the follower’s optimal reaction is not unique. However, in these existed models, the follower’s cooperation level does not depend on the leader’s decision. A new model is proposed to solve this deficiency. It is proved the feasibility of the new model when the reaction set of the lower level is lower semicontinuous. And the numerical results show that the new model has optimal solutions when the reaction set of the lower level is discrete, lower semi-continuous and non-lower semi-continuous.     

求解混合整数规划的嵌入正交杂交的差分进化算法

针对混合整数非线性规划问题中同时含有0-1整数变量和连续变量,采用0-1二进制编码和实数编码的混合编码方案,将布尔逻辑运算中的异或(exclusive or, XOR)算子引入到差分进化的变异算子中,以处理0-1整数变量,将基于正交试验设计的正交杂交算子和差分进化的杂交算子相结合,来增强差分进化算法的系统探索能力。为了验证该算法的性能,测试了一些数值例子,并与其他算法作了比较。数值实验结果表明,提出算法具有良好的稳健性和有效性。     

一种多损失条件风险值的双层规划模型及应用

在两级供应链中制造商与零售商之间的多产品定价与订购问题, 是一个多损失的双层风险决策问题, 可以建立双层规划模型解决. 本文研究了一种多损失条件风险值的双层规划模型, 对于多个损失函数和对应的权值水平, 在给定的置信水平下, 定义了不超过给定损失值的最小风险值(即VaR值)和对应的累积期望损失值(即CVaR损失值) 概念, 然后建立了一个多损失条件风险值的双层规划模型, 该模型的目标是求上下层的多损失CVaR值达最小的最优策略, 我们证明了它可以通过另一个较容易求解的双层规划模型获得最优解. 最后, 给出了两级供应链中多产品的定价与订购的双层条件风险值模型, 通过对2种面包产品销售数据进行计算, 获得了面包制造商的最优批发价和最优回购策略, 及零售商最优订购量.     

Global convergent algorithm for the bilevel linear fractional-linear programming based on modified convex simplex method

A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming,which is a special class of bilevel programming.In our algorithm,replacing the lower level problem by its dual gap equaling to zero,the bilevel linear fractional-linear programming is transformed into a traditional single level programming problem,which can be transformed into a series of linear fractional programming problem.Thus,the modified convex simplex method is used to solve the infinite linear fractional programming to obtain the global convergent solution of the original bilevel linear fractional-linear programming.Finally,an example demonstrates the feasibility of the proposed algorithm.     

一个物流网络的双层规划模型

物流网络的规划与布局不仅影响企业的经营活动，而且影响城市的交通运输功能．在一个物流周期内，用广义费用的概念描述了物流成本的相关内容，从物流成本的角度对物流中心的规模和位置进行优化．通过考察物流中心布局与配送作业成本之间的关系，以物流总费用最小为目标函数建立了一个双层规划模型．随后，用遗传算法得到一个该模型的近似最优解．实例所得结果证明了模型的实用价值及其有效性．     

Solution for integer linear bilevel programming problems using orthogonal genetic algorithm

An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorithm is developed for solving the binary linear implicit programming problem based on the orthogonal design. The orthogonal design with the factor analysis, an experimental design method is applied to the genetic algorithm to make the algorithm more robust, statistical y sound and quickly convergent. A crossover operator formed by the orthogonal array and the factor analysis is presented. First, this crossover operator can generate a smal but representative sample of points as offspring. After al of the better genes of these offspring are selected, a best combination among these offspring is then generated. The simulation results show the effectiveness of the proposed algorithm.     

Multiobjective evolutionary algorithm for dynamic nonlinear constrained optimization problems

A new method to solve dynamic nonlinear constrained optimization problems (DNCOP) is proposed. First, the time (environment) variable period of DNCOP is divided into several equal subperiods. In each subperiod, the DNCOP is approximated by a static nonlinear constrained optimization problem (SNCOP). Second, for each SNCOP, inspired by the idea of multiobjective optimization, it is transformed into a static bi-objective optimization problem. As a result, the original DNCOP is approximately transformed into several static bi-objective optimization problems. Third, a new multiobjective evolutionary algorithm is proposed based on a new selection operator and an improved nonuniformity mutation operator. The simulation results indicate that the proposed algorithm is effective for DNCOP.     

一种求解二阶锥规划问题的新算法

为了提高求解二阶锥规划问题的效率,提出一种新的求解二阶锥规划问题的非单调信赖域算法.基于Fischer-Burmeister光滑函数,对二阶锥规划问题的最优性条件进行转化,得到与其等价的无约束优化问题的非线性可微的光滑方程组,构造信赖域子问题,利用非单调信赖域算法求解.算法在求解信赖域子问题时,提出了一个新的自适应选取信赖域半径机制,搜索到全局最优解.数值实验结果表明,该算法运行速度快、迭代次数少,比内点算法和不可行内点算法优越.     

基于免疫规划的单亲遗传算法研究及其应用

在分析了单亲遗传算法的优越性与存在不足的基础上,借鉴生物免疫概念与理论,提出了一种新的单亲遗传算法——基于免疫规划的单亲遗传算法。该算法的核心在于使用最优保留策略前提下,合理地构造了非均匀算子和免疫算子。理论分析和仿真结果表明,该算法不仅能够有效地保持群体多样性,而且减轻了遗传算法的后期波动现象,同时收敛速度明显提高。     

求解多目标二层规划的多目标进化算法

提出了一个求解多目标二层规划问题的多目标进化算法.用传统优化算法求解下层规划中用权向量线性加权后得到的单目标问题,而对上层的多目标规划问题则采用基于NSGA-II的选择机制的多目标进化算法求解.数值试验表明所提出的算法是有效的.     

启发式交叉求解TSP问题的混合遗传算法

在给出度约束最小生成树的快速生成方法的基础上，设计了一种启发式交叉求解TSP问题的混合遗传算法．该算法在交叉操作的设计上，与其他遗传算法有本质的不同，该交叉操作是在不违反度约束和不形成圈的前提下，每次从父代基因所拥有的边中加入权最小的边，从而形成子代．利用该算法得到了TSP CHN144问题迄今为止最好的解．