具有实际约束的多阶段M-V投资组合时间一致性策略研究

从动态规划的角度分析,方差算子的不可分离性导致标准的多阶段均值-方差模型的最优投资策略不满足时间一致性。文章采用条件期望映射的方法,构建了一个具有交易成本、借贷约束和阈值约束的多阶段M-V投资组合模型。由于考虑了交易成本,该模型是一个具有路径依赖性的动态优化问题。为了获得其时间一致性投资策略,文章将该问题近似地转化为连续性动态规划模型,证明最优解的近似度,并运用离散迭代算法求解。最后,使用上海证券交易所的部分历史数据验证了模型和算法的有效性。     

并列选择单亲遗传算法在自动化立体仓库货位优化中的应用

针对传统遗传算法在求解自动化立体仓库货位优化多目标模型中容易陷于局部最优解以及交叉变异过程中产生大量不可行解等问题,提出了并列选择单亲遗传算法.算法采用了0,1矩阵编码、并列选择算子、单亲变异算子等,有效避免了交叉变异操作产生不可行解的问题.通过对控制参数进行较合理地选取,算法能够综合考虑各子目标的相对优秀个体,从中选取出全局近似最优解,有效降低了算法陷于局部最优解的概率.利用该算法对36种货物的自动化立体仓库货位进行优化,通过比较优化前后的货位对应的拣选时间及货架重心可以看出,优化后的货位对应的拣选效率及货架稳定性均有明显提高.     

具有动应力、位移和稳定性约束的离散变量桁架结构布局优化设计算法

给出了在动应力、动位移和动稳定约束下离散变量结构布局优化设计问题的数学模型,用“拟静力”算法,将具有动应力约束、动位移约束和动稳定约束的离散变量结构布局优化设计问题化为静应力、静位移和静稳定约束的优化问题,然后利用两级优化算法求解该模型．优化过程由两级组成,拓扑级优化和形状级优化．在每一级,都使用了综合算法,并且在搜索过程中都根据两类设计变量的相对差商值进行搜索．对包含稳定约束和不包含稳定约束的优化结果做了比较,结果显示稳定性约束对优化结果产生较大的影响．     

基于权值编码的组合拍卖竞胜标确定启发式算法研究

针对较大规模组合拍卖竞胜标确定问题(WDP),提出了基于权值编码的竞胜标确定启发式算法.改进了算法编码机制并嵌入基于WDP本质特点的启发式搜索规则,极大地提高了算法进化能力和求解效率.模拟实验结果表明该算法能够在较短时间内求出WDP最优解或满意近似解,为较大规模网上组合拍卖竞胜标确定问题提供了切实可行的求解算法.     

离散变量的分级优化方法及其应用

在工程优化设计中,绝大多数实际问题的设计变量往往限定取离散值,为了求得问题的真正最优解,就必须采用离散变量的优化方法进行求解.本文根据离散变量数学规划的特性,提出了一种分级优化搜索算法.这种方法的基本思想是在约束集合内,寻求一可行的离散初始点,然后在该点的邻域内,进行分级寻优搜索,以求得一个改进的新离散点,随之,以该点作为初始点,重复执行分级寻优搜索过程,直至求得问题的最优解.通过对工程实例的计算,证明本文所提出的新方法具有快速、简便的特点,能有效地应用各种工程优化设计问题.     

基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法

传统的求解0-1规划问题方法大多属于直接离散的解法.现提出一个包含严格转换和近似逼近三个步骤的连续化解法:(1)借助阶跃函数把0-1离散变量转化为[0,1]区间上的连续变量;(2)对目标函数采用逼近折中阶跃函数近光滑打磨函数,约束条件采用线性打磨函数逼近折中阶跃函数,把0-1规划问题由离散问题转化为连续优化模型;(3)利用高阶光滑的解法求解优化模型.该方法打破了特定求解方法仅适用于特定类型0-1规划问题惯例,使求解0-1规划问题的方法更加一般化.在具体求解时,采用正弦型光滑打磨函数来逼近折中阶跃函数,计算效果很好.     

求解线性二层规划问题的多表旋转算法

