❖ 优化模块 ❖

优化模块

1.功能介绍

在工程系统的规划设计阶段以及建成后的运营阶段，工程人员一直都面临着对构成系统方案的各种工程设计参数、运营参数的选择问题。对这些设计参数的每一次具体取值，就形成了一个具体的工程项目规划方案、或者系统运营方案。不同的参数选择方案，就对应着不同的设计和运营方案，由此，工程设计人员可以对比多个不同设计方案的绩效，以获得优选的系统方案。

在实际工程应用中，每个设计参数都会有多个不同取值，这些参数的取值选择组合就构成了设计方案或者项目运营方案的方案空间（决策空间）。通常工程系统的方案空间的规模都是巨大的。假定一个工程设计项目由15个设计变量构成，每一个变量参数有5个取值可能，那么这个项目的方案解空间规模即为15个5相乘：

5*5***—**5 =  30,517,578,125

对一个工程项目来说，仅有15个设计参数，通常是一个很小规模的设计，但其形成的方案空间规模，已经是相当巨大的。当系统的仿真模型建好后，使用这些参数取值，就可以在计算机内快速仿真一次工程系统的设计或运营效果，快速获得该方案的各种绩效水平，用于不同方案的绩效对比寻优，即使一次仿真运行速度很快，也要消耗一定的现实时间，哪怕是几微妙，当项目的方案空间巨大时，消耗的现实时间也是相当可观，有些情况下寻优工作甚至是不可实现的。

BHTC Simulation系统提供了本优化功能模块，协助用户灵活地选择和管理优化变量，通过增加设计约束，合理的控制方案空间规模，并提供多种方案寻优策略，协助用户，快速地获得系统设计或运营的优选方案。

使用BHTC Simulation优化功能，由以下步骤与内容构成：

• 首先建好一个用于优化目的的仿真模型

通过以上分析可知，工程项目的方案空间规模直接由项目的设计变量个数、及其变化的范围决定的，因此在建立项目的仿真模型时，就要围绕优化目标，调研项目运作流程，明晰模型边界，将那些与项目绩效水平关联度高的因素，纳入到模型中来，减少无关因素，或对项目绩效影响不敏感的因素，对方案空间的贡献，从而提高方案寻优的效率。

另一方面，由于仿真建模是一项个性化、主观性都很强的工作。即面对同一个项目流程，和同一个优化目标，不同的建模工程师，都会按照各自对建模任务不同的理解，建立其各自不同的仿真模型。面对同一个对项目运作流程，不同的建模抽象，往往对应着不同的、有时甚至是天差地别的方案空间。

比如某项工程需要20个人工，每个工人可以有上午班、下午班、晚班、夜班等4种班次可能，那么实施这项工程的人员-班次的组合空间共有多少种可能，即是这个问题的方案空间。如果以人员为核心分析该问题，则方案空间就是：4*4*4*………….4，即20个4相乘，结果是一个巨大的天文数字；如果以班次为核心分析该工程项目的人员-班次组合，每个班次的人员变化可能只有20种，即每个班次可以有1个人直到20个人的可能取值，班次只有4个，那么该问题的方案空间就是20*20*20*20 = 160000。显然，第二种方法可获得一个可以进行快速寻优的方案空间。

因此，在建模阶段，有必要尝试多种不同的建模策略，通过对比分析以获得既能满足建模任务需求，又具有较高寻优效率的流程模型。

• 定义目标函数

目标函数是工程系统的性能指标与设计变量或者运营参数之间的函数关系。比如，设计一条生产线，设计者希望获得一个较高的产能指标、产线的运营方，希望获得一个较高的利润水平、或者是一个较高的客户满足度水平，就需要根据特定的领域知识，建立这些绩效指标与系统设计变量之间的函数关系表达式，即目标函数。

