高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

基于降维的全局优化近似解法

    作者简介: 陈丹丹(1994-),女,安徽芜湖人,硕士生,研究方向:最优化。E-mail:18818262015@163.com;
    通讯作者: 王薇, wangwei@ecust.edu.cn
  • 中图分类号: O221.2

Approximate Solution of Global Optimization Problem Based on Dimensionality Reduction

    Corresponding author: Wei WANG, wangwei@ecust.edu.cn ;
  • CLC number: O221.2

  • 摘要: 将降维应用到全局优化问题的求解中,提出了一个基于降维的全局优化近似算法,用以求解带箱约束的非线性全局优化问题。首先在区间[0,π]上构造一个新的降维公式,给出基于该降维变换曲线的α-致密度,再从降维曲线长度对该近似算法的计算量进行估计并给予证明,给出理论算法,最后给出了数值实验结果以说明算法的有效性。
  • 图 1  算例1目标函数值随着迭代次数的变化情况

    Figure 1.  The value change of Test1’s objective function with number of iterations

    表 1  函数的数值实验结果

    Table 1.  Numerical results of the function

    Example${\theta ^ * }$minGlobal min
    11.883 780.000 014 120
    21.572 00–0.199 992 11–0.2
    30.792 070.004 134 190
    41.537 41–0.591 313 44–0.6
    50.994 46–0.988 568 68–1
    60.947 43–0.965 497 70–1
    下载: 导出CSV
  • [1] BUTZ R. Space filling curves and mathematical programming, information and control[J]. Information and control, 1968, 12: 314-330. doi: 10.1016/S0019-9958(68)90367-7
    [2] CHERRUAULT Y. A new method for global optimization(Alienor)[J]. Kybernetes, 1990, 19: 19-32. doi: 10.1108/eb005845
    [3] ZIADI A, CHERRUAULT Y. Generation of α-dense curves in a cube of R n[J]. Kynernetes, 1998, 27(4): 416-425. doi: 10.1108/EUM0000000004524
    [4] CHERRUAULT Y. Optimization and optimal control for life sciences[J]. Kynernetes, 1998, 27(9): 1012-1019. doi: 10.1108/03684929810246035
    [5] CHERRUAULT Y. α-Dense curves and global optimization[J]. Kynernetes, 2003, 32(3): 369-375. doi: 10.1108/03684920310458593
    [6] GE R P. A filled function method for finding a global minimizer of a function of several variables[J]. Mathematical Programming, 1990, 46(1): 191-204.
    [7] GERMN S, HWANG C R. Diffusions for global optimization[J]. Stochastic Processes and Their Applications, 2006, 21(1): 57-58.
    [8] 王薇, 袁琪, 李民, 等. 基于降维的填充函数方法[J]. 华东理工大学学报(自然科学版), 2016, 42(6): 877-880.
    [9] 曾婉. 辅助函数型全局最优化算法[D]. 上海: 上海大学, 2013.
    [10] BALIRA O, CHERRUAULT Y, BENNEOUALA T. A global optimization method for a large number of variables(variant of a lienor method)[J]. Kynernetes, 2005, 34(7/8): 1070-1083. doi: 10.1108/03684920510605885
    [11] MORA G, CHERRUAULT Y. On the minimal length curve that densifies the square[J]. Kynernetes, 1999, 28(9): 1054-1064. doi: 10.1108/03684929910300277
    [12] CHERRUAULT Y. A new reducing transformation for global optimization[J]. Kynernetes, 2005, 34(7/8): 1084-1089. doi: 10.1108/03684920510605894
    [13] MORA G, CHERRUAULT Y, BENABIDALLAH A, et al. Approximating multiple integrals via α-dense curves[J]. Kynernetes, 2002, 31(2): 292-304. doi: 10.1108/03684920210419010
    [14] ZIADI A, CHERRUAULT Y, MORA G. The existence of α-dense curves with minimal length in a metric space[J]. Kynernetes, 2000, 29(2): 219-230. doi: 10.1108/03684920010312803
    [15] LI H, JIAO Y C, WANG Y P. Integrating the simplified quadratic interpolation into the genetic algorithm for solving constrained optimization problems[C] // Proc of Int Conf on Computational Intelligence and Security. Germany: Springer, 2005, 1: 247 – 254.
    [16] ZIADI A, KHELLADI S, CHERRUAULT Y. The Alienor method coupled to the Brent algorithm[J]. Kynernetes, 2005, 34(7/8): 1059-1069. doi: 10.1108/03684920510605876
    [17] YAROSLAV D, SERGEYEV, ROMAN G, et al. Introduction to Global Optimization Exploiting Space-Filling Curves[M]. New York: Springer, 2013: 96-108.
  • [1] 曹移林余炜 . 平行三阶段流水作业问题的近似算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180206001
    [2] 于中宝邵方明 . 并行系统中排列图的可靠性近似算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180531001
    [3] 王瑞许妍霞宋兴福吴非克于建国 . 降膜结晶分离提纯对二甲苯. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180424003
    [4] 陈兰萍牛玉刚 . 基于多代理的微电网分区分布式最优潮流分析. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190523004
    [5] 王森王永香李金霞 . 三维石墨烯宏观体的制备及超级电容性能. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180530001
    [6] 金志超高大启朱昌明王喆 . 基于权重的多视角全局和局部结构风险最小化分类器. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180704001
    [7] 黄克骄贺理珀宋兴福于建国 . 响应曲面法优化2-(4-羟基苯氧基)丙酸甲酯结晶工艺. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180425001
    [8] 王学武闵永顾幸生 . 基于密度聚类的多目标粒子群优化算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180321005
    [9] 马恒达袁伟娜徐睿 . 一种组稀疏信道估计中的信号重构优化方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180409004
    [10] 陈鹏罗娜 . 基于竞争机制差分进化算法的无分流换热网络优化. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181015004
    [11] 孙京云张琴张雷达赵伟杨辉杭海峰王泽建庄英萍 . 搅拌桨组合与葡萄糖流加工艺相结合的凝胶多糖发酵工艺优化. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180508001
  • 加载中
