智能优化技术 课件汇 黄思翰 第2-3讲- 遗传算法 -模拟退火算法

遗传算法目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践遗传算法概述1达尔文提出“物竞天择、适者生存”进化论遗传算法诞生的标志年份遗传算法已经形成了完整的理论体系遗传算法及其应用被全面系统的论述、普及及推广。1975至今18591989“霍兰德的专著系统性地阐述了遗传算法”“遗传算法在工程技术和社会生活中的大量应用实例”19661963德国学者提出了进化策略的初步思想美国学者阐述了进化编程的思想进化计算作为一个学科正式出现90年代“随着遗传算法、进化策略、进化编程、遗传编程的交叉融合”遗传算法理论基础2遗传算法（GeneticAlgorithm，GA）是一种应用广泛、效果显著的经典优化算法。通过对生物系统进行计算机模拟研究，把问题的解决方案编码为由多个基因位组成的染色体（个体）。然后针对染色体执行选择、交叉、变异等运算操作来重组染色体上的基因信息，最终获得高质量的解决方案。物种进化过程：选择操作：具有优秀特性的个体会比其他个体更容易生存并繁殖。交叉和变异操作：是在保证子代和亲代具有一定相似性的同时，进行种群更新迭代。进化过程遗传算法理论基础3遗传算法起始于问题的潜在解集合。每个解个体代表一个解决方案，一定数目的个体组成种群（Population）。通过选择、交叉和变异操作，使进化搜索方向逐渐向更有前景的方向进行发展。随着迭代搜索的进行，最后收敛到一群最适应环境的个体。通过评估每个个体的适应度值，使得进化搜索具有方向性。进化流程遗传算法理论基础4自组织、自适应性遗传算法可根据进化过程得到的信息进行自行组织和搜索求解。无须像传统算法一样必须事先广泛全面地了解问题才能求解。并行性遗传算法首先适合大规模的并行操作，只需在运算完成后选择最优个体。其次，以种群形式进行问题搜索求解，同时搜索解空间内的多个区域。不依赖数学性质遗传算法只根据目标函数及合理的适应度函数便能对解个体进行比较选优。无须事先知晓问题的相关复杂数学性质。概率转换规则解的搜索方向以概率转换规则为核心。各种进化操作中都具有一定的发生概率，因此不确定的搜索过程使得种群中的个体更为多样化。遗传算法的基本特点目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践5遗传算法流程【步骤1】初始化参数：设置种群大小N、交叉概率Pc、变异概率Pm、每个个体染色体的基因个数n、遗传算法的最大迭代次数T，并按照随机或某种方式产生N个个体，进而组成初始种群。【步骤2】适应度计算：每个个体通过适应度函数（基于优化目标）计算出适应度值，用以判断个体的优劣程度。【步骤3】选择操作：根据某种选择策略从当前种群中选择一定数量的个体，并将其作为子代个体。【步骤4】交叉操作：随机生成一个数c∈[0,1]，若c<Pc，则对父代种群中的两两个体进行交叉操作，直至产生N×Pc个子代个体。6遗传算法流程【步骤5】变异操作：随机生成一个数m∈[0,1]，若m<Pm，则根据变异概率Pm对当前种群中个体的单个或多个基因位进行变异操作产生变异个体，直至产生N×Pc个子代个体。【步骤6】修剪种群：将父代、子代种群进行合并，计算其适应度值，并按照一定策略保留N个个体形成当前种群。【步骤7】终止条件判断：若不满足终止条件，则返回算法步骤3；若满足终止条件，则输出当前适应度最佳的个体作为最优解，算法结束。7遗传算法概念详解术语表征编码(coding)表现型到基因型的映射；解码(decoding)从基因型到表现型的映射；个体(individual)携带遗传基因的染色体，即具有串结构特征的解方案；种群(population）个体的集合。其中第

t代种群记作

P(t)；适应度(fitness)表示个体的优劣性，适应度值函数的设定因问题而异；选择(selection):根据个体适应度，按照一定规则，选择出一些优良的个体遗传到下一代种群中；交叉(crossover)将种群个体搭配成对，并针对每对个体根据交叉概率按照一定方法交换它们之间的部分染色体片段；变异(mutation)针对种群中的每一个个体，根据变异概率改变单(多)个基因位上的基因值为其他的等位基因；遗传算法基本术语8遗传算法概念详解

9遗传算法概念详解数值案例简介求解下述二元二次函数的最大值:基于此数值案例剖析遗传算法，对其编解码方式、适应度值计算、初始化参数、选择、交叉、变异操作、修剪种群等具体流程深入讲解。

10遗传算法概念详解编码与解码问题分析实际问题解决方案结构数据串算法执行问题求解算法编码算法解码输入输出编码:即将问题的解决方案表征为具有一定特征的结构数据串。解码:是将结构化的数据串转化为解决方案的过程，即编码的逆运算。常见的编码形式包括：二进制编码、实数编码、符号编码等。11遗传算法概念详解编码与解码—二进制编码二进制编码是常见的编码方式。特点：解码简单，染色体上每个基因位的数值非0即1。交叉、变异算子易于实现。但要通过实际决策变量的取值范围及求解精度来确定编码串长度。编码串长度确定：在本数值案例中，因为x1,x2

为0~31之间的整数，故求解范围为[0,31]，求解精度为1。由于24<31-0<25，所以用5位二进制编码串来表示决策变量。故个体的基因型采用10位的二进制编码串来表示。如图所示，基因型X＝1010011001所对应的表现型是：[x1,x2]＝[20,

25]。

基因型表现型

12遗传算法概念详解编码与解码—实数编码实数编码又称为浮点型编码，染色体基因位用实数表示，能够达到任意精度。特点：展现直观易于理解。但在执行具体的遗传操作时需要相关制定规则。举例说明：如图所示，在本数值案例中，基因型X＝20|25所对应的表现型是：[x1,x2]＝[20,

25]。每个编码位的取值均为0~31之间的整数。基因型表现型13遗传算法概念详解编码与解码—符号编码符号编码中个体的基因位由符号集中的符号表示，可以是字符、无数值意义的数字等。特点：适应于一些特定的问题，比如排序问题、旅行商问题等。并且编码方式易于理解。举例说明：针对旅游商问题(TSP问题)，假设需旅居5个城市，分别记为C1,C2,...,C5，个体基因型X＝5|2|3|1|4对应旅行路线顺序[C5→C2→C3→C1→C4]。基因型表现型14遗传算法概念详解适应度计算个体的适应度指个体在种群生存的优劣程度度量。针对个体进行解码处理后，得到个体的表现型。由个体的表现型计算出个体的目标函数值。根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。评价个体适应度的一般过程为

遗传算法概念详解适应度计算—一般范式特点：适应度函数不要求具有连续可微性，且其定义域可以为任意集合。但要满足可行解的适应度值可以进行优劣比较。在具体应用中，适应度函数的设计要结合求解问题本身的要求确定。依照目标函数值建立适应度函数得一般范式：正负数方式：差值方式：除数方式：1516遗传算法概念详解初始化参数1.种群大小N

即种群中所含个体的数目，通常N的取值范围为20~200。

种群过大则使得算法运行时间变长，种群过小则容易导致算法搜索能力偏弱。2.选择代沟S_gap从父代种群中选择出子代种群的个体比例，一般其取值范围为0.8~1。选择概率不能过小，过小会导致后续的交叉、变异操作起不到对种群进化的推进作用。17遗传算法概念详解初始化参数3.交叉概率Pc指定交叉操作发生的概率，一般其取值范围为0.4~0.9。交叉概率不能过大不易保留优秀的基因片段。过小则起不到更新进化的作用。4.变异概率Pm

变异操作发生的概率，用于保证种群多样性。一般取值范围为0.001~0.2。5.遗传算法的最大迭代次数T通常T的取值范围为100~500，其与算法的运行时间正相关。18遗传算法概念详解初始化参数6.算法停止条件制定最大迭代次数。（最常用的标准方式）计算耗费的资源限制。（如算法所用的时间或计算所占用的内存空间等）算法已经找到最优解。（往往使用在有标准最优解的情况下）个体不再进化。（即在一定的时间范围内，算法继续进化不会产生适应度值更好的个体。通常认为算法基本达到收敛水平。）其他的人为干预。19遗传算法概念详解选择操作选择算子就是以某种选择方法从父代群体中选择一些个体遗传到下一代，比较常用的选择操作有：轮盘赌选择法

（Roulettewheelselection）锦标赛选择方法（Tournamentselection）随机遍历抽样

（Stochasticuniversalselection）局部选择法

（Localselection）截断选择法

（Truncationselection）排序选择法

（Rankedselection）20遗传算法概念详解选择操作—轮盘赌选择法轮盘赌选择法即选择概率与适应度函数值成正比，进而适应度值高的个体更容易被遗传保留下来。具体步骤如下： 计算种群中各个体xi

的适应度函数值

F(xi)，i=1,2,...,N，其中N为种群大小。 计算种群中所有个体的适应度函数值之和。计算公式为 计算出每个个体xi

被遗传到下一个种群的选择概率pi。计算公式为 计算出每个个体xi的累积概率qi。计算公式为 在[0,1]区间内产生Ns个随机数ri。若ri≤q1，则选择第一个父代个体

x1

加入子代种群，若

qi-1≤r≤qi

成立，则选择第i个个体xi加入子代。21遗传算法概念详解选择操作—轮盘赌选择法

个体编号父代种群x1,x2目标函数值所占百分比选择次数子代种群1010111010111,20-2796820.180010101011102101010111020,1420411650.307210101011103011111001115,19-1368250.218101111100114111001100128,2515911200.29511110011001总和

37901

22遗传算法概念详解选择操作—锦标赛选择法从父代种群中随机选择一定数目（通常2~5个）的个体，其中适应度函数值最高的个体保存到子代，这个过程反复执行多次，选出子代种群。锦标赛选择方法属于有放回的抽样方法。具有O(n)的低复杂度易并行化处理不易陷入局部最优不需排序处理特点锦标赛父代子代23遗传算法概念详解选择操作—其他选择方式随机遍历抽样（Stochasticuniversalselection）此方法针对种群规模为N的种群，其中的个体被选中概率均为1/N。然后进行Ns次抽样选择出Ns个优秀个体。局部选择法（Localselection）在局部选择法中，我们认为每个个体都有一些邻域个体，个体和这些邻域个体组成局部邻域，然后按照分好的局部邻域进行选择。例如，可以将种群按适应度值进行均匀划分后每部分有针对性的进行选择。

24遗传算法概念详解选择操作—其他选择方式25遗传算法概念详解交叉操作交叉操作的原理是结合两个父代个体信息产生新个体。交叉操作可以使种群中的个体具有多样性，扩大搜索空间，增加个体搜索到全局最优解的概率。具体计算步骤如下：形成交叉对交叉执行将父代种群中的个体进行配对处理，若父代种群大小为Np，则共有对个体组。选择交叉点针对每对相互配对的个体，随机选择某基因点位作为交叉点。根据设定的交叉概率Pc，使每一对个体交叉后生成两个新个体。26遗传算法概念详解交叉操作—单点交叉随机选择一基因位，然后交换该基因位后的编码段。27遗传算法概念详解交叉操作—两点交叉随机选择两个不同的基因位，然后交换两基因位间的编码段。28遗传算法概念详解交叉操作—多点交叉随机选择多个基因位，然后交换多个基因位上的编码片段。29遗传算法概念详解变异操作变异操作即对种群中某个染色体的某个基因重新赋值，通过基因突变的方式帮助算法跳出局部最优。单点变异算子随机选择一个基因点位进行变异多点变异算子随机选择多个基因点位进行变异30遗传算法概念详解修剪种群当父代种群经过选择、交叉、变异操作后形成子代种群。为了避免迭代过程中的最优个体遗失，通常会合并父代和子代种群，在世代更迭之前需要按照一定策略保留N个个体形成下一代的种群。31遗传算法改进算法改进概述一个优秀的智能优化算法的关键在于提高及平衡其全局探索（exploration）和局部开发（exploitation）能力。全局探索：对解空间进行全面的搜索，希望探知发现更多的未知区域；局部开发：对已知区域进行精细的搜索，希望获得质量更好的新解。随着进化计算研究的不断深入，为适应更多类型的复杂工程问题，对改进遗传算法的研究也逐渐增多。这里，给出以下几种改进思路以供参考。32遗传算法改进改进1：针对种群初始化的改进：混沌初始化在优化领域，普通的初始化往往是随机生成方式。混沌映射可以用于替代随机数生成器生成0到1之间的混沌数，以增加算法的随机性和多样性、提高其全局探索能力。混沌映射：是一种由简单确定性系统产生的随机性序列的方式,其主要特征是不可预测性和对初始条件的极端敏感性。目前混沌映射的方式主要包括以下6种Logistic映射Circle映射Sine映射Singer映射Cubic映射33遗传算法改进改进2：针对遗传算子的改进：自适应交叉、变异概率随迭代的进行自适应改变交叉、变异概率。如果某一代个体的适应度函数大于适应度函数平均水平，则表明该个体性能佳，应该降低交叉、变异概率，尽可能保留该个体的优良基因；反之，需要对其进行加速交叉、变异，将其快速淘汰。

自适应交叉率公式自适应变异率公式实现高适应度值个体低交叉变异概率，低适应度值个体高交叉变异概率，从而有针对性的提高算法的局部开发能力。改进34遗传算法改进改进3：将算法与启发式策略结合：基于邻域搜索策略改进的遗传算法为了使得所设计算法更加适应特定问题的求解，通常基于问题特征设计启发式邻域结构，在执行完成遗传操作（选择、交叉、变异）后对迭代子种群执行邻域搜索，进而再次提高算法的局部开发能力。遗传算法的基本流程具有通用性，可以面向各类工程问题进行优化求解，但是很难有针对性的求解特定复杂场景下的优化问题。不足目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践35工程案例分析可重构制造系统调度问题面向具有多品种、小批量特点的产品订单，在一个基于可重构机床的制造系统中如何合理的组织现有的制造资源，进行快速高效的产品生产是制造企业需要解决的关键问题。具体来说，该制造系统由多台可重构机床组成。每台可重构机床具有多种构型，每种构型对应一种产品特征（工序）的加工。对于一台可重构机床来说，不同构型之间的转化需要一定的设置时间和成本。此外，订单由多种类型的产品组成，每种产品的加工数量也各不相同。一种产品包含多个特征（工序），特征的加工存在固定的先后顺序。36工程案例分析可重构制造系统调度问题问题假设：针对每台可重构机床切换不不同构型时的设置时间及成本是固定相同的。可重构机床加工期间针对某一产品特征加工时间固定不考虑其运行故障。一台可重构机床的一种构型至多对应一种产品的一个特征的加工，即不考虑一种可重构机床的构型可以生产一种产品的多个特征的加工的情况。每种产品类型的同一产品特征必须在一台可重构机床上连续生产，不允许间断及生产任务拆分。在零时刻所有可重构机床均可用，所有产品均可以被加工。37工程案例建模符号说明：索引常量符号含义i,j产品类型索引(i,j=(1,2,…,P))k,lm可重构机床索引(m=(1,2,…,M))c38工程案例建模常量符号说明：常量符号含义产品

i

的特征总数量可重构机床m的构型总数量产品i的加工数量产品i

的第k个特征在可重构机床m上的加工时间可重构机床m的构型切换时间产品i

的第k个特征能采用可重构机床m的第c个构型加工则为1，否则为0如果在可重构机床m上产品i

的第k个特征的加工构型与产品j

的第l个特征的加工构型不同则为1，否则为0足够大的数39工程案例建模符号说明：决策变量与辅助变量常量符号含义产品i

的第k

个特征的生产开始时间产品i

的第k

个特征的生产完成时间产品i

的最终生产完成时间如果产品i

的第

k个特征选择可重构机床m进行加工则为1，否则为0如果在可重构机床

m上产品i

的第

k个特征加工完成后紧接加工产品

j

的第

l个特征则为1，否则为040工程案例建模优化目标：Makespan

模型约束：1）产品特征加工时间约束41工程案例建模模型约束：2）产品前后特征的加工时间约束模型约束：3）产品完工时间约束模型约束：4）可重构机床上时间占用约束模型约束：5）构型加工约束42工程案例建模模型约束：6）可重构机床的一种构型至多对应一种产品的一个特征的加工模型约束：7）对于任意的一个产品特征必须被某一个可重构机床进行加工模型约束：8）可重构机床上一个特征加工至多只有一个紧前、紧后加工特征模型约束：9）定义变量的取值范围43基于遗传算法的案例求解遗传算法应用分析使用遗传算法求解可重构制造系统调度问题，需要重点解决以下3个问题：如何根据该可重构制造系统调度问题设计合理可行的编解码方案？选择操作、交叉操作、变异操作如何具体执行？如何设定种群的迭代更新策略（即如何修剪种群）？44基于遗传算法的案例求解编码产品特征的加工顺序子决策问题:基于可重构制造系统调度的问题特征，我们需要进行两个子决策问题的求解：

在满足同一产品前后加工特征的顺序约束的基础上，我们需要考虑在可供选择的可重构机床上先生产哪一产品特征，以及后生产哪一产品特征。不同的产品特征生产顺序会影响最终调度方案的整体完工时间。加工产品特征的可重构机床配置子决策问题:

在满足同一时刻一台可重构机床至多只能用于一项产品特征加工的约束基础上，我们需要考虑针对不同产品的不同特征选择哪一可重构机床进行加工。不同的可重构机床配置方案会影响可重构机床的加工进程，进而影响最终调度方案的整体完工时间。45基于遗传算法的案例求解编码考虑到以上两个子决策问题的解决，针对本数值案例，我们设计了如上双层编码的形式。第一行代表产品特征的加工顺序，其中各编码位为产品序号。同一产品序号多次出现代表产品的不同特征。例如，第1个3代表产品3的第1个特征，第2个3代表产品3的第2个特征，以此类推。第二行代表产品特征选用的可重构机床序号，例如，第一个编码位的2代表产品3的特征1由可重构机床2进行加工，以此类推。可以看出，对于产品总数为P，每个产品i的加工特征数为Fi

的问题时，染色体是长度为的整数编码串。46基于遗传算法的案例求解解码在设计完成编码方式后，针对一个编码方案我们需要对其进行评价，以表征编码方案的优劣。因此，此步的设计与数学模型中的目标函数密切相关。即根据具体的编码方案，计算得出与之对应的目标函数值。在遗传算法中，采用适应度值函数(Fitness)表征目标函数值(f(x))，即在一般化的遗传算法范式中，适应度值越大，表明染色体越优。即针对极大化目标函数模型时Fitness=f(x)。而针对本问题的最小化目标函数模型时Fitness=-f(x)即可。注：在算法的具体编程实现时，我们不必拘泥于形式化的表达方式，即选用适应度值函数形式还是目标函数值都是可以的，但是要保证编码方案的优劣是可以进行对比的。47基于遗传算法的案例求解种群初始化针对本工程案例，我们设计了如下双层编码形式。如何初始化一个编码个体哪?本节采用了随机生成方式进行初始化个体。针对第一层编码，假设产品1、2、3、4其各自所对应的特征总数为：3、3、4、2。我们只需要打乱其顺序即可获得不同的产品特征层编码。然后依照确定的第一行编码，从前向后逐个为产品特征随机选取进行加工的可重构机床，进而获得第二行机床配置层的编码。48基于遗传算法的案例求解选择操作

针对本工程案例，采用多元锦标赛选择法从种群中抽出部分个体至选择池，然后比较其的适应度值，将具有最大适应度值个体选出。如图所示：二元锦标赛选择法，代表每次随机抽出两个个体，其中适应度值较大的个体被选择出来。49基于遗传算法的案例求解交叉操作

针对本工程案例，采用一个标准的两点交叉进行该操作的执行，具体操作流程如下：流程1针对执行选择操作挑选出来的个体两两配对形成交叉组合。并设定一个交叉概率来判断是否针对该配对个体执行交叉，交叉概率通常被设定在（0，1）之间。

注：如果经选择操作挑选出的个体集合是偶数，则自上至下两两配对进行交叉。

如果挑选出的个体集合是奇数，仍然自上至下两两配对进行交叉，最后一个个体默

认不执行交叉操作即可。50基于遗传算法的案例求解交叉操作流程2如果根据交叉概率该交叉组合被判定执行交叉操作，则在编码长度范围内随机选择两个不等的编码位，并将该编码位之间的编码片段进行交换形成两个新的子代个体。51基于遗传算法的案例求解交叉操作流程3执行完交叉操作后，所得的子代个体可能是非法解，即该个体不满足编码方式的要求。因此，需要针对生成的子代个体逐一进行个体修复以使其满足编码规范要求。针对本工程案例：第一行产品特征层可能出现部分产品特征缺失和多余的情况；第二行机床配置层可能出现无法加工第一层所对应的产品特征的情况；52基于遗传算法的案例求解交叉操作—修复产品特征层编码如下图所示，子代个体1的第一行出现了（2个1、2个2、7个3、1个4）。对比（3个1、3个2、4个3、2个4）的要求（缺失1个1、1个2、1个4，多余3个3）。本案例采用“相消替换”的思路来合法化非法个体，即首先明确子代个体与父代个体的缺失、多余基因，然后按照缺失多余的次序一一配对进行替换，进而完成解的合法化。53基于遗传算法的案例求解交叉操作—修复机床配置层编码即按照产品特征层的编码确定机床配置层编码是否可行，如果不可行则需为其随机选择可行的机床进行加工。

54基于遗传算法的案例求解变异操作针对本工程案例，采用一个多点变异操作进行该操作的执行，具体操作流程如下：首先随机生成进行变异的基因点位数。然后随机选择变异点数个编码位置，并为该编码位置的产品特征随机更换机床序号。55基于遗传算法的案例求解修剪种群针对本工程案例，本节采用基于精英保留策略的修剪方式。如图所示展现了具体操作流程如下：首先，将父子代种群合并，然后按照个体的适应度值（或目标函数）进行排序，截取最优的前POPSIZE个个体，作为下一次迭代的父代种群。目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践56工程实例产品类型产品数量特征数量1A20032B50033C10044D3002针对如下所示的具体实例数据进行遗传算法的编写。生产订单信息可重构机床构型数转换时间转换成本1A38003502B56003003C31000500可重构机床信息57工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)1-2F(1,2)-41F(1,3)213F(2,1)23-F(2,2)3-1F(2,3)11-F(3,1)-52F(3,2)2-1F(3,3)143F(3,4)33-F(4,1)143F(4,2)322产品特征对应机床构型表58工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)5-8F(1,2)-1012F(1,3)679F(2,1)1319-F(2,2)10-5F(2,3)812-F(3,1)-49F(3,2)6-1F(3,3)3710F(3,4)93-F(4,1)594F(4,2)836产品特征加工时间（Min）59参数设置算法参数设定值种群大小10迭代次数100选择代沟0.9选择框大小2交叉概率0.7变异概率0.260工程求解主代码导入依赖包输入实例数据执行遗传算法并作图首先进行数据输入。然后，创建工程问题类FJSP_RMT，创建遗传算法类GA。最后，根据算法运行结果画出迭代图和最优解甘特图。61工程问题类FJSP_RMTFJSP_RMT类的初始化62种群初始化代码初始化种群中的个体63解码代码初始化种群并计算适应度值根据个体，计算其所对应的实际运行方案，然后获取其所对应的Makespan。64遗传算法主代码初始化种群并计算适应度值用于实现遗传算法的主循环功能，经过初始化种群、计算适应度值(解码)、种群迭代循环(选择、交叉、变异、修剪种群)直至达到最大迭代要求终止搜索，输出最优个体解。65遗传算法主代码初始化种群并计算适应度值种群迭代循环主程序用于实现遗传算法的主循环功能，通过初始化种群、计算适应度值(解码)、种群迭代循环(选择、交叉、变异、修剪种群)直至达到最大迭代要求终止搜索，输出最优个体解。66选择操作代码初始化种群并计算适应度值多元锦标赛选择操作67交叉操作代码初始化种群并计算适应度值标准的两点交叉操作68交叉操作代码初始化种群并计算适应度值交叉操作—产品特征层编码合法化69交叉操作代码初始化种群并计算适应度值交叉操作—机床配置层编码合法化70变异操作代码机床配置层编码合法化多点变异操作70实验结果实验结果展示如下，其搜索到的最优Makespan=13000s，运行时间为0.835s。遗传算法迭代优化图最优个体方案的Gantt图主讲教师：黄思翰本节结束强化学习目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践强化学习概述1Sutton基于时序差分算法，建立了条件反射心理模型1988至今1957198919721960Klopf将试错学习和时序差分结合在一起2013贝尔曼提出马尔可夫决策过程强化学习算法已经形成了完整的理论体系Watkins提出Q-learning模型，将时序差分和最优控制结合Howard提出马尔可夫决策过程的策略迭代方法DeepMind提出深度强化学习模型，即DQN模型2强化学习算法理论基础强化学习（ReinforcementLearning，RL）,又称再励学习、评价学习或增强学习，是机器学习的范式和方法论之一，用于描述和解决智能体（Agent）在与环境的交互过程中通过学习策略以达成回报最大化或实现特定目标的问题。强化学习是一种机器学习方法。强化学习关注智能体与环境之间的交互。强化学习的目标是追求最大回报3强化学习基础框架强化学习一般包括四个要素：状态(state)、动作(action)、策略（policy）、奖励(reward)。智能体（Agent）与环境（Environment）围绕这四要素进行交互：智能体处在一个环境中，每个状态为智能体对当前环境的感知；智能体只能通过动作来影响环境，当智能体执行一个动作后，会使得环境按某种概率转移到另一个状态；同时，环境会根据奖励函数反馈给智能体一个及时的奖励。典型的案例就是“平衡杆游戏（cartpole）”4强化学习基础框架(1) 智能体在环境中采取行动的实体，其目标是最大化累积奖励。(2) 环境智能体所处的系统，其状态和行为会影响环境，并可能获得奖励或惩罚。(3) 策略描述智能体在给定状态下选择动作的规则。5强化学习基础框架(3) 状态描述智能体在特定时刻所处的环境情况。(4) 动作智能体可以选择的操作，执行动作后，智能体会进入新的状态并可能获得奖励。(6) 奖励智能体采取某个动作后环境给予的反馈，用于评价智能体的表现。6马尔可夫决策过程马尔可夫性质在强化学习中，通常使用马尔可夫决策过程（MDP）来描述具有马尔可夫性的问题。若状态St具有马尔可夫性，当且仅当：

