优化求解

2024-08-15

优化求解（共9篇）

优化求解篇1

然而, 粒子群优化算法常有陷入局部极值、过早收敛和收敛性能不佳的缺点。为了克服PSO的缺点, 出现了大量的改进PSO算法, 如自适应粒子群优化算法[4]、带约束因子的粒子群优化算法[5,6]、杂交粒子群算法[7]或增加粒子群的规模, 尽管这些改进对算法的性能有一定改善, 但效果不佳, 未能从根本上克服早熟收敛问题, 况且会增加算法的运算量。再次, 在函数的维数增加时, 很多改进的方法显得束手无策。但对某些问题, 比如函数优化中的解分布于坐标轴原点附近的一类问题, 通过对惯性权重和粒子群算法公式的分析, 选用合适的惯性权重值, 改进粒子的进化迭代公式, 简化进化过程, 使该类问题在求解中可以快速找到给定目标解。

本文针对函数优化中的解分布于坐标轴原点附近的一类问题, 利用简化计算方法, 选取合适惯性权重值, 提出了一种改进的粒子群优化算法。

1粒子群算法

设有N个粒子组成一个群体, 在D维空间中搜索目标, 其中第i个粒子记为一D维向量xi= (xi1, xi2, …, xiD) ;i = 1, 2, …, N。第i个粒子的飞行速度也是一个D维的向量, 记为vi = (vi1 , vi2 , …, viD) , i= 1, 2, …, N。并记第i个粒子迄今为止搜索到的最优位置为pi= (pi1, pi2, …, piD) , 整个粒子群迄今为止搜索到的最优位置为pg= (pg1, pg2, …, pgD) 。每个粒子的速度和位置按如下公式进行更新:

v $_{i d}^{t + 1}$ =v $_{i d}^{t}$ +c1r1 (p $_{i d}^{t}$ -x $_{i d}^{t}$ ) +c2r2 (p $_{g d}^{t}$ -x $_{i d}^{t}$ ) (1)

x $_{i d}^{t + 1}$ =x $_{i d}^{t}$ +v $_{i d}^{t + 1}$ (2)

其中i=1, 2, …, N;d=1, 2, …, D;t表示进化到第t代;学习因子c1和c2是非负常数, 通常取c1=c2=2;r1, r2为服从U～ (0, 1) 分布的两个相互独立的随机数;vid∈[-vmax, vmax], vmax是常数, 根据实验需要与函数本身设定其大小。迭代终止条件为预设的最大迭代次数或 (和) 预定的最小适应度阈值。

为改善PSO算法的性能, Shi和Ebrhart在速度进化方程中引入惯性权重[4], 即把式 (1) 变为:

v $_{i d}^{t + 1}$ =ωv $_{i d}^{t}$ +c1r1 (p $_{i d}^{t}$ -x $_{i d}^{t}$ ) +c2r2 (p $_{g d}^{t}$ -x $_{i d}^{t}$ ) (3)

式 (3) 中ω称为惯性权重, 通常取值在0.8～1.4之间, 通过实验证明, ω随着算法迭代的进行而线性减小, 算法的收敛性能得以改善。较大ω值有利于提高算法的收敛速度, 而较小ω值有利于提高算法的收敛精度。惯性权重ω使微粒保持运动惯性, 具有探索新区域和扩展搜索空间的功能[4,8]。

学者们通常把由式 (1) 、式 (2) 进行迭代的算法称为基本粒子群算法[9] (bPSO算法) , 而把式 (2) 、式 (3) 进行迭代的算法称为标准粒子群算法[9] (sPSO算法) 。因此, 基本粒子群算法是标准粒子群算法的特例 (即ω=1) 。有关PSO算法的研究大多以带惯性权重的PSO算法为基础进行扩展和修正。

2标准粒子群算法 (sPSO) 的有关分析及算法的改进

有关sPSO及相关算法的改进, 基本上是基于微粒速度和位置两个概念, 如自适应参数变化、变异、或增加混沌搜索等, 这既使得PSO算法描述复杂化, 也使得对PSO的收敛性分析增加了难度[10,11,12]。

从式 (2) 、式 (3) 式可知, 尽管xi和vi是多维的变量, 但各维之间相互独立, 因而, 对算法的分析可以简化至一维中进行:即粒子的速度可以省略。粒子的位置xi表示问题的解, 故算法的迭代过程, 就是xi向x* (全局最优位置) 无限逼近的过程。因而在迭代中, 我们关注的是xi的变化, 而非vi的变化。可以得出如下结论。

2.1定理:sPSO的进化过程与粒子速度无关[10,13]

证明迭代过程中, 除pid和pgd对搜索空间各维的联系以外, 各维的更新相互独立。故其过程可简化到一维进行。并假设粒子本身所找到最优解位置和整个种群找到的最优解位置不变, 记pb和pg, 令 $θ_{1} = r_{1} c_{1}, θ_{2} = r_{2} c_{2}, θ = θ_{1} + θ_{2}, ρ = \frac{θ_{1} p_{b} + θ_{2} p_{g}}{θ_{1} + θ_{2}}$ 并把式 (3) 和式 (2) 中变量符的上标移到变量符后的括号中, 则:

v (t+1) =ωv (t) +θ (ρ-x (t) ) (4)

x (t+1) =x (t) +v (t+1) (5)

将式 (4) 和式 (5) 迭代可以得到式 (6) :

x (t+2) + (θ-ω-1) x (t+1) +ωx (t) =θρ (6)

式 (6) 是二阶常系数非齐次差分方程。从定理可知:进化过程与速度无关, 那么就可以将进化过程予以简化。

2.2简化粒子群优化算法 (mPSO)

由分析可得, 不含速度项的粒子群迭代方程可简化为[10,13]:

x $_{i x}^{t + 1}$ =ωx $_{i x}^{t}$ +c1r1 (p $_{i d}^{t}$ -x $_{i d}^{t}$ ) +c2r2 (p $_{g d}^{t}$ -x $_{i d}^{t}$ ) (7)

式 (7) 中ωx $_{i d}^{t}$ 部分表示右端第一项对现在位置的影响, 其影响程度可以通过ω来调节;式 (7) 右端第二、三项与PSO的分析一致。

实验中, 把以式 (7) 进化的算法称为简化的粒子群优化算法 (mPSO) 。亦可将式 (7) 变形为一阶微分方程:

x (t+1) + (θ1+θ2-ω) x (t) =θ1pb+θ2p $_{g}^{}$ (8)

显然, 方程也由二阶降到了一阶, 其进化过程明显得到简化, 这将大大地提高计算的效率。

3一类函数优化问题求解的结果分析与性能比教

下面通过4个经典的Benchmark函数优化问题来测试笔者所提算法的性能, 并和已有结果进行比较。

3.1实验所用的测试函数

实验采用文献[4,14]中的四个函数。对于每个变量x, x=[x1, x2, …, xD]为D维实值向量, 定义:

f1 (x) = $\sum_{i = 1}^{D}$ x $_{i}^{2}$ (9)

f2 (x) =|x1|2+|x2|3 (10)

f3 (x) = $\sum_{i = 1}^{D}$ (x $_{i}^{2}$ -10cos (2πxi) +10) (11)

$f_{4} (x) = \frac{1}{4 000}$ $\sum_{i = 1}^{D}$ x $_{i}^{2}$ $\prod_{i = 1}^{D}$ $\cos (\frac{x_{i}}{\sqrt{i}}) + 1$ (12)

3.2比较固定收敛精度下所需的迭代次数

设定各函数的收敛精度为10-5, 改进算法采用经过20次独立运行后的收敛时的迭代范围, 取种群大小为N=50和N=100分别计算, c1=c2=2.0, 惯性权重ω取0.1, 维数取10维和30维 (f2为2维, 例外) , 比较基本粒子群算法 (PSO) 和改进的粒子群算法 (mPSO) [4,14], 改进算法中取位置xi初值时, 每一维的位置初值是任意选取的 (无范围限制) 。

求目标值为10-5, 实验结果如表1～表4。

表1f1函数所需迭代次数 (目标值为10-5)

*该实验中, ∞表示求目标值时迭代次数过大或无法求得目标值

