一种改进的遗传退火算法以及收敛性分析

《一种改进的遗传退火算法以及收敛性分析》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第３２卷第２期重庆工商大学学报（自然科学版）２０１５年２月Ｖｏｌ?３２ＮＯ．２ＪＣｈｏｎｇｑｉｎｇＴｅｃｈｎｏｌＢｕｓｉｎｅｓｓＵｎｉｖ?（ＮａｔＳｃｉＥｄ）Ｆｅｂ．２０１５ｄｏｉ：１０．１６０５５／ｊ．ｉｓｓｎ．１６７２－０５８Ｘ．２０１５．０００２．０１０∗一种改进的遗传退火算法以及收敛性分析高发玲（青岛理工大学琴岛学院，山东青岛２６６１００）摘要：针对一种约束条件既有０－１变量又有整数变量的非线性混合整数规划模型，给出一种改进的遗传退火算法求解，并建立对应的Ｍａｒｋｏｖ链且理论证明其收敛性．关键

2、词：遗传退火；Ｍａｒｋｏｖ链；遍历；收敛性中图分类号：Ｏ２２１．２文献标识码：Ａ文章编号：１６７２－０５８Ｘ（２０１５）０２－００４９－０５０引言针对一种约束条件既有０－１变量又有整数变量的非线性混合整数规划模型，数学模型ｍｉｎｆ（Ｘ，Ｙ）ìïｇｉ（Ｘ，Ｙ）≥０，（ｉ＝１，２，…Ｍ）ï（１）ｓ．ｔíｈｊ（Ｘ，Ｙ）＝０，（ｊ＝Ｍ＋１，Ｍ＋２，…Ｎ）ïïｌîＸ∈Ｚ，Ｙ∈{０，１}提出一种改进的遗传退火算法并对其算法对应Ｍａｒｋｏｖ链进行收敛性分析．１算法设计改进的遗传退火算法分为５步：编码方案的设计、解除