MDP是强化学习问题在数学上的理想化的形式。几乎所有的强化学习问题都可以在数学上表示为马尔可夫决策过程。7马尔可夫决策过程状态转移矩阵状态转移是描述智能体从一个状态（s）采取一个动作（a）后，将转移到哪一个新的状态（s‘）的规则。通常，这个过程是随机的，可以用概率来描述，这就引出了“状态转换矩阵”。对于马尔可夫状态s与其后继状态s’，它们的状态转移概率定义为：

状态转移矩阵可以定义为：

8马尔可夫决策过程马尔可夫过程马尔可夫过程是一种无记忆的随机过程。

时间、状态都离散的马尔可夫过程（马尔可夫链）时间连续、状态离散的马尔可夫过程（连续时间的马尔可夫链）时间、状态都连续的马尔可夫过程。9马尔可夫决策过程马尔可夫奖励过程

10马尔可夫决策过程回报

折扣因子γ在其中起到了很重要的作用：（1）避免有环的马尔可夫过程计算收益时出现无限循环；（2）折扣因子让即时奖励比延时奖励占的权重更大；（3）动物/人类行为中都表现出对即使奖励的偏好，折扣因子赋予了智能体这一特性；（4）可以表达对未来的不确定性。11马尔可夫决策过程价值函数在马尔可夫奖励过程中，一个状态的期望回报被称为这个状态的价值函数，用来评估给给定状态（或给定状态-动作）下智能体表现的“好”还是“坏”。这种“好”还是“坏”是通过预期回报来定义的。然而，智能体未来可能获得的奖励取决于它所采取的行动，因此，价值函数是通过被称为策略的特定行为方式来定义的。