3.3实验结果的分析与讨论

标准的粒子群算法 (sPSO) 中, Shi与Eberhart的惯性权重ω引入, 在ω取0.8—1.4的值时, 尽管基本上可以求得目标解, 但其迭代次数需要上百次乃至上千次。但对于f3函数, 在求解空间为4维, 有时却无法求得给定目标的解;在解空间为10维或更高维时, 用该法几乎无法求得目标解。

在改进的算法中, 采用简化的粒子群算法, 突破了ω的取值范围, 让ω取较小的值 (如取0.1。实际上, 根据需要, 可以让ω的值取得更小, 如0.01, 收敛则更快) , 该方法使解分布于坐标轴原点附近的函数优化问题快速求解, 仅仅需要3—7次迭代, 就可以找出满足条件的解, 该改进的方法大大提高了问题求解的效率。

其次, 从实验结果可知, 标准的粒子群算法对函数的维数增加很敏感, 而使用改进后的方法则不同。实际上, 维数增加时, 如100维或更高, 该改进的方法同样只需数次的迭代即可求解。

再次, 改进算法对粒子群的种群大小变化也不敏感, 只需要较小的种群就能达到较大种群的求解效果, 计算中内存的消耗量明显减少。

最后, 由于改进的算法使用不带速度项的迭代式, 在实验中, 对位置的初值也无范围限制, 且优化效果良好。

4结论与展望

本文通过对惯性权重ω以及粒子群算法公式的构成进行分析, 使用改进的简化粒子群算法, 并且突破ω的取值范围, 针对函数的解分布于坐标轴原点附近的优问题提出了改进的方法。通过实验证明, 该方法提高了算法的效率, 用极少次数的迭代, 使原本复杂甚至不能求解的问题得以解决。该算法对函数的维数变化不敏感, 在维数较多时, 其算法的优越性体现更加明显。同时, 改进的算法用较小的粒子群种群也可以取得较大种群的求解效果, 在计算中节约了内存资源。

本文所提的改进算法, 对于解分布于坐标轴原点附近的函数优问题作了较好地回答, 但对于解的分布不在坐标轴原点附近的函数优优化问题, 其效果不是很理想。对解的任意分布的函数优化问题, 开发出新的高效算法, 仍是值得考虑的问题。

优化求解篇2

摘要：本文提出了一种用于解决约束多目标优化问题的方法。本算法在进化算法的基础上加入了邻里竞争与邻里合作算子，并通过引入agent-based模型的设计理念，更加注重个体变化对整个群体的影响。本算法首先使用约束偏离值的方法将约束多目标优化问题简化为多目标优化问题;然后使用自我更新算子，当新产生的个体优于原先的个体时予以替换;之后通过邻里竞争与邻里合作加快种群内部的信息交流;最后加入量子加速算子，通过使用量子旋转门来扩大计算搜寻范围提高程序计算速度。本文最后与两种已有算法进行对比，实验结果表明，本算法完成了设计目标。在运行时间和输出结果精度方面都有不错的表现。

关键词：约束多目标优化约束偏离值邻里竞争量子计算

一、引言

进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术。与传统的优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性。尤其是在处理多目标优化问题时，进化算法表现出很好的效果。

近年来，出现了很多优秀的算法用于解决约束多目标优化问题，其中Deb提出的NSGA-II算法是最为经典的一个算法。NSGA-II成功的将进化算法应用在约束多目标优化问题上，在进化算法的基础上引入了约束偏离值。Hongguang Li提出了基于agent的进化算法用于求解约束多目标优化问题。算法利用agent概念认为每个个体与其种群内其他个体都有相互的作用和影响，虽然算法精度不是很高但是计算速度很快。本文受到基于agent概念的启发，希望设计出一个计算速度快，精度高的算法。

二、量子进化算法

2.1 邻里竞争与邻里合作

agent-based模型是一种从底层到高层的数学模型，模型更加注重的是每个个体对整个群体的影响，通过改变个体的某些特征和表现从而影响整个整体。本算法在此基础上，通过模仿自然界种群内部个体之间既有竞争又有合作的关系，设计出了邻里竞争与邻里合作算子。邻里竞争算子采用的是吞并算子，算子表示如下：

设对于一个种群共有k个个体X1，X2，…，Xi，每个个体的目标函数值分别为，则：

(1)

其中表示的是新产生的个体。公式表达的意义是：每个个体与其排名靠后一位的个体进行竞争，将两者目标函数值进行对比，目标函数值较小的个体成为这一位置上的新个体。

邻里合作算子如下：

(2)

(3)

其中，是个体i、j的第k个决策变量，且。r，u是分布在[0，1]之间的随机数。

2.2 量子计算

加入量子算子是为了加快计算速度，希望通过更少的进化代数进化出更加优秀的种群。本算法通过设计出一个对周围区域具有自适应调整搜索步长的量子旋转门，从而提升量子计算运行效率。量子计算首先需要将个体的基因编码从实数编码形式转换为量子编码形式，之后通过量子旋转门的计算快速搜索周围空间寻找更加优秀的个体进行输出。

个体在完成量子旋转门的计算后，个体的基因编码需要映射回实数域，完成其他计算过程。量子算子的本质也就是通过将个体基因编码转换为量子域，通过利用量子计算在量子域具有指数级加速和指数级存储的能力，快速的寻找最优解的过程。

2.3 算法的主要流程

图1为本算法流程图。算法采用顺序结构设计，结构简单，在进化计算的基础上首先使用了约束偏离值的方法，将约束多目标问题进行简化。其次借鉴了基于agent模型里种群中个体之间又相互的影响和作用，设计了邻里竞争与邻里合作算子。又利用了量子计算的加速性能，提升了算法的运行速度。

若为第一代种群，本算法通过之前修正好的目标函数向量进行选择，首先在可行解里选取非支配解，形成种群FeaPop，并在全部种群中寻找非支配解，放入种群NonPop中;若不是第一代种群，则将上一代产生的父代FeaPop与当代的进化种群Pop合并形成NPop，在合并之后的种群里再去寻找可行非支配解形成当代的FeaPop种群，寻找非支配解形成当代的NonPop。变异算子对于防止种群陷入局部最优解起到了重要的作用，本算法采用文献中非一致性变异算子。

三、仿真实验与结果分析

本文的测试问题是Deb提出的.六个经典的约束多目标最小化问题，算法参数设计为：初始种群大小为100，合作概率为0.9，合作指数为10，变异概率为0.5，非一致系数为2，自我更新指数为20。最大的可行非支配解集FeaPop大小为100，非支配解集NonPop大小为100。对比算法初始种群大小为100，交叉概率为0.9，交叉分布指数为15，变异概率为0.1，变异分布指数为20。

文中所有测试问题均独立运行30次，我们采用的度量指标分别为GD和算法运行时间。世代距离指标(GD)，是度量算法所得Pareto前端与真实前端之间的距离。其数学表达式如下式所示：

(4)

其中，，n为个体数目，是中第个个体的目标函数向量与中最近个体间的欧氏距离。GD值越小，所求得的前端就越接近真实前端，解集的收敛性就越好。运行时间则是算法的跑完相同进化代数所需要的时间，时间越短说明算法运行速度越快，本文中涉及到的几种算法运行代数均为1000代。

表1给出本文算法与两种对比算法运行6测试问题的结果。

CTP2、CTP7是寻找离散的几个线段，CTP3、CTP4两个问题要寻找的Pareto前端都是离散的端点，CTP5是离散点和线段的组合，CTP6问题是寻找连续的直线。从表中我们可以看出几种算法对于处理CTP2问题都有不错的结果，都可以很好地找到几个离散端点。对于CTP3和CTP4问题由于测试函数难度的加大，算法[3]已不能很好地找出真实Pareto前端所在位置，而NSGA-II、本算法还能找到真实Pareto前端所在区域，不过已经无法做到很精准的定位Pareto前端的位置。对于CTP5，几种算法在找离散点的能力都很不错。对于CTP6问题几种算法都找到了Pareto前端，只是均匀性稍有差异。CTP7问题，除了算法[3]之外也都很好的找到了前端所在区域。

4 总结与展望

优化求解篇3

