Ch01 概述
1.1 石材的优化排样技术
优化样的目的：寻找某种优化的布局方式，使得平面区域的面积利用率较高。
石材行业的排样问题又称为下料问题，通常是指在一定数量的石材大板形状和尺寸给定的区域上，尽可能多地排放所需要的石材工程板。
石材排样问题需要满足“一刀切”约束。
注：“一刀切”约束就是直线切割，即板材的每一次分割都必须从板材的这一端沿直线到另一端。
1.2 石材排样问题分类
- 一维排样问题：原料为棒料、管材和型材时，在已知其尺寸和数量等情况下如何优化切割排样，提高材料利用率。问题简单，应用较少。
- 二维排样问题：原料为二维板材时，在已知其尺寸和数量等情况下如何优化切割排样，提高材料利用率。原料形状可以是：矩形、圆形、扇形等规则形状，或者不规则形状，求解过程属于高计算复杂度问题。类别细分：
- 矩形板材单一排样：工程板材尺寸固定，而石材大板尺寸在一定范围内，使得工程板在大板上排列最多。排样方案必须满足一刀切约束，便于在想入桥式切割机上加工。
- 矩形板材混合排样：工程板材具有几种不同的尺寸规格，石材大板尺寸在一定范围内变化，排列方式没有方向性，但是排样方案必须满足一刀切约束，便于加工。
- 缺陷矩形石板排样：工程板材尺寸固定，石材大板尺寸固定，但是石材大板存在缺陷（空洞或者大斑），排样方案必须绕过缺陷，还要满足一刀切约束，便于加工。
- 不规则石板上的最大内接矩形排样：石材大板的边缘凹凸不平，需要寻找最大的内接矩形。
- 三维排样问题：问题复杂，应用较少
1.3 石材优化排样方法
排样问题是经典的 NP（nondeterministic problem）完全问题，以目前的计算理论和算法，或者根本无解，或者求解代价不可接受。因此，石材排样结合最优化原理求其有效近似最优解。
1.3.1 最优化问题的数学模型
最优化问题数学模型的构成
最优化问题的数学模型由三个基本要素构成：设计变量、约束条件和目标函数
设计变量：设计中可以独立改变的基本参数。设计变量的每一个确定的取值对应着一个设计方案，对应于最优化方案的设计变量取值称为最优点或者最优解。与最优点相对应的目标函数值称为最优值。设计变量用 $X\in\mathcal{R}^n$ 表示，$x_i,i=1,2,\cdots,n$为第$i$个变量
$$
X=[x_1:x_2:\cdots:x_n]^T=\begin{bmatrix}x_1\x_2\\vdots\x_n\end{bmatrix}
$$约束条件：求目标函数极值时的某些限制称为约束条件，简称约束。它也是对设计变量取值限制。
$$
\begin{align}
h_i(x_1,x_2,\cdots,x_n)=0\
g_i(x_1,x_2,\cdots,x_n)\le0
\end{align}
$$目标函数：评价设计方案的质量，是设计变量的函数，也称为评价函数。其数学描述为
$$
f(X)=f(x_1,x_2,\cdots,x_n)
$$
综上所述，最优化问题的数学模型就是对实际问题的数学抽象，得出一个在设计变量满足约束条件，求目标函数极值的数学表达式。其数学描述为
$$
\begin{cases}
\min&f(X),&X\in\mathcal{E}^n\
s.t.&g_u(X)\le0,&u=1,2,\cdots,m\
&h_v(X)=0,&v=1,2,\cdots,p
\end{cases}
$$
其中，$X$为设计变量，$f(X)$为目标函数，$g_u(X)$为不等式的约束条件，$h_v(X)$为等式的约束条件。
最优化问题的求解过程
- 分析待优化问题，建立数学模型：明确设计要求，掌握已知条件，明白设计准则。在此基础上，明确设计变量、性能指标，构造目标函数和约束条件的关系式，并且选定计算精度等。然后基于问题建立最优化模型
- 分析数学模型，选择最优化方法：选用方法的几条原则
- 求解的成功率或者可靠性要高
- 逻辑结构简单，计算程序不复杂
- 数值稳定性好，计算精度高
- 计算工作量小，求解速度快
- 编制计算程序，求得最优解：基于计算机能力对最优化问题进行分类
- 小型最优化问题：设计变量和约束条件不超过10个
- 中型最优化问题：设计变量和约束条件不超过50个
- 大型最优化问题：设计变量和约束条件不超过200个
- 待研究优化问题：设计变量和约束条件均超过200个
- 检验结果，输出决策：对计算出的最优解和最优值进行检验，对算法的收敛性、通用性、简便性、效率和精度等进行评价，最后确认最优方案。
1.3.2 矩形排样优化方法
矩形排样优化方法介绍
- 枚举法：对整个可选择解空间的氯碱的性能进行比较并找出最优点作为问题的最终解
- 优点：简略简单
- 缺点：计算工作量极大，只有应用于可行解空间是有限集合的情况
- 以解析法为基础的数值解法：在搜索过程中使用目标函数的解析性质（一阶导数、二阶导数等）。常用的解析搜索法：牛顿法、共轭梯度法，爬山法等。梯度法是根据目标函数的梯度方向来确定下一步的搜索方向，由于搜索策略是沿着最陡的方向爬向一个最优点，因此当问题存在多个极值点时，可能找出的最优解是局部极值点而不是全局极值点。
- 随机法：在搜索过程中对搜索方向引入随机的变化，使得算法在搜索的过程中可以以较大的概率跳出局部极值点
- 盲目随机法：在可行解空间内随机地选择不同的点进行检测
- 导向随机法：以一定的概率改变当前的搜索方向，从而跳出局部极值点，特别适合求解具有多极值点的问题，目前使用最广泛的是遗传算法
- 贪心算法：改进了的分级处理方法。根据某个优化测度，一步一步地进行优化，每一步都要保证能够获得局部最优解。每一步只考虑一个数据，它的选取需要满足局部优化条件。如果下一个数据与部分最优解连在一直不再是可行解，就不添加该数据到部分解中，直到把所有数据枚举完，或者不能再添加。这种能够得到某种试题意义下的最优解的分级处理方法称为贪心法。
常用的矩形优化排样算法
局部优化算法
- 背包算法
- 动态规划算法
- 线性规划算法
全局优化算法
- 模拟退火算法
- 蚁群算法
- 遗传算法
矩形排样优化算法的需求分析
- 板材尺寸与矩形件尺寸的比例不确定之间的矛盾：有时板材尺寸与矩形尺寸的比例相差较大，而有时相差较小。不同的算法可能适应不同的问题。
- 矩形件种类与数量之间的矛盾：批量生产时，矩形件种类少，但是数量大；定制生产时，矩形件种类多，但是数量少。因此，需要建立带有数量约束的混合排样优化数学模型。
- 优化排样的效率与计算时间之间的矛盾：较高的材料利用率与较短的等待时间，得到一个较好的近似最优解
- 下料的工艺问题：一刀切与混合切割。混合切割的材料更省，但是成本更高。
Ch02 矩形工程板单一优化排样问题
应用线性规划算法和动态规划算法对矩形工程板进行单一排样优化下料。
2.1 矩形单一排样问题的几个概念
2.1.1 毛坯的方向、条带和级
毛坯的方向：矩形毛坯在排样时存在方向问题，这里将毛坯的长度方向定义为毛坯的方向。
条带：为了满足一刀切的工艺要求，将同一方向的毛坯横向或者纵向排列成一行或一列，这种组合称为条带。
级：将长度相等、方向相同、所含毛坯数相同的几根条带在垂直于条带的方向上排列，这样的组合称为级。
2.1.2 规范多级方式
规范多级方式：是一类特殊的排样切割方式。
- 规范：是指满足一刀切的工艺要求。
- 多级：是指在大板上排列多个不同方向的级
假设在一张板材上已经排样完毕，反向按照级被切下的顺序对级进行编号，那么所有编号为奇数的级必须有相同的方向，所有编号为偶数的级必须有相同的方向，而且编号为奇数的级的方向与编号为偶数的级的方向之间相互垂直，这种排列方式称为规范多级方式。
定理2-1：在保持毛坯数不减少的情况下，任意非规范多级切割方式都可以转换为规范多级方式。^1
2.2 基于线性规范方法的单一矩形排样
2.2.1 单一矩形排样的线性规范算法基础
在一定的约束条件下，求一个目标函数的极大（或者极小 ）的优化模型称为数学规划，包括：约束性数学规划和无约束性数学规划。
线性规划是（linear programming）属于约束性数学规划，是最简单、最基础的一类数学规划问题，其历史悠久、理论比较成熟、方法比较完善，研究方向为：
- 通过统筹安排，使得一项任务尽量做到最少的资源来完成
- 通过统筹安排，使得固定的资源尽量做到完成最多的任务
线性规划问题的特征：
- 每一个问题都有未知数来表示某一方案，通常这些未知数都是非负的 ，它们称为决策变量。
- 存在一定的限制条件，通常称为约束条件，它们可以用一线性等式或者不等式来表达。
- 存在目标要求，并且这个目标可以为一组未知数的线性函数，通常称为目标函数。根据实际问题的不同，要求目标函数实现最大化或者最小化。
因此，设计变量、约束条件和目标函数组成了线性规划数学模型的三个要素。
求解线性规划问题的最常用方法：单纯形法。
$$
\begin{align}
\max &f(X)=c_1x_1+c_2x_2+\cdots+c_nx_n\
s.t. &a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1n}x_n=b_1\
&a_{21}x_1+a_{22}x_2+a_{23}x_3+\cdots+a_{2n}x_n=b_2\
&\vdots\
&a_{n1}x_1+a_{n2}x_2+a_{n3}x_3+\cdots+a_{nn}x_n=b_n\
&x_i\ge0,i=1,2,\cdots,n
\end{align}
$$
线性规划数学模型的非标准形式与标准形式的区别：
- 目标函数为求最小值，而不是求最大值
- 约束条件为不等式，而不是等式
- 自由变量可能为负值，而不是非负值
将不同形式的线性规划模型转化为标准型的方法：
- 将目标函数求最小值转化为求最大值
- 将不等式的约束转化为等式约束
- 对于小于等于型不等式： $a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n\le b_i$，引入新变量 $y_i\ge 0$，将不等式转化为 $a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n+y_i=b_i$，其中 $y_i$ 称为松弛变量
- 对于大于等于型不等式：$a_{j1}x_1+a{j2}x_2+\cdots+a_{jn}x_n\ge b_j$，引入新变量 $y_j\ge 0$，将不等式转化为 $a_{j1}x_1+a{j2}x_2+\cdots+a_{jn}x_n-y_j=b_j$，其中 $y_j$ 称为剩余变量
- 将自由变量化为非负变量：在线性规划的数学模型中，有某个变量 $x_k$ 没有非负的要求，则称 $x_k$ 为自由变量，通过变换 $x_k=x_{k1}-x_{k2}, x_{k1}\ge 0,x_{k2}\ge 0$ 可以将一个自由变量化为两个非负变量
2.2.2 单一矩形排样线性规划数学模型
（详情参考原书）
建立数学模型
求解数学模型
几种特殊情况
2.2.3 线性规划方法的程序设计
（详情参考原书）
程序设计思想
程序实现方法
2.3 基于动态规划算法的单一矩形排样
2.3.1 单一矩形排样动态规划算法基础
动态规划算法的基本概念
动态规划是解决多阶段决策过程最优化问题的一种方法。基本思路是将一个多阶段决策问题转化为依次求解多个单阶段的决策问题，并将前面的解传递并纳入下一个阶段一并考虑，即使到使求解的各阶段间具有递推性。
- 阶段：在动态规划问题中总要把大问题化成若干个相互联系的小问题，这些小问题的解决构成了原问题求解过程中的几个步骤，即几个阶段。
- 状态：为了量化动态过程，便于进行数学上的分析与计算，需要给整个过程定义一些状态变量。把每一阶段的输入 $x_k$（$k$表示第$k$个阶段）称为状态变量。通常第$k$个阶段的输入状态变量就是第$k-1$个阶段的输出状态变量，每一阶段的状态变量可以是一个数、一组数或者一个连续函数。当各个阶段状态和最终状态确定后，整个过程就完全确定了。于是，整个问题的演变过程就可描述为状态序列${x_1,x_2,\cdots,x_n}$
- 决策：从某阶段的给定状态出发，到下一个状态时对方案的选择。像状态变量一样，决策也可以是一个数或者一组数，称为决策变量。对于整个问题的最优化过程，在各个阶段选取的决策变量值应该使全局最优。
- 策略：在各阶段决策确定后，整个决策过程便决定了一个决策函数序列${u_1(x_1),u_2(x_2),\cdots,u_n(x_n)}$，称为一个策略。最优策略是指整个动态过程按照指定的准则达到最优的策略。从某一个阶段开始到过程最终的决策序列称为过程的一个子策略，记为${u_k(x_k),u_{k+1}(x_{k+1}),\cdots,u_n(x_n)}$，$k$表示从第$k$个阶段开始。
- 状态转移议程：在确定决策过程中，当第$k$个阶段的状态变量$x_k$和决策变量$u_k(x_k)$确定后，第$k+1$个阶段的状态变量$x_{k+1}$也就确定了，写成函数$x_{k+1}=g_k[x_k,u_k(x_k)]$，称为状态转移方程。其中，$g_k$为变换，$x_k$为第$k$个阶段的输入状态变量，$u_k(x_k)$为第$k$个阶段状态为$x_k$时选择的决策变量。
- 目标函数：在一个决策过程中，总要确定一个度量决策好坏的标准，称为目标函数。它是某种效益试题，与状态变量和决策变量相关，第$k$个阶段的目标函数为$V_k(x_k,u_k)$，使用$V_{k,n}(x_k,u_k,x_{k+1},u_{k+1},\cdots,x_n,u_n)$表示从状态$x_k$出发到状态$x_n$为止的效益目标函数，最优目标函数是指对某一确定状态选取最优策略后得到的目标函数值。
动态规划算法的数学模型
动态规划算法的关键在于正确写出基本递推关系式和恰当的边界条件。实现方法：先将问题的过程分为几个相互联系的阶段，恰当地选取状态变量和决策变量，并且定义最优函数，从而把一个大问题化为一组同类型的子问题，然后逐个求解。
动态规划数学模型的解法
一般的动态规划数学模型，其求解过程都是逆序的，即从问题的最后一个阶段开始，往前依次逆阶段寻优。
2.3.2 单一矩形排样动态规划数学模型
（详情参考原书）
2.3.3 动态规划算法的程序设计
（详情参考原书）
2.4 矩形单一排样模块的程序设计
（详情参考原书）
Ch03 矩形工程板混合优化排样问题
应用遗传算法对矩形工程板进行有约束和无约束的混合排样。
3.1 矩形工程板的混合排样问题简述
在一张大板上采用不同尺寸工程板进行排样的方法，即混合排样方法。
- 矩形工程板的无约束混合排样问题：在固定长和宽的大板上排样多种工程板，但是对工程板的数量没有限制
- 矩形工程板的有约束混合排样问题：在确定长和宽的大板上排样多种工程板，但是对工程板的数量存在限制
“约束”指的是数量上的约束，与优化数学模型的“约束条件”不同。
3.1.1 矩形工程板的无约束混合排样问题
已知待排样的工程板材和库存大板的长与宽，工程板材的需求数量没有约束，目的是在一张大板上排放的工程板材的面积达到最多，称为工程板的无约束优化排样问题。
3.1.2 矩形工程板的有约束混合排样问题
已知待排样的工程板材和库存大板的长与宽 ，工程板材的需求数量存在约束，目的是满足约束时需要的大板面积最小，称为工程板的有约束优化排样
3.1.3 矩形工程板混合排样方式
- 单尺寸条带排样方式
- 多尺寸条带排样方式
- 其他排样方式
3.2 矩形工程板混合优化排样数学模型
3.2.1 矩形工程板无约束混合优化排样算法的数学模型
目的是在一张板材上排放的工程板达到最多。由于一刀切原则的需要，工程板可以横放也可以竖放，但是在纵方向上每行只能摆放一种工程板，每一行的工程板只能使用一种排放方式（横放或者竖放）。
（详情参考原书）
3.2.2 矩形工程板有约束混合优化排样算法的数学模型
目的是排样所需的大板面积最小，或者所排工程板的面积总和最大。工程板可以横放或者竖放，但是板材在纵方向上每行只能摆放一种工程板，每一行的工程板只能使用一种排放方式（横放或者竖放）。
（详情参考原书）
3.3 矩形工程板混合排样数学模型的求解
3.3.1 混合优化排样数学模型求解算法
由于目标函数 $S$ 为非线性函数，约束条件也为非线性，而且既有等式约束，也有不等式中，所以该问题为单目标非线性组合优化问题，其函数含有多个贬值，求解时容易陷入局部最小值，因此求解这类问题需要能够全局搜索并且速度较快的优化方法。
近似算法^2属于启发式算法的一种，可以解决工程板的优化排样问题，但是排样结果呈现锯齿形，不适合一刀切的约束条件。
遗传算法提供了一种求解复杂系统优化问题的通用框架，不依赖于问题的具体领域，对问题的种类具有很强的鲁棒性，可以应用于许多学科中求解可行解问题，而且只要改变相应的编码方式，就能够解决近似算法排样结果呈现的锯齿性问题。
遗传算法理论
遗传算法（genetic algorithms, GA）借助生物界的进化机制“适者生存，优胜劣汰”在人工适应系统中设计一种随机化搜索机制。由 Holland 最先提出，并且设计了算法的操作原理，还利用统计决策理论对算法的搜索机理进行了理论分析，建立了著名的模式理论（schema theory）和隐含并行性（implicit parallelism, IP）原理，为遗传算法的发展奠定了基础。在工程领域，特别是人工智能与控制领域出现的超大规模的非线性系统，无法使用经典优化方法求解其优化问题；算法本身可以独立于原始系统。因此，算法在多个学科得到广泛应用。
遗传算法思想
从代表问题可能解集的一个种群开始，把待解决问题的参数编成二进制码或十进制码，即基因。若干基因组成一个染色体（个体）许多染色体进行类似于自然选择、配对交叉和变异的运算，经过多次重复迭代（世代遗传）直到得到最后的优化结果。
算法以群体为基础，能同时从不同点获得多个极值，因此不易陷入局部最优；算法对问题变量的编码集进行操作，而不是对变量本身，有效地避免了对变量的微分操作；算法只是利用目标函数来区别群体中个体的好坏，而不必对其进行过多的附加操作。
算法操作的是一群编码化的可靠解，称为种群。通过种群的更新与迭代来搜索全局最优解。种群的迭代通过选择、交叉和变异等算法实现。^3
表3-1 遗传算法的概念与最优化概念之间的关系
| 遗传算法 | 最优化理论 |
|---|---|
| 个体 | 解/单一可行解 |
| 染色体 | 解的编码 |
| 基因 | 解的每个分量 |
| 群体 | 选定的一组解（其中解的个数为群体的规模） |
| 种群 | 根据适应度函数值选取的一组解 |
| 交叉 | 通过交配原则产生一组新解的过程 |
| 变异 | 编码的某一个分量发生变化的过程 |
遗传算法求解过程
- 基本遗传算法（simple genetic algorithm, SGA）：只使用选择（selection）、交叉（cross）和变异（mutation）三种基本遗传算子，其遗传进行操作简单，容易理解。定义为一个8元组 $SGA=(C,E,P_0,m,\Phi,\Gamma,\Psi,T)$，其中$C$为个体的编码方法；$E$为个体适应度评价函数；$P_0$为初始群体；$M$为群体规模大小；$\Phi$为选择算子；$\Gamma$为交叉算子；$\Psi$为变异算子；$T$为遗传运算中止条件。
- 算法的主要步骤：
- 随机产生一组初始个体构成初始种群，并且评价每一个个体的适应值
- 判断算法收敛准则是否满足，如果满足则输出搜索结果，否则执行下面的步骤
- 根据适应值大小以一定的方式执行复制操作
- 按照交叉概率$P_c$进行交叉操作
- 按照变异概率$P_m$进行变异操作
- 返回（2）
- 遗传编码方法：编码方法是把问题的搜索空间中每个可能的点定义为确定长度的特征串
- 二进制编码：对于多维的、高精度要求的连续函数优化问题，则存在连续函数离散化时的映射误差，同时不便于反映所求问题的特定知识
- 实数编码：个体的每个基因值用实数表示
- 其他编码方式：多值编码、实值编码、区间值编码、Delta编码等
- 适应函数：为群体中每个可能的染色体指定一个适应度值，通过计算搜索空间中每个确定的染色体的适应度值，确定它在此环境下的生存能力
- 遗传算子：标准遗传算法的三种操作算子（选择、交叉、变异）构成了遗传算法的搜索核心，是模拟自然选择和遗传过程中发生的繁殖、杂交和突变现象的主要载体。遗传算法利用遗传算子产生新一代群体来实现群体进化，算子也是调整和控制进化过程的基本工具。
- 终止循环条件：遗传算法迭代地执行从父代产生子代的过程，直到满足某个停止准则。
- 设定最大迭代次数，一般为3000~6000
- 找到某个较优的染色体。
- 设定群体的收敛程度。
- 处理约束条件的DCPM方法：直接比较——比例方法（direct comparison-proportional method, DCPM）是约束处理方法，提供了群体中个体的比较准则，给出了群体中保持一定比例的不可行解的适应性策略。
- 算法特点：遗传算法是一类可以用于复杂系统优化计算的鲁棒搜索算法，与其他一些优化算法相比
- 优点：
- 遗传算法的操作对象是一组近似解，而非单个可行解；搜索轨道有多条，采用多点搜索，具有良好的并行性。
- 遗传算法以决策编码作为运算对象，而非实际值来进行算法优化，其运算是以决策变量的某种形式的编码作为运算对象，使得优化计算过程可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传与进行等机制，特别是对一些无数值的优化问题，更易于操作。
- 遗传算法是一种自适应的搜索技术，而确定性的搜索方法，其运算都是以概率方式进行的，从而增加了搜索过程的灵活性，并能以很大的概率收敛于最优解，具有较好的全局优化求解能力。
- 遗传算法操作的可行解集是经过编码化的（通常采用二进制编码），目标函数解释为编码化个体（可靠解）的适应度值，因而具有良好的可操作性与简单性。
- 遗传算法直接以目标函数值作为搜索信息就能确定搜索方向，而不需要目标函数的导数值等其他辅助信息，对于目标函数是难于求导的函数时，应用起来比较方便。
- 缺点：遗传算法的收敛速度慢、计算量大
- 优点：
3.3.2 遗传算法求解矩形工程板混合排样
遗传算法的基本步骤：
- 对于需要解决的问题进行基因编码
- 随机初始化群体
- 评价群体
- 应用选择算子
- 应用交叉算子
- 应用变异算子
- 所选参数及停止准则
（详情参考原书）
3.4 矩形工程板混合优化排样程序设计
（详情参考原书）
Ch04 缺陷石板的单一优化排样问题
4.1 缺陷石板排样问题
典型的组合优化问题，分别计算所有的排版方案，选择其中最优的。
4.2 缺陷石板优化排样的数学模型
数学模型
$$
\begin{align*}
N=\max\sum_{i=0}^3[(1-r_i)n_ix_i+r_im_iy_i]\
L-[(1-r_0)x_0w+r_0y_0l]\ge0\
y_{\min}-[(1-r_0)n_0l+r_0m_0w]\ge0\
W-[(1-r_0)n_0l+r_0m_0w]-[(1-r_1)n_1l+r_1m_1w]\ge0
\
x_{\min}-[(1-r_1)x_1w+r_1y_1l]\ge0\
L-[(1-r_1)x_1w+r_1y_1l]-[(1-r_2)x_2w+r_2y_2l]\ge0\
W-y_{\max}-[(1-r_2)n_2l+r_2m_2w]\ge0\
L-x_{\max}-[(1-r_3)x_3w+r_3y_3l]\ge0\
W-[(1-r_0)n_0l+r_0m_0w]-[(1-r_2)n_2l+r_2m_2w]-[(1-r_3)n_3l+r_3m_3w]\ge0
\end{align*}
$$
其中，$N$为可排的最大工程板的块数；$L$为均质大板的长度；$W$为均质大板的宽度；$l$为工程板的长度；$w$为工程板的宽度；$i$取$(0,1,2,3)$分别表示第$i$块工程板；$r_i=0$表示横放；$r_i=1$表示竖放；$m_i$为大板上第$i$块区域内工程板横放时可排多少行；$n_i$为大板上第$i$块区域内工程板竖放时可排多少行；$y_i$为大板上第$i$块区域内工程板横放时每行可排多少个；$x_i$为大板上第$i$块区域内工程板竖放时每行可排多少个；$x_{\min}$为缺陷横坐标的极小值；$x_{\max}$为缺陷横坐标的极大值；$y_{\min}$为缺陷纵坐标的极小值；$y_{\max}$为缺陷纵坐标的极大值。
在模型中，各条件之间相互制约，为一个带约束的组合优化问题。通常采用的方法都是抛弃不可行解，但是考虑到有些解虽然不可行，但是接近极大解，因此可以采用 3.3.1 节的 DCPM 约束处理算法，基于群体中个体的比较准则，给出在群体中保持一定比例的不可行解的适应性策略。
4.3 遗传算法求解缺陷石板优化排样
在该排样问题中，搜索所有解是不可行的，因此采用遗传算法随机从一个解开始，逐步进化到最优解，从而避免在巨大的解空间中搜索，并且可以基于用户的判断随时终止算法的搜索过程，确定适应生产实际情况的排版方案。
4.3.1 基因编码
采用二进制编码方法。
4.3.2 初始化群体
设初始群体为$P(0)=(s_1,s_2,\cdots,s_N)$，选择$N$为群体的规模，随机产生$N$个长度为32的二进制编码的染色体作为初始种群。
注：种群规模的大小对算法的运行效果会有影响。种群太小会影响多样性，不利于适应度高的染色体的进化，难以得到满意解；种群太大影响计算效率，得到满意解需要消耗过多资源。
4.3.3 评价群体
- 根据编码方式将染色体位串解码得参数 $r_i,m_i/n_i,y_i/x_i$
- 定义适应度函数：$f=\sum_{i=0}^3[(1-r_i)n_ix_i+r_im_iy_i]$
- 将第1步输出的解码结果代入适应度函数，得到输出再计算 viol 值
- 根据适应度值、viol 值和$\varepsilon$值，按照 DCPM 比较准则用竞争选择方法生成下一代
4.3.4 应用遗传算子
- 采用多点交叉方法，选出需要交配的一对个体，在区间$[1,31]$中随机选取三个交叉位置。在交叉点之间的变量间续地相互变换，产生两个新的后代，但在第一个交叉点之前的不进行交换
- 再应用变异算子。变异概率 $p_m$ 的取值范围设定为 $p_m=(e^x-1)/(e^{0.7}-1),x\in{0.0,\cdots,0.7}$。在遗传算法中，变异算子基于变异概率随机反转某位等位基因的二进制字符来实现。
- 所选参数和停止准则。通过以上步骤产生新一代群体$P(t+1)$，这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想；当计算到第 $K$ 代时若群体收敛则停止。
4.4 缺陷石板优化程序设计
（详情参考原书）
Ch05 不规则石材大板最大内部矩形问题
5.1 最大内部矩形问题的描述
最大内部矩形（maximum enclosed rectangle, MER）问题在空间数据索引、图像目标特征提取、模拟集成电路布线、二维零件优化排样等过程中都会遇到。
MER 问题就是在一个任意不规则的封闭图形中寻求一个内部的最大矩形，对于这个矩形需要满足的条件：
- 矩形必须位于任意不规则封闭图形之内，矩形的边和顶点不能走出封闭图形的边界，即整个矩形都位于封闭图形之内
- 矩形必须满足矩形的基本条件：四个内角都为 $90^\circ$
- 矩形必须是封闭图形内最大的矩形
由上述条件可知，所求问题不仅包含集合之间关系的差别，还具有等式约束，因此此问题求解时不存在多项式时间内的精确算法，属于NP-hard问题
5.2 最大内部矩形问题的数学模型
5.2.1 最大内部矩形数学建模
任意不规则图形的MER问题就是在一个任意不规则的封闭图形区域内寻求一个最大的内部矩形，其设计变量为矩形四个顶点的坐标值$P_1(X_1,Y_1),P_2(X_2,Y_2),P_3(X_3,Y_3),P_4(X_4,Y_4)$。在评价内部矩形是否最大时，目标函数采用最大面积作为评价准则，约束条件为：
- 矩形的四个坐标点位于任意不规则图形的边界上或者边界内
- 不规则图形的所有边界坐标点都必须位于矩形边界外或者边界上
- 内接的四边形必须为矩形，即四条边的任意一条边都与其相信的边相互垂直，与其对边相互平行
（详情参考原书）
5.2.2 问题的性质及常见的求解方法
最优化问题按照变量的性质分为两类：
- 连续变量问题
- 离散变量问题：也称为组合优化（combinatorial optimization）问题。常用的优化算法：
- 经典算法：线性规划、动态规划、整数规划、分支定界法
- 现代智能算法：人工神经网络、遗传算法、模拟退火、禁忌搜索
5.3 遗传算法求解最大内部矩形
5.3.1 编码方式
遗传算法将优化变量转化为由基因按照一定方式进行排列的染色体，即进行编码处理。
由问题空间向遗传算法编码空间的映射，称为编码（encoding）。
遗传算法的进化过程是建立在编码机制上的，编码方式的选择与设计影响着算法的性能，还决定着个体从搜索空间的基因型转换到解空间的表现型的解码方法。
基因编码的三个基本原则：
- 完备性（completeness）：问题空间中的所有点（潜在解）都能成为遗传算法编码空间中的点（染色体位串）的表现型。
- 健全性（soundness）：遗传算法编码空间中的染色体位串必须对应问题空间中的某一潜在解。
- 非冗余性（non-redundancy）：染色体与潜在解必须一一对应。
基因编码的常用方式：
- 二进制编码
- 格雷码编码
- 浮点数编码：能够消除因编码精度不够导致的因为编码精确度不够无法取得最优解的问题，可以消除海明悬崖（hamming cliffs）^4
- 排列编码
5.3.2 初始种群生成方法的设计
为了提高种群的多样性，提高算法的效率，在随机生成初始种群时加入了一定比例的两种类型的染色体：
- 四个顶点坐标值都不超过不规则图形边界的矩形种群
- 满足边界条件的任意四边形种群
两类种群通过四个顶点的连线得到一个四边形，然后利用射线法[^5]差别四边形的顶点和四条边是否在不规则图形的边界区域范围之内：
- 如果是，则利用这四个顶点生成一个染色体基因
- 如果否，则利用上述过程重新随机产生一个四边形
5.3.3 带有惩罚项的个体适应度评价
基于惩罚项可以评价染色体对约束条件的不满足程度，从而扩大了解的搜索空间，使得一部分不可行解具有一定的生存机会，从而可以保留不满足约束条件的基因中存在的优良的基因片段，使得算法可以更加有效地全局搜索解空间，从而避免落入局部最优解。
5.3.4 遗传操作算子
- 对种群进行选择操作，完成个体的优胜劣汰，适应值高的个体更有机会遗传基因给下一代，计算每个基因的适应度函数值并且通过轮盘赌进行选择，每一个个体的适应值大小决定了其被选择进行遗传操作的概率。经过选择，使得整个优化过程向着适应值大的方向进行。
- 对选择得到的优良个体进行交叉操作，将原有的优良基因遗传给下一代，并且在遗传过程中产生更加复杂的新个体
- 觉的交叉形式：单点交叉、多点交叉、一致交叉
- 对交叉得到的个体进行变异操作，每一个染色体的变异基于$[0,1]$之间随机产生的变异概率
5.3.5 精英保存及竞争策略
为了避免遗传操作时破坏了种群内的最优基因，可以采取精英保存策略，将每一代种群中的最优染色体基因直接复制到下一代的染色体基因池中，从而保证算法的收敛性。
为了提高算法的收敛速度，将每一代的父代及父代经过每一个遗传算子操作后产生的染色体基因整合在一起进入基因池中，这样就会使得基因池中包含全部遗传过程中产生的染色体基因。
5.3.6 遗传算法的执行流程
1 | graph TB |
进化终止原则一般是最优染色体基因适应值达到设定的预定值或者满足了预定的遗传的迭代次数。
5.4 遗传算法求解 MER 问题的实例应用
（详情参考原书）
参考文献
[^5]：陈瑞卿，周健，虞烈，一种判断点与多边形关系的快速算法，西安交通大学学报，2007，41（1）：59-63