介绍
模拟退火算法最早的思想是由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语言实战》李诗羽、张飞、王正林
文章出处登录后可见!