关键词无约束优化；谱共轭梯度法；下降性；全局收敛

中图分类号 O224 文献标识码 A

1 引言

1952年Hestenes和Stiefel提出求解线性方程组Ax=b（x∈Rn）的共轭梯度法.当矩阵A对称正定时，解此方程组等价于求n元二次函数

的极小值点，1964年Fletcher和Reeves将该方法推广应用于解决非线性无约束优化问题，得到求一般函数极小值的共轭梯度法.因具有结构简单、计算机存储需要小等优点，共轭梯度法已经发展成为科学、工程、经济等领域中求解大规模优化问题的一类有效方法，至今对其研究依然很活跃.

考虑无约束优化问题

优化求解篇4

印染行业是一个典型的化工批处理[1] (间歇) 过程, 单靠人工很难对大量订单的生产做到合理的调度, 人工染缸排产己影响了车间的操作自动化。因此, 对印染生产进行研究, 建立合理的生产调度模型, 寻找有效的调度方法, 可大大提高生产效率和资源利用率, 增强企业的竞争能力。印染的核心过程是染色工艺, 故对印染企业来说, 调度的核心就是确定各类型的印染产品在染缸中的加工次序, 以达到最优生产目标。染色过程对于所有产品都相同, 并且在实际生产中企业每次调度往往只安排1-2天的生产任务, 所以印染生产也可以看做单阶段多产品批处理过程短期调度问题 (SMSP (Single Machine Scheduling Problem) ) 。

极值优化算法[2]是一种新型的智能算法, 在解决一些调度问题中显示出了独特的优势。该算法通过搜索相似局部空间来凸现全局最优, 进化过程更加遵循自然界规律, 利用解内变量之间关联性减少运算量。本文提出用极值优化算法结合优先适合启发式解决排产调度问题。

2. 印染生产调度的建模

在印染的染色过程中, 我们知道要对原材料进行染色, 则需要待染色的产品和染色剂等染色用品, 这就产生了染色所需的固定成本。在印染调度过程中, 有的产品需求量小, 有的产品需求量很大, 在这种情况下, 有时需要在染缸上对产品进行切换, 这就产生了切换费用, 不同的排产方式产生的总的切换费用是不同的。产品生产完在到达交货期之前需要放在仓库中进行储存, 产生了储存成本。另外, 有些时候由于排产调度安排不好, 可能会产生有的产品不能按时完工的情况, 这样需要向客户支付违约金。由上述可知不同的排产顺序会产生不同的切换成本、存储成本、违约款, 本文的目的则是通过有效的算法对该排产调度问题进行优化, 使印染的总成本最小。

由上述可得, 印染的总体成本如下式所示:

印染成本=固定成本+切换费用+储存成本+违约款

由上述可得到印染成本的数学模型如公式 (1) 所示:

上述公式中从左至右依次为固定成本、切换费用、储存成本、违约款。

3. 极值优化算法求解印染调度问题

3.1 极值优化算法

极值优化算法由Boettcher[3]在国际遗传与进化计算会议上首次提出。算法的思想源于自组织临界理论 (SOC[4]) , 其突出的特点为非平衡性 (准平衡性) 。EO算法不会收敛到一个平衡态, 而出现断续平衡, 产生的波动性使算法具有更好的持续搜索和跳出局优解的能力。极值优化算法的思想是通过不断的剔除最不期望的解元素, 产生一个改进的新解元素来替换。模拟自然界中的一个生物群落进化过程:淘汰最不适应的物种, 而出现新物种代替它。EO算法易于实现, 计算量小, 算法效果好, 因此得到了广泛的应用。与其他智能优化算法的比较研究表明, EO算法是解决NP难题的一种有效方法。

EO算法的基本流程

1产生一个初始化种群, 定义种群中的每一个物种及对应的适应值

2随机产生一个初始配置, 计算每个物种的适应值, 对所有的

进行排序, 排序的规则按照适应值

3选择适应值最差的变量进行更新

4在迭代次数内, 重复操作2至4的操作

5达到迭代次数时, 算法停止, 返回最好的C (S) , C (S) =

本文采用改进的EO算法—τ-EO, 引入了参数→, 即对适应值排序后, 按照正比于的概率选择。其中τ>0, τ越小, 选择概率的差别越小;τ越大, 最差的变量越容易被选中。当τ→0时, 此算法成为完全的随机算法;而当时, →-EO便成为基本EO算法。

EO算法是一种非平衡的算法, 不会收敛于某个平衡点, 在局部最优点附近有爬山能力。并且由于在求解过程中, EO算法每次迭代只处理一个解, 算法的计算量不会随着解的维数的增加呈指数增加, 极大的减少了算法的时间。

3.2 极值优化算法在印染调度问题上的应用

对于印染调度的具体问题, 在τ-EO算法的基础上引入了优先适合启发式算法来进行求解。对应每个订单都有染缸对该订单进行处理, 在到达该产品的交货期之前, 对应染缸对订单进行多个批次的处理。如果染缸的各个批次都按随机数产生, 则产生的排产调度模型很可能是不可行解。所以本文引入启发式规则对该调度模型按如下步骤进行初始化:

(1) 将产品随机排序分配染缸。

(2) 判断到达交货期时产品在对应染缸上是否处理完毕:完毕, 则该产品剩余需加工量为0;否则, 将该产品编号及剩余需加工量保存。

(3) 将染缸进行随机排序, 依次取出剩余需加工量不为0的产品编号, 取出重新排序后的第一个产品编号, 重新按照染缸顺序遍历所有染缸, 遇到已加工时间未到达产品交货期的染缸时, 则将该产品在此染缸上进行处理。

(4) 直至第一个产品处理完毕, 开始处理第二个产品。

(5) 直至所有产品的剩余需加工量为0或所有染缸均已到达交货期, 则认为初始化结束。

算法步骤

(1) 按照上述启发式规则初始化印染调度的排产顺序, 并将其初设为最优排产顺序, 求得此排产顺序的适应解做为最优解m_dBestFitness。

(2) 将各个染缸作为单个物种。

(3) 计算出整个排产过程中各个染缸上进行生产的单位成本, 即染缸上进行生产的总成本除以该染缸中进行生产的产品的总生产量。从小到大进行排序为:。

(4) 按照-EO算法选择需要进行调整的染缸。

(5) 按照上述启发式规则对模型重新进行初始化, 对初始化步骤中的 (3) 步进行调整, 将上述得到的需要进行调整的染缸放在随机排序好的染缸的最后, 这样做可以使适应值最差的染缸上最小几率发生两产品之间的切换, 即降低成本、增大其适应值。

(6) 求得第 (5) 步得到的排产顺序的适应值m_dFitness。剩余的n-1个标进行重新的随机完全排列, 返回 (2) 开始新的选择。

(7) 比较m_dFitness与m_dBestFitness。若m_dFitness

(8) 将第 (5) 步得到的排产顺序按照第 (2) - (8) 进行循环操作, 直至到达迭代次数, 返回成本最小的排产顺序。

4. 仿真结果与分析

本文仿真时采用大规模染缸排产调度问题, 染缸分为大、中、小三种类型的染缸, 每种类型的染缸用10个, 大规模产品的种类为30, 设定每个订单的到来时间与交货期。算法程序采用C++编写, 程序运行在4-M CPU/1.90Hz, 1G内存计算机上, 程序中设定迭代次数为10000次, 算例1设定=1.3。仿真图由Matlab7.1产生, 如图1所示。

由图1可以看出, 每次迭代得到的排产顺序均为可行解, 且偏离最优解 (生产成本最小的解) 的程度不大, 程序运行10000次, 达优率为98%, 运行时间平均为414.205s。且从图1中可以看到, EO算法不是一种平衡的算法, 它最终不收敛于一个平衡值, 在找到最优解以后, 每次迭代的目标函数值仍然不断震荡, 使算法具有跳出局部最优点的爬山能力。

程序得到的最优解f_best=34554.4, 我们认为, 在f_best的99%-102%范围内的值是可以接受的满意解。我们把算法的停止准则改为找到满意解即f_best*102% (35245.488) , 运行程序, 找到满意解则停止运行, 采用上述测试数据, 运行5次每次运行20遍, 结果见表1所示。

