战德臣全套配套课件大学计算机——计算与信息素养第2版 第09章-怎样研究算法-遗传算法研究示例.ppt

《战德臣全套配套课件大学计算机——计算与信息素养第2版 第09章-怎样研究算法-遗传算法研究示例.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、可求解与难求解问题ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员现实世界中的问题分类可求解与难求解问题(1)什么是可求解与难求解问题?计算机在有限时间内能够求解的(可求解问题)计算机在有限时间内不能求解的(难求解问题)计算机完全不能求解的(不可计算问题)计算复杂性是指问题的一种特性，即利用计算机求解问题的难易性或难易程度，其衡量标准：计算所需的步数或指令条数(即

2、时间复杂度)计算所需的存储空间大小(即空间复杂度)----通常表达为关于问题规模n的一个函数O(f(n))问题的计算复杂性可求解与难求解问题(2)什么是有限时间内不能求解?问题规模n计算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=8000O(n3)O(3n)0.2秒41028秒=1015年注：每秒百万次，n=60，1015年相当于10亿台计算机计算一百万年O(n3)与O(3n)的差别，O(n!)与O(n3)的差别O(bn),O(n!)O(1),O(logn),O(n),O(nlogn),O(

3、nb)可求解与难求解问题(3)怎样以复杂性来划分问题?P类问题，NP类问题，NPC类问题P类问题：多项式问题(PolynomialProblem)，指计算机可以在有限时间内求解的问题，即：P类问题是可以找出一个呈现O(na)复杂性算法的问题，其中a为常数。NP类问题：非确定性多项式问题(Non-deterministicPolynomial)。有些问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到结果，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一

4、个算法验证一个解是否正确的非确定性问题，就是NP类问题。NPC问题：完全非确定性多项式问题(NP-Complete)。如果NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非确定性多项式问题，即NP-Complete问题。问：加密算法应该设计成一个什么问题呢？可求解与难求解问题(4)NPC类问题如何求解?NPC类问题求解穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果---精确解可能是O(n!)或O(an)近似解求解算法---近似解应该是O(na)∆=

5、近似解–精确解

6、满意解：∆充分小

7、时的近似解TSP问题的遍历算法TSP问题的贪心算法仿生学算法进化算法，遗传算法，蚁群算法，蜂群算法,…算法复杂性计算复杂性P类问题NP类问题NPC类问题可求解问题可求解与难求解问题(5)小结?难求解问题NPC类问题求解-计算精确解近似解遗传算法的缘起--生物学中的遗传与进化ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员遗传算法的缘起--生物学中的遗传与进化(1)

8、为什么引入生物学的内容?精确解近似解NPC类问题NPC类问题的解算法计算生物界问题求解思维类比与借鉴趋近于降低计算量遗传算法蚁群算法蜂群算法…算法遗传算法的缘起--生物学中的遗传与进化(2)生物体中是怎样遗传的?生物学中的遗传和进化关于生物遗传进化的基本观点(i)生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；(ii)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；(iii)生物的繁殖过程是由其基因的复制过程来完成的；(iv)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(v)对环境适应性好的基因

9、或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。遗传与进化优胜劣汰遗传算法的缘起--生物学中的遗传与进化(3)生物体遗传与进化的过程是怎样的?生物学中的遗传和进化遗传算法的缘起--生物学中的遗传与进化(4)什么是染色体和基因，它们与遗传有什么关系?生物学中的遗传和进化基本概念种群(Population)vs.个体(Individual)vs.染色体(chromosome)染色体(chromosome)vs.基因(gene)基因型(Genotype)vs.表现型(Phenotype)个体的适应度(Fitness)选择(Selection)复制((R

10、eproduction)交配/杂交(C