在BHTC Simulation系统中，就是使用“Function”建模元素来表达目标函数，如前文所述，目标函数表达的是系统绩效指标与设计变量之间的函数关系，这些设计变量通常就是模型结构树上的全局变量节点，在书写目标函数表达式时，可直接双击模型结构树上的变量节点，直接在目标函数表达式中引用它们，因此，目标函数通常不再需要形式参数。简言之：目标函数就是用户使用“Function”建模元素定义的那些具有整型、实型返回值，并且不带形参的函数。

因为考察系统绩效的目标函数，是在系统经过一段时间运营后才被观察的，即目标函数只在仿真周期完成的时刻，自动被系统调用。

• 选择优化变量

优化变量就是指工程系统中那些设计变量或者运营参数，它们的变化，对系统的绩效指标具有显著的影响，这样的设计变量有必要被选为方案寻优时的优化变量。在选用之前，可以预先运行仿真实验，在保持其他设计变量取值不变的情况下，观察该变量在其取值范围内变化时，对系统绩效指标的影响程度。如果对绩效指标的影响很小，在1%以内，这样的变量不必要作为优化变量（这一取舍的阀值可根据不同的领域任务而有所差别），从而尽可能的减少方案空间的寻优规模。

• 设计约束条件

为进一步缩减方案空间规模，更为有效的方法是利用工程约束，排除掉那些明显不合理的参数组合，即只有那些符合工程约束条件的参数组合，才被纳入到方案空间内，用于方案寻优。

通过增加设计约束来减少方案空间，在实践应用中是一个非常有效且高效的寻优方法。因此，在实际应用中，尽可能多的利用领域知识，为方案寻优，设计出多个约束条件，它们就像一把把筛子一样，过滤掉巨量的不合理的参数组合。

• 选择优化策略

BHTC Simulation优化功能模块，提供了多种方案空间寻优策略算法，比如全空间搜索（All Combination）、模拟退火算法、随机搜索策略等等，用于方案寻优。每一种方法都有其自身的局限和特长，具体应用时，需综合考虑具体问题的方案空间规模、可接受的寻优耗时等等因素酌情选择使用。

• 方案寻优

最后设定好每一寻优的仿真周期，评估完成寻优过程的大致时间，启动寻优功能按钮开始寻优搜索。优化功能模块会以图形、报表的形式展示出方案寻优的过程，直至获得最优结果或者完成整个方案空间的搜索而结束寻优过程。

以下，结合一个具体的产线规划设计案列，介绍BHTC Simulation软件优化功能模块的使用。案例内容如下：（该案例模型文件详见本系统安装主目录下Demo子目录下的“case_生产线规划设计.BHsim”文件）。

【案例1】生产线规划设计

• 产线规划描述

某车间生产线的加工过程由三道工序构成，以下简称工序1，工序2、工序3以及操作这三道工序的一组员工。其中工序1设备的加工节拍服从（8,12）分钟均匀分布，加工时需要1名员工操作；工序2设备的加工节拍服从（10,15）分钟均匀分布，加工时需要2名员工操作；工序3设备的加工节拍服从（6,10）分钟均匀分布，加工时需要1名员工操作。该产线规划模型结构与设施布局如下图所示。在模型中分别使用“Machine1”、“Machine2”、“Machine3”元素代表这三道工序上的设备，使用“Labor1”元素代表班组员工，使用“Camp1”、“Camp2”、“Camp3”、“Camp4”分别代表员工的营地和他们的工作地点。产线开工时，“工序1”的设备从外部世界抓取零件毛坯“Part1”开始加工，并且生产过程中始终有料（即设置“Part1”为“Passive”类型的“Part”元素），完成后依次“Push to”下一道工序设备上继续加工。

工序1设备的每分钟运行成本为2.8元，产线可配备的数量在2，6之间；工序2设备的每分钟运行成本为7.5元，产线可配备的数量在1，6之间；工序3设备的每分钟运行成本为5.6元，产线可配备的数量在2，5之间。

员工的每分钟使用成本为4.5元，产线可配备的数量在3，8之间

