(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210237176.3 (22)申请日 2022.03.10 (71)申请人 南京邮电大 学 地址 210003 江苏省南京市新模范马路6 6 号 (72)发明人 赖向京　龚玮　岳东　 (74)专利代理 机构 南京正联知识产权代理有限 公司 32243 专利代理师 张玉红 (51)Int.Cl. G06V 10/26(2022.01) G06V 10/762(2022.01) G06K 9/62(2022.01) G06N 3/12(2006.01) (54)发明名称 一种求解基因芯片图像分割的Memetic方法 (57)摘要 一种求解基因芯片图像分割的Memetic方 法， 该方法主要由四个部分组成， 它们分别是： 种 群初始化， 即随机生成 p个初始解并由此构成一 个初始种群； 用k ‑means算法作为局部优 化方法； 一个用来产生后代解的交叉算子； 一个基于种群 多样性的种群更新方法。 通过利用一种新的交叉 算子和基于多样性的种群更新策略， 本方法增强 了全局搜索能力， 克服了使用传统k ‑means算法 易陷入局部最优解的缺点， 这在很大程度上提高 了基因芯片图像 分割结果的准确度和效率， 有利 于处理大规模的基因芯片图像分割。 权利要求书2页 说明书6页 附图4页 CN 114596438 A 2022.06.07 CN 114596438 A 1.一种求 解基因芯片图像分割的Memetic方法， 其特 征在于： 所述方法包括如下步骤： 步骤1， 输入经过预处理和网格定位后的基因芯片图像 中的所有像素点的灰度值矢量， 随机生成p个初始解并由此构建一个初始种群P； 步骤2， 使用k ‑means算法对种群P中的每个个体进行局部优化， 然后记录下种群P中的 最好解， 记为Sb； 步骤3， 从种群P中随机 选择两个父代解， 使用交叉算子来产生 一个新的后代解S0； 步骤4， 使用k ‑means算法对S0进行局部 搜索； 步骤5， 利用基于多样 性的种群更新策略和S0更新种群P； 然后将S0与目前发现的最好解 Sb作比较， 判断是否更新Sb； 步骤6， 判断是否改进最好解， 若有改进， 则执行NoImprove ←0， NoImprove指连续未改 进的次数， 初始化为0， 然后跳转到步骤3； 若没有改进， 则使NoImprove增加1， 然后进入步骤 7； 步骤7， 判断NoImprove≤Lmax是否成立， Lmax指搜索深度， 若成立， 则跳转到步骤3； 若不 成立， 则流 程停止， 输出最优解即最优的图像分割结果。 2.根据权利要求1所述的一种求解基因芯片图像分割的Memetic方法， 其特征在于： 所 述步骤1中初始种群的构造方法如下： 步骤1.1： 从给定的数据集X＝{x1,x2,...,xn}(n指数据集X中 的节点总数)中随机选择K (K指类总数)个点作为初始中心， 记为yq(q＝1,2,...,K)， 然后将未分配的点依次分配给距 其欧氏距离最近的中心点所在的类Cq(q＝1,2,...,K)， 直到X里的所有点都已被分配， 将 此 解记为S1； 步骤1.2： 连续执行p次初始解生成程序， 得到p个初始解， 由此构成了一个初始种群P＝ (S1,S2,...,Sp)。 3.根据权利要求1所述的一种求解基因芯片图像分割的Memetic方法， 其特征在于： 所 述步骤2中用k ‑means算法对种群P中的每 个个体进行局部优化的步骤如下： 步骤2.1： 将解中的每 个类的中心更新 为该类所有点的重心点， 用公式表示 为： 其中， |Cq|表示第q个 类的节点个数； 步骤2.2： 如果中心不再变化， 则退出循环； 否则将数据集中的每个点分配给距其最近 的中心， 形成新的聚类， 然后跳转到步骤2.1； 步骤2.3： 根据目标函数值记录下目前该种群P中的最好解， 记为Sb； 目标函数值f(s)指 每个类中的每 个节点到各自中心点的欧氏距离的平方之和， 用公式表示 为： 其中， 指每个类中的每 个节点xi到各自所在类的中心点yq的欧氏距离的平方。 4.根据权利要求1所述的一种求解基因芯片图像分割的Memetic方法， 其特征在于： 所 述步骤3中使用交叉算子来产生 一个新的后代解S0的主要步骤如下：权　利　要　求　书 1/2 页 2 CN 114596438 A 2步骤3.1： 从种群P中随机 选取两个解作为父代解并记为P1和P2。 定义 和 分别为P1和P2的各类， 和 分别为P1和P2的类 的中心点； 步骤3.2： 对两个解P1和P2的中心点 和 进行匹配； 使用贪心匹配准则对两个解的类 中心点集合进行两两匹配； 该贪心匹配方法有K个迭代步， 在每一步， 若两个类中心点之间 的欧氏距离最小， 则它 们相互配对， 直到所有的类都已配对； 步骤3.3： 对两个父代解P1和P2进行杂交生成一个后代解S0； 首先， 对配对好的K组类分 别取它们之间的交集 得到一个新的K个类 接着， 运用公式(1)计算 每个类 的中心点 然后， 将配对时取交集后剩下的点分配给距其欧氏距离 最近的中心 点所在的类里， 直到剩下的所有点 都已分配完； 最后， 杂交生成了一个新的后代 解S0。 5.根据权利要求1所述的一种求解基因芯片图像分割的Memetic方法， 其特征在于： 所 述步骤5中， 定义了一个解Si(i＝1,2,...,p)对于种群P的打 分函数： 其中， α是一个参数， f(Si)是Si(i＝1,2,...,p)的目标函数值， D(Si,P)表示Si(i＝1, 2,...,p)与种群P之间的距离， 定义 为Si与种群P中其 他解之间的最小距离， 用公式表示 为： D(Si,P)＝min{dij|Sj∈P,j≠i,j＝1,2,. ..,p}    (4) 其中， dij表示Si与Sj之间的距离， 定义为Si与Sj中相对应的类中心之间的欧氏距离之 和， 用公式表示 为： 其中， 和 分别指Si和Sj对应的Cq的中心。 打分函数Score(Si,P)越小， 说明Si质量越好； 种群更新规则为， 首先将后代解S0插入种群P 中， 即P'＝P∪{S0}； 然后计算种群P'中的 每个Si的分数Sc ore(Si,P)， 并记录下质量最差即打分函数值最 大的解， 记为Sworst； 然后用S0 替换掉种群P'中质量 最差的解Sworst， 即P＝P∪{S0}\{Sworst}。 最后， 将后代解S0与目前发现的最 好解Sb作比较， 若f(S0)＜f(Sb)， 则用S0来更新Sb。权　利　要　求　书 2/2 页 3 CN 114596438 A 3