（机械制造及其自动化专业论文）基于遗传编程的可持续性模拟退火算法建模及应用实现.pdf

贵州大学硕士研究生学位论文 摘要 基于遗传编程的可持续性模拟退火算法 建模及应用实现 摘要 本文在研究分析标准模拟退火算法在可持续性进化方面的缺陷基础之上，受 生物进化中公平竞争模式的启发，引入了可持续进化算法模型一h f c 模型，提 出了一种新的可持续的模拟退火算法一h f c s a 。h f c 模型将种群中的个体按 适应度值分成不同的等级并且各个等级单独进化，此外h f c 模型中以输入、输 出阀值来控制各等级中个体的迁移。该模型将传统收敛进化计算模型转换为可持 续搜索模型，缓解了进化算法局部收敛的问题，保证了种群的多样性。通过结合 h f c 模型，h f c s a 算法不仅保存模拟退火算法全局最优的搜索特性，而且改进 了搜索的可持续性。在用h f c s a 算法、遗传算法( g a ) 和模拟退火算法( s a ) 在相同条件下求解4 8 城市旅行商问题的对比实验中，搜索结果表明h f c s a 在 搜索的结果和可持续性上优于g a 和s a 。在帮助贵阳医学院设计医学实验时间 安排这种带约束的优化的问题上，h f c s a 算法也可以很好的设计出合理的方案。 虽然h f c s a 算法在我们的对比实验中表现出了较g a 和s a 有搜索结果和 可持续性的优势，并在应用设计中体现了良好的应用设计能力。但是，和其它两 种算法一样，h f c s a 也存在着编码的局限，只能进化数据，无法进行结构和参 数的同时进化，这个缺陷是由s a 算法与生俱来的搜索机制决定的，主要是算法 的算子无法对结构和参数的编码同时等价操作。众所周知，工程领域的很多优化 设计问题都需要参数和结构协同优化，s a 的这种编码方式大大限制了它们解决 协同搜索的能力，使它们的应用范围受到限制。因此，在进一步的研究中，我们 寻求解决这个问题，引入了遗传编程( g p ) 的思想提出了基于遗传编程的h f c s a 算法。g p - h f c s a 算法借鉴遗传编程的树形编码，将结构和参数混合编入g p 树 中，这样，随着g p 树的生长，参数和结构实现了同时进化，并用g p - h f c s a 算 法和参考算法在相同条件下解决8 特征值放置问题做对比，通过连续随机运行 2 0 次的统计结果看出，g p - h f c s a 算法的平均搜索效果要优于参照算法。 最后，我们用g p - h f c s a 算法做了无源滤波器的设计实验，即用g p h f c s a 算法来设计与目标无源滤波器功能类似的滤波器。实验中，设计出的无源滤波器 功能比较接近目标。这表明：g p h f c s a 算法可以实现电路设计这种需要结构和 参数同时进化的设计，将来可以应用到复杂的多域动态系统设计，具有广泛的应 用前景。 关键词；模拟退火算法；分等级搜索；h f c 模型；遗传编程：可持续进化； 模拟滤波器自动设计 贵州人学硕士研究生学位论文 a b s t r a c t m o d e l i n ga n da p p l i c a t i o no f s u s t a i n a b l es i m u l a t e d a n n e a l i n ga l g o r i t h mb a s e do ng p a b s t r a c t t h i sp a p e rp r o p o s e dt h es u s t a i n a b l es i m u l a t e da n n e a l i n ga l g o r i t h m - h f c s a ( s i m u l a t e da n n e a l i n ga l g o r i t h mb a s e do nh i e r a r c h i c a lf a i rc o m p e t i t i o nm o d e l ) w h i c hi m p r o v e st h ef l a w so fs t a n d a r ds i m u l a t e da n n e a l i n ga l g o r i t h m i n s p i r e db yt h e f a i rc o m p e t i t i o np r i n c i p l ei nb i o l o g i cs y s t e m s ，t h eh f cm o d e li si n t r o d u c e d i nt h e h f cm o d e l ，t h ei n d i v i d u a la r ed i v i d e di n t os e v e r a lf i t n e s sg r a d e sb yd i f f e r e n tf i t n e s s a n dk e e pe v o l u t i o ng o i n ga ta l lf i t n e s sg r a d e s a n dt h e r ea r et h ea d m i s s i o nt h r e s h o l d a n do u t p u tt h r e s h o l dt oc o n t r o lt h em o v e m e n to fi n d i v i d u a l sb e t w e e nt w og r a d e s h f ct r a n s f o r m st h ec o n v e n t i o n a lc o n v e r g e n te v o l u t i o n a r yc o m p u t a t i o nm o d e li n t oa s u s t a i n a b l es e a r c hf r a m e w o r k c o m b i n e dw i t hh f cm o d e l ，h f c s ac a nn o to n l y r e t a i nt h eg l o b a ls e a r c ha b i l i t y , b u ta l s or e l i e v et h ep r o b l e mo f p r e m a t u r ec o n v e 唱e n c e a n de n s u r et h ed i v e r s i t yo fp o p u l a t i o n i no u rc o m p a r i s o ne x p e r i m e n t ，h f c s aw a s b e t t e rt h a ng aa n ds ai nr e s u l ta n ds u s t a i n a b i l i t yo f s e a r c h i nt h ed e s i g na p p l i c a t i o n a r r a n g et h et i m es o l u t i o nf o rm e d i c a le x p e r i m e n t ，w h i c hi sac o n s t r a i n e do p t i m i z a t i o n p r o b l e m ，h f c s ad i dag o o dj o ba n dd e s i g n e dar e a s o n a b l et i m es o l u t i o n b u t , t h ee n c o d i n gm e t h o do fh f c s aa l g o r i t h mi ss i m p l ew h i c hi ss i m i l a rt og a a n ds a t h e yo n l yc o d es t r u c t u r eo rp a r a m e t e rr e s p e c t i v e l yw h i c hc o n s t r a i n st h e i r a p p l i c a t i o nf i e l d i no r d e rt oi m p r o v et h el i m i to fs i m p l ee n c o d i n gm e t h o d ，w e i n t r o d u c e dt h ed a t as t r u c t u r eo fg e n e t i cp r o g r a m m i n g ( g p ) w h i c hm i xs t r u c t u r ea n d p a r a m e t e r si n t og pt r e e ，a n d ，p r o p o s e da ni m p r o v e da l g o r i t h m - h f c s aa l g o r i t h m b a s e do ng p ( g p h f c s a ) t i l i si m p r o v e da l g o r i t h mc a ne v o l v es t r u c t u r ea n d p a r a m e t e ra tt h es a m et i m ew i t lt h eg r o w i n go fg p t r e e i n t h i s p a p e r , w ed e s c r i b et h ea l g o r i t h mp r o c e s so fh f c s aa l g o r i t h ma n d g p h f c s aa l g o r i t h mi nd e t a i l f i n a l l y , t h ep a p e rp r o v e st h ef e a s i b i l i t yo fh f c s a a l g o r i t h ma n dg p h f c s aa l g o r i t h mb yt h e8 - e i g e n v a l u ep r o b l e m a l s o ，w et r i e dt h e a n a l o gf i l t e rs y n t h e s i s w i t hg p h f c s aa l g o r i t h m t h er e s e a r c hs h o w e dt h a t g p - h f c s aa l g o r i t h mc a ns e a r c hs t r u c t u r ea n dp a r a m e t e ra tt h es a m et i m ei n o p e n e n d e dw a y i nt h ef u t u r e ，g p h f c s aa l g o r i t h mw i l ls o l v es o m ec o m p l i c a t e d d e s i g np r o b l e m ss u c ha sm u l t i d o m a i nd y n a m i cs y s t e m k e yw o r d s ：s i m u l a t e da n n e a l i n ga l g o r i t h m ；h i e r a r c h i c a l s e a r c h ；h f cm o d e l ； g e n e t i cp r o g r a m m i n g ；s u s t a i n a b l ee v o l u t i o n ；a n a l o gf i l t e ra u t o m a t e dd e s i g n 贵州1 人学硕士研究t i 学位论文 附录四：学位论文原创性声明和关于学位论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究在做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律责任由本人承担。 论文作者签名： 埠 日 期：2 q q 蒸生篁旦 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权贵州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作槲：埠抽签雄咖进血 贵州大学硕士研究生学位论文 第一母绪论 第一章绪论 1 1 课题来源 本课题是李少波老师主持承担的国家自然科学基金项目“基于进化遗传编程 的机电系统自动化创新设计研究”( 5 0 5 7 5 0 4 7 ) 的子课题之一。 1 2 课题研究的目标及意义 宇宙中的万事万物和谐而美妙的并存，物体内部种种奇妙的现象一直是科学 家关注和探索的焦点，近年来，各种仿照自然界中物理现象的算法层出不穷，模 拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m s ，简称s a ) 就是其中之一。 模拟退火算法是一种用于求解大规模优化问题的随机搜索算法，它以优化问 题求解过程与物理系统退火过程之间的相似性为基础：优化的目标函数相当于金 属的内能；优化问题的自变量组合状态空间相当于金属的内能状态空间：问题的 求解过程就是找个组合状态，使目标函数值最小。利用m e t r o p o l i s 准则并适当 地控制温度的下降过程实现模拟退火，从而达到在多项式时间内求解全局优化问 题的目标，是基于蒙特卡罗( m o n t ec a r l o ) 迭代求解法的一种启发式随机搜索方 法。 模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m s ) 有其独特的地方。由于它 具有全局优化性能，鲁棒性强，通用性强且适于并行处理的优点，成为现代启发 式算法下的一个重要分支，具有极强的生命力，它被广泛的应用于各种优化设计 中，尤其在n p 问题中表现出色。t a i y u ew a n g 等人【5 7 l 曾以无等待流水线( n o - w a i t f l o w - s h o p ) 问题为例研究了s a 和g a 在解决n p h a r d 问题时的性能比较，得出 结论：在同样条件下，s a 的解得质量和计算效率均优于g a ( 资源有限的情况下) 。 模拟退火算法不仅具有现在启发式算法的种种优点，而且由于它采用的接受准则 是m e t r o p 0 1 i s 准则，从而保证了其算法的突跳性，使其不被陷于局部最优解的“早 熟( p r e m a t u r ec o n v e r g e n c e ) ”困境中，因而在多目标优化过程中表现出色。 基于遗传编程的可持续性模拟退火算法的研究将为现代机电产品系统化的 创新设计提供一种系统化的手段。本方法的优点在于其开放式的结构搜索，以及 同时进行的参数优化搜索。这种基于进化计算和系统仿真的自动设计方法给传统 贵州大学硕士研究生学位论文 第一章绪论 的机电系统的创新设计提供了新的思路，同时对改进各种现有设计方案也具有广 泛的应用潜力。这一课题的研究将填补国内的研究空白，研究产生的基于进化计 算的设计理论、方法和原型系统将促进其它工程系统的设计，具有深远的学术价 值及应用意义。 1 3 国内外研究现状 1 3 1 标准的模拟退火算法( s a ) 模拟退火的思想最早由k i r k p a t r i c k 等人提出，并于19 8 3 年成功地应用在组合 优化的问题上，此算法克服了爬山法( h c ) 极易陷入局部解的缺点。 s a 算法是基于固体退火原理，此原理的主要思想是：将固体加温至充分高， 再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐 冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能 减为最小。s a 算法思想正是源于此。根据m e t r o p o l i s 准则，粒子在温度t 时趋 于平衡的概率为e a e ( k t ) ，其中e 为温度t 时的内能，e 为其改变量，k 为伯 茨曼( b o l t z m a n n ) 常数。用国体退火模拟组合优化问题，将内能e 模拟为目标 函数值c 温度t 演化成控制参数t ，即得到解组合优化问题的模拟退火算法： 由初始解i 和控制参数初值t 开始，对当前解重复“产生新解_ 计算目标函数差_ 接受或舍弃”的迭代，并逐步衰减t 值，算法终止时的当前解即为所得近似最优 解，这是基于蒙特卡罗( m o n t ec a r l o ) 迭代求解法的一种启发式随机搜索过程。 退火过程由冷却进度表( c o o l i n gs c h e d u l e ) 控制，包括控制参数的初值t 及其衰减 因子t 、每个t 值时的迭代次数l 和停止条件s 。简而言之，s a 算法的伪程序 如下： 表1 1s a 算法伪码 2 贵州大学硕士研究牛学位论文 第一章绪论 由以上原理可知，模拟退火算法与初始值无关，算法求得的解与初始解状态 s ( 是算法迭代的起点) 无关；模拟退火算法具有渐近收敛性，并且已在理论上被 证明是一种以概率i 收敛于全局最优解的全局优化算法；模拟退火算法具有并行 性。下表是关于s a 算法性能的研究现状。 表1 2s a 算法性能的研究现状 研究的性能研究的情况 收敛性 m i t r a 5 2 1 ，h a j e k1 4 0 1 证明了在退温函数满足一定的条件下，s a 以概率为1 收敛剑全局最优。 收敛速度很慢。( m i t r a 对此作过研究【5 2 1 ) 鲁棒性 王凌等2 1 以f l o w - s h o p 为例研究了s a 的初值鲁棒性。 参数或策略a d a rak a l i r 等f 2 9 1 研究了初始解和统治规则( d o m i n a n c er u l e s ) 对算法的影在s a 中的作用。并应用到并行处理器调度问题上得到结论： 响 初始解越优，最终解也越优；当统治规则包含在s a 系统早期 的实验中，并且并行的确定最优的s a 参数值时，可以找到进 一步的改进解。王凌等1 2 7 以f l o w s h o p 为例研究了s a 的初始温 度，退温速度，邻域结构和初始状态对s a 算法的影响。 适应性 l e o n i l d er o c h av a r e l a 等f 4 9 】利用r i b e i r o 和m o u r a p i r e s ( 19 9 9 年) 提出的模糊方法( f u z z i f i c a t i o n m e t h o d ) 测试了s a 在解决 模糊优化问题时的灵活性和适应性。 解的质量和 t a i y u ew a n g 等【5 7 】以2 到3 部机器无等待流水线( n o w a i t 计算效率 f l o w - s h o p ) 问题为例研究了s a 和g a 在解决n p - h a r d 问题时 的性能比较，得出结论：在同样条件下，s a 的解得质量和计 贵州大学硕士研究生学位论文第一章绪论 算效率均优于g a ，此研究只适于有限的资源情况。 选择参数的要求初始温度足够高，每一温度下的抽样数足够多，终止温度 方法 足够小。对此，p a r k 等提出非线性规划确定s a 最优参数。 尽管现在产生了很多改进的s a 算法都来源于热力学退火理论，但它们的产 生有其不同的研究背景。这些不同导致了各种算法关于各种操作算子的描述有其 不同的特点。而这些特点完善了s a 算法并推动了持续s a 算法的发展。 1 3 2 并行模拟退火算法( p a r a l l e ls a ) 由于并行计算可以大大提高算法的计算效率，而且s a 算法的并行改造也相 对容易，近年来并行的s a 算法( 简称：p s a ) 得到很大发展。目前常见的有以下 几种策略：操作并行策略；试验并行策略；区域分裂策略和混乱松弛策略。这几 种并行策略在不同程度上对解的质量和收敛速度较s a 更优。国外对p s a 的相 关研究主要有：k i md o n g - w o n 等【4 5 】将s a 在不相关的并行机上解决一种调度问 题。n w a n av 等1 5 3 1 提出一种基于m i p s a 的合作并行启发式算法，它结合 b & b ( b r a n c ha n db o u n d ) 和s a ，并通过并行计算来解决广义的一类整数规划0 p ) 问题。c h a n d yj o h n 和k i ms u n g h o l 3 4 j 研究了将p s a 算法在特定的t i m b e r w o r l f s c 排序工具上进行标准的细胞排序，并对其进行评价。g a l l e g o 等【3 9 】提出一种用来 解决长期传j 差( 1 0 n gt e r mt r a n s m i s s i o n ) 网络扩展的计划问题的p s a 算法。l e e s o o - y o u n g 掣5 0 j 提出一种多条m a r k o v 链的同步和异步的p s a 算法。这种算法允 许能互相通信的工作单元同时追踪多条m a r k o v 链，且重点研究在算法中实现： 同步和异步；s a 的并行和用来检查m a r k o v 链的途径。p rm c m u l l e n 等【5 4 】将 s a 算法运行在并行工作站上来解决多目标装配线平衡问题。s a n j a y r a d h a k r i s h n a n 等1 5 6 】将s a 用到并行机上调度p e t n d d s p 问题。k h a l i ls h i n d i 等 h 6 j 将s a 改进到并行机上解决线性的退化工作调度问题等。 国内对p s a 的相关研究主要有：c h i n y a ol o w 等【岁7 】提出一种多步( m u l t i s t a g e ) 启发式s a 算法，通过各不相关的并行机来解决f l o w - s h o p 调度问题。高齐圣等【2 3 】 针对参数设计中的一类非线性规划问题，基于均匀设计的思想，提出一种全局优 化的p s a 算法。李树有等f 4 】利用高性能并行超级计算机系统t h n p s c 1 成功实 现了s a 算法的并行计算，并将其应用于会聚束电子衍射，俄歇电子能源等实验 数据的分析中，取得了以往实验数据分析方法无法获得的定量数据。明廷锋等1 1 6 】 4 贵州大学硕士研究生学位论文 第一章绪论 提出一种用于故障识别的并行组合模拟退火算法( p r s a ) 。李晓莉等 1 9 1 提出一种 利用统计思想的并行计算方案。张德富等【9 】提出一种基于s a 算法的解决t s p 问 题的并行算法，并在t r a n s p u t e r 多处理机上实现等。 下面以经典的t s p 问题来阐述p s a 算法主要思想：在p s a 中，算法首先由 初始化过程随机产生k 个规模为n 的进化种群，并计算种群中每个解的目标函 数值，将每个种群中的最优解保存后由状态产生函数在每个解的领域结构内产生 k n 个候选解，并计算候选解的目标函数值。若候选解的目标函数值大于当前解 则取代之，否则根据接受准则判断是否接受。这样形成了新一代种群。若k 个 新种群中有优于原历史最优解的个体则保留该个体。随后继续重复抽样过程直到 当前温度下的抽样稳定后进行退温操作，当温度低于某个终止温度时算法结束。 再从k 个种群最优解中选出一个最优解作为最终得到的全局最优解。 表1 3 描述并行模拟退火算法的步骤： s l ：初始化：设置控制参数，产生k 个规模为n 的种群； s 2 ：计算每个解的目标函数值并保留各种群的最优解； s 3 ：w h i l e ( t t e ) t e 为终止温度 s 3 1 ：w h i l e ( 抽样过程未达到稳定) s 3 1 1 ：f o r ( i = l ；i l 。较大的 t l 允许接受较大量的“劣化解”，试图搜索跳出可能的局部最优解陷井，而较小 的t s 可加速搜索最优解。如果m a x ( n l ，n s ) n ( i ) ，产生较大的t l ，令t ( i + 1 ) = t l ，t ( i + 2 ) = t ( i + 1 ) ，目的是增加搜索力度。如果m a x ( n l ，n s ) n s ， t ( i + 1 ) = lo 5 幸( t i + t s ) ，i f n l = n s ， 自适应退火策略确定的参数序列 t i 保证每个温度砸不为零，当n ( i 户 n ( 卜l 即或n ( i ) n ( - 1 ) ，参数t i 允许分别采用较大值t l 和较小值t s 当 m a x ( n l ，n s ) o 时最优解还没有出现) ，目前已经 出现了一些措施或方法来改进算法的可持续性。刘岩等【3 】提出一种带有单调升 温过程的s 卜m t r s a 算法。但是，此算法引入升温过程后带来的局部极小点 判断、升温时机判定、升温i 幅度判定等类似于s a 的定参过程的问题目前尚无成 熟的方法。还有一些方法通过改进冷却表来控制退火的速度，以此来缓解t 过 早收敛于0 ，但是仍然不能取得很好的结果。而且，在降温中对温度进行调整， 使得个体退化时的接受概率e x p ( a t 7 厂1 d 受到影响，判断个体接受的准则不再严格 公正。 通过上面的分析我们发现：如果s a 算法可以平稳持续地进行搜索，有些问 题可以得到一定程度上地缓解。然而，s a 自身对温度参数的依赖使得温度函数 需要保持单调递减以吻合m e t r o p o l i s 接受准则，进而保持s a 的全局优化性。所 以单一地从s a 内部调整相关参数或环境并不能得到满意的结果。考虑了以上因 素，我们引入了一种分等级搜索的可持续性算法模型h f c ( 分等级公平竞争) 模型，从外部将s a 进行可持续性的改进，提出一种改进的s a 算法，该算法不 仅保留了模拟退火算法的优点，而且还具有可持续的搜索能力。 2 1 标准模拟退火算法及其缺陷 2 1 1 算法描述 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 基本算法步 骤如下： ( 1 ) 初始化：初始温度t ( 充分大) ，初始解状态s ( 是算法迭代的起点) ， 每个 t 值的迭代次数l ( 2 ) 对k = l ，l 做第( 3 ) 至第6 步： ( 3 ) 产生新解s ( 4 ) 计算增量a t7 = c ( s7 ) - c ( s ) ，其中c ( s ) 为评价函数 ( 5 ) 若t 7 0 ，然后转第2 步。 其中模拟退火算法新解的产生和接受可分为如下四个具体步骤： ( 1 ) 由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计 算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的 方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变 换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 ( 2 ) 计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生， 所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计 算目标函数差的最快方法。 ( 3 ) 判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是 m e t r o p 0 1 i s 准则：若t o 时，退火就结束，算法即终止， 此过程对s a 算法的可持续性造成很大障碍。这种障碍是s a 自身的结构造成的。 为了阻止退火过程不在最优解出现前就结束( 即t - 0 时最优解还没有出现) ，目 前已经出现了一些措施或方法来改进算法的刊持续性。刘岩等1 3 】提出一种带有单 调升温过程的s a m t r s a 算法。但是，此算法引入升温过程后带来的局部极 小点判断、升温时机判定、升温幅度判定等类似于s a 的定参过程的问题目前尚 无成熟的方法。还有一些方法通过改进冷却表来控制退火的速度，以此来缓解t 过旱收敛于0 ，但是仍然不能取得很好的结果。而且，在降温中对温度进行调整， 使得个体退化时的接受概率e x p ( a t t ) 受到影响，判断个体接受的准则不再严格 公正。 通过上面的分析我们发现：如果s a 算法可以平稳持续地进行搜索，有些问 题可以得到一定程度上地缓解。然而，s a 自身对温度参数的依赖使得温度函数 需要保持单调递减以吻合m e t r o p o l i s 接受准则，进而保持s a 的全局优化性。所 以单一地从s a 内部调整相关参数或环境并不能得到满意的结果。考虑了以上因 素，我们引入了一种分等级搜索的可持续性算法模型岍c ( 分等级公平竞争) 模型，从外部将s a 进行可持续性的改进，提出一种改进的s a 算法，该算法不 仅保留了模拟退火算法的优点，而且还具有可持续的搜索能力。 2 2h f c 模型 h f c 模型1 由胡建军博士提出，它来源于对生物种群中分等级进化过程的 模拟。同一物种中适应能力相近的个体之间竞争；适应性很低的个体不会参加适 应性高的个体之间的竞争，这样不仅保存了物种内部的多样性，而且还让有些优 秀的“家族”不会因为进化初期的表现不佳而被过早淘汰出局。此模型已经成功的 与g a 结合，并在天线设置问题上表现出色。 2 2 1h f c 模型的基本结构 h f c 模型中包括下面三个相互依赖的部分： ( 1 ) 通过设立适应值梯度来分等级组织个体 贵州人学硕士研究卫：学位论文第二章基于分等级搜索的可持续性模拟退火算法研究 典型的遗传算法搜索过程由于群体处于绝对的选择压力下，只有更好的群体 才能生存下来，因此导致了群体的平均适应性不断的增加直到停滞为止。在以后 的进化阶段，适应能力低的个体很难生存下去，从而导致过早收敛。因此，为了 让进化算法更好地实现可持续性，在h f c 模型中按适应度值建立了适应度等级。 个体被分成一系列不同适应度等级，每个等级内部独立地进行进化操作。 ( 2 ) 随机个体生成器：母体的来源 在典型的遗传算法进化过程中，必须依靠巨大的种群数量来提供和保护种群 的多样性，以使问题空问得到充分的搜索，但是太大的种群数量会阻碍进化算法 的运行速度。为了解决典型的遗传算法进化过程中的这一缺陷，h f c 模型中加 入了随机个体生成器，它能随机的产生低适应度的个体，以确保种群的多样性。 图2 1h f c 模型的算法运算流程 ( 3 ) 从低适应度等级到高适应度等级的移动策略 在h f c 模型中建立了一种移动策略，这种移动策略保证了具有高适应度值 的个体能够适时从低适应度等级向高适应度等级移动，以替换一些被淘汰的低适 1 6 贵州大学硕士研究生学位论文第二章暴下分等级搜索的可持续性模拟退火算法研究 应度值个体。在h f c 方法中，个体的迁移仅仅是单方向的从低适应度等级移向。 高适应度等级，但迁移可以是跨级进行。原因是避免在低等级中种群被退化的个 体所占据。 2 2 2h f c 模型的特点 h f c 模型有以下特点1 1 5 】： ( 1 ) h f c 模型根据个体适应性分等级地组织成多样性群体。个体的竞争是 在同级之间进行的。 ( 2 ) h f c 模型中个体的交换是单方向的，在等级交换结构中允许个体从低 适应性群体向高适应性群体移动。 ( 3 ) h f c 模型中不同适应性水平群体的进化平衡被维持。低适应性群体往 往探索新的搜索领域并将它们的后代送往更高适应性的群体进行进一步的进化。 ( 4 ) 在h f c 模型的每个群体中，搜索强度能被独立的控制。因此，相对于 传统的模型，h f c 模型被认为是在竖直方向而不是在水平方向维持多群体环境。 ( 5 ) h f c 模型中，在不会消除低适应性个体的前提下维持大量的高适应性 个体。这样未来的新搜索领域才能维持长久的最优解探索，而不会出现早熟现象。 ( 6 ) 当低适应性个体能持续进行彻底地搜索时，一旦它们产生高适应性的 后代，后代会立即进入高适应性水平，来完成和其它的高适应性个体的重组。这 保证了同水平情况下的公平竞争。 ( 7 ) 在低适应性群体中随机地插入新的个体，以帮助探索新的搜索领域， 并减少搜索陷入局部最优解的可能。 ( 8 ) 在h f c 模型中，可以认为每个适应性水平的群体是在不断的进化的。 根据群体特征适当的分配搜索能力，称为h f c 模型的自适应性。 ( 9 ) h f c 模型可以和当前的其它技术兼容，来改善进化算法的搜索能力。 2 3 基于h f c 模型的可持续模拟退火算法一h f c s a 2 3 1 改进标准模拟退火算法的基本思路 利用h f c 模型的分等级搜索机制，为维持不同适应性程度个体的持续搜索能 力，将标准模拟算法做出如下改进； 贵州大学硕士研究尘学位论文第二章基于分等级搜索的可持续性模拟退火算法研究 ( 1 ) 初始解种群产生之后，按照单个初始解的适应性水平将它们分成不同的 等级。适应性高的个体分入高等级，适应性低的个体分入低等级，适应性居中的 个体分入中间等级。 ( 2 ) 把个体分成不同等级保证种群的多样性。在各等级内部对每个个体进行 退火操作( 参照s a ) ，仍然按照m e t r o p o l i s 准则对新个体进行判断。被m e t r o p o j i s 准则接受的个体按照其适应值参与相应等级的竞争，而不受其“父亲”所在等级的 限制。尤其当产生了适应性高的个体时将其输送到高等级进行竞争，以保证同等 级内个体的公平竞争。 ( 3 ) 在低适应性水平增加随机的子代，以拓展新的搜索领域，并保持各种适 应性程度个体的存留，为持续搜索源源不断的提供新的力量。 这样，h - f c 模型避免了搜索过程中丢失种群多样性，维持了不同适应性程度 个体的存在。标准模拟退火算法经过改进后，能有效地对母体空间进行反复搜索。 由于改进后的算法维持了种群多样性和公平竞争的自然规律，使得其在解决实际 问题时更加接近最优值。 2 3 2h f c s a 算法的描述 改进的s a 算法h f c s a 是结合了h f c 模型的一种可持续s a 算法。结 合实验问题的条件，算法描述如下： ( 1 ) 初始化种群x ( j i ) ，此时k - - 0 ，初始温度为t ； ( 2 ) 根据适应性水平，把母体从高到低分成n 个等级，每种等级分别有 n 1 ，n 2 n n 个母体； ( 3 ) 在同等级内部独立地对于m ( f = l 一2 埘) 个母体分别进行，次退火运算，退 火算子可表示为t ：s _ s 是母体空间到个体空间的映射，这样得到下一代种群，t 用降温函数降温次。对于不同的层次将采用不同的退火算子：较低层次的种群 将采用i n v 算子( 在数据串中随机选取2 点，将这2 点之间的数据串逆置) ，而 对于较高层次的种群将采用s w a p 算子( 在数据串中随机选取2 点，将这2 点 的数据交换) ： ( 4 ) 对于新产生的子代，如果它相对其父亲是进化的，则接受此个体；如 果它退化了，则以概率e x p ( a t t k ) 接受它。一旦接受此个体，则将其替换它所 属层次的当前种群中最差的个体。 1 r 贵州人学硕士研究生学位论文第二二章慕于分等级搜索的可持续性模拟退火算法研究 ( 5 ) 检验停止准则。若满足条件则停止，否则k = 后+ j 并返回到( 3 ) ，同时， 在每一代运行完后，系统随机地加入一定数量的低适应性个体到相应等级。 注：1 适应值函数是个体空间s 到正实数空间的映射，即适应值函数- 。为 f ：s - 。2 对于停止准则还未满足，但是t l ( 一) 0 这种情况，则采用刘岩等提 出的一种带有单调升温过程的s a m t r s a 算法吲来处理。 算法的流程图如图2 2 所示： 图2 2 基于h f c 模型的可持续s a 算法运算流程 2 3 3h f c s a 算法的特点 改进后的可持续s a 算法除了具备2 2 2 中总结的h f c 模型分层搜索的各种 特点外，还有以下特点： ( 】) 结合了模拟退火算法的优点，不仅具有现在启发式算法的种种优点， 1 9 贵州大学硕士研究生学位论文第二章麟于分等级搜索的可持续性模拟退火算法研究 而且由于它采用的接受准则是m e t r o p 0 1 i s 准则，从而保证了其算法的突跳性， 使其不被陷于局部最优解的“早熟( p r e m a t u r ec o n v e r g e n c e ) ”困境中。 ( 2 ) 可持续的s a 算法具有渐近收敛性，并且已在理论上被证明是种以 概率l 收敛于全局最优解的全局优化算法1 5 2 1 1 】。 ( 3 ) 当低适应个体能持续进行彻底地搜索时，一旦它们产生高适应性的后 代，后代会立即进入高适应性水平，来完成高适应性级别的退火，每次降温中， 完成l 次( l 值根据置换点的取定来决定【2 0 1 ，目的是为了尽可能遍历当前状态的 邻域) s w a p f l n v 算子操作，这保证了同适应值水平下的公平竞争。 ( 4 ) 由于表示解的数据串通常很长，而且算子的随机性使解空间近似均匀分 布，因此在降温中，s w a p i n v 算子选择的两个位置相隔两个或两个以上的点的 概率最大。而在此种情况下，i n v 算子有利于算法的大范围搜索，s w a p 算予则 更有利于算法小范围的迁移。因此，在h f c 模型中，低层次的个体需要进行大 范围的搜索，而高层次的个体则需要尽可能地避免破坏。所以本算法中，对较低 层次的种群采用了i n v 算子，而对于较高层次的种群将采用s w a p 算子。这样 处理与s a 算法的理念不谋而合。s a 算法参照的热力学退火原理有如下特点： 高温下可接受与当前状态能量差较大的新状态，而在低温时基本只接受与当前能 量差较小的新状态，而且当温度趋于0 时，就不接受比当前状态能量高的新状态。 2 4 验证实例 对于实例对比验算，我们参照的是b e n c h m a r k 问题之4 8 t s p ( 4 8 城市 旅行商) 问题，我们参照的算法是标准模拟退火算法和遗传算法。两种算法的源 码由h t t p ：w w w h u i s o f l t o m c n d o w n l 下载( 注：由于参照算法没有限制起点、 终点，为了公平比较，我们的改进算法也在此条件运行) 。在此非常感谢源码的 作者殷明慧。我们的改进算法h f c s a 的已知条件( 4 8 个城市坐标) 均与参 照算法的条件相同( 也可以在以上网站下载或阅读) 。考虑到算法运行的随机性， 我们将每种算法均计算1 0 次( 算法源代码见附录二) 。 在4 8 t s p 问题中，我们将条可行的路径作为一个个体，所有个体看作一 个种群，各个等级的个体组成群体称为种群的一个子群。下面是本次实验中 h f c s a 的主要参数设置情况：种群总共分为4 层( 即4 个子种群) ，所有种群 的个体总和限制为1 0 0 0 个，其中每层得门槛值( 警位根据城市的坐标单位决定) 贵州大学硕士研究生学位论文第二章幕于分等级搜索的可持续性漠拟退火算法研究 和种群规模( 单位：个) 限制从低层到高层依次设为：3 0 0 0 0 0 0 3 0 0 ；1 2 0 0 0 0 0 3 5 0 ； 1 0 0 0 0 0 0 2 5 0 ：4 0 0 0 0 0 1 0 0 。初始温度为1 0 0 0 度。在每一代中将随机加入2 0 个 个体。 结合实际运行条件和情况，h f c s a 在处理4 8 t s p 问题时采取了以下的一些 策略： ( 1 ) 初始时由随机生成算子生成一组随机个体，组成初始种群。由于是随 机产生，所以对于初始种群将不对每个子种群实施规模限制而只对所有子种群的 个体总和即初始科t 群规模限制。本实验中初始种群规模设为1 0 0 0 个个体。将它 们按照各自的适应值放入到相应的层次中而不受每层的规模限制，这样刚开始的 种群中，低层次的种群很可能是超过规模的，但是高层次的种群很可能是个体很 少甚至没有的。 ( 2 ) 在接下来一代一代的进化中，当低层次种群的个体进化出高适应值的 个体时，该优秀个体将取代低层次且超规模的种群中的最差个体。这样处理的好 处是：既保证了所有种群的整体规模保持1 0 0 0 不变，避免因为后代的增加而发 生种群“膨胀”，而且动态地挤压低层次的种群有利于个体朝着高层次的方向进 化，同时又有各个层次的规模限制保护了低层次种群不被过度挤压而扭曲 “h i e r a r c h i c a lf a i rc o m p e t i t i o n ( 分层次公平竞争) ”的。原则。 ( 3 ) 在进化中，当由退火算子产生的新个体被当前种群接纳后，如果其适 应值所属的层次已满，则将此个体替换该层的最差个体；反之，如果它的适应值 所在的层次未满，则按( 2 ) 处理：取代低层次且超规模的种群中的最差个