算例2同样采用上述算例1所采用的数据, 设定=1.4, 程序运行10000次, 达优率为95%。同样把算法的停止准则设为找到满意解即f_best*102% (35245.488) , 运行程序, 找到满意解则停止运行, 采用上述测试数据, 运行5次每次运行20遍, 结果见表2所示。

从上述结果可以看出=1.3时, EO算法达到满意解的平均时间最短, 算法性能最好。

由于篇幅限制, 这里只列出这两个例子。大量仿真实验表明, 本文提出的改进EO算法解决大规模排产调度成本问题有非常好的达优率, 且在=1.3时, 算法性能最好。

5. 小结

排产调度问题虽然有很多经典算法和智能优化算法尝试解决, 但是这些算法或者容易陷入局部最优解, 或者因为随机搜索的空间太大而无法找到最优解。极值优化算法总是淘汰最不适应的物种, 而产生新的物种。合理选择值, 并根据印染排产调度的实际问题, 引入优先适合启发式规则, 计算实例表明此算法运算时间短, 方法简单有效。

参考文献

[1]李慧芳, 李人厚, 陈浩勋.化工批处理过程调度综述[J].信息与控制, 1999, 28 (2) :1-4.

[2]M.P.Wachowiak, R.Smolikova, Y.F.Zheng, J.M.Zurada, and A.S.Elmaghraby, “An approach to multimodal biomedical image registrationutilizing particle swarm optimization, ”IEEE Trans.Evol.Comput., vol.8, pp.289–301, Jun.2004.

[3]Niculescu S.Delay effects on stability:A robust control approach[M].London:Spring-Verlay, 2001.

优化求解篇5

切削用量三要素包括切削深度、进给量、切削速度，在被加工的工件材料、刀具材料和刀具几何参数确定的情况下。切削力、切削功率、刀具磨损、工件和刀具强度和刚度等均为切削深度、进给量、切削速度的函数。切削用量的选择直接影响加工质量的好坏和生产效率的高低。目前工程师在加工工艺编制方面，是通过切削用量手册、实践总结或工艺试验来选择切削用量，并不是最优的切削用量。因此，在计算机发展的今天，如何合理选择切削用量，是金属切削重要问题。编制切削用量的优化计算求解是具有工程实际意义[1,2]。

1 切削用量选取的一般原则

根据金属切削原理，制订切削用量，就是在刀具材料和几何角度确定的基础上，合理确定切削深度ap、进给量f、和切削速度v，在充分利用刀具切削性能和机床性能，保证加工质量前提下，获高生产率和低加工成本切削用量[3,4]。

基本原则，使得切削加工的生产率高，加工相同体积所用时间tm最短：

式中，dw为车削加工前毛坯直径，lw为工件切削部分长度;Δ为加工余量;nw为工件转速。

限制条件包括：

(1)刀具耐用度满足要求条件

Tp计算刀具耐用度;T设定的刀具耐用度;CT为耐用度系数。

(2)切削功率条件

Pp为计算功率;PE为机床额定功率，η为机床效率。

(3)机床进给机构强度

(4)粗糙度指标

(5)另外切削深度、进给量和切削速度的边界限制条件：

2 基于加工时间最小的切削用量选取优化求解模型与程序设计

2.1 求解模型

若采用生产率为目标函数：;设计变量为z=[z1,z2,z3]T=[ap,f,v]T。其余条件均为约束条件。则切削用量选取的最优化问题模型可以描述为(1)，该模型属于含不等式约束的优化模型。切削深度ap单位为mm、进给量f单位为mm/r、切削速度v单位为m/min,

2.2 程序设计框图

本文按随机搜索方法的优化程序设计[5]，建立本文问题程序如图1。

3 算例分析

下面车削加工实例分析。

3.1 具体参数

(1)加工工件：材料45，σb=700MPa，毛坯dw=70mm，加工后dm=106mm，加工长度l=280mm，粗糙度Ra=3.2μm;粗车余量为

(2)所用车刀：刀杆B×H=16mm×25mm，刀片材料硬质合金YT15，刀片厚度4.5mm，车刀角度为κr=60°,κr′=10°,γ0=12°,α0=8°,λs=0°,rs=1mm。

(3)所用车床：CA6140：其主轴允许功率PE=5.9kW，最大转速nmax=230r/min，最大切削功率PE=5900W，切削效率η=0.8最大进给力为Fx=3530N，进给量范围fmax=1.59mm/r,fmin=00.82mm/r，转速范围为nmax=1200r/min,nmin=11.4r/min，切削深度：ap,max=7mm。

由切削用量手册：

优化模型(1)描述为(2):

由于粗车不必限制g4(z)，且实际余量为Δ=4mm，综合

按随机优化方法

已经满足：(4)～(10),7个条件;只判断(1)～(3)

则：问题转化为：

取NN=500000，并考虑了ap=2mm,ap=4mm情况，列出表1～3，分别为不同切削用量的优化结果。表明粗车，若ap=4mm,f=1.57mm/r,v=35.35m/min，在保证约束条件下，生产率是最高的。此时切削时间为tm=1.112min。

若假设一次精车完成，其他参数不变，此时fmin=0.16mm/r。列出计算的前10个随机优化结果。

显然是ap=5mm,f=0.16mm/r,v=147.74m/min，生产率是最高的。此时切削时间为tm=2.082min。

4 结论

本文从切削原理出发，应用随机优化原理，提出了在满足被加工材料、刀具和机床等限定条件情况下的，加工时间最小的较为合理的切削用量的优化计算选择方法。通过实例分析车削加工的问题。给出了相应的结果。这种方法为高效切削加工问题的实现提供条件。

参考文献

[1]陈日曜.金属切削原理(第2版)[M],北京:机械工业出版社,2002.

[2]艾兴,肖诗纲.切削用量简明手册(第3版)[M],北京:机械工业出版社,1994.

[3]赵健.金属切削用量最优化值数学模型的建立[J],机械制造,2008,46(531):55～56.

[4]任小平,刘战强,万熠等.切削用量优化模型的建立及应用[J],工具技术,2010,44(15):39-42.

优化求解篇6

线性规划模型广泛地用于解决和处理经济管理问题,但是这些工具在演算和使用上往往要耗费大量的时间和精力,使得急需的经济信息无法及时提供和灵敏反馈,制约了信息利用的及时性和深广度。通常的方法是利用计算机编程来代替繁重的计算,但需要一定的计算机编程知识和相关软件[1]。Microsoft Excel是一个广为普及的Office办公软件组件之一,运用其强大的公式、函数功能和数据处理功能等,能方便地求解线性规划问题,提高数据处理能力。

1 农机具优化配备模型的建立

1.1 准备工作

已知某兵团中心团场主要种植小麦、棉花、番茄和玉米等,其种植面积分别为小麦186.67hm2、棉花11266.67hm2、番茄2100hm2和玉米466.67hm2。根据该中心团场全年机械化作业的任务要求,以及主要种植作物的种植要求和特点,制定了全年机械化作业工艺流程,见表1所示。

1.2 设变量

变量包括机具配备量与作业机组台班数。设X1为JDT-654拖拉机台数,X2为东方红1002台数,X3为东方红1204台数,X4为JD-7810拖拉机台数,X5为喷雾器台数,……;X21为24行播种机台数,X22为JDT-654拖拉机番茄地化除台班数,X23为JDT-654拖拉机番茄地播种台班数,……;X74为JD-7810耕棉花地台班数。

1.3 建立约束方程组

约束方程有3类,即作业量、拖拉机配备和农具配备[2]。

1.3.1 作业量约束方程

式中k—作业序号,每项作业一个约束方程;

S(k)—与第k项作业有关的作业机组变量号;

A(k)—第k项作业的规定作业量;

X(ks)—第S(k)项作业机组的台班数变量;

W(ks)—第S(k)项作业机组的班生产率。

方程意义为:进行某项作业的各机组工作量之和应大于或等于该项作业规定作业量。作业量约束方程如下

1.3.2 拖拉机配备量约束方程

式中i—拖拉机变量号;

S(i)—i拖拉机作业机组变量号;