12马尔可夫决策过程贝尔曼方程求解价值函数就需要利用贝尔曼方程，贝尔曼方程是强化学习的基础和核心。

贝尔曼方程还可以用矩阵形式简明表示为：

由于贝尔曼方程是线性方程，因此可以进行直接求解，即：

13强化学习算法理论基础小结探索与利用在游戏机问题中，探索意味着尝试不同的拉杆，以便更好地了解每个游戏机的概率分布。利用则是根据已有的信息，选择目前看起来最好的拉杆来获得更多奖励。在强化学习中需要学习一个策略，即在每个状态下选择哪个动作，以最大化累积奖励。同时，还需要估计每个状态的价值，表示在当前策略下从这个状态开始能够获得的预期累积奖励。试错过程开始时，你可能会随机尝试不同的拉杆，逐渐积累经验并估计每个拉杆的价值。然后，你可以根据估计的价值来改进你的策略，选择估计价值最高的拉杆。这个过程就是策略改进。接着，你可以再次尝试新的拉杆，重新估计价值，进而再次改进策略，形成策略迭代。目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践17Q-learning算法概述Q-learning算法是一种经典的强化学习算法，基于值迭代的思想，通过估计每个状态-动作对的价值函数Q值来指导智能体在每个状态下的最佳动作选择。Q-learning的核心思想是构建一个Q表来存储状态和动作的Q值，并根据这些值来选择能够获得最大收益的动作。有模型强化学习智能体在学习过程中能够对环境进行建模。基于环境模型，智能体能够预测未来状态和奖励，进而制定更优的决策策略。在有模型强化学习中，智能体需要进行两个过程：学习环境模型和基于模型进行决策。无模型强化学习智能体在学习过程中不需要对环境进行建模。智能体通过与环境交互来学习决策策略。在无模型强化学习中，智能体只需要进行一个过程：基于当前状态和奖励进行决策。Q-learning17Q-learning算法流程【步骤1】初始化Q值函数：初始化一个Q值函数Q(s,a)，其中s表示状态，a表示动作。通常，可以将所有Q值初始化为零或者随机值。【步骤2】选择动作：根据某种策略（例如ε-greedy策略）选择一个动作来执行。ε-greedy策略以ε的概率选择一个随机动作，以1-ε的概率选择当前状态下具有最高Q值的动作。【步骤3】执行动作并观察奖励和下一个状态：执行选择的动作，并观察由环境返回的奖励（reward）以及下一个状态（nextstate）。【步骤4】更新Q值函数：使用Q-learning更新规则来更新Q值函数。选择动作结束初始化Q值函数更新Q值函数迭代结束条件？结束训练完成否是18Q-learning算法流程【步骤5】重复步骤2到4：重复选择动作、执行动作、观察奖励和状态、以及更新Q值函数的过程，直到达到某个停止条件，例如达到最大迭代次数或者Q值函数收敛。【步骤6】收敛和策略提取：当Q值函数收敛时，可以使用它来提取最佳策略。最佳策略通常是选择具有最高Q值的动作。【步骤7】终止：算法终止，完成训练。选择动作结束初始化Q值函数更新Q值函数迭代结束条件？结束训练完成否是19Q-learning概念详解强化学习求解数值案例简介求解下述二元二次函数的最大值:

