优纳科技北京有限公司机器视觉部笔试题.doc

优纳科技（北京）有限公司机器视觉部笔试题说明：1 本套笔试题适用于应聘机器视觉/图像处理算法工程师的应聘者。2 本套试题请在1周内完成并发回本公司人力资源部门.E-mail: 。3 应聘者在答题期间可查阅各种参考书和文献，但请确保独立完成，我们期望看到您的智慧火花。4 以下试题中如果有您认为无法解答或不可能解决的问题，请给出您的理由。1 嘉年华中总会有投硬币的游戏，如果硬币完整地落在一个格子里您就可以赢得一个礼物，这个游戏和下面这道题很相似。我们有如下一个平面，平面上是一道道的平行线，平行线间的距离为d, 我们还有一根长度同样为d的木棍（您可以把它简化为一段长度为d的线段），把这根木棍扔到划有平行线的平面上，请问木棍刚好落在平行线间而不会和平行线相交的概率。dd2 请用C/C+语言编写一个或多个函数完成下图中圆形图像（靠近外圆无突出部分的圆形）的检测。主函数申明如下：bool FindCircel(unsigned char *pInImg, int nWidth, int nHeight, float *pCx, float *pCy, float *pR)其中，pInImg 为输入8位图像数据，nWidth和nHeight为输入图像大小，pCx，pCy为输出圆的中心坐标，pR为输出圆的半径。请注意编程风格和效率。Hough 变换cvHoughCircles();3 请任选下面一个或多个主题，从自己认识的角度说明其主要理论和观点。请使用尽量简洁明确的论述。（1）David Marr的视觉计算理论框架 视觉计算理论（computational theory of vision） 从七十年代以来，随着认知心理学自身的发展，认知心理学关于模式识别的研究在取向上出现了某些重要的变化。一些认知心理学家继续在物理符号系统假设的基础上进行研究，探讨计算机和人的识别模式的特点；而另一些认知心理学家则转向用神经网络的思想来研究识别模式的问题。下面介绍的一些模型是近十多年来有重要影响的理论模型。从根本上讲，这些研究取向并不是互相矛盾的，而是互相补充的。视觉计算理论是在20世纪70年代由马尔（David Marr）提出的。1982代表作视觉马尔认为，视觉就是要对外部世界的图像（iamge）构成有效的符号描述，它的核心问题是要从图像的结构推导出外部世界的结构。视觉从图像开始，经过一系列的处理和转换，最后达到对外部现实世界的认识。两个重要概念：表征（representation）：指能把某些客体或几类信息表达清楚的一种形式化系统，以及说明该系统如何行使其职能的若干规则。使用某一表征描述某一实体所得的结果，就是该实体在这种表征下的一个描述。处理（process）：是指某种操作，它促使事物的转换。视觉从接收图像到认识一个在空间内排列的、完整的物体，需要经过一系列的表征阶段。从一种表征转换为另一种表征，必须借助于某些处理过程。零交叉（zero crossing）代表明度的不连续变化或突然变化，是形成物体轮廓的基础。对零交叉的检测就是视觉系统对二维表面轮廓或边界的检测。马尔把视觉图像的形成划分为三个阶段。二维要素图（2-D sketch）。构成二维要素图的基元或基本单位（base unit）为斑点、边缘、棒、端点。这些基元都是在检测零交叉的基础上产生的。2.5维要素图。是按以观察者为中心的坐标框架建构起来的。2.5维要素图依赖于单一的观察点，它的作用是揭示一个图像的表面特征。马尔声称，早期视觉加工的目标就是要建立一个2.5维的要素图，这是把一个表面解释为一个特定的物体或一组物体之前的最后一步。2.5维要素图的建立标志着纯粹知觉过程的结束。不能解释知觉的恒常性（单一观察点）：在人的知觉条件发生变化时，物体的表面特征看起来基本保持不变；而在2.5维要素图中，当观察点改变时，知觉到的特性将出现变化。三维模型表征（3-D model representation）。包含容积、大小和形状的表征。它的坐标系统是以物体为中心，而不是以观察者为中心。它具有不同大小，具有一些简单的可以认识的形状。当三维模型表征建立起来时，其最终结果是对我们能够区别的物体的一种独特的描述。同一物体产生相同的描述，而不管对它的观察角度如何。人和机器的最终目的：了解一个场景或一个图像的意义。阶段如下：计算阶段，形成要素图。视觉系统根据广泛搜集到的特征，如边界、线条和斑点，组成对一个场景的描述。通过符号处理，将线条、点和斑点以不同的方式组织起来，对要素图进行分析，形成2.5维要素图。产生对一个物体的确认。马尔：人脑中已有的知识在视觉处理的早期阶段不起作用，只有在形状已经完全得到分析之后，即知觉的后期阶段，对知觉有重要意义的知识才开始实际地发挥其作用。评论：马尔的视觉理论把视觉研究从描述水平提高到数理科学的严密水平，因而它一出现就深受神经科学家、人工智能专家和认知心理学家的推崇。批评：马尔对视觉的解释主要集中在视觉加工的早期阶段；除要素图以外，他设想的各种表征还没有得到神经生理学的证明。他把知识的作用限制在视觉加工的晚期阶段，也引起要些人的怀疑。还有人认为，知觉开始于大范围拓扑性质的提取，而不是对个别特征的分析。人的视觉系统的功能具有拓扑性，它注重整体性质而忽略局部性质，因而对视觉的计算性质提出了尖锐的挑战。经常听说Marr的视觉计算理论，多少人谈着视觉计算理论的三个层次。今天终于读了一下Marr的视觉计算理论这本书的中译本，看了书中所论述的三个层次，记录下一些要点：与我们人类很多有关的现象其本质上都是信息处理现象。信息处理过程包含了多个层次，我们应在不同的层次上寻求各种不同的解释，这些层次之间相互连接的细节是十分复杂的，而且想要弄清楚这些细节也是不现实地，但至少在原则上它们是被结合成一个内在的统一体的。表象的定义：一种能把某些实体或某几类信息表达清楚的形式化系统（如我们通常使用的阿拉伯数字）信息处理的三个层次：（1）计算理论 它含有两个独立的论点，即计算的是什么东西，为什么要计算这些东西 最后得到的运算仅由它必须满足的约束条件唯一的确定 它实际上是实现一种信息到另一种信息的映射（2）表象和算法 这一层次要进行两个选择：选择处理的输入表象和输出表象 选择一个实际上能完成表象变换的算法 要点：通常有许多可供选择的表象 算法的选择往往主要取决于所使用的特殊的表象 即使对于一个给定的固定表象，也常常有好几种能完成同样处理任务的算法（3）硬件实现：物力上具体实现处理的装置 同一个算法可以用完全不同的技术途径来实现要解释某些现象，要放到其所对应得层次上这三个层次之间是有耦合的，尽管很松散。对于信息处理的观点，至关重要的仍是最高层次即计算理论层次，这是因为构成知觉基础的计算的本质，与其说取决于用以解决计算问题的特殊的硬件，倒不如说取决于必须予以解决的计算问题的本身（2）格式塔（Gestalt）心理学派的主要观点 格式塔心理学派是20世纪初期在德国兴起的心理学派，也称完形心理学派。其创始人魏特曼、考夫卡和柯勒自1910年起密切合作，成为格式塔学派的核心。他们于1921年创立了该学派的刊物心理学研究。在20年代和30年代，他们先后移居美国并吸引了许多支持者。 1912年，魏特曼发表了一篇题为似动的实验研究的论文，标志着格式塔心理学的开始。在格式塔学派创始以前，构造主义心理学派主张对意识经验进行分析，将经验分解为单元或元素。经验元素的相加构成复杂的经验。格式塔学派则主张，人的每一种经验都是一个整体，不能简单地用其组成部分来说明。似动现象是一个整体经验，单个刺激的相加并不能说明似动现象的发生。格式塔学派认为整体大于部分之和。德语中Gestalt(格式塔）的意思是整体或完整的图形。 格式塔学派认为知觉经验服从于某些图形组织的规律。这些规律也叫做格式塔原则，主要有图形和背景原则、接近性原则、相似性原则、连续性原则、完美图形原则等。客观刺激容易按以上的规律被知觉成有意义的图。 在格式塔学派建立后的数十年里，其理论被应用到学习、问题解决、思维等其它领域。格式塔学派认为，条件化的重复性学习是最低级的学习方法，学习是对关系的掌握。在柯勒看来，关系的掌握即是理解过程。一旦学习者知觉到特定情境中各要素间的相互关系，产生出新的经验，就会出现创造性的结果。这种突然贯通的解决问题过程称为顿悟（insight）。 50年代前后，格式塔理论被推广到人格、社会及临床心理学领域里。60年代，新兴的认知心理学吸取了格式塔心理学的某些观点，特别是格式塔心理学对思维研究的成果。目前，格式塔学派在个别领域中仍相当有影响。例如，在知觉研究中，格式塔观点仍占主导地位。但是在当代心理学中，格式塔心理学已经不作为一个独立的学派进行活动了。格式塔（Gestalt）是一个德语词，原意是外形、形状、或者配置。在心理学里用这个词表示的意思是，作为一个有意义的整体而感知到的一组感觉，通过格式塔，思维对进入大脑的各种感觉分辨结构或归纳意义。例如，当我们从不同的角度看一个圆圈时，它看起来总是圆的，对思维结果而言，这一点非常重要，因为那确实是一个圆而不是椭圆。但是，在一个镜头上它有时却是椭圆形的，例如用相机从不同的角度给这个圆拍照，在图片上能明确显示出：从不同的角度上观察这个圆得到的却是些不同形状的椭圆形，虽然事实上它是一个圆。这就是说，思维使我们看到了本质。同样地，当我们从不同的角度看一张桌子时，视网膜上的图像也会改变，可是，我们在内心里体会到的、看见过的那张桌子的经验却不会改变。应用格式塔心理学的原理可以很好地解释其中的原由：这是因为思维在解释感觉时会按自己知道的目标的样子去描述。也就是说，思维能去除掉多种复杂性的干扰而抓住最简单和本质的东西，这就是思维的力量，或者说是认识模式的力量。人类在认知上的这种特点，使思维不至于迷失在复杂的细节之中，而能掌握内在的结构。具体到上述圆圈的例子来说，就是使我们不会因为所处的角度的不同而把一个圆当成一个椭圆。这是认识模式最为重要的一个作用。在格式塔心理学的上百条已被明确的原理中，有一个很重要的原理，叫求简律。正如同自然法则会使一个肥皂泡以最简单的可能形状存在一样，思维也倾向于在复杂的表象中看见整体的最简单、最本质的结构。在思维中培养这种最重要的系统性思考能力， 就是要能在复杂的（现象）中，看出一再重复发生，并起着决定性作用的结构形态来。人类的思维过程是一个试图揭示被认识事物的系统性整体的复杂过程，从系统科学的观点来看，任何一个复杂的系统都是由各种要素及其关系组成的整体。思维通过自组织的过程，对进入头脑的各种信息进行深入的加工，在此过程中将启用一系列智力操作。通常的那些基本的智力操作包括分析、综合、抽象和概括，此外还有比较、分类等。思维通过自组织的过程抓住复杂事物内在的本质结构，并以这种结构化的认识模式拓展自己的认识空间。例如，当我们刚认识一个陌生人的时候，会感知到很多有关其特征的信息，例如圆形脸、双眼皮、高鼻梁等等。下次看到他的时候，他的容貌可能发生了部分的改变，但我们可以凭着一些主要特征来认出他是同一个人，这就是因为思维把握住了那些最为本质的东西某种本质的固有结构（3）Bayes决策理论 bayesian theory 贝叶斯决策理论贝叶斯决策理论概述 贝叶斯决策理论是主观贝叶斯派归纳理论的重要组成部分。 贝叶斯决策就是在不完全情报下，对部分未知的状态用主观概率估计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。 贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是： 已知类条件概率密度参数表达式和先验概率 利用贝叶斯公式转换成后验概率 根据后验概率大小进行决策分类（4）人工神经网络中的BP网络、自组织网络和联想记忆网络的主要内容 人工神经网络（Artificial Neural Networks, ANN），一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力，可以通过预先提供的一批相互对应的输入输出数据，分析掌握两者之间潜在的规律，最终根据这些规律，用新的输入数据来推算输出结果，这种学习分析的过程被称为“训练”。（引自环球科学2007年第一期神经语言：老鼠胡须下的秘密） 概念 由大量处理单元互联组成的非线性、自适应信息处理系统。它是在现代神经科学研究成果的基础上提出的，试图通过模拟大脑神经网络处理、记忆信息的方式进行信息处理。 人工神经网络具有四个基本特征： （1）非线性 非线性关系是自然界的普遍特性。大脑的智慧就是一种非线性现象。人工神经元处于激活或抑制二种不同的状态，这种行为在数学上表现为一种非线性关系。具有阈值的神经元构成的网络具有更好的性能，可以提高容错性和存储容量。 （2）非局限性 一个神经网络通常由多个神经元广泛连接而成。一个系统的整体行为不仅取决于单个神经元的特征，而且可能主要由单元之间的相互作用、相互连接所决定。通过单元之间的大量连接模拟大脑的非局限性。联想记忆是非局限性的典型例子。 （3）非常定性 人工神经网络具有自适应、自组织、自学习能力。神经网络不但处理的信息可以有各种变化，而且在处理信息的同时，非线性动力系统本身也在不断变化。经常采用迭代过程描写动力系统的演化过程。 （4）非凸性 一个系统的演化方向，在一定条件下将取决于某个特定的状态函数。例如能量函数，它的极值相应于系统比较稳定的状态。非凸性是指这种函数有多个极值，故系统具有多个较稳定的平衡态，这将导致系统演化的多样性。 人工神经网络中，神经元处理单元可表示不同的对象，例如特征、字母、概念，或者一些有意义的抽象模式。网络中处理单元的类型分为三类：输入单元、输出单元和隐单元。输入单元接受外部世界的信号与数据；输出单元实现系统处理结果的输出；隐单元是处在输入和输出单元之间，不能由系统外部观察的单元。神经元间的连接权值反映了单元间的连接强度，信息的表示和处理体现在网络处理单元的连接关系中。人工神经网络是一种非程序化、适应性、大脑风格的信息处理，其本质是通过网络的变换和动力学行为得到一种并行分布式的信息处理功能，并在不同程度和层次上模仿人脑神经系统的信息处理功能。它是涉及神经科学、思维科学、人工智能、计算机科学等多个领域的交叉学科。 人工神经网络是并行分布式系统，采用了与传统人工智能和信息处理技术完全不同的机理，克服了传统的基于逻辑符号的人工智能在处理直觉、非结构化信息方面的缺陷，具有自适应、自组织和实时学习的特点。 历史沿革 1943年，心理学家W.S.McCulloch和数理逻辑学家W.Pitts建立了神经网络和数学模型，称为MP模型。他们通过MP模型提出了神经元的形式化数学描述和网络结构方法，证明了单个神经元能执行逻辑功能，从而开创了人工神经网络研究的时代。1949年，心理学家提出了突触联系强度可变的设想。60年代，人工神经网络的到了进一步发展，更完善的神经网络模型被提出，其中包括感知器和自适应线性元件等。M.Minsky等仔细分析了以感知器为代表的神经网络系统的功能及局限后，于1969年出版了Perceptron一书，指出感知器不能解决高阶谓词问题。他们的论点极大地影响了神经网络的研究，加之当时串行计算机和人工智能所取得的成就，掩盖了发展新型计算机和人工智能新途径的必要性和迫切性，使人工神经网络的研究处于低潮。在此期间，一些人工神经网络的研究者仍然致力于这一研究，提出了适应谐振理论（ART网）、自组织映射、认知机网络，同时进行了神经网络数学理论的研究。以上研究为神经网络的研究和发展奠定了基础。1982年，美国加州工学院物理学家J.J.Hopfield提出了Hopfield神经网格模型，引入了“计算能量”概念，给出了网络稳定性判断。 1984年，他又提出了连续时间Hopfield神经网络模型，为神经计算机的研究做了开拓性的工作，开创了神经网络用于联想记忆和优化计算的新途径，有力地推动了神经网络的研究，1985年，又有学者提出了波耳兹曼模型，在学习中采用统计热力学模拟退火技术，保证整个系统趋于全局稳定点。1986年进行认知微观结构地研究，提出了并行分布处理的理论。人工神经网络的研究受到了各个发达国家的重视，美国国会通过决议将1990年1月5日开始的十年定为“脑的十年”，国际研究组织号召它的成员国将“脑的十年”变为全球行为。在日本的“真实世界计算（RWC）”项目中，人工智能的研究成了一个重要的组成部分。 基本内容 人工神经网络模型主要考虑网络连接的拓扑结构、神经元的特征、学习规则等。目前，已有近40种神经网络模型，其中有反传网络、感知器、自组织映射、Hopfield网络、波耳兹曼机、适应谐振理论等。根据连接的拓扑结构，神经网络模型可以分为： （1）前向网络 网络中各个神经元接受前一级的输入，并输出到下一级，网络中没有反馈，可以用一个有向无环路图表示。这种网络实现信号从输入空间到输出空间的变换，它的信息处理能力来自于简单非线性函数的多次复合。网络结构简单，易于实现。反传网络是一种典型的前向网络。 （2）反馈网络 网络内神经元间有反馈，可以用一个无向的完备图表示。这种神经网络的信息处理是状态的变换，可以用动力学系统理论处理。系统的稳定性与联想记忆功能有密切关系。Hopfield网络、波耳兹曼机均属于这种类型。 学习是神经网络研究的一个重要内容，它的适应性是通过学习实现的。根据环境的变化，对权值进行调整，改善系统的行为。由Hebb提出的Hebb学习规则为神经网络的学习算法奠定了基础。Hebb规则认为学习过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。在此基础上，人们提出了各种学习规则和算法，以适应不同网络模型的需要。有效的学习算法，使得神经网络能够通过连接权值的调整，构造客观世界的内在表示，形成具有特色的信息处理方法，信息存储和处理体现在网络的连接中。 根据学习环境不同，神经网络的学习方式可分为监督学习和非监督学习。在监督学习中，将训练样本的数据加到网络输入端，同时将相应的期望输出与网络输出相比较，得到误差信号，以此控制权值连接强度的调整，经多次训练后收敛到一个确定的权值。当样本情况发生变化时，经学习可以修改权值以适应新的环境。使用监督学习的神经网络模型有反传网络、感知器等。非监督学习时，事先不给定标准样本，直接将网络置于环境之中，学习阶段与工作阶段成为一体。此时，学习规律的变化服从连接权值的演变方程。非监督学习最简单的例子是Hebb学习规则。竞争学习规则是一个更复杂的非监督学习的例子，它是根据已建立的聚类进行权值调整。自组织映射、适应谐振理论网络等都是与竞争学习有关的典型模型。 研究神经网络的非线性动力学性质，主要采用动力学系统理论、非线性规划理论和统计理论，来分析神经网络的演化过程和吸引子的性质，探索神经网络的协同行为和集体计算功能，了解神经信息处理机制。为了探讨神经网络在整体性和模糊性方面处理信息的可能，混沌理论的概念和方法将会发挥作用。混沌是一个相当难以精确定义的数学概念。一般而言，“混沌”是指由确定性方程描述的动力学系统中表现出的非确定性行为，或称之为确定的随机性。“确定性”是因为它由内在的原因而不是外来的噪声或干扰所产生，而“随机性”是指其不规则的、不能预测的行为，只可能用统计的方法描述。混沌动力学系统的主要特征是其状态对初始条件的灵敏依赖性，混沌反映其内在的随机性。混沌理论是指描述具有混沌行为的非线性动力学系统的基本理论、概念、方法，它把动力学系统的复杂行为理解为其自身与其在同外界进行物质、能量和信息交换过程中内在的有结构的行为，而不是外来的和偶然的行为，混沌状态是一种定态。混沌动力学系统的定态包括：静止、平稳量、周期性、准同期性和混沌解。混沌轨线是整体上稳定与局部不稳定相结合的结果，称之为奇异吸引子。一个奇异吸引子有如下一些特征：（1）奇异吸引子是一个吸引子，但它既不是不动点，也不是周期解；（2）奇异吸引子是不可分割的，即不能分为两个以及两个以上的吸引子；（3）它对初始值十分敏感，不同的初始值会导致极不相同的行为。 发展趋势 人工神经网络特有的非线性适应性信息处理能力，克服了传统人工智能方法对于直觉，如模式、语音识别、非结构化信息处理方面的缺陷，使之在神经专家系统、模式识别、智能控制、组合优化、预测等领域得到成功应用。人工神经网络与其它传统方法相结合，将推动人工智能和信息处理技术不断发展。近年来，人工神经网络正向模拟人类认知的道路上更加深入发展，与模糊系统、遗传算法、进化机制等结合，形成计算智能，成为人工智能的一个重要方向，将在实际应用中得到发展。将信息几何应用于人工神经网络的研究，为人工神经网络的理论研究开辟了新的途径。神经计算机的研究发展很快，已有产品进入市场。光电结合的神经计算机为人工神经网络的发展提供了良好条件。自组织神经网络多层感知器的学和分类是已知一定的先验知识为条件的，即网络权值的调整 是在监督情况下进行的。而在实际应用中，有时并不能提供所需的先验知识，这 就需要网络具有能够自学习的能力。Kohonen提出的自组织特征映射图就是这种 具有自学习功能的神经网络。这种网络是基于生理学和脑科学研究成果提出的。 脑神经科学研究表明：传递感觉的神经元排列是按某种规律有序进行的，这种排 列往往反映所感受的外部刺激的某些物理特征。例如，在听觉系统中，神经细胞 和纤维是按照其最敏感的频率分布而排列的。为此，Kohonen认为，神经网络在 接受外界输入时，将会分成不同的区域，不同的区域对不同的模式具有不同的响 应特征，即不同的神经元以最佳方式响应不同性质的信号激励，从而形成一种拓 扑意义上的有序图。这种有序图也称之为特征图，它实际上时一种非线性映射关 系，它将信号空间中各模式的拓扑关系几乎不变地反映在这张图上，即各神经元 的输出响应上。由于这种映射是通过无监督的自适应过程完成的，所以也称它为 自组织特征图。 在这种网络中，输出节点与其邻域其它节点广泛相连，并相互激励。输入节 点和输出节点之间通过强度Wij(t)相连接。通过某种规则，不断地调整Wij(t)， 使得在稳定时，每一邻域的所有节点对某种输入具有类似的输出，并且这聚类的 概率分布与输入模式的概率分布相接近。 完成自组织特征映射的算法较多。下面给出一种常用的自组织算法： (1)权值初始化并选定邻域的大小； (2)输入模式； (3)计算空间距离dj(dj是所有输入节点与连接强度之差的平方和）。 (4)选择节点j，它满足min(dj)； (5)改变j，和其邻域节点的连接强度； (6)回(2)，直到满足dj(i) BP (Back Propagation)神经网络是一种神经网络学习算法。其由输入层、中间层、输出层组成的阶层型神经网络，中间层可扩展为多层。相邻层之间各神经元进行全连接，而每层各神经元之间无连接，网络按有教师示教的方式进行学习，当一对学习模式提供给网络后，各神经元获得网络的输入响应产生连接权值（Weight）。然后按减小希望输出与实际输出误差的方向，从输出层经各中间层逐层修正各连接权，回到输入层。此过程反复交替进行，直至网络的全局误差趋向给定的极小值，即完成学习的过程。（5）基因算法 基因算法应该叫遗传算法（GA) 遗传算法(Genetic Algorithm,GA)是一种抽象于生物进化过程的 、基于自然选择和生物遗传机制的优化技术. 遗传算法的基本原理 在遗传算法的执行过程中,每一代有许多不同的种群个体(染色体 )同时存在。这些染色体中哪个保留(生存)、哪个淘汰(死亡),是根据 它们对环境的适应能力来决定的,适应性强的有更多的机会保留下来 。适应性强弱是通过计算适应性函数f(x)的值来判别的,这个值称为 适应值。适应值函数f(x)的构成与目标函数有密切关系,往往是目标 函数的变种。主要的遗传算子有如下几种: 1.选择(Selection)算子 又称复制(reproduction)、繁殖算子。选择是从种群中选择生命 力强的染色体,产生新种群的过程。选择的依据是每个染色体的适应 值大小,适应值越大,被选中的概率就越大,其子孙在下一代产生的个 数就越多。选择的方法根据不同的问题,采用不同的方案。最常见的 方法有比率法、排列法和比率排列法。 2.交叉(Crossover)算子 又称重组(recombination)、配对(breeding)算子。当许多染色 体相同或后代的染色体与上一代没有多大差别时,可通过染色体重组 来产生新一代染色体。染色体重组分两个步骤进行:首先,在新复制的 群体中随机选取两个染色体,每个染色体由多个位(基因)组成;然后, 沿着这两个染色体的基因随机取一个位置,二者互换从该位置起的末 尾部分基因。例如,有两个用二进制编码的个体A和B,长度L=5,A=a1a2 a3a4a5,B=b1b2b3b4b5。随机选择一个整数k1,L-1,设k=4,经交叉 后变为: A=a1a2a3|a4a5 A=a1a2a3b4b5 B=b1b2b3|b4b5 B=b1b2b3a4a5 遗传算法的有效性主要来自选择和交叉操作,尤其是交叉,在遗传 算法中起着核心作用。 3.变异(Mutation)算子 选择和交叉算子基本上完成了遗传算法的大部分搜索功能,而变 异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率 ,随机改变字符串某个位置上的值。在二进制编码中,就是将0变成1, 将1变成0。变异发生的概率极低(一般取值在0.0010.02之间)。它 本身是一种随机搜索,但与选择、交叉算子结合在一起,就能避免由复 制和交叉算子引起的某些信息的永久性丢失,从而保证了遗传算法的 有效性。 传算法是多学科结合与渗透的产物,已经发展成一种自组织、 自适应的综合技术,广泛应用在计算机科学、工程技术和社会科学等 领域。其研究工作主要集中在以下几个方面 1.基础理论 包括进一步发展遗传算法的数学基础,从理论和试验研究它们的 计算复杂性。在遗传算法中,群体规模和遗传算子的控制参数的选取 非常困难,但它们又是必不可少的试验参数。在这方面,已有一些具有 指导性的试验结果。遗传算法还有一个过早收敛的问题,怎样阻止过 早收敛也是人们正在研究的问题之一。 2.分布并行遗传算法 遗传算法在操作上具有高度的并行性,许多研究人员都在探索在 并行机和分布式系统上高效执行遗传算法的策略。对分布并行遗传算 法的研究表明,只要通过保持多个群体和恰当控制群体间的相互作用 来模拟并行执行过程,即使不使用并行计算机,也能提高算法的执行效 率。 3.分类系统 分类系统属于基于遗传算法的机器学习中的一类,包括一个简单 的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统 。分类系统被人们越来越多地应用在科学、工程和经济领域中,是目 前遗传算法研究中一个十分活跃的领域。 4.遗传神经网络 包括连接权、网络结构和学习规则的进化。遗传算法与神经网络 相结合,正成功地用于从时间序列分析来进行财政预算。在这些系统 中,训练信号是模糊的,数据是有噪声的,一般很难正确给出每个执行 的定量评价。如果采用遗传算法来学习,就能克服这些困难,显著提高 系统性能。Muhlenbein分析了多层感知机网络的局限性,并猜想下一 代神经网络将是遗传神经网络。 5.进化算法 模拟自然进化过程可以产生鲁棒的计算机算法进化算法。遗 传算法是其三种典型的算法之一,其余两种算法是进化规划(Evolutio nary Programming,EP)和进化策略(Evolutio nary Strategies,ES) 。这三种算法是彼此独立地发展起来的。进化规划最早由美国的L.J. Fogel、A.J.Owens和M.J.Walsh提出;进化策略则由德国的I.Rechenb erg和H.P.Schwefel建立。 具体应用也很广， 我就拿它解决了好几个难题。 下面我给出我们校数学建模时的程序你分析一下就明白了。 #define Ins 35 /*指令数*/ #define Com 45/*部件数*/ #define Row 100 #define JCn 0*Row/*交叉的概率*/ #define FZn .15*Row #define PY Row-JCn-FZn #define times 1000 /*迭代次数*/ #define hyR .4*Ins/*交叉概率*/ #define Optnum 5 /*最优解的个数*/ #include stdlib.h #include time.h #include stdio.h #include conio.h unsigned char *ARow+1; /*遗传矩阵*/ unsigned char *AimgRow+1; /*A的备份*/ unsigned long AusedRow+1; unsigned long AcomnumRow+1; unsigned long AinsnumRow+1; unsigned long OptOptnum+1Ins+1; /*最优的解*/ unsigned long OptinsOptnum+1; /*最优解的指令个数*/ double adaIns+1; /*行适应度*/ char insIns+1Com+1=0,0,4,8,20,31,44,0,8,19,22,29,37,0,2,16,34,33,32, 0,7,11,35,30,0,5,13,18,21,0,1,7,9,23,25, 0,3,5,6,14,24,0,7,20,21,32,35,0,9,15,20,45, 0,6,10,39,42,43,0,1,11,21,34,38,0,2,4,18,22,37, 0,6,17,25,36,0,22,33,34,38,0,2,10,20,37, 0,9,24,29,39,0,15,18,29,31,0,4,42,44,45, 0,13,23,26,39,0,7,12,40,41,0,12,16,19,28,35, 0,6,23,27,45,0,33,37,40,41,0,3,17,19,36, 0,16,33,44,45,0,13,19,24,25,0,2,3,5,8, 0,4,7,9,12,43,0,16,17,20,32,0,28,33,34,36, 0,10,23,25,27,0,1,5,44,45,0,11,15,18,43, 0,7,14,22,36,0,3,15,25,39 ;/*促使*/ char inslenIns+1=0,15,80,30,12,7,19,32,12,45,36,57,78,65,53,34,48,46,32,26,22,26,19,17,22,10,30,82,73,66,55,24,46,37,77,9;/*指令长度*/ unsigned long step=0; void iniA(void); /*初始化A*/ void adaRate(void); /*适应度*/ void judge(void); /*判断*/ void elim(void); /*选取:最优的五个解*/ void JC(void); /*交叉*/ void FZ1(void); /*复制*/ void PY1(void); /*变异*/ void back(void); void showA(void); /*给出A*/ void showOpt(void); /*给出最优解*/ double rnd(void); /*给出01间的随机数*/ void main(void) randomize(); iniA(); while(1) adaRate(); judge(); elim(); if(step+=times) break; JC(); FZ1(); PY1(); back(); showOpt(); void iniA(void) unsigned long i,j,knum=0; for(i=1;i=Row;i+) Ai=(unsigned char *)malloc(sizeof(char)*(Ins+1); Aimgi=(unsigned char *)malloc(sizeof(char)*(Ins+1); for(i=1;i=Row;i+) for(j=1;j0.5) Aij=1; else aij=0; for(i=1;i=Optnum;i+) for(j=1;j=Ins;j+) Optij=1; Optinsi+=inslenj; void adaRate(void) unsigned long i,j,k; double insnum,comnum; int iscomCom+1; /* 部件是否出现 *