Xi—i拖拉机配备量;

Mi—第i拖拉机能够提供某项作业的最大班次数。

方程意义为:一个阶段内某型拖拉机的各项作业所需台班数之和,不得大于该型拖拉机能提供的最大台班数。在一个作业阶段内,拖拉机各项作业相互交叉,在不同阶段内相互独立,故配备量约束方程一般按阶段分机型编制。模型中拖拉机配备量约束方程为

1.3.3 农具配备量约束方程

式中j—农具变量号;

S(j)—第j型农具的作业机组变量号;

Xj—i拖拉机配备量;

Xs(j)—第k型使用第j种农具的作业机组台班数变量;

Zk—第k型作业期最大可作业班次数。

方程意义为:某项作业中s,同时使用某种农具的作业机组台班数不得大于该种农具可提供的最大台班数。模型中,农具配备量约束方程为

1.4 建立目标函数

目标函数应根据配备单位的要求来确定,一般为作业成本最低、功率最小、投资最少或耗油最低等。本文以作s业成本最低为目标函数,作业成本最低的目标函数为

2 用EXCEL求解农机具优化配备量

2.1 建立数学模型

在EXCEL中建立电子表格数学模型,如图1所示。模型中,单元格C156:BX156是输出单元格,C7:BX152为数据单元格。74个变量放在单元格C157:BX157中,它们是可变单元格,初始值设置为0。BY2是目标单元格(总作业成本),目标单元格中需输入函数“SUMPRODUCT(C3:BX3,C156:BX156)”。同样,BY7:BY152单元格中输入SUMPRODUCT函数求相应数据单元格与变量单元格的乘积,如BY7单元格中输入“=SUMPRODUCT(C7:BX7,C156:BX156)”。

2.2 求解

应用EXCEL提供的“规划求解”加载宏求解问题,如尚未加载则需先加载。选择“工具”菜单的“规划求解”选项,弹出“规划求解参数”对话框,依次选定符合模型要求的项目:

1)在“设置单元格”设置$BY$3(总成本),选取“最小值”;

2)在“可变单元格”设置$C$156:$BX$156(台变量);

3)单击“添加约束”对话框,在“单元格引用位置”选定“$BY$7:$BY$152”,“约束值”选择“$CA$7:$CA$152”,取相应不等式符号以后,单击“确定”;

4)“规划求解参数”对话框单击“选项”,选定“采用线性模型”和“假定非负”;

5)一切就绪后,单击“求解”,在“报告”中选择想要的报告,单击“确定”,完成运算(3)。

3 结论

1)经运算并进行圆整后,得到优化的农机具配备量为:JDT-654拖拉机128台,东方红1002拖拉机8台,东方红1204拖拉机16台,JD-7810拖拉机12台,喷雾器69台架,联合整地机35台架,精量播种机95台架,悬挂中耕机113台架,平地机15台架,打捆机1台,五铧犁12台架,四铧犁9台架,24行播种机1台架,总作业成本1147.2231万元。与现实系统相比,全年作业成本降低了10.31%,农机具配备量减少了21.39%。可见,经过优化可以减少机器系统的总投资,降低机器全年作业的总成本和单位面积作业成本,提高机器的利用率,从而得到较好的经济效益。

2)Excel拥有大量的用户群及规划求解的强大计算功能,可以轻松实现对有多个变量的线性规划问题的求解,省去了用线性规划专业软件计算对操作者的专业要求,克服了笔算的缺点,其操作方法的简单、方便、快捷,大大提高了计算的效率和准确性,能提供可靠的运算结果、敏感性和极限值分析报告,使之在农机管理和决策上发挥更大的作用。

摘要：数学中线性规划问题的求解一直是很繁琐的,功能强大的Excel软件提供了一种很好的求解方法。为此,以兵团某中心团场为例,建立了农业机器系统优化配备的线性规划模型,论述了利用Excel进行求解的过程。通过Excel对建立的模型进行求解,得到了该中心团场优化的农业机器系统配备量,优化的结果与现实系统相比,全年作业成本降低了10.31%,农业机器系统配备量减少了21.39%。这表明,利用Excel进行求解具有操作方法简单、方便和快捷的特点。

关键词：农业工程,农业机器系统优化配备,设计,Excel,线性规划

参考文献

[1]朱伟民.Excel求解经济数学模型新方法[J].昆明师范高等专科学校学报,2006,28(4):68-70.

[2]高焕文.高等农业机械化管理学[M].北京:中国农业出版社,1998:140-142.

复杂环境下的装配路径求解与优化篇7

良好的装配工艺规划可以提高效率和质量,缩短加工时间,并降低整个产品制造过程中的成本,因此,对装配路径规划进行研究十分必要[1]。

装配路径规划是指在有障碍物的工作环境下,寻找从起始位姿到终止位姿的一系列点或曲线,旨在避开空间障碍并提高装配效率[2]。装配路径的求解是路径规划环节的核心部分,路径的求解一方面是为了避障或满足作业需要,另一方面用于验证产品设计和装配序列规划是否合理[3]。

随着产品日趋复杂化、大型化、精密化,装配路径的求解也愈加复杂,国内外学者在装配路径求解方面取得了大量的研究成果:如VMap法[4]、A*搜索算法[5]、视点跟随法[6]、力反馈引导法[7]、人工势场法[8]、遗传算法[9]、RRT算法[10,11]等。这些算法求解的是二维环境条件下或较简单的三维环境下的装配路径,没有考虑产品在多障碍物环境下的路径规划问题。由于复杂环境下空间规模大、多约束、非线性,对路径的求解必须进行大量的碰撞检测,所以算法效率低,实际工程应用缺乏。

蚁群算法由Dorigo[12]提出,近年来已被广泛应用于路径规划问题、旅行商问题、生产调度问题等。蚁群算法具有群体智能等优势,在路径规划上具有很大的潜力,文献[13]提出了基于可视图法与蚁群算法的装配路径规划方法,该算法解决的是二维环境条件下简单的装配路径求解问题,至于在三维环境条件下的效果还有待验证;文献[14]将蚁群算法用于求解装配序列规划,文献[15]基于改进的蚁群算法和分布式局部导航对多机器人系统的路径进行规划,但只是将蚁群算法用于求解较简单环境下的路径规划。

本文基于蚁群算法对三维复杂环境下的装配路径规划进行了详细的分析,并给出了实例验证,最后对求解的初始路径进行了优化。

1装配路径规划问题描述

1.1路径规划概述

路径规划是指在有障碍物的工作环境中寻找一条从起点到终点、无碰撞地绕过所有障碍物的运动路径的过程。装配路径规划的总体思路如下:1从产品的CAD模型中抽象出三维规划空间;2应用路径搜索算法求解出一条避障且路径最短的初始路径;3优化初始路径,得到最终装配路径。对装配路径规划的描述如图1所示。

图1中环境空间是一个包含机械零部件、工装夹具、障碍物等信息的无限大的空间,而目标零件从起始点到目标点的路径是一个有限的空间,所以需要对目标零件确定一个有限的规划空间。在规划空间中分布着位置与形状已知的障碍物(图1中的1、2、3),在路径规划时,将障碍物尺寸根据目标零件的尺寸及运行安全性要求进行相应“膨化”处理,使“膨化”后的障碍物边界为安全区域,这样目标零件就可以看作一个质点。目标零件的路径path由目标零件从起始点S到目标点G绕过障碍物的有限个路径点组成,即

1.2规划空间建模

装配路径规划首先需要从产品的CAD模型中抽象出三维空间模型。其方法为:以规划空间左下角的顶点作为坐标原点O建立空间直角坐标系;采用栅格法对规划空间进行划分(图2):设该规划空间由 (Xmin,Xmax,Ymin,Ymax,Zmin,Zmax)确定,先沿X轴方向进行Nx等分,再沿Y轴方向进行Ny等分,最后沿Z轴方向进行Nz等分,则沿X、Y、Z轴方向的像素单位分别为a、b、c,其关系如下式所示:

如此整个规划空间就离散化为一个小长方体集合,集合中的每个元素对应着相应的序号Ri和坐标(Xi,Yi,Zi),而且序号与坐标一一对应,则可得关系式如下:

