论文部分内容阅读
摘要：针对几个高维函数优化进行了研究，提出一种混合智能算法。借鉴人口迁移算法的进化体制，精简了算法步骤；鉴于云模型的云滴在随机中带有稳定倾向性，将人口进化过程中初始人口群体由云模型的云滴代替，人口流动转化为上一代云滴产生新一代云滴的过程；为防止寻优陷入局部极值，借用柯西分布的强扰动性，对优惠区域的人口实施柯西变异。几个典型高维函数的仿真实验表明，算法求解质量高、性能稳定，甚至对几个维数高达10000维的超高维函数，算法都可以稳定收敛到理论最优。
關键词：人口迁移算法；云模型；柯西变异；高维函数优化
中图分类号：TP18
文献标志码：A
文章编号：1006-8228（2017）01-47-04
0.引言
求解高维函数时，随着维数的增加，解空间及问题的复杂度呈指数级增加，甚至产生维数灾难，高维函数又常有多个局部最优，增加了问题求解的欺骗性。遗传算法、粒子群算法、蚁群算法等传统智能算法，在求解小规模低维优化问题时性能较好，对高维或超高维函数的优化却效果不佳。人类是自然界最具智慧的，人类的生息必然蕴藏着高智能的算法。人口迁移算法（Population Migration Algorithm，PMA）就是从人类活动中总结、抽象出来的一种智能算法，于2003年由我国学者周永华、毛宗源提出。这两位学者通过对人类的社会活动进行研究，发现当人类的经济重心发生转移时，人口密度也随之转移，根据人类活动的这种机理他们提出了人口迁移算法。算法进化的过程由人口流动、人口迁移和人口扩散组成，实验表明算法的全局搜索能力较强，且文献证明了算法是收敛的。但在高维函数的求解中，人口迁移算法易陷入局部极值，寻优速度有所下降。
云模型是一个定性、定量转换模型，由我国学者李德毅教授提出。该模型既是对模糊理论的创新，也是对隶属函数概念的发展，它的云滴体现了随机性和稳定性的有机结合。云模型一经提出，就受到多方学者的关注，已成功应用于多个领域。柯西分布是概率论与数理统计中的一种常见分布，相比高斯分布，柯西分布下降至零的速度慢得多。因此，柯西变异的扰动性比高斯变异强很多，更易使搜索跳出局部极值，从而可进一步提高算法的全局寻优能力。
在原人口迁移算法的基础上，有机结合云模型和柯西变异，提出一种可求解高维函数优化的混合智能算法（hybrid intelligence algorithm，简称HIA）。典型的高维函数测试表明，算法求解质量高、性能稳定，甚至对几个维数高达10000维的函数也表现出了极好的寻优效果。
1.云模型和柯西变异
1.1云模型
定义设u是一个用精确数值表示的论域（一维或多维的），u上对应着定性概念A，对于论域中的任意一个元素x，都存在一个有稳定倾向的随机数y=uA（x），叫作x对概念A的确定度，uA（X）在u上的分布称为云模型，简称云。当uA（x）服从正态分布时，称为正态云模型。
定性概念A的定量特征由云的三个数字特征（期望Ex、熵En、超熵He）来体现（如图l所示）。
生成云滴的算法或硬件称为云发生器。文献[7]阐述了基本云发生器的算法步骤。
1.2柯西变异
1.2.1柯西分布
柯西分布和高斯分布是概率论与数理统计中的常见分布。标准柯西、高斯分布概率密度函数图如图2所示。
由图2知，柯西变异的扰动能力显然强于高斯变异，用它对人口变异，更易跳出局部极值，从而提高搜索速度和全局寻优能力。
由随机变量生成函数定理呻知，式中Cauchy（0，1）=tan[（∈-0.5）π]，其中∈是[o，1]上服从均匀分布的随机变量。
2.混合智能算法
2.1算法思想
人口迁移算法是一种基于随机搜索的智能仿生算法，初始群体在搜索空间随机产生，人口流动是在邻域内随机变动，人口迁移是在优惠区域随机变动，随机性一定程度上存在盲目性和不稳定性，从而影响了算法的寻优效果。从云模型示意图可知，随机的云滴具有稳定倾向的特点，如果适当调整云模型的三个数字特征（期望Ex，熵En和超熵He），还可调整云滴的随机性范围和稳定性程度。混合算法采用人口迁移算法的进化体制，用整个搜索空问的云滴作为人口迁移算法的初始群体，去掉人口扩散精简算法步骤，用在邻域范围内产生云滴代替人口流动，为了避免算法限入局部极值，对优惠区域的人口实施苛西变异。从前面的分析知，柯西变异具有很强的扰动能力，对优惠区域人口进行柯西变异，提高了算法跳出局部极值的可能性，使算法具有更强的寻优能力。将云模型、柯西变异与人口迁移相结合也是一种新的尝试。
2.2融合柯西变异、云模型和人口迁移算法的混合智能算法（HlA）
3.混合智能算法（HIA）性能分析
本文所用实验环境为：操作系统为Windows XPProfessional SP3，硬件为Intel（R）Core（TM）2 Due CPUT5870～2GB内存、wDc WD2500BEVS-08VAT2硬盘的ThinkPad SL400笔记本电脑，编程软件为Matlab 2012b。
实验中，为便于比较，对函数fi～fs的维数取30，50，100时进行了实验，对函数f4的维数分别为10、20、30时进行了实验，每个函数的各维独立计算30次，取最好解（best）、最差解（worst）、数学期望（average）和标准差（Std.Dev.）作为评价参数，将实验数据与文献的MEDE进行了比较，结果如表2所示。
从表2可见，对f1、f4、30和50维的f3，MEDE可搜到最优，但对f2和100维的f3，MEDE的搜索结果只是接近于理论最优。由文献[11]知，当函数f1-f3的维数为30，50.100及函数f4的维数为10.20，30时.MEDE的最大迭代次数分别为1000，2000，5000。对函数f1～f4的各维，本文算法都可稳定精确收敛于理论最优，且算法参数不因函数维数的增加而变化，始终保持表1的设置，迭代次数均为2。可见，相对目前搜索结果较好的MEDE，本文算法具有更好的寻优性能、稳定性和鲁棒性。 实验中，还对f1～f4的100维、200维进行了测试，本文算法的参数仍保持表1的设置。测试结果与文献[11]的MEDE、DefirDE、DEfirSPX進行比较，文献[HI中几个算法的迭代次数对f1～f3为50000，对f4同文献[12]。比较结果如表3所示。
从表3可以看出，对于100维和200维的f1～f4，本文算法比目前结果较好的文献nu中的几个算法的求解质量都要好，平均值和标准差都明显优于其他几个算法，且本文算法的群体规模为3，迭代次数为2，比其他几个算法少得多，但却达到了更好的寻优效果。而且随着维数的增加，这种优势越来越明显。
3.2超高维函数测试
为进一步验证算法的性能，对函数f1～f4的超高维（1000，2000，5000，10000）进行了实验。对如此高维函数的测试，目前基本都是在性能非常好的并行机上运行，而本文的实验仍然是在个人笔记本上运行。实验时，HIA的各参数仍保持表1的设置不变，算法对每个函数的各超高维均运行10次。实验结果令人鼓舞：随着函数维数的增加，问题的复杂度大大增加，但算法的参数和求解质量却不受影响，避免了维数灾难。事实上，每一次实验，算法都可精确收敛到各超高维函数的理论最优。可见，混合智能算法求解质量高，性能稳定。
4.结论与展望
原人口迁移算法步骤多，搜索速度慢，易陷入局部最优，不利于求解高维或超高维函数。正态云模型的云滴既具有随机性又具有稳定性，稳定性可在一定程度上保护历史较好个体，随机性可帮助个体跳出局部极值。柯西变异相对高斯变异具有更强的扰动能力，可帮助个体扩大搜索范围。将改进后的人口迁移算法与云模型和柯西变异有机融合：借用改进人口迁移算法的搜索机制，初始群体为搜索空间产生的云滴，人口流动为邻域内产生云滴的过程，人口迁移后对优惠区域的人口进行柯西变异。所以，混合智能算法既保留了改进人口迁移算法的较好寻优机制，又充分利用了云模型的随机稳定性和柯西变异的强扰动力，提高了算法的寻优能力。仿真实验表明，混合智能算法寻优性能好，求解效率和质量高，且性能稳定。
關键词：人口迁移算法；云模型；柯西变异；高维函数优化
中图分类号：TP18
文献标志码：A
文章编号：1006-8228（2017）01-47-04
0.引言
求解高维函数时，随着维数的增加，解空间及问题的复杂度呈指数级增加，甚至产生维数灾难，高维函数又常有多个局部最优，增加了问题求解的欺骗性。遗传算法、粒子群算法、蚁群算法等传统智能算法，在求解小规模低维优化问题时性能较好，对高维或超高维函数的优化却效果不佳。人类是自然界最具智慧的，人类的生息必然蕴藏着高智能的算法。人口迁移算法（Population Migration Algorithm，PMA）就是从人类活动中总结、抽象出来的一种智能算法，于2003年由我国学者周永华、毛宗源提出。这两位学者通过对人类的社会活动进行研究，发现当人类的经济重心发生转移时，人口密度也随之转移，根据人类活动的这种机理他们提出了人口迁移算法。算法进化的过程由人口流动、人口迁移和人口扩散组成，实验表明算法的全局搜索能力较强，且文献证明了算法是收敛的。但在高维函数的求解中，人口迁移算法易陷入局部极值，寻优速度有所下降。
云模型是一个定性、定量转换模型，由我国学者李德毅教授提出。该模型既是对模糊理论的创新，也是对隶属函数概念的发展，它的云滴体现了随机性和稳定性的有机结合。云模型一经提出，就受到多方学者的关注，已成功应用于多个领域。柯西分布是概率论与数理统计中的一种常见分布，相比高斯分布，柯西分布下降至零的速度慢得多。因此，柯西变异的扰动性比高斯变异强很多，更易使搜索跳出局部极值，从而可进一步提高算法的全局寻优能力。
在原人口迁移算法的基础上，有机结合云模型和柯西变异，提出一种可求解高维函数优化的混合智能算法（hybrid intelligence algorithm，简称HIA）。典型的高维函数测试表明，算法求解质量高、性能稳定，甚至对几个维数高达10000维的函数也表现出了极好的寻优效果。
1.云模型和柯西变异
1.1云模型
定义设u是一个用精确数值表示的论域（一维或多维的），u上对应着定性概念A，对于论域中的任意一个元素x，都存在一个有稳定倾向的随机数y=uA（x），叫作x对概念A的确定度，uA（X）在u上的分布称为云模型，简称云。当uA（x）服从正态分布时，称为正态云模型。
定性概念A的定量特征由云的三个数字特征（期望Ex、熵En、超熵He）来体现（如图l所示）。
生成云滴的算法或硬件称为云发生器。文献[7]阐述了基本云发生器的算法步骤。
1.2柯西变异
1.2.1柯西分布
柯西分布和高斯分布是概率论与数理统计中的常见分布。标准柯西、高斯分布概率密度函数图如图2所示。
由图2知，柯西变异的扰动能力显然强于高斯变异，用它对人口变异，更易跳出局部极值，从而提高搜索速度和全局寻优能力。
由随机变量生成函数定理呻知，式中Cauchy（0，1）=tan[（∈-0.5）π]，其中∈是[o，1]上服从均匀分布的随机变量。
2.混合智能算法
2.1算法思想
人口迁移算法是一种基于随机搜索的智能仿生算法，初始群体在搜索空间随机产生，人口流动是在邻域内随机变动，人口迁移是在优惠区域随机变动，随机性一定程度上存在盲目性和不稳定性，从而影响了算法的寻优效果。从云模型示意图可知，随机的云滴具有稳定倾向的特点，如果适当调整云模型的三个数字特征（期望Ex，熵En和超熵He），还可调整云滴的随机性范围和稳定性程度。混合算法采用人口迁移算法的进化体制，用整个搜索空问的云滴作为人口迁移算法的初始群体，去掉人口扩散精简算法步骤，用在邻域范围内产生云滴代替人口流动，为了避免算法限入局部极值，对优惠区域的人口实施苛西变异。从前面的分析知，柯西变异具有很强的扰动能力，对优惠区域人口进行柯西变异，提高了算法跳出局部极值的可能性，使算法具有更强的寻优能力。将云模型、柯西变异与人口迁移相结合也是一种新的尝试。
2.2融合柯西变异、云模型和人口迁移算法的混合智能算法（HlA）
3.混合智能算法（HIA）性能分析
本文所用实验环境为：操作系统为Windows XPProfessional SP3，硬件为Intel（R）Core（TM）2 Due CPUT5870～2GB内存、wDc WD2500BEVS-08VAT2硬盘的ThinkPad SL400笔记本电脑，编程软件为Matlab 2012b。
实验中，为便于比较，对函数fi～fs的维数取30，50，100时进行了实验，对函数f4的维数分别为10、20、30时进行了实验，每个函数的各维独立计算30次，取最好解（best）、最差解（worst）、数学期望（average）和标准差（Std.Dev.）作为评价参数，将实验数据与文献的MEDE进行了比较，结果如表2所示。
从表2可见，对f1、f4、30和50维的f3，MEDE可搜到最优，但对f2和100维的f3，MEDE的搜索结果只是接近于理论最优。由文献[11]知，当函数f1-f3的维数为30，50.100及函数f4的维数为10.20，30时.MEDE的最大迭代次数分别为1000，2000，5000。对函数f1～f4的各维，本文算法都可稳定精确收敛于理论最优，且算法参数不因函数维数的增加而变化，始终保持表1的设置，迭代次数均为2。可见，相对目前搜索结果较好的MEDE，本文算法具有更好的寻优性能、稳定性和鲁棒性。 实验中，还对f1～f4的100维、200维进行了测试，本文算法的参数仍保持表1的设置。测试结果与文献[11]的MEDE、DefirDE、DEfirSPX進行比较，文献[HI中几个算法的迭代次数对f1～f3为50000，对f4同文献[12]。比较结果如表3所示。
从表3可以看出，对于100维和200维的f1～f4，本文算法比目前结果较好的文献nu中的几个算法的求解质量都要好，平均值和标准差都明显优于其他几个算法，且本文算法的群体规模为3，迭代次数为2，比其他几个算法少得多，但却达到了更好的寻优效果。而且随着维数的增加，这种优势越来越明显。
3.2超高维函数测试
为进一步验证算法的性能，对函数f1～f4的超高维（1000，2000，5000，10000）进行了实验。对如此高维函数的测试，目前基本都是在性能非常好的并行机上运行，而本文的实验仍然是在个人笔记本上运行。实验时，HIA的各参数仍保持表1的设置不变，算法对每个函数的各超高维均运行10次。实验结果令人鼓舞：随着函数维数的增加，问题的复杂度大大增加，但算法的参数和求解质量却不受影响，避免了维数灾难。事实上，每一次实验，算法都可精确收敛到各超高维函数的理论最优。可见，混合智能算法求解质量高，性能稳定。
4.结论与展望
原人口迁移算法步骤多，搜索速度慢，易陷入局部最优，不利于求解高维或超高维函数。正态云模型的云滴既具有随机性又具有稳定性，稳定性可在一定程度上保护历史较好个体，随机性可帮助个体跳出局部极值。柯西变异相对高斯变异具有更强的扰动能力，可帮助个体扩大搜索范围。将改进后的人口迁移算法与云模型和柯西变异有机融合：借用改进人口迁移算法的搜索机制，初始群体为搜索空间产生的云滴，人口流动为邻域内产生云滴的过程，人口迁移后对优惠区域的人口进行柯西变异。所以，混合智能算法既保留了改进人口迁移算法的较好寻优机制，又充分利用了云模型的随机稳定性和柯西变异的强扰动力，提高了算法的寻优能力。仿真实验表明，混合智能算法寻优性能好，求解效率和质量高，且性能稳定。