论文部分内容阅读
[摘 要] 蚁群优化算法是一种新兴的优化技术，它的思想来源于人工生命和演化计算理论。蚁群算法简单容易实现、可调参数少，已经得到了广泛研究和应用。本文提出了一种结合有限元方法求解偏微分方程反问题的蚁群优化算法，在对微分方程模型测试的数值模拟中都得到了较好的结果，体现了该算法的有效性、通用性和稳健性。
[关键词] 数学物理 蚁群优化算法 求解
引言
数学物理反问题是一个新兴的研究领域。有别于传统的数学物理方程的定解问题（通常称为正问题，它由给定的数学物理方程和相应的定解条件来求定解问题的解），反问题研究由解的部分已知信息来求定解问题中的某些未知量，如微分方程中的系数，定解问题的区域或者是某些定解条件。二维抛物型反问题是数学物理反问题中的一个重要方面，多年来人们已经为此进行了一系列的研究，提出了不少富有成效的求解方法，如最佳摄动量法，正则化方法等。但这些经典的方法一般都要求函数连续并且可微，大都使用了基于梯度信息的数学技巧，在接近最优解的时候，往往会出现所谓的锯齿现象，收敛缓慢。因此传统的优化方法并不适合于求解不可微函数以及高维函数的优化问题。近年来蓬勃发展起来的智能演化算法被广泛应用于优化领域，其全局最优性、可并行性和高效性在函数优化中得到了广泛的应用。1991年意大利学者Marco Dorigo及其导师Colorni提出了一种更简单、更有效的智能演化算法——蚁群优化算法（简称ACD），是智能演化算法产生以来在算法方面取得的巨大进展，该算法在许多领域都取得了广泛的应用。蚁群优化算法不仅能更快、更稳定地收敛到问题的全局最优解，而且它要比其他算法简单得多。
本文在目前组合优化领域中颇有成效的蚁群算法思想的基础上，提出了一种改进的求解反问题的连续型蚁群算法，对函数优化问题没有任何可微甚至连续的要求。通过一系列测试，效果良好。
蚁群智能
昆虫学家们在研究类似蚂蚁这样的视盲动物如何沿最佳路线从其巢穴到达事物源的过程中发现，蚂蚁与蚂蚁之间最重要的通信媒介就是它们在移动过程中所释放的特有的分泌物——信息素。当一个孤立的蚂蚁随机移动时，它能检测到其他同伴所释放的信息素，并沿着该路线移动，同时又释放自身的信息素，从而增强了该路线上的信息素数量。随着越来越多的蚂蚁通过该路线，一条最佳的路径就会逐渐形成。蚁群智能是多蚂蚁的聚集行为，信息素是该系统的标识，整个蚁群智能具有一些特点：非线性，涌现和自组织性；活性主体和并行性；正反馈和初值敏感；个体与环境及其他个体相互影响，相互作用；把宏观与微观有机地联系在一起，引进了随机因子。蚂蚁选择路径是随机的，只不过蚂蚁选择信息素浓度高的路径的概率高于信息素浓度低的路径。算法中随机因子扩大了蚂蚁的活动范围，从而能够使蚂蚁接触到更多的解。
求解函数优化问题的ACD算法
在新一代的智能型算法——蚁群算法中，尽管仍未能彻底解决收敛性问题，但至少对于求解一般函数优化问题而言，没有对这些优化函数要求任何可微甚至连续的前提条件。
一个经典的带约束函数优化问题可写成如下形式：
用常规的罚函数将所有约束方程转入目标函数中，这样，在算法的具体搜索过程中可不必考虑约束是否满足的问题，而直接通过对目标函数的评价，由罚函数来强制这种形式满足。
对每个蚂蚁i，定义其评价函数值为相应的目标函数值Zi并记 .
定义转移概率：
其中，Ti为蚂蚁i的邻域（半径为r）内的信息素数量，α，β为非负数。
算法中的转移概率定义不同于其在组合优化路径类问题中的实现，搜索过程将分两部分来寻找最优解。
第一部分是将给定个数的蚂蚁随机地散布在解读定义域内的等分区域的某处，可按以下方法生成：
rand是[0,1]之间的随机数，并记录具有最好评价函数值的精英蚂蚁。
第二部分是按转移概率移动个蚂蚁，并嵌入邻域搜索机制（按ΔZij的正负来决定是否作邻域搜索），试图寻找更好的解，然后按蚂蚁信息素更新规则进行轨迹更新。
通过不断地重复上述过程，使算法能够找到问题的最优解，或较好的满意解。求解函数优化问题的基本蚁群算法思想可简述如下：
步骤1. 初始化：
nc←迭代次数；m←蚂蚁个数；
对每个蚂蚁 （较小的正常数）；
（外循环）
步骤2. 对每个蚂蚁k：
在X的定义范围内随机生成一个解X(k)，并计算相应评价函数值；
Z*←当前最好的评价函数值，X*←对应Z*的X；
步骤3. 置s←1（内循环）
步骤4. 对每个蚂蚁k：
按转移概率Pkj将X（j ），；
（Q为单位蚂蚁遗留的信息素数量）
以邻域半径r对X(k)作局部搜索，更新Z*和X*；
步骤5. s←s+1；
步骤6. 若s<预定次数≤nc（可自定），则转移步骤4；
步骤7. 对每个蚂蚁； ；
步骤8. r ← r ·99%；（按99%缩减，可自定缩减比例）
步骤9.count 步骤10. 输出Z*和X*。
结 论
本文在基本的粒子群算法的基础上，成功地与有限元方法相结合，在求解抛物型方程反问题上显示了该算法的优越性，实验结果表明，本文提出的算法对偏微分方程反问题均适用，该算法可以更快、更稳定地收敛到问题的全局最优解，而且该算法易懂，通用。
参考文献：
[1]Kenneth Price, Rainer M Storn, Jouni A. Lampinen differential evolution: a practical approach to global optimization. Springer, 2004.
[2]吴志健,康立山,邹秀芬.一种解函数优化问题的精英子空间演化算法[J].计算机应用，2003,23(2):13-14.
[3]阳明盛,罗长童.最优化原理、方法及求解软件[M].北京:科学出版社,2006.
[4]龚纯,王正林.MATLAB常用算法程序集[M].北京:电子工业出版社,2008.
[5]王正林,刘明.精通MATLAB7[M].北京:电子工业出版社,2006.
作者单位：西安交通大学城市学院 陕西西安
[关键词] 数学物理 蚁群优化算法 求解
引言
数学物理反问题是一个新兴的研究领域。有别于传统的数学物理方程的定解问题（通常称为正问题，它由给定的数学物理方程和相应的定解条件来求定解问题的解），反问题研究由解的部分已知信息来求定解问题中的某些未知量，如微分方程中的系数，定解问题的区域或者是某些定解条件。二维抛物型反问题是数学物理反问题中的一个重要方面，多年来人们已经为此进行了一系列的研究，提出了不少富有成效的求解方法，如最佳摄动量法，正则化方法等。但这些经典的方法一般都要求函数连续并且可微，大都使用了基于梯度信息的数学技巧，在接近最优解的时候，往往会出现所谓的锯齿现象，收敛缓慢。因此传统的优化方法并不适合于求解不可微函数以及高维函数的优化问题。近年来蓬勃发展起来的智能演化算法被广泛应用于优化领域，其全局最优性、可并行性和高效性在函数优化中得到了广泛的应用。1991年意大利学者Marco Dorigo及其导师Colorni提出了一种更简单、更有效的智能演化算法——蚁群优化算法（简称ACD），是智能演化算法产生以来在算法方面取得的巨大进展，该算法在许多领域都取得了广泛的应用。蚁群优化算法不仅能更快、更稳定地收敛到问题的全局最优解，而且它要比其他算法简单得多。
本文在目前组合优化领域中颇有成效的蚁群算法思想的基础上，提出了一种改进的求解反问题的连续型蚁群算法，对函数优化问题没有任何可微甚至连续的要求。通过一系列测试，效果良好。
蚁群智能
昆虫学家们在研究类似蚂蚁这样的视盲动物如何沿最佳路线从其巢穴到达事物源的过程中发现，蚂蚁与蚂蚁之间最重要的通信媒介就是它们在移动过程中所释放的特有的分泌物——信息素。当一个孤立的蚂蚁随机移动时，它能检测到其他同伴所释放的信息素，并沿着该路线移动，同时又释放自身的信息素，从而增强了该路线上的信息素数量。随着越来越多的蚂蚁通过该路线，一条最佳的路径就会逐渐形成。蚁群智能是多蚂蚁的聚集行为，信息素是该系统的标识，整个蚁群智能具有一些特点：非线性，涌现和自组织性；活性主体和并行性；正反馈和初值敏感；个体与环境及其他个体相互影响，相互作用；把宏观与微观有机地联系在一起，引进了随机因子。蚂蚁选择路径是随机的，只不过蚂蚁选择信息素浓度高的路径的概率高于信息素浓度低的路径。算法中随机因子扩大了蚂蚁的活动范围，从而能够使蚂蚁接触到更多的解。
求解函数优化问题的ACD算法
在新一代的智能型算法——蚁群算法中，尽管仍未能彻底解决收敛性问题，但至少对于求解一般函数优化问题而言，没有对这些优化函数要求任何可微甚至连续的前提条件。
一个经典的带约束函数优化问题可写成如下形式：
用常规的罚函数将所有约束方程转入目标函数中，这样，在算法的具体搜索过程中可不必考虑约束是否满足的问题，而直接通过对目标函数的评价，由罚函数来强制这种形式满足。
对每个蚂蚁i，定义其评价函数值为相应的目标函数值Zi并记 .
定义转移概率：
其中，Ti为蚂蚁i的邻域（半径为r）内的信息素数量，α，β为非负数。
算法中的转移概率定义不同于其在组合优化路径类问题中的实现，搜索过程将分两部分来寻找最优解。
第一部分是将给定个数的蚂蚁随机地散布在解读定义域内的等分区域的某处，可按以下方法生成：
rand是[0,1]之间的随机数，并记录具有最好评价函数值的精英蚂蚁。
第二部分是按转移概率移动个蚂蚁，并嵌入邻域搜索机制（按ΔZij的正负来决定是否作邻域搜索），试图寻找更好的解，然后按蚂蚁信息素更新规则进行轨迹更新。
通过不断地重复上述过程，使算法能够找到问题的最优解，或较好的满意解。求解函数优化问题的基本蚁群算法思想可简述如下：
步骤1. 初始化：
nc←迭代次数；m←蚂蚁个数；
对每个蚂蚁 （较小的正常数）；
（外循环）
步骤2. 对每个蚂蚁k：
在X的定义范围内随机生成一个解X(k)，并计算相应评价函数值；
Z*←当前最好的评价函数值，X*←对应Z*的X；
步骤3. 置s←1（内循环）
步骤4. 对每个蚂蚁k：
按转移概率Pkj将X（j ），；
（Q为单位蚂蚁遗留的信息素数量）
以邻域半径r对X(k)作局部搜索，更新Z*和X*；
步骤5. s←s+1；
步骤6. 若s<预定次数≤nc（可自定），则转移步骤4；
步骤7. 对每个蚂蚁； ；
步骤8. r ← r ·99%；（按99%缩减，可自定缩减比例）
步骤9.count
结 论
本文在基本的粒子群算法的基础上，成功地与有限元方法相结合，在求解抛物型方程反问题上显示了该算法的优越性，实验结果表明，本文提出的算法对偏微分方程反问题均适用，该算法可以更快、更稳定地收敛到问题的全局最优解，而且该算法易懂，通用。
参考文献：
[1]Kenneth Price, Rainer M Storn, Jouni A. Lampinen differential evolution: a practical approach to global optimization. Springer, 2004.
[2]吴志健,康立山,邹秀芬.一种解函数优化问题的精英子空间演化算法[J].计算机应用，2003,23(2):13-14.
[3]阳明盛,罗长童.最优化原理、方法及求解软件[M].北京:科学出版社,2006.
[4]龚纯,王正林.MATLAB常用算法程序集[M].北京:电子工业出版社,2008.
[5]王正林,刘明.精通MATLAB7[M].北京:电子工业出版社,2006.
作者单位：西安交通大学城市学院 陕西西安