在用Q-learning算法来求解优化问题的时候，首先需要的就是对问题进行强化学习模型构建，把求解最优化问题转化为强化学习问题，利用强化学习来解决最优化问题。20Q-learning概念详解一、定义状态和动作定义状态在Q-learning中状态是智能体与环境交互的基础，也是智能体学习的对象。状态的集合称为状态空间，用S表示。状态空间可以是离散的或者连续的，也可以是有限的或者无限的，这取决于具体的问题和环境。当状态空间和动作空间都是有限的，就可以用一个二维表格来储存每个状态-动作对应的Q值，这是最简单的方法，但是不适用于状态空间过大或者连续的情况。当状态空间是连续的或者高维的，可以用一些特征提取的方法来降维或者离散化21Q-learning概念详解一、定义状态和动作

22Q-learning概念详解一、定义状态和动作定义动作在Q-learning中，动作是指每个状态下可以选择的动作，它会影响智能体的状态转移和奖励。动作是智能体与环境交互的方式，也是智能体学习的关键。动作的选择决定了智能体能否达到最优的策略和最大的累积奖励。动作的集合也称动作空间。动作空间可以是离散的或者连续的，也可以是有限的或者无限的，这取决于具体的问题和环境。案例动作定义在这个二元函数求解最大值的问题中。可以定义以下几个操作为动作。1