其中,坐标(Xi,Yi,Zi)取长方体栅格的质心处坐标;mod为取余运算,floor为返回小于或等于指定表达式的最大整数函数;ceil为返回大于或者等于指定表达式的最小整数函数。

图2中,Nx=5,Ny=7,Nz=4,第1个小长方体序号R1=1,位置坐标(X1,Y2,Z1)=(0.5a,0.5b,0.5c);第36个小长方体序号R36=36,位置坐标(X36,Y36,Z36)= (0.5a,0.5b,1.5c),…,其余以此类推。

2 基于蚁群算法的装配路径规划

2.1装配路径规划分析

装配路径规划要求找到一条从起点到终点的绕过有限个障碍物的最佳路径,为求解装配路径规划问题,首先需要构造规划空间,按1.2节的方法建立规划空间模型。建立规划空间时,像素a、b、c的值需根据障碍物的疏密程度及目标零件的尺寸等进行合理设置。像素小,环境信息描述得更精确,但会加大计算量;像素大,环境信息描述得不够精确,影响路径规划的效果。

在路径规划过程中,蚂蚁只能从当前栅格向其邻域栅格运动,如图3所示。当前栅格Ri的邻域neighbor(Ri)指的是以当前栅格为中心的立方体。图3中除Ri共26个元素,其中N1=NxNy。Ri的邻域为

在用蚁群算法求解路径规划时,由于下一个可以前往的节点可能在障碍物中,所以,当前栅格Ri 的可行邻域必须要去除落在障碍物中的栅格及禁忌表中已经过的栅格,即

其中,allow(Ri)表示Ri的可行邻域,tabu(m)表示第m只蚂蚁的禁忌表,obs表示障碍栅格集,“-”为集合的差集运算。

在装配路径规划过程中,为了能够尽快找到一条最优路径,需要对已装配的装配体进行简化处理,如用轴向包围盒包围复杂的形状等,并将障碍物尺寸按目标零件尺寸的一半及安全指标同向扩展,进行膨化处理,对环境中存在的障碍物,如果不满一个栅格按一个栅格处理。目标零件的位姿在装配运动过程中保持不变。

2.2路径规划计算步骤

基于蚁群算法的装配路径规划的具体计算步骤如下。

(1)初始化参数。

(2)将循环次数k←k+1。

(3)将蚂蚁数目m←m+1。

(4)创建路径表path、禁忌表tabu,将起点S添加到path、tabu中。

(5)依概率P(k)ij在可行邻域中选择一个元素t,将t添加到path、tabu中,更新路径长度,若蚂蚁到达终点或者无路可走,则执行步骤(6),否则循环执行步骤(5)。概率P(k)ij的计算公式如下:

其中,τij(t)为信息素的浓度,ηij(t)为启发式信息,α、β分别为τij(t)、ηij(t)的权重参数。为了能够尽快找到一条最优路径,ηij(t)取为当前栅格至目标点距离的倒数;allowk表示蚂蚁k下一步允许选择的可行邻域。

(6)若所有蚂蚁都遍历完,则更新信息量;否则跳转到步骤(3)。

(7)重复步骤(2)~步骤(6),直至达到最大循环次数K,则循环结束并输出结果。

3 基于二分法的装配路径插值优化方法

3.1二分法插值优化方法

由于蚁群算法在选择路径时会走过一些多余的栅格,使得由一系列离散点连接成的装配初始路径不够平滑,同时栅格像素的大小也会增加一些不必要的路径长度,为提高算法的可用性,本文对装配初始路径形成的离散点进行插值优化,尽量使规划的路径更加符合实际。

文献[16]提出一种基于分段线性拟合的装配路径优化技术,但该算法会产生路径冗余中间点。为此,本文提出二分法插值优化方法对规划出的装配初始路径进行优化。

二分法插值优化描述如图4所示,其中1为初始路径,2为优化后的路径。1中的点从P(1)→P(2)→P(3)→P(4),起始点为P(1),若连接点P(1)→P(2)的路径不与障碍物相碰,连接点P(1)→P(3)的路径与障碍物相碰,则查找范围为P(2)→P(3),再找线段P(2)→P(3)上的一点Q,使得连接点P(1)→Q的路径不与障碍物相碰。

3.2路径优化的计算流程

图5为二分法插值优化计算流程,其中P为初始路径中目标零件的位置,L为优化后路径的长度,path记录优化过程中目标零件的位置。

4装配路径规划实例

为验证算法求解装配路径规划问题的性能,本文用两个实例进行了验证,目标零件与障碍物采用轴向包围盒包围进行避障。

图6为减速器装配中零件螺钉的初始路径求解,图7为安装架装配中零件栏杆的初始路径求解,图中1为装配初始路径,2为优化后的路径。

由图6、图7可知,目标零件通过寻找障碍物外的可行栅格进行路径规划;由表1可知,利用蚁群算法能够快速求解出零件在复杂环境下的装配初始路径,整个计算过程用时0.30~0.55s,蚁群算法具有群体智能等优势,将其应用于路径规划中有很高的求解效率。

对比表1中初始与优化用时及路径长度可得,用二分法插值优化后的路径长度明显比初始路径要短,而且二分法插值优化用时极短,在1.1~1.5ms之间,显示出了很高的求解效率,优化后的路径是一条较为平滑的路径,更加符合装配实际。

5结论

(1)本文基于蚁群算法对三维复杂环境下的装配路径规划问题进行了详细的分析,规划出一条避开障碍物的装配初始路径,并对求解得到的初始路径提出采用二分法插值优化方法以缩短路径长度,仿真结果取得了良好的效果。

优化求解篇8

全局优化问题在科学计算、工程技术、经济管理等领域得到越来越广泛的关注和应用, 近些年来, 人们相继提出一些求解全局优化问题的算法, 填充函数法属于其中的确定型算法, 最早由Ge[1]提出, 用来求解无约束多极值函数的全局极小点。这种算法的关键是构造一个称为填充函数的辅助函数, 其基本思想是借助辅助函数, 从目标函数的当前局部极小点找到另一个目标函数值更小的局部极小点, 直至找到全局最小点为止。

Ge之后, 不少学者相继提出了不少性质良好的填充函数, 但基本上都是针对无约束优化问题的, 对于求解约束优化问题的填充函数虽有讨论, 如文献[2,3,4,5,6,7], 但都有各自不同程度的缺陷。本文在无强制性条件下给出了一类性质良好的求解带一般约束优化问题的单参数填充函数, 并讨论了其填充性质。

1 基本概念

考虑带约束全局优化问题 (P) : min f (x) , s.t.x∈S={x∈Rn|gi (x) ≤0, i∈Γ}, 其中f (x) , gi (x) , i∈Γ:Rn→R是连续可微函数, Γ={1, 2, …, m}是下标集。对上述问题假设如下。

假设1 问题 (P) 的不同局部极小点的个数可以是无限的, 但不同局部极小值个数是有限的。

假设2 用L (p) 表示问题 (P) 的局部极小点集合, 若x*是问题 (P) 的局部极小点, 则Lx*={x∈L (p) |f (x) =f (x*) }是一个有界闭集, 且问题 (P) 存在全局极小点。

注:在很多全局优化的实际问题中, f (x) 的强制性条件不一定满足, 因此这里对问题 (P) 的假设中没有考虑到目标函数f (x) 的强制性条件。下面针对问题 (P) 给出有约束优化问题的填充函数定义。

定义1[4] 函数p (x, x*, a) 称为f (x) 在局部极小点x*处的填充函数, 如果它满足:

(1) 在Rn空间中, x*是p (x, x*, a) 的严格局部极大点;

(2) 对x∈S1∩S且x≠x*或x∈Rn＼S有∇p (x, x*, a) ≠0, 这里S1={x∈Rn|f (x) ≥f (x*) };

(3) 如果x*不是全局极小点, 那么p (x, x*, a) 一定在S2={x∈S|f (x) <f (x*) }上有局部极小点。

