模拟退火算法与遗传算法

1、第二章狭义计算智能优化计算/ 82确定性优化算法2022-2-222In computer science, a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. 给定初始条件后，搜索策略、过程和结果均确定。数值计算法/wik

2、i/Deterministic_algorithm/ 82确定性优化算法2022-2-22计算智能3NP完全问题的计算复杂度1 lg(n) n nlg(n) n2 . nk . 2n/ 822.3 启发式优化算法4混合优化证券投资组合：证券品种选择属于组合优化问题，买入卖出价位及时机决策属于函数（来自于数据挖掘的预测函数） 优化问题。思考：我们不可能掌握全部有用信息，也不可能建立这些信息对后市影响的明确的函数关系，那么如何投资？/ 82启发式优化算法5股票投资的启发式规则 历史数据 社会心理 K线走势 宏观经济情况 国家政策 / 82启发式优化算法6股票投资的结果 跑赢大盘 跑赢一年定期存款利

3、率 当然不是最优结果，但已经值得满意/ 82启发式优化算法2022-2-22计算智能7定义（Heuristics）p 一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题的一个满意的可行解，该可行解与最优解的偏离程度一般不能被预计。p : Heuristic refers to experience-based techniques for problem solving, learning, and discovery that find a solution which is not guaranteed to be optimal, but good

4、enough for a given set of goals. Where the exhaustive search is impractical, heuristic methods are used to speed up the process of finding a satisfactory solution via mental shortcuts to ease the cognitive load of making a decision./ 82启发式优化算法8特点p 启发式搜索规则：Strategies that guide the search processp 随机

5、性：每次计算都带有随机性，结果不保证p 综合优势：以利用较小的计算资源得到较好的可行解为目标p No Free Lunch Theorems假设有A、B两种任意（随机或确定）算法，对于所有问题集，它们的平均性能是相同的（性能可采用多种方法度量，如最优解、收敛速率等）。因此，要根据具体问题和性能要求选择合适的算法及其启发式搜索规则。The only viable option for a variety of complex optimization problems in NP-hardness经验、自然界、仿生/ 82启发式优化算法9发展p 研究热点p 算法的启发式规则不同p 有些算法缺乏严

6、格证明共性p 首先提出一个（组）候选解p 依据某些适应性条件测算这个（些）候选解的适应度（性能指标）p 根据适应度保留某些候选解，放弃其他候选解p 对保留的候选解进行某些操作，生成新的候选解/ 82启发式优化算法10分类p 搜索策略：局部搜索 or 全局搜索确定机制 or 学习机制p 迭代方法：单一解 or 群体解p 计算流程：serial or parallel or hybrid/ 82启发式优化算法11分类1: 搜索策略p 对简单局部搜索的改进simulated annealing (SA)tabu searchiterated local searchvariable neighbor

7、hood searchGRASPp 具有学习机制ant colony optimization (ACO)genetic algorithms (GA) Simulated evolutionary computation (SEC), 模拟进化计算局部搜索从一个初始解出发，搜索它的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。优点是简单、灵活及易于实现；缺点是容易陷入局部最优，且解的质量与初始解和邻域的结构密切相关。张雷, 范波. 计算智能理论与方法 M. 北京: 科学出版社. 2013: 13./ 82启发式优化算法12分类2: 迭代方法p Single solutions

8、imulated annealingiterated local searchp Population-basedInheritance: GAharmony search (HS)Contemporaries: particle swarm optimization (PSO)differential evolution (DE)Environment:ant colony optimization (ACO)binary bees algorithm (BBA)S. Xu, F. Yu, Z. Luo, Z. Ji, D.T. Pham, R. Qiu. Adaptive Bees Alg

9、orithm Bioinspiration from honeybee foraging to optimize fuel economy of a semi-track air-cushion vehicle J. The Computer Journal. 2011, 54(9): 1416-1426./ 82启发式优化算法2022-2-22计算智能13代表性算法p simulated annealing (SA)：模拟退火算法p genetic algorithms (GA)：遗传算法p ant colony optimization (ACO)：蚁群算法p particle swarm

10、 optimization (PSO)：粒子群算法p Bees algorithm (BA) and its variants：蜜蜂算法/ 82启发式优化算法2022-2-22计算智能14函数优化问题算例二元函数求最小值，精确到4位小数Rosenbrock function / 82启发式优化算法2022-2-22计算智能15组合优化问题算例Berlin52旅行商问题（旅行商问题（TSPTSP）有一个推销员，要到n个城市推销商品。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactly once)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。52 52D