3、约束与适应度函数的选定、交叉操作设计、变异操作设计以及终止条件的确定．１．１编码方案的设计对于０－１决策变量的Ｙ，采用二进制编码；对于整数变量Ｘ，采用浮点编码．１．２解除约束与适应函数的选定（１）约束优化问题处理．采用惩罚策略技术将有约束的优化模型转化为无约束优化问题，ｅｖａｌ（Ｘ，Ｙ）＝ｆ（Ｘ，Ｙ）＋Ｐ（Ｘ，Ｙ）（２）Ｎ１２［１］其中Ｐ（Ｘ，Ｙ）＝?ｄｉ（Ｘ，Ｙ），ａ是可变惩罚因子，而２ａｉ＝１ｍａｘ{０，ｇ（Ｘ，Ｙ）}，ｉｆ（１≤ｉ≤Ｍ）ｉｄ（Ｘ，Ｙ）＝ｉ{ｈ（Ｘ，Ｙ），ｉｆ（Ｍ＋１≤ｉ≤Ｎ）ｉ此

4、时采用的可变惩罚因子ａ＝ｔ，其中ｔ为第ｋ代退火温度．ｋｋ收稿日期：２０１４－０６－１５；修回日期：２０１４－０９－１０．作者简介：高发玲（１９８２⁃）女，山东青岛人，讲师，硕士，从事网络优化设计研究．５０重庆工商大学学报（自然科学版）第３２卷（２）适应度函数的选定．Ｆ－Ｆ（ｔ）ｍｉｎｉｋＦ（ｔ）＝ｅｘｐｉｋ＋１{}（３）ｔｋ１．３交叉操作设计由于编码方法采用的是上述混合并行方案，因此在交叉操作中也采用相应的方式，对０－１决策变量的Ｙ进行单点交叉，对整数变量Ｘ进行混合交叉．１．４变异操作设计对模型中的两

5、种决策变量采用不同的变异方式，对０－１决策变量的Ｙ采用基本位变异，对整数变量Ｘ采用均匀变异．１．５终止条件的确定计算在每一温度下每一代群体染色体的最大适应值和最小适应值，当最大适应值与最小适应值之间的差小于ε（ε为参数）时，停止此温度下的种群迭代；设退火温度为ｔ，若满足ｔ≤η（η为很小的参数）时（计ｋｋ算迭代到规定的退火温度），则停止计算．２算法收敛性分析２．１算法对应Ｍａｒｋｏｖ链的建立离散组合优化问题ｍｉｎｆ（ｂ），其中ｂ为所有变量对应的一个状态，设状态集Ω＝{ｂ，ｉ＝１，２，…，ｎ}，ｉｉｉΩ＝

6、ｎ．ｉｉｉ设变量的个数为ｋ（其中有ｌ个０－１变量；有ｋ－ｌ个整数变量），称ｂ＝ａａ…ａ为一个个体或染色体，这ｉ１２ｋ里的ａ（ｊ＝１，２，…，ｌ）为０或１，ａ（ｊ＝ｌ＋１，…，ｋ）为整数．ｊｊ设种群集Ｑ中每一种群包含ｍ个个体，任一点集Ｂ＝{ｂ，ｂ，…ｂ}称为一个种群，则种群总数Ｑ＝Ｃ１２ｍ（１）（２）Ｑ（ｎ，ｍ），相当于从ｎ个不同个体中可选取ｍ个的方案总数，设Ｑ＝{Ｂ，Ｂ，…，Ｂ}．（ｉ）（ｊ）（ｉ）定义１矩阵Ｃ＝（ｃ），Ｍ＝（ｍ）（Ｂ，Ｂ＝１，２，…Ｑ），若ｃ是由Ｂ以交叉概率Ｐ∈Ｂ（ｉ）Ｂ（ｊ）Ｂ（ｉ

7、）Ｂ（ｊ）Ｂ（ｉ）Ｂ（ｊ）ｃ（ｊ）（ｉ）（ｊ）[０，１]杂交到Ｂ对应的一步转移概率，ｍ是由Ｂ以变异概率Ｐ∈（０，１）变异到Ｂ对应的一步转移Ｂ（ｉ）Ｂ（ｊ）ｍ概率，则称Ｃ和Ｍ分别为交叉和变异对应的一步转移概率矩阵．［２］引理１若Ｃ和Ｍ分别是以交叉概率Ｐ∈[０，１]进行交叉和以变异概率Ｐ∈(０，１)进行变异对应的ｃｍ一步转移概率矩阵，则Ｃ和Ｍ均为随机阵．（ｉ）（ｊ）（ｉ）（ｊ）定义２若种群Ｂ和Ｂ中仅有某一个个体不同，设ｂ∈Ｂ≠ｂ∈Ｂ且满足ｂ∈Ｎ（ｂ），则称种群ｉｊｊｉ（ｉ）（ｊ）（ｊ）Ｂ属于种群Ｂ的邻域Ｎ

8、（Ｂ）．（ｉ）（ｊ）定义３ＳＡ状态产生函数使种群Ｂ转移到Ｂ的一步转移概率为ｅ－ｆ（Ｂ（ｉ））／Ｔｈ／［?ｅ－ｆ（Ｂ（ｊ））／Ｔｈ］，Ｂ（ｊ）∈Ｎ（Ｂ（ｉ））ｇ（Ｔ）＝Ｂ（ｊ）∈Ｎ（Ｂ（ｉ））（４）Ｂ（ｉ）Ｂ（ｊ）ｈ{（ｊ）（ｉ）０，Ｂ∉Ｎ（Ｂ）其中（ｉ）ｆ（Ｂ）＝?ｆ（ｂ）（５）ｉｂｉ∈Ｂ（ｉ）定义４对种群中个体作模拟退火操作所引起的种群的一步转移概率：（ｉ）（ｊ）（ｊ）（ｉ）ìïｇＢ（ｉ）Ｂ（ｊ）ｍｉｎ{１，ｅｘｐ（－（ｆ（Ｂ）－ｆ（Ｂ））／Ｔｈ}，Ｂ