2

3

4

24Q-learning概念详解二、定义奖励在强化学习中，奖励函数的设置非常关键，因为奖励函数定义了智能体与环境交互时的反馈。奖励函数设置应该遵循的原则1一致性：奖励函数应该与真实的任务性能指标一致，即奖励函数的最大化应该导致性能指标的最大化。2简单性：奖励函数应该尽可能简单和稀疏，即只在关键的状态-动作对上给予奖励，避免多过的中间奖励或者惩罚。3安全性：奖励函数应该避免引导智能体做出危险或者不可逆的行为，即奖励函数应该考虑潜在的风险和代价。4可学习性：奖励函数应该使得智能体能够有效地从奖励信号中学习，即奖励函数应该提供足够的信息和梯度。25Q-learning概念详解设计奖励函数的方法通过观察一个或多个优秀的智能体或者人类的行为，来推断出他们所遵循的奖励函数，然后用这个奖励函数来指导自己的学习。这是最常见的方法，即由人类专家根据任务的需求和经验来设计奖励函数，比如设定一些固定的数值或者函数来表示奖励。人工设计逆向强化学习通过让人类提供一些反馈，比如评分，指导，示范，或者偏好，来不断地更新和改进奖励函数，然后用这个奖励函数来指导自己的学习。交互式强化学习26Q-learning概念详解二、定义奖励函数

