本发明涉及矩形件二维排样的技术领域，尤其是涉及基于自适应遗传算法的矩形件优化排样方法。
背景技术：
在如今的工业生产领域，矩形件二维排样的应用十分广泛，比如石材、玻璃、皮革等材料的切割，如何在上面优化布局使原材料得到最大限度的利用，需要寻找出一种矩形件的排列组合而使剩余面积s最大化，但随着矩形件数目的增多，其排列组合将呈爆炸式增长，无法在短时间内寻找出最优解，现有存在技术也大多是利用一些智能优化算法，比如遗传算法、蚁群算法、模拟退火算法等寻找近似最优算法，但运用这些算法时优化目标函数考虑单一，参数也大多是预先固定，导致算法运行结果对参数设置依赖很大。
例如，一种在中国专利文献上公开的“一种基于遗传算法的排案优化方法”，其公告号cn108090650a，该发明建立各矩形待排件数学模型，确定待排件尺寸规模，将各待排件及其待排属性视为一个基因，并进行基因编码；由一组待排件组成一个种群，其基因组成视为一组染色体；实数编码与交叉：确定交叉位置，选择交叉部分，根据交叉概率确定是否交叉；对每一组个体的每一个位置进行变异判断是否需要旋转变异和位置变异；采用选择算法在末代遗传操作产生新的种群后，计算出种群的适应度，然后按适应度将种群中的个体进行排序，取适应度高的个体组成新的准群。该发明优化目标函数考虑单一，另外参数也是预先固定的，导致算法运行结果对参数设置依赖很大，优化效果对参数的设置依赖性高。
技术实现要素：
本发明是为了解决现有算法求解矩形件优化排样时对参数设置依赖大的问题，提供基于自适应遗传算法的矩形件优化排样方法。本发明采用自适应遗传算法对矩形件排样问题进行优化，采取启发式规则进行参数初始化，并且综合考虑了排样最大长度
为了实现上述目的，本发明采用以下技术方案：
基于自适应遗传算法的矩形件优化排样方法，包括步骤：
a)采集待排样矩形件，获取各个矩形件的尺寸和质量，对尺寸进行归一化处理；
b)采用十进制的方法对矩形件进行基因编码，每一个矩形件表示一个基因，各个基因构成一条染色体，每条染色体代表一组解，每条染色体上的基因数为矩形件的总个数，种群规模为n；
c)采取启发式规则进行参数初始化；
d)获取排样最大长度
e)对种群中的每组解进行评估，计算每组解的适应度函数值，根据适应度函数值对染色体进行排序；
f)设置算法停止条件，若满足停止条件，则结束算法，获得矩形件最佳排样方案；若不能满足停止条件，则进入步骤g)；
g)对种群进行选择，根据种群适应度值的统计分布设置交叉概率pc和变异概率pm，按照交叉概率pc对选择后的种群进行交叉操作，把种群中的两条染色体作为父代，染色体的部分基因进行交叉重组，形成新的染色体，获得交叉后的种群；
h)在交叉后的种群中，设定变异位置，对变异位置上的基因值作变动，按照变异概率pm进行个体基因变异，产生新一代的群体，返回步骤d)。
本发明采用自适应遗传算法对矩形件排样问题进行优化，采取启发式规则进行参数初始化，并且综合考虑了排样最大长度
进一步地，步骤a)中对尺寸进行归一化处理，包括步骤：
步骤a)中对尺寸进行归一化处理，包括步骤：
a1)设置矩形件个数为n，统计各个矩形件的长和宽，将各个矩形件的长记为{h1,h2,...hi,...,hn}，hi表示第i个矩形件的长；将各个矩形件的宽记为{ω1,ω2,...ωi,...,ωn}，ωi表示第i个矩形件的宽；
a2)对各个矩形件的长进行归一化，获得各个矩形件归一化后的长，记为
a3)对各个矩形件的宽进行归一化，获得各个矩形件归一化后的宽，记为
对尺寸进行归一化处理，能够加快优化求解过程中参数的收敛速度。
进一步地，步骤b)中采用十进制的方法对矩形件进行基因编码，包括：对待排样矩形件进行数字编号，数字编号顺序表示各个矩形件排样的先后顺序，数字编号前的负号表示将矩形件旋转90度。
遗传算法的编码方式有二进制编码、十进制编码、实数编码等，本发明采取十进制编码，即以排样小矩形的下标索引进行编码，假如要排样10个小矩形，则种群的一个样本可以是[-9,6,3,10,-5,4,7,1,-2,8]，样本中的数字顺序即代表排样先后顺序，负号表示旋转90度排放。
进一步地，步骤c)中采取启发式规则进行参数初始化，包括：
c1)设置每个矩形件的权重，第i个矩形件的权重
c2)根据权重从大到小的顺序对矩形件进行排序。
在初始化参数过程中，本发明并不按照传统的随机策略对种群进行初始化，而是采取启发式的规则对样本进行排序，优选地，α取0.9，
进一步地，步骤d)中构建迭代过程中的适应度函数
在计算个体适应函数值(即要优化的目标函数值)时，本发明除了考虑到排样最大长度
进一步地，步骤g)中根据种群适应度值的统计分布设置交叉概率pc和变异概率pm，统计分布包括种群适应度函数值的方差d和种群适应度函数值的均值
在选择、交叉、变异操作中，选择就是要选取哪些个体进行交叉和变异，而交叉和变异是遗传算法的核心，其中交叉概率pc的大小代表种群的全局搜素能力，变异概率pm的大小代表局部搜索能力，传统遗传算法采取恒定值，但这容易使算法陷入局部最优，所以本发明在算法前期要使pc大一些，pm小一些，后期则相反。本发明根据种群适应度值的分布情况对交叉概率pc和变异概率pm采取了自适应策略，优选地，偏置量δ取0.01。在交叉概率pc和变异概率pm的计算公式中，由于在算法前期种群适应度值的方差大(方差代表数据发散程度)，而适应度均值小，所以随着算法的收敛，交叉概率pc逐渐减小，变异概率pm则相反。
进一步地，步骤g)中对种群进行选择，包括步骤：
g1)计算每条染色体的适应度函数值；
g2)获得第g条染色体遗传到下一代的概率
g3)计算每条染色体的累积概率，第g条染色体的累积概率为
g4)生成n个随机数，随机数值的范围为[0,1]，获得各个随机数所属的累积概率区间；
g5)根据各个随机数所属的累积概率区间获得遗传到下一代的染色体，获得进行选择后的种群。
基于轮盘赌算法的思想对种群进行选择，累积概率区间可以为闭区间，也可以为半开区间。
进一步地，步骤g)中采取双点交叉按照交叉概率pc对选择的染色体进行交叉操作。
步骤h)中设定变异位置，包括：随机生成三个位置坐标，将前两个位置坐标对应的基因值进行交换，将第三个位置坐标对应的基因值进行数值取反。
在交叉操作中，本发明采取双点交叉，即随机生成两个位置坐标，把两个要交叉个体的位置坐标之间的部分交换即可；在变异操作中，本发明采取的策略是随机生成三个位置坐标，前两个坐标的数字进行交换，第三个坐标的数字取反即代表将矩形件旋转90度后排放。
步骤f)中，设置最大迭代次数，将算法停止条件设为是否达到最大迭代次数。
因此，本发明具有如下有益效果：本发明采用自适应遗传算法对矩形件排样问题进行优化，采取启发式规则进行参数初始化，并且综合考虑了排样最大长度
附图说明
图1是本发明实施例一的流程框图。
图2是本发明实施例一的矩形件排样示意图。
图3是本发明实施例一的采用自适应遗传算法进行矩形件排样后的示意图。
图4是本发明实施例一的采用传统遗传算法进行矩形件排样后的示意图。
图5是本发明实施例一的进行矩形件排样后对比曲线图。
1、本发明方法，2、传统遗传算法。
具体实施方式
下面结合附图与具体实施方式对本发明做进一步的描述。
实施例一，如图1、图2所示，图2中w表示样板的总长，h表示样本的总宽，hmax表示进行矩形件排样后的最大长度，s表示剩余面积。
基于自适应遗传算法的矩形件优化排样方法，包括步骤：
a)采集23个待排样矩形件，获取各个矩形件的尺寸和质量，对尺寸进行归一化处理，包括步骤：
a1)设置矩形件个数为n，统计各个矩形件的长和宽，将各个矩形件的长记为{h1,h2,...hi,...,hn}，hi表示第i个矩形件的长；将各个矩形件的宽记为{ω1,ω2,...ωi,...,ωn}，ωi表示第i个矩形件的宽；
a2)对各个矩形件的长进行归一化，获得各个矩形件归一化后的长，记为
a3)对各个矩形件的宽进行归一化，获得各个矩形件归一化后的宽，记为
b)采用十进制的方法对矩形件进行基因编码，包括：对待排样矩形件进行数字编号，数字编号顺序表示各个矩形件排样的先后顺序，数字编号前的负号表示将矩形件旋转90度。每一个矩形件表示一个基因，各个基因构成一条染色体，每条染色体代表一组解，每条染色体上的基因数为矩形件的总个数，种群规模为n。
c)采取启发式规则进行参数初始化，包括步骤：
c1)设置每个矩形件的权重，第i个矩形件的权重
c2)根据权重从大到小的顺序对矩形件进行排序。
d)获取排样最大长度
e)对种群中的每组解进行评估，计算每组解的适应度函数值，根据适应度函数值对染色体进行排序；
f)设置最大迭代次数，将算法停止条件设为是否达到最大迭代次数，若满足停止条件，则结束算法，获得矩形件最佳排样方案；若不能满足停止条件，则进入步骤g)。
g)对种群进行选择，包括步骤：
g1)计算每条染色体的适应度函数值；
g2)获得第g条染色体遗传到下一代的概率
g3)计算每条染色体的累积概率，第g条染色体的累积概率为
g4)生成n个随机数，随机数值的范围为[0,1]，获得各个随机数所属的累积概率区间；
g5)根据各个随机数所属的累积概率区间获得遗传到下一代的染色体，获得进行选择后的种群。
根据种群适应度值的统计分布设置交叉概率pc和变异概率pm，统计分布包括种群适应度函数值的方差d和种群适应度函数值的均值
采取双点交叉按照交叉概率pc对选择后的种群进行交叉操作，把种群中的两条染色体作为父代，染色体的部分基因进行交叉重组，形成新的染色体，获得交叉后的种群。
h)在交叉后的种群中，设定变异位置，包括：随机生成三个位置坐标，将前两个位置坐标对应的基因值进行交换，将第三个位置坐标对应的基因值进行数值取反。对变异位置上的基因值作变动，按照变异概率pm进行个体基因变异，产生新一代的群体，返回步骤d)。
如图3、图4所示，图3、图4分别为采用自适应遗传算法和传统遗传算法进行矩形件排样后的排样示意图。采用自适应遗传算法进行矩形件排样中，一共有6列，从左往右矩形件长度不相等的个数分别为2、3、3、3、3和3，采用普通遗传算法进行矩形件排样中，从左往右矩形件长度不相等的个数分别为3、5、4、3、2和3，可以看出采用自适应遗传算法进行矩形件排样更整齐，并且获得的剩余面积更大。采用自适应遗传算法和普通遗传算法关于各个参数的对比如表1所示。如图5所示，曲线1为本发明方法随着迭代次数的增加适应度函数值的变化曲线，曲线2为传统遗传算法随着迭代次数的增加适应度函数值的变化曲线，通过对比可以看出，采用自适应遗传算法获得的种群适应度函数值的均值
表1自适应遗传算法和普通遗传算法的参数对比
表1
本发明采用自适应遗传算法对矩形件排样问题进行优化，采取启发式规则进行参数初始化，并且综合考虑了排样最大长度
上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明保护范围以内。
1.基于自适应遗传算法的矩形件优化排样方法，其特征是，包括步骤：
a)采集待排样矩形件，获取各个矩形件的尺寸和质量，对尺寸进行归一化处理；
b)采用十进制的方法对矩形件进行基因编码，每一个矩形件表示一个基因，各个基因构成一条染色体，每条染色体代表一组解，每条染色体上的基因数为矩形件的总个数，种群规模为n；
c)采取启发式规则进行参数初始化；
d)获取排样最大长度
e)对种群中的每组解进行评估，计算每组解的适应度函数值，根据适应度函数值对染色体进行排序；
f)设置算法停止条件，若满足停止条件，则结束算法，获得矩形件最佳排样方案；若不能满足停止条件，则进入步骤g)；
g)对种群进行选择，根据种群适应度值的统计分布设置交叉概率pc和变异概率pm，按照交叉概率pc对选择后的种群进行交叉操作，把种群中的两条染色体作为父代，染色体的部分基因进行交叉重组，形成新的染色体，获得交叉后的种群；
h)在交叉后的种群中，设定变异位置，对变异位置上的基因值作变动，按照变异概率pm进行个体基因变异，产生新一代的群体，返回步骤d)。
2.根据权利要求1所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤a)中对尺寸进行归一化处理，包括步骤：
a1)设置矩形件个数为n，统计各个矩形件的长和宽，将各个矩形件的长记为{h1,h2,...hi,...,hn}，hi表示第i个矩形件的长；将各个矩形件的宽记为{ω1,ω2,...ωi,...,ωn}，ωi表示第i个矩形件的宽；
a2)对各个矩形件的长进行归一化，获得各个矩形件归一化后的长，记为
a3)对各个矩形件的宽进行归一化，获得各个矩形件归一化后的宽，记为
3.根据权利要求1或2所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤b)中采用十进制的方法对矩形件进行基因编码，包括：步骤b)中采用十进制的方法对矩形件进行基因编码，包括：对待排样矩形件进行数字编号，数字编号顺序表示各个矩形件排样的先后顺序，数字编号前的负号表示将矩形件旋转90度。
4.根据权利要求3所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤c)中采取启发式规则进行参数初始化，包括步骤：
c1)设置每个矩形件的权重，第i个矩形件的权重
c2)根据权重从大到小的顺序对矩形件进行排序。
5.根据权利要求1或4所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤d)中构建迭代过程中的适应度函数
6.根据权利要求5所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤g)中根据种群适应度值的统计分布设置交叉概率pc和变异概率pm，统计分布包括种群适应度函数值的方差d和种群适应度函数值的均值f，计算
7.根据权利要求1或6所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤g)中对种群进行选择，包括步骤：
g1)计算每条染色体的适应度函数值；
g2)获得第g条染色体遗传到下一代的概率
g3)计算每条染色体的累积概率，第g条染色体的累积概率为
g4)生成n个随机数，随机数值的范围为[0,1]，获得各个随机数所属的累积概率区间；
g5)根据各个随机数所属的累积概率区间获得遗传到下一代的染色体，获得进行选择后的种群。
8.根据权利要求7所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤g)中采取双点交叉按照交叉概率pc对选择后的种群进行交叉操作。
9.根据权利要求1或8所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤h)中设定变异位置，包括：随机生成三个位置坐标，将前两个位置坐标对应的基因值进行交换，将第三个位置坐标对应的基因值进行数值取反。
10.根据权利要求9所述的基于自适应遗传算法的矩形件优化排样方法，其特征是，步骤f)中，设置最大迭代次数，将算法停止条件设为是否达到最大迭代次数。
技术总结