关键词： 算法
克隆算法（精选十篇）
克隆算法 篇1
关键词：克隆选择,基因重组,高频变异,函数优化
0 引言
生物免疫系统是生物体内结构最为复杂、功能最为独特的系统之一。研究生物免疫学机理, 成为当代生命科学中的前沿学科[1]。人工免疫系统AIS (Artificial Immune System) 是模仿生物免疫系统功能的一种新的智能方法, 是继模糊逻辑、进化计算和神经网络后, 人工智能领域又一研究热点[2,3,4]。Castro等根据免疫克隆选择机理, 提出了一种克隆选择算法[5], 并成功用于模式识别和函数优化[6]。随着人工免疫系统的迅速发展, 一些基于克隆选择机理的新算法相继提出, 李恒杰等提出了一种基于单一高斯算子变异的克隆选择算法[7], 加快解的收敛性, 同时保持解的多样性和分布的均匀性。胡江强等人提出了一种分级变异的动态克隆选择算法[8], 根据抗体亲和度将种群分解为3个子种群, 实施不同的变异策略, 加快全局搜索速度, 提高局部搜索精度。焦李成、杨咚咚、公茂果等人提出了一种基于偏好等级的免疫记忆克隆选择优化算法[9], 利用决策者提供的偏好信息来为抗体分配偏好等级, 增大抗体选择压力, 加快收敛速度。陶新明等人提出了一种混合变异克隆选择算法 (HMC-SA) [10], 在抗体进化过程中, 不同抗体种群采用不同的变异算子, 并通过外部记忆抗体群的更新, 保留进化的最优抗体, 避免算法进化后期出现的退化现象。
克隆选择算法CSA (Clonal Selection Algorithm) 是模拟生物免疫系统抵御外来抗原侵袭的一种自主学习进化过程。与遗传算法的有性繁殖 (父代基因交叉变异) 不同, 免疫克隆选择算法是通过无性繁殖 (自身克隆变异) 连续传代生成抗体种群, 并利用高频变异提高抗体克隆种群的亲和力, 从而实现抗体种群的不断进化, 最终找到最优抗体[11]。与传统克隆选择算法相比, 虽然改进的克隆选择算法克服了局部搜索能力低和进化缓慢的不足, 但是高频变异的随机性和不确定性可能会导致出现退化现象, 影响算法的收敛速度和降低全局搜索的能力。本文根据克隆选择机理, 利用生物工程中的基因重组技术, 提出一种基于基因重组的克隆选择算法 (GRCSA) 。根据抗体与抗原之间亲和力的大小, 获取优秀抗体的优秀基因片段, 并对亲和力低的抗体进行基因的交换与重新组合, 实现定向变异的目的, 防止种群退化, 提高变异效率。另外, 根据不同抗体浓度进行不同规模的克隆增殖, 保持抗体种群的多样性, 扩大全局的搜索范围, 防止陷入局部收敛。最后利用测试函数对算法性能进行评估, 并与文献[10]的算法进行比较, 实验结果验证了本文提出的算法提高了其收敛速度和解的精度, 证明算法的有效性。
1 基因重组的形式化描述
在生物工程领域, 基因是包含遗传信息的DNA分子片段, 基因重组技术就是对生物体的DNA分子进行交换和重新组合, 形成新的DNA分子, 改变生物体某些外在性状[12]。基因重组的优点是在生物体的DNA分子发生变异的过程中, 有方向性地改变生物体的基因组成, 避免生物体基因 (DNA分子) 出现有害变异, 导致退化现象。在克隆选择算法中, 基因重组包含两个过程:第一, 提取优秀抗体的优秀基因片段;第二, 利用优秀基因片段, 通过某些技术手段, 对抗体的某些DNA分子片段进行交换和重新组合, 形成新的抗体DNA分子, 从而达到改变抗体基因的目的。将基因重组做如下形式化描述:
定义1将基因重组形式化描述成一个三元组GR=。其中, Ab={Ab1, Ab2, …, Abp}表示p个优秀的抗体组成的抗体种群, 每一个抗体Abi (i∈[1, p]) 是由l位二进制串组成的抗体DNA分子表示;Abs表示从优秀抗体Ab种群中提取的优秀基因 (DNA分子) 片段;R (·) 表示一种操作算子, 将优秀基因片段经过交换和重新组合注入到其他抗体的DNA分子中, 达到控制抗体变异方向的目的。
1.1 抗体优秀基因片段
在生物免疫学中, 虽然抗体表面有多个表位, 但在诱导免疫应答时只可能是一种或者一个表位其主要作用, 使宿主产生特异性为主的免疫应答, 这种现象叫作免疫显性或免疫优势, 关键作用的表位叫作显性免疫优势点[13,14]。在抗体DNA分子中, 显性免疫优势点是由某段基因片段表达的, 称为优秀基因片段。基因重组的基础就是获取优秀基因片段。
在人工免疫系统中, 抗原、抗体以及抗原/抗体的亲和力分别对应函数优化问题的目标函数、优化解以及解与目标函数的匹配程度。人工免疫系统借鉴生物免疫学的有关机理, 通过抗体自身的不断进化以适应抗原的刺激, 达到解决目标函数最优值的目的。为了简化问题, 将被优化的目标函数记为f:F→F', 亲和力函数aff一般为目标函数f。对于抗体编码, 每个抗体Ab∈Bl、Bl={0, 1}l代表由长度为l的二进制串组成, 这个二进制串表示抗体的DNA分子, 抗体种群Ab={Ab1, Ab2, …, Abn}为抗体Ab的n元组。
定义2假设每一个抗体是由一个长度为l的二进制串组成, 记为Ab=[ab1, abn, …, abn], 如果它满足:f (Ab) =f (ab1, …, abi-1, 1, abi+1, …, abl) ≥f (ab1, …, abi-1, 0, abi+1, …, abl) 或者f (Ab) =f (ab1, …, abi-1, 1, abi+1, …, abl) ≤f (ab1, …, abi-1, 0, abi+1, …, abl) , 则称抗体的第i位为优秀基因片段, 其性状表达为显性免疫优势点。
1.2 抗体优秀基因片段的获得
利用获取的优秀基因片段, 改造与抗原亲和力低的抗体的基因, 使之表现出显性免疫优势点的外在性状, 促使每次变异都趋向于好的方向, 从而达到定向变异的目的, 提高变异效率和算法收敛速度。
优秀基因片段的获得算子:
1) 定义规模为n的初始抗体种群Ab={Ab1, Ab2, …, Abn}, 每个抗体的DNA分子由l位二进制串表示。抗体种群可记为:
2) 计算种群中每个抗体的亲和力, 根据亲和力大小, 选取亲和力大的优秀抗体。定义一个参照抗体Abs, 用来记录显性免疫优势点, 从而提取优秀基因片段。
3) 利用参照抗体Abs, 对亲和力低的抗体的DNA分子进行交换与重新组合, 改变其DNA分子, 使其获得优秀基因片段, 表现出显性免疫优势点的外在性状, 实现高频变异中的定向变异。
2 基于基因重组的克隆选择算法
本文在传统克隆选择算法的基础上, 借鉴基因重组技术, 提出了一种基于基因重组的克隆选择算法, 对传统克隆选择算法中的高频变异进行定向控制, 使每一次变异都趋向于好的方向, 产生更优秀的抗体, 避免出现退化现象, 提高算法的收敛速度。假设一个规模为n的抗体种群Ab={Ab1, Ab2, …, Abn}, 每一个抗体的DNA分子由l位二进制串组成, 即Abi=[ab1, ab2, …, abl], i∈[1, n]。对基于基因重组的克隆选择算法作如下形式化描述:
克隆选择规则Rscs对初始抗体种群进行亲和力计算, 然后根据亲和力大小, 选择亲和力高的抗体进行克隆增殖。具体规则如下:
Rscs规则具体包括计算抗原和抗体亲和力的值和根据亲和力大小对初始抗体种群进行排序两个过程:
(1) 计算抗原与抗体之间的亲和力的值, 得到一个抗体亲和力的集合Aff={aff1, aff2, …, affn}。如今最常用的计算亲和力的方法有:Euclidean距离 (式 (2) ) 、Manhattan距离 (式 (3) ) 以及Hamming距离 (式 (4) ) :
(2) 根据亲和力大小对亲和力集合的个体进行排序, 得到新的抗体种群序列rank (Aff) ={Ab'1, Ab'2, …, Ab'n}。另外, 定义一个克隆选择概率P, 由如下公式求得:
其中, pi是第i个抗体的选择概率, affi是第i个抗体与抗原的亲和力, i∈[1, n]。根据克隆选择规则Rscs, 选择出ε×n优秀抗体, 即种群{Ab'1, Ab'2, …, Ab'ε×n}进入克隆增殖过程, 对应的选择概率为{p1, p2, …, pε×n}。ε是克隆选择参数, 决定克隆选择的数目。
克隆增殖规则Rpcs对克隆选择出的优秀抗体种群Rscs (Ab) , 根据抗体/抗原亲和力的大小, 进行不同规模的克隆增殖, 具体规则如下:
其中, Ab'i=×jAb'i, (i∈[1, ε×n], j∈[p1, pε×n]) , 是克隆增殖参数, 决定不同的克隆增殖规模。根据克隆选择概率, 对概率大且浓度低的抗体进行优先克隆, 且克隆的规模与选择概率成正比, 即选择概率越大, 克隆规模越大。
克隆变异规则Rhcs运用基因重组技术, 借助从优秀抗体的DNA分子中获取的优秀基因片段, 对亲和力低的抗体的DNA分子进行交换和重新组合, 使之表现出高亲和力的性状, 达到定向变异、提高变异效率的目的。具体规则如下:
其中克隆变异概率与克隆选择概率成反比, 即选择概率越小, 变异概率越大。Rhcs规则具体包括获取优秀抗体的优秀基因片段和定向改造抗体DNA分子两个过程:
(1) 获取优秀抗体的优秀基因片段。根据抗体/抗原亲和力大小, 选取η个优秀抗体。定义一个参照抗体Abs, 用来记录优秀基因片段, 获取方法如下:
(2) 定向改造抗体DNA分子。利用参照抗体Abs, 对亲和力低的抗体进行DNA分子的重组, 将获取的优秀基因片段注入其DNA分子内, 定向改造亲和力的性状, 从而达到定向变异的目的。具体方法如下:
其中, Abm表示亲和力较低的抗体, Ab'm表示经过基因重组改造以后的抗体, remove () 是根据参照抗体Abs对抗体Abm的DNA分子进行交换和重组操作算子。
免疫记忆规则Rmcs从优秀抗体种群中选取一定数量的优秀抗体进入记忆细胞集合, 成为记忆细胞, 用于引发二次免疫应答。具体规则如下:
其中λ是免疫记忆参数, 决定生成记忆细胞的个数。
基于基因重组的克隆选择算法的算法流程如下:
Step1随机生成规模大小为n的初始抗体种群Ab={Ab1, Ab2, …, Abn};
Step2 For每一代种群do
{
Step2.1对随机生成的初始抗体种群Ab, 按照克隆选择规则, 进行Rscs (Ab) 操作, 构成规模大小为k的子种群Abk;/*计算抗体/抗原的亲和力, 按照亲和力大小对抗体种群进行排序, 选取亲和力较大的抗体形成子种群*/
Step2.2对子种群Abk, 参照克隆扩增规则, 进行Rpcs (Abk) 操作;/*对选择出来的抗体根据亲和力大小进行克隆增殖, 亲和力越大增殖的规模越大*/
Step2.3对于余下种群Abn-k, 参考克隆变异规则, 进行Rhcs (Abn-k) 操作, 对低亲和力的抗体进行定向变异, 改变其亲和力;/*获取优秀抗体的优势基因片段, 借助基因重组技术对亲和力低的抗体进行有效的改造, 完成变异过程*/
Step2.4参照免疫记忆规则, 进行Rmcs (Abn-k) , 生成记忆细胞;/*选取最优抗体成为记忆细胞, 用于引发二次免疫应答*/
Step2.5将原种群中亲和力低的 (l+r) 个抗体用l个优秀抗体和r个随机生成抗原细胞进行代替进入下一代新的抗体种群;/*引入部分随机生成的抗体, 避免陷入局部最优解*/
}
Step3直到满足算法结束条件
Step4从抗体种群中选择亲和力最大的抗体作为最优抗体
3 仿真实验与结论
为了评估基于基因重组克隆选择算法的在收敛速度与搜索范围的性能, 实验选取如式 (11) 、式 (12) 作为测试函数, 并与基于混合变异的克隆选择算法进行比较:
基于混合变异的克隆选择算法采用文献[9]的代码, 种群规模为100, 每个变量 (抗体) 的二进制编码 (抗体DNA分子) 长度为20位, 测试函数与亲和力函数的映射关系如式 (13) , 亲和力值越大, 说明抗体越好, 越接近函数的最优值 (测试函数的极小值) 。终止条件是达到给定的最大进化代数 (本文的进化代数是200) 或者是解在连续30次迭代中不再变化, 认为算法基本收敛, 算法结束。
其中, f (Ab) 为抗体Ab对应的可行解的目标函数值, β是调节因子。
利用基于基因重组的克隆选择算法 (GRCSA) 和基于混合变异的克隆选择算法 (HMCSA) 分别对对目标函数f1和目标函数f2进行性能评估, 实验数据如下表所示。
从表中可以看出, 在算法进化过程中, 通过GRCSA算法得到的测试函数的极小值和种群均值都要小于由HMCSA算法得到的。另外, 对于测试函数f2, 由于是函数本身就是多峰函数, 具有多个函数极小值, 通过GRCSA算法得到函数的极小值小于HMCSA算法得到的, 说明GRCSA算法扩大了问题解的搜索范围, 提高了目标函数最优解 (极小值) 的精度。
图1和图2分别是目标函数f1和f2的进化曲线, 横坐标轴为进化代数, 纵坐标轴为测试函数的极小值。从图中可以看出, GRCSA算法的收敛迭代次数要明显低于HMCSA算法的, 并且每次迭代GRCSA算法取到的测试函数的极小值均小于HMCSA算法的, 说明GRCSA算法在种群进化速度上优于HMCSA算法。基于基因重组的克隆选择算法是借助基因重组技术, 在抗体高频变异阶段, 对亲和力低的抗体进行定向变异, 提高了抗体变异效率和算法收敛速度。因此, 在进化初期, GRCSA算法的收敛速度明显快于HMCSA算法的。另外, 基于基因重组的克隆选择算法根据相同亲和力的不同的抗体浓度, 对抗体进行不同规模的克隆增殖, 增加了优秀抗体的种类及多样性, 避免在收敛速度加快的同时, 陷入局部收敛, 造成局部最优的情况。在进化后期, 虽然两种算法都达到了一种基本收敛, 但是从测试函数的极小值上看, GRCSA算法得到函数极小值是小于HMCSA算法的, 从而证明基于基因重组的克隆选择算法在收敛速度和搜索范围的有效性。
4 结语
假如我会克隆，我要克隆作文 篇2
于是，他想着，他如果能克隆，就一定要克隆出他的母亲，一个上班，一个陪伴在他身边。虽然他没因失去母爱而颓废，却为失去母爱而伤悲;虽然他没因失去母爱而自暴自弃，却为失去母爱而忧伤。他虽然不是折翼的天使，却是独脚的稚鹰，要停得稳就只能比别人更辛苦、更努力。
没有什么爱比母爱更重要，没有了母爱，就像幼苗没了春雨的抚摸，所以，他想着，他如果能克隆，就一定要克隆出他的母亲。这就是母爱的力量，给你信心，给你力量，让你留恋。
克隆算法 篇3
关键词： 蚁群算法； 信息素策略； 能见度
中图分类号： TP 391.4文献标志码： Adoi： 10.3969/j.issn.10055630.2015.03.016
Abstract： The highthroughput monoclonal colony selection instrument is a highend equipment applied to biological cell engineering which contains the technologies of optical imaging， image recognition and automatic control. For the 12×8 probe array and the targets in random order， only the optimization of selected path and order can improve the throughput. Thus， this paper presents the principle of the basic ant colony algorithm and optimizes the selection path based on the algorithm. Then results of the experiment prove the method can greatly improve the selection efficiency.
Keywords： ant colony algorithm； pheromone update strategy； visiability
引言单克隆菌落挑选仪是集光学成像、图像识别和自动控制等技术于一身，应用于生物工程领域的一种高端仪器，在我国处于起步研制阶段。在经过诱变和培养的数以万计的菌株中，仅有百分之几是符合要求的高性能菌株。传统的挑选菌株方式是通过目视菌落形态颜色等特征，人工方式取出优质菌株，该方法不仅重复性差，而且效率极低。为了提高挑选效率和可靠性，美国、德国、瑞士等国相继开发出基于光学成像和图像识别技术的单克隆菌落挑选仪。其工作原理是对菌落图像进行分析，通过分析菌落形态、大小、圆度、长短径比和颜色等特征，进而标记出高性能菌落[12]，并利用机械手带动探针实现菌落的挑取和转移。单克隆菌落挑选仪的一个重要考核指标是单位时间内能完成的操作数量（即通量），通量与机械手行走的路径直接相关。因此为了实现高通量，需要找到最科学合理的挑选路径，这也是仪器研发面临的重要问题之一。图1菌落挑选仪探针阵列
Fig.1Probe array on selection instrument菌落挑选仪探针阵列如图1所示，机械手末端为12×8的探针阵列，菌落目标则随机分布在圆形培养皿区域内。随机械手移动到相应位置，探针逐一伸出，每根探针挑取一个目标后，一次性放入标准96孔深孔板。在设计初期，每次挑选匹配间隔距离最小的探针和菌落目标，以期通过减小单次运动量缩短总路径长度，该方法称为最近点法。最近点法是一种贪心算法，单次运动量对路径优化具有启发性，但不是决定性的。针对这一典型的组合优化问题，本文使用蚁群算法进行优化。
1蚁群算法及其在路径优化中的实现
1.1蚁群算法蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法[3]，觅食过程中，虽然每只蚂蚁的智能和认知水平有限，但是通过个体与个体之间基于生物化学物质的通信，相互影响，最终能适应苛刻的环境，解决复杂的问题，这是一种群体智能。图2为反映群体智能的双桥实验。
如图2（a）所示蚁穴A与食物D之间存在障碍，起初蚁穴中的蚂蚁随机地寻找能绕过障碍搬运食物的路径，同时在这些路径上留下能被同伴嗅觉捕捉的信息素。不同的路径长度不一，如图（b）中的ABD、ACD，蚂蚁往返在较短的路径上将留下更多的信息素，随着信息素的浓度的差异，大多数的蚂蚁将选择较短的路径如图（c）所示。蚁群算法即仿照蚂蚁群的这种行为特征，利用一组数据作为算子间通信的生物信息素，启发算法进行寻优搜索，可以解决复杂的组合优化问题。假设有n个目标地点，开始有m只蚂蚁随机地分布在n个地点上，记t时刻i到j的路径lij上的信息素强度为τij（t），在t+1时刻，m只蚂蚁各自向下一目标移动，为了防止蚂蚁反复经过同一目标，需设置禁忌表tabu，记录已经去过的目标，随移动进程变动。蚂蚁k在t时间内选择i到j的路径lij的概率可以根据路径上的信息素计算出[4]Pkij（t）=[τij（t）]α·[ηij（t）]β∑sallowedk[τis（t）]α·[ηis（t）]βjallowedk
0else（1）式中：allowedk表示蚂蚁k下一步允许选择的目标，即全部目标集合C减去k的禁忌表集合；α为信息启发因子，表征信息素在路径选择时的作用；β为期望启发因子，表征距离启发因素（能见度）在路径选择时的作用；ηij为启发函数，是路径长度dij的倒数。每次蚂蚁完成了一条路径，就会更新各处的信息素。遍历过n个城市后在路径lij上的信息素为τij（t+n）=ρτij（t）+Δτij（2）
Δτij =∑mk=1Δτkij（3）式中，ρ为挥发系数，Δτij为在该次移动中由其他蚂蚁留下的信息素，Δτkij为蚂蚁k在路径lij上留下的信息素。根据基本的信息素策略[3]，信息素表达式为Δτkij=QLk第k只蚂蚁经过路径lij
nlc202309011923
0第k只蚂蚁并未经过路径lij（4）式中，Q为为信息素强度，Lk为蚂蚁走过的长度。
1.2蚁群算法在挑选仪单克隆菌落挑选仪优化中的实现蚁群算法可用在求解旅行商问题，旅行商问题（travelling salesman problem，TSP）即为一名旅行商需要去拜访若干城市，寻找只拜访各城市一次后返回出发点的最短路线的问题。其数学模型描述[5]为C={c1，c2，…，cn}为城市，L={lijci，cjC} 是集合C中元素两两之间的路径集合，dij为lij长度。G=（C，L）是一个有向图，求解旅行商问题是从G中找到长度最短的Hamilton圈。区别于传统旅行商问题，在对挑选仪进行优化时，需要做以下处理：（1）在对挑选仪路径优化时，相对目标移动的不是一个点，而是矩形探针阵列（以下称运动针盘），算法中的每次移动取决于运动针盘上要使用的探针p以及目标菌落t，组合集合C={（p，t）p∈P，t∈T}（P，T分别为96枚探针的集合和96处菌落目标的集合），由于探针和菌落均不重复使用，故约束任意两个C的元素ck=（pi，ti）和cl=（pj，tj），有pi≠pj且ti≠tj。（2）运动针盘安装在正交的二维导轨组成的机械手上，由伺服电机驱动，以脉冲信号控制。在常加速度模式下，伺服电机接收到指定脉冲信号开始以a=0.3 g起步加速，加速至预先设定的工作速率vm，脉冲停止时开始减速刹车[6]。在统计行程时依据机械手运动的两个特点①两条导轨分别由各自电机驱动，定位时间由两条导轨中行程长的一维决定；②电机的行程和时间对应关系可视为为线性关系t=vma+svm。（3）蚁群算法工作建立在个体通信的基础上，对于大规模TSP问题，使用蚁群算法会产生极其庞大的运算开销，本文研究的探针与目标组合数达到了962，完整的信息素记录可能多达几千万组，因此平衡通信开销和搜索空间的充分性是改进蚁群算法的必要工作。算法工作者为改进蚁群算法提出了多种信息素更新策略[7]。在解决本问题时，引入能见度阈值的概念，运动针盘可选路径很多时（如在最开始的几步），决定运动方向前先根据各目标位置进行初步过滤，忽略运动跨度较大的路径上的信息素，这种跨越必然是不合理的。一种阈值设置方法Qd=w（dmin+dmax），其中系数w∈（0，1），dmin、dmax分别为未使用的各探针与各目标的距离的最小、最大值。此外，在算法程序中设置信息素字典动态记录路径被采用的概率，信息素持续挥发值小于一定值时，将此记录删除以节省存储空间。
2模拟仿真实验
2.1实验设计本文根据蚁群算法编写了优化程序，并设计了仿真实验测试优化效果。在直径9 cm的区域内随机生成96个点作为菌落目标，探针排列为12列8行，相邻间隔9 mm，在菌落区域移动仿真图见图3。根据菌落挑选仪在图像捕获时刻的位置关系，将两者初始相对位置设定为常数。目标排列的形状与探针形状相符的程度决定着最优解的大小，极端情况下，目标排列与探针阵列完全相同，则整个挑选过程只需一次移动。为了减少“巧合”造成的影响，实验通过对多组目标优化，分析最优解的收敛情况。
2.2实验结果实验参数[89]中α=2.5、β=4.5、ρ=0.5、Q=400、m=20。绘制出平均路径长度收敛曲线如图4，由图中可见，算法在1次迭代将最优解值收敛到415 mm，在5次内开始优于最近点法，随迭代次数增加，收敛逐渐趋于平缓。图5反映了不同样本分别用最近点法和蚁群算法优化最终结果的差异。经过蚁群算法优化，路径总长度相比最近点法得到进一步缩短，而且没有因样本差异产生显著波动。
3结论本文针对单克隆挑选仪研发中遇到的挑选路径优化问题，结合机械手运动特点，将探针与目标组合，构成抽象城市的概念，根据蚁群算法，对最优挑选步骤进行了启发式优化，并采取适当的信息素策略控制运算规模。模拟实验结果表明，蚁群算法的应用有效地减少了菌落挑选探针的移动距离，从而提高了仪器通量。参考文献：
[1]周莹莉，曾立波，刘均堂，等.基于图像处理的菌落自动计数方法及其实现[J].数据采集与处理，2003，18（4）：460464.
[2]陈东科.加强形态学检查提高细菌鉴定的准确性[J].实验与检测医学，2012，30（5）：419422.
[3]ERIC B，MARCO D，GUY T.Swarm intelligence：from natural to artificial systems[M].Oxford：Oxford University Press，1999.
[4]李士勇，陈永强，李研.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.
[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.
[6]黄兆斌，黄云龙，余世明.几种步进电机加减速方法的对比研究及其应用[J].机电工程，2011，28（8）：951974.
[7]岑宇森，熊芳敏，曾碧卿.基于新型信息素更新策略的蚁群算法[J].计算机应用研究，2010，27（6）：20802083.
[8]詹士昌，徐婕，吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报，2003，19（5）：381386.
[9]吴春明，陈治，姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报，2006，（8）：15301533.
（编辑：张磊）
克隆算法 篇4
关键词：克隆选择算法,脉冲耦合神经网络,图像分割
1 引言
近年来,被国际上称为第三代人工神经网络的脉冲耦合神经网络(PCNN)以其更接近生物机制的优越性,被广泛地应用在图像处理、决策优化和通信等方面。PCNN数学模型中各种门限系数、时间衰减常数、链接系数等参数,控制着网络运行效率,对它们的恰当设置是一个不容忽视的环节。目前,P C N N模型参数的选择基本还是靠经验设定,需要针对每一幅图像反复实验才能获得合适的数值,导致人机交互的工作量很大,无法实现自动化,并且对处理结果的判定也会因人的主观评价不同而产生较大的差异[1]。因此如何合理计算参数是P C N N理论研究亟待解决的一个难题。
克隆选择算法(Clone Selection Algorithm,以下简称CSA)是由De.Castro和Von.Zuben在2000年提出的一种算法,其灵感来自生物获得免疫的克隆选择原理[2]。克隆选择算法所具有的多样性,高变异率和依据适应度成熟等特点使其既能在全空间搜索又有着较快的收敛速度。在一定程度上解决了进化算法通常面临的早熟收敛问题,是一种新型而优秀的优化算法。本文通过将克隆选择算法和P C N N结合,利用克隆选择算法的解空间搜索能力,来自动寻找P C N N关键参数的最优值,从而自动完成关键参数的自动设置。由此提出了一种基于克隆选择算法的P C N N参数自动设定方法,并通过其在图像分割中的应用,验证了其正确性与可行性。
2 PCNN模型
PCNN模型是由若干神经元组成的单层二维局部链接的反馈型网络,每个神经元由三部分组成:接受部分、调制部分和脉冲产生部分。图1为单个PCNN神经元模型。
式(1)-(5)为PCNN模型的数学方程描述。
神经元j的接收部分来自其他神经元与外部的输入,将接收到的输入信号通过两条通道传输。一条通道称为F通道,发送馈送输入;另一条通道称为L通道,发送链接输入。调制部分将来自L通道的信号Lj加上一个正的偏离量后与来自F通道的信号Fj进行相乘调制(模型中偏移量规整为1,β为链接强度系数,当前像素和周围像素之间相互作用的大小可通过链接系数β调节)得到内部状态信号Uj,接着Uj输入到脉冲产生部分。脉冲产生部分由阈值信号发生器与脉冲产生器组成。阈值信号发生器中的Vθ与αθ分别表示阈值幅度系数与时间衰减系数,Vθ决定迭代计算中只发放一次的条件,αθ决定一个周期中的迭代次数,见式(4)。当阈值θj超过Uj时,脉冲产生器就被关掉,停止发放脉冲,紧接着,阈值就开始下降;当θj低于Uj时,脉冲产生器被打开,神经元点火,即出于激活状态,输出一个脉冲或脉冲序列。
P C N N进行图像分割时,二维图像的每一个像素的灰度值对应为每个神经元的输入。当内部链接矩阵M、W所在邻域内有灰度值相近的像素存在时,则其中某一个像素激发产生的脉动输出将会引起附近其他类似灰度像素对应神经元的激发,产生脉动序列输出Y[t]。显然序列Y[t]包含有图像区域、边缘、纹理特征等信息。这样相似的多个神经元就构成了一个神经元集群。该神经元集群相当于一个巨大的神经元,同步的发放脉冲。一个神经元集群对应着图像中相同的区域,不同的神经元集群分别对应这图像中不同的区域。这就是PCNN的脉冲传播特性引发的同步脉冲发放特性,也是利用PCNN进行图像分割的基本原理[3]。
3 CSA算法基本原理
克隆选择算法是一种基于种群的随机迭代搜索算法,其中心思想为:抗体是天然产物,以受体的形式存在与细胞表面,抗原可与之选择性地反应,抗御与响应抗体的反应可导致细胞克隆性增值,该群体具有相同的抗体特异性,其中某些细胞克隆分化为抗体生成细胞,另一些形成免疫记忆细胞以参加之后的二次免疫反应。克隆选择是生物体免疫自适应抗原刺激的动态过程。在这一过程中所体现的学习,记忆,抗体多样性等生物特征正是人工免疫系统所借鉴的[4]。
基于信息处理的观点可以认为,克隆选择的实质就是在一代进化中,在候选解集的附近,根据亲和度大小,产生一个变异解的群体。克隆选择算法通过抗体-抗原亲和度实现个体竞争,并有效地调节过度竞争以保持抗体群的多样性。算法的运行主要基于以下几个算子[5,6,7]
3.1 克隆选择算子
将初始抗体种群按亲和度由大到小按降序排列,并将其分成由m个和r个抗体组成的两部分Am和Ar,分别表示进入记忆集的抗体和剩下的部分,其中进入记忆集的都是亲和度较高的抗体。
3.2 重组变异算子
抗体在亲和度成熟的过程中,是以受体编辑和体细胞高频变异为主要方式,由抗体重组算子和变异算子来实现克隆选择算法的亲和度成熟过程。抗体重组算子又包括抗体交换算子、抗体逆转算子和抗体移位算子。
抗体交换算子(Change Operator):是指抗体按照一定的交换概率Pc,随机选取抗体中的两个或多个点,并交换这些点上的基因形成新的抗体,抗体交换算子的示意图(图中为两点交换)如图2所示。
抗体逆转算子(Inverse Operator):是指抗体按照一定的逆转概率PI随机选取抗体中的两个点,将这两点之间的基因段首尾倒转过来形成新的抗体,抗体逆转算子的示意图如图3所示。
抗体移位算子(Shift Operator):是指抗体按照一定的移位概率Ps,随机选取抗体中的两个点,将两点之间基因段中的基因循环向左移位,使该基因段中的末位基因移到段的首位形成新的抗体,抗体循环移位算子的示意图如图4所示。
抗体变异算子(Mutation Operator):是指抗体按照一定的突变概率Pm,随机选取抗体中的一个或多个点,并由随机生成的一个或多个基因来取代,形成新的抗体,抗体变异算子的示意图(图中为单点变异)如图5所示。
3.3 克隆删除算子
克隆删除算子(Clone Deletion Operator):是指抗体A经过重组或者突变之后得到的抗体A',如果A'的亲和度低于重组或突变前的父代抗体A的亲和度,即:
则删除抗体A',用其父代抗体A来代替。
3.4 抗体补充算子
抗体补充算子(Supplement Operator):是指每一次对抗体群A进行克隆选择扩增之前,从一个随机产生的规模为Nr的候选抗体群Ar中选择NS(其中NS<
4 基于CSA算法的PCNN自动系统实现
PCNN是一种多参数神经网络模型,其应用效果的好坏在很大程度上取决于各个参数的设置。而众多参数中,有4个参数对应用效果的影响很大。它们分别是连接权矩阵W、衰减幅度系数Vθ、链接强度系数β和时间衰减系数αθ。其中连接权矩阵的设定相对简单,在不同场合均习惯将其设定为神经元之间的欧式距离平方的倒数,而衰减幅度系数在不同的具体应用中对它的要求往往也不同但可依据不同要求直接设定。另外两个参数链接强度系数β和时间衰减系数αθ对运行效果影响最大。前者将影响相似集群的大小,后者将直接影响运算效率[8]。以往方法是手工设定,需要反复实验来确定较好的一组参数,效率低且不确定性大,本文将通过克隆选择算法在解空间里自动寻求这两个关键参数的准最优解,从而实现PCNN参数的自动设定。
将克隆选择算法应用于PCNN参数选取时,首先要解决的两个问题是编码和适应度函数的设计,然后是四个进化算子(克隆选择算子,重组变异算子,克隆删除算子,抗体补充算子)的设计,当然还有初始条件和收敛条件的设置,然后运行CSA以求得问题的准最优解。其算法步骤如下:
(1)开始:设置种群规模,收敛条件,选择适合的适应度函数,对β和αθ编码。
(2)初始化:随机产生N个抗体对应β和αθ在可能范围内的可能值;
(3)评价和选择1:将N个抗体分解成由m和r个抗体组成的两部分mA,rA,分别表示进入记忆集的抗体和剩下的部分,其中进入记忆集的都是亲和度较高的抗体;
(4)克隆:在亲和度最高的抗体中选择k个进行克隆,克隆的数量与其亲和度成正比;
(5)变异:模拟生物克隆选择中的超变异过程,对克隆后的抗体执行变异操作,变异按某一变异概率以一定规模随机进行;
(6)评价和选择2:重新计算变异后的抗体的亲和度,若克隆变异后的抗体中亲和度最高的抗体比原抗体的亲和度还要高,就用该抗体替换原抗体,形成新的记忆集;
(7)消亡:模拟生物克隆选择中5%的B细胞自然消亡的过程,在Ar中选择d个亲和度最低的抗体重新初始化,以保证抗体的多样性;
(8)检查是否满足终止条件,若是则终止;否则转到步骤(2),进入下一次迭代。
上述算法的具体实现步骤如图6所示。
5 仿真试验结果与分析
PCNN在数字图像处理上的应用是其产生、发展的根本。图像分割是图像处理中最基本同时也是最重要的一个步骤,目前人们通常选用图像分割的效果来评价PCNN应用的效果[8]。本文也选用图像分割来验证本文提出算法的正确性和可行性。
实验所用计算机软硬件配置如下:
处理器:Intel Pentium 4;
主频:2.6GHZ;
显卡:NVIDIA GForce2440;
显存:64M;
内存:256MDDR;
操作系统:Microsoft Windows XP;
仿真软件:MATLAB 7.0版本。
本文将选择文献[9]中提出的基于Unit-Linking PCNN和图像熵的图像分割新方法进行对比实验。该方法是2008年1月提出的最新的基于PCNN的图像分割方法,其分割效果可以得到充分肯定。本文将通过实验从分割效果、分割时间两方面进行对比实验。
本文提出的PCNN参数自动设定方法实现图像分割时,对于所求解的PCNN参数β和αθ求解范围均设定为(0.001,2.6),编码长度为16位。设定种群规模设置为40,交叉概率pc=0.7,变异概率pm=0.35,迭代次数n=20,二次选择概率m=8,选取PCNN输出二值图像的信息熵作为适应度函数:
5.1 主观视觉效果对比
图7给出了原始图像与采用不同分割方法进行图像分割的不同结果。在主观视觉效果上看,本文提出的算法略好于文献[9]中提出的方法。这是由于虽然二者分割原理相同,所不同的只是参数选取方式,但文献[9]算法由于是手工确定,误差较大而本文提出的算法可以接近准最佳阈值,因此效果略好。
5.2 客观评价
虽然从主观视觉上可以验证本文提出算法效果优于文献[9]算法,但为了更好的评价算法的性能,本文又进行了客观评价分析。选取分割后的区域一致性、区域对比度和形状测量作为评价两种算法分割效果的客观准则[10]。
(1)区域一致性参数U(t)计算公式
其中,C为归一化因子,在这里是指整幅图像的像素数;
(2)区域对比度C(t)计算公式
其中,f0,fb为阈值t分割出的像素数;
(3)区域形状参数S(t)计算公式
其中,fN(x,y)为邻域N(x,y)的灰度
均值,t为灰度阈值,∆(x,y)为广义梯度,C为归一化因子,
三个评价准则通过计算来客观定量的评价,它们的值越接近于1,表明分割的效果越好。经计算两种算法的评价效果如表2所示,从表中可以看出本文提出算法分割效果略好于文献[9]算法。
5.3 算法执行时间
算法执行时间短是本文提出算法的主要优势,为此本文重点进行了实验测试。综合多次实验结果,迭代20次,本文提出改进算法执行时间大约为3-5分钟,而人工设定参数的时间则因人和应用的不同而有很大差别,要得到和准最优解近似的解通常至少需要花费几小时。由此可以看出本文提出的方法较人工设定参数的方法在时间上有数量级的优势。
通过上述三方面的对比实验可以看出,本文提出算法的分割效果略好于文献[9]提出算法,而在运行时间上却有明显优势,从而充分证明本文提出的基于克隆选择算法的脉冲耦合神经网络参数自动设定算法是正确和可行的。
6 结束语
本文实现了基于克隆选择算法的脉冲耦合神经网络参数自动设定,通过其在图像分割上的方针对比验证了其可行性和优越性。从仿真结果可以看出,本算法研究思想具有较好的应用前景,P C N N算法参数设定一直影响着其在实际应用中的推广,本文提出的算法较好解决这一问题,是对P C N N理论的进一步完善,在P C N N的理论研究和实际应用中具有很重要的现实意义和应用价值。同时也应看到由于对视觉机制认识的限制,P C N N模型离真正的视觉模型尚有一定差距,对P C N N模型的进一步改进,仍是该领域研究的重点和难点。
参考文献
[1]马义德,齐春亮.基于遗传算法的脉冲耦合神经网络自动系统的研究[J].系统仿真学报,2006,18(3):722-725.
[2]吴泽俊,钱立进,梁意文.入侵检测系统中基于免疫的克隆选择算法[J].计算机工程,2004,6(30):50-52.
[3]黄荣杰,崔世林.基于点火频率的PCNN灰度图像分割方法研究[J].电子技术应用,2007,(1):64-66.
[4]王磊,潘近,李成.免疫算法[J].电子报,2000,28(7):74-78.
[5]高玮.遗传算法与进化规划的比较研究[J].通讯和计算机,2005,2(8):10-14.
[6]王正志,薄涛.进化计算[M].长沙:国防科技大学出版社,2000
[7]杜海峰.免疫克隆计算与人工免疫网络研究与应用,博士后研究工作报告[R].西安电子科技大学,2003
[8]马义德,李廉,王亚馥,戴若兰.脉冲偶尔神经网络原理及其应用[M].北京:科学出版社,2006
[9]聂仁灿,周东明,赵东风.基于Unit-Linking PCNN和图像熵的图像分割新方法[J].系统仿真学报,2008,20(1):222-227.
假如我会克隆,我要克隆地球作文 篇5
“咚咚咚!”“请进!”“所长!据有关资料显示，目前地球资源所剩无几，而人口总数却多达100多……”“停!”我挥了挥手，“我知道了!”片刻，我问道：“剩下的资源还能维持多久?”“最多只有八年!”“什么?”我愣了一会儿说：“先去开个紧急会议!”“好!”我抱着头想了一会儿，便向“会议室”走去。
“什么事这么急呀!”大家都问我，我表情严肃地说：“地球资源紧缺，必须‘转移’了!”“可是到哪儿去呢?”“太阳系以外不是有一颗有空气和水的星球吗?”“不过……”……大家开始争论起来。最后，举手表决，26比24。实行“转移”!
“可是‘转移’必须将地球上的物品也带走，否则……”一位同志说，“我们依然无法生活!”“这我已想好了!”我笑着说：“克隆!”、“‘转移’a计划实施中。”电脑汇报着，“现在，就是运输问题了!”李逸凡对我说道。我微微一笑，调出‘n’星目前状态屏，“在各地区都已放置了克隆机器，我们只需将各种物品的一部分放入提取器中，就能提取出‘非生物dna’，将它们的‘非生物dna’用巨型发报机(宇宙型bx号)发向‘n’星球，一切都ok了!”我向李逸凡介绍着，“这样虽然会浪费不少地球资源，不过还是一个不错的方案!”李逸凡听了，高兴地笑了。
克隆算法 篇6
人工免疫系统 (Artificial Immune Systems, AIS) 是继神经计算、进化计算之后的自然计算的研究新方向, 已经迅速成为研究热点, 主要是通过深入探索生物免疫系统所蕴含的信息处理机制, 建立相应的工程模型和算法, 用于解决各种复杂问题。1958年, Burnet提出了生物免疫的克隆选择学说, 该学说的核心是抗体形成理论, 旨在解释生物免疫系统的应答机制。
1 免疫系统
生物免疫系统将所有的细胞分为两类:Self细胞 (自我) 和NonSelf细胞 (非我) 。Self细胞指自身健康, 没有被感染、破坏的细胞;NonSelf细胞指病毒、细菌、寄生虫等有害物质和自身被感染、破坏的细胞。免疫就是识别Self和NonSelf, 并消灭NonSelf, 是为了保证机体完整性的一种生理学反应。用集合表示有这么一个关系:对于集合域X, 它包括两个子集自体集合S和非自体集合N, 则有自体集合S X和非自体集合N X, 而且S∪F=X且S∩F=φ。
2 人工免疫算法
人工免疫系统抽取生物免疫系统所蕴含的信息处理机制, 建立用于解决各种复杂问题的工程模型和算法, 这些模型和算法都力图集中体现以上的生物免疫系统的相应特点。
人工免疫算法 (A r t i f i c i a l I m m u n e Algorithlum, AIA) 是模拟人体免疫学原理而设计的一种新型算法, 是自然免疫系统在进化计算的一个实现。
人工免疫算法的基本流程如图1:
STEP1:初始化AIA的抗原。对运行过程所需参数和数据进行设置, 包括初始化运行参数、基因库以及确定抗体的编码方式和构造初始抗体集, 通常可以在解空间中随机产生N个候选解作为初始抗体, N为抗体群中抗体的数目。
STEP2:计算亲和力 (affinity) 。亲和力是一个抗体结合部位与一个抗原决定基结合的牢固性, 结合自抗原分离的可能越小。用来表示抗原和抗体之间、抗体和抗体之间结构的相信程度。设定亲和力的计算函数为Affinity (B, G) , 一般使用介于0到1之间的实数表示, Affinity (B, G) 值越大说明抗体B和抗原G之间匹配得越好。
STEP3:产生新的抗体。调用人工免疫算法, 初识抗体通过人工免疫算法的作用产生新的抗体。
STEP4:调用Affinity (B, G) , 计算新抗体的亲和力。
STEP5:若新抗体中有与抗原匹配的抗体, 则结束, 否则转到STEP6。
STEP6:抗体选择。按照“优胜劣汰”的自然选择机制, 在原有的N个有效抗体和新产生的若干个体抗体中选择出N个与抗原匹配得较好的抗体构成新的抗体群, 在进行选择操作时, 应依据抗体之间的排斥力限制进入新抗体群中的相同抗体的数目, 以保持抗体群中抗体的多样性, 增强抗体群的免疫力, 选择完成后转到STEP3。
3. 基于克隆选择的免疫识别算法
克隆选择学说早在1958年就由Burnet建立, 描述了获得性免疫的基本特性, 并且生命只有成功识别抗原的免疫细胞才得以增殖, 经变异后的免疫细胞分化为效应细胞 (抗体) 和记忆细胞两种。但计算领域的克隆选择算法 (Colonel Selection Algorithm, CSA) 却直到2001年才由D.castro和von Zuben明确提出, 能够完成机器学习和模式识别的任务, 并可以用来解决优化问题。其核心是复制 (克隆) 和变异。前者与个体的亲和度成正比, 保证群体亲和度逐步增大, 后者与个体的亲和度成反比, 保留最佳个体并改进较差个体。
克隆选择算法是基于群体的免疫算法, 是一种模拟免疫系统的学习过程的进化算法, 它模拟这一过程进行优化。也是抗体集进行群体更新的策略。
STEP1:抽取抗原集合中的一个抗原。
STEP2:计算与抗体集合中每个抗体的亲和力;从中选择n个亲和力最高的抗体。
STEP3:对选择出来的抗体进行克隆增殖, 目的是确定对各抗体所在邻域做局部搜索的次数。克隆规模正比于抗体的亲和度, 即亲和度高的抗体得到的局部搜索的机会较多。
STEP4:对克隆产生的个体进行突变, 用来对各抗体所在的邻域进行局部搜索, 变异位数反比于其同抗原的亲和力, 即对亲和度较高的抗体, 则在其较小的邻域范围内做精细搜索。
STEP5:压缩选择, 在抗体群中选择具有最高亲和度的n个抗体组成新一代抗体群, 更新抗体集合。
STEP6:如果满足终止条件, 则结束;否则转至STEP1继续执行。
从算法流程分析得知, 克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖, 随后通过遗传变异分化为多样性效应细胞 (如抗体细胞) 和记忆细胞。克隆选择对应着一个亲和力成熟 (affinity maturation) 的过程, 即对抗原亲和力较低的个体在克隆选择机制的作用下, 经历增殖复制和变异操作后, 其亲和力逐步提高而“成熟”的过程, 本质上是一个达尔文式的选择和变异的过程。
4 结论
利用人工免疫的基本原理来解决计算机系统的安全问题, 主要也是区分“自体”和“非自体”的问题, 人工免疫系统是具有自学习、自适应、自组织的高度复杂性系统的代表, 已经迅速成为研究热点, 其研究成果已应用到计算机安全、模式识别、机器学习、机器人控制、异常和故障检测、数据挖掘和分析及复杂优化问题求解等诸多领域。
摘要：传统基于人工免疫的识别算法对于正常行为和非正常行为的定义仅限一次, 无法根据实际网络环境中的变化做出调整。克隆选择算法是基于群体的免疫算法, 是一种模拟免疫系统的学习过程的进化算法, 也是抗体集进行群体更新的策略。
关键词：人工免疫,克隆选择,亲和力
参考文献
[1]Bumet, F.M.The Clonal Selection Theory of Acquired Immunity[M].Cambridge:Cambridge University, 1959.
[2]De Castro, Von Zuben, F.J.Learning and Optimization Principle Using the Clonal Principle[J].Advanced Immunology, 1998, 4:62-70.
克隆算法 篇7
自80年代后期, 由于小波变换、分形、人工神经网络、视觉仿真理论的建立, 人们开始突破传统的信源编码理论, 例如不再假设图像是平稳的随机场。图像压缩编码向着更高的压缩比和更好的压缩质量发展。
图像压缩方法主要有两种途径, 一是通过减少图像中各像素间相关性的冗余来减少图像的总比特数, 例如利用离散余弦变换 (DCT) 来降低数据间的相关性, 然后将其中主要的分量保留, 最终实现减少数据量的目的。另一种是根据数据的动态范围及其出现的频繁程度, 来确定适当的编码方案, 通过这种适当的编码方式安排不同数据所占编码比特数, 实现减少所需总比特数以达到压缩的目的[1,2,3]。
本文主要涉及的图像压缩方式是变换编码的压缩。变换编码有两个显著特点:一是高压缩比;二是计算复杂度高。变换编码之所以能压缩信息的比特数, 是因在经过变换得到的系数矩阵中, 数值较大的方差总是集中在少数系数中。多数图像的统计特性表明, 大幅度的系数往往集中在低频率区内, 这样可给较小的系数分配较少的比特数, 甚至可不予传送, 从而压缩了整个传送数据的比特数。因此, 变换本身只是将分布在变换域中的信息变得相对集中, 为合理的少分配给某些数据比特数提供可能。变换编码有诸多特点, 故应用广泛。
2 小波图像压缩
小波的定义是在有限间隔, 且其平均值为零的一种函数。其具有有限的持续时间和突变的频率与振幅, 波形可以是不规则的, 也可是不对称的, 在整个时间范围内的幅度平均值为零。而正弦波和余弦波具有无限的持续时间, 其可从负无穷扩展到正无穷, 且波形平滑, 其振幅和频率也恒定。
在数学上, 小波定义为对给定函数局部化的函数。小波可由一个定义在有限区间的函数Ψ (x) 来构造, Ψ (x) 称为母小波 (Mother Wavelet) 或基本小波。一组小波基函数{Ψa, b (x) }, 可通过缩放和平移基本小波Ψ (x) 来生成, 即
式中, a为进行缩放的缩放参数, 反映特定基函数的宽度;b为进行平移的平移参数, 指定沿x轴平移的位置。
一幅图像的小波变换编码过程如图1所示。小波变换的目的是对图像做解相关处理, 若不考虑计算误差, 该过程是无损且可逆的。解相关后的图像在变换域形成一系列小波系数, 并对其进行整数量化后编码形成码流下传。而量化过程是有损且不可逆的, 图像的失真主要是因该过程而产生的。图像的解码恢复过程是图1编码过程的逆过程, 如图2所示。
一幅图像经图1和图2的处理过程后, 得到的恢复图像为具有一定压缩的有损图像。在处理过程中, 压缩是由量化过程和编码过程产生, 量化方法的选择与量化效果的优劣将直接影响最终图像的压缩结果。
3 免疫克隆选择的图像压缩
克隆选择算法在人工免疫界备受研究者的欢迎, 这是由于其具有的特性。首先, 高频变异和新个体的不停加入保证了算法在执行中抗体的多样性, 而多样性对于优化或进化算法均较为重要, 若不能保证将会导致算法的早熟。其次, 算法具有多分辨分析的特性, 在算法前期, 变异操作对抗体的修改幅度较大, 保证能够在全局范围内搜索。
De Castro提出的克隆选择算法流程已成为标准克隆选择算法, 其算法流程如图3所示。
对于一幅图像进行二维小波变换后, 尺度为j的低频部分可分解为尺度为j+1的低频部分和3个方向的高频部分。由图3可看出, 经变换后的图像被分成了低频与高频两部分, 且能量集中于低频段, 所以可根据此现象对图像进行压缩。
4 实验结果
本实验选用30张不同的图片对其进行压缩, 实验过程中克隆选择算法的各参数设置如下表1所示。
如图5和图6所示, 经克隆选择后得到该图像的分解级别为5时最优, 这与分析的结果极为接近。
在小波变换中, 小波基的选择会影响压缩效果, 实验选用的Daubechies 1小波基可获得较好的压缩效果, 因此实验选用Daubechies 1小波基, 其结果如图7所示。
5 结束语
基于免疫克隆选择的图像压缩算法结合了免疫克隆算法的抗体多样性、全局寻优的特点和小波变换多分辨率分析的特点。在压缩过程中不仅采用了小波分解后的低频分量, 且还加入了具有一定的高频部分, 使压缩后的图像信噪比更低, 从而保证了图像的质量。实验结果表明, 所提出的图像压缩方法具有良好的压缩效果。此外, 在实际的应用中, 亲和度的计算还可选用不同的函数来度量, 进一步改善了算法性能。克隆选择算法的全局寻优能力依赖于初始解, 若选择好的初始解进行迭代, 相信能够取得更好的识别效果。
摘要：针对在图像压缩过程中压缩质量与压缩时间相互间存在矛盾, 文中提出了一种基于免疫克隆选择的图像压缩算法。该算法结合免疫克隆算法的抗体的多样性、全局寻优和小波变换多分辨率分析的特点。在压缩过程中不仅采用了小波分解后的低频分量, 还加入了一定的高频部分, 使压缩后的图像信噪比更低, 从而保证了图像的质量。实验结果表明, 所提出的图像压缩方法具有相对较高的压缩比和良好的压缩效果。
关键词：免疫克隆选择,多分辨分析,小波变换,信噪比
参考文献
[1]龚涛, 蔡自兴.基于正常模型的人工免疫系统及其应用[M].北京:清华大学出版社, 2011.
[2]丁永生.基于生物网络的智能控制与优化研究进展[J].控制工程, 2010 (4) :416-421, 536.
[3]DASGUPTA D, ATTOH-OKINE N.Immunity-based systems:a survey[C].Orlando, USA:In proceedings of the Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics, 1997.
[4]赵书兰.Matlab R2008数字图像处理与分析实例教程[M].北京:化学工业出版社, 2009.
[5]田振川.基于遗传算法的分形图像压缩技术研究[J].计算机应用与软件, 2013, 26 (3) :79-83.
[6]阮秋琦, 阮宇智.数字图像处理[M].3版.北京:电子工业出版社, 2012.
[7]TIMMIS J, KNIGHT T.Artificial immunes system:using the immune system as inspiration for data mining[M].Hershey:Idea Publishing Group, 2001.
[8]TIMMIS J, NEAL M, HUNT J.An artificial immune system for data analysis[J].Biosystems, 2000, 55 (1) :143-150.
[9]DE CASTROL N, VON ZUBEN F J.Artificial immune systems:Part I-basic theory and applications[R].Dezembro:Universidade Estadual de Campinas, 1999.
克隆算法 篇8
1.1 相关术语
抗原:免疫学上,抗原是指能刺激机体免疫系统产生抗体的物质。本文中,抗原指待求问题。例如优化问题(p)
其中,f(X)为目标函数,变量X={x1,x2,…,xm},xi(i=1,2,…,m))为变量X第i个分量。目标函数f(X)称为抗原。
抗体及抗体群:本文中,抗体是抗原可行解的一个代表。抗体A={x1′,x2′,…,xm′}是变量X的编码,记为A=e(X),而X称为抗体A的解码,记为X=e-1(A)。xi′(i=1,2,…,m)称为抗体A的第i个分量编码。编码方式可以是二进制串,十进制串,本文采用十进制编码。根据设定精度,变量分量xi∈[di,ui](i=1,2,…,m)的编码长度为l,其编码形式为:xi′=0.a1a2…al,式中,ai(i=1,2,…,l)为0到9之间的整数,这样就实现了变量分量在0～1的实数编码。对应变量分量译码方式为:
令I为抗体空间,则A∈I,抗体种群A=[A1A2…An],Ai∈I,1≤i≤n,正整数n称为抗体种群规模。
亲合度:免疫学上为抗体与抗原结合力的大小。本文中,亲合度就是目标函数值
1.2 自适应二段克隆选择算法(adaptive two phase clone selection algorithm,ATPCSA)
算法主要步骤如下:
Step1:初始化:给出算法终止条件,设定抗体分量编码长度l,抗体分量编码每增加1位所经历的迭代次数itbit,随机产生初始抗体群A(0)=[A1(0)A2(0)...An(0)](抗体Ai(0)={ai1(0),ai2(0),...,aim(0)}(i=1,2,…,m)的各分量aij(0)(j=1,2,…,m)编码长度l(0)=1),令k=0;置抗体分量编码每增加一位所经历的迭代次数记数器itcount=0;
Step2:计算亲合度:计算抗体群A(k)中所有抗体亲合度。
Step3:抗体群排序:A(k)中所有抗体按亲合度从大到小排序。
Step4:抗体分量编码逐位增加操作Tac若itcount>itbit,且l(k)
Step5:对A(k)进行克隆操作Tcc,得群体Y(k)。
Step6:Baldwin效应学习操作Tlc:若l(k)=l,则对Y(k)进行Baldwin学习操作。得群体,Y(k)′令。Y(k)=Y(k)′
Step7:对Y(k)进行克隆变异操作Tmc:即依据概率对克隆后的群体Y(k)进行变异,得抗体群Z(k)
Step8:计算亲合度:计算Z(k)各抗体亲和度。
Step9:对Z(k)及A(k)进行克隆选择操作Tsc,得A(k+1)。
Step10:算法终止测试:如果算法终止条件满足,则停止;否则,itcount=itcount+1,k=k+1回到Step3。
1.2.1 抗体分量编码逐位增加操作
定义:
式中,i=1,2,…,n,j=1,2,…,m,|→表示数字的按位替代,aij(k)l(k)+1表示抗体Ai(k)各分量的第l(k)+1位上的数字编码。(5)式表示将Ai(k)各分量的l(k)+1位上的数字置为0;这样确保编码长度增加,不会影响到抗体Ai(k)的亲合度。
1.2.2 克隆操作
定义:Y(k)=Tcc(A(k))=[Tcc(A1(k))Tcc(A2(k))…Tcc(An(k))]T(6)
式中:Y(k)=Tcc(Ai(k))=Ii×Ai(k),i=1,2,…,n,Ii为元素为1的qi维向量,称抗体Ai的qi克隆。qi是一个自适应的参数或是一个常量。
克隆过后,抗体群变为:
1.2.3 Baldwin效应学习操作
根据文献[9],基于Baldwin效应的学习可改变搜索空间的形状,也因此提供搜索到最优解的更好的路径,Baldwin学习操作Tlc设计如下:
对Y(k)=[Y1(k),Y2(k),…,Yn(k)]中的每一个抗体Yij(k),这里Yi(k)=[Yi1(k)Yi2(k)…Yiqi(k)]
定义:
并进一步如下修正:
式中,s,t∈{1,2,…,n},s≠t≠i,ys(k)表示从Ys(k)中随机选取的一个抗体,yt(k)表示从Yt(k)随机选择的一个抗体,并且f(yt(k))>f(yt(k)),s>0称为学习强度。Pl∈[0,1]为Baldwin学习概率。rand代表[0,1]区间内均匀分布的随机数。
1.2.4 变异操作
变异算子Tmc定义如下:
本文采用自适应位变异法。设编码长度l=10,Yij(k)∈Yi(k),i=1,2,…,n,Yij(k)={yij1(k),yij2(k),...,yijm(k)},yijw(k)(w=1,2,…,m)为K代变异前第i个抗体的第w个分量值,zijw(k)为其变异后的值。具体做法如下:
1)在变异操作之前先将抗体群按亲合度大小排序。
2)计算Yij(k)的变异概率Pm:Pm=m-(n+1)/(n+r),这样保证每个其变异概率在变化。
3)按下式算yijw(k)各编码位的变异概率Pi(i=1,2,…,l):
式中n为群体规模,r为抗体在群体中的排名序号,k为当前迭代次数,T为设定的进化总代数,α为编码位的变异概率控制参数。
4)以概率分布Pi(i=1,2,…,l)从中随机选择一个位号b,如第2位。
将yijw(k)的第b位变为0～9的随机整数。表示为:
式中,|→表示数字的按位替代,rand代表[0,1]区间内均匀分布的随机数,Int()表示取整,yijw(k)b表示克隆抗体yij(k)的第w个分量yijw(k)的第b位上的数字编码。
1.2.5 克隆选择操作
对Z(k)进行克隆选择操作。坌i=1,2,…,n,记
新一代群体如下:
式中,Ai(k+1)=Tsc(Zi(k)∪Ai(k)),i=1,2,…,n
2 函数优化应用
为了评价上面提出的自适应两段克隆选择算法,在对函数优化时的求解性能,将该算法与保留最优值的标准的遗传算法(SGA)和基于非均匀变异的克隆选择算法(CSA)、文献[1]中提出的采用混沌变异的进化算法以及文献[2]中提出的自适应混沌克隆进化规划算法(ACCA)进行了对比。测试函数如下:
测试时,对于标准遗传算法和混沌进化算法,取交叉概率Pc=0.9,变异概Pb=0.08,种群规模都为50;而克隆选择算法、自适应混沌克隆进化规划算法和自适应两段克隆选择算法的种群规模为25,克隆规模为50,这样,保证各种算法的每代的函数计算次数大致相同;混沌变异进化算法采用文献[1]中提到的“尺度收缩”的变异策略;克隆选择算法,采用非均匀变异;自适应混沌克隆进化规划算法,取变异控制参数α=1,β=0.1～10,γ=0.2。自适应两段克隆选择算法中取编码长度l=10,位变异概率控制参数α=0.1,,学习概率Pl=0.8,学习强度s=0.8;
对于二维测试函数优化,取算法的总进化代数为100,抗体增加一位编码所经历的迭代数itbit=5;对于高维函数,取变量维数为10,算法总进化代数为300,抗体增加一位编码所经历的代数itbit=15。无论是二维测试函数还是高维测试函数,ATPCSA的求解精度和求解的稳定性明显优于其它三种算法;
3 结论
本文基于免疫学中的克隆选择理论,首先引入了新的变异算子,利用了抗体质量、进化代数自适应控制位变异。一定程度上避免了按位随机变异搜索的盲目性。再者,为充分有效的利用进化过程中的有用信息指导进化,引入了Baldwin学习算子,并将克隆选择进化过程分为两个阶段,抗体编码位的增加阶段及Baldwin学习阶段,部分函数优化测试实验证实,本文提出的算法在求解精度及求解的稳定性上是有效的。
参考文献
[1]骆晨钟,邵惠鹤.采用混沌变异的进化算法[J].控制与决策,2000,15(5):557-560
[2]杜海峰,公茂果,刘若辰,焦李成.自适应混沌克隆进化规划算法[J].中国科学E辑,信息科学,2005,35(8):817-829.
[3]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.
[4]焦李成,杜海峰,刘芳,等.免疫优化计算、学习与识别[M].西安:西安电子科技大学出版社.
[5]周泉,章兢.基于克隆选择原理的免疫算法[J].计算机工程与应用,2005(21).
克隆算法 篇9
克隆选择算法是模拟自然免疫系统功能的1种新的智能方法,它是在传统进化算法的基础上,引入了亲合度成熟、克隆和记忆机理,并利用相应的算子保证了算法能快速地收敛到全局最优解。与进化计算相比,克隆选择算法在提高收敛了速度的同时,较好地保持了种群的多样性,有效地克服了早熟收敛等进化计算本身难以解决的问题。因此,克隆选择算法也可用于解决水库优化调度问题。人工免疫系统算法在水库优化调度中已有初步的应用[1],并表现出了良好的优化性能。本文在克隆选择算法的基础上,结合抗体克隆选择学说,对克隆选择算法进行了改进,提出了1种新的人工免疫系统算法——免疫克隆选择算法(Immune Clonal Selection Algorithm,ICSA),并将其应用到水库优化调度中,建立了基于免疫克隆选择算法的水库优化调度方法,为水库优化调度问题的求解提供了1种新的方法。
1 水库优化调度数学模型
水电优化调度目标常采用在调度周期内水电系统的发电量或经济效益最大、耗水量或发电支出费用最小和弃水量最小等[2,3,4,5]。在此采用发电量最大优化调度目标,则水电优化调度问题描述为:已知水库的初始水位和调度期内各时段的来水量,求电站在调度周期内各时段的发电引用流量以及出力过程,使调度周期内电站的发电量最大,并且满足水库水位、流量限制以及水力联系等约束条件,并且弃水量最小。
以单个水电站水库为例,设1个调度周期划分为T个时段,t为时段变量(t=1,2,…,T),Qt为电站第t时段发电流量,H1为电站第t时段的平均发电水头,Mt为第t时段小时数,K为电站综合出力系数,则在调度周期内水电站发电量最大的目标函数可表示为:
约束条件:
(1)水量平衡约束
(2)水库蓄水量约束
(3)水库下泄流量约束
(4)电站出力约束
式中:E为电站年发电量;Vt+1为电站第t时段末水库蓄水量;Vt为电站第t时段初水库蓄水量;It为第t时段平均入库流量;St为水库第t时段弃水流量;Vt,min为电站第t时段应保证的水库最小蓄水量;Vt为电站第t时段水库蓄水量;Vt,max为电站第t时段允许的水库最大蓄水量;Qt,min为电站第t时段应保证的最小下泄流量;Qt为电站第t时段下泄流量;Qt,max为电站第t时段允许的最大下泄流量;Nmin为电站的保证出力;Nmax为电站的装机容量。
2 免疫克隆选择机理及算法
人工免疫系统是受免疫学启发,模拟免疫学功能、原理和模型来解决复杂问题的自适应系统。1958年Burnet等提出了著名的抗体克隆选择学说,克隆选择是生物免疫系统自适应抗原刺激的动态过程,在这一过程中所体现出的学习、记忆、抗体多样性等生物特性,正是人工免疫系统所借鉴的。目前对抗体克隆选择机理进行模拟最为经典的算法是De Castro在2000年提出的克隆选择算法[6],它通过克隆、超变异、选择等操作来完成对抗体种群成熟过程的模拟。抗体克隆选择原理如图1所示。
免疫克隆选择算法是依靠编码来实现与问题本身无关的搜索,并表现出更好的解决问题的潜力[7]。克隆是将1个低维空间的问题转化到更高维的空间中解决,然后将结果投影到低维空间中,从而获得对问题更全面的认识。
3 水库优化调度的ICSA算法设计
在水电站优化调度中,水电站运行策略一般用发电引水流量序列(Q1,Q2,…,QT)来表示[8],而发电引水流量序列又可以转化为水位变化序列(Z1,Z2,…,ZT)。为方便起见,以水库水位Zt(t=1,2,…T)作为优化变量[9]。对于水电站优化调度的ICSA可理解为:在水库运行水位允许的范围内,随机选取m组水位变化序列,根据预定的法则,逐步迭代,最终达到最优解。
3.1 抗体编码
针对水库优化调度问题的特点,本文采用实数编码方式。同时,根据水库水位编码空间是离散的还是连续的,将实数编码分为离散空间实数编码和连续空间实数编码。
(1)离散空间实数编码。把水库在时段t允许的水位变化区间分为m等份,抗体的每一向量(基因)可用整数n(n=1,2,…,m,m+1)表示。从抗体基因转换到水库水位的解码公式为:
式中:Zt,max、Zt,min分别为t时段水库水位的最大值和最小值。
(2)连续空间实数编码。在水库时段t允许的水位变化区间内随机产生1个抗体,则从抗体基因转换到水库水位的解码公式为:
式中:rand(0,1)表示[0,1]区间均匀分布的随机数。
3.2 亲和度函数
根据水库优化调度的目标,以发电量最大为目标的适应度函数如下:
3.3 克隆操作
在人工免疫系统中,克隆操作按如下方式进行定义:
式中:为抗体种群规模,Ii为元素值为1的qi维行向量,称抗体αi的qi克隆,qi如式(10)所示:
一般取
式中:f(ai(k))为抗体ai(k)的亲和度;Nc为克隆规模;Int为大于x的最小整数。
克隆过后,种群变为:
Y'(k)=A'(k)={A1'(k),A2'(k),…,A'n{k))(12)式中:A'(k)={ai1(k),ai2(k),…,aiqi(k)且aij(k)=ai(k),j=1,2,…,qi。
3.4 克隆变异操作
针对马斯京根模型参数估计具体问题,免疫克隆选择算法采用了多项式变异方式来实现对于免疫系统中超变异的模拟。根据变异概率pm,对克隆后的抗体群体进行变异操作,克隆变异操作可表示为:
3.5 克隆选择操作
与进化计算中的选择操作不同,克隆选择操作是从抗体各自克隆后的子代中选择出优秀的个体,从而形成新的种群。具体地,Vi=1,2,…n,记Bi(k)=max{Zij(k)}={Zij(k)Imaxf(Zij(k)),j=1,2,…,qi}为对应的Ai(k)经过克隆、变异操作后亲和度最大的抗体,则对概率ps(Bi(k)∪Ai(k)→Ai⑷k+1)),当f(Ai(k))
3.6 算法流程
通过上面对水电优化调度的免疫克隆选择算法的描述,下面给出基于免疫克隆选择的水电优化调度算法的计算流程:
(1)初始化参数设置。抗体种群规模n,抗体克隆规模Nc,变异概率Pm,交叉概率Pc;随机生成初始抗体种群A(0)={a1(0),α2(0),…,αN(0)},设定亲和度成熟条件;设定当前迭代次数k=0。
(2)计算抗体群A(k)的亲和度A(k):{f(A(k))},若满足亲和度成熟条件,则输出A (k)中抗体-抗原亲和度最高的抗体,算法停止;否则,转步骤(3)。
(3)对抗体种群A(k)执行克隆操作:(A(k)),获得抗体种群A'(k)。
(4)对抗体种群A'(k)执行克隆变异操作:(A'(k),获得抗体种群A"(k)。
(5)计算抗体A”(k)的亲和度A"(k):{f(A"(k))}。
(6)根据亲和度大小,针对抗体种群A(k)和A"(k)执行克隆选择操作:Ts(A(k)+A"(k),生成下一代抗体种群A(k+1)。
(7)k=k+1,如果终止条件满足,则算法结束。否则,转步骤(2)。
算法终止条件:1)抗体亲和度成熟达到了指定的停止条件;2)算法达到最大迭代次数。
4 实例仿真
4.1 实例计算
为了验证上述算法的可行性与有效性,以某水库为例进行计算。已知该水电站水库的水位、库容关系曲线,下游水位与流量关系曲线,设计中水年流量过程线,水库正常蓄水位为704 m,死水位685 m,电站出力系数为8.5,保证出力为78 MW,装机容量为300 MW,要求水库在洪水期6、7、8 3个月水位不超过695 m,按年发电量最大求水库的优化调度过程。ICSA算法参数设置为:抗体种群规模n=50,抗体克隆规模Nc=5,变异概率Pm=0.8,交叉概率Pc=0.2,最大迭代数为300。用ICSA算法求得的优化调度结果如表1所示。
4.2 结果分析
本文用增大离散点的方法模拟问题规模的增大,同时为了对计算结果进行比较,分别用免疫克隆选择算法和动态规划在不同的水库水位离散情况下进行计算,其中免疫克隆选择算对法每种离散情况分别计算30次,结果取平均值。表2列出了2种算法最优解和所花费计算时间,其中免疫克隆选择算法还给出了连续编码方式下30次最优值。
由表2可知,当离散点由500增大到5 000时,动态规划求解时间明显增加,而免疫克隆选择算法运行时间增加不明显,计算速度快。同时,由表2还可以看出,对于免疫克隆选择算法,采用连续编码方式比5 000离散点的发电量增加了14 MW,而时间仅增加了0.2 s左右,说明ICSA算法具有很强的寻优能力。表3给出了ICSA连续编码30次独立运行的统计结果。可以看出,30次求解结果都优于动态规划5 000离散点的求解结果,寻优率达到了100%,这说明ICSA算法具有卓越寻优能力和很好的稳定性。
为了反应免疫克隆选择算法的收敛速度,在抗体种群规模、抗体克隆规模、进化代数、交叉概率、变异概率选取相同参数条件下,取不同的进化代数进行计算,结果见表4。由表4可知,在种群规模不、变的情况下,仅增加进化代数、增加迭代次数,免疫克隆选择算法可很快收敛。
图2给出了连续编码方式下免疫克隆选择算法求解水库优化调度问题的最优适应值变化曲线。从图2可以看出,免疫克隆选择算法在35代其求解结果就达到了动态规划5 000离散点的计算精度,其计算时间在0.5 s左右,而动态规划计算时间则超过400 s,由此可见,免疫克隆选择算法不但具有更高的求解精度,而且具有更好的求解效率。
5 结论
本文基于抗体克隆选择学说,提出了1种新的水库优化调度优化算法——基于免疫克隆选择算法的水库优化调度方法。研究结论如下:1)通过在克隆选择算法中引入免疫基因操作,提高了算法的求解精度和求解效率,避免了“维数灾”和早熟问题。2)通过水库优化调度实例验证了ICSA算法用于水库优化调度的可行性和有效性。实例研究结果表明ICSA算法为水库优化调度问题的求解提供了1种新的方法。
摘要：在研究了人工免疫系统中的克隆选择学说和克隆选择算法的基础上,研究了1种新的人工免疫算法——免疫克隆选择算法,并将其应用到水库优化调度中,提出了1种基于免疫克隆选择算法的水库优化调度方法。该算法通过在克隆选择算法中引入免疫基因操作,提高了算法的求解精度和求解效率,避免了“维数灾”和早熟问题。实例研究结果表明,相对于动态规划,免疫克隆选择算法计算速度快、收敛性好,提高了计算效率,较好地解决了传统的动态规划方法求解水库(群)优化调度问题存在“维数灾”问题。
关键词：水库,优化调度,免疫克隆选择算法
参考文献
[1]左幸,马光文,徐刚,等.人工免疫系统在梯级水库群短期优化调度中的应用[J].水科学进展,2007,18(2):277-281.
[2]罗云霞,周慕逊,王万良.基于基因拟子协同进化算法的水电优化调度研究[J].水力发电学报,2010,29(4):58- 62.
[3]贾仁甫,陈守伦,梁伟.基于混沌优化算法的混联水电站群长期优化调度[J].水利学报,2008,39(9):1131-1135.
[4]陈立华,梅亚东,董雅洁,等.改进遗传算法及其在水库群优化调度中的应用[J].水利学报,2008,39(5):550-556.
[5]向波,纪昌明,罗庆松.免疫粒子群算法及其在水库优化调度中的应用[J].河海大学学报(自然科学版),2008,36 (2):198-202.
[6]DE C L N,VON Z F J.The Clonal Selection Algorithm with Engineering Applications[C].IEEE press,2000.
[7]刘芳,潘晓英.基于免疫克隆选择的块匹配运动估计[J].软件学报,2007,18(4):850-860.
[8]席秩义,李成家,杨建霞.水电站水库优化调试几种求解方法的比较研究[J].陕西电力,2010,38(4):74-77.
克隆算法 篇10
地震波阻抗反演属于求解最优化问题。模拟退火算法、混沌算法、人工神经网络算法、遗传算法等已经在这个领域得到了应用。但这些算法对反演的初始模型要求较高, 而且求解精度不高。近年来, 作为一种基于迭代的人工智能优化算法, 粒子群优化算法已经在许多领域得到了广泛应用。2006年易远元博士提出了地震波阻抗反演的粒子群算法实现方法, 并利用模型对其进行了检验, 在无噪声的情况下, 反演结果与模型一致[1]。但是, 在优化后期迭代过程中, 收敛速度下降;当收敛到一定精度时, 无法继续优化, 因此不利于实现全局极值搜索, 易于陷入局部极值。
免疫克隆IC ( Immunity Clone) 算法源自对生物免疫系统的研究, 克隆选择机制中存在着克隆、超变异、抗体与抗原特性结合、记忆细胞产生等过程, 在保证收敛速度的同时, 又能够维持抗体的多样性。因此免疫克隆算法与粒子群算法结合可以避免粒子群优化算法易陷于局部极值的缺陷, 提高了进化后期算法的收敛速度和精度。文献[4]提出求解大规模TSP问题的自适应归约免疫算法;文献[5]提出用于约束响应的人工免疫响应进化策略;文献[3]提出用于多目标优化的量子免疫克隆算法;文献[2]提出用于函数优化的基于蚁群信息素的无指导的学习机制, 并在此基础之上构造了基于信息素模因的克隆选择算法。
近年来, 免疫粒子群算法及其应用也因此受到越来越多的关注和研究。文献[6]提出的免疫粒子群算法通过引入免疫算子, 提取“疫苗”并通过“接种疫苗”和“免疫选择”指导搜索过程;文献[8]基于传统的速度——位置更新操作, 根据亲和度的高低进行粒子克隆选择、克隆抑制和高频变异, 大大缩短了搜索时间;文献[7]提出了一种把免疫接种、免疫测试机制与二进制粒子群算法相结合的混合算法用于最小属性约简问题;倪霖等 (2007年) 提出使用二进制字符串序列表示粒子位置的免疫粒子群算法进行特征选择;文献[10]用免疫粒子群算法解决光纤通信系统中偏振模色散现象的自适应补偿问题;张蕾等 (2007年) 提出自适应克隆选择粒子群优化算法用于多用户检测, 将亲和度高的抗体按与其亲和度成正比进行克隆, 引入变异算子与亲和度成反比进行变异, 以保证抗体的多样性。本文在以上研究的基础上, 提出了一种自适应免疫粒子群优化算法, 并将该算法应用于波阻抗反演问题, 以验证该算法的有效性。
1波阻抗反演模型
地震波阻抗反演是利用数字化的地震记录信息来反推目的层的岩性特征和储集参数。波阻抗反演的目标函数是非线性的, 如何找到合适的目标函数且能用计算机求解是实现波阻抗反演的关键, 但使用线性反演方法很难获得满意结果。为此, 需要使用非线性优化方法来解决反演问题。地震波阻抗反演就是求取下列目标函数的极值问题。
目标函数:
S=W×R+N
其中N为平衡的白噪音序列, 服从高斯分布;W 为地震子波序列;R为地震反射系数序列;d为地震记录序列。波阻抗反演就是通过上式使E达到最小时的R值[11]。
实际反演中, 要求地震资料具有振幅真值, 波传播过程中的地震信号要完整, 已知信息的提供要充分, 且要求没有有色噪音存在。显然, 现行采集系统是无法满足这些要求的。因此反演结果一般只得到模型参数的估计值, 要提高反演结果的精度和可信度具有相当大的难度, 为此很多地球物理工作者做了大量的研究工作, 如广义线性反演等方法, 取得了较好的效果[12]。近年来各种最优化方法引入到波阻抗反演中, 各种各样的优化算法相继出现, 在解决计算精度的同时提高算法收敛速度, 减少反演的多解性, 取得了卓有成效的效果。从Rothman最先提出利用模拟退火方法进行自动剩余校正问题, Stoffa等人研究利用遗传算法进行地震波形的非线性多参数反演, 以及利用人工神经网络技术进行地震波形参数反演等。尽管如此, 波阻抗反演方法仍然存在诸多不足之处, 如算法复杂、实现困难、抗干扰能力差、收敛速度慢等, 因此仍需要对其进行不断改进。
2粒子群算法和免疫克隆算法
2.1粒子群算法
PSO是一种基于群体的优化算法, 群体中每个粒子表示问题的一个可行解, 并具有与目标函数相关的适应度值。粒子在搜索空间中以一定的速度飞行, 并根据自身的飞行经验以及当前最优粒子的状态对速度进行动态调整, 个体之间通过协作与竞争, 实现对问题最优解的搜索。
设在n维搜索空间中, 由m个粒子组成种群X={x1, xi, xm}, 其中第i个粒子位置为xi= (xi1, xi2, …, xin) T, 速度为vi= (vi1, vi2, …, vin) T。粒子i经历的最好位置记作pi= (pi1, pi2, …, pin) T, 整个粒子群经历的最好位置记作pg= (pg1, pg2, …, pgn) T, 粒子xi将按式 (2) 、式 (3) 改变速度和位置:
v
x
式 (2) 主要通过三部分来更新粒子i的速度:粒子i前一时刻的速度;粒子i的当前位置与其最好位置之间的距离;粒子i的当前位置与群体最好位置之间的距离。粒子i通过式 (3) 更新位置坐标。粒子i通过式 (2) 、式 (3) 决定下一步的运动位置。每个粒子都通过pi和pg这两个极值的不断更新, 产生新一代群体, 不停地迭代从而达到寻优的目的。粒子群优化算法需要用户确定的参数并不多, 而且操作简单, 故使用比较方便。但是它的缺点是易陷入局部极值点, 搜索精度不高, 进化后期收敛速度慢。在此, 本文以粒子群优化算法的进化大框架为基础, 结合克隆选择算法, 提出了以下的自适应免疫克隆粒子群优化算法。
2.2免疫克隆算法
免疫算法是一种确定性和随机性选择相统一, 并具有勘测与开采能力的启发式随机搜索算法。其被认为是对自然免疫系统中体液免疫的简单模拟, 这种应答过程通过抗体学习抗原来完成, 克隆选择使亲和力较高的抗体被确定性地选择参与进化;细胞克隆使亲和力较高的抗体依据其亲和力繁殖克隆, 其中部分克隆作为记忆细胞更新记忆池, 即记忆细胞演化, 其余克隆参与进化;亲和突变使克隆依据其母体的亲和力按可变概率进行变异;克隆抑制消除相同、相似及亲和力低的克隆。在人工免疫系统中, 克隆选择是由亲合度诱导的抗体随机映射, 抗体群的状态转移可表示成:
依据抗体与抗原的亲合度f (*) , 解空间中的一个点ai (k) ∈A (k) 分裂成了qi个相同的点a′i (k) ∈A′ (k) , 经过变异和选择后获得新的抗体群。免疫克隆的实质是在一代进化中, 在候选解附近, 根据亲合度大小, 产生一个变异解的群体, 扩大了搜索范围, 从而有助于防止进化早熟和搜索陷于局部极小值。根据Brunet的克隆选择学说原理, 前人提出基本的克隆选择算法, 算法的步骤如下:
1) 初始化抗体种群A (0) , 设定算法参数, 计算初始种群的亲和度;
2) 选择n个与抗原具有较高亲和度的个体, 并生成临时克隆种群, 克隆的数量与其亲和度成正比;
3) 对临时克隆种群进行高频变异, 高频变异的程度与抗体—抗原的亲和度成反比;
4) 在变异后的群体中选择对抗原具有最高亲和度的个体, 不被选择的个体则被替换;
5) 用选择出的抗体群替代原抗体群, 亲和度低的个体被淘汰。
生物的免疫克隆机制保证了系统抗体的多样性, 使系统有选择地产生能够与抗原最具反应的抗体克隆变异, 从而产生抗体的多样性样本。在这一指导思想下形成的免疫算法, 可最大程度上避免陷入局部极值, 快速收敛于全局极值[13]。
2.3自适应免疫克隆粒子群算法 (AICPSO)
2.3.1 个体置换算子和自适应变异算子
为了提高PSO算法摆脱局部极值的能力, 文中构造了个体置换算子, 在当PSO算法连续一定的代数, 群体中没有出现更优个体即已经陷入局部最优时, 选取一定数量的个体用随机生成的个体进行置换, 从而保持了种群的多样性而跳出局部最优。其中适应值越低、浓度越高的个体被置换的概率越高, 为此定义了以下的个体置换概率。
定义1 个体置换概率 第i个个体的置换概率Ri由个体本身的浓度概率Ric和第M-i个个体的适应度概率R (M-i) f (M是种群规模) 决定, 具体:
Ri=αR (m-i) f+ (1-α) Ric 0≤α≤1
Rif=fi∑fi (4)
其中fi是个体i的适应值,
另外, 为避免进化过程中由大量相同抗体引起的算法退化现象, 根据记忆库和抗体群不同的特性, 采用自适应变异算子更新记忆库, 而依据抗体浓度和亲和度更新下一代抗体群体。在更新记忆库时, 考虑到粒子在当前全局最优个体的作用下可能发现更好的位置, 因此AICPSO算法将变异操作设计成一个随机自适应变异算子[14], 即对满足变异条件的个体按一定概率pm进行变异。
定义2 自适应变异概率 对满足变异条件的个体按概率pm变异, pm的计算公式如下:
其中k可取[0.1, 0.2]之间的任意数值, σ2是群体适应度方差, η是服从Gauss (0 , 1) 分布的随机变量。其中σ2可以定义为:
其中n为粒子数目, fi为第i个粒子的适应度, favg为粒子群的平均适应度。
2.3.2 算法流程
根据地震波阻抗反演的特点, 结合自适应免疫克隆粒子群算法反演的基本思想, 可以设置下列具体步骤。
Step1 将待优化的目标函数视为抗原, 则目标函数可以表示为测量数据估算可信度项和先验项的和, 即式 (1) 所示的目标函数;
Step2 根据问题的复杂性来确定种群的大小, 在波阻抗反演问题中, 将种群根据待解问题生成初始粒子群, 规定种群规模为M;
Step3 计算各粒子的适应度函数值, 更新局部极值点pi和全局极值点pg;
Step4 判断如果满足最大迭代次数, 则此时pg就是所求解;否则, 继续;
Step5 根据式 (2) 和 (3) 产生下一代种群;
Step6 重新计算各粒子的适应度函数值, 选取最好的m个局部极值点pi组成记忆库;
Step7 将抗体群中的m个pi按亲和度降序排列, 按1:7:2规模分解成3个子种群, 即最高亲和度Ah (g) 、中等亲和度Am (g) 以及最低亲和度Al (g) ;
Step8 对于最高亲和度Ah (g) , 按与亲和度成正比进行克隆, 克隆数为:
αi=β× (n+i)
其中, i为按亲和度排序的序号, β为[0, 1]之间的克隆常数, n为种群规模。
对于最低亲和度Al (g) 按比例λ重新进行初始化, λ为与种群规模相关的常数;
Step9 对克隆后的抗体执行变异操作。对于最高亲和度Ah (g) , 进行如下小幅变异操作:
其中δ为[0, 1]之间的随机数列向量;
对于中等亲和度Am (g) 进行与最高亲和度Ah (g) 交叉操作以产生新的抗体;
Step10 重新计算变异后的抗体亲和度和抗体浓度, 根据抗体亲和度和抗体浓度更新抗体群体。对记忆集中的个体按式 (5) 自适应变异算子操作进行更新;
Step11 判断与最优值的误差是否在允许范围内, 如是则提前终止算法。否则如果连续一定的代数, 群体中pg没有变得更优, 则按照式 (4) 个体置换概率选择一定比例的个体由随机生成的个体替换, 转Step3, 否则直接转Step3。
2.4仿真测试
为了验证算法的收敛性能, 下面将通过三个典型函数优化问题 (求解最小值) 来对本文提出的算法进行测试, 同时与基本PSO算法进行比较。Rosenbrock函数是很难极小化的病态单峰二次函数, Rastrigin函数和Griewank函数为多峰函数。
(1) Rosenbrock函数:
(2) Rastrigrin函数:
(3) Griewank函数:
为了评价不同算法的优劣, 采用如下评估指标[13]:①平均迭代次数Itavg:M次试验所得函数值的算术平均值;②最大迭代次数Itmax;③最小迭代次数Itmin。
仿真实验时函数的寻优精度分别设为10-4, 10-6, 10-4, 初始群体数m=50, 通过100次的重复仿真实验, 采用PSO、APSO (自适应粒子群算法) 、AICPSO三种算法搜索全局极值时所需要的迭代次数进行对比, 结果如表1所示。由对比结果可知, AICPSO算法的全局搜索能力明显提高[15,16]。
AICPSO算法将初始群体按其亲和度分为高亲和度、中等亲和度和低亲和度三类不同抗体, 计算过程中根据亲和度不同对抗体进行克隆操作, 并且淘汰亲和度差的抗体, 这样不仅可以保持种群多样性而且大大减少了计算量。在更新抗体记忆库和下一代群体的过程中, 采用两套不同的更新机制。其中采用自适应变异算子更新记忆库, 而依据抗体浓度更新下一代群体, 从而避免了由大量相同抗体而导致的算法退化现象。
3理论模型与实际资料反演
3.1理论模型分析
为了检验AICPSO反演算法, 首先选用主频为35Hz的零相位ricker子波做合成地震记录剖面 (如图1所示) , 然后对合成地震记录用AICPSO算法进行波阻抗反演, 得到波阻抗反演剖面 (如图2所示) 。经计算, 反演前后地震记录曲线的能量相对误差不足0.23%, 而相关系数达到99.63 %。
为了检测AICPSO算法对随机噪声的抗干扰能力, 本文又设计了三个不同的初始模型, 并附加了0、15 %和30%三种情形的噪声作对比。从表2和图3不同初始模型和不同噪声水平的反演结果可以看出, 对不同的初始模型, 反演结果均能较好地反映真实模型, 说明AICPSO反演方法对初始模型的选取无严格要求, 是一种全局收敛的反演方法;随着噪声的增加, ACMPSO反演结果精度明显高于PSO。因此, AICPSO方法相对于PSO方法存在一定的优越性。
3.2实际资料反演
对山东某探区测井资料进行AICPSO反演。首先除去声波测井时差曲线中明显的异常值, 将校正后的声波测井时差数据进行时深转换, 求得速度值后乘以密度值得到测井波阻抗值, 并根据频谱分析确定的震源子波作合成记录;最后给定反演的初始波阻抗值, 采用同样的子波使用AICPSO和PSO方法分别进行反演。
表3是三个不同初始模型和噪声的AICPSO和PSO的计算结果。由表3可以看出, AICPSO在性能和效率上要优于PSO。初始模型即使在30%噪声情况下, AICPSO搜索421670次, 最终误差0.01106;而PSO需搜索3422100次, 最终误差0.04619;在15%噪声或无噪声的情况下, 其优势也相当明显。
4结论
本文通过分析粒子群优化、免疫克隆算法和求解波阻抗反演问题存在的缺陷, 提出了一种自适应免疫克隆粒子群优化算法。该算法根据亲和度不同对抗体进行分类, 并对其进行相应不同的操作从而保持了种群多样性而且大大减少了计算量;通过引入免疫机制, 根据个体浓度和适应值概率定义了个体置换算子, 能够避免粒子群算法陷于局部极值。为避免由进化过程中大量相同抗体引起的算法退化现象, 根据记忆库和抗体群不同的特性, 采用自适应变异算子更新记忆库, 而依据抗体浓度和亲和度更新下一代抗体群体。经数值模拟和实际波阻抗资料反演表明, 该算法不依赖于初始模型, 收敛速度快且结果可靠。免疫粒子群优化算法为解决地震波阻抗反演问题提供了一条可行途径。
