人工智能课程报告.docx

轻工大学数计学院人工智能课设报告名 称：人工智能算法的应用班级： 信计1201姓 名:相军学号：1205130122指导教师:曾山学年学期：20152016学年第一学期2015年12月11 日1矢口识简介32发展概况.43研究与应用54遗传算法的研究65实验结果76课设总结87附录文件91知识简介人工智能概述人工智能（Artificial Intelligence，简称AI）,是相对自然人的天然智能而 言，即用人工的方法和技术，模仿、延伸和扩展人的智能，实现某些“机器思维气作为计算机学科的一个重要分支，是由McCarthy于1956年在 Dartmouth学会上正式提出，在当前被人们称为世界三大尖端技术之一。美国 斯坦福大学著名的人工智能研究中心尼尔逊（Nilson）教授这样定义人工智能“人 工智能是关于知识的学科一一怎样表示知识以及怎样获得知识并使用知识的学 科”，另一名著名的美国大学MIT的Winston教授认为“人工智能就是研究如 何使计算机去做过去只有人才能的智能的工作”。除此之外，还有很多关于人工 智能的定义，今尚未统一，但这些说法均反映了人工智能学科的基本思想和基本 容，由此可以将人工智能概括为研究人类智能活动的规律，构造具有一定智能行 为的人工系统。2发展概况人工智能（Artificial Intelligence）自 1956年正式问世以来的五十年间已 经取得了长足的进展，由于其应用的极其广泛性及存在的巨大研究开发潜力，吸 引了越来越多的科技工作者投入人工智能的研究中去。尤其是八十年代以来出现 了世界围的开发新技术的高潮，许多发达国家的高科技计划的重要容是计算机 技术，而尤以人工智能为其基本重要组成部分。人工智能成为国际公认的当代高 技术的核心部分之一。人工智能的发展历史自古以来，人类就力图根据自己的认识水平和当时的技术条件,企图用机器来 代替人的部分脑力劳动，以提高征服自然的能力。公元850年，古希腊就有制造 机器人帮助人们劳动的传说。在我国公元前900多年，也有歌舞机器人传说的记 载，这说明古代人就有人工智能的幻想。随着历史的发展，到十二世纪末至十三 世纪初，西班牙的神学家和逻辑学家Romen Luee试图制造能解决各种问题 的通用逻辑机。十七世纪法国物理学家和数学家B - Pascal制成了世界第一台 会演算的机械加法器并获得实际应用。随后德国数学家和哲学家G -W -Leibniz 在这台加法器的基础上发展并制成了进行全部四则运算的计算器。他还提出了逻 辑机的设计思想，即通过符号体系，对对象的特征进行推理，这种“万能符号” 和“推理计算”的思想是现代化“思考”机器的萌芽，因而他被后人誉为数 理逻辑的第一个奠基人。 接着，英国数学家、 逻辑学家Boole初步实现了 LeibniZ关于思维符号化和数学化的思想，提出了一种崭新的代数系统，这就是 后来在计算机上广泛应用的布尔代数。十九世纪末英国数学和力学家 C - Babbage致力于差分机和分析机的研究，虽因条件限制未能完全实现, 但其设计思想不愧为当年人工智能的最高成就。进入二十世纪后，人工智能相继出现若干开创性的工作。1936年，年仅24岁的英国数学家A-M- Turing在他的一篇“理想计 算机”的论文中，就提出了著名的图林机模型，1945年他进一步论述了电子数 字计算机的设计思想，1950年他又在“计算机能思维吗？ ”一文中提出了机器 能够思维的论述，可以说这些都是图林为人工智能所作的杰出贡献。1946年美 国科学家J - W- Mauchly等人制成了世界上第一台电子数字计算机ENIAC。 随后又有不少人为计算机的实用化不懈奋斗，其中贡献卓著的应当是 VonNeomann。目前世界上占统治地位的依然是诺依曼计算机。电子计算 机的研制成功是许多代人坚持不懈地努力的结果。这项划时代的成果为人工智能 研究奠定了坚实的物质基础。同一时代，美国数学家N Wiener控制论的创立, 美国数学家CE Shannon信息论的创立，英国生物学家WRAshby所 设计的电脑等，这一切都为人工智能学科的诞生作了理论和实验工具的巨大贡 献。1.1形成时期(1956- 1961年)1956年夏季，在美国Dartmouth大学，由年青数学助教J Mdarthy和 他的三位朋友 M minsky、N Lochester和C Shannor共同发起，邀请 IBM 公司的 T More 和 A Samuel、MIT 的 O Self-ridge 和 R Solomonff 以及RAND公司和Carnagie工科大学的A Newell和H，A Simon等 人参加夏季学术讨论班，历时两个月。这十位学者都是在数学神经生理学、心 理学、信息论和计算机科学等领域中从事教学和研究工作的学者，在会上他们 第一次正式使用了人工智能(AI )这一术语，从而开创了人工智能的研究方向。 这次历史性的聚会被认为是人工智能学科正式诞生的标志，从此在美国开始形 成了以人工智能为研究目标的几个研究组：如Newell和Simon的 Carnegie- RAND协作组；Samuel和 Gelernter的IBM 公司工程课题研 究组；Minsky和McCarthy的MIT研究组等，这一时期人工智能的主要研究 工作有下述几个方面：1957年A Newells J Shaw 和H Siomon等人的心 理学小组编制出一个称为逻辑理论机LT(The Logic Theory Machine)的数学 定理证明程序，当时该程序证明了 B A W Russell和A N Whitehend和 “数学原理”一书第二章中的38个定理。后来他们又揭示了人在解题时的思维过程大致可归结为三个阶段：(1 )先想出大致的解题计划；（2 ）根据记忆中的公理、定理和推理规则组织解题过程;（3）进行方法和目的分析，修正解题计划。这种思维活动不仅解数学题时如 此，解决其他问题时也大致如此。基于这一思想他们于1960年又编制了能解十 种类型不同课题的通用问题求解程序GPS（General Problem Solving），另外他 们还发明了编程的 表处理技术和NSS国际象棋机，和这些工作有 联系的 Newell关于自适应象棋机的论文和Simon关于问题求解和决策过程中合理选 择和环境影响的行为理论的论文，也是当时信息处理研究方面的巨大成就。1956年Samuel研究的具有自学习、自组织、自适应能力的西洋跳棋程序 是IBM小组有影响的工作,这个程序可以像一个优秀棋手那样，向前看几步来下 棋。它还能学习棋谱，在分析大约1 75000幅不同棋局后，可猜测出书上所有推荐 的走步，准确度达48%，这是机器模拟人类学习过程卓有成就的探索。1959年这 个程序曾战胜设计者本人,1962年还击败了美国一个州的跳棋大师。在MIT小组，1959年McCarthy发明的表（符号）处理语言LISP，成为 人工智能程序设计的主要语言，至今仍被广泛采用。1958年McCarthy建立的 行动计划咨询系统以及1960年Minsky的论文“走向人工智能的步骤”，对人 工智能的发展都起了积极的作用。此外，1956年NChomsky的文法体系, 1958年Selfridge等人的模式识别系统程序等堵S对人工智能的研究产生有益的 影响。这些早期成果，充分表明人工智能作为一门新兴学科正在茁壮成长。1.2发展时期（1961年以后）上世纪六十年代以来，人工智能的研究活动越来越受到重视。为了揭示智能的 有关原理，研究者们相继对问题求解、博弈、定理证明、程序设计、机器视觉、自 然语言理解等领域的课题进行了深入的研究。四十多年来,不仅使研究课题有所 扩展和深入，而且还逐渐搞清了这些课题共同的基本核心问题以及它们和其他学 科间的相互关系。1974年NJNillson对发展时期的一些工作写过一篇综述 论文，他把人工智能的研究归纳为四个核心课题和八个应用课题。这四个具有一 般意义的核心课题是:(1 )知识的模型化和表示方法;(2 )启发式搜索理论;(3 ) 各种推理方法(演绎推理、规划、常识性推理、归纳推理等)；(4 )人工智能 系统结构和语言。这些课题的新成果极推动了人工智能应用课题的研究。这八个 应用课题是：(1 )自然语言理解(Natural Language Under-standing ) 数据 库的智 能检索(Intelligent Retrieval fromDatabase )( 3 ) 专家 咨询系统(Expert Consulting Systems ) (4)定理证明(Theorem Proving ) 博 弈(Game Playing ) (6)机器人 学(Robotics ) (7)自动程序设计 (Automatic Programming ) (8)组合调度问题 (Combinatorial and Scheduling Problems )。这一时期学术交流的发展对人工智能的研究有很大 推动作用。1969年国际人工智能联合会成立，并举行第一次学术会议IJCAI- 69 ( International Joint Conference On Artificial Intelligence ) 以后每两年 召开一次。随着人工智能研究的发展，1974年又成立了欧洲人工智能学会，并召 开第一次会议 ECAI ( European Con-ference On Artificial Intelligence ), 也是相隔两年召开一次。此外，许多国家也都有本国的人工智能学术团体。在人 工智能刊物方面，1970年创办了Artificial Intelligence国际性期刊，爱丁 堡大学还不定期出版<<Machine Intelligence>>杂志，还有IJCAI会议文集, ECAI会议文集等。另外许多国际知名刊物也刊载人工智能的论著。1.3繁荣时期上世纪九十年代以来，人工智能研究出现了新的高潮。这一方面是因为在人工智能理论方面有了新的进展，另一方面也是因为计算机硬件突飞猛进的发展。随着计算机速度的不断提高、存储容量的不断扩大、价格的不断降低以及网络 技术的不断发展，许多原来无法完成的工作现在已经能够实现。因此，人工智能研 究也就进入繁荣期。目前人工智能研究的3个热点是：智能接口、数据挖掘、主 体及多主体系统。其中某些技术已经实用化。技术的发展总是超乎人们的想象， 从目前的一些前瞻性研究可以看出未来人工智能可能会向以下几个方面发展： 模糊处理、并行化、神经网络和机器情感。人工智能一直处于计算机技术的前沿, 人工智能研究的理论和发现在很大程度上将决定计算机技术的发展方向。今天， 已经有很多人工智能研究的成果进入人们的日常生活。将来，人工智能技术的发 展将会给人们的生活、工作和教育等带来更大的影响。人工智能是计算机科学、控制论、信息论、神经生理学、心理学、语言学等 多种学科互相渗透而发展起来的一门综合性学科，就其本质而言，它是研究如何制 造出人造的智能机器或智能系统，来模拟人类智能活动的能力，以延伸人们智能 的科学。计算机所要模拟的人类智能活动的能力,具体地可以概括为：(1 )通过视觉、听觉、触觉等感官活动，接受并理解文字、图象、声音、 语言等各种外界的“自然信息”，这就是认识和理解世界环境的能力。(2 )通过人脑的生理与心理活动以及有关的信息处理过程，将感性知识抽象 为理性知识，并能对事物运动的规律进行分析，判断和推理，这就是提出概念, 建立方法，进行演绎和归纳推理，作出决策的能力。(3 )通过教育、训练和学习过程，日益丰富自身的知识和技能，这就是学习 的能力。(4 )对变化多端的外界环境条件，如干扰、刺激等作用能灵活地作出反应, 这就是自我适应的能力。针对以上人类智能活动的能力,目前研究人工智能主要有两条途径。一条是心 理学家、生理学家们希望搞清大脑信息处理过程的机理。他们认为大脑是智能活 动的物质基础，要揭示人类智能的奥秘，就必须弄清大脑的结构，也就是要从大脑 的神经元模型着手研究。显然由于人脑有上百亿神经元，而且现阶段要进行人脑 的物理模拟实验很困难,因而完成这个任务极其艰巨。但是这一学派试图创立“信 息处理的智能理论”作为实现人工智能的长远研究目标，这个观点是值得重视 的。另一条是计算机科学家们提出的从模拟人脑功能的角度来实现人工智能，也 就是通过计算机程序的运行，从效果上达到和人们智能行为活动过程相类似作为 研究目标，因而这派学者只是局限于解决“建造智能机器或系统为工程目标的有 关原理和技术”作为实现人工智能的近期目标，这个观点比较实际,目前引起较多 人的注意。总之不论从什么角度来研究人工智能，都是通过计算机来实现,因此可 以说人工智能的中心目标是要搞清楚实现人工智能的有关原理，使计算机有智 慧、更聪明、更有用。美国是人工智能的发源地，随着人工智能的发展，世界各国 有关学者也都相继加入这一行列。英国在60年代就起步人工智能的研究,到70 年代，在爱丁堡大学还成立了人工智能系,日本和西欧一些国家虽起步较晚, 但发展都较快，前联对人工智能研究也给予重视。我国是从1978年才开始人工 智能课题的研究，主要在定理证明、汉语自然语言理解、机器人及专家系统方面 设立课题，并取得一些初步成果。八十年代国也相应成立了中国人工智能学会， 中国计算机学会人工智能和模式识别专业委员会，中国自动化学会模式识别与 机器智能专业委员会，开展这方面的学术交流。作为“86.3”高科技计划的重要 容，国家着手兴建了若干个人工智能研究中心实验室，极促进了我国人工智能的 研究，缩短了我国人工智能技术与世界先进水平的差距，也为未来的发展奠定了 技术和人才基础。获得首届国家最高科学奖的数学家吴文俊院士，就是因为其 研究领域主要集中在运用计算机进行定理证明方面。人工智能这门新兴学科也曾一度陷入低谷，遭到某些人的攻击和非难。但是随 着高科技竞争的愈演愈烈，以及人工智能学者的艰苦卓绝的探索，它最终冲破迷雾 以先锋的姿态披荆斩棘，乘风破浪，成为二十一世纪的前卫学科。也许在不远的将 来,我们会无法分辨谁是机器人，谁是自然人。3研究与应用3.1问题求解问题求解，即解决管理活动中由于意外引起的非预期效应或与预期效应之间 的偏差。能够求解难题的下棋（如国际象棋）程序的出现，是人工智能发展的一 大成就。在下棋程序中应用的推理，如向前看几步，把困难的问题分成一些较容 易的子问题等技术，逐渐发展成为搜索和问题归约这类人工智能的基本技术。搜 索策略可分为无信息导引的盲目搜索和利用经验知识导引的启发式搜索，它决定 着问题求解的推理步骤中，使用知识的优先关系。另一种问题的求解程序，是把 各种数学公式符号汇编在一起,其性能已达到非常高的水平并正在被许多科学家 和工程师所应用，甚至有些程序还能够用经验来改善其性能。例如，1993年美 国发布的一个叫做MACSYMA的软件，它能够进行较复杂的数学公式符号运 算。如前所述，尚未解决的问题包括人类棋手具有的表达的能力，如国际象棋大 师们洞察棋局的能力；另一个未解决的问题涉及问题的原概念，在人工智能中叫 做问题表示的选择。人们常常能够找到某种思考问题的方法从而使求解变得容易 而最终解决该问题。3.2专家系统专家系统ES (Expert System)是人工智能研究领域中另一重要分支，它 将探讨一般的思维方法转入到运用专门知识求解专门问题，实现了人工智能从 理论研究向实际应用的重大突破；专家系统可看作一类具有专门知识的计算机智 能程序系统，它能运用特定领域中专家提供的专门知识和经验，并采用人工智能 中的推理技术来求解和模拟通常由专家才能解决的各种复杂问题。总的来说，专 家系统是一种具有智能的软件，它求解方法是一种启发式方法，专家系统所要解 决的问题一般无算法解，并且与传统的计算机程序上不同之处在于，它要经常在 不完全、不精确或不确定的信息基础上做出结论。在近年来的专家系统或“知识工程的研究中，已经出现了成功和有效应用人 工智能技术的趋势，具有有代表性的是用户与专家系统进行“咨询对话”，如同 其与专家面对面的进行对话是一样的：解释问题并建议进行某些试验，向专家系 统询问以期得到有关解答等。当前的实验系统，在比如化学和地质数据分析、计 算机系统结构、建筑工程以及医疗诊断等咨询任务方面，已达到很高的水平。另 外，还有很多研究主要是集中在让专家系统能够说明推理的能力，从而使咨询更 好地被用户接受，同时还能帮助人类发现系统推理过程中所出现的差错。发展专 家系统的关键在于表达和运用专家知识，即来自人类专家的且已被证明能够解决 某领域的典型问题的有用的事实和过程。不同领域与不同类型的专家系统，它们 的体系结构和功能是有一定的差异的，但它们的组成基本一致。一个基本的专家 系统主要由知识库、数据库、推理机、解释机制、知识获取和用户界面六部分组 成，如图1所示。一貌用尸.轲域女* A1 鼻寿家系纬的某本培构3.3机器学习机器学习(Machine Learning)是研究如何使用计算机模拟或实现人类的 学习活动。它是继专家系统之后人工智能的又一重要应用领域，是使计算机具有 智能的根本途径，也是人工智能研究的核心课题之一，它的应用遍及人工智能的 各个领域。学习是人类智能的重要特征，是获得知识的基本手段，而机器学习也是使计 算机具有智能的根本途径，如香克所说：“一台计算机若不会学习，就不能称为 具有智能的。”除此之外，机器学习还有助于发现人类学习的机理和揭示人脑 的奥秘。学习是一个有特定目的的知识获取过程，它的部主要表现为新知识结构 的不断建立和修改，外部表现为性能的改善。一个学习过程本质上讲，就是学习 系统把导师(或专家)提供的信息转换成能被系统理解并应用的形式的过程。 按照系统对导师的依赖程度可将学习方法分类为:机械式学习(Rotelearning)、 讲授式学习(Learning from instruction)、类比学习(Learning by analogy)、 归纳学习(Learning from induction)、观察发现式学习(learning by observation and discovery ）等。此外，近年来又发展了基于解释、事例、概 念、神经网络的学习和遗传学习等学习方法。3.4神经网络人工神经网络（Aficial Neural Network），是由大量处理单元即神经元互连 而成的网络，也常简称为神经网络或类神经网络。神经网络是一种由大量的节点 （或称神经元）和之间相互联接构成的运算模型，是对人脑或自然神经网络一些 基本特性的抽象和模拟，其目的在于模拟大脑的某些机理与机制，从而实现某些 方面的功能。通俗地讲，人工神经网络是仿真研究生物神经网络的结果。详细地 说，人工神经网络是为获得某个特定问题的解，根据所掌握的生物神经网络机理， 按照控制工程的思路及数学描述方法，建立相应的数学模型并采用适当的算法， 而有针对性地确定数学模型参数的技术。神经网络的信息处理是由神经元之间的 相互作用实现的：知识与信息的存贮主要表现为网络元件互连间分布式的物理联 系。人工神经网络具有很强的自学习能力，它可以不依赖于“专家”的头脑， 而自动从已有的实验数据中总结规律。由此，人工神经网络擅长于处理复杂多维 的非线性问题，不但可以解决定性问题，也可解决定量的问题，同时还具有大规 模并行处理和分布的信息存储能力，具有良好的自适应、自组织性以及很强的学 习、联想、容错和较好的可靠性。3.5模式识别计算机人工智能所研究的模式识别是指用计算机代替人类或帮助人类感知模 式。其主要的研究对象是计算机模式识别系统，也就是让计算机系统能够模拟人 类通过感觉器官对外界产生的各种感知能力。较早的模式识别研究工作集中在对 文字和二维图像的识别方面，并取得了不少成果。自20世纪60年代中期起，机 器视觉方面的研究工作开始转向解释和描述复杂的三维景物这一更困难的课题。 罗伯斯特（Robest ）于1965年发表的论文奠定了分析由棱柱体组成的景物的 方向，迈出了用计算机将三维图像解释成三维景物的一个单眼视图的第一步，即 所谓的积木世界。接着，机器识别由积木世界进入识别更复杂的景物和在复杂环 境中寻找目标以及室外景物分析等方面的研究。目前研究的热点是活动目标（如飞行器）的识别和分析，它是景物分析走向实 用化研究的一个标志。语音识别技术的研究始于20世纪50年代初期，发展到 20世纪70年代，各种语音识别装置相继出现，性能良好的能够识别单词的声音 识别系统已进入实用阶段，神经网络用于语音识别也已取得成功。作为一门新兴 学科，模式识别在不断发展，其理论基础和研究围也在不断发展。当前模式识别 正处于大发展的阶段，随着其应用围的逐渐扩大及计算机科学的发展，模式识别 技术将在今后有更大的发展，并且量子计算技术也将用于模式识别的研究。3.6人工生命人工生命（Artificial Life,简称AL）是由美国圣菲研究所非线性研究组的 计算机科学家 Christopher Langton 于 1987 年与 Los Alamos National Laboratory召开的“生成以及模拟生命系统的国际会议”上首先提出的。它 主要是通过人工模拟生命系统来研究生命的领域。AL的概念主要包括两方面 容：1）计算机科学领域的虚拟生命系统，主要涉及计算机软件工程和人工智能技 术；2）基因工程技术人工改造生物的工程生物系统，主要涉及合成生物学技术。相比于传统的人工智能和神经网络，人工生命不论在理论上还是方法上都有 很大的区别。人工生命主要是通过计算机仿真生命现象来体现自适应机理，对相 关非线性对象进行更真实的动态描述以及动态特征研究。人工生命学科主要包括 仿生系统、人工建模与仿真、人工生命的计算理论、进化动力学、进化与学习综 合系统以及人工生命的应用等研究容。现阶段比较典型的人工生命研究有：计算 机病毒、计算机进程、进化机器人、自催化网络、细胞自动机、人工核苜酸和人 工脑等。4遗传算法的研究1遗传算法概述遗传算法(GeneticAlgorithm,GA)是模拟生物进化论的自然选择和遗传学 进化过程的计算模型，是一种通过模拟自然进化过程随机搜索最优解的方法，体现 了适者生存、优胜劣汰的进化原则，其主要特点是直接对结构对象进行操作，不存 在求导和函数连续性的限定，具有并行性和较强的全局寻优能力。遗传算法把问 题的解表示成染色体， 求解步骤如下：编码:定义问题的解空间到染色体编码空间的映射，一个候选解(个体)用一串符号表示。(2) 初始化种群:在一定的限制条件下初始化种群，该种群是解空间的一个子空间。(3) 设计适应度函数:将种群中的每个染色体解码成适于适应度函数的形式，计算 其数值。(4) 选择:根据适应度大小选择优秀个体繁殖下一代，适应度越高，选择概率越大。(5) 交叉:随机选择两个用于繁殖下一代的个体的相同位置，在选中的位置实行交 换。(6) 变异:对某个串中的基因按突变概率进行翻转。(7) 从步骤4开始重复进行，直到满足某一性能指标或规定的遗传代数。GA在图像分割领域应用最为成熟，只要有两种应用,一是在多种分割结果中搜索 最佳分割结果,二是搜索图像分割算法的最优参数，如用来确定图像最佳分割阂 值。Jincong等使用最小误差概率做为适应度函数来搜索图像最佳分割阂 值,Leesu将GA用于分割阂值计算，提高了分割效率,Bhanu使用GA在多个分 割参数空间中搜索最优分割参数，提出了动态环境中图像分割系统，大大提高了环 境适应性,iaJgniTan ihz使用GA搜索最优细胞轮廓模型参数，对高噪声细胞 图像进行分割,chunDaeN使用GA对灰度图像的区域进行模糊测量，搜索一最 佳区域。GA在图像增强方面的应用主要是搜索最优或次优控制参数的过程。GA在图像恢复中的应用主要解决高噪声图像的恢复。在图像压缩中,GA能有效 解决分形压缩的最优匹配问题，提高了压缩比和精度，可用于低比特率的图像压 缩。GA在图像匹配方面的应用主要解决速度问题，通过减少搜索位置的数量来减少 计算量，提高效率。遗传算法是一类借鉴生物界自然选择和自然选择机制的随机 化搜索方法,有美国J -Holhdn教授提出，他的主要特点是能够提供群体的搜索方 案和实现群体里面个体之间的信息交换,且搜索不会依赖于梯度信息。它尤其适 用于处理传统搜索方法难于解决的复杂和非线性的问题，可广泛应用于组合优 化、机器学习、自适应控制、规划设计和图像处理等多个方面，是二十一世纪的 智能计算的关键技术之一。2遗传方法在图像处理中的应用2.1在图像增强中的应用。图像增强技术是将不清晰的图像经过优化处理变一比之前更加清楚，或者变成一 使得特点更加鲜明的照片，以便于对图像再进行后期的加工。目前图像增强方法 主要包括将图像进行某种变换的频域法和对直接对原始图像进行处理的空域法 两种。而基于遗传算法的图像增强技术的实现则是利用遗传的选择方法找到一个 最优或者局部最优的方法。具体的操作方法是，首先将每一个目标值设置一个基位，用实数进行编码,这样问 题就转化成求解这个目标基位组合的题目。然后，对适应度进行设计，适应度设计 为个体进化提供动力，在设置适应度的时候既要考虑图像的整体和局部的质量问 题，也要将结构和细节考虑进去。再后，对遗传算子进行设计,先根据前面设置的适应度值将个体从大到小进行排列, 从中选择优秀的个体进入下一个程序当中；为了防止遗传算法在计算的过程中过 早收敛，对种群的多样性进行保护，在计算过程中采用交叉操作的方法产生新的个 体;对进化方向进行微调，采用变异操作的方法，对一个被选中的变异操作来说，就 是采用“1”一“0”和“1”一“0”的方式进行变异。最后，设置算法的结束条 件，一般算法的结束条件就是迭代次数达到了最大进化代数或者最大适应度的值 变化不明显。2.2图像恢复技术。图像恢复技术的目的就是降一些退化的图像经过技术处理使得图像的本来面目 得到恢复。作为数字图像处理技术的一个分支,他的恢复方法有很多，包括维纳滤 波法，逆滤波法、最大嫡恢复法和奇异值分解伪逆法等。但是，上述方法在应用过 程中都有自己的缺陷,图像退化原因的不确定性和无确定的函数表达式，会导致上 述算法过于复杂，计算量过大和约束条件过多等情况的出现。采用遗传算法进行图像恢复，突破了原有理论的缚，能够更好的与其他一些计算方 法进行融合，使得计算率和精确度都有很大的提高。由于遗传算法具有功能强大的全局搜索能力，采用遗传算法结合其他算法处理过 的图像在客服噪影响方面具有很大的优势，同时也能使得图像边缘不会出现条纹 效应、过的更加平滑,整体感觉好。2.3图像重建技术。图像重建是由在某种观测方式下得到的携带图像信息的数据恢复出原图像的过 程。图像重建技术的方法也有很多种，主要是根据取得图像信息的方法不同，使用 重建方法也不同，有迭代法、代数法和傅里叶变换法等法。遗传算法在图像重建中的应用主要是解决带有噪声的投影数据的图像处理问题。 遗传算法在这方面的处理方法有很多，包括利用最小化被测像素值和计算的线总 和之间的差的方法;利用松弛迭代的傅里叶变换算法来解决计算过程中出现的停 滞现象;假定目标组合点分散的条件下,使用线性拟合方式来重建高分辨雷达图像 数据。2.4图像压缩技术。图像压缩技术最主要的原理就是将拥有自相似性的对象用这一组简单的代数关 系式进行表达的过程。将互相不重叠的小块定义为值域块，然后进行编码,并使经 过映射后的定义域块与值域块的距离在某种度量值下最小，在分解和处理过程中, 由于值域块的数量过于庞大，压缩搜索过程任务繁重,遗传算法的强大全局搜索能 力就能很好的派上用场，发挥良好的效果。遗传算法的基本原理遗传算法（GA）是基于“适者生存”的一种高度并行、随机和自适应的优化算法, 它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉 和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意 解。其中选择、交叉和变异是遗传算法的三个主要操作算子。具体操作步骤图如下：1）在一定编码方案下，随机产生一个初始种群；2）用相应的解码方法将编码后的个体转换成问题空间的决策变量，并求个体的适 应值;3）按照个体适应值的大小，从种群中选出适应值较大的一些个体构成交配池；4）由交叉和变异这两个遗传算子对交配池中的个体进行操作,并形成新一的种群;5）反复执步骤2）- 4）,直至满足收敛判据为止。GA是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条 件的约束,其搜索过程是从问题解的一个集合开始的，而不是从单个个体开始的， 具有隐含并行搜索特性，也就大大减小了陷人局部极小值的可能。正是由于其具有以上突出的优点，遗传算法几乎渗透到从工程到社会科学的各个 领域。为了验证遗传算法的全局寻优能力，本文将运用基于MATLAB编制的遗传 算法来求解数值优化和旅行商问题。遗传算法概述遗传算法（GeneticAlgorithm,GA）是借鉴生物界自然选择和群体进化机制形成 的一种全局寻优算法。与传统的优化算法相比，遗传算法具有如下优点1：1）不是 从单个点,而是从多个点构成的群体开始搜索；2）在搜索最优解过程中，只需要由 目标函数值转换得来的适应值信息，而不需要导数等其它辅助信息；3）搜索过程不 易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题 的有力工具2。在遗传算法中，将问题空间中的决策变量通过一定编码方法表示 成遗传空间的一个个体，它是一个基因型串结构数据；同时，将目标函数值转换成 适应值，它用来评价个体的优劣，并作为遗传操作的依据。遗传操作包括三个算子: 选择、交叉和变异。选择用来实施适者生存的原则，即把当前群体中的个体按与 适应值成比例的概率复制到新的群体中，构成交配池（当前代与下一代之间的中 间群体）。选择算子的作用效果是提高了群体的平均适应值。由于选择算子没有 产生新个体，所以群体中最好个体的适应值不会因选择操作而有所改进。交叉算 子可以产生新的个体，它首先使从交配池中的个体随机配对,然后将两两配对的个 体按某种方式相互交换部分基因。变异是对个体的某一个或某一些基因值按某一 较小概率进行改变。从产生新个体的能力方面来说,交叉算子是产生新个体的主 要方法，它决定了遗传算法的全局搜索能力;而变异算子只是产生新个体的辅助方 法,但也必不可少，因为它决定了遗传算法的局部搜索能力。交叉和变异相配合， 共同完成对搜索空间的全局和局部搜索。遗传算法的基本步骤3如下：1）在一定编码方案下，随机产生一个初始种群；2）用相应的解码方法，将编码后的个体转换成问题空间的决策变量,并求得个体的 适应值；3）按照个体适应值的大小，从种群中选出适应值较大的一些个体构成交配池；4）由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种 群；5）反复执行步骤24,直至满足收敛判据为止。使用遗传算法需要决定的运行参数有:编码串长度、种群大小、交叉和变异概 率。编码串长度由优化问题所要求的求解精度决定。种群大小表示种群中所含个 体的数量，种群较小时，可提高遗传算法的运算速度，但却降低了群体的多样性，可 能找不出最优解;种群较大时，又会增加计算量，使遗传算法的运行效率降低。一般 取种群数目为20100。交叉概率控制着交叉操作的频率,由于交叉操作是遗传 算法中产生新个体的主要方法，所以交叉概率通常应取较大值;但若过大的话，又 可能破坏群体的优良模式。一般取0.40.99。变异概率也是影响新个体产生的 一个因素，变异概率小，产生新个体少;变异概率太大，又会使遗传算法变成随机搜 索。一般取变异概率为0.00010.1。遗传算法常采用的收敛判据有:规定遗传代 数;连续几次得到的最优个体的适应值没有变化或变化很小等。3用MATLAB实现遗传算法MATLAB是Matwork公司的产品,是一个功能强大的数学软件，其优秀的数 值计算能力使其在工业界和学术界的使用率都非常高。MATLAB还十分便于使 用，它以直观、简洁并符合人们思维习惯的代码给用户提供了一个非常友好的开 发环境。利用MATLAB处理矩阵运算的强大功能来编写遗传算法程序有着巨大 的优势。3. 1编码遗传算法不对优化问题的实际决策变量进行操作，所以应用遗传算法首要的 问题是通过编码将决策变量表示成串结构数据。本文中我们采用最常用的二 进制编码方案，即用二进制数构成的符号串来表示一个个体，用下面的 encoding函数来实现编码并产生初始种群：functionbin-gen,bits=encoding(min-var,max-var,scale-var,popsize)bits二ceil(log2( max-var-min-var)./scale-var);bin-gen二randint(popsize,sum(bits);在上面的代码中，首先根据各决策变量的下界(min-var)、上界(max-var) 及其搜索精度scale-var来确定表示各决策变量的二进制串的长度bits,然后随 机产生一个种群大小为popsize的初始种群bin -gen。编码后的实际搜索精 度为 scale-dec=(max-var-min-var)/(2bits-1),该精度会在解码时用到。3. 2解码编码后的个体构成的种群bin-gen必须经过解码，以转换成原问题空间的决 策变量构成的种群var - gen，方能计算相应的适应值。我们用下面的代码实现。functionvar-gen,fitness=decoding(funname,bin-gen,bits,min- var,max-var)num-var=length(bits);popsize二size(bin-gen,1);scale-dec=(max-var-min-var)./(2.bits-1);bits=cumsum(bits);bits=0bits;fori=1:num-varbin-vari=bin-gen(:,bits(i) + 1:bits(i+1);vari=sum(ones(popsize,1) * 2.(size(bin-vari,2)-1:-1:0).* bin-vari,2).* scale-dec(i)+min-var(i);endvar-gen=var1,:;fori=1:popsizefitness(i)=eval(funname,'(var-gen(i,:)');end解码函数的关键在于先由二进制数求得对应的十进制数 D,并根据下式求 得实际决策变量值X:X二Dxscale-dec+min-var3. 3选择选择过程是利用解码后求得的各个体适应值大小，淘汰一些较差的个体而选 出一些比较优良的个体,以进行下一步的交叉和变异操作。选择算子的程序如 下：functionevo-gen,best-indiv,max-fitness=selection(old-gen,fit-ness)popsize=length(fitness);max-fitness,index1=max(fitness)