由于车间场地限制，三道工序累计至多可以放置12台机器设备。

生产线每产出一个零件的产值为1000元。

试规划上述生产线，考察产线运行3天，使得产线产出利润最大化。

2.优化变量配置

启动BHTC Simulation软件，打开上述产线规划模型，模型完成后，点击软件主界面“控制面板”上左下角上的“优化配置”页签按钮，如下图红色箭头所示：

点击“优化配置”按钮后，系统将软件控制面板界面切换至系统的“优化配置”菜单区，如下图所示：

在模型结构树区域，展示出了该产线规划模型可用于选择优化变量的所有模型节点。鼠标点击模型结构树上的“Machine1”节点，系统展示出该设备节点可用做优化变量的元素：“Quantity”、“Cycle_Time”如下图所示。即“Machine”元素的数量、加工时间可被选作优化变量，在BHTC Simulation系统进行方案寻优时，这些变量的值可在其定义的范围内变化，从而形成产线规划方案空间中不同的解。

双击“Quantity”节点，即选择“工序1”设备的数量作为优化变量，系统弹出优化变量定义界面如下图所示：

在变化范围“Range”框下，输入“工序1”设备的变化范围：最小值2，最大值6，方案寻优时，该变量的变化步长“1”。然后点击“确定”按钮，完成对“工序1”设备优化变量的选择，该变量信息，随即显示在优化变量列表中。

依次类推，按照题意分别定义“工序2”、“工序3”设备的数量、班组员工“Labor1”的数量为优化变量，如下图所示：

BHTC Simulation系统的每个仿真建模元素，可作为优化变量使用的属性值内容如下表所示：

元素名称	优化变量	元素属性描述
Part	MaxNum	Part元素实例的最大数量
	First Arrival	Part元素实例首次进入模型系统时间
	Interval	Part元素实例到达间隔
Machine	Quantity	机器设备数量
	Cycle_Time	加工循环时间
Buffer	Quantity	库存设备数量
	Capacity	库存容量
Vehicle	Quantity	车辆数量
	Capacity	车载容量
	Unload_Speed	空载速度
	Load_Speed	满载速度
Track	Capacity	轨道容量
	Physical_Length	轨道长度
Conveyor	Capacity	传送带容量
	Physical_Length	传送带长度
	Speed	传送带运行速度
Labor	Quantity	员工数量
	Speed	行走速度
Path	Physical_Length	路径长度
	Capacity	道路容量
Fluid	First_arrival	初始进入模型系统时间
	Speed	流速
Pipe	Capacity	管道容量
	Speed	额定流速
Tank	Initial_Vol	储罐初始容量
	Capacity	储罐罐容
Processor	Process_Time	处理器反应时间
	Capacity	处理器容量
Variable	Value	单变量（整型、实型）值

【注意】

在启动BHTC Simulation优化功能模块进行方案寻优，每次寻优仿真进行之前，系统首先根据上述定义的、优化变量取值范围，逐一给每个优化变量赋值，然后激活仿真模型运行，获得在该取值方案下的系统绩效。但运行仿真模型时，同样也会激活用户在建立产线规划模型时，设置在“初始化action”代码框中的模型初始化代码的运行（详见“模型初始化”一节的内容），而这些代码的作用就是用来给模型中变量、或模型中元素的属性值进行赋值，这样就会产生冲突。因此，为避免同一个变量或者元素属性被二次赋值的冲突，在BHTC Simulation系统中规定，当系统进入方案寻优运行模式时，对变量、元素属性的赋值以优化功能的赋值为优先。具体执行次序如下：

1. 对于模型中的变量，如果该变量被选作为优化变量，则该变量不再使用其建模时定义的初始值，对它进行初始化赋值，而交由优化模块，在每次方案寻优时，按照当时的该变量的寻优取值对其进行初始化赋值。

