欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2019101249300
申请人: 西安理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于改进遗传算法的快速最短枝切搜索方法,其特征在于,包括以下步骤:步骤1,残差点识别、数量匹配与残差点编码,具体做法是:

1)扫描整幅包裹相位图,识别出正、负残差点,并将正、幅残差点在包裹相位图中的行列号分别记录在两个矩阵中,记为正残差点行列号矩阵和负残差点行列号矩阵;

2)残差点编码时,最大编码为正、负残差点数量的最大值,依据公式(2),当正、负残差点的数量不一致时,残差点数量少的需要补充至两者相等;补充的残差点的行列号为(0,

0),行列号为(0,0)的残差点既可以作为正残差点,也可以作为负残差点,即相当于图像的四边界,N=max{No_positive,No_negative}              (2)式中,No_positive为正残差点的数量,No_negative为负残差点的数量,N为最大编码;

当一个普通残差点与一个行列号为(0,0)的特殊残差点匹配时,适应度函数采用公式(3),公式(3)表示残差点与四边界之间的最近距离,i i i i

fitness=min{x ,y ,(width‑x),(length‑y)}            (3)i i

式中,width为包裹相位图的宽,length为包裹相位图的长,(x ,y)为普通残差点的行列号;

步骤2,负残差点初始种群的生成

正残差点的染色体序列只有一个,且固定不变,

A、随机产生m种具有不同排序的负残差点的染色体序列;

B、采用最近邻算法产生n种有不同排序的负残差点的染色体序列,且为了实现种群多样性,所有产生的染色体序列与步骤A中的染色体序列互不相同;

C、共生成m+n种染色体序列的初始种群,为了实现后面的交叉算子,m+n应为偶数,即染色体交叉算子配对的数目为[(m+n)/2];

步骤3,选择算子

采用适者生存的自然选择法则,以适应度函数为评价标准,在当前的群体中,寻找适用度最佳的k(k<[(m+n)/2])种染色体序列来替换适应度最差的k种染色体序列,因此,优良的父染色体序列具有更大的概率将染色体传递给子染色体序列;

步骤4,交叉算子

以交叉概率Pc实施交叉算子,如果有(m+n)种染色体序列的初始种群,相邻的两个染色体序列形成交叉对,则交叉对的数目为[(m+n)/2];然后,将交叉对染色体序列的一串基因交换,并将重复的基因替换,生成两个新的子染色体,步骤5,变异算子

以变异概率Pm实施变异算子,其原理是在同一染色体序列上随机选择两个基因并互换它们,变异后将产生一个新的染色体来改善种群多样性,类似于交叉算子,如果新的子染色体更适合,则父染色体被子染色体取代;否则,父染色体被保留,子染色体丢失。

2.根据权利要求1所述的一种基于改进遗传算法的快速最短枝切搜索方法,其特征在于,步骤4所述的交叉算子,其操作步骤如下:a、在交叉对染色体序列上随机选取两个交叉点,交叉点分别记为crosspoint(1)和crosspoint(2);

b、交叉点crosspoint(1)和crosspoint(2)之间的基因串互换,crosspoint(1)=5,表示交叉点位置,不是基因编码数据,crosspoint(2)=8;染色体序列1的crosspoint(1)和crosspoint(2)之间的基因串为7‑,6‑,2‑,8‑,染色体序列2的crosspoint(1)和crosspoint(2)之间的基因串为3‑,5‑,4‑,6‑;交互之后,染色体序列1替换为5‑,4‑,1‑,9‑,3‑,5‑,4‑,

6‑,3‑,染色体序列2替换为7‑,8‑,2‑,1‑,7‑,6‑,2‑,8‑,9‑;

c、基因串交叉完成后,当基因编码存在重复时,参照现有遗传算法的交叉算子解决;

d、如果生成的子染色体序列适应度更好,则父染色体序列会被子染色体序列替换,否则,父染色体序列被保留而子染色体序列被遗弃。