对非法动作需要设置惩罚1

2

27Q-learning概念详解三、策略迭代Q值是一种用来估计在给定状态下采取特定行动后可以获得的未来总回报的函数。Q-learning中的Q表就是一种用于储存每个状态-动作对应Q值的数据结构。Q表的作用是记录和更新智能体对每个状态-动作对的价值评估，指导智能体做出最优的决策，提高其长期的累计奖励。Q表是Q-learning算法的核心组成部分，也是一种基于表格的强化学习方法。28Q-learning概念详解三、策略迭代1.初始化Q-table（该表的大小应该为32*32*4，即Q-table有1024*4。）状态

动作00000000……………0000000029Q-learning概念详解2.设置Q-learning参数1学习率α：新获得的信息覆盖旧信息的程度。2折扣因子γ：决定了未来奖励的重要性。3探索策略：为了平衡探索和利用，强化学习中的探索策略通常是一种交叉策略，即在选择动作时同时考虑随机策略和贪婪策略。Q-learning参数Q-learning中探索参数设置的作用是调节智能体在探索和利用之间的平衡。探索是指智能体尝试一些未知或不确定的动作，以获取更多的环境信息和奖励信号。主要的探索参数设置有以下几个：30Q-learning概念详解a) 学习率α定义了新获得的信息覆盖旧信息的程度，取值范围为0到1。α=0时:智能体不会学习任何新的信息。α=1时:智能体只考虑最新的信息。0<α<1时:智能体既考虑过去的知识也考虑新的奖励。b) 折扣因子γ则决定了未来奖励的重要性。取值范围为0到1。γ=0时：智能体只考虑当前奖励，完全忽略未来奖励。γ=1时：智能体会评估每一步的长期奖励。0<γ<1时：智能体对未来的奖励加上适当的权重。

参考公式：31Q-learning概念详解C) 选择探索策略。在早期的探索学习中，探索环境通常很重要，而随着Q-learning算法学习到的经验增加，利用已知信息的重要性也会增加。而ε-贪婪策略是一种常用的策略来平衡这两者，在本案例中就可以使用这一策略。以ε的概率来选择一个随机动作，以1-ε的概率来选择具有最高Q值的动作。主要的探索策略有以下几个：1置信区间上限UCB：每一个选择对应一个乐观的index（回报的经验均值+confidenceradius，第二项可以近似理解成不确定性），agent选择index最大的动作。2Boltzmann探索：agent根据由温度参数调节的Q值从boltzmann分布（softmax）中提取动作τ。

32Q-learning概念详解3.Q表更新训练迭代的目的就是要强化智能体的Q-table，训练迭代的次数越多，则Q-table被训练优化得更好，当一个Q-table已经被训练得很完善得时候，智能体就可以轻松找到reward最大的状态了。那么接下来就需要进一步进行解读算法迭代收敛求解最大值的过程。33Q-learning概念详解a)案例的R表如下所示，里面的数值表示各个行动状态转移后的奖励值。构建R表R表是一个奖励矩阵，它描述了从一个状态到另一个状态的转移所获得的奖励，也就是环境对智能体的反馈。R表可以是预先定义的，也可以是动态学习的。状态

动作1-M-1-M0-M-40……………-M00120-M-61-M6134Q-learning概念详解b)初始化的0矩阵Q表开始如下表所示。

状态

动作00000000……………0000000035Q-learning概念详解

状态

动作00-0.800000……………0000000036Q-learning概念详解

状态

动作00-0.8000-3.920……………0000000038Q-learning算法改进四、算法改进Q-learning是强化学习领域的一种基础算法，可以通过多种方式进行改进，以获得更好的性能、更快的收敛速度或更好的适应性。可以尝试以下几个改进策略：1优先经验回放：并不是所有的经验在学习中都是平等的。某些可能含有罕见但重要的信息。优先回放根据其时序误差的大小更频繁地采样重要的经验。2双重Q-learning：为了处理Q值的过高估计偏见，可以使用两个Q网络，从一个中选择动作但用另一个评估它们。3自适应学习率：使用像RMSProp或Adam这样的优化算法，根据最近的梯度大小调整学习率，尤其是当使用神经网络时，可以提高Q-learning的收敛速度。从Q-learning演变过来的DQN算法在高维度、连续动作的马尔可夫模型中更具优势。39Q-learning算法改进DQN算法DQN使用深度神经网络来估计Q值函数。这意味着它可以处理更复杂的状态空间，同时减少了存储需求。神经网络可以自动提取特征，使其在高维状态空间中表现更好。Q-learning值函数用状态空间到动作空间的一张表来表达，通常用于离散动作空间，其中每个动作都是离散的选择。DQN将状态值函数或动作值函数进行参数化，将值函数空间转化为参数空间，达到泛化的目的。用神经网络代替Q表40Q-learning算法改进术语表征DQN神经网络作为Q函数来表示优化问题的当前状态；DQN目标网络目标网络是一个固定的网络，用于计算目标值，通过减少目标值的变化来提高训练的稳定性。经验回放将智能体的经验存储在一个经验池中，并从中随机抽样进行训练，以减少样本之间的相关性。记忆容量用于存储经验回放的缓冲区的大小。记忆库记忆库是用于储存和重用之前经验的一种机制。损失函数损失函数是一种用来衡量神经网络预测值和目标值之间差异的函数，它可以指导神经网络的参数更新，使得预测值更接近目标值。网络更新频率延迟更新的目标网络用来计算Q的目标值，避免Q网络误差的“自激效应”，并借此来提高训练稳定性。DQN算法概念说明：41Q-learning算法改进DQN使用深度神经网络来估计Q值函数。这意味着它可以处理更复杂的状态空间，同时减少了存储需求。神经网络可以自动提取特征，使其在高维状态空间中表现更好。