多表旋转算法是一种基于旋转算法来求解线性二层规划问题的方法,通过表格组合还可以求解线性多层规划、以及线性一主多从有关联的stackelberg-nash均衡等问题,求解的思想是使用旋转算法,在多个主体间通过约束传递达到均衡。通过算例显示该方法可以迅速地算出局部最优解,如果问题的诱导域是连通的,还可以计算出全局最优解。     

并行技术在约束凸规划化问题的对偶算法中的应用

用 Rosen(196 1)的投影梯度的方法求解约束凸规划化问题的对偶问题 ,在计算投影梯度方向时 ,涉及求关于原始变量的最小化问题的最优解 .我们用并行梯度分布算法 (PGD)计算出这一极小化问题的近似解 ,证明近似解可以达到任何给定的精度 ,并说明当精度选取合适时 ,Rosen方法仍然是收敛的     

均值—动态VaR多阶段投资组合优化研究

将动态风险度量方法运用到多阶段投资组合中,提出了具有交易成本和交易量限制的均值—动态VaR多阶段投资组合模型,并运用自创算法——离散近似迭代法求解.方法的基本思路为:首先,将模型中的连续型状态变量离散化,并将上述模型转化多阶段赋权有向图,然后,运用极大代数求出起点至终点的最长路程,即获得模型的一个可行解;最后,以该可行解为基础,继续迭代直到前后两个可行解非常接近.证明了该方法的收敛性,并以一个具体的算例,验证了该算法可以较快地计算出不同终期财富所对应的最优投资策略.     

有时间窗装卸问题的多策略分组编码遗传算法

根据有时间窗装卸问题(PDPTW)的数学模型,设计了多策略分组编码遗传算法,将禁忌思想用于产生可行解的启发式插入算法之中,对计算实例进行了求解,结果表明,此算法可以有效求得有时间窗装卸问题的近似最优解.     

On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions

The winner determination problem (WDP) in combinatorial auctions is the problem of, given a finite set of combinatorial bids B, finding a feasible subset B of B with a maximum revenue. WDP is known to be equivalent to the maximum weight set packing problem, and hard to approximate by polynomial time algorithms. This paper proposes three heuristic bid ordering schemes for solving WDP; the first two schemes take into account the number of goods shared by conflicting bids, and the third one is based on a recursive application of such local heuristic functions. We conducted several experiments to evaluate the goodness of the proposed schemes. The result of experiments implies that the first two schemes are particularly effective to improve the performance of the resulting heuristic search procedures. More concretely, they are scalable compared with the conventional linear programming (LP) relaxation based schemes, and could quickly provide an optimum solution under optimization schemes such as the branch-and-bound method. In addition, they exhibit a good anytime performance competitive to the LP-based schemes, although it is sensitive to configurable parameters controlling the strength of contributions of bid conflicts to the resultant bid ordering schemes.     

Heuristic concentration: Two stage solution construction

By utilizing information from multiple runs of an interchange heuristic we construct a new solution that is generally better than the best local optimum previously found. This new, two stage, approach to combinatorial optimization is demonstrated in the context of the p-median problem. Two layers of optimization are superimposed. The first layer is a conventional heuristic the second is a heuristic or exact procedure which draws on the concentrated solution set generated by the initial heuristic. The intention is to provide an alternative heuristic procedure which, when dealing with large problems, has a higher probability of producing optimal solutions than existing methods. The procedure is fairly general and appears to be applicable to combinatorial problems in a number of contexts.     

A robust algorithm for generalized geometric programming

Most existing methods of global optimization for generalized geometric programming (GGP) actually compute an approximate optimal solution of a linear or convex relaxation of the original problem. However, these approaches may sometimes provide an infeasible solution, or far from the true optimum. To overcome these limitations, a robust solution algorithm is proposed for global optimization of (GGP) problem. This algorithm guarantees adequately to obtain a robust optimal solution, which is feasible and close to the actual optimal solution, and is also stable under small perturbations of the constraints.     

Rollout Algorithms for Combinatorial Optimization

