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、如果生成的子染色体序列适应度更好,则父染色体序列会被子染色体序列替换,否则,父染色体序列被保留而子染色体序列被遗弃。