模拟退火算法与遗传算法

第二章狭义计算智能 ——优化计算确定性优化算法Incomputerscience,adeterministicalgorithmisanalgorithmwhich,givenaparticularinput,willalwaysproducethesameoutput,withtheunderlyingmachinealwayspassingthroughthesamesequenceofstates.给定初始条件后，搜索策略、过程和结果均确定。数值计算法/wiki/Deterministic_algorithm2023/9/232确定性优化算法NP完全问题的计算复杂度1<lg(n)<n<nlg(n)<n^2<...<n^k<...<2^n2023/9/233《计算智能》计算智能》2.3启发式优化算法混合优化证券投资组合：证券品种选择属于组合优化问题，买入卖出价位及时机决策属于函数（来自于数据挖掘的预测函数）优化问题。思考：我们不可能掌握全部有用信息，也不可能建立这些信息对后市影响的明确的函数关系，那么如何投资？4启发式优化算法股票投资的启发式规则历史数据社会心理K线走势宏观经济情况国家政策……5启发式优化算法股票投资的结果跑赢大盘跑赢一年定期存款利率……当然不是最优结果，但已经值得满意6启发式优化算法定义（Heuristics）一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题的一个满意的可行解，该可行解与最优解的偏离程度一般不能被预计。<Wikipedia>:Heuristicreferstoexperience-basedtechniquesforproblemsolving,learning,anddiscoverythatfindasolutionwhichisnotguaranteedtobeoptimal,butgoodenoughforagivensetofgoals.Wheretheexhaustivesearchisimpractical,heuristicmethodsareusedtospeeduptheprocessoffindingasatisfactorysolutionviamentalshortcutstoeasethecognitiveloadofmakingadecision.？2023/9/237《计算智能》计算智能》启发式优化算法特点启发式搜索规则：Strategiesthatguidethesearchprocess随机性：每次计算都带有随机性，结果不保证综合优势：以利用较小的计算资源得到较好的可行解为目标NoFreeLunchTheorems假设有A、B两种任意（随机或确定）算法，对于所有问题集，它们的平均性能是相同的（性能可采用多种方法度量，如最优解、收敛速率等）。因此，要根据具体问题和性能要求选择合适的算法及其启发式搜索规则。TheonlyviableoptionforavarietyofcomplexoptimizationproblemsinNP-hardness经验、自然界、仿生…8启发式优化算法发展研究热点算法的启发式规则不同有些算法缺乏严格证明共性首先提出一个（组）候选解依据某些适应性条件测算这个（些）候选解的适应度（性能指标）根据适应度保留某些候选解，放弃其他候选解对保留的候选解进行某些操作，生成新的候选解9启发式优化算法分类搜索策略：局部搜索or全局搜索确定机制or学习机制迭代方法：单一解or群体解计算流程：serialorparallelorhybrid10启发式优化算法分类1:搜索策略对简单局部搜索的改进simulatedannealing(SA)tabusearchiteratedlocalsearchvariableneighborhoodsearchGRASP具有学习机制antcolonyoptimization(ACO)geneticalgorithms(GA)Simulatedevolutionarycomputation(SEC),模拟进化计算局部搜索从一个初始解出发，搜索它的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。优点是简单、灵活及易于实现；缺点是容易陷入局部最优，且解的质量与初始解和邻域的结构密切相关。张雷,范波.计算智能理论与方法[M].北京:科学出版社.2013:13.11启发式优化算法分类2:迭代方法SinglesolutionsimulatedannealingiteratedlocalsearchPopulation-basedInheritance:GAharmonysearch(HS)Contemporaries:particleswarmoptimization(PSO)differentialevolution(DE)Environment:antcolonyoptimization(ACO)binarybeesalgorithm(BBA)S.Xu,F.Yu,Z.Luo,Z.Ji,D.T.Pham,R.Qiu.AdaptiveBeesAlgorithm–Bioinspirationfromhoneybeeforagingtooptimizefueleconomyofasemi-trackair-cushionvehicle[J].TheComputerJournal.2011,54(9):1416-1426.12启发式优化算法代表性算法simulatedannealing(SA)：模拟退火算法geneticalgorithms(GA)：遗传算法antcolonyoptimization(ACO)：蚁群算法particleswarmoptimization(PSO)：粒子群算法Beesalgorithm(BA)anditsvariants：蜜蜂算法2023/9/2313《计算智能》计算智能》启发式优化算法函数优化问题算例二元函数求最小值，精确到4位小数Rosenbrockfunction2023/9/2314《计算智能》计算智能》启发式优化算法组合优化问题算例Berlin52

