模拟退火算法

介绍

模拟退火算法最早的思想是由N.Metroplis等人于1953年提出的,1983年,S.Kirkpatrick等人成功地将退火思想引入到组合优化领域,提出一种解决大规模组合优化问题,特别是NP完全组合优化难题的有效近似算法——模拟退火算法。它是来源于固体退火的原理,先将固体加温至充分高,再将其徐徐冷却的过程。加温时,固体内部例子随温度上升而变为无序态,内能增大,而徐徐冷却时粒子渐渐趋有序态,在每个温度点上都能达到平衡态,最后在常温时达到基态,内能减为最小。模拟退火算法应用于组合最优化,克服了优化过程中局部极小和初值依赖性的缺陷。

根据模拟退火算法准则,内部粒子在温度T时趋于平衡的概率为模拟退火算法,其中模拟退火算法为当温度模拟退火算法时的内能,模拟退火算法为内能改变量,模拟退火算法模拟退火算法常数。用固体退火过程来模拟组合优化问题,先将内能E模拟为目标函数值模拟退火算法,温度模拟退火算法演化成控制参数模拟退火算法,即可得到解投资组合优化问题的模拟退火算法:由初始解模拟退火算法和控制参数初值模拟退火算法开始,对当前解重复“产生新解-计算目标函数差-判断是否接受-接受或舍弃”的迭代过程,并逐步衰减当前温度t值,直至达到阶数温度,算法终止时的当前解即为所得近似最优解,这是一种基于蒙特卡罗迭代求解法的启发式随机搜索过程。退火过程由冷却进度表控制,包括控制参数的温度初值t及其衰减因子模拟退火算法、每个模拟退火算法值时的迭代次数模拟退火算法和停止条件模拟退火算法

固定退火过程的物理图像和统计性质是模拟退火算法的物理背景;冷却进度表的合理选择是算法应用的前提;而模拟退火算法接受准则使算法脱离局部最优的“陷阱”。

步骤

1)初始化:初始温度模拟退火算法(充分大),初始解状态模拟退火算法(是算法迭代的起点),每个T值的迭代次数模拟退火算法(马尔科夫链),减温系数模拟退火算法
2)对模拟退火算法做3)至6)循环,完成一次马尔科夫链。
3)通过变异产生新解模拟退火算法
4)计算增量模拟退火算法,其中模拟退火算法为评价函数。
5)若模拟退火算法则接受模拟退火算法作为新的当前解,否则以概率模拟退火算法接受模拟退火算法作为新的当前解。
6)如果满足终止条件则输出当前解作为最优解,结束程序。否则转到7)。
7)模拟退火算法逐渐减少模拟退火算法,且模拟退火算法,然后转2)。

目标函数的选择

方法1:乘法函数法:
应用乘法函数法可以将模拟退火算法模型转化为如下的惩罚函数模拟退火算法的无约束优化问题来进行求解:
模拟退火算法
其中,模拟退火算法为惩罚因子,是充分大的正数。

方法2:正态假设法
模拟退火算法为目标收益率,那么投资组合最优化的目标即为使组合收益率达到δ的概率最大化模拟退火算法

假设每个证券的期望收益率均服从正态分布,那么投资组合的收益率也服从正态分布,即
模拟退火算法

从而概率最大化的模型可以表示为
模拟退火算法

参数选择

1) 目标收益率模拟退火算法模拟退火算法应大于所选取的30支股票的最高收益率。

2)相邻状态的产生
由于模拟退火算法的模拟退火算法性,相邻状态的产生依赖于当前状态。假设当前状态下投资组合权重为模拟退火算法
它的相邻状态产生函数为模拟退火算法。其中,模拟退火算法模拟退火算法上的随机数,模拟退火算法模拟退火算法的取值范围,即模拟退火算法

3)温度衰减函数。模拟退火算法其中,模拟退火算法是初始温度,模拟退火算法是一个大于等于1的常数,通常取3;模拟退火算法是第模拟退火算法次降温后的温度。

4)终止条件。温度最终降为模拟退火算法(接近零度,冷却状态)时循环过程结束。

在参数选择的过程中,对初始温度及内层迭代的次数没有进行设置,由于这两个参数直接决定着算法的循环次数以及优化效果,初始温度的选择越高,则退温次数越多,搜索到全局最优的可能性越大,从而得到的结果比较稳定。但算法的迭代次数增加会降低算法的可行性和有效性,因此本文通过几次尝试,选择最适合的参数来控制循环次数和结果。

参考文献:
《数据分析——R语言实战》李诗羽、张飞、王正林

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
扎眼的阳光的头像扎眼的阳光普通用户
上一篇 2022年5月21日
下一篇 2022年5月21日

相关推荐