以上定义的填充函数的意义为:对于有约束最优化问题, 首先要考虑的就是求出来的点是否可行。由条件 (2) 知, 要找的点一定在可行域内;其次, 对于全局最优化问题的填充函数法, 关心的是比当前局部极小点更好的那些点, 由条件 (2) 知, 要找的点一定不会再比当前局部极小点差的水平集上达到。若x*是局部极小点但不是全局极小点, 由定义中的条件 (1) 和条件 (3) , 则可以从x*的邻域中的任意一点出发, 用求无约束最优化问题的极小化方法极小化填充函数, 总能找到填充函数的局部极小点x*0, 由条件 (3) 知, f (x*0) <f (x*) , 再由条件 (2) , 对x∈S1∩S且x≠x*或x∈Rn＼S有∇p (x, x*, a) ≠0, 得知x*0∈S。

2 填充函数及其性质

针对问题 (P) , 设x*是当前局部极小点, 构造单参数填充函数如下。

1) p (x, x*, a) =-φ (1+‖x-x*‖3) +amin [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]。

其中a>0是参数, 函数φ (t) 满足:1) φ (0) =0, 2) φ′ (t) >0, 这样的函数有 $1 - e^{- t}, \arctan t, \frac{t}{1 + t}$ 等。

当参数a>0充分大时, 下面的几个定理表明p (x, x*, a) 是满足定义1的一类填充函数。

定理1 对任意a>0, x*是p (x, x*, a) 的严格局部极大点。

证明因为x*是f (x) 的局部极小点, 则存在它的一个邻域N (x*, δ) (δ>0) , 使得∀x∈N (x*, δ) ∩S, 有f (x) ≥f (x*) , gi (x) ≤0, i∈Γ。

下面分两种情况来证明对∀x∈N (x*, δ) , p (x, x*, a) <p (x*, x*, a) 成立。

(1) 当x∈N (x*, δ) ∩S, x≠x*时, 由于f (x) ≥f (x*) , 则有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0于是p (x, x*, a) =-φ (1+‖x-x*‖3) <-φ (1) =p (x*, x*, a) 。

(2) 当x∈N (x*, δ) ∩ (Rn＼S) 时, 则至少存在一个指标i0∈Γ, 使得gi0 (x) >0, 故min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0, 于是同 (1) 有结论成立。

综上, p (x, x*, a) <p (x*, x*, a) 对于∀x∈N (x*, δ) 都成立。因此, x*是p (x, x*, a) 的严格局部极大点。

定理2 若x*是f (x) 的局部极小点, 则p (x, x*, a) 在 (S∩S1) ＼{x*}或Rn＼S上有∇p (x, x*, a) ≠0成立。

证明易得对∀x∈S∩S1或Rn＼S都有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0, 此时, p (x, x*, a) =-φ (1+‖x-x*‖3) , 显然∇p (x, x*, a) ≠0。

定理3 若x*是f (x) 的局部极小点, 但不是f (x) 的全局极小点, 且cl (int S) =cl (S) , 则当a>0充分大时, 一定存在x*0∈S2, 使得x*0是p (x, x*, a) 的局部极小点。

证明因为x*是f (x) 的局部极小点但非全局极小点, 则存在f (x) 的另一个局部极小点x*1, 使得f (x*1) <f (x*) , gi (x*1) ≤0, i∈Γ。

由于f (x) , gi (x) , i∈Γ是连续函数, 且cl (int S) =cl (S) , 则一定存在x*2∈Rn, 使得f (x*2) <f (x*) , gi (x*2) <0, 故有

p (x*2, x*, a) =-φ (1+‖x*2-x*‖3) +amax {f (x*2) -f (x*) , gi (x*2) , i∈Γ}。

显然Lx*1⊂S, x*2∈int S∩S2。

另一方面, 对∀x∈∂S, 至少存在一个指标i1∈Γ, 使得gi1 (x) =0, 于是当x∈∂S时有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ]=0, 从而p (x, x*, a) =-φ (1+‖x-x*‖3) 。

所以, 当a>0充分大时, 对∀x∈∂S, 有p (x*2, x*, a) <p (x, x*, a) 。显然, S＼∂S是开集, 于是当a>0充分大时存在一点x*0∈S＼∂S使得

$\begin{array}{l} \min_{x \in S} p (x ‚ x^{*} ‚ a) = \min_{x \in S \partial S} p (x ‚ x^{*} ‚ a) = \\ p (x_{0}^{*} ‚ x^{*} ‚ a) \leq p (x_{2}^{*} ‚ x^{*} ‚ a) ‚ \end{array}$

故x*0∈int S, 且f (x*0) <f (x*) 。

定理4 若x*是f (x) 的全局极小点, 则对∀x∈S, x≠x*都有p (x, x*, a) <0。

证明由于x*是f (x) 的全局极小点, 则对所有的x∈S都有f (x) ≥f (x*) 成立。因此, 由定理1, 对∀x∈S, x≠x*有p (x, x*, a) <0成立。

定理5 任给x1, x2∈Rn, 若f (x1) ≥f (x*) , f (x2) ≥f (x*) , 则‖x2-x*‖>‖x1-x*‖当且仅当p (x2, x*, a) <p (x1, x*, a) 。

证明若f (x1) ≥f (x*) , f (x2) ≥f (x*) , 则min [0, max (f (xj) -f (x*) , gi (x) , i=∈Γ) ]=0, j=1, 2, 此时有p (xj, x*, a) =-φ (1+‖xj-x*‖3) , 显然有p (x2, x*, a) <p (x1, x*, a) , 反之亦然。

定理6 如果x1, x2∈Rn并且满足f (x1) ≥f (x*) ≥f (x2) 和‖x2-x*‖>‖x1-x*‖, 则p (x2, x*, a) <p (x1, x*, a) 。

证明由条件, p (x2, x*, a) =-φ (1+‖x2-x*‖3) +amax [f (x2) -f (x*) , gi (x2) , i∈Γ]。

且p (x1, x*, a) =-φ (1+‖x1-x*‖3) , 显然结论是成立的。

注:定理4-定理6说明目标函数当前的极小点x*被淘汰, 而新的填充函数的极小点将会被找到, 并且目标函数在这个点的函数值不比当前极小点处的函数值大。这也正是本文的填充函数所具有的良好性质之一。

3 算法和数值实验

3.1 算法

根据上述理论, 参考文献[7]给出下述算法。

(0) 初始步:选取初始点xk∈S;选取A>0作为可接受的终止参数;令a=1, k=1;

(1) 以xk为初始点, 应用局部下降算法求得问题 (P) 的一个局部极小点, 记作x*k;

(2) 选取初始点列{x $_{k + 1}^{i}$ :i∈Γ}, 使得对于某个δk>0有x $_{k + 1}^{i}$ ∈S＼N (x*k, δk) ;

(3) 令i=1;

(4) 若i≤m, 令x=x $_{k + 1}^{i}$ , 转步 (5) ;否则, 转步 (7) ;

(5) 若f (x) <f (x*k) , 且x∈S, 则以x为初始点, 应用已有局部下降算法求问题 (P) 的局部极小点x*k+1, 使得f (x*k+1) <f (x*k) , 令x*k=x*k+1, k=k+1, 转步 (2) ;否则, 转步 (6) ;

(6) 沿方向D1=-∇p (x, x*k, a) 或者 $D_{2} = - \frac{\nabla f (x)}{∥ \nabla f (x) ∥} - \frac{\nabla p (x, x_{k}^{*}, a)}{∥ \nabla p (x, x_{k}^{*}, a) ∥}$ , 找到一个新的点x, 使得p (x, x*, a) 能下降到一定程度。若在极小化过程中, x超出S的边界, 则令i=i+1, 转步 (4) , 否则, 转步 (5) ;

(7) 令a=2a。若a≤A, 转步 (3) ;否则, 算法终止, 视x*k为问题 (P) 的全局极小点。

注:下降方向D1、D2的合理性及优越性在文献[7]中有详细的说明, 不再赘述。

3.2 实验

通过两个算例的数值实验验证算法的可行性与有效性。算例都是在Matlab7.1.0运行环境中实现的。

算例1

$\min f (x) = 4 x_{1}^{2} - 4 x_{2}^{2} + 4 x_{2}^{4} - 2.1 x_{1}^{4} + \frac{1}{3} x_{1}^{6} - x_{1} x_{2}$