2. 对于模型中的变量，如果该变量被选作为优化变量，则其在“初始化action”代码中的赋值语句被禁用，但仍可在其他变量的赋值表达式中被引用。

3. 对于模型中的元素属性，如果该属性被选作优化变量，那么在该属性在每次仿真前，交由优化模块，在每次方案寻优时，按照当时的该属性的寻优取值对其进行赋值，而“初始化action”代码中的有关该属性的赋值语句被禁用。

3.约束条件设计

如前文所示，为缩减方案空间规模，更为有效的方法是利用工程约束，排除掉那些明显不合理的参数组合方案，从而避免不必要的时间花费，快速获得寻优结果。同样的，对本案例，“由于车间场地限制，三道工序累计至多可以放置12台机器设备”，这就是一条工程约束，接下来，我们将这一约束条件建立到优化功能的参数设置中去。点击软件控制面板“优化配置”界面底部的“约束定义按钮”，如下图所示：

弹出软件“约束定义”对话框，如下图所示：

本案例的工程约束，使用优化变量表述就是：“Machine1”设备的数量Quantity + “Machine2”设备的数量Quantity +“Machine3”设备的数量Quantity <= 12。 因此，鼠标左键点选上图右侧优化变量列表中的“Machine1”元素的Quantity变量，接着单击鼠标右键系统弹出“选用”下拉菜单，点选后，该变量便出现在约束“Constrain”定义框的列表中，如下图所示：

在“变量系数”下的文本框中输入该变量在约束条件表达式中的系数“1”， 依次分别选用优化变量列表中的“Machine2”的Quantity变量、“Machine3”的Quantity变量，然后在条件定义框中输入“12”，并选择“<=”左边的可选框，最后点击上方“Constrain”定义框中的“添加”按钮，最后约束条件表达式：

“Machine1”设备数量Quantity + “Machine2”设备的数量Quantity +“Machine3”设备的数量Quantity <= 12

便出现在左上角的“Constrain”定义框中，从而完成本案工程约束的定义。如下图所示：

至此，完成了本案例的“优化变量”选取及“工程约束”的定义工作，因为产线方案的优化设计，是一个循环往复的过程，因此BHTC Simulation系统提供了文件保存功能，这些信息可以文件的形式单独保存起来。点击系统“优化配置”界面底部的“保存文件”按钮，如下图所示，进行优化信息的保存，以供以后使用。

【备注】

优化信息的文件保存格式为*.BHopt，文件保存时可使用与模型文件相同的文件名，这样当启动BHTC Simulation系统打开模型文件时，与模型文件名同名的优化信息文件也一同被打开使用。

4.目标函数定义

在启动方案寻优功能之前，还需要定义方案寻优的目标函数。对于本案例，就是该产线营业利润的函数表达式，方案寻优的目的就是寻找使得产线营业利润最大化的设计方案。产线的营业利润 = 产线的产值 – 产线的营业成本。按照这一原理，打开本案例的模型文件，在原来的模型结构树上定义一个名为“Profit”的函数节点，函数体的内容如下图所示：

产线的运营成本由设备使用成本、人工使用成本构成、函数体中，分别定义了代表着两种成本的局部变量：cost_Maci、cost_Labor。其计算表达式定义，设备的使用成本表达式，以工序1设备使用成本cost_Mac1为例：

cost_Mac1 = 2.8*System_Machine_Work_T(“Machine1”)

表达式中，“2.8”是工序1设备每分钟的使用成本，System_Machine_Work（）是系统内部函数，它返回的是其形参“Machine1”设备在仿真周期内累计的工作时长。如果“Machine1”是由几台相同设备构成的成组设备，该函数就返回该成组设备，在仿真周期内总计的工作时间。显然通过这个计算表达式，就可以计算出，在当前这个方案下，工序1设备的使用成本。

人工使用成本cost_Labor的表达式如下：

cost_Labor = System_Labor_Work_T(“MM_Model_Labor1”)*4.5

