基于遗传算法的商标图案设计.doc

山东师范大学硕士学位论文山东师范大学硕士学位论文基于遗传算法的商标图案设计姓名：曲永超申请学位级别：硕士专业：计算机软件与理论导教师：刘弘20090518关键词：遗传算法；进化计算；人工智能；商标设计；商标分类;ABSTRACTWith the rapid development of society and the economy，enterprise of all kinds are continuing without end, be more being accompanying enterprises, the logo is regarded highly as enterprise sign more and more，but the brand design becomes the important link that enterprise develops, the brand have notable characteristic sign that differentiated a commodity or services source. It is composed of characters，artwork or another combination and applied with making，processing，selecting or being sold by a producer or serving by service provider. The brand is modem economy outcome, it is different from ancient print，the modem sign is bearing the weight of the enterprise intangible assets，is a hereditary synthetical enterprise information intermediary. The logo is the mainest part in enterprises CIS strategy，in the process of enterprise image delivery，it is the broadest and turning up frequency , the same time is also the most key element. The brand has embodied the enterprise overall strength、 perfect the product managing mechanism、 high grade and service, and the brand is remembered by customer t. with the ceaseless stimulation and depict again and again.Genetic Algorithm is a kind of the randomization reconnaissance method using biospheres evolution law (survival of the fittest，survival of the fittest inherit mechanism) for reference evolving but coming. It is to suggested that first in 1975 by American J.Holland professor， whose main characteristic is that the marriage partner carries out operation on structure directly， the nothingness asks lead setting a limit for composing in reply a function continuity; Have the hide concurrence nature and much better inherent overall situation optimizing ability; Adopt probability-rization optimizing method，can voluntarily, gain and guide the searched volume optimizing , adjust direction of search certainly fit in with，not needing the regulation ascertaining that 1. In recent years, studying with Genetic Algorithm is regard to in depth perfect，the more and more people cognition to have known Genetic Algorithm , and apply it in more and more broad field，such as for instance, the machine study about，principles of pattern recognition, image handling，neural networks，industry optimizing the social sciences controlling a sum.The main body of a book is studied mainly making use of Genetic Algorithm to carry outmdesign on brand pattern，The thereby imitate such that the automation being in progress to briand pattern analyses, the random produces and various brand pattern carrying out hereditary variation，the automation preparation by screening being in progress to large amount of brand pattern analyses, pattern makes ones option to the brand，get series relevance pattern thereby, and choose out the brand suitable out of carrying out an at last choose. At last，we have applied expansion to being in progress to Genetic Algorithm pattern design，we have proven that the scheme correctness，the applicability has carried out investigation and discussion on to GAs and other，have given a few out and application field after application designing a field in brand carries out analysis on Genetic Algorithm.Keywords： Genetic Algorithm; Evolution Arithmetic; Artificial intelligence AI ； Brand Design ； Brand Classify ；独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得(注：如没有其他需要特别声明的，本栏可空）或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：导师签字：学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权I可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名：导师签字： Y 签字日期：200 J上月/g日 签字日期：200产工月曰山东师范大学硕士学位论文第1章引言1.1研究背景商标是商品的生产者经营者在其生产、制造、加工、拣选或者经销的商品上或者服务 的提供者在其提供的服务上采用的，区别商品或者服务来源的，由文字、图形或者其组合 构成的，具有显著特征的标志。我国最早的商标，可追溯到北宋时期。当时济南有家姓刘 的针铺店，以白兔为商标，颇负盛名。这个商标是用铜版印刷的，近似方形，中间绘有白 兔揭药图，画像鲜明突出。图画的上端横写着店名“济南刘家功夫针铺”，两侧写有“认准 门前白兔儿为记”的条幅，图下方从左到右写关于经商范围、方法和质量要求的告白。商标通过确保商标注册人享有用以标明商品或服务，或者许可他人使用以获取报酬的 专用权，而使商标注册人受到保护。保护期限长短不一，但期满之后，只要另外缴付费 用，即可对商标予以续展，次数不限。商标保护是由法院来实施的，在大多数制度中，法 院有权制止商标侵权行为。从广义上讲，商标通过对商标注册人加以奖励，使其获得承认 和经济效益，而对全世界的积极和进取精神起到促进作用。商标保护还可阻止诸如假冒者 之类的不正当竞争者用相似的区别性标记来推销低劣或不同产品或服务的行为。这一制度 能使有技能、有进取心的人们在尽可能公平的条件下进行商品和服务的生产与销售，从而 促进国际贸易的发展。遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。生物在自然界中 的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生 存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传 算法(GeneticAlgorithms，简称GAS)就是这种生物行为的计算机模拟中令人瞩目的重要成 果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自 适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。其主要特点 是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更 好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应 地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合 优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的 关键技术之一2遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决 策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物 学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方 便的应用遗传操作算子。近年来，随着对于遗传算法研究的不断深入完善，有越来越多的人认识了解了遗传算 法，并把它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网络、 工业优化控制和社会科学等方面。特别是在解决旅行商问题、煤气管道的最优控制、通信 网络链接长度的优化问题3、铁路运输计划优化【4、喷气式收音机祸轮机的设计【5、VLSI 版面设计6】、键盘排列优化等问题上遗传算法都取得了很大的成功。在遗传算法的应用中， 本课题将其应用到商标的图案设计，利用遗传算法的遗传交叉变异操作，将传统的商标设 计与遗传算法相结合，从而实现商标图案设计的自动性、方便性、优化性，使商标设计更 为简单灵活，减轻商标设计者的负担。1.2本文的主要工作本文第二部分对遗传算法的发展研究情况进行了介绍，并给出了遗传算法的基本要 素，介绍了遗传算法的定义，对遗传算法的基本模型也做了分析。第三部分给出了商品商标的综述，给出了商标的定义，商标设计过程中的注意事项， 并介绍了商标的发展。第四部分给出了具体实现遗传算法应用于商标图案设计，给出并分析了图案设计方案。第五部分作为全文的总结，对遗传算法在图案设计中的应用下一步的研究方向进行了 展望。第2章遗传算法理论分析 2.1遗传算法的基本知识遗传算法（Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程 的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它是有美国Michigan大 学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常 为简单遗传算法（SGA)。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因 编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传 物质的主要载体，即多个基因的集合，其内部表现（即基因型是某种基因组合，它决定 了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决 定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码 的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和 优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适 应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新 的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环 境，末代种群中的最优个体经过解码，可以作为问题近似最优解。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想 源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法【7 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空 间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始 群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法 的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于 并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并 逐渐成为重要的智能算法之一。 2.1.1遗传算法的背景进化算法与其他科学技术一样，都经历一段成长过程，逐渐发展壮大。此过程可大致 分为三个时期：萌芽期、成长期和发展期8】。 (1) 萌芽期（50年代后期至70年代初期） 50年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管 这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。 1965年，德国的L.Rechenberg等人正式提出进化策略的方法，当时的进化策略 只有一个个体，而且进化操作也只有变异一种。 1965年，美国的L.j.Fogel正式提出进化规划，在计算中采用多个个体组成的 群体，而且只运用变异操作。60年代期间，美国J.H.HoUand在研究自适应系统时，提出系统本身与外部环 境相互协调的遗传算法。1968年，J.H.HO丨land教授又提出模式理论，它成为遗传算法的 主要理论基础。 1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传 算法”一词。(2)成长期（70年代中期至80年代末期） 1975年，J.H.Holland教授的专著自然界和人工系统的适应性(Adaptation in Natural and Artificial System)正式出版，全面地介绍了遗传算法，人们常常把这一事件 视作遗传算法问世的标志，Holland也被视作遗传算法的创始人。 1975年，DeJong在其博士论文中结合模式定理进行了大量的纯数值函数优化 计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。 1987年，美国D丄awrence总结人们长期从事遗传算法的经验，公开出版遗 传 算法和模拟退火(Genetic Algorithm and Simulated Annealing)一书，以论文集形式用 大量实例介绍遗传算法。 1985年，作为Holland的学生，D.E.Goldberg博士出版专著遗传算法搜索、优化及机器学习（Genetic Algorithmsin Search, Optimization and MachineLearning),全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为 遗传算法的教科书。 1985年，在美国举行第一届遗传算法国际学术会议(International Conferenceon Genetic Algorithms,简称ICGA)，与会者交流运用遗传算法的经验。随后，1987， 1989,. 1991, 1993，1995及997年，每2年左右都举行一次这种会议。 (3)发展期(90年代以后）90年代，遗传算法不断地向广度和深度发展。 1991 年，D丄awrence 出版遗传算法手册(Handbook of Genetic Algorithms )一书， 详尽地介绍遗传算法的工作细节。 1996年Z.Michalewicz的专著遗传算法+数据结构=进化程序深入讨论 了遗传算法的各种专门问题。同年，T.Back的专著进化算法的理论与实践：进化策略、 进化规划、遗传算法深入阐明进化算法的许多理论问题。 1992年，Koza出版专著遗传规划一应用自然选择法则的计算机程序设计 (Genetic Programmingron the Programming of Computer by Means of Natural Selection)，该 书全面介绍了遗传规划的原理及应用实例，标明遗传规划己成为进化算法的一个重要分 支。Koza本人也被视作遗传规划的奠基人。 1994年，Koza又出版第二部专著遗传规划II ：可再用程序的自动发现(Genetic Programming II :Automatic Discovery of Reusable Programs)，提出自动定义函数的新概 念，在遗传规划中引入子程序的新技术。同年，K.E.Kinnear主编遗传规划进展(Advances in Genetic Programming),汇集许多研究工作者有关应用遗传规划的经验和技术。虽然遗传算法的基本框架已经形成,并且在各种问题的求解和应用中展现了它的特点 和魅力。但是客观地说，遗传算法的理论基础仍不完善。尽管有各种新策略和新提案不断 地被提出，但它们几乎都是针对特定问题而言的，对它们的评估主要也是基于仿真实验， 尚缺乏深刻而具有普遍意义的理论分析。关于遗传算法的研究，主要分成两大类：理论研究：研究遗传算法本身的理论基础，包括各种遗传算子在遗传算法中起的作 用、算法的收敛性证明等。但是，该领域目前进展不大【9。(2)应用研究：用遗传算法作为工具解决实际问题，包括问题优化、机器学习、遗传算 法的并行实现、人工生命等。这一直是遗传算法的主要研究领域。2.1.2遗传算法的基本步驟生物进化论认为生物的进化过程可以被看成是对种群操作的物理变化过程，这个过程 包括复制、杂交、变异、竞争和选择。复制过程使得种群按指数速度扩张，复制完成对后 代个体的遗传基因的传递；杂交是两个个体的部分基因互换而产生两个新个体；变异是遗传基因在传递过程中出现差错；竞争是在有限的生存空间对群体进行压缩；选择是在有限的 生存空间竞争的不可避免的结果;最后适者生存，劣者淘汰。遗传进化算法就是模拟生物进 化过程，由美国J.Holland教授首先提出来的。这种算法模仿生物遗传进化的步骤，将复制、杂 交、变异、竞争和选择等概念引入到算法中。遗传算法通过作用于染色体上的基因寻找好 的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的 15是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染 色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若千个所求解问题的数字编码， 即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个 体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。 对这个新种群进行下一轮进化。这就是遗传算法的基本原理。其步骤如下：a) 定义一个目标函数，函数值表示可行解的适应性。b) 将候选解群体在一定的约束条件下初始化，每一个候选解用一个向量X来编码，称 为一条染色体，向量的分量代表基因。C)群体中的每一条染色体Xi (i = 1，2,，n)，被译码成适于评价的形式，并赋予它一 个适应值(函数值)。d) 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的 好坏按概率随机选择，进行自我复制，形成新的群体。e) 通过随机选择染色体进行遗传操作(杂交和变异)，产生子代。杂交是随机选择两条染 色体(双亲)，将某一位置的基因互换而产生两个新个体；变异是基因中的某一位发生突变，以 达到产生新品种的目的。I f)对子代群体重复步骤C)e)的操作，进行新一轮遗传进化过程，如果找到合适解或 达到最大进化代数，则计算结束。从上述算法可以看出“，优胜劣汰的机制”以及“按概率 零制”是为了使新群体的性能提高，“杂交”和“变异”的操作是为了产生新的品种。只有 产生新的品种，才能为“优胜劣汰”提供原材料，才有可能找到最优解，从而使算法跳出局部 极值，将“按概率复制”和“杂交”、“变异”结合在一起，则是为了产生好的新品种，以 达到进化的目的。由此可见，遗传进化算法虽属一种随机算法，但它又具有一定的方向性，它 所使用的“按概率随机选择”是在有方向的搜索过程中的一种工具,正是由于它的方向性， 使得它比一般的随机搜索的效率要高。在遗传算法中，编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个 关键步骤。编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法；编码方法也影响到交叉算子、变异算子等遗 传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化 运算的效率。针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之 也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完整的指导理论 及评价准则能够帮助我们设计编码方案。作为参考，De Jong曾提出了两条操作性较强的实 用编码原则(又称为编码规则)：1) 编码原则一(有意义积木块编码原则)：应使用能易于产生与所求问题相关的且具有低 阶、短定义长度模式的编码方案。2) 编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的具有最小编 码字符集的编码方案。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的 来说，这些编码方法可以分为三大类：二进制编码方法、浮点数编码方法、符号编码方法。 其次，在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量 某个物种对于其生存环境的适应程度。与此相类似，遗传算法中也使用适应度这个概念来 度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就 是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力，都会有以 相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性可言，只是一种随机 的选择过程。这将导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率。 因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行适当的放大， 扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。2.1.3遗传算法的特点与应用遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，在遗传算法中，先建 立工程优化问题的数学模型，将问题的所有解决变量编码，称为一个基因。多个基因形成 一个有限场的编码串，称为染色体。其对应的表现型即个体，都对应予优化问题的一个可 行解，一组个体组成一代种群。优化问题的目标函数作为种群所处的环境，可以得出每个 个体对环境的适应度，由适应度决定该歌体生存的概率。搜索时先随即产生一定数量的原始种群，从这些种群开始，模拟进化过程。按每个个体适应度依照概率进行优胜劣汰，从 而使适应度高的个体生存下来。在利用交换、变异等遗产手段，使这些种群的优良特性得 以遗传并保留到下一代。如此“选择一交换一变异一再选择”循环往复，使各代的优良基 因成分逐渐累积，种群的平均适应度和最优个体适应度不断上升，直到迭代过程趋于收敛， 从而求得一组最优种群。与传统的优化算法相比，遗传算法主要有以下特点：1) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实 际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中 的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够 方便的应用遗传操作算子。2) 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。3) 遗传算法使用多个点的搜索信息，具有隐含并行性。4) 遗传算法使用概率搜索技术，而非确定性规则。生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们 致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统设计和开发提供了 广阔的前景。遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生 物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优 化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全清楚 染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点 却为人们所共识-1) 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；2) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；3) 生物的繁殖过程是由其基因的复制过程来完.成的；.4) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。5) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传 到下一代。由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅 助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一 种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁 棒件，所以广应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：1) 函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多 人构造出了各种各样复杂形式的测试函数：连续函数和离散函数11】、凸函数和凹函数12、 低维函数和高维函数丨I3】、单峰函数14和多峰函数15等。对于一些非线性、多模型、多目 标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2) 组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用 枚举法很难求出最优解。对这类复杂的问题，人们己经意识到应把主要精力放在寻求满意 解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化 中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、 图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题16、自动控制17】、机 器人学n8】、图象处理ti9、人工生命20、遗传编码【21和机器学习22等方面获得了广泛的运 用。3) 生产调度问题生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化 之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生 产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工 具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都 得到了有效的应用。4) 自动控制在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的 应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法 设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、 基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和 权值学习等，都显示出了遗传算法在这些领域中应用的可能性。5) 机器人学机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自 适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗 传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细 朐机器人的结构优化和行为协调等方面得到研究和应用。6)丨图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、 特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如 何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的 优化计算方面找到了用武之地，日前已在模式识别、图像恢复、图像边缘特征提取等方面 得到了应用。7) i人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特 有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗 传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。 虽然人工生命的研究尚处于启蒙阶段.但遗传算法己在其进化模型、学习模型、行为模型、 自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工 生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命 的研究也必将促进遗传算法的进一步发展。8) 遗传编程Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种 树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用 也有一些限制，但它己成功地应用于人工智能、机器学习等领域。9) 机器学习学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是 分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利 用ii传算法来学习隶属度函数，从而更好地改进了模糊系统 的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用 于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规 划系统中得到了成功的应用。2.1.4遗传算法的现状进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了 十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而 且利用遗传算法进行优化和规则学习的能力也显荖提高，同时产业应用方面的研究也在摸山东师范大学硕士学位论文索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传 算法增添了新的活力23-25】。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更 新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传 算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩 展到具有独特的规则生成功能的薪新的机器学习算法。这一新的学习机制对于解决人工智 能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、 模糊推理以及混纯理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智 能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅 对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四 是遗传算法和另一个称为人工生命的薪新研究领域正不断渗透。所谓人工生命即是用计算 机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的 重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划26 (Evolution Programming,EP)以及进化策略【27 (Evolution Strategy,ES)等进化计算理论 曰益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也 是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特 点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子28】(Adjacency based crossover),这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了 TSP问 题中，通过实验对其进行了验证。D.H.Ackley 等提出了随即迭代遗传爬山法【29_3i ( Stochastic Iterated Genetic Hill-climbing, SIGH)采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同 决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的 神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH 比现存的许多算法在求解速度方面更有竞争力。H.Bersini和GSeront将遗传算法与单一方法（simplex method)结合起来，形成了一 种叫单一操作的多亲交叉算子32 (simplex crossover),该算子在根据两个母体以及一个额 外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同 时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其 佘两个有更好的性能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应 用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变 异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传 算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现 象，提出了一种用基因块编码的并行遗传算法(Bui丨ding-block Coded Parallel GA, BCPGA) 33。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块， 然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编 码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题，探讨了使用弹性策略来维持群体的 多样性，使得算法跨过局部收敛的障碍，向全局最优解方向进化。2.2典型的遗传算法2.2.1简单遗传算法SGA虽然在实际应用中遗传算法的形式出现了不少变型，但这些遗传算法都有共同的特 点，即通过对自然界进化过程中自然选择、交叉、变异机理的模仿，来完成对最优解的搜 索过程34】。基于这个共同的特点，Goldberg总结了一种统一的最基本的遗传算法，该算 法被称为简单遗传算法（SimpleGeneticAlgorithms，SGA), SGA只使用了选择算子、交 叉算子和变异算子这三种遗传算子，其结构简单，易于理解，是其它遗传算法的雏形和基 础。基本遗传算法模型，它是一个反复迭代的进化计算过程，通过对一组表示候选解的个 体进行评价、选择、交叉、变异等操作，来产生新一代的个体(候选解)，这个迭代过程直到 满足某种结束条件为止。 SGA的基本流程如下：1) 初始化，产生初始种群。2) 个体评价，即计算种群中每个个体的适应度。3) 按选择概率Ps，执行选择算子，从当前种群中选择部分个体进入下一代种群。4) 按交叉概率Pc，执行交叉算子。5) 按变异概率Pm，执行变异算子。6) 若满足设定的终止条件，则执行7，否则执行1。13山东师范大学硕士学位论文7)输出种群中适应度最优的个体作为问题的最优解或满意解。 遗传算法的终止条件可以设定为：达到了预先设定的进化代数;(2)种群中的最优个 体在连续若干代中都没有再获得改进;(3)最优个体达到预先设定的满意解。简单遗传算法的遗传操作主要有三种：选择(selection)、交叉(crossover)、变异 (mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。选择操作也叫 复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被- 遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制，令表示群体 的适应度值之总和，/i.表示种群中第/个染色体的适应度值，它产生后代的能力正好为 其适应度值所占份额/ 。/I/,2.2.2交互式遗传算法传统的遗传算法主要解决性能指标明确定义的显式性能指标优化问题，但难以解决性 能指标不能明确定义的隐式性能指标优化问题，而交互式遗传算法将人的智能评价与传统 的进化机制相结合，可以有效解决上述隐式性能指标优化问题。自20世纪80年代被提出 以来，交互式遗传算法已在人脸识别、服装设计、乐曲创作与韵律控制、语S处理、知识 获取与数据挖掘等多个领域得到成功应用。交互式遗传算法研究仍然存在一些不足之处：交互式遗传算法理论f35】，如环境、抽象 模型研究不足；人的疲劳问题是交互式遗传算法的核心问题，但已有的解决方法不能满足 用户需求，算法性能尚需要进一步的提高；奴前尚无多种群协同进化交互式遗传算法的研 究成果；交互式遗传算法中的噪声建模以及相应的降噪声策略也没有成熟的研究成果；如 何利用交互式遗传算法解决混合性能指标优化问题目前仍是研究的空白。2.2.3人工免疫遗传算法遗传算法是一种借鉴生物界自然选择和自然遗传机理的随机化搜索算法，最初的设计 目的和应用主要是在数值优化、组合优化等问题中。多年来，这种算法受到了广泛的关注 和研究，已广泛应用于计算机科学、人工智能、信息技术及工程实践等诸多方面。但是人13们发现遗传算法也会由于各种原因，产生“早熟收敛”，影响全局最优解的搜索。由此而引入 了免疫遗传算法。免疫系统、遗传系统以及神经系统三者，具备大规模并行信息处理能力、强大的学习 能力、记忆能力、识别能力、自适应性和鲁棒性、自组织能力和保持多样性的能力。早 熟收敛，容易陷入局部最优是标准遗传算法存在的致命。通过适应度尺度变换来调节选择 压力是克服这一缺陷的主要方法。但适应度尺度变换是依赖于问题的，通用性稍差。通过 对髙等脊椎动物免疫系统的了解,我们得到了解决问题的一些启示：针对遗传算法早熟收 敛，容易陷入局部最优的缺陷，将免疫浓度调节机制引入到遗传算法，形成免疫遗传算法。免 疫遗传算法采用适应度和浓度两个指标对个体(抗体)进行进化评价,有效地调节了选择压 力，保持了群体的多样性,克服了遗传算法早熟收敛的弱点，提高问题解的质量。为了克服基本遗传算法存在的缺点和不足，将免疫系统中抗体多样性的维持机制引入 遗传算法，同时兼顾个体多样性和提高种群中个体适应度的水平，提出了基于相似性矢量距 为选择概率的免疫遗传算法,并给出了此类概率选择的一般表示形式.为了防止基于相似性 矢量距为选择概率的免疫遗传算法在优化过程中出现退化现象，通过在算法中引入免疫疫 苗的方式，对该算法进一步加以改进.从每一代保优抗体中提取有效信息，进而得到一种新 的疫苗提取方法.在对现有免疫遗传算法研究的基础上，提出一种基于百分比的抗体相似度 定义方法，由此形成一种改进的免疫遗传算法，有效提高算法计算速度、克服早熟收敛。2.2.3并行遗传算法目前开发出来的并行遗传算法虽然种类繁多，但概括起来基本分为二类，即标准型并 行方法和分解型并行方法。标准型并行方法在一个总体的环境中实现进化运算，所以它需要使用一个统一的群 体，实现时也需要有一个全局存储器，还需要有一个统一的控制机构来协调群体的遗传进 化过程及群体之间的通信过程。这种实现方法对遗传算法的运行速度提高不大。分解型并行方法将整个群体分解为几个子群体，各个子群体被分配在不同的节点上， 它们各自运行自己节点上的遗传算法,然后在适当的时候,各节点之间相互交换一些信息， 这种实现方法很容易在计算机集群中实现。首先，这种实现方法比较符合个体自然进化的 过程，所以理解起来比较自然；其次，它充分地利用了遗传算法的天然并行结构和群体特 征，所以实现起来也比较简单；另外，这种方法由于保持了各节点上群体进化的局部特性， 所以这种方法还能够有效地回避遗传算法的早熟现象。因此这种方法在遗传算法的并行化M中得到了广泛的使用。根据对生物不同环境和生存特性的模拟，共有三种不同的群体分组 方法或模型：踏脚石模型36、岛均模型【37、邻接模型38】，相应地就有三种基于不同群体模 型的并行遗传算法。1) 踏脚石群体模型这个模型的各个子群体中所含个体的数量多于1，各个子群体在其节点上并行独立地 运行简单遗传算法，子群体之间的信息交换只能在地理上邻近的处理机之间进行。该模型 由于对处理机之间的通信要求不高，所以实