(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110749458.7 (22)申请日 2021.07.01 (65)同一申请的已公布的文献号 申请公布号 CN 113420345 A (43)申请公布日 2021.09.21 (73)专利权人 浙江大学 地址 315400 浙江省宁波市余 姚市凤山 街 道冶山路479号科创大厦12 楼 (72)发明人 王进　肖金松　刘登辉　陆国栋　 张旭生　 (74)专利代理 机构 杭州浙科专利事务所(普通 合伙) 33213 专利代理师 孙孟辉 (51)Int.Cl. G06F 30/10(2020.01)G06F 30/27(2020.01) G06N 3/12(2006.01) (56)对比文件 CN 112232022 A,2021.01.15 审查员 罗畅 (54)发明名称 一种基于骨架导向的二维单元交互式遗传 离散布局方法 (57)摘要 本发明属于二 维单元布局优化领域， 公开了 一种基于骨架导向的二维单元交互式遗传离散 布局方法， 包括如下步骤： S1： 构建二维单元离散 布局问题的数学模型； S2： 设计以骨架为导向的 单元定位及遗传算法编码； S3： 基于直方图推土 机距离 （EMD） 设计遗传算法评价函数， 用于对解 码之后的种群中个体的表现型进行评价； S4： 引 入交互式评价调整方法对遗传算法进行改进； S5， 设计遗传算法进化过程。 本发明可以有效的 生成给定目标形状无轮廓边界约束、 无严格连接 约束的二维单元离散布局方案， 并且为用户提供 了多种启发性的思路， 可获得多样化的布局结 果。 本发明提出的算法可 以应用在拼图求解、 艺 术造型设计等领域。 权利要求书4页 说明书9页 附图5页 CN 113420345 B 2022.05.20 CN 113420345 B 1.一种基于骨架导向的二维单元交互式遗传离散布局方法， 其特征在于， 包括如下步 骤： S1： 构建二维单 元离散布局问题的数 学模型； S2： 设计以骨架为 导向的单 元定位及遗传算法编码； S21,在骨架提取之前先对目标形状进行DCE离散轮廓简化方法对轮廓进行简化， 假设 有两条线段s1和s2,其中v1， v2， v3表示曲线轮廓点， 若这三个点中， v2对形状识别贡献最小， 则删除v2， 连接剩下点v1和v3形成一条新线段s3＝{v1,v3}； S22， 使用热方程生成一个类似距离场的高度表面， 通过求解距离场高度表面脊线获取 输入的二维形状的骨架； S23， 将单元重心的位置限制在骨架线上， 将提取出的目标形状骨架点的坐标存放在列 表之中， 使用每个骨架点坐标在列表中的索引来选择对应的点坐标将单元的重心进行定 位， 对骨架线 上的点以5个点为间隔进 行采样存放在列 表之中， 单元旋转的角度以10的间隔 进行采样， 单 元布局的输出为O＝( (x1,y1, θ1),(x2,y2, θ2)...(xn,yn, θn))； S3： 基于直方图推土机距离(EMD)设计遗传算法评价函数， 用于对解码之后的种群中个 体的表现型进行评价； S4： 引入交 互式评价调整方法对遗传算法进行改进； S5： 设计遗传算法进化过程。 2.根据权利要求1所述的基于骨架导向的二维单元交互式遗传离散布局方法， 其特征 在于， 所述S1包括如下 具体步骤： S11， 将二维单元离散布局问题描述为形状和大小都固定的一组单元R1,R2,R3…Rn‑1,Rn, 对单元进行放置使得布局的结果Ω ′和目标形状Ω的相似度最高， 在满足布局结果和目标 形状相似的条件下， 生成多个可 行解； S12， 将目标函数定义 为单元的布局结果Ω ′和目标形状Ω的相似度D： D＝max(d(Ω,Ω ′))   (1) S13， 将约束条件定义 为单元Ri和Rj相互之间不允许重 叠相交， 允许边 缘重叠， 表示为： S14， 规定每个单元的姿态由单元的重心位置(x,y)和旋转角 度θ来确定， n个单元的布 局求解包含3n个变量， 即： ((x1,y1, θ1),(x2,y2, θ2)...(xn,yn, θn))， 加上约束条件的限制， 构 成最终解。 3.根据权利要求2所述的基于骨架导向的二维单元交互式遗传离散布局方法， 其特征 在于， 所述S3包括如下 具体步骤： 将推土机模型用于解决直方图匹配问题， 构建布局单元和目标形状的直方图； 首先依 据单元的总面积S1和目标形状的面积S2的大小将单元和目标形状整体缩放到同一尺度， 接 下来采用矩形栅格划分的方法对目标形状和布局结果进行栅格划分， 对形状落在栅格里面 的像素点的个数进行统计可以构建形状的像素分布直方图， 通过对直方图进行归一化操 作,可通过直方图求 解形状矩阵对目标 形状进行描述； 设目标形状和单元布局结果的直方图分布分别为U＝{u(i)： 1≤i≤N},V＝{v(j)： 1≤j权　利　要　求　书 1/4 页 2 CN 113420345 B 2≤N}， 两个分布值栅格总数相等设为N， u(i)和v(j)表示归一化之后直方图对应栅格的高 度， 从u(i)到v(j)的距离dij被定义为栅格之间的欧式距离， 用row和col表示栅格在直方图 中的横纵索引： dij定义为从u(i)到v(j)的运输量， 定义运输量集合为F＝{fij： 1≤i,j≤N}， 问题模型需 要求解所有的最优值 即最优集合F*得到总工作量W的最小值， 进而求出两个直方图分布 之间的推土 机距离， 将直方图推土 机模型描述 为如下的线型规划问题： 求解出F*获得工作量的最小值 W以后， 求得两个直方图之间的推土 机距离： 在对单元布局结果进行评价时， 设计一个重合度惩罚系数， 将未重合单元的面积比上 单元的总面积得到公式(6)的惩罚系数， 将目标形状和布局结果之间基于直方图推土机距 离的形状相似度评价和单元重合度惩罚系数进行综合考虑 对算法的适应度定义如公 式(7) 所示： U和V为目标形状和单元布局结果的像素点直方图分布， EMD(U,V)为两个直方图之间的 推土机距离， F与EMD(U,V)成反比例的关系， EMD(U,V)越小， 表示两个形状 之间距离越小， 相 似度越高， 对应种群的适应值 也越大， k是放大系数， 取正数。 4.根据权利要求3所述的基于骨架导向的二维单元交互式遗传离散布局方法， 其特征 在于， 所述S4包括如下 具体步骤： 根据S3提出的基于直方图推土机距离的形状相似度计算方法结合对单元重叠惩罚项 因子进行设计； 采用预先迭代若干代次的方法生成优化之后的种群； 得到优化的初始种群 之后， 每次选择最优的若干个种群个体展现给用户进行交互式调整和评价， 直到用户获得 满意结果之后停止算法； 评 分区间为0 ‑100分， 将当前评分C除以80 分得到一个倍乘系数， 如 公式(8)， 将调整之前的该个体的目标函数值乘以该系数作为调整之后该个体的目标函数 值； 当获得满意结果时， 对布局结果评价10 0分系统会保存该 结果；权　利　要　求　书 2/4 页 3 CN 113420345 B 3