表达式中，“4.5”是班组员工每分钟的使用成本，同样地，System_Labor_Work（）是系统内部函数，它返回的是所有班组员工“Labor1”在仿真周期内总计的工作时长。

产线的产值由局部变量“Revenue”表示，其表达式为：

Revenue = System_Part_NSHIP(“Part1”)*1000

表达式中“1000”是每产出一件产品的价值，System_Part_NSHIP是系统内部函数，它返回的是在仿真周期终止时刻“Part1”零件的产出数量。

这样，我们就得到了本案例目标函数产值营业利润Profit的表达式：

Profit = Revenue – cost_Mac1 – cost_Mac2 – cost_Mac3 – cost_Labor

5.方案寻优

完成上述准备工作后，接下来就可以开始本产线规划设计的方案寻优过程。点击软件主界面“控制面板”上左下角上的“方案寻优”页签按钮，如下图红色箭头所示：

点击“方案寻优”按钮后，系统将软件控制面板界面切换至系统的“方案寻优”菜单区，如下图所示：

与此同时，原来的屏幕右侧的模型布局区窗口隐藏，出现了两个新的窗口：

“OPT结果”窗口：该窗口用于以列表的形式展示出在进行方案寻优过程中，所遍历的每一个设计方案的配置参数。其中序号列对应的是方案的序号，“Results”列对应着每一个方案仿真运行结束后计算出的目标函数的结果，其余各列分别对应着该方案优化变量的具体取值。

“OPT运行”窗口：该窗口绘制了寻优过程中目标函数曲线，以曲线的形式展示出系统寻优的过程，曲线的横轴代表寻优方案序号，曲线的纵轴代表寻优的目标函数结果。缺省的情况下，系统只连续展示出100个方案的寻优结果曲线。每当展示的方案数量超过100个时，图形便被刷新，重新开始展示下一个轮次的100个方案的寻优情况。每个轮次展示方案的数量，可在“方案寻优”界面中“Display”控制面板中的“显示样本数”输入框中进行定义。

如果要观察全部寻优方案目标函数曲线的变化情况，在寻优结束后，可点击该窗口右下角的“全局视图”复选框切换观察模式。

• 接下来在“方案寻优”界面的“Model Setting”控制面板中

输入本案例的仿真时长：3天*8小时*60分钟 = 1440分钟，在“重复次数”文本框中输入 “1”。

• 在“Optimization”控制面板中

选择本次方案寻优的目标函数及寻优取向（如上图所示）

• 在“Running”控制面板中

对本次方案寻优的时间花费进行评估：点击其中的“方案空间”按钮，系统弹出本次方案寻优的方案空间规模对话框，提示总计有“360”个可能的方案，继续点击“运行评估”按钮，系统弹出对话框提示：“完成方案空间搜索的时间花费大约为：1079秒”大约18分钟。

进一步应用工程约束，点击“应用约束”按钮，系统弹出对话框提示，应用约束后方案空间规模为“258”个，比原来减少了近30%。由此可以看出工程约束的运用，对控制方案空间规模的作用是非常大的！再点击“运行评估按钮”，系统弹出对话框提示：“完成方案空间搜索的时间花费大约为：785秒”大约13分钟。

【备注】

由于在该模型中使用了随机函数表示工序设备的加工循环时间，因为随机函数采样特性，上面的结果在不同电脑上表现会有差异，结果供参考。

• 考虑到本次方案寻优规模不大，完成时间花费也在可接受的范围内

因此在选择寻优搜索策略是，可选择全局搜索，即通过仿真遍历每一个可能的方案，通过对比获得最优设计方案。因此在“Algorithm”控制面板中，选择全局搜索算法“All Combination ”即可。

• 最后点击“Running”控制面板中“运行”按钮

系统开始方案寻优过程，随着仿真时钟的推进，在“OPT结果”窗口中，以列表的形式展示出方案寻优所遍历的每一个设计方案的配置参数与运行结果，并且把发现的迄今为止有最好结果的方案，始终放置在第一行。与此同时，在“OPT运行”窗口，以曲线的形式展示出系统寻优方案的目标函数曲线。如下图所示：