$s . t . x \in {(x_{1} ‚ x_{2}) | - 3 \leq x_{1} ‚ x_{2} \leq 3}$ 全局极小点x*= (0.090 1, 0.712 2) T, 全局极小值f (x*) =-1.133 1。

算例2

min f (x) = (x $_{1}^{6}$ -16x $_{1}^{5}$ +86x $_{1}^{4}$ -176x $_{1}^{3}$ +105x $_{1}^{2}$ ) /100+x $_{2}^{2}$ (x $_{2}^{2}$ -6x2+8) (x $_{2}^{2}$ -14x2+48) /100。

$s . t . x \in {(x_{1} ‚ x_{2}) | x_{1} + x_{2} \leq 10 ‚ x_{1} ‚ x_{2} \geq 0 ‚ 0 \leq x_{1} ‚ x_{2} \leq 8}$ 。

全局极小点x*= (2.174 0, 7.341 9) T, 全局极小值f (x*) =-9.123 1。

用k表示迭代次数, xk1表示第k次迭代初始点, x*k表示第k次迭代的局部最优解。迭代过程见表1。

参考文献

[1] Ge R P, Qin Y F. A class of filled functions for finding a global minimizer of a function of several variables.Journal of Optimization Theory and Applications, 1987;54 (2) :241—252

[2]Yang Yongjian, Shang Youlin.A filled function method for uncon-strained global optimization.Shanghai:Science College, Shanghai Univevs:ty, 2006;503—504

[3] Zhang L S, Kong Chi, Duan N G, et al.A new filled function method for global optimization.Global Optim, 2004;28:17—43

[4] Wang Weixiang, Shang Youlin, Zhang Liansheng. A filled function method with one parameter for box constrained global optimization.Applied Mathematics and Computation, 2007;194:54—66

[5] Wang Changyu, Li Duan. Unified theory of augmented Lagrangian methods for constrain-ed global optimization.J Glob Optim, 2009;44:433—458

[6] Wang Weixiang, Shang Youlin, Zhang Liansheng. A filled function method with one parameter for constrained global optim-ization.Journal of Engineering Mathemati-cs, 2008;25 (5) :795—803

优化求解篇9

关键词：投资组合模型,非线性规划,多目标优化,进化算法

引言

投资组合就是如何配置各种有价证券的头寸来最好地符合投资者对风险和收益的权衡。Markowitz利用证劵收益的方差度量风险提出了M-V模型。该模型要求效用函数是二次的或者收益满足正态分布, 故在实际应用中受到较多限制, 若问题规模较大, 则需要解决一个带有稠密协方差矩阵的二次规划问题, 这给问题的求解带来高度的复杂性。

继Markowitz之后, 大量的模型及求解算法被提出[1]。2008年, Dellino等[2]基于遗传算法设计出一种动态目标聚集算法求解投资组合优化模型;Kawakami等[3]以信息率为目标函数建立了动态资产投资组合模型, 并利用遗传算法求解。

综上, 大量的投资组合优化模型及算法被提出。然而, 在实践中, 投资者频繁地进行交易, 交易费对收益的影响也是投资者不容忽视的问题。已有的求解方法主要是固定风险或效益使效益最大或风险最小, 需经过多次迭代才能获得不同要求下的最优投资组合。本文主要针对含交易费的投资组合模型, 从智能优化角度设计求解算法直接对模型求解。

一、投资组合模型

假设有n种资产可供投资, 现用数额为M的资金作一个时期的投资, 投资过程中存在一定的风险, 总体风险用投资项目中最大的一个风险度量。假设购买资产时要付一定的交易费, 当项目i投资额不超过给定值时, 交易费按投资额计算, 另外, 假定存入银行存款利率为定值。建立如下多目标投资组合模型 (POM) [4]。

为资产i交易费, x= (x1, x2, ……, xn) T∈Rn为投资权重向量, μi、pi、ri、qi分别表资产i的投资定额、交易率、平均收益率和风险损失率。

二、求解算法

K.Deb提出了NSGAII解决多目标优化问题, 该算法已广泛应用于求解各类多目标数值优化问题, 但其设计时只是针对无约束的多目标优化模型。在此, 基于NSGAII给予改进使其适合该模型的求解, 获得一种提高的多目标约束进化算法 (INSGAII) 用于模型POM的求解。

设最大迭代数为N, 当前代数为k, 算法步骤描述为:

Step1:随机产生初始可行个体群A (|A|=P) 及外部集S (S=Φ) , 置初始代数k=1;

Step2:若k≤N, 则输出结果, 算法结束;否则, 进入Step3;

Step3:群体A经由Pareto非控关系获Pareto个体集S, 若|S|≥S0, 则利用浓度抑制删去冗余的|S|-S0个个体;否则, 转入Step4。并获可行群B及非可行群C;

Step4:可行群B与非可行群C经交叉, 获群体D;

Step5:群体D经突变获群体E, 并对E中非可行个体修正, 获群体F;

Step6:置k←k+1, A←F, 转入Step2。

三、数值仿真

根据初始样本空间中投资项目数定义染色体 (个体) 的长度, 染色体上每一基因代表一个项目, 基因的数值表示投资比例, 一个个体x= (x1, x2, ……, xn) ∈Rn代表一种投资组合。采用数术交叉和多项式变异策略, 对不可行的个体进行修正使其可行[5]。

现设有5种投资项目供选择, 总投资金额M设为1, 各自的交易率、收益率等信息详见表1, 其中S1为无风险资产。

线性规划[4] (LP) 、GA和INSGAII应用于算例求解分析, 两种进化算法的最大迭代数N=200, 交叉概率为0.8, 变异概率为1/n, 群体规模P=100, GA利用权重系数法将模型转化为单目标求解。

由于交易费是分段函数, 已有的LP方法无法直接求解, 在此首先不考虑交易费为分段函数, 直接设为线性函数Ti= (xiM) pi获得如图1和表2比较结果。若交易费为分段函数, 获图2比较结果, 此时LP无法获得Pareto面, 故未画出。

图1中“-”为利用Matlab软件, 在风险固定的情况下算法LP所获风险-收益Pareto面, 虽然能得到较好的收益率, 但由于该方法通过固定风险使收益最大, 故需经过不同的固定风险才能获得不同的最大收益, 算法需经过多次运算。而GA在风险较小时能获得较好的收益, 当风险稍大时, 对收益率的收索较困难。INSGAII通过一次循环即可得出多组风险——收益Pareto面, 而且由图获知收索效果较好, 速度快捷。表2为各算法在获相同的风险——收益点对下所需的平均时间, 可见LP及GA所需的时间较长。特别, 在交易函数为分段函数时LP无法获风险-收益Pareto面 (图2) , 故未能描绘, 而与GA比较易知, GA获点较少, 且收敛性较差, 而INS-GAII获得pareto面较均匀, 效果较好。

四、结论及进一步研究

在交易费为线性函数时, INSGAII较其他两算法获较均匀的pareto面;在交易费为分段函数时, 算法LP便无法获得风险-收益点对, 而GA所获效果劣于INSGAII。对于INSGA在资产数量较大的情况的性能有待于进一步研究。

参考文献

[1]H.Konno, H.Yamazaki.Mean-absolute deviation portfolio optimization model and its application to Tokyo stock marcher[J].Management Science.1991, 37 (5) :519-531.

[2]G.Dellino, M.Fedele, C..Meloni.DOAM for Evolutionary Portfolio Optimization:a computational study[J].New economics pa-per, 2008:253-266.

[3]A.Kawakami, Y.Orito, M.Inoguchi.Dynamic Asset Portfolio Optimization by Using Genetic Algorithm[C].IEEE.Transactions onElectronics, Information and Systems, 2009, 129 (7) :1348-1355.

[4]赵静, 但琦.数学建模与数学实验[M].北京:高等教育出版社, 2008.

【优化求解】推荐阅读：

线性优化求解09-07

求解约束最优化问题KKT系统的BFGS方法07-08

混合求解07-28

函数求解09-30

联合求解10-23

约束求解10-24

规划求解法10-17

求解新方法07-24

求解视角论文09-14

Excel规划求解06-04