11、5252个城市的个城市的位置坐标位置坐标/ 82模拟退火算法16启发式规则p 模拟退火算法来源于固体退火原理。将固体加热至充分高温后，让其慢慢冷却。加热时，固体内部粒子随温升变为无序状，内能增大；而慢慢冷却时粒子渐趋有序，在每个温度都有可能达到平衡态，最后在常温时达到基态，内能减为最小。/ 82模拟退火算法2022-2-2217/ 82模拟退火算法18算法流程及要素p 自变量空间中解x的更新机制目标函数值改进，绝对接受 优化进展目标函数值恶化，概率接受 摆脱局部最小值陷阱p 控制参数t的更新机制逐渐收敛，但具体方式多样劣解接受概率与t正相关 振荡范围逐渐变小，趋于稳定p 邻域定义及其更新机制思

12、考：如何在算法/程序中实现？/ 8219算例1.4结果初值x0=1.745，步长f xx nf n 结果：x= 1.6516，f= 3.6494，n=16结论：与固定步长相比，在收敛速度和计算精度之间求平衡。0.01, 0.0001思考：这种随机步长选择策略是否有问题？是否还有其他更好的步长选择策略，使收敛速度与计算精度的平衡性更好？/ 82模拟退火算法20算法评价p 优点具有渐进收敛性，概率性地收敛于全局最优解p 缺点参数（初始值、控制参数的更新机制等）敏感振荡范围单向收缩收敛速度与求全局最优解的要求相矛盾 全局搜索算子与局部搜索算子不独立/ 82模拟退火算法21算法改进p 根据具体问题的特

13、点，合理设计更具启发性的算法机制，例如当前解在解空间中的振荡范围不仅与搜索进程有关，还应该与解的更新效率与收益率有关p 增加重升温过程，动态调整当前解在解空间中的振荡范围，从而避免算法在局部极小解处停滞不前或在计算后期收敛速度太慢p 增加记忆功能，避免当前最优解衰退p 参考群智能的思想，针对每一个当前状态x，采用多次搜索策略，以概率方式进行当前最优解的更新，而非传统的单次比较/ 82模拟退火算法22算例1二元函数求最小值，精确到4位小数 定义域 -2, 2 初始温度：100 温度衰减系数：0.95 同一温度下计算次数：50 邻域范围系数：0.2 终止条件：温度降低到1以下 算例x.1: 初值x

14、10=0.5, x20=0.5 算例x.2: 初值x10=-0.5, x20=0.5/ 82模拟退火算法23算例1.1实验结果x1*=0.9837, x2*=0.9684, F*=3.1438e-4, n*=10/ 82模拟退火算法2022-2-2224算例1.1重复实验结果计算次数x1*x2*F*n*10.98370.96843.1438e-41021.01701.03688.9150e-4531.04591.09280.0022840.96800.93240.00321250.98470.97860.008212/ 82模拟退火算法25算例1.2实验结果x1*=1.0288, x2*=1.

15、0577, F*=8.7113e-4, n*=20/ 82模拟退火算法2022-2-2226算例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-414/ 82模拟退火算法2022-2-2227算例1结果分析 由于是单值迭代，且渐进收敛，因此存在早熟收敛的问题，表现为以上计算均没有找到全局最优解 初值对迭代结果无明显影响/ 82模拟退火算法28算例2二元函数求最小值，精确到

16、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.5/ 82模拟退火算法29算例2.1实验结果x1*=1.1089, x2*=1.2319, F*=0.0124, n*=6/ 82模拟退火算法2022-2-2230算例2.1重复实验结果计算次数x1*x2*F*n*11.10891.23190.0124620.95350.92210.0186930.86350.74870.0196541.097

17、61.19850.0135850.92190.83730.02218/ 82模拟退火算法31算例2.2实验结果x1*=0.9209, x2*=0.8505, F*=0.0068, n*=6/ 82模拟退火算法2022-2-2232算例2.2重复实验结果计算次数x1*x2*F*n*10.92090.85050.0068620.90390.82320.0130831.01951.03240.0052741.11921.27180.0509751.00481.01440.002411/ 82模拟退火算法2022-2-2233算例2结果分析 与算例1相比，初值改变后，迭代次数没有发生显著变化。原因在于

