基于微粒群算法的图像阈值分割方法及其应用-硕士学位论文

基于微粒群算法的图像阈值分割方法及其应用-硕士学位论文内容摘要：

随机的，但蚂蚁可通过自组织过程形成高 度有序的群体行为。 由上述假设可见，基本蚁群算法的 寻优机制包含两个基本阶段：适应阶段和协作阶段。 在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大 ，则该路径越容易被选择，时间越长，信息量越小；在协作阶段，候选解之间通过信息交流 ，以期望产生性能更好的解。 蚂蚁觅食的过程与 旅行商问题 (TSP)之间有很大的相似性，以求解 TSP 为例 ，其 蚁群算法的数学模型 如下： 求解 n 个城市的 TSP 时 ， 设 蚁群中蚂蚁的数量为 m ； ()ibt表示 t 时刻位于城市i 的蚂蚁个数，则1 ()niim b t； ijd 表示两城市 i 和 j 间的距离； ij 表示路径 (, )ij 的能见度 ，反映由城市 i 转移到城市 j 的启发程度； ij 表示连接城市 i 和 j 路径上的信息 素 强度。 在初始时刻各条路径上的信息 素 量相等，即 (0)ij C  （ C 为常数）。 蚂蚁 k ( 1,2, ,km )在运动过程中，根据各条路径上的信息 素 量 决定转移方向。 用禁忌表 ktabu ( 1,2, ,km )来记录蚂蚁 k 当前所走过的城市。 在搜索过程中，蚂蚁根据路径上的信息素量及路径的启发信息来计算转移概率。 ()kijPt表示在 t 时刻蚂蚁 k 由 i 转移到 j 的转移概率： [ ( ) ] [ ( ) ] ,[ ( ) ] [ ( ) ]()0kaij ijkakis isijs ta b utt j t abuttPtot he rw i se     () 其中， 参数  和  分别反映蚂蚁 在运动过程中所积累的信息和启发信息在其选择路径中的相对重要性。 每只蚂蚁在完成对 n 个城市的遍历后，要对残余信息进行更新处理，以避免残余信息过多而淹没了启发信息。 由此， tn 时刻在路径 (, )ij 上的信息素量根据下式 进行 调整： ( ) (1 ) ( ) ( )ij ij ijt n t t         () 1( ) ( )ijm kij ktt   () 基于微粒群算法的 图像 阈值分割 方法 及 其 应用 8 其中 ，  是信息素挥发系数，则 1 表示信息素残余因子； ()ij t表示本次循环中路径 (, )ij 上的信息素增量； ()ijk t表示 本次循环中第 k 只蚂蚁留 在路径 (, )ij 上的信息素量。 在实际应用中，ij、ijk 、ijkP的表达形式可以不同， 要 根据 具体问题 、具体算法 来 加以 确定。 蚁群算法流程 以 TSP 为例，基本蚁群算法的实现流程 如下 ： ⑴ 初始化各参数。 令 时间 t =0， 迭代次数 N =0，设置最大迭代次数 maxN ，蚂蚁总数为 m ，元素（城市）个数为 n ，令连 接元素 i 和 j 路径上的信息量 ()ijt =C (C为常数 )，初始时刻 (0)ij =0； ⑵ 迭代次数 N =N +1； ⑶ 蚂蚁的禁忌表索引号 k =1； ⑷ 蚂蚁数目 k =k +1； ⑸ 根据状态转移概率公式 ()计算的概率选择下一个元素 j ， j ktabu ， 蚂蚁个体向元素 j 前进 ； ⑹ 修改禁忌表。 将元素 j 放到该蚂蚁个体的禁忌表中； ⑺ 若 km ，元素未遍历完，则转到第 ⑷ 步，否则继续执行第 ⑻ 步； ⑻ 按照公式 ()和 ()进行信息量更新； ⑼ 若 maxNN ，则迭代结束并输出计算结果，否则清空禁忌表 并转到第 ⑵ 步。 微粒群算法 微粒群算法 思想的起源 自然界中，鸟群中的每个个体是离散的，它们的排列看起来是随机的，但在整体的运动过程中却保持着惊人的同步性。 这些呈分布状态的群体所表现出的似乎是有意识的集中控制，这一特性引起了研究者们的注意。 有些研究者对鸟群的运动进行了计算机仿真，通过对个体设定简单的运动规则，来模拟鸟群整体的复硕士学位论文 9 杂行为。 1986 年， Craig Reynolds 提出了 Boid 模型 ，用以模拟鸟类聚集飞行的行为。 仿真的目的主要是研究如何对各种可能的运动进行描述和控制。 通过对 现实世界中这些群体运动的观察，在计算机中复制和重建这些运动轨迹，并对这些运动进行抽象建模，以发现新的运动模式。 Reynolds 在仿真中采用了下列三条简单的行为规则 [36]： ⑴ 飞离最近的个体，以避免碰撞 ⑵ 飞向目标 ⑶ 飞向 群体的中心 群体中的每个个体的行为都遵循以上的三条规则，通过这个模型来模拟整个群体的运动。 生物学家 Frank Heppner 在 Boid 模型的基础上增加了 一个仿真条件 —— 鸟类被吸引飞向栖息地 ， 提出了新的鸟群模型。 在仿真中，鸟群在刚飞起的时候并没有目的地，在空中自然地形成群体， 直到群体中的一只鸟飞向栖息地，当设置期望栖息比期望留在鸟群中具有较大的适应值时，每只鸟都离开群体飞向栖息地，随后就自然形成鸟群，整个群体飞向栖息地。 鸟类寻找栖息地与对一个特定问题寻找解很相似 ，已经找到栖息地的鸟引导它周围的鸟飞向栖息地的方式，增加了整个鸟群都找到栖息地的可能性。 美国社会心理学家 James Kennedy 和电气工程师 Russell Eberhart 受到这个模型的启发于1995 年共同提出了微粒群优化算法（ Particle Swarm Optimization, PSO）。 该算法将鸟群运 动模型中的栖息地类比于所求问题解空间中可能解的位置，通过个体间的信息传递，引导整个群体向可能解的方向移动，在求解过程中逐步增加发现较好解的 可能性。 群体中的鸟被抽象成为没有质量和体积的“微粒”，通过这些微粒间的相互协作和信息共享，使其运动速度受到自身和群体的历史运动状态的影响，以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响，较好地协调微粒本身和群体运动之间的关系，以利于群体在复杂的解空间中进行寻优操作。 微粒群算法基本原理 基于微粒群算法的 图像 阈值分割 方法 及 其 应用 10 PSO 算法 与其它进化类算法类似，也采用“群体”与“进化 ”的概念，同样也是依据个体（微粒）的适应值大小进行操作。 所不同的是， PSO 算法不像其它进化算法那样对于个体使用进化算子，而是将每个个体看作是在 n 维搜索空间中的一个没有重量和体积的微粒，并在搜索空间中以一定的速度飞行。 通过对环境的学习和适应 ，根据个体和群体的飞行经验的综合分析结果来动态调整 飞行速度。 在整个寻优过程中，每个微粒的适应值（ Fitness Value）取决于所选优化函数的值。 并且每个微粒都具有以下几类信息：微粒当前所处的位置；到目前为止 微粒所经历过的有最好适应值的 位置 pbest， pbest 视为 微粒自身的飞行经验 ；到目前为止整个群体所有微粒所经历过的最好位置 gbest（ gbest 是 pbest 中的最优值）。 PSO 算法是一种基于迭代模式的优化算法，最初被用于连续空间的优化。 在连续空间坐标系中，该算法的数学描述如下： 设微粒群体规模为 N。 微粒 i ( 1,2, ,iN )在 n 维空间中 当前 的坐标位置为 12( , , , )i i i inx x x x。 微粒 i ( 1,2, ,iN )当前的飞行速度为 12( , , , )i i i inv v v v。 微粒 i ( 1,2, ,iN )所经历的最好位置为 12( , , , )i i i inp p p p 根据以上的定义，微粒 i ( 1,2, ,iN )在第 j （ 1,2, ,jN ）维子空间中的飞行速度可描述为： 1 1 2 2( 1 ) ( ) ( ) ( ( ) ( ) ) ( ) ( ( ) ( ) )ij ij ij ij gj ijv t v t c ran d t p t x t c ran d t p t x t          () ( 1 ) ( ) ( 1 )ij ij ijx t x t v t    () 其中： t 表示第 t 代； 1c ， 2c 为加速常数，通常在 0~2 间取值； 1rand ~U(0,1)和2rand ~U(0,1)为两个相互独立的随机函数； gjp 为整个群体所有微粒所经历的最好位置。 为了减少在进化过程中，微粒离开搜索空间的可能性， ijv 通常限定在一定的范围内，即 max max[ , ]ijv v v。 如果问题的搜索空间限定在 max max[ , ]xx 内，则可设定 max maxv k x ， 。 微粒群算法流程 基本 PSO 算法的流程如下： 硕士学位论文 11 ⑴ 初始化所有微粒。 群体规模 N；在允许范围内随机设置微粒的初始位置和速度；每个微粒的 pbest 设为其初始位置 ， pbest 中的最 优 值设为 gbest。 ⑵ 计算每个微粒的适应值。 ⑶ 对每个微粒，将其适应值与其经历过的最 优 位置 pbest 进行比较，如果优于 pbest，则将其作为当前的最 优 位置 pbest。 ⑷ 对每个微粒，将其适应值与 群体 经历过的最 优 位置 gbest 进 行比较，如果优于 gbest，则将其作为 群体 的最 优 位置 gbest。 ⑸ 根据方程 ()和 ()对微粒的速度和位置进行进化。 ⑹ 检查终止条件 (达到预设最大迭代次数 maxG 或者满足足够好的适应值，或者最优解停滞不再变化 )。 若满足终止条件，则停止迭代 ，输出结果 ；否则返回步骤 ⑵。 基本微粒群算法的结构流程图如图 所示。 微粒群算法的发展 PSO 算法是一种原理简单的启发式算法。 它可以用于求解一些非线性 、 多峰基于微粒群算法的 图像 阈值分割 方法 及 其 应用 12 值的复杂的优化问题， 其 算法易于实现，需要 调整的参数也很少，因此受到了相关领域众多学者的关注。 作为一种新型的优化搜索算法，基本 PSO 算法不是很完善，在实际应用中，存在过早收敛以及全局收敛性差的缺点 [37][38]。 针对这些问题，研究者对该算法做了大量的改进研究，主要体现在： PSO 算法离散二进制模型[39][40]、 参数的选择与设计 [41][42][43]等。 PSO 算法离散二进制模型 PSO 算法最初是一种基于实值连续空间的优化技巧，然而许多工程应用问题是组合优化问题，因而需要将微粒群算法在二进制空间进行扩展。 二进制 PSO 算法也为 PSO 算法与遗传算法的性能比较提供了一个有用的方式。 在离散二进制模型中，个体进行二进制决策的概率是一个与个体和群体相关的函数， 文献 [10]对它的 定义如下： ( ( ) 1 ) ( ( 1 ) , ( 1 ) , , )ij ij ij ij gjP x t f x t v t p p    () 其中： ( ( ) 1)ijP x t  是个体 i 为位串上第 j 位选择 1 的概率（选择 0 的概率为 1 P）； ()ijxt是个体 i 的位串位置 j 的当前 状态； t 是当前时间步； ()ijvt代表个体做一个或另一个选择的倾向； ijp 是迄今为止发现的最好状态，例如，如果 ijx 为 1 时个体取得最大成功，那么 ijp 为 1；如果 ijx 为 0 时个体取得最大成功，那么 ijp 为 0； gjp 是邻域的最好状态，如果邻域的任一成员在处于 1 状态时取得最大成功，那么 gjp 为 1；否则为 0。 二进制 PSO 算法与基本 PSO 算法的主要区别在于位置更新方程不同。 离散二进制模型中速度和位置更新等式可表示为： 1 1 2 2( 1 ) ( ) ( ) ( ( ) ( ) ) ( ) ( ( ) ( ) )ij ij ij ij gj ijv t v t c ran d t p t x t c ran d t p t x t          () if( () ( )ijrand S v ) then ijx =1； () else ijx =0； 硕士学位论文 13 其中 ()ijSv为 Sigmoid 函数，定义为： 1()1 ex p ( )ij ijSv v ； ()rand 为 [0， 1]之间的随机数。 速度分量ijv决定了位置分量ijx取 1 或 0 的概率，ijv越大，则ijx取 1 的概率越大。 在离散二进制 PSO 算法中，保留了 maxv ，它可以限制 ijv ，以使 ()ijSv 不会太接近 或 ，从而限制 ijx 取 1 或。