（计算机软件与理论专业论文）基于遗传算法的商标图案设计.pdf

山东师范大学硕士学位论文 摘要 随着社会经济的快速发展，各类企业层出不穷，伴随着企业的越来越多，商标作为企 业的标志越来越受到重视，而商标的设计成为企业发展的重要环节。商标是商品的生产者 经营者在其生产、制造、加工、拣选或者经销的商品上或者服务的提供者在其提供的服务 上采用的，区别商品或者服务来源的，由文字、图形或者其组合构成的，具有显著特征的 标志。商标是现代经济的产物，它不同与古代的印记，现代标志承载着企业的无形资产， 是企业综合信息传递的媒介。商标作为企业形象的标志，具有鲜明的独创性与独有性，商 标设计并不仅仅是设计美学以及技术因素，还涉及到法律、文化传统的方面。标志作为企 业c i s 战略的最主要部分，在企业形象传递过程中，是应用最广泛、出现频率最高，同 时也是最关键的元素。企业强大的整体实力、完善的管理机制、优质的产品和服务，都被 涵概于标志中，通过不断的刺激和反复刻画，深深的留在受众心中。 遗传算法是一类借鉴生物界的进化规律( 适者生存，优胜劣汰遗传机制) 演化而来的 随机化搜索方法。它是由美国的j h o l l a n d 教授1 9 7 5 年首先提出，其主要特点是直接对结 构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻 优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索 方向，不需要确定的规则。生物进化论认为生物的进化过程可以被看成是对种群操作的物 理变化过程，这个过程包括复制、杂交、变异、竞争和选择。复制过程使得种群按指数速 度扩张，复制完成对后代个体的遗传基因的传递；杂交是两个个体的部分基因互换而产 生两个新个体；变异是遗传基因在传递过程中出现差错；竞争是在有限的生存空间对群体 进行压缩：选择是在有限的生存空间竞争的不可避免的结果；最后适者生存，劣者淘汰。近年 来，随着对于遗传算法研究的不断深入完善，有越来越多的人认识了解了遗传算法，并把 它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网络、工业优化 控制和社会科学等方面。 本文主要研究利用遗传算法对商标图案进行设计，从而有效得对商标图案进行自动化 分析，并随机产生多种商标图案进行遗传变异，对大量商标图案进行自动筛选分析，对商 标图案进行选择，从而得到系列相关图案，并从中挑选出适合商标进行最后挑选。 最后，我们在对基于遗传算法的图案设计进行应用扩展，在对遗传算法在商标设计领 域的应用进行分析后，对方案的正确性我们予以证明，且对遗传算法的其他应用性进行了 探讨，并给出一些应用领域。 山东师范大学硕士学位论文 关键词：遗传算法；进化计算；人工智能；商标设计；商标分类； 山东师范大学硕士学位论文 a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fs o c i e t ya n dt h ee c o n o m y ，e n t e r p r i s eo fa l lk i n d sa r e c o n t i n u i n gw i t h o u te n d ，b em o r eb e i n ga c c o m p a n y i n ge n t e r p r i s e s ，t h el o g oi sr e g a r d e dh i g h l y a se n t e r p r i s e s i g nm o r ea n dm o r e ，b u tt h eb r a n dd e s i g nb e c o m e st h ei m p o r t a n tl i n kt h a t e n t e r p r i s ed e v e l o p s t h eb r a n dh a v en o t a b l ec h a r a c t e r i s t i cs i g nt h a td i f f e r e n t i a t e dac o m m o d i t y o rs e r v i c e ss o u r c e i ti sc o m p o s e do fc h a r a c t e r s ，a r t w o r ko ra n o t h e rc o m b i n a t i o na n da p p l i e d w i t hm a k i n g ，p r o c e s s i n g ，s e l e c t i n go rb e i n gs o l db yap r o d u c e ro rs e r v i n gb ys e r v i c ep r o v i d e r t h eb r a n d i s m o d e me c o n o m yo u t c o m e ，i ti sd i f f e r e n tf r o ma n c i e n tp r i n t ，t h em o d e ms i g ni s b e a r i n gt h ew e i g h to ft h ee n t e r p r i s ei n t a n g i b l ea s s e t s ，i sah e r e d i t a r ys y n t h e t i c a le n t e r p r i s e i n f o r m a t i o ni n t e r m e d i a r y t h el o g oi st h em a i n e s tp a r ti ne n t e r p r i s e sc i ss t r a t e g y ，i nt h e p r o c e s so fe n t e r p r i s ei m a g ed e l i v e r y ，i ti st h eb r o a d e s ta n dt u r n i n gu pf r e q u e n c y ，t h es a m et i m e i sa l s ot h em o s tk e ye l e m e n t t h eb r a n dh a se m b o d i e dt h ee n t e r p r i s eo v e r a l ls t r e n g t h 、p e r f e c t t h ep r o d u c tm a n a g i n gm e c h a n i s m 、h i g hg r a d ea n ds e r v i c e ，a n dt h eb r a n di sr e m e m b e r e db y c u s t o m e rt w i t ht h ec e a s e l e s ss t i m u l a t i o na n dd e p i c ta g a i na n da g a i n ， g e n e t i ca l g o r i t h mi sak i n do ft h er a n d o m i z a t i o nr e c o n n a i s s a n c em e t h o du s i n gb i o s p h e r e s e v o l u t i o n l a w ( s u r v i v a lo ft h ef i t t e s t ，s u r v i v a lo ft h ef i t t e s ti n h e r i tm e c h a n i s m ) f o rr e f e r e n c e e v o l v i n gb u tc o m i n g i ti st os u g g e s t e dt h a tf i r s ti n19 7 5b ya m e r i c a nj h o l l a n dp r o f e s s o r ， w h o s em a i nc h a r a c t e r i s t i ci st h a tt h em a r r i a g ep a n n e rc a r r i e so u to p e r a t i o no ns t r u c t u r ed i r e c t l y ， t h en o t h i n g n e s sa s k sl e a ds e t t i n gal i m i tf o rc o m p o s i n gi nr e p l yaf u n c t i o nc o n t i n u i t y ；h a v et h e h i d ec o n c u r r e n c en a t u r ea n dm u c hb e t t e ri n h e r e n to v e r a l ls i t u a t i o no p t i m i z i n ga b i l i t y ；a d o p t p r o b a b i l i t y r i z a t i o no p t i m i z i n gm e t h o d ，c a nv o l u n t a r i l y g a i na n dg u i d et h es e a r c h e dv o l u m e o p t i m i z i n g ，a d j u s td i r e c t i o no fs e a r c hc e r t a i n l yf i ti nw i t h ，n o tn e e d i n gt h er e g u l a t i o n a s c e r t a i n i n gt h a t 【1 】i nr e c e n ty e a r s ，s t u d y i n gw i t hg e n e t i ca l g o r i t h mi sr e g a r dt oi nd e p t h p e r f e c t ，t h em o r ea n dm o r ep e o p l ec o g n i t i o nt oh a v ek n o w ng e n e t i ca l g o r i t h m ，a n da p p l yi ti n m o r ea n dm o r eb r o a df i e l d ，s u c ha sf o ri n s t a n c e ，t h em a c h i n es t u d ya b o u t ，p r i n c i p l e so f p a t t e r n r e c o g n i t i o n ，i m a g eh a n d l i n g ，n e u r a ln e t w o r k s ，i n d u s t r yo p t i m i z i n gt h es o c i a ls c i e n c e s c o n t r o l l i n gas u m t h em a i nb o d yo fab o o ki ss t u d i e dm a i n l ym a k i n gu s eo fg e n e t i ca l g o r i t h mt oc a r r yo u t i 山东师范大学硕士学位论文 d e s i g no nb r a n dp a t t e r n ，t h et h e r e b yi m i t a t es u c ht h a tt h ea u t o m a t i o nb e i n gi np r o g r e s st o b r a n dp a t t e r na n a ly s e s ，t h er a n d o mp r o d u c e sa n dv a r i o u sb r a n dp a t t e r nc a r r y i n go u th e r e d i t a r y v a r i a t i o n ，t h ea u t o m a t i o np r e p a r a t i o nb ys c r e e n i n gb e i n gi np r o g r e s st ol a r g ea m o u n to fb r a n d p a t t e r na n a l y s e s ，p a t t e r nm a k e so n e so p t i o nt ot h eb r a n d ，g e ts e r i e sr e l e v a n c ep a t t e r nt h e r e b y , a n dc h o o s eo u tt h eb r a n ds u i t a b l eo u to f c a r r y i n go u ta na tl a s tc h o o s e a tl a s t ：，w eh a v ea p p l i e de x p a n s i o nt ob e i n gi np r o g r e s st og e n e t i ca l g o r i t h mp a t t e r n d e s i g n ，w eh a v ep r o v e nt h a tt h es c h e m ec o r r e c t n e s s ，t h ea p p l i c a b i l i t yh a sc a r r i e d o u t i n v e s t i g a t i o na n dd i s c u s s i o no nt og a sa n do t h e r ，h a v eg i v e naf e wo u ta n da p p l i c a t i o nf i e l d a f t e ra p p l i c a t i o nd e s i g n i n gaf i e l di nb r a n dc a r r i e so u ta n a l y s i so ng e n e t i ca l g o r i t h m k e y w o r d s - g e n e t i ca l g o r i t h m ；e v o l u t i o na r i t h m e t i c ；a r t i f i c i a li n t e l l i g e n c ea i ；b r a n d d e s i g n ；b r a n dc l a s s i f y ； i v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的， 本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： 坳永起 导师酶叫膨 学位论文版权使用授权书 本学位论文作者完全了解兰趁有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权邀可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文j 乍者签名掐永缸 签字日期：2 0 07 年、参月g 日 导师签字： m ) 山东师范大学硕士学位论文 第1 章引言 1 1 研究背景 商标是商品的生产者经营者在其生产、制造、加工、拣选或者经销的商品上或者服务 的提供者在其提供的服务上采用的，区别商品或者服务来源的，由文字、图形或者其组合 构成的，具有显著特征的标志。我国最早的商标，可追溯到北宋时期。当时济南有家姓刘 的针铺店，以白兔为商标，颇负盛名。这个商标是用铜版印刷的，近似方形，中间绘有白 兔捣药图，画像鲜明突出。图画的上端横写着店名“济南刘家功夫针铺”，两侧写有“认准 门前白兔儿为记”的条幅，图下方从左到右写关于经商范围、方法和质量要求的告白。 商标通过确保商标注册人享有用以标明商品或服务，或者许可他人使用以获取报酬的 专用权，而使商标注册人受到保护【l 】。保护期限长短不一，但期满之后，只要另外缴付费 用，即可对商标予以续展，次数不限。商标保护是由法院来实施的，在大多数制度中，法 院有权制止商标侵权行为。从广义上讲，商标通过对商标注册人加以奖励，使其获得承认 和经济效益，而对全世界的积极和进取精神起到促进作用。商标保护还可阻止诸如假冒者 之类的不正当竞争者用相似的区别性标记来推销低劣或不同产品或服务的行为。这一制度 能使有技能、有进取心的人们在尽可能公平的条件下进行商品和服务的生产与销售，从而 促进国际贸易的发展。 遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。生物在自然界中 的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生 存特性的机理研究和行为模拟，为人工白适应系统的设计和开发提供了广阔的前景。遗传 算法( g e n e t i ca l g o r i t h m s ，简称g a s ) 就是这种生物行为的计算机模拟中令人瞩目的重要成 果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自 适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。其主要特点 是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更 好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应 地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合 优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的 关键技术之- - 2 】遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决 策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物 山东师范大学硕士学位论文 学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方 便的应用遗传操作算子。 近年来，随着对于遗传算法研究的不断深入完善，有越来越多的人认识了解了遗传算 法，并把它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网络、 工业优化控制和社会科学等方面。特别是在解决旅行商问题、煤气管道的最优控制、通信 网络链接长度的优化问题3 1 、铁路运输计划优化4 1 、喷气式收音机涡轮机的设计5 1 、v l s i 版面设计【6 】、键盘排列优化等问题上遗传算法都取得了很大的成功。在遗传算法的应用中， 本课题将其应用到商标的图案设计，利用遗传算法的遗传交叉变异操作，将传统的商标设 计与遗传算法相结合，从而实现商标图案设计的自动性、方便性、优化性，使商标设计更 为简单灵活，减轻商标设计者的负担。 1 2 本文的主要工作 本文第二部分对遗传算法的发展研究情况进行了介绍，并给出了遗传算法的基本要 素，介绍了遗传算法的定义，对遗传算法的基本模型也做了分析。 第三部分给出了商品商标的综述，给出了商标的定义，商标设计过程中的注意事项， 并介绍了商标的发展。 第四部分给出了具体实现遗传算法应用于商标图案设计，给出并分析了图案设计方 案。 第五部分作为全文的总结，对遗传算法在图案设计中的应用下一步的研究方向进行了 展望。 2 山东师范大学硕士学位论文 第2 章遗传算法理论分析 2 1遗传算法的基本知识 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文的遗传选择和自然淘汰的生物进化过程 的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它是有美国m i c h i g a n 大 学j h o l l a n d 教授于1 9 7 5 年首先提出来的，并出版了颇有影响的专著( ( a d a p t a t i o ni nn a t u r a l a n da r t i f i c i a ls y s t e m s ) ) ，g a 这个名称才逐渐为人所知，j h o l l a n d 教授所提出的g a 通常 为简单遗传算法( s g a ) 。 遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因 编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传 物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 是某种基因组合，它决定 了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决 定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码 的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和 优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适 应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新 的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环 境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想 源于生物遗传学和适者生存的自然规律，是具有“生存+ 检测”的迭代过程的搜索算法【7 】。 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空 间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始 群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法 的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于 并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并 逐渐成为重要的智能算法之一。 3 山东师范大学硕士学位论文 2 1 1 遗传算法的背景 进化算法与其他科学技术一样，都经历一段成长过程，逐渐发展壮大。此过程可大致 分为三个时期：萌芽期、成长期和发展期8 1 。 ( 1 )萌芽期( 5 0 年代后期至7 0 年代初期) 5 0 年代后期，些生物学家着手采用电子计算机模拟生物的遗传系统，尽管 这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。 1 9 6 5 年，德国的l r e c h e n b e r g 等人正式提出进化策略的方法，当时的进化策略 只有一个个体，而且进化操作也只有变异一种。 1 9 6 5 年，美国的l j f o g e l 正式提出进化规划，在计算中采用多个个体组成的 群体，而且只运用变异操作。 6 0 年代期间，美国j h h o l l a n d 在研究自适应系统时，提出系统本身与外部环 境相互协调的遗传算法。1 9 6 8 年，j h h o l l a n d 教授又提出模式理论，它成为遗传算法的 主要理论基础。 1 9 6 7 年，b a g l e y 发表了关于遗传算法应用的论文，在其论文中首次使用“遗传 算法”一词。 ( 2 ) 成长期( 7 0 年代中期至8 0 年代末期) 1 9 7 5 年，j h h o l l a n d 教授的专著自然界和人工系统的适应性( a d a p t m 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 ) ) ) 正式出版，全面地介绍了遗传算法，人们常常把这一事件 视作遗传算法问世的标志，h o l l a n d 也被视作遗传算法的创始人。 1 9 7 5 年，d e j o n g 在其博士论文中结合模式定理进行了大量的纯数值函数优化 计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。 1 9 8 7 年，美国d l a w r e n c e 总结人们长期从事遗传算法的经验，公开出版遗 传 算法和模拟退火( g e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n g ) ) ) 一书，以论文集形式用 大量实例介绍遗传算法。 1 9 8 5 年，作为h o l l a n d 的学生，d e g o l d b e r g 博士出版专著遗传算法 搜索、优化及机器学习( g e n e t i ca l g o r i t h m s i ns e a r c h ，o p t i m i z a t i o na n dm a c h i n e l e a r n i n g ) ) ) ，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为 遗传算法的教科书。 1 9 8 5 年，在美国举行第一届遗传算法国际学术会议( i n t e r n a t i o n a lc o n f e r e n c e 4 山东师范大学硕士学位论文 o ng e n e t i ca l g o r i t h m s ，简称i c g a ) ，与会者交流运用遗传算法的经验。随后，1 9 8 7 ， 1 9 8 9 。1 9 9 1 ，1 9 9 3 ，l9 9 5 及19 9 7 年，每2 年左右都举行一次这种会议。 ( 3 ) 发展期( 9 0 年代以后) ， 9 0 年代，遗传算法不断地向广度和深度发展。 19 9 1 年，d l a w r e n c e 出版遗传算法手册( h a n d b o o ko fg e n e t i ca l g o r i t h m s ) 一书， 详尽地介绍遗传算法的工作细节。 1 9 9 6 年z m i c h a l e w i c z 的专著遗传算法+ 数据结构= 进化程序深入讨论 了遗传算法的各种专门问题。同年，t b a c k 的专著进化算法的理论与实践：进化策略、 进化规划、遗传算法深入阐明进化算法的许多理论问题。 1 9 9 2 年，k o z a 出版专著遗传规划应用自然选择法则的计算机程序设计 ( g e n e t i cp r o g r a m m i n g ：o nt h ep r o g r a m m i n go fc o m p u t e rb ym e a n so fn a t u r a ls e l e c t i o n ) ) ) ，该 书全面介绍了遗传规划的原理及应用实例，标明遗传规划己成为进化算法的一个重要分 支。k o z a 本人也被视作遗传规划的奠基人。 1 9 9 4 年，k o z a 又出版第二部专著遗传规划i i ：可再用程序的自动发现( g e n e t i c p r o g r a m m i n gi i ：a u t o m a t i cd i s c o v e r yo fr e u s a b l ep r o g r a m s ) ) ) ，提出自动定义函数的新概 念，在遗传规划中引入子程序的新技术。同年，k e k i n n e a r 主编遗传规划进展( a d v a n c e s i ng e n e t i cp r o g r a m m i n g ) ) ) ，汇集许多研究工作者有关应用遗传规划的经验和技术。 虽然遗传算法的基本框架已经形成，并且在各种问题的求解和应用中展现了它的特点 和魅力。但是客观地说，遗传算法的理论基础仍不完善。尽管有各种新策略和新提案不断 地被提出，但它们几乎都是针对特定问题而言的，对它们的评估主要也是基于仿真实验， 尚缺乏深刻而具有普遍意义的理论分析。关于遗传算法的研究，主要分成两大类： ( 1 ) 理论研究：研究遗传算法本身的理论基础，包括各种遗传算子在遗传算法中起的作 用、算法的收敛性证明等。但是，该领域目前进展不大【9 】。 ( 2 ) 应用研究：用遗传算法作为工具解决实际问题，包括问题优化、机器学习、遗传算 法的并行实现、人工生命等。这一直是遗传算法的主要研究领域。 2 1 2 遗传算法的基本步骤 生物进化论认为生物的进化过程可以被看成是对种群操作的物理变化过程，这个过程 包括复制、杂交、变异、竞争和选择。复制过程使得种群按指数速度扩张，复制完成对后 代个体的遗传基因的传递；杂交是两个个体的部分基因互换而产生两个新个体；变异是遗 5 山东师范大学硕十学位论文 传基因在传递过程中出现差错；竞争是在有限的生存空间对群体进行压缩；选择是在有限的 生存空间竞争的不可避免的结果；最后适者生存，劣者淘汰。遗传进化算法就是模拟生物进 化过程，由美国j h o l l a n d 教授首先提出来的。这种算法模仿生物遗传进化的步骤，将复制、杂 交、变异、竞争和选择等概念引入到算法中。遗传算法通过作用于染色体上的基因寻找好 的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的 仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染 色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码， 即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个 体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。 对这个新种群进行下一轮进化。这就是遗传算法的基本原理。其步骤如下： a ) 定义一个目标函数，函数值表示可行解的适应性。 b ) 将候选解群体在一定的约束条件下初始化，每一个候选解用一个向量x 来编码，称 为一条染色体，向量的分量代表基因。 c ) 群体中的每一条染色体x i ( i - 1 ，2 ，r ，n ) ，被译码成适于评价的形式，并赋予它一 个适应值( 函数值) 。 d ) 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的 好坏按概率随机选择，进行自我复制，形成新的群体。 e ) 通过随机选择染色体进行遗传操作( 杂交和变异) ，产生子代。杂交是随机选择两条染 色体( x 亲) ，将某一位置的基因互换而产生两个新个体；变异是基因中的某一位发生突变，以 达到产生新品种的目的。 f ) 对子代群体重复步骤c ) e ) 的操作，进行新一轮遗传进化过程，如果找到合适解或 达到最大进化代数，则计算结束。从上述算法可以看出“，优胜劣汰的机制 以及“按概率 复制是为了使新群体的性能提高，“杂交和“变异”的操作是为了产生新的品种。只有 产生新的品种，才能为“优胜劣汰 提供原材料，才有可能找到最优解，从而使算法跳出局部 极值1 0 1 。将“按概率复制”和“杂交”、“变异”结合在一起，则是为了产生好的新品种，以 达到进化的目的。由此可见，遗传进化算法虽属一种随机算法，但它又具有一定的方向性，它 所使用的“按概率随机选择”是在有方向的搜索过程中的一种工具，正是由于它的方向性， 使得它比一般的随机搜索的效率要高。 在遗传算法中，编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个 关键步骤。编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空间的 6 山东师范大学硕士学位论文 基因型变换到解空间的表现型时的解码方法；编码方法也影响到交叉算子、变异算子等遗 传算子的运算方法。 由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化 运算的效率。 针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之 也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完整的指导理论 及评价准则能够帮助我们设计编码方案。作为参考，d ej o n g 曾提出了两条操作性较强的实 用编码原则( 又称为编码规则) ： 1 ) 编码原则一( 有意义积木块编码原则) ：应使用能易于产生与所求问题相关的且具有低 阶、短定义长度模式的编码方案。 2 ) 编码原则二( 最小字符集编码原则) ：应使用能使问题得到自然表示或描述的具有最小编 码字符集的编码方案。 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的 来说，这些编码方法可以分为三大类：二进制编码方法、浮点数编码方法、符号编码方法。 其次，在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量 某个物种对于其生存环境的适应程度。与此相类似，遗传算法中也使用适应度这个概念来 度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。 群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就 是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力，都会有以 相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性可言，只是一种随机 的选择过程。这将导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率。 因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行适当的放大， 扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。 2 1 3 遗传算法的特点与应用 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，在遗传算法中，先建 立工程优化问题的数学模型，将问题的所有解决变量编码，称为一个基因。多个基因形成 一个有限场的编码串，称为染色体。其对应的表现型即个体，都对应予优化问题的一个可 行解，一组个体组成一代种群。优化问题的目标函数作为种群所处的环境，可以得出每个 个体对环境的适应度，由适应度决定该歌体生存的概率。搜索时先随即产生一定数量的原 7 山东师范人学硕十学位论文 始种群，从这些种群开始，模拟进化过程。按每个个体适应度依照概率进行优胜劣汰，从 而使适应度高的个体生存下来。在利用交换、变异等遗产手段，使这些种群的优良特性得 以遗传并保留到下一代。如此“选择一交换一变异一再选择循环往复，使各代的优良基 因成分逐渐累积，种群的平均适应度和最优个体适应度不断上升，直到迭代过程趋于收敛， 从而求得一组最优种群。与传统的优化算法相比，遗传算法主要有以下特点： 1 ) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实 际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中 的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够 方便的应用遗传操作算子。 2 ) 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 3 ) 遗传算法使用多个点的搜索信息，具有隐含并行性。 4 ) 遗传算法使用概率搜索技术，而非确定性规则。 生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们 致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统设计和开发提供了 广阔的前景。遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生 物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优 化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。 虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全清楚 染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点 却为人们所共识： 1 ) 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状； 2 ) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上； 3 ) 生物的繁殖过程是由其基因的复制过程来完成的； 4 ) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。 5 ) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传 到下一代。 由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅 助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一 种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁 棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域： 8 山东师范大学硕士学位论文 1 ) 函数优化。 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多 人构造出了各种各样复杂形式的测试函数：连续函数和离散函数1 1 1 、凸函数和凹函数1 2 】、 低维函数和高维函数1 3 1 、单峰函数和多峰函数等。对于一些非线性、多模型、多目 标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。 2 ) 组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目f i i 的计算上用 枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意 解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化 中的n p 问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、 图形划分问题等方面得到成功的应用。此外，g a 也在生产调度问题16 1 、自动控制1 7 】、机 器人学、图象处理【1 9 】、人工生命 2 0 1 、遗传编码和机器学习蚴等方面获得了广泛的运 用。 3 ) 生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化 之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生 产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工 具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都 得到了有效的应用。 4 )自动控制 在自动控制领域中很多与优化相关的问题需要求解，遗传算法己在其中得到了初步的 应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法 设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、 基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和 权值学习等，都显示出了遗传算法在这些领域中应用的可能性。 5 ) 机器入学 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自 适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗 传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细 胞机器人的结构优化和行为协调等方面得到研究和应用。 9 山东师范大学硕十学位论文 6 ) 图像处理 f 图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、 特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如 何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的 优化计算方面找到了用武之地，日前已在模式识别、图像恢复、图像边缘特征提取等方面 得到了应用。 7 ) ；人工生命 人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特 有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗 传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。 虽然人工生命的研究尚处于启蒙阶段但遗传算法已在其进化模型、学习模型、行为模型、 自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工 生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命 的研究也必将促进遗传算法的进一步发展。 8 ) 遗传编程 k o z a 发展了遗传编程的概念，他使用了以l i s p 语言所表示的编码方法，基于对一种 树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用 也有一些限制，但它己成功地应用于人工智能、机器学习等领域。 9 ) 机器学习 学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是 分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利 用遗传算法来学习隶属度函数，从而更好地改进了模糊系统 的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用 于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规 划系统中得到了成功的应用。 2 1 4 遗传算法的现状 进入9 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了 十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而 且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸 1 0 山东师范大学硕士学位论文 索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传 算法增添了新的活力 2 3 - 2 5 】。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更 新、更工程化的应用方面。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传 算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩 展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智 能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、 模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓2 1 世纪中新的智 能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅 对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四 是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算 机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的 重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划 2 6 1 ( e v o l u t i o np r o g r a m m i n g ，e p ) 以及进化策略( e v o l u t i o ns t r a t