（理论物理专业论文）基因算法和晶格玻尔兹曼方法在物理计算和模拟中的应用.pdf

、r 摘要 x 3 6 1 2 1 7 本学位论文由两部分内容组成。第一部分简要介绍了遗传算法( 又 称基因算法g e n e t i ca l g o r i t h m ，g a ) ，应用遗传算法尝试搜索二维i s i n g s p i ng l a s s 体系的基态自旋配置和基态能，并且提出一种直观的方法来 讨论算法的性能和效率：第二部分先简介了晶格玻尔兹曼方法及其基 本理论，再讨论毛细管中两种互不混合流体之间的界面、界面与固体 不可穿透壁间相交而成的接触角的动力学的一般知识，最后用晶格玻 尔兹曼方法的p o t e n t i a l 模型模拟在一个二维毛细管中二种不相混合的 流体的系统中的界面、接触点、接触角在界面以低速移动时的变化特 征。 部分包括第二童、第三章。遗传算法六十、七十年代提出并 确立，八十年代中期以来得到迅速发展目前仍具有极大开放和成长 性。遗传算法是作为一种研究在计算机系统引入自动适应性等“人工 智能”、“人工生命”特征的方法提出的。它采用了生物界演化“适者 生存，优胜劣汰”的原则，通过模仿自然选择机制以使系统有自动适 应环境的特征。选择机制使遗传算法拥有较强的系统全局优化性能 而这一方面的应用到今天反而成为主流。我们在第三童应用带局域弛 豫修正的遗传算法对自旋最近邻关联是g a u s s i a n 分布的二维l s i n gs p i n g l a s s 系统的基态自旋配置和基态能量进行搜索得到与其他研究者的 结果大致一致的基态能量，手丰对算法优化过程中搜索到的最低系统能 量下降和这个变化所需的时间步数的关系进行统计，发现这种统计是 一个能较为有效评价算法性能和效率的盲观的方法。上述的局域弛豫 修正中的l m 和m v f t 方法是我们自行提出的。 第二部分包括第四、第五和第六章。晶格玻尔兹曼方法来源于格 子气自动机，而格子气自动机是一种特殊的元胞自动机。晶格玻尔兹 曼方法在八十年代得以确立，之后迅速发展，研究日益深入、应用越 来越广。其基本思想是把连续流场、连续时间和速度连续分布都离散 化，并规定只存在极少的几种速度，建立一个简化了的概括微观、介 观过程主要物理特征的动力学模型以使宏观平均i | l 生质遵守所要求的宏 观方程( 这里宏观方程是指n a v i e r s t o k e s 方程) 。l bp o t e n t i a l 模型是 xs h a n 和hc h e n 提出用来研究多相多组分流体系统的它能符合关 于界面的l a p l a c e 定律。我们应用l bp o t e n t i a l 模型又寸二维光滑壁毛细 管中二种不可混合流体这样的体系进行模拟研究流体间界面与壁相 交的接触角和界面( 接触点) 移动速度之间的关系。我们得到与理论 计算和分子动力学模拟相一致 拟这种体系运动的可靠的方法 此说明l bp o t e n t i a l 模型是模 关键词：基因算法，i s i n g 自旋玻璃，晶格玻尔兹曼方法接触角 贫券考：o q t t 3 ，0 3 s ，0 3 6 乃1 天 2 芦 a b s t r a c t t h i sp hdt h e s i sc o n s i s t so ft w op a r t si nt h ef i r s tp a r t ，t h eg e n e t i ca l g o r i t h mi si n t r o d u c e db r i e f l yam o d i f i e dg a i sa p p l i e dt os e a r c ht h es p i nc o n f i g u r a t i o n sa n dt h ee n e r g yv a l u eo f t h eg r o u n ds t a t e so f2 di s i n gs p i ng l a s s s y s t e ma v i s u a lm e t h o di sr a i s e dt od i s c u s st h ep e r f o r m a n c ea n de f f i c i e n c y o ft h ea l g o r i t h m i nt h es e c o n dp m ，l a t t i c eb o l t z m a n nm e t h o da n di t sf u n d a m e n t a lt h e o r ya r ei n t r o d u c e db r i e f l y t h e nd i s c u s st h eg e n e r a lk n o w l e d g e o ft h ed y n a m i c so ft h ei n t e r f a c e ，c o n t a c tl i n e ，a n dc o n t a c ta n g l ef o r m e db y t w oi m m i s c i b l ef l u i d sa n ds o l i di m p e r m e a b l ew a l li nc a p i l l a r yt u b ef i n a l l y , l a t t i c eb o l t z m a n np o t e n t i a lm o d e li sa p p l i e dt os i m u l a t eas y s t e mc o n s i s t i n g o ft w oi m m i s c i b l ef l u i d si na2 d c a p i l l a r yt u b et os t u d yt h ed y n a m i cp r o p e r t i e so ft h ei n t e r f a c e ，c o n t a c tp o i n t ，a n dc o n t a c ta n g l eb e t w e e nf l u i d sa n d s o l i dw a l l t h ef i r s tp a r ti n c l u d e sc h a p t e r2a n dc h a p t e r3g e n e t i ca l g o r i t h mi s i n v e n t e da n de s t a b l i s h e di n1 9 6 0 sa n d 1 9 7 0 s ，r a p i d l yd e v e l o p e di n t h e m i d d l eo f1 9 8 0 si ti ss t i l la no p e na n dg r o w i n gs u b j e c tt h eg e n e t i ca l g o r i t h mi si n v e n t e da sa na p p r o a c ht os t u d yh o wt oi n t r o d u c et h ef e a t u r eo f “a r t i f i c i a li n t e l l i g e n c e a n d “a r t i f i c i a ll i f e ”s u c ha sa d a p t a b i l i t yi n t oc o m p u t e rs y s t e mi t e m p l o y st h eg r e a tp r i n c i p l e f o rt h e p r o c e s so fl i f eo r g a n i s m e v o l u t i o n ，“t h ea d a p t a b l em a ys u r v i v et h es t r u g g l ef o rl i v i n g ”，t oi m i t a t e n a t u r a ls e l e c t i o nt om a k es y s t e ma d a p t a b l et oe n v i r o n m e n ts e l e c t i o nm a k e s g ah a v es t r o n ga b i l i t yo f g l o b a lo p t i m i z a t i o n i t i s b e c o m i n gt ot h em a i n t r e n dt h a tt h eg ai s a p p l i e da s ak i n do fo p t i m i z a t i o nt o o lw e e m p l o y e d g am o d i f i e db yl o c a lr e l a x a t i o nt os e a r c ht h es p i nc o n f i g u r a t i o n sa n de n e r g yv a l u eo f t h eg r o u n ds t a t e so f2 di s i n gs p i ng l a s ss y s t e mi nw h i c ht h e b o n db e t w e e nt w on e a r e s t n e i g h b o r e ds p i n sd i s t r i b u t e sa sg a u s s i a nt y p e 3 o u rs e a r c h i n gr e s u l t sa r ea p p r o x i m a t e l yc o n s i s t e n tw i t ho t h e rr e s e a r c h e r s r e s u i t sw ea l s od i dt h es t a t i s t i c so nt h er e l a t i o nb e t w e e nt h ec u r r e n tl o w e s t e n e r g yc h a n g e sv sc o r r e s p o n d i n gt i m ed u r a t i o ni nt h ep r o c e s so fs e a r c h i n g a n df o u n dt h i ss t a t i s t i c sa ne f f e c t i v ea n dv i s u a le v a l u a t i n gc r i t e r i o nf o rt h e p e r f o r m a n c e a n de f f i c i e n c yo fas e a r c h i n ga l g o r i t h m t h es e c o n dp a r ti n c l u d e sc h a p t e rf o u r , c h a p t e rf i v e ，a n dc h a p t e rs i x l a t t i c eb o l t z m a n nm e t h o do r i g i n a t e sf r o ml a t t i c eg a sa u t o m a t a ，w h i c hi sa s p e c i a lv e r s i o no fc e l l u l a r a u t o m a t al a t t i c eb o l t z m a n nm e t h o dw a si n v e n t e di n19 8 0 sa n db l o s s o m se x t e n s i v e l yo v e rm a n yf i e l d si t se s s e n t i a l i d e ai st od i s c r e t i z ef l o wf i e l d ，t i m ea n dv e l o c i t yd i s t r i b u t i o n ，c o n s t r u c ta s i m p l i f i e dk i n e t i cm o d e li n c o r p o r a t i n gt h ee s s e n t i a lp h y s i c so fm i c r o s c o p i c o rm e s o s c o p i cp r o c e s ss ot h a tt h em a c r o s c o p i ca v e r a g e dp r o p e r t i e sr e c o v e r d e s i r e dm a c r o s c o p i ce q u a t i o n sf n a v i e r - s t o k e se q u a t i o n ) l a t t i c eb o l t z m a n n p o t e n t i a lm o d e lw a sd e v e l o p e dt os t u d ym u l t i p h a s e sa n dm u l t i c o m p o n e n t s f l o w sb yxs h a na n dhc h e ni tc a nr e c o v e rl a p l a c el a w , w h i c hc o n c e r n s t h ei n t e r r a c i a lp h e n o m e n aw e a p p l i e dl a t t i c eb o l t z m a n np o t e n t i a lm o d e lt o s i m u l a t et h ed i s p l a c e m e n to ft w oi m m i s c i b l ef l u i d si n2 d c a p i l l a r yt u b ea n d s t u d yt h ed y n a m i cp r o p e r t i e so fi n t e r f a c e ，c o n t a c tp o i n t ，a n dc o n t a c ta n g l e o u rs i m u l a t i n gr e s u l t sa r ee x c e l l e n t l yc o n s i s t e n tw i t ht h e o r e t i c a lc o m p u t a t i o n sa n dm o l e c u l a rs i m u l a t i o n st h i sm e a n st h a tl a t t i c eb o l t z m a n nm e t h o d i sap r o m i s i n ga p p r o a c ht os t u d yt h i sk i n do f s y s t e m s k e yw o r d s ：g e n e t i ca l g o r i t h m ，l s i n gs p i ng l a s s ，l a t t i c eb o l t z m a n n m e t h o d s ，c o n t a c ta n g l e 4 第一章引言 基凶算法( g e n e t i ca l g o r i t h m ) 又名遗传算法1 ，是一个较新的、当 前正快速成长的研究领域。这是一种借鉴生物界自然选择和物种遗传 机制的高度并行、随机、自适应搜索算法。基因算法最引人入胜、激 动人心的应用领域包括机器学习、科学建模和“人工生命”，但目前最 常用的是处理最优化问题和工程设计。隐含并行性和对全局信息的有 效利用能力是遗传算法的两大显著优点，前者使基因算法只须检测少 量的结构就能反映搜索空间的大量区域，后者使基因算法具有强健性 ( r o b u s t n e s s ) 。基因算法尤其适于处理传统搜索方法解决不了的复杂和 非线性问题。 自旋玻璃( s p i ng l a s s ) 是一种自旋系统，各自旋磁矩之间的相互作用 处于冻结无序状态，因而没有传统的长程序( 铁磁或反铁磁) 可以建 立起来。自旋玻璃具有巨大数量的自由度，因此搜索其基态确定基态 能是个极复杂困难的课题。这是一个典型的组合优化问题。即使对自 旋方向加以限制的i s i n g 自旋玻璃仍然是极端困难的。已经有多种方法 被引入研究这一问题，如模拟退火算法、随机优化法等。基因算法也 被尝试用来寻找基态能。最近对特定的几个i s i n gs p i ng l a s s 模型( 如 j ) 有了精确解算法，这当然是对特定问题最好的方法。基因算法是 一类普遍有效的优化工具，并不是为某一问题定制的，但它在i s i n gs p i n g l a s s 系统的基态搜索方面展现了一定的性能和价值。同时基因算法在 该领域的应用也有利于其本身的动力机制的更深入地研究。 品格玻尔兹曼方法( l b m ) 最近一些年来发展成为一个研究计算流体 力学尤其是模拟复杂流体的有力的工具。l b m 以l g a 为基础发展而 国内文献似喜用后者以下两种译名混用 7 来，继承了l g a 的许多优势并去除r 诸如过多的统计噪声和格子人为 性质如没有伽利略不变性、压强依赖于流速等缺陷。l b e 方法以微观 或介观的简单模型来模拟宏观的流体现象，并且由其粒子分布函数得 来的宏观流体密度和速度完全符合n a v i e r - s t o k e s 方程，这保证了l b m 的有效性。 两相互不混合的流体在固体表面的运动直吸引着众多研究者的 注意。从液滴在固体表面的扩展到容器中流体的驱替，从化学电镀到 注水采油，都涉及这一大类课题。这一类课题中，界面及界面与壁交 成的接触线及在接触线上界面与壁的接触角的运动变化更是重要研究 课题。 本文分前后两个部分。第一部分包括第二、第三章。第二章为基 因算法简介，分思想起源、发展背景、特征描述、举例和与其他搜索 方法的对比；第三章为基因算法应用在二维i s i n gs p i ng l a s s 系统基态能 搜索，并且分析了其优化性能、效率。 第二部分包括第四、第五、第六章。第四章叙述l g a 的发明与发 展，l g a 的局限和l b m 的提出与确立和l b m 的理论简述；在第五章 主要介绍了用于多相不可混合流体运动模拟的l b 模型及其理论；运 用l bp o t e n t i a l 模型研究不可混合流体驱替，其界面、接触线及接触角 的动力学的内容放在第六章。 第二章基因算法简介 2 1 基因算法基本思想的起源和背景 物种演化( 进化，e v o l u t i o n ) 思想似乎可以上溯至中外古代先贤的 智慧，但真正奠基是达尔文发表物种起源 1 。演化思想在其后虽 遭包括宗教在内多方面的强有力的反击，但一直保持了旺盛的生命力 并逐渐为越来越多新的科学知识所支持。直到2 0 世纪在古生物学、分 子遗传学等现代生物学科的新成果出现后，物种演化思想才真正地为 人们普遍接受。 早在生物的演化理论得到人们的接受之前，生物学家就对其机制 产生了极大的兴趣，并且这还是各种争论聚焦的最热点。尽管达尔文 的关于自然选择作为物种演化的终极驱动的理论已几乎成为公论，但 生物界表现出来的多样性和复杂性仍然不时让包括生物学家在内的许 多人惊异并时而对达尔文学说提出质疑或诘难。化石记录表明我们所 观察到的复杂结构的生命是在相对短的时间进化而来的；生物演化史 上发生过数次“大规模绝种”和“物种大爆炸”。这些事实背后所隐藏 的关于物种演化的动力机制及运作规律特征目前尚不清楚，但它们的 某些特征已为人所知。进化是发生在作为生物体结构编码的染色体卜， 通过对染色体的译码部分地生成生物体。 人们现在还不完全清楚染色体的编码和译码过程的细节，但下面 几个关于进化理论的一般性知识已广为人们所接受 2 【3 】。 ( 1 ) 进化过程是发生在染色体上，而不是发生在它们所编码的 生物体上。 ( 2 )自然选择把染色体以及由它们所译成的结构的表现联系在 9 一起，那些适应性好的个体的染色体经常比羞的个体的染 色体有更多的繁殖机会。 ( 3 ) 繁殖过程是进化发生的那一刻。变异可以使生物体子代的 染色体不同于它们父代的染色体。通过结合两个父代染色 体中的物质，重组过程可以在子代中产生有很大差异的染 色体。 ( 4 ) 生物进化没有记忆。有关产生个体的信息包含在个体所携 带的染色体的集合以及染色体编码的结构之中，这些个体 会很好地适应它们的环境。 自然界生物体通过自身的演化就能使问题得到完美的解决，这种 才能让最好的计算程序也相形见绌。计算机科学家为了某个算法可能 耗费数月甚至几年的努力，而生物体通过缝丝塑自丛选蛏这种韭定囱 机制就达到了这个目的。 大多数生物体是通过自然选择和有性生殖这两种基本过程进行演 化的。自然选择决定了群体中哪些个体能够存活并繁殖：有性生殖保 证了后代基因中的混合和重组。比起那些仅包含单个亲本的基因拷贝 和依靠偶然的变异来改进的后代，这种由基因重组产生的后代进化要 快得多。自然选择的原则是适应者生存，不适应者淘汰。 基因算法是由j o h nh o l l a n d 在6 0 年代提出，并在6 0 、7 0 年代由他 和他的学生及同事发展起来的【4 - 6 。在此之前，遗传策略( e v o l u t i o n s t r a t e g i e s ) 7 和- - 大类受遗传机制启发的优化或机器学习算法 8 1 2 已 经由一些计算机科学家各自独立研究了。一个主要动机是试图创造出 人工智b ( a m f i c l a li m e l l i g e n c e ) 和人工生命( a r t i f i c i a ll i f e ) 。生命现象和智 能现象是生物界特别是人特有的现象。计算机科学的先驱a l a nt u r i n g ， j o h nv o nn e u m a n n ，n o r b e r tw i e n e r 等人以深远的洞察力提出原则上生 1 0 物个体表现的自我复制、适应环境及学习能力等生命和智能特征可以 在计算机上以程序方式实现。 在6 0 年代，r e c h e n b e r g ( 1 9 6 5 ，1 9 7 3 ) 【7 1 提出遗传策略( e v o l u t i o n s t r a t e g i e s ) ，德文原文为( e v 0 1 u t i o n s s t r a t e g i e ) ，这种方法用于优化一些设 施如风洞的实参数。s c h w e f e l ( 1 9 7 5 ，1 9 7 7 ) 1 3 进一步发展了这个想法。 f o g e l ，o w e n s 和w a l s h ( 1 9 6 6 ) 提出“遗传编程” 1 4 。此两者与基因算 法一起并列为“遗传计算”( e v u l o t i o n c o m p u t a t i o n ) 领域的主要分支。 值得注意的是，与遗传策略和遗传编程不同，h o l l a n d 最初提出基 因算法的目的并不是解决特定的问题，而是形式地研究自然过程中的 适应现象以发展出可能的把自然的适应机制引入计算机系统的途径。 h o l l a n d1 9 7 5 年的著作自然和人工系统中的适应性( a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ) 把基因算法表示为一种抽象的生物进化并 给定了在g a 下适应性的理论框架。h o l l a n d 的g a 把条比特链( o 或1 ) ( 染色体c h r o m o s o m e ) 通过“选择”( 仿自然选择) ，和一些受生 物遗传启发的操纵子如交换c r o s s o v e r ，变异m u t a t i o n ，反转i n v e r s i o n 操作得到一条新的比特链。“染色体”由“基因”组成，而“基因”实 际上是特定比特序列。选择操作把特定“染色体”从群体中挑选出来 和另一些被挑选的染色体“繁殖”，平均而言，较高适应性的比较低适 应性的有更多的“繁殖”机会。“繁殖”时发生交换( c r o s s o v e r ) 操作。 c r o s s o v e r 操作交换“染色体”的局部片断、模拟单倍体生物之间有性 生殖时染色体的重组；变异( m u t a t i o n ) 操作则随机变换“染色体”上某 一位的值：反转( i n v e r s i o n ) 操作颠倒染色体的某片断的顺序。这一切都 对“基因”作了重新排序。 h o l l a n d 引入的以候选群体为基础的算法及c r o s s o v e r ，i n v e r s i o n 和 m u t a t i o n 等操纵子是一个重要创新。( r e c h e n b e r g 的遗传策略以只有两 个个体的“群体”开始，其中一个为父代，一个为子代，子代是父代 的变异版本；多个体的群体和c r o s s o v e r 直到后来才被纳入。f o g e l ， o w e n s ，和w a l s h 的遗传编程类似地也只用变异来提供基因变化。) 另 外，h o l l a n d 是首位尝试把计算演化( c o m p u t a t i o n a le v o l u t i o n ) 置于一个 坚实的理论基础的研究者 6 。直到最近，这一建立在s c h e m a s 这一概 念上的理论基础仍然是几乎所有g a 理论研究工作的基础 1 5 - 1 8 1 。 1 2 2 2 简单基因算法描述和实例 并没有一个关于“基因算法”的在遗传计算界中广泛接受的严格 定义把g a 和其他遗传计算( e v o l u t i o n a r yc o m p u t a t i o n ) 方法区别开。但 所有可被称作“g a ”的方法至少有下列共同基本要素：染色体群体；按 适应性的选择：交叉或交换( c r o s s o v e r ) 以产生新子代；随机变异产生新 个体。h o l l a n d 的另一个g a 的要素反转( i n v e r s i o n ) 如今则较为少用。 g a 群体中的个体“染色体”典型地可有b i t 链的形式。链上每个 位置( 1 0 c u s ) 有两个可能的“碱基对“( 0 或1 ) 。每条“染色体”可以被 设想为候选解的搜索空间中的一个点。g a 过程把这一群搜索空间中的 点经特定操作变换为另群点。g a 通常需要一个适应度函数对当前群 体中的每一“染色体”予以评价打分( 确定适应度) ，而适应度的高低 取决于“染色体”有多好地解决所关心的问题。 适应性函数的例子 g a 的一个普遍的应用是函数优化，目的是找到一个参数值集以使 一个复杂多参数的函数值最大化。考虑一个简单例子，找出使下列函 数值最大的y 值 1 9 f ( y ) = j ，+ is i n ( 3 2 y ) i ，0 y 7 这里y 可以以b i t ( 0 或1 ) 链编码来代表实数。适应度计算过程先把b i t 链翻译成实数y 再计算函数值。链的适应度是链在这种编码方法下本 身对应的函数值。 另一个非数值的实例是，考虑一个有5 0 个氨基酸的序列折叠成要 1 3 求的三维蛋白质结构的问题，一种g a 可以用来搜索候选解群体，其 中每个都编码为5 0 个字符长的诸如 i h c c v a s a n f p g i 的链，每个字母代表2 0 中可能的氨基酸之。一种序列适应度的定义 是其特定结构所对应的势能负值。势能越低，适应度越高。 以上两例不同问题中不同编码及适应度定义方式：问题的候选解 编码抽象的由符号串构成“染色体”，适应度函数定义在串的所有可能 性拓展的空间上。g a 就是在这样的适应度空间地形上搜索高适应度的 串形式。 最简单的g a 包含三种操纵予：选择，交叉( 单点) ，变异。 选择( s e l e c t i o n ) ：这个操纵子把个别“染色体”从群体中选出进行 “繁殖”。“染色体”个体适应度越高，则有越多的机会被选中。 交叉( c r o s s o v e r ) ：该操纵子在两条“染色体”上随机选取一个位置 把它切断，然后交换各自部分以产生两条新的子代“染色体”。举个例 子，两串1 0 0 0 0 1 0 0 与1 1 1 1 1 1 1 1 可在第三位后进行c f o s s o v e f 产生两条 新个体】0 0 1 1 】1 和1 】0 0 1 0 0 。c r o s s o v e r 算子大致地模拟两个单位体 生物( 基因) 重组的情形。 变异( m u t a t i o n ) ：该操纵子随机翻转串上的任一位。如串0 0 0 0 0 0 10 0 可能在第二位变异而得0 1 0 0 0 1 0 0 。m u t a t i o n 可能以比较小的几率在串 的任一位上发生。 以下给一个简单的应用b i t 串作为候选解的g a 的例子。 1 4 简单g a 的步骤如下： 1 先随机产生几个，b i t 的串“染色体”作为问题的候选解。 2 计算对应群体中的每条“染色体”的适应度。 3 重复以下步骤直到几个子代个体产生。 a 从当前群体中选出一对父本“染色体”。选中几率是适应度的 单调上升函数。每个“染色体”可以多次选中。 b 对上步选中的“染色体对”在随机选择的数位上( 所有位置 同几率) 以几率p 。( c r o s s o v e r 几率) 进行c r o s s o v e r 产生 了子代。( 这里的c r o s s o v e r 几率定义在“染色体”单一位置 上发生的“s i n g l e p o i n tc r o s s o v e r ”。相应的有“m u l t i 。p o i n t c r o s s o v e r ”。) c 对上一步新产生的个体的每一位按变异几率p 。( m u t a t i o n p r o b a b i l i t y ) 进行变异。 4 把新产生的几个个体代替原先的几个个体( 更新群体) 。 5 返回步骤2 。 每一次循环叠代称为一“代“。一般一个典型的g a 可能会循环几 十至几百几千代不定。 这几十至上千代循环被称为一个运q i ( r u n ) 。每 次运行结束群体中将包括一些适应度较高的“染色体”。由于随机性在 单独一次r u n 中的重要作用，两次有不同随机种子数的独立运行将会 有不同的行为细节特征。g a 的研究者通常会对一个问题讨论同一个g a 的多次运行统计结果。 上述的操作步骤是大多数g a 应用的基础。还有许多细节如群体大 小，c r o s s o v e r 和m u t a t i o n 的几率大小可以讨论，算法的成功很大程度 上依赖于这些细节。另外还有一些较为复杂的g a ( 如群体中的个体并 不是位串或是别的什么编码形式，g a 可能采用别的形式的c r o s s o v e r 和m u t a t i o n ) 。 下面是一个更详细的关于简单g a 的例子，考虑串长，为8 的b i t 串，串的适应度f ( x ) 等于串中1 的数目( 一个极为简单的适应度函数， 在此只是作范例用) ，群体中个体数为n = 4 ，p 。= 0 7 ，p ，= o0 0 1 ( 如 同适应度函数的选取，这里的l 和n 也是选取以作范例。更典型的1 和 n 可以是很大的数值。p 。和p 。比较接近典型值。) 初始( 随机产生的) 群体可以是如下 个体序号 a b c d 0 0 0 0 0 1l o 1 1 l o l l l o 0 0 1 0 0 0 0 0 0 0 1l o l 0 0 值 2 6 l 3 g a 中常用的选择方法是“正比适应度选择”，即一个个体被期望 选中的次数等于其适应度值除以群体的平均适应度值。 一个简单的“正比适应度选择“的实现方法是所谓“轮盘赌取样” ( 2 0 ，就是在轮盘上给每个个体划一块扇形片，其面积正比于其适应度。 轮盘转起来，球最后落在哪一个片上，对应的哪个个体就被选中。上 例中n = 4 ，轮盘就转4 次；前两次转动可能选出b 和d 为父本，后两 次转动选出b 和c 。 1 6 旦一对父本选定，则以p ，的几率c r o s s o v e r 产生两个子代。如果 c r o s s o v e r 没有发生，则子代就是这两者本身。假如上例中b 和d 在第 一字节后c r o s s o v e r 产生子代个体e = 1 0 1 1 0 l o o 和f = 0 1 1 0 1 11 0 ，b 和c 不发生c r o s s o v e r 子代个体就是b 和c 。然后，每个子代个体的每一 位都按几率p 。变异( 翻转) 。例如子代个体e 在第六字节上发生变异 变成e = 1 0 1 1 0 0 0 0 ，子代个体f 和c 都不变异，子代个体b 在第 字节变异成b = 0 1 1 0 1 1 l o 。这样新的群体如下 序号 e f c b 富 0 0 0 0 0 11 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 11 0 1 0 0 值 3 5 1 5 在上面新的一代群体中虽然最佳值( 适应度6 ) 丢失了，但平均 适应度从1 2 4 上升为1 4 4 。重复循环这样的过程将导致群体中的串每 一字节都是1 。 1 7 2 3 作为搜索方法的基因算法与传统搜索方法 基因算法很大程度上可归之为一种搜索方法。这里的“搜索“的 含义可以与计算机科学中的“搜索”形成对照。 一般而言有三种搜索的“含义”： 1 储存数据的搜索 对此的主要问题在于有效的获取储存在计算机存储器中的信息。 假定具备一个关于姓名和地址的以一定次序排列的大数据库，那么找 到对应于给定姓氏的记录的最佳方法是什么昵? “二元搜索”是一种 搜索所求记录的方法。k n u t h 2 1 】的著作描述分析了许多这样的搜索方 法。 2 达到目标之路径的搜索 在此的问题在于有效的找到实现从初始状态到给定目标的一组动作 ( 即路径) 。这种形式的搜索主要用于人工智能领域的许多方法。 3 解的搜索 这是比“到目标路径搜索”更为普遍的一类搜索。主要问题是在庞 大的候选解空间中有效的找到问题的解。有许多种搜索问题应用了 g a 。， 第一种搜索雨后二种搜索有很大的不同。第一种涉及的问题要求在 已显式储存了的信息集合找到特定的信息( 如一个电话号码) 。后二者 中，要寻找的信息并未被显式的储存而是在搜索过程中不断地有候选 值被创造出来。当用g a 搜索候选解空间时，并不是所有的候选解先 被创造出来然后判断其之而是只检查可能解的一小部分以确定最优或 优质解。 “解的搜索”可以涵盖“对目标的路径搜索”，因为一条通过搜索 分支树的路径可以编码为候选解。当然，许多“路径搜索”问题a i 树 搜索技术( 这里只须部分求值) 比g a 或类g a 技术表现出色( 这里 所有候选解在求值之前必须被产生) 。 然后，标准a j 树搜索方法并不是总有效。并不是所有问题都需要 求得的从初始态到目标态的路径。如从蛋白质氨基酸序列预测三维蛋 白质结构并不需要y 解其在三维中折叠运动的过程，只需要知道最后 的构形配置。对于大多数问题，包括蛋白质折叠问题，目标态即最终 的配置构形事前是不知道的。 g a 是一种普遍的解决“搜索解”问题的方法( 如同另一些遗传进 化启发的技术如遗传策略和遗传编程) 。爬山法( h i l lc l i m b i n 9 1 ，模拟 退火法( s i m u l a t e da n n e a l i n g ) 是另一些普遍方法的例子。具体描述可见文 献 2 2 2 3 。属爬山法的“最陡上升法”如下操作： 1 随机选定一个候选解( 编定编码方式的b i t 串) ，称为“当前串”。 2 整个系统地变化串中的每个位，从左至右一次一位，记录每次单b i t 变化带来的适应度的变化。 3 若任一次单b i t 变异导致适应度上升，把“当前串”定为导致适应 度最大上升的单b i t 变异后的串。 4 如无适应度上升，把当前串( 山顶) 储存起来并回到1 。否则待3 中产生的新“当前串”回到2 。 5 当一些数量的适应度函数被求过值，返回发现的最高山顶。 在a j 中这一类普遍方法( 通用于大量不同问题) 称为“弱方法” 以区别于专为特殊问题设计的“强方法”。所有的“搜索解”问题都有 如下特点： ( 1 ) 初始地产生一组候选解( 在g a 中这是初始群体；在“最陡上升” 爬山法这是初始串及其所有单b i t 变异串) ； 1 9 ( 2 ) 按一定的适应度标准对候选解求值； ( 3 ) 按一定标准决定哪个候选解去，哪个候选解留 ( 4 ) 进一步用一些操作产生进一步变化。 g a 式并行群体搜索、个体随机选取、c r o s s o v e r 、变异这些要素的 特殊组合， 这使其和别的一些搜索方法区分开来。许多方法有其中 的一部分要素，但不是全部。 2 0 第三章基因算法在搜索二维i s i n gs p i n g l a s s 系统基态能中的应用2 3 1 面对最优化问题的g a 对于一些“搜索解”问题，基因算法是一个优化工具，它可以在巨大 的态空问里搜索全局最优( 或接近最优) 的态【1 3 】。穷举法搜索全局最优 解理论上是可靠，但对几乎任何实际问题都不具实用性。于是许多其 他方法包括下降( 或上升) 搜索方法( d e s c e n t o fa s c e n ts e a r c h i n gm e t h o d s ) 象爬山法，模拟退火法【4 ，和g a 等被发展来应付这一类问题。 直到现在，能用简单g a ( s i m p l eg a , s g a ) 有效解决的问题几乎都 是一维的。旅行推销商问题 5 看起来是二维的，但要求的解实际上还 是连接所有城市的一维路径。对一维问题s g a 可以轻易地以极小的计 算代价( 计算时间，计算机资源占用) 找到全局最优解。 面对2 d 问题，g a 看起来就没那么强有力和有效了，这是由于二 维系统本身的困难度和复杂性导致的。二维系统有大量相互作用关联， 即使只是考虑最近邻相互作用。另外，f r u s t r a t i o n 是另一个困难，因为 系统中任意二个元素可以通过无数条间接连接通道相关联。这些困难 降低了任何一种算法的效率，包括g a 。因此若干修正对一种对于某些 特定系统实用的g a 是必需的。同时一种典型的2 d 的具有物理方面兴 趣的体系对观察一个修正的g a 的效率性能来说是一个合适模型。 2 第三章内容参见完成工作和发表论文。 2 1 l s i n gs p i ng l a s s 确实是一个困难的问题，吸引了许多研究者【6 7 。 搜索2 d 或更高维的i s i n gs p i ng l a s s 是该领域里最困难的问题之- 8 11 。由于d i s o r d e r 和f r u s t r a t i o n ，要通过决定论的( d e t e r m i n i s t i c ) 手段获 得基态结构是困难的。随着系统的尺度增大，态空间的大小以指数方 式增长，穷举法只能对于最小尺度的几个系统是适用的。因此，出现 了些以随机过程为基础的搜索算法。其中模拟退火法是有效且实用 的算法 4 1 1 8 1 ，它是以梯度搜索方法( g r a d i e n ts e a r c hm e t h o d ) 为基础因而 也属于局域优化一类。最近一些年，一种名为b r a n c h a n d c a t 的准确算 法被提出 9 2 0 1 1 2 1 。这是一种为i s i n gs p i ng l a s s 系统定做的搜索算法。 而g a 是一种普遍的“弱”优化方法，并且对复杂的物理系统而言它 是具有全局优化的特征。它无疑是一种研究基态问题的候选方法 1 2 【1 4 f 1 5 。另外，g a 应用在l s i n gs p i ng l a s s 上，其性能和机理司 以在搜索过程中得到揭示。 3 2 l s i n gs p i ng l a s s 模型及修正的g a 算法描述 我们研究2 d l l 方晶格系统，用循环边界条件。每个格点有一个 i s i n g 自旋占位，与4 个最近邻自旋有随机分布的相互作用关联。这种 e d w a r d a n d e r s o ni s i n gs p i ng l a s s 系统( e a 模型) 的h a m i l t o n i a n 如下： h = 一j 。墨s ， ( 31 ) 其中j ，由随机分布函数p ( j ，) 决定。 己知如果p ( j i ) 是普通的连续分布则在巨量的可能自旋组态中只有 一对基态【1 6 】。如果p ( ，。) 取如下的离散分布( 1 分布) p ( j 。) o e a ( j ，一1 ) + 6 ( j 。十1 ) ， ( 32 ) 将由大量的局域简并基态。这样达到其中任意一个简并基态的几率比 连续分布时要达到一对基态的几率大多了。这就可以理鳃大多数文献 是关于1 分布，连续随机分布较少被注意 8 9 儿1 2 2 1 】。在这些文献 中，gsg r e s t 应用s i m u l a t e da n n e a l i n g 8 ；kfp t l 在3 di s i n gs p i ng l a s s 系统上应用一个“杂种的”( h y b r i d ) g a 1 2