18、，邻域范围与定义域范围成正比，在较大的定义域范围下，初值的变化量是一个相对小量。 与算例1相比，解的质量更为恶化，早熟收敛的问题更为突出。其原因还是在于较大的邻域范围，导致新解的变化量大，起不到局部搜索的作用。 希望通过下调最低温度来实现局部搜索NextX1=PreX1+StepFactor*X1MAX*(rand-0.5);NextX2=PreX2+StepFactor*X2MAX*(rand-0.5);/ 82模拟退火算法34算例3二元函数求最小值，精确到4位小数 定义域 -10, 10 初始温度：100 温度衰减系数：0.95 同一温度下计算次数：50 邻域范围系数：0.2 终止条件：温

19、度降低到0.01以下 算例x.1: 初值x10=0.5, x20=0.5 算例x.2: 初值x10=-0.5, x20=0.5/ 82模拟退火算法35算例3.1实验结果x1*=1.0061, x2*=1.0107, F*=2.4269e-4, n*=6/ 82模拟退火算法36算例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*x

20、2*F*n*11.10891.23190.0124620.95350.92210.0186930.86350.74870.0196541.09761.19850.0135850.92190.83730.02218/ 82模拟退火算法37算例3.2实验结果x1*=0.9563, x2*=0.9116, F*=0.0028, n*=9/ 82模拟退火算法38算例3.2重复实验结果计算次数x1*x2*F*n*10.95630.91160.0028920.97860.95927.2158e-4931.05381.11030.0029941.01971.03660.0014550.96690.92730

21、.00704算例2.2重复实验结果计算次数x1*x2*F*n*10.92090.85050.0068620.90390.82320.0130831.01951.03240.0052741.11921.27180.0509751.00481.01440.002411/ 82模拟退火算法39算例3结果分析 与算例2相比，解的质量有所提高，早熟收敛问题有所改善。这说明下调最低温度能够在迭代后期、在一定程度上起到局部搜索的作用。 但是，下调最低温度只是让变化程度小的解有了相对更大的存活几率，但它无法控制变化程度小的解的产生（要靠收缩搜索邻域范围实现）。 因此，依靠下调最低温度在迭代后期起到局部搜索的作

22、用，也只是治标不治本的办法。 比较3.1和3.2的结果，初值对解的影响有所显现。/ 82模拟退火算法40算例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.5/ 82模拟退火算法41算例4.1实验结果x1*=0.9395, x2*=0.8829, F*=0.0037, n*=10/ 82模拟退火算法42算例4.1重复实验结果计算次数x1*

23、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-411/ 82模拟退火算法43算例4.2实验结果x1*=0.9711, x2*=

24、0.9448, F*=0.0011, n*=6/ 82模拟退火算法44算例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.00704/ 8

25、2模拟退火算法45算例4结果分析 温度衰减系数减小，同一温度下计算次数增大，代表计算量从全局搜索向局部搜索调整。 比较4.1和3.1的结果，前者解的质量下降，说明当全局搜索力量减少后，即使局部搜索很充分，也难免陷入早熟收敛。这是由渐进性收敛的算法机制所决定的。 前文已述，随着计算的进展逐渐收缩搜索邻域范围可提高局部搜索的效果，但这样一来，预计会使全局搜索的效果更差，早熟收敛的现象更严重。 究其根本，是由全局搜索和局部搜索的算法机制分工不明晰造成的。通过实验证明/ 82模拟退火算法2022-2-2246算例5Berlin52旅行商问题（旅行商问题（TSPTSP）有一个推销员，要到n个城市推销商品

26、。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactly once)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。 随机初值 温度衰减系数：0.9 同一温度下计算次数：100 新解产生机制：随机选择两位交换 终止条件：温度降到0.001以下/ 82模拟退火算法2022-2-2247算例5实验结果初始最小路程：26117.6727最终最小路程： 9049.3107/ 82模拟退火算法2022-2-2248算例5重复实验结果计算次数 初始最小路程最终最小路程126117.67279049.3107228527.966010140.5852329896.22