其中灰色的是记录每次寻优方案产线绩效结果的目标函数曲线，红色的是连续记录出现最优值的寻优曲线。本案例完成全部方案空间搜索的结果如下图所示：

“OPT结果”窗口中第一行展示出本案例方案寻优的最佳结果：产线配置参数为：“工序1”配备加工设备的数量为3，“工序,2”配备加工设备的数量为6，“工序3”配备加工设备的数量为3，班组员工配备数量为8，该方案的营业利润为258810.9元。

如果要根据方案寻优的最佳结果，重新生成本案例的仿真模型，可鼠标点击“OPT结果”窗口中第一行数据，单击鼠标右键弹出下拉菜单“设置为模型”，点选后，BHTC Simulation系统会根据最优的产线配置数据，重新生成案例的仿真模型。如下图所示：

通常，方案空间的规模都在几万甚至几十万的规模，点击“OPT结果”窗口顶部的“导出到EXCEL”按钮，可将方案寻优结果数据导出到EXCEL文件中，进行进一步的数据对比、筛选、排序、统计等等分析工作。

6.优化算法

当方案空间规模很大（方案空间规模达到数万级规模以上）时，通过全局搜索遍历每一种可能的方案，以获取最优解，在时间花费上可能无法实施。需要更“聪明的”搜索策略，因此，针对大规模方案空间的寻优问题，本系统提供了一系列智能化的解空间搜索算法，以最小的时间花费获取项目的最优解。

本质上说，这些算法都是一种解空间的启发式的搜索算法，即为避免在全域范围内探索解空间所有可能的方案，启发式的搜索算法是根据前一次的搜索结果，判断下一次搜索的去向，力求只探索有限的解空间域而获得全局最优解，至少是次优解的搜索方法。以下分别作以介绍。

6.1遗传算法

点击“Algorithm”控制面板中的优化算法下拉菜单，从中选择遗传算法“Genetic ”，此时，系统弹出执行遗传算法的控制参数界面，如下图所示：

遗传算法是解决工程优化问题被广泛采用的一种启发式的解空间搜索策略。这组参数的选择，对遗传算法的运行性能有着重要的影响。合理的参数选择使得求解过程具有较高的求解效率和求解质量。所谓“求解效率”就是指在有限的时间内，能够快速的获取方案空间的最优解，“求解质量”就是指能够获取全局最优解，而避免过早的落入局部搜索而获得局部最优解。在具体应用时，仍需要结合问题特征酌情选取，下面是这些控制参数的涵义及其选择建议：

• “种群规模”

定义了遗传算法中，初始群体所包含的方案样本的数量。建议这一数值在20至200之间，过大的种群规模会花费更多的时间在当前代的群体评测上，从而影响代际迭代的效率；

• “代际淘汰比率”

定义了遗传算法中，从当前代种群复制到下一代种群时，按照这一比例去除掉种群中那些目标函数值较差的个体，为保持种群规模，选取同样数量的目标函数值较高的个体作为替代样本空间，从这一样本空间中随机选取较好个体替代被去除掉的较差的个体。建议比例值在5%以内，避免个别优秀基因过早的被排除掉。

• “杂交概率”

定义了在每一代种群中，对个体（染色体）进行杂交操作产生新个体的频率。杂交概率越高，在种群中引入新个体的速度就越快，同时已获得的优良基因结构丢失的也就越快。反之，杂交概率很低，有可能导致新个体产生不足，过早陷入局部搜索。一般地，建议将“杂交概率”定义为0.5至1之间的数值。

• “变异概率”

定义了在每一代种群中，对个体（染色体）每一个基因位进行变异操作产生新个体的频率。变异概率过高，就会丧失遗传算法特征，使得在方案空间的寻优过程变成随机搜索；变异概率过低又不利于优良基因的早期发现与传承，建议将“变异概率”定义在0.3至0.8之间。