We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential application. In particular, we embed the problem within a dynamic programming framework, and we introduce several types of rollout algorithms, which are related to notions of policy iteration. We provide conditions guaranteeing that the rollout algorithm improves the performance of the original heuristic algorithm. The method is illustrated in the context of a machine maintenance and repair problem.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

Approximate solution of the trust region problem by minimization over two-dimensional subspaces

The trust region problem, minimization of a quadratic function subject to a spherical trust region constraint, occurs in many optimization algorithms. In a previous paper, the authors introduced an inexpensive approximate solution technique for this problem that involves the solution of a two-dimensional trust region problem. They showed that using this approximation in an unconstrained optimization algorithm leads to the same theoretical global and local convergence properties as are obtained using the exact solution to the trust region problem. This paper reports computational results showing that the two-dimensional minimization approach gives nearly optimal reductions in then-dimension quadratic model over a wide range of test cases. We also show that there is very little difference, in efficiency and reliability, between using the approximate or exact trust region step in solving standard test problems for unconstrained optimization. These results may encourage the application of similar approximate trust region techniques in other contexts.Research supported by ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NSF cooperative agreement DCR-8420944.     

Embedding evolutionary strategy in ordinal optimization for hard optimization problems

This work proposes a method for embedding evolutionary strategy (ES) in ordinal optimization (OO), abbreviated as ESOO, for solving real-time hard optimization problems with time-consuming evaluation of the objective function and a huge discrete solution space. Firstly, an approximate model that is based on a radial basis function (RBF) network is utilized to evaluate approximately the objective value of a solution. Secondly, ES associated with the approximate model is applied to generate a representative subset from a huge discrete solution space. Finally, the optimal computing budget allocation (OCBA) technique is adopted to select the best solution in the representative subset as the obtained “good enough” solution. The proposed method is applied to a hotel booking limits (HBL) problem, which is formulated as a stochastic combinatorial optimization problem with a huge discrete solution space. The good enough booking limits, obtained by the proposed method, have promising solution quality, and the computational efficiency of the method makes it suitable for real-time applications. To demonstrate the computational efficiency of the proposed method and the quality of the obtained solution, it is compared with two competing methods – the canonical ES and the genetic algorithm (GA). Test results demonstrate that the proposed approach greatly outperforms the canonical ES and GA.     

An analytical approach to global optimization

Global optimization problems with a few variables and constraints arise in numerous applications but are seldom solved exactly. Most often only a local optimum is found, or if a global optimum is detected no proof is provided that it is one. We study here the extent to which such global optimization problems can be solved exactly using analytical methods. To this effect, we propose a series of tests, similar to those of combinatorial optimization, organized in a branch-and-bound framework. The first complete solution of two difficult test problems illustrates the efficiency of the resulting algorithm. Computational experience with the programbagop, which uses the computer algebra systemmacsyma, is reported on. Many test problems from the compendiums of Hock and Schittkowski and others sources have been solved.The research of the first and the third authors has been supported by AFOSR grants #0271 and #0066 to Rutgers University. Research of the second author has been supported by NSERC grant #GP0036426 and FCAR grants #89EQ4144 and #90NC0305.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

改进鲸鱼优化算法在电力负荷调度中的应用

为了提高鲸鱼优化算法(WOA)的全局优化性能, 提出了一种基于黄金分割搜索的改进鲸鱼优化算法(GWOA)。首先利用黄金分割搜索对WOA的初始种群进行初始化, 使得初始种群能够尽可能的靠近全局最优解, 然后利用黄金分割搜索所形成的变区间, 进行变区间黄金分割非均匀变异操作, 以增加WOA的粒子多样性和提高粒子跳出局部最优陷阱的能力, 从而改善WOA的寻优性能。选取了15个大规模测试函数进行数值仿真测试, 仿真结果和统计分析表明GWOA的寻优性能要优于对比文献的改进鲸鱼优化算法(IWOA)。此外, 将GWOA用于对工程实际应用领域中的电力负荷优化调度问题进行实例分析, 实例应用结果表明, GWOA能有效对电力负荷优化调度问题进行寻优求解。