当我们重新审视时序差分公式，不难发现其本质上就是下面目标式的一步随机梯度下降：

43Q-learning算法改进DQN算法的要点：1两个网络：DQN算法采用了2个神经网络，分别是Q值网络和目标网络，两个网络结构完全相同2基本框架：算法分成两个部分，分别是策略选择和策略评估，这也是强化学习算法基本的两个模块。3经验回放：DQN算法设计了一个固定大小的记忆库memory，用来记录经验，经验是一条一条的observation或者说是transition，这就需要在DQN算法中设置记忆容量以及记忆库。42Q-learning算法改进DQN算法与前文介绍的Q-learning方法的不同点有以下几点：DQNQ-learning基于函数逼近的方法，用一个深度神经网络来近似Q值函数，可以处理高维、连续的状态空间和动作空间基于表格的方法，用一个二维数组来存储每个状态-动作对的Q值，需要人工设计特征或者离散化状态空间和动作空间，这会导致维度灾难或者信息损失。批量更新的方法，利用经验回放机制，从一个储存了大量历史数据的缓冲池中随机抽取一批数据还训练神经网络，提高数据的利用效率和算法的稳定性。单步更新的方法，每次只利用当前的状态、动作和奖励来更新Q表。延迟更新的方法，用一个独立目标网络来计算目标Q值，可以避免目标的震荡，提高了算法的收敛性。自举的方法，用当前的Q表来计算目标Q值，这会导致目标和估计之间的相互影响。44Q-learning算法改进【步骤1】将状态转换为神经网络输入格式：在本文的案例中是一个一维的张量。【步骤2】选择动作：使用动作函数选择一个智能体的动作，并将其添加到策略的列表中去。【步骤3】获取奖励：根据当前的状态和动作，得到下一个状态，奖励以及判断该轮训练是否结束。并将下一个状态也转为神经网络的输入格式，即一个一维的张量。【步骤4】储存状态：使用设定的动作储存函数，将当前的状态，动作，奖励和下一个状态储存到记忆库中，用于后续的学习。DQN算法流程：45Q-learning算法改进【步骤5】累加奖励：将奖励累加累积的奖励中去，将奖励添加到每一步的价值列表中去。【步骤6】更新网络参数：如果记忆库的数量达到一定的阈值，就使用前文设置的学习函数，从记忆库中抽取一批数据，更新评估网络的参数，使其逼近最优的动作值函数。如果当前状态是终止状态，则结束此轮训练。【步骤7】更新状态：将当前状态更新为下一个状态，继续循环。目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践35工程案例分析可重构制造系统调度问题面向具有多品种、小批量特点的产品订单，在一个基于可重构机床的制造系统中如何合理的组织现有的制造资源，进行快速高效的产品生产是制造企业需要解决的关键问题。具体来说，该制造系统由多台可重构机床组成。每台可重构机床具有多种构型，每种构型对应一种产品特征（工序）的加工。对于一台可重构机床来说，不同构型之间的转化需要一定的设置时间和成本。此外，订单由多种类型的产品组成，每种产品的加工数量也各不相同。一种产品包含多个特征（工序），特征的加工存在固定的先后顺序。36工程案例分析可重构制造系统调度问题问题假设：针对每台可重构机床切换不不同构型时的设置时间及成本是固定相同的。可重构机床加工期间针对某一产品特征加工时间固定不考虑其运行故障。一台可重构机床的一种构型至多对应一种产品的一个特征的加工，即不考虑一种可重构机床的构型可以生产一种产品的多个特征的加工的情况。每种产品类型的同一产品特征必须在一台可重构机床上连续生产，不允许间断及生产任务拆分。在零时刻所有可重构机床均可用，所有产品均可以被加工。37工程案例建模符号说明：索引常量符号含义i,j产品类型索引(i,j=(1,2,…,P))k,lm可重构机床索引(m=(1,2,…,M))c38工程案例建模常量符号说明：常量符号含义产品

i

的特征总数量可重构机床m的构型总数量产品i的加工数量产品i

的第k个特征在可重构机床m上的加工时间可重构机床m的构型切换时间产品i

的第k个特征能采用可重构机床m的第c个构型加工则为1，否则为0如果在可重构机床m上产品i

的第k个特征的加工构型与产品j

的第l个特征的加工构型不同则为1，否则为0足够大的数39工程案例建模符号说明：决策变量与辅助变量常量符号含义产品i

的第k

个特征的生产开始时间产品i

的第k

个特征的生产完成时间产品i

的最终生产完成时间如果产品i

的第

k个特征选择可重构机床m进行加工则为1，否则为0如果在可重构机床

m上产品i

的第

k个特征加工完成后紧接加工产品

j

的第

l个特征则为1，否则为040工程案例建模优化目标：Makespan

模型约束：1）产品特征加工时间约束41工程案例建模模型约束：2）产品前后特征的加工时间约束模型约束：3）产品完工时间约束模型约束：4）可重构机床上时间占用约束模型约束：5）构型加工约束42工程案例建模模型约束：6）可重构机床的一种构型至多对应一种产品的一个特征的加工模型约束：7）对于任意的一个产品特征必须被某一个可重构机床进行加工模型约束：8）可重构机床上一个特征加工至多只有一个紧前、紧后加工特征模型约束：9）定义变量的取值范围54基于强化学习的案例求解强化学习应用分析使用强化学习求解可重构制造系统调度问题，需要重点解决以下3个问题：如何有效地表示可重构机床制造系统的状态和动作空间？如何设计合适的奖励函数？如何选择合适的强化学习算法？55基于强化学习的案例求解编码产品特征的加工顺序子决策问题:基于可重构制造系统调度的问题特征，我们需要进行两个子决策问题的求解：