• “迭代次数”

定义了系统执行遗传算法进行代际遗传的代数。随着时间的推进，当遗传代数达到这一数值时，算法终止。本质上说，所有智能化的搜索算法，都是在全部的方案解空间中，按照其算法定义的策略选取有限数量的个体，进行性能评估实验，以期望获得全局最优解。事实上，在执行算法之前，并不能确定到底需要尝试多少个个体进行评估实验。一般地建议，当方案空间规模达到10000时，评估个体的数量规模至少要在100个至500个之间；当方案空间规模大于10000,000时，评估个体的数量规模至少要在1000个至5000个之间；依次类推，方案空间规模每增加3个“0”，实际参与评测的个体规模就相应地增加1个“0”。在遗传算法中评估的有限个体数量 = 迭代次数X种群规模，据此可大致定义遗传算法终止的“迭代次数”。

• “连续N代”和“最优值提升少于%”参数

定义了系统运用遗传算法另一种附加的终止条件。即随着时间的推进，系统会随时观察经历“连续N”参数定义的遗传代数后，种群中最优个体的目标函数值的提升是否小于“最优值提升少于%”参数定义的阀值，如果少于这一阀值，则算法提前终止。

以上给出了系统执行遗传算法进行控制参数选择的大致原则。通常控制参数的选择是与求解问题的特征相关联的，并且目标函数越复杂，参数的选择也越困难，不存在一个适用于所有问题的最佳参数。在实际应用中，可通过多次参数选择的效果对比，获得优选的控制参数方案。

最后点击“Running”控制面板中“运行”按钮，系统开始使用遗传算法导引方案空间的寻优过程，随着仿真时钟的推进，在“OPT结果”窗口中，以列表的形式展示出方案寻优所遍历的每一个设计方案的配置参数与运行结果，并且把发现的迄今为止有最好结果的方案，始终放置在第一行。与此同时，在“OPT运行”窗口，以曲线的形式展示出系统寻优方案的目标函数曲线。

6.2模拟退火算法

点击“Algorithm”控制面板中的优化算法下拉菜单，从中选择模拟退火算法“Annealing ”，此时，系统弹出执行模拟退火算法的控制参数界面，如下图所示：

模拟退火算法是将在方案的解空间搜索优化解的过程类比金属高温退火时，分子由高能量不稳定状态，通过逐渐的退火冷却变成低能量稳定状态的过程而形成的一种解空间搜索方法。算法执行时，首先在解空间随机采样取得一个样本作为目标解，然后开始探索这个解的邻域，寻找可以替代目标解的候选解，如果从邻域找到的这个解的目标函数值好于目标解，则接受这个候选解为新的目标解；如果邻域候选解的目标函数值差于目标解，则按当前退火温度相关的概率来接受这个较差的劣质解，重复这个过程直至满足终止条件而退出。同样地，算法控制参数的合理选择，对“求解质量”和“求解效率”有着重要的影响，下面是这些控制参数的涵义及其选择建议：

• 初始温度

是一个类比金属高温退火时初始温度的数值，这一数值决定了算法初期接受劣质解的能力，这一数值越高，算法接受劣质解的概率就越大，搜索范围越广，避免陷入局部最优。通常设置得足够高，使得在初始阶段，几乎邻域中所有候选解（即使是劣解）都能被接受。一个简单的方法是，根据目标函数的值来设置“初始温度”的值。如果目标函数变化范围在几百到几千，“初始温度”的值可以设为几百或几千；或者，在执行算法之前，对优化模型先进行多次的采样评估，获得目标函数值的大致变动范围，将“初始温度值”设置为这一变动范围的10至100倍等。

• 冷却系数