27、359258.2481429603.738410517.0181530460.80369931.8698630730.712010080.4342733165.207610240.6288826690.74009805.1238930206.77129104.27581030441.232710295.3118/ 82模拟退火算法2022-2-2249算例5重复实验结果分析 迭代中期即完成收敛，但对比遗传算法，结果并不好，因此是早熟收敛。/ 82模拟退火算法2022-2-2250算例6Berlin52旅行商问题（旅行商问题（TSPTSP）有一个推销员，要到n个城市推销商品。各城市之间的距离已知

28、，要求以最短路线将每个城市访问且只访问1次(exactly once)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。 随机初值 温度衰减系数：0.8 同一温度下计算次数：400 新解产生机制：随机选择两位交换 终止条件：温度降到0.001以下/ 82模拟退火算法2022-2-2251算例6重复实验结果计算次数 初始最小路程最终最小路程129592.24849510.6520230016.46778675.1014331878.966410401.9821428111.13809667.1841531010.81849995.6709/ 82模拟退火算法2022-2-2252算

29、例6重复实验结果分析 对比算例5的结果，没有显著变化。 除了之前分析过的单点搜索、全局搜索和局部搜索机制不明晰等问题之外，随机选择两位交换的新解产生机制使搜索力量太弱。通过实验证明a=round(rand(1,2)*(N-1)+1); %产生两个随机位置 用来交换W=S2(a(1);S2(a(1)=S2(a(2);S2(a(2)=W; %得到一个新路线/ 82模拟退火算法53实验结论 计算结果对初值较敏感 温度衰减系数、同一温度下计算次数、邻域范围等算法参数相互制约，对计算结果有较大影响 全局搜索和局部搜索的算法机制分工不明晰，因此存在早熟收敛的现象 与确定性算法（如牛顿法）相比，杀鸡用牛刀，

30、效果未必好/ 82遗传算法54启发式规则p 模拟达尔文生物进化论的自然选择（优胜劣汰，适者生存）和遗传学机理（染色体的基因链结构及其交叉、变异）的生物进化过程。p 思路 (Philosophy)染色体的基因链结构 编码/解码自变量空间中的表示字符串或0/1串优胜劣汰 全局进化概率选择、交叉、变异 局部随机交叉、变异 全局搜索与局部搜索相结合，但机制并不独立/ 82遗传算法55算法流程p 需要确定的参数编码长度种群规模交叉概率变异概率p 需要确定的算法机制编码方式：传统为二进制选择方式：比例、轮盘赌、锦标赛、保留最优值交叉方式：单点、多点变异方式：单点、多点终止规则：最大迭代次数、稳定次数、进化

31、效率/ 82遗传算法56算法流程p 编码问题：一元函数求最大值，精确到6位小数结论：编码的二进制串长应为22位编码原则： 完备性（completeness） 健全性（soundness） 非冗余性（non-redundancy）问题空间与表达空间一一对应/ 82遗传算法57算法流程p 随机产生初始种群（二进制）p 个体评价解码，二进制 十进制计算适应度（目标函数值）预先设定种群规模s1000101110110101000111 x0.637197 f(x)xsin(10 x)2.02.586345适应度函数的条件： 单值、连续、非负、最大化 合理、一致性 计算量小 通用性强在具体应用中，适应度

32、函数的设计要结合求解问题本身的要求而定。适应度函数的设计直接影响到遗传算法的性能。/ 82遗传算法58解码方法：（1）定义边界值（2）二进制 十进制（3）将十进制数对应到自变量定义域中比例系数/ 82算法流程p 个体选择：Guided Random Searchp 轮盘赌（1）根据适应度值，计算每个个体被选中遗传的概率（2）计算每个个体的累积概率（3）在0，1区间内产生一个均匀分布的伪随机数d（4）若d q1，则选择个体1；否则，选择个体k，使得qk-1 r qk（5）重复步骤（3）和（4）若干次，构成Parents遗传算法59/ 82算法流程p 交叉（单点交叉）（1）选择一对Parents（

33、2）确定交叉点位置（3）交叉，产生Childrenp 变异（单点变异）（1）选择变异个体（2）确定变异点位置（3）变异，产生新解遗传算法60/ 82遗传算法61理论解g=1g=4g=10g=200算法实例/ 82算法评价p 优点直接对结构对象操作，不存在求导和函数连续性的限定群体解迭代，具有内在的并行性和更好的全局寻优能力采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体初始值的影响有限遗传算法62/ 82算法评价p 缺点适应度函数值标定缺乏简洁、通用的方法不易对约束条件进行编码全局搜

34、索和局部搜索功能不清晰由于变异率通常较低，存在早熟收敛的风险快要接近最优解时在最优解附近左右摆动，收敛较慢算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法遗传算法63/ 82算法改进p 适应度函数：例如，引入时间相关性和干扰，与SA结合p 选优方法：例如，精英选择p 搜索范围与搜索精度的平衡：例如，高位基因发生变异的概率逐渐降低，从而扮演局部搜索算子的角色p 采用自适应技术，在进化过程中动态调整算法控制参数和编码精度遗传算法64/ 82算法改进p 实例1：气垫车能耗优化问题基本算法-染色体长度：11+11-适应度指标：目标函数值的倒数-算子：比例选择、单点交叉、多点均匀变异-参数

35、：种群规模20，终止代数100，交叉概率0.6，变异概率0.01遗传算法65(, )ssfQQ nv周科, 罗哲, 喻凡. 基于遗传算法的半履带气垫车多参数优化 J. 传动技术. 2008, 22(3): 15-18+48+31.修改前每代最优修改前每代平均/ 82算法改进p 实例1：气垫车能耗优化算法问题-种群规模太小，使参数较优值和最优值出现的机会减小；-比例选择算子降低了寻优的随机性，使某些劣势染色体的优质基因片断没有机会被保留下来；-选择和复制过程中，来源于相同父代的染色体在子代中的位置是相邻的，降低了交叉运算的效果，降低了收敛速度； -变异概率为固定值，且染色体的每一个基因均有可能变

36、异，这虽然有助于在优化初期产生较优的基因片断，但不利于优化后期结果的稳定性。遗传算法66周科, 罗哲, 喻凡. 基于遗传算法的半履带气垫车多参数优化 J. 传动技术. 2008, 22(3): 15-18+48+31./ 82算法改进p 实例1：气垫车能耗优化改进算法-种群规模2040-轮盘赌选择，解决随机性和个体排序问题-自适应变异概率，前期加速进化，后期提高稳定性-单点变异，后期提高稳定性-最优个体保留，避免最优解退化遗传算法67周科, 罗哲, 喻凡. 基于遗传算法的半履带气垫车多参数优化 J. 传动技术. 2008, 22(3): 15-18+48+31.修改前每代最优修改后每代最优/

37、82遗传算法2022-2-2268算例1二元函数求最小值，精确到4位小数 定义域 -2, 2 随机初值 比例选择，总概率小于1 多点变异，概率：0.1 种群规模：100 单点交叉，概率：0.6 终止条件：100次迭代/ 82遗传算法69算例1实验结果x1*=1.0000, x2*=1.0000, F*=0, n*=40/ 82遗传算法2022-2-2270算例1重复实验结果计算次数x1*x2*F*n*11.00001.000004021.00001.000004530.99850.9969 2.3918e-069941.00001.0001 2.5373e-088751.00001.00000

38、58/ 82遗传算法2022-2-2271算例1重复实验结果分析 各次计算的迭代过程和结果均不相同，这区别于确定性算法 各次计算的初值对迭代结果无明显影响 个别解存在100次迭代终止后解尚未完全收敛或早熟收敛的情况 个别解接近但达不到全局最优解（即陷在窄带内不能继续优化），说明优化后期缺乏有效的局部搜索机制，原因在于变异位太多/ 82遗传算法2022-2-2272算例2二元函数求最小值，精确到4位小数 定义域 -4, 4 随机初值 比例选择，总概率小于1 多点变异，概率：0.1 种群规模：100 单点交叉，概率：0.6 终止条件：100次迭代/ 82遗传算法73算例2实验结果x1*=0.686

39、3, x2*=0.4687, F*=0.0989, n*=42/ 82遗传算法2022-2-2274算例2重复实验结果计算次数x1*x2*F*n*10.68630.46870.09894220.98440.9687 3.0000e-046431.00001.000008041.00001.00000550.98440.9690 2.0000e-0437/ 82遗传算法2022-2-2275算例2重复实验结果分析 大量存在早熟收敛的现象，变量取值范围对优化结果影响很大 早熟收敛说明算法缺乏有效的全局搜索机制。采用比例选择策略，当在进化早期出现一个优势个体后，其他个体没有机会被选择，因此很容易消除

40、基因多样性，进而使交叉操作失去作用 部分解接近但达不到全局最优解（即陷在窄带内不能继续优化），说明优化后期缺乏有效的局部搜索机制，原因在于变异位太多/ 82遗传算法2022-2-2276算例3.1二元函数求最小值，精确到4位小数 定义域 -2, 2 随机初值 比例选择，总概率小于1 多点变异，概率：0.1 单点交叉，概率：0.6 种群规模：40 终止条件：250次迭代（总计算量平衡）/ 82遗传算法77算例3.1实验结果x1*=0.9980, x2*=0.9961, F*=4.3991e-06, n*=62/ 82遗传算法2022-2-2278算例3.1重复实验结果计算次数x1*x2*F*n*

41、10.99800.9961 4.3991e-066220.99220.9844 1.0000e-041631.00001.0001 2.5373e-0815040.99990.9999 2.9087e-0822350.93750.87900.003918/ 82遗传算法2022-2-2279算例3.1重复实验结果分析 与算例1的结果相比有所恶化 主要矛盾是局部搜索机制不足 迭代次数已足够多，但种群规模太小，容易丧失基因多样性 迭代达到一定次数时结果已收敛，之后是计算量的浪费，因此应采用更灵活的迭代终止策略/ 82遗传算法2022-2-2280算例3.2二元函数求最小值，精确到4位小数 定义域

42、-2, 2 随机初值 比例选择，总概率小于1 多点变异，概率：0.1 单点交叉，概率：0.6 种群规模：20 终止条件：500次迭代（总计算量平衡）/ 82遗传算法81算例3.2实验结果x1*=1.0019, x2*=1.0040, F*=4.2816e-06, n*=320/ 82遗传算法2022-2-2282算例3.2重复实验结果计算次数x1*x2*F*n*11.00191.0040 4.2816e-0632021.00001.0001 2.5373e-0839231.00781.0157 1.0000e-0425840.99970.9996 6.4836e-0747451.00001.0

43、000047/ 82遗传算法2022-2-2283算例3.2重复实验结果分析 存在算例3.1结果中所述的问题 但在迭代后期仍可能发生进化，这是相对于模拟退火算法的优势/ 82遗传算法84实验结论 在各种实验条件下，早熟收敛、达不到全局最优解是一个共性问题。之前的分析认为，因变异位太多而导致的在优化后期缺乏有效的局部搜索机制，是引起上述问题的主要原因。 但是，无论将多点变异改为单点变异，还是降低变异率（这些措施看起来都是在加强局部搜索机制），结果都更加恶化。 究其根本原因，还是全局搜索和局部搜索的算法机制分工不明晰。/ 82遗传算法2022-2-2285算例4 随机初值 轮盘赌选择，概率：0.9

44、 单点变异，概率：0.05 种群规模：200 两点交叉，概率：0.9 终止条件：200次迭代Berlin52旅行商问题（旅行商问题（TSPTSP）有一个推销员，要到n个城市推销商品。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactly once)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。/ 82遗传算法2022-2-2286算例4实验结果初始最小路程：31749.7089最终最小路程：10159.6675/ 82遗传算法2022-2-2287算例4重复实验结果计算次数 初始最小路程最终最小路程131749.708910159.6675231823

45、.06719413.8526328810.74178646.1665429600.30749591.5999530122.85139465.8913628325.70059442.2367730992.946510287.0539832013.04938671.077931871.74419835.70591027206.978310105.522/ 82遗传算法2022-2-2288算例4重复实验结果分析 各次计算的迭代过程和结果均不相同，区别于确定性算法 重复实验的算法稳定性较好 各次计算的初值对迭代结果无明显影响 对于此算例，200次迭代终止后解尚未完全收敛/ 82遗传算法2022-2-

46、2289算例5.1 随机初值 轮盘赌选择，概率：0.9 单点变异，概率：0.05 种群规模：50 两点交叉，概率：0.9 终止条件：800次迭代（总计算量平衡）Berlin52旅行商问题（旅行商问题（TSPTSP）有一个推销员，要到n个城市推销商品。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactly once)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。/ 82遗传算法2022-2-2290算例5.1实验结果初始最小路程：28424.5588最终最小路程： 8027.5413/ 82遗传算法2022-2-2291算例5.1重复实验结果计算次数 初始最小路程最终最小路程128424.55888027.5413228446.62968174.7340331328.70478059.8033428258.73578638.993352782