旅行商问题（TSP）——有一个推销员，要到n个城市推销商品。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactlyonce)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。52个城市的位置坐标2023/9/2315《计算智能》计算智能》模拟退火算法启发式规则模拟退火算法来源于固体退火原理。将固体加热至充分高温后，让其慢慢冷却。加热时，固体内部粒子随温升变为无序状，内能增大；而慢慢冷却时粒子渐趋有序，在每个温度都有可能达到平衡态，最后在常温时达到基态，内能减为最小。16模拟退火算法

2023/9/2317模拟退火算法算法流程及要素自变量空间中解x的更新机制目标函数值改进，绝对接受

优化进展目标函数值恶化，概率接受

摆脱局部最小值陷阱控制参数t的更新机制逐渐收敛，但具体方式多样劣解接受概率与t正相关

振荡范围逐渐变小，趋于稳定邻域定义及其更新机制思考：如何在算法/程序中实现？18算例1.4结果初值x0=1.745，步长f~xx~nf~n结果：x=1.6516，f=3.6494，n=16结论：与固定步长相比，在收敛速度和计算精度之间求平衡。思考：这种随机步长选择策略是否有问题？是否还有其他更好的步长选择策略，使收敛速度与计算精度的平衡性更好？19模拟退火算法算法评价优点具有渐进收敛性，概率性地收敛于全局最优解缺点参数（初始值、控制参数的更新机制等）敏感振荡范围单向收缩收敛速度与求全局最优解的要求相矛盾