模拟退火算法是类比金属从高温逐次降温的退火过程，“冷却系数”定义了相邻的两次退火温度的比例系数，简言之：Tk+1 =Tk * “冷却系数”，这里Tk是算法的第K次退火温度，Tk+1是算法的第k+1次退火温度。 由于退火温度决定了算法对劣质解的接受概率，冷却越快，算法接受劣质解的概率越小，算法可能收敛快，但容易错过全局最优解。一般地建议“冷却系数”取值在【0.75，0.99】之间。

• 当前温度下尝试搜索次数

该数值定义了在当前退火温度下，算法尝试对邻域搜索候选解的次数，以此来类比金属在某个退火温度下的退火过程，即保持当前温度一段时间后达到退火平衡状态，由此可以下降温度，进入下一个温度的退火过程。即算法在目标解的邻域尝试搜索候选解的次数达到这一数值后，即可结束本次退火过程，根据“冷却系数”下降退火温度，在新的退火温度下继续重复退火过程。

• 当前温度下连续拒绝新解的次数

该数值定义了另外一种结束当前温度下退火计算的条件，即在当前退火温度下，算法尝试对邻域搜索候选解时被拒绝，如果这种尝试被连续拒绝次数达到这一数值时，则算法认为在当前退火温度下，已经达到退火平衡状态，可以进入下一退火温度进行退火。

• 迭代次数

定义了系统执行模拟退火算法进行的次数。随着时间的推进，当累计退火计算次数达到这一数值时，算法终止。本质上说，所有智能化的搜索算法，都是在全部的方案解空间中，按照其算法定义的策略选取有限数量的个体，进行性能评估实验，以期望获得全局最优解。事实上，在执行算法之前，并不能确定到底需要尝试多少次退火计算，这时，仍可参考前文遗传算法中的“迭代次数”评估方案，根据方案空间的总体规模，并结合“在当前温度下尝试搜索次数”，大致定义出模拟退火算法终止的“迭代次数”。

• “连续N次”和“最优值提升少于%”参数

参数定义了系统运用模拟退火算法时的另一种附加的终止条件。即随着时间的推进，系统会随时观察经历“连续N次”参数定义的退火次数后，目标解目标函数值的提升是否小于“最优值提升少于%”参数定义的阀值，如果少于这一阀值，则算法提前终止。

最后点击“Running”控制面板中“运行”按钮，系统开始使用模拟退火算法导引方案空间的寻优过程，随着仿真时钟的推进，在“OPT结果”窗口中，以列表的形式展示出方案寻优所遍历的每一个设计方案的配置参数与运行结果，并且把发现的迄今为止有最好结果的方案，始终放置在第一行。与此同时，在“OPT运行”窗口，以曲线的形式展示出系统寻优方案的目标函数曲线。

6.3Random搜索

点击“Algorithm”控制面板中的优化算法下拉菜单，从中选择随机搜索算法“Random”，然后点击“Running”控制面板中“运行”按钮，系统开始以在方案解空间随机采样的方式进行寻优，随着仿真时钟的推进，在“OPT结果”窗口中，以列表的形式展示出方案寻优所遍历的每一个设计方案的配置参数与运行结果，并且把发现的迄今为止有最好结果的方案，始终放置在第一行。与此同时，在“OPT运行”窗口，以曲线的形式展示出系统寻优方案的目标函数曲线。

6.4小结

如前文所述，这些方案解空间中的优化搜索算法，本质上就是为避免进行全局搜索（All_Combination），力求只探索有限的解空间域而获得全局最优解，至少是次优解的搜索方法。其搜索过程的“求解效率”和“求解质量”取决于这些算法的控制参数。由于算法的核心是选择有限的方案空间域进行搜索，因此算法本身并不能确保这次搜索一定能找到全局最优解，但至少可以获得次优解。并且，一般情况下，次优解要好于局部最优解。当然，如果扩大搜索范围，算法终究能找到全局最优解。因此在实际应用中，就需要合理兼顾“求解效率”与“求解质量”，尽可能以较少的时间花费获得较好的工程上可接受的解。