图(1)表(1)
计量
  • 文章访问数:  2632
  • HTML全文浏览量:  1152
  • PDF下载量:  1
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-07-20
  • 网络出版日期:  2019-10-12

基于降维的全局优化近似解法

    作者简介:陈丹丹(1994-),女,安徽芜湖人,硕士生,研究方向:最优化。E-mail:18818262015@163.com
    通讯作者: 王薇, wangwei@ecust.edu.cn
  • 1. 华东理工大学数学系,上海 200237
  • 2. 复旦大学管理学院,上海 200433

摘要: 将降维应用到全局优化问题的求解中,提出了一个基于降维的全局优化近似算法,用以求解带箱约束的非线性全局优化问题。首先在区间[0,π]上构造一个新的降维公式,给出基于该降维变换曲线的α-致密度,再从降维曲线长度对该近似算法的计算量进行估计并给予证明,给出理论算法,最后给出了数值实验结果以说明算法的有效性。

English Abstract

  • 考虑带箱约束的非线性全局优化问题

    其中$f:{\mathbb{R}^n} \to \mathbb{R}$$X = \prod\limits_{i = 1}^n {\left[ {{a_i},{b_i}} \right] \subseteq {\mathbb{R}^n}} $。通过空间填充曲线是求解这类问题的有效方法。

    空间填充曲线是填充在整个多维空间的一维曲线,因此是降低空间维度的方法。该方法通过降维将原n维空间的优化问题转化为一维函数的优化问题,从而通过求解一元问题得到原问题的近似最优解。近似解的近似程度,取决于该曲线填充n维空间的致密度。空间填充函数曲线有很多种形式,根据不同的排列规则,有结合分形思想的连续但处处不可导的希尔伯特曲线[1],也有基于三角函数的$\alpha $-致密曲线[2],在此主要研究文献[3-5]中提出的一种基于三角函数的空间填充曲线。

    对于求解多维多极值的全局优化问题,由于全局最优性条件的欠缺,目前尚无有效方法判定全局最优解。在数值计算方面亦有困难,例如确定性算法中的填充函数方法可能会导致一些假的稳定点或者很难找到更低的盆谷[6];结合维纳过程的随机优化算法求解带维纳过程的随机微分方程也有较高的难度[7]。相比之下,求解一维问题的全局最优解比多维问题要容易,因而将降维这种古典的方法应用到优化问题求解中不失为一种新的尝试。近年来也有一些关于降维的应用,例如文献[8]将降维与填充函数相结合求解全局优化问题,文献[9]将降维与填充函数相结合求解带有球形约束的全局优化问题,文献[10-11]对于降维参数也进行了研究。基于前人的研究,可以考虑将降维方法与随机型算法相结合来求解非线性全局优化问题。虽然有非常多的方法求解一维优化问题,但是由于降维后的一元函数波动比较大,所以选择用遗传算法求解降维后的辅助问题。

    本文首先提出了一个基于三角函数的新的降维变换,将带箱式约束的n维优化问题转化为区间[0,$\pi $]上的一维优化问题,并且讨论了一些有意义的性质。在此基础上提出了基于降维的全局优化近似算法,最后对该算法进行了数值实验以说明算法的有效性。

    • 对问题(1)提出如下假设:

      假设1 $f(x)$X上Lipschitz连续可微,Lipschitz常数记为$l_1$

      假设2 $f(x)$X上仅有有限个极小值。

      对于任意的超立方体$X = \mathop \prod \limits_{i = 1}^n \left[ {{a_i},{b_i}} \right]$${a_i} < {b_i},i = 1,$$2,\cdots,n $,取m为足够大的正偶数,构造以下降维变换:

      其中,${h_i}(\theta ) = \dfrac{1}{2}({b_i} - {a_i})(1 - \cos ({m^{i - 1}}\theta )) + {a_i},i = 1,2, \cdot \cdot \cdot ,n$

      变换函数$h(\theta)$ 具有下面的性质。

      定理1 由式(1)定义的$h = ({h_1}, \cdot \cdot \cdot ,{h_n}):\left[ {0,\pi } \right] \to $$\prod\limits_{i = 1}^n {\left[ {{a_i},{b_i}} \right]}$是Lipschitz连续的。

      证明$M = \max \left\{ {{b_i} - {a_i}:i = 1,2, \cdot \cdot \cdot ,n} \right\}$,对于任意的$\theta ',\theta '' \in \left[ {0,\pi } \right]$,有

      所以函数$h(\theta )$是Lipschitz连续的,且Lipschitz常数为${l_2} = \dfrac{M}{2}{\left(\dfrac{{1 - {m^{2n}}}}{{1 - {m^2}}}\right)^{1/2}}$。证毕。

      ${l_1}$是原始函数$f(x)$的Lipschitz常数,根据函数$f(x)$和降维变换函数$h(\theta )$的Lipschitz连续性得,它们的复合函数$f({h_1}(\theta ),{h_2}(\theta ), \cdot \cdot \cdot ,{h_n}(\theta ))$也是Lipschitz连续的,并且Lipschitz常数为${l_1}{l_2}$

      利用降维变换${x_i} = {h_i}(\theta ),i = 1, \cdot \cdot \cdot ,n,$n个变量${x_i}$均表示为单变量$\theta $的形式,有:

      这样求解原n维优化问题转化为求解一维优化问题:

      记集合$S \!= \!\{ ({x_1},{x_2}, \cdot \cdot \cdot ,{x_n})\left| {{x_i} = {h_i}(\theta )} \right.,i = 1, \cdot \cdot \cdot ,n,\;0 \le $$ \theta \leqslant\pi ,\;n \ge 2 \}$,显然$S \subseteq X$

      类似于文献[12],给出以下定义。

      定义1 假设有度量空间$(E,d)$,令X是E的子集。给定一个正数$\alpha $,于是连续曲线$h:[0,\pi ] \to E$被称为$\alpha $-致密的,当且仅当:

      (1) $h\;[0,\pi ] \subset X$

      (2) 对于任意的$x \in X$,存在$\theta \in \left[ {0,\pi } \right]$,使得$d(x,h(\theta )) \leqslant \alpha $,其中d${\mathbb{R}^n}$中的欧氏距离。

      如果曲线h$\alpha $-致密的,则称曲线h的致密度为$\alpha $$\alpha $-致密的曲线用${h_\alpha }$表示,其长度记为$L({h_\alpha })$

      定理2 超立方体$X = \prod\limits_{i = 1}^n {\left[ {{a_i},{b_i}} \right]} $中用式(1)描述的降维曲线$h(\theta )$$\alpha $-致密的,并且致密度$\alpha =\dfrac{M}{m}\sqrt {n - 1} $

      证明 由于余弦三角函数具有周期性,曲线${h_2}(\theta )$可以将区间$\left[ {{a_2},{b_2}} \right]$上的点遍历m次,曲线${h_3}(\theta )$可以将区间$\left[ {{a_3},{b_3}} \right]$上的点遍历${m^2}$次,依此类推,曲线${h_n}(\theta )$可以将$\left[ {{a_n},{b_n}} \right]$上的点遍历${m^{n - 1}}$次。将前$n - 1$维空间的每一维分别等分为$m$段,可以得到${m^{n - 1}}$X的超子立方体。它们的一维边长为$\dfrac{{{b_1} - {a_1}}}{m}$,二维边长为$\dfrac{{{b_2} - {a_2}}}{m}$,依此类推,第$n - 1$维边长为$\dfrac{{{b_{n - 1}} - {a_{n - 1}}}}{m}$。由于第$n$维没有划分,边长为${b_n} - {a_n}$统一表示为:$\dfrac{{{b_1} - {a_1}}}{m} \times \dfrac{{{b_2} - {a_2}}}{m} \times \cdot \cdot \cdot \dfrac{{{b_{n - 1}} - {a_{n - 1}}}}{m} \times ({b_n} - {a_n})$,即每一条穿越子立方体的曲线遍历第n维坐标上的区间$\left[ {{a_n},{b_n}} \right]$。因此,给定$X = \mathop \prod \limits_{i = 1}^n \left[ {{a_i},{b_i}} \right]$上的任意一点${(x_i^{(0)})_{i = 1, \cdots ,n}}$,每一条穿越子立方体的曲线与第$n$维平面${x_n} = x_n^{(0)}$相交,同时可以由$x_n^{(0)}=h_n^{(0)}(\theta ) = \dfrac{1}{2}({b_n} - {a_n})(1 - \cos {m^{n - 1}}\theta ) + {a_n}$来确定$\theta $,即${({x_i})_{i = 1, \cdot \cdot \cdot ,n}}$${({h_i}(\theta ))_{i = 1, \cdot \cdot \cdot ,n}}$的第$n$维分量相同,从而只需考虑两点在前$(n - 1)$维空间${R^{n - 1}}$中投影的距离。已知${R^{n - 1}}$中每一维宽度为$\dfrac{{{b_i} - {a_i}}}{m}$,由度量距离公式,${\rm{d}}(x,h(\theta )) \leqslant {\left(\sum\limits_{i = 1}^{n - 1} {{{\left(\dfrac{{{b_i} - {a_i}}}{m}\right)}^2}} \right)^{1/2}} \leqslant {\left(\sum\limits_{i = 1}^{n - 1} {{{\left(\dfrac{M}{m}\right)}^2}} \right)^{1/2}} = $$ \dfrac{M}{m}\sqrt {n - 1} =\alpha $。证毕。

      推论1 如果降维变换$h(\theta ) = ({h_1}(\theta ),{h_2}(\theta ), \cdot \cdot \cdot ,{h_n}(\theta ))$$\alpha $-致密的,那么${f^ * }(\theta )$在[0,$\pi $]上的全局极小值是问题(1)的近似全局极小值。

      证明${x^ + } = (x_1^ + , \cdot \cdot \cdot ,x_n^ + )$为函数$f({x_1}, \cdot \cdot \cdot ,{x_n})$的全局极小点,${\theta ^ * }$${f^ * }(\theta )$的全局极小点,即$f({x^ + }) = \mathop {\min }\limits_{x \in X} f(x)$${f^ * }({\theta ^ * }) = \mathop {\min }\limits_{\theta \in [0,\pi ]} {f^ * }(\theta )$

      由式(2)和定理2可知,存在$\bar \theta $使得点$({\bar x_1},...,{\bar x_n})$逼近点${x^ + }$,其中${\bar x_i} = {h_i}(\bar \theta ),i = 1,...,n$,即$d({x^ + },h(\bar \theta )) \leqslant \alpha $。由函数f的Lipschitz连续性可知:存在$\varepsilon > 0$,使得$0 \leqslant f(\bar x) - f({x^{\rm{ + }}}) \leqslant \varepsilon $。显然${f^ * }({\theta ^ * }) \leqslant {f^ * }(\bar \theta ) = f(\bar x)$,从而$0 \leqslant {f^ * }({\theta ^ * }) - f({x^{\rm{ + }}}) \leqslant f(\bar x) - f({x^{\rm{ + }}}) \leqslant \varepsilon $,所以${f^ * }(\theta )$的全局极小值是原问题$f(x)$的全局极小值的近似。证毕。

      对降维曲线的长度$L({h_\alpha })$有如下定理。

      定理3 令超立方体$X = \prod\limits_{i = 1}^n {[{a_i},{b_i}]} $,如果存在致密度为$\alpha '\sqrt {n - 1} $的曲线${h_\alpha }$,则:

      其中$S' = {(\alpha ')^{n - 1}}L({h_\alpha })$$\alpha '=\dfrac{M}{m}$$c = {b_n} - {a_n}$为第n维区间长度。

      证明 对于$\alpha '=\dfrac{M}{m}$,其中$m$为正偶数,考虑曲线$h:\left[ {0,\pi } \right] \to X$,那么

      ${m^{n - 1}}\theta = u$,则$\theta {\rm{ = }}\dfrac{u}{{{m^{n - 1}}}},\;{\rm{d}}\theta = \dfrac{{{\rm{d}}u}}{{{m^{n - 1}}}}$

      其中${S_1}^{\left( i \right)} = \int_{\pi (i - 1)}^{\pi i} ({{({b_1} - {a_1})}^2}{{\sin }^2}\dfrac{u}{{{m^{n - 1}}}} + {{({b_2} - {a_2})}^2}{m^2}$${{\sin }^2}\!\dfrac{u}{{{m^{n - 2}}}}\! +\! \cdot \cdot \cdot \!+\! {{(\!{b_n} \!-\! {a_n}\!)}^2}{m^{2(n - 1)}}{{\sin }^2}u)^{1/2} {\rm{d}}u\,,$$i \!=\!\! 1,2, \cdot \cdot \cdot ,$${m^{n - 1}} $,存在$1 \leqslant p,$$q \leqslant {m^{n - 1}}$,使得${S_1}^{(p)}={S_1}^{(\min )} =\min\Big\{ {S_1}^{(i)}: i = $$ 1,2, \cdot \cdot \cdot ,{m^{n - 1}} \Big\}$${S_1}^{(q)}\!=\!{S_1}^{(\max )} \!=\! \max \left\{ {{S_1}^{(i)}:i \!=\! 1,2, \cdot \cdot \cdot ,{m^{n - 1}}} \right\}$,并且

      $u - (p - 1)\pi = v$,则:

      $u - (q - 1)\pi = w$,则:

      联立(4),(5),(6)式得到:

      取极限$m \to \infty $,结合一致收敛性得:

      对于给定的箱约束,第n维坐标区间长度$({b_n} - {a_n})$为常量,由

      得到${\lim\limits_{m \to \infty }}S'={M^{n - 1}}c$,证毕。

      由定理3得,当$m \gg 1$时,降维曲线的长度为$L({h_\alpha }) \approx c{m^{n - 1}}=c{(\dfrac{M}{{\alpha '}})^{n - 1}}$。可以看到,当m减小时,降维曲线的长度减小,但致密度增大;当m增大时,致密度变小,但降维曲线长度增大,计算量也随之增大。由定理2可知,致密度越小近似效果越好,所以m的适当取值相当重要。在实际计算中,既不能让m太大使得计算量非常大,也不能使得m小到无法满足致密度,即需要在保证$\alpha $-致密度的前提下选取适当的m值。

      由函数$f(x)$的Lipschitz连续性和$h(\theta )$$\alpha $-致密性可知:当${\rm{d}}((x_1^ + , \cdot \cdot \cdot ,x_n^ + ,h(\bar \theta )) \leqslant \alpha $时,为使$f(\bar x) - f({x^{\rm{ + }}}) $$\leqslant {l_1}\alpha \leqslant \varepsilon $,只需$\alpha =\dfrac{M}{m}\sqrt {n - 1} \leqslant \dfrac{\varepsilon }{{{l_1}}}$即可,进而得到$m \geqslant \dfrac{{M{l_1}\sqrt {n - 1} }}{\varepsilon }$

    • 考虑降维之后的一维全局优化问题:$\mathop {\min }\limits_{\theta \in D} {f^ * }(\theta )$D=[0,$\pi $]。可得,降维函数的最小正周期为$\dfrac{{2\pi }}{{{m^{i - 1}}}}\left( {m > 0,i = 1, \cdot \cdot \cdot ,n} \right)$的最小公倍数,这会导致降维模拟出的函数曲线呈现较强波动,因此本节采用对函数性态没有要求的遗传算法求解一维问题(式3)。

    • 采用实数编码,$\theta $作为一个个体,表示问题的解。适应度函数取函数本身,即$fit(\theta ) = {f^ * }(\theta )$。假设选出的两个父代为${\theta _1},{\theta _2}$,交叉子代[15]

      变异概率${p_m}$用于判断个体是否需要变异,选定一个个体,产生一个$(0,1)$之间的随机数,在随机数小于变异概率${p_m}$时,变异子代[15]

      其中$\lambda \sim N(0,1)$$\Delta \theta \sim N(0,{\sigma ^2})$

    • 步骤1 初始化参数:令$\varepsilon $=0.1,${\varepsilon _1}={10^{ - 4}}$$\sigma $=${10^{ - 4}}$,遗传种群规模为N,杂交概率为${p_c}$,变异概率为${p_m}$,遗传代数为t,遗传最大代数为T

      步骤2 计算整数$[M{l_1}\sqrt {n - 1} /\varepsilon ]$,若值为偶数,则令$m = [M{l_1}\sqrt {n - 1} /\varepsilon ]$;若值为奇数,则令$m = [M{l_1}\sqrt {n - 1} /$$\varepsilon ] - 1 $

      步骤3m值代入降维变换(2),使得多维函数$f({x_1},{x_2}, \cdot \cdot \cdot ,{x_n})$转化为一维函数${f^ * }(\theta )$

      步骤4t=0;

      步骤5 在区间$\left[ {0,\pi } \right]$内随机产生种群$P(t) = \{ \theta _1^t,$$\theta _2^t, \cdot \cdot \cdot ,\theta _N^t \}$,转步骤6;

      步骤6P(t)中所有个体作为产生子代的父母,用交叉算子${p_c}$作用于每一个$\theta _i^t$(表示第t代中第i个个体)产生交叉子代$\theta '$,再用变异算子${p_m}$作用于$\theta '$产生变异子代$\theta ''$,令父代及其交叉子代、变异子代构成集合${{ O}^t}$,转步骤7;

      步骤7 计算集合${{ O}^t}$中每个个体的适应度函数值,转步骤8;

      步骤8 选择,对集合${{ O}^t}$中个体对应的${f^ * }$进行从小到大排序,取前$N - {N_1}$的个体,再随机产生${N_1}$个个体,把这两部分个体合起来作为下一代种群P(t+1),转步骤9;

      步骤9 t=t+1,若t<T,转步骤5;若t=T,停止。同时输出精英库中的$\theta _{{\rm{best}}}^t$为一维全局极小值点,相应的${f^ * }(\theta _{{\rm{best}}}^t)$为近似的全局极小值。

      在本算法中,利用降维变换将原目标函数$f(x)$变换为${f^ * }(\theta )$,进而将原问题转化为一维全局优化问题,用遗传算法求解问题(3)的全局最优解。

    • 本文使用软件MATLAB R2017b对以上算法进行了数值模拟,并给出了实例的数值实验和结果,并将得到的结果与原函数的精确最优解进行对比,如表1所示,其中${\theta ^ * }$${f^ * }(\theta )$最优点,min为${f^ * }(\theta )$最优值,Global min为标准算例最优值。

      Example${\theta ^ * }$minGlobal min
      11.883 780.000 014 120
      21.572 00–0.199 992 11–0.2
      30.792 070.004 134 190
      41.537 41–0.591 313 44–0.6
      50.994 46–0.988 568 68–1
      60.947 43–0.965 497 70–1

      表 1  函数的数值实验结果

      Table 1.  Numerical results of the function

      算例1[13]$\min 100{({x_2} - x_1^2)^2} + {(1 - {x_1})^2}, - 5 \leqslant {x_i} \leqslant 5\;,$$i = 1\;,\;2$

      对算例1执行2.2节算法,首先将其降维成一维函数,然后对一维函数执行遗传算法,种群规模取500,迭代600代,取交叉概率${p_c}$=0.8,变异概率${p_m}$=0.3,求得最小值点${\theta ^ * }$= 1.883 775 176 539 976,全局最小值$f({\theta ^ * })$ =1.411 790 146 315 494×10−5。如图1所示,每一代精英个体的目标函数值随着迭代次数的增加逐渐较小,并最终收敛到0,即理论上的最优解。

      图  1  算例1目标函数值随着迭代次数的变化情况

      Figure 1.  The value change of Test1’s objective function with number of iterations

      算例2[14]:min$G({x_1},{x_2}) = x_1^2 + x_2^2 - \dfrac{1}{{10}}(\cos (5\pi {x_1}) +$$ \cos (5\pi {x_2})), - 1 \leqslant {x_i} \leqslant 1,i = 1,2 $

      算例3[16]:min$100{({x_2} - x_1^2)^2} + {(1 - x_1^2)^2} + 90{({x_4} - x_3^2)^2} + $$ {(1 - {x_3})^2} + 10.1\;[{({x_2} - 1)^2} +{({x_4} - 1)^2}] + 19.8({x_2} - 1)({x_4} - 1) $, $- 2 \leqslant {x_i} \leqslant 2,i = 1,2,3,4$

      算例4[16]:min$G({x_1}, \cdot \cdot \cdot ,{x_6}) = \sum\limits_{i = 1}^6 {(x_i^2 - \dfrac{1}{{10}}\cos (5\pi {x_i}))} , $$- 1 \leqslant {x_i} \leqslant 1,i = 1,2,...,6 $

      算例5[17]:min$f\left( x \right) = \dfrac{1}{{20}}\sum\limits_{i = 1}^{20} {(0.025x_i^2} - {\sin ^2}(\pi {x_i})), $$ - 1 \leqslant{x_i} \leqslant 1,i = 1,2,...,20$

      算例6[17]:min$f(x) = \dfrac{1}{{40}}\sum\limits_{i = 1}^{40} {(0.025x_i^2} - {\sin ^2}(\pi {x_i})), $$- 1 \leqslant{x_i} \leqslant 1,i = 1,2,...,40$

      表1可以看出,提出的基于降维的全局优化近似解法是可行的。从数值效果来看,函数的维数越低,精度越高。

    • 给出了一个基于降维的全局优化近似算法,这种方法将降维与遗传算法相结合,用一维问题的最优解作为原n维箱式约束问题的最优解的近似,降低问题难度。从数值效果来看,算法是有效的。

(1)  表(1) 参考文献 (17) 相关文章 (11)

目录

    /

    返回文章