全局搜索算子与局部搜索算子不独立20模拟退火算法算法改进根据具体问题的特点，合理设计更具启发性的算法机制，例如当前解在解空间中的振荡范围不仅与搜索进程有关，还应该与解的更新效率与收益率有关增加重升温过程，动态调整当前解在解空间中的振荡范围，从而避免算法在局部极小解处停滞不前或在计算后期收敛速度太慢增加记忆功能，避免当前最优解衰退参考群智能的思想，针对每一个当前状态x，采用多次搜索策略，以概率方式进行当前最优解的更新，而非传统的单次比较21模拟退火算法算例1二元函数求最小值，精确到4位小数定义域[-2,2]初始温度：100温度衰减系数：0.95同一温度下计算次数：50邻域范围系数：0.2终止条件：温度降低到1以下算例x.1:初值x10=0.5,x20=0.5算例x.2:初值x10=-0.5,x20=0.522模拟退火算法算例1.1实验结果x1*=0.9837,x2*=0.9684,F*=3.1438e-4,n*=1023模拟退火算法算例1.1重复实验结果计算次数x1*x2*F*n*10.98370.96843.1438e-41021.01701.03688.9150e-4531.04591.09280.0022840.96800.93240.00321250.98470.97860.0082122023/9/2324模拟退火算法算例1.2实验结果x1*=1.0288,x2*=1.0577,F*=8.7113e-4,n*=2025模拟退火算法算例1.2重复实验结果计算次数x1*x2*F*n*11.02881.05778.7113e-42020.99130.98201.1681e-41831.00501.00660.00121140.98100.96183.8874e-41451.02211.04505.0343e-4142023/9/2326模拟退火算法算例1结果分析由于是单值迭代，且渐进收敛，因此存在早熟收敛的问题，表现为以上计算均没有找到全局最优解初值对迭代结果无明显影响2023/9/2327模拟退火算法算例2二元函数求最小值，精确到4位小数定义域[-10,10]初始温度：100温度衰减系数：0.95同一温度下计算次数：50邻域范围系数：0.2终止条件：温度降低到1以下算例x.1:初值x10=0.5,x20=0.5算例x.2:初值x10=-0.5,x20=0.528模拟退火算法算例2.1实验结果x1*=1.1089,x2*=1.2319,F*=0.0124,n*=629模拟退火算法算例2.1重复实验结果计算次数x1*x2*F*n*11.10891.23190.0124620.95350.92210.0186930.86350.74870.0196541.09761.19850.0135850.92190.83730.022182023/9/2330模拟退火算法算例2.2实验结果x1*=0.9209,x2*=0.8505,F*=0.0068,n*=631模拟退火算法算例2.2重复实验结果计算次数x1*x2*F*n*10.92090.85050.0068620.90390.82320.0130831.01951.03240.0052741.11921.27180.0509751.00481.01440.0024112023/9/2332模拟退火算法算例2结果分析与算例1相比，初值改变后，迭代次数没有发生显著变化。原因在于，邻域范围与定义域范围成正比，在较大的定义域范围下，初值的变化量是一个相对小量。与算例1相比，解的质量更为恶化，早熟收敛的问题更为突出。其原因还是在于较大的邻域范围，导致新解的变化量大，起不到局部搜索的作用。希望通过下调最低温度来实现局部搜索NextX1=PreX1+StepFactor*X1MAX*(rand-0.5);NextX2=PreX2+StepFactor*X2MAX*(rand-0.5);2023/9/2333模拟退火算法算例3二元函数求最小值，精确到4位小数定义域[-10,10]初始温度：100温度衰减系数：0.95同一温度下计算次数：50邻域范围系数：0.2终止条件：温度降低到0.01以下算例x.1:初值x10=0.5,x20=0.5算例x.2:初值x10=-0.5,x20=0.534模拟退火算法算例3.1实验结果x1*=1.0061,x2*=1.0107,F*=2.4269e-4,n*=635模拟退火算法算例3.1重复实验结果计算次数x1*x2*F*n*11.00611.01072.4269e-4620.98850.97731.3624e-41231.00981.02133.9480e-41641.00591.01332.1228e-4851.00391.00651.7983e-411算例2.1重复实验结果计算次数x1*x2*F*n*11.10891.23190.0124620.95350.92210.0186930.86350.74870.0196541.09761.19850.0135850.92190.83730.0221836模拟退火算法算例3.2实验结果x1*=0.9563,x2*=0.9116,F*=0.0028,n*=937模拟退火算法算例3.2重复实验结果计算次数x1*x2*F*n*10.95630.91160.0028920.97860.95927.2158e-4931.05381.11030.0029941.01971.03660.0014550.96690.92730.00704算例2.2重复实验结果计算次数x1*x2*F*n*10.92090.85050.0068620.90390.82320.0130831.01951.03240.0052741.11921.27180.0509751.00481.01440.00241138模拟退火算法算例3结果分析与算例2相比，解的质量有所提高，早熟收敛问题有所改善。这说明下调最低温度能够在迭代后期、在一定程度上起到局部搜索的作用。但是，下调最低温度只是让变化程度小的解有了相对更大的存活几率，但它无法控制变化程度小的解的产生（要靠收缩搜索邻域范围实现）。因此，依靠下调最低温度在迭代后期起到局部搜索的作用，也只是治标不治本的办法。比较3.1和3.2的结果，初值对解的影响有所显现。39模拟退火算法算例4二元函数求最小值，精确到4位小数定义域[-10,10]初始温度：100温度衰减系数：0.8（总计算量基本保持平衡）同一温度下计算次数：200邻域范围系数：0.2终止条件：温度降到0.01以下算例x.1:初值x10=0.5,x20=0.5算例x.2:初值x10=-0.5,x20=0.540模拟退火算法算例4.1实验结果x1*=0.9395,x2*=0.8829,F*=0.0037,n*=1041模拟退火算法算例4.1重复实验结果计算次数x1*x2*F*n*10.93950.88290.00371020.96990.94139.4554e-4831.03001.06330.00151140.98230.96604.2588e-41050.97340.94727.2256e-413算例3.1重复实验结果计算次数x1*x2*F*n*11.00611.01072.4269e-4620.98850.97731.3624e-41231.00981.02133.9480e-41641.00591.01332.1228e-4851.00391.00651.7983e-41142模拟退火算法算例4.2实验结果x1*=0.9711,x2*=0.9448,F*=0.0011,n*=643模拟退火算法算例4.2重复实验结果算例3.2重复实验结果计算次数x1*x2*F*n*10.97110.94480.0011620.95980.92050.0017931.02011.03868.2588e-41741.00841.01562.4414e-41650.99320.97760.007911计算次数x1*x2*F*n*10.95630.91160.0028920.97860.95927.2158e-4931.05381.11030.0029941.01971.03660.0014550.96690.92730.0070444模拟退火算法算例4结果分析温度衰减系数减小，同一温度下计算次数增大，代表计算量从全局搜索向局部搜索调整。比较4.1和3.1的结果，前者解的质量下降，说明当全局搜索力量减少后，即使局部搜索很充分，也难免陷入早熟收敛。这是由渐进性收敛的算法机制所决定的。前文已述，随着计算的进展逐渐收缩搜索邻域范围可提高局部搜索的效果，但这样一来，预计会使全局搜索的效果更差，早熟收敛的现象更严重。究其根本，是由全局搜索和局部搜索的算法机制分工不明晰造成的。通过实验证明45模拟退火算法算例5Berlin52