在满足同一产品前后加工特征的顺序约束的基础上，我们需要考虑在可供选择的可重构机床上先生产哪一产品特征，以及后生产哪一产品特征。不同的产品特征生产顺序会影响最终调度方案的整体完工时间。加工产品特征的可重构机床配置子决策问题:

在满足同一时刻一台可重构机床至多只能用于一项产品特征加工的约束基础上，我们需要考虑针对不同产品的不同特征选择哪一可重构机床进行加工。不同的可重构机床配置方案会影响可重构机床的加工进程，进而影响最终调度方案的整体完工时间。56基于强化学习的案例求解DQN算法状态表达

某一时刻的状态由完成加工特征数量、所有工件加工特征完成情况、加工设备当前构型情况、工件所在加工设备位置构成，以一个四元组对状态空间进行表示：常量符号含义表示完成加工特征数量。所有工件加工特征完成情况。表示当前智能制造系统中加工设备的构型情况。表示工件当前所处的位置。57基于强化学习的案例求解1N:加工特征数量当完成加工特征数量与总计工件加工特征数量相等时，完成加工任务。2F:所有工件加工特征完成情况

58基于强化学习的案例求解3C:智能制造系统中加工设备的构型情况

4P:当前工件所在加工设备的编号

59基于强化学习的案例求解定义动作动作可以定义为四个部分：12选择需要加工的工件加工特征选择需要加工的工件34选择进行加工操作的机床的构型选择进行加工操作的机床

60基于强化学习的案例求解定义奖励函数以最小化最大完工时间为目标，设置智能制造系统集成式工艺-重构-调度问题的奖励函数如式所示：

条件1

条件2所选动作不满足约束要求，例如动作中的机床构型无法对对应工件的加工特征进行加工时；工件的加工特征需要在完成其他加工特征之后进行加工等情况，将获得一个负值惩罚。61基于强化学习的案例求解本案例采用DQN算法进行求解DQN算法迭代DQN算法是一种将深度神经网络和Q学习结合的方法，用于解决高维、连续的状态空间和动作空间的问题。DQN算法的核心思想是使用神经网络来近似Q值函数，即给定一个状态和一个动作，输出该动作在该状态下的期望回报。62基于强化学习的案例求解构建DQN神经网络：.........输入层维度2032维隐藏层28维输出层本文所构建的神经网络定义了四层神经网络，分别是输入层、两层隐藏层和输出层。每两个层都设置一个权重矩阵，用于将输入向量映射到输出向量。权重矩阵的维度由输入和输出的大小决定，例如输入层的权重矩阵的维度是（20，32），表示它可以将20维的向量映射到一个32维的输出向量。权重矩阵的初始值是从均值为0，标准差为0.1的正态分布中随机采样的。...16维隐藏层63基于强化学习的案例求解初始化DQN神经网络：在构建了神经网络的结构后，需要进一步初始化两个神经网络。一个神经网络用于评估当前状态下的动作值，另外一个神经网络用于计算目标动作值，两者的结构相同，但是参数不同，随机初始化两个神经网络的参数。定义：折扣因子探索率记忆容量损失函数记忆库学习率网络更新频率64基于强化学习的案例求解记忆容量记忆库损失函数记忆容量是指DQN算法中用于存储经验回放的缓冲区的大小。记忆容量需要根据实验结果进行调整，找到一个合适的平衡点。记忆库是用于储存和重用之前经验的一种机制。可以打破数据之间的相关性提高学习效率和稳定性。每次更新神经网络的参数时，DQN算法会从记忆库中随机抽取一批样本进行训练，而不是仅仅使用最近一次经验。损失函数是一种用来衡量神经网络预测值和目标值之间差异的函数，它可以指导神经网络的参数更新，使得预测值更接近目标值。在强化学习DQN算法中，损失函数通常是均方误差（MSE）网络更新频率标准DQN引入了一个延迟更新的目标网络用来计算Q的目标值，避免Q网络误差的“自激效应”，并借此来提高训练稳定性。65基于强化学习的案例求解迭代过程：动作选择模块：66基于强化学习的案例求解迭代过程：记忆库模块：67基于强化学习的案例求解迭代过程：学习模块：目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践68工程实例产品类型产品数量特征数量1A20032B50033C10044D3002针对如下所示的具体实例数据进行遗传算法的编写。生产订单信息可重构机床构型数转换时间转换成本1A38003502B56003003C31000500可重构机床信息69工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)1-2F(1,2)-41F(1,3)213F(2,1)23-F(2,2)3-1F(2,3)11-F(3,1)-52F(3,2)2-1F(3,3)143F(3,4)33-F(4,1)143F(4,2)322产品特征对应机床构型表70工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)5-8F(1,2)-1012F(1,3)679F(2,1)1319-F(2,2)10-5F(2,3)812-F(3,1)-49F(3,2)6-1F(3,3)3710F(3,4)93-F(4,1)594F(4,2)836产品特征加工时间（Min）71参数设置算法参数设定值批量大小512学习率0.01折扣因子0.9贪婪策略因子1记忆容量2000Q网络更新频率10072构建神经网络代码导入依赖包，定义超参数72构建神经网络代码设置神经网络结构。构建四层神经网络，分别是输入层、两层隐藏层和输出层。每两个层都设置一个权重矩阵，用于将输入向量映射到输出向量。73构建DQN智能体构建DQN智能体74智能体环境构建导入依赖包，环境变量设置75智能体环境构建初始化环境状态73智能体环境构建动作转移策略77迭代主函数动作转移略导入依赖包78迭代主函数动作转移略循环迭代79迭代主函数动作转移略循环迭代80其他相关函数工件类相关函数格式转化函数81其他相关函数格式转化函数设备类相关函数82其他相关函数表格设置相关83其他相关函数表格读取数据84其他相关函数表格读取数据85其他相关函数表格读取数据86表格设置工件特征表工件数量表机床间距表加工时间表机床表构型变化表87DQN算法结果DQN算法迭代优化图最优策略对应的Gantt图主讲教师：黄思翰本节结束模拟退火算法目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践模拟退火算法发展历程Metropolis提出重要性采样方法，即以概率来接受新状态，可以显著减小计算量。第一次使用模拟退火算法求解组合优化问题多目标优化和并行模拟退火基于蒙特卡洛方法的改进，更好地模拟系统的随机性。19832010s19531990s