旅行商问题（TSP）——有一个推销员，要到n个城市推销商品。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactlyonce)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。随机初值温度衰减系数：0.9同一温度下计算次数：100新解产生机制：随机选择两位交换终止条件：温度降到0.001以下2023/9/2346模拟退火算法算例5实验结果初始最小路程：26117.6727最终最小路程：9049.31072023/9/2347模拟退火算法算例5重复实验结果计算次数初始最小路程最终最小路程126117.67279049.3107228527.966010140.5852329896.22359258.2481429603.738410517.0181530460.80369931.8698630730.712010080.4342733165.207610240.6288826690.74009805.1238930206.77129104.27581030441.232710295.31182023/9/2348模拟退火算法算例5重复实验结果分析迭代中期即完成收敛，但对比遗传算法，结果并不好，因此是早熟收敛。2023/9/2349模拟退火算法算例6Berlin52

旅行商问题（TSP）——有一个推销员，要到n个城市推销商品。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactlyonce)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。随机初值温度衰减系数：0.8同一温度下计算次数：400新解产生机制：随机选择两位交换终止条件：温度降到0.001以下2023/9/2350模拟退火算法算例6重复实验结果计算次数初始最小路程最终最小路程129592.24849510.6520230016.46778675.1014331878.966410401.9821428111.13809667.1841531010.81849995.67092023/9/2351模拟退火算法算例6重复实验结果分析对比算例5的结果，没有显著变化。除了之前分析过的单点搜索、全局搜索和局部搜索机制不明晰等问题之外，随机选择两位交换的新解产生机制使搜索力量太弱。通过实验证明a=round(rand(1,2)*(N-1)+1);%产生两个随机位置用来交换W=S2(a(1));S2(a(1))=S2(a(2));S2(a(2))=W;%得到一个新路线2023/9/2352模拟退火算法实验结论计算结果对初值较敏感温度衰减系数、同一温度下计算次数、邻域范围等算法参数相互制约，对计算结果有较大影响全局搜索和局部搜索的算法机制分工不明晰，因此存在早熟收敛的现象与确定性算法（如牛顿法）相比，杀鸡用牛刀，效果未必好53遗传算法启发式规则模拟达尔文生物进化论的自然选择（优胜劣汰，适者生存）和遗传学机理（染色体的基因链结构及其交叉、变异）的生物进化过程。思路(Philosophy)染色体的基因链结构

编码/解码自变量空间中的表示

字符串或0/1串优胜劣汰

全局进化概率选择、交叉、变异

局部随机交叉、变异

全局搜索与局部搜索相结合，但机制并不独立54遗传算法算法流程需要确定的参数编码长度种群规模交叉概率变异概率需要确定的算法机制编码方式：传统为二进制选择方式：比例、轮盘赌、锦标赛、保留最优值…交叉方式：单点、多点变异方式：单点、多点终止规则：最大迭代次数、稳定次数、进化效率…55遗传算法算法流程编码问题：一元函数求最大值，精确到6位小数结论：编码的二进制串长应为22位编码原则：完备性（completeness）健全性（soundness）非冗余性（non-redundancy）问题空间与表达空间一一对应56遗传算法算法流程随机产生初始种群（二进制）个体评价解码，二进制

十进制计算适应度（目标函数值）预先设定种群规模适应度函数的条件：单值、连续、非负、最大化合理、一致性计算量小通用性强在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数的设计直接影响到遗传算法的性能。57遗传算法解码方法：（1）定义边界值（2）二进制

十进制（3）将十进制数对应到自变量定义域中比例系数58算法流程个体选择：GuidedRandomSearch轮盘赌（1）根据适应度值，计算每个个体被选中遗传的概率（2）计算每个个体的累积概率（3）在[0，1]区间内产生一个均匀分布的伪随机数d（4）若d<q1，则选择个体1；否则，选择个体k，使得qk-1<r≤

qk（5）重复步骤（3）和（4）若干次，构成Parents遗传算法59算法流程交叉（单点交叉）（1）选择一对Parents（2）确定交叉点位置（3）交叉，产生Children变异（单点变异）（1）选择变异个体（2）确定变异点位置（3）变异，产生新解遗传算法60遗传算法理论解g=1g=4g=10g=200算法实例61算法评价优点直接对结构对象操作，不存在求导和函数连续性的限定群体解迭代，具有内在的并行性和更好的全局寻优能力采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体初始值的影响有限遗传算法62算法评价缺点适应度函数值标定缺乏简洁、通用的方法不易对约束条件进行编码全局搜索和局部搜索功能不清晰由于变异率通常较低，存在早熟收敛的风险快要接近最优解时在最优解附近左右摆动，收敛较慢算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法遗传算法63算法改进适应度函数：例如，引入时间相关性和干扰，与SA结合选优方法：例如，精英选择搜索范围与搜索精度的平衡：例如，高位基因发生变异的概率逐渐降低，从而扮演局部搜索算子的角色采用自适应技术，在进化过程中动态调整算法控制参数和编码精度遗传算法64算法改进实例1：气垫车能耗优化问题基本算法

-染色体长度：11+11

-适应度指标：目标函数值的倒数

-算子：比例选择、单点交叉、多点

均匀变异

-参数：种群规模20，终止代数100，

交叉概率0.6，变异概率0.01遗传算法周科,罗哲,喻凡.基于遗传算法的半履带气垫车多参数优化[J].传动技术.2008,22(3):15-18+48+31.修改前每代最优修改前每代平均65算法改进实例1：气垫车能耗优化算法问题

-种群规模太小，使参数较优值和最优值出现的机会减小；

-比例选择算子降低了寻优的随机性，使某些劣势染色体的优质基因片断没有机会被保留下来； -选择和复制过程中，来源于相同父代的染色体在子代中的位置是相邻的，降低了交叉运算的效果，降低了收敛速度；

-变异概率为固定值，且染色体的每一个基因均有可能变异，这虽然有助于在优化初期产生较优的基因片断，但不利于优化后期结果的稳定性。遗传算法周科,罗哲,喻凡.基于遗传算法的半履带气垫车多参数优化[J].传动技术.2008,22(3):15-18+48+31.66算法改进实例1：气垫车能耗优化改进算法

-种群规模2040 -轮盘赌选择，解决随机性和个体排序问题

-自适应变异概率，前期加速进化，后期提高稳定性

-单点变异，后期提高稳定性 -最优个体保留，避免最优解退化遗传算法周科,罗哲,喻凡.基于遗传算法的半履带气垫车多参数优化[J].传动技术.2008,22(3):15-18+48+31.修改前每代最优修改后每代最优67遗传算法算例1二元函数求最小值，精确到4位小数定义域[-2,2]随机初值比例选择，总概率小于1多点变异，概率：0.1种群规模：100单点交叉，概率：0.6终止条件：100次迭代2023/9/2368遗传算法算例1实验结果x1*=1.0000,x2*=1.0000,F*=0,n*=4069遗传算法算例1重复实验结果计算次数x1*x2*F*n*11.00001.000004021.00001.000004530.99850.99692.3918e-069941.00001.00012.5373e-088751.00001.00000582023/9/2370遗传算法算例1重复实验结果分析各次计算的迭代过程和结果均不相同，这区别于确定性算法各次计算的初值对迭代结果无明显影响个别解存在100次迭代终止后解尚未完全收敛或早熟收敛的情况