计算思维导论 课件 第9、10讲 难解性问题求解与算法、软件思维

第9讲难解性问题求解与算法哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣第9讲难解性问题求解与算法一、算法类思维概述二、可求解与难求解问题三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、遗传算法为什么可以求解NPC问题六、遗传算法的应用遗传算法蚁群算法蜂群算法…算法算法类思维概述怎样研究算法：研究什么算法社会/自然现象(遗传与进化)计算学科的(遗传)算法(遗传)算法的本质(遗传)算法的应用算法类思维概述本讲内容组织思路社会/自然现象(遗传与进化)计算学科的(遗传)算法(遗传)算法的本质(遗传)算法的应用算法类思维概述本讲内容组织思路生物学中的问题求解思想生物学中的问题求解过程/步骤计算学科中的问题求解过程/步骤NPC类问题NPC类问题的解过程/步骤中的设计技巧具体问题社会/自然现象(遗传与进化)计算学科的(遗传)算法(遗传)算法的本质(遗传)算法的应用算法类思维概述本讲内容组织思路计算与计算系统(浅层次)社会/自然/生活计算与计算系统(深层次)由遗传算法的学习，学会算法的研究，更重要的是养成科学研究良好的习惯本质应用宽度学习深度学习第9讲难解性问题求解与算法一、算法类思维概述二、可求解与难求解问题三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、遗传算法为什么可以求解NPC问题六、遗传算法的应用可求解与难求解问题算法复杂性如何评价算法的性能?算法复杂性，是指求解一个问题的某一个算法的复杂性空间复杂性：衡量算法运行中所需要的存储空间（参照时间复杂性来进一步理解）时间复杂性：衡量算法的运行速度。一个算法由一些基本步骤构成，则算法基本步骤的执行次数被称为时间复杂性。问题通常与自然数n相关联，以反映问题的规模。例如求解5种、50种、50000种物品的组合问题，就是不同规模的问题。问题求解算法通常与问题规模n相关（典型的就是循环、递归等）。算法基本步骤的执行次数通常被表达为关于n的一个函数T(n)，该T(n)被称为时间复杂性或时间复杂度。例如T(n)=2n,或者T(n)=2n2+3n+5。时间复杂性是衡量算法的运行时间随着问题规模的增大而增加的趋势，而不是具体的运行时间。故而时间复杂性通常以量级来衡量，即大O表示法：O(T(n))。例如O(2n2+3n+5)=O(n2)，表示它们是同一量级的复杂性。测练题：下列说法正确的是_________，其中b为常数。“O(logn),O(nb)”等是多项式级别的复杂性,“O(bn)，O(n!)”等是指数级别的复杂性“O(nb),O(bn)”等是多项式级别的复杂性,“O(n!)”等是指数级别的复杂性“O(nb),O(n!)”等是多项式级别的复杂性,“O(bn)”等是指数级别的复杂性“O(logn),O(n)”等是多项式级别的复杂性,“O(nb)，O(bn)，O(n!)”等是指数级别的复杂性ABCD提交单选题1分测练题：下列说法正确的是_________，其中b为常数。

O(1)<O(logn)<O(bn)<O(n)<O(nb)

O(1)<O(logn)<O(n)<O(nb)<O(bn)

O(1)>O(logn)>O(n)>O(nb)>O(bn)

O(1)<O(n)<O(logn)<O(nb)<O(bn)ABCD提交单选题1分问题规模n计算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=

8000O(n3)O(3n)0.2秒4

1028秒=1015年注：每秒百万次，n=60，1015年相当于10亿台计算机计算一百万年O(n!)与O(n3)、O(n3)与O(3n)的差别O(bn),O(n!)O(1),O(logn),O(n),O(nlogn),O(nb)可求解与难求解问题不同量级复杂性在计算时间方面的差异可求解与难求解问题不同量级复杂性在计算时间方面的差异算法复杂性：求解问题的某一个算法的复杂性计算复杂性：能求问题精确解的那个最快的算法的复杂性计算复杂性是指问题的一种特性，即利用计算机求解问题的难易性或难易程度问题的计算复杂性计算机在有限时间内能够求解的--【可求解问题】计算机在有限时间内难于求解的--【难求解问题】计算机完全不能求解的--【不可计算问题】可求解与难求解问题计算复杂性还是没有回答怎样才是有限时间？继续…

当算法的复杂度是一个多项式，如O(n2)时，则对于大规模问题，该算法是可以在有限时间内被计算机完成的。例如，某一问题的贪心算法

O(n3)

。当算法的复杂度是用指数函数表示如O(2n)或阶乘函数表示如O(n!)，则当n很大（如10000）时，该算法是计算机在有限时间内无法处理的。例如某一问题的遍历算法O(n!)。O(1),O(logn),O(n),O(nlogn),O(nb)O(bn),O(n!)可求解与难求解问题有限时间内是否能完成算法的执行？测练题：关于算法复杂性和计算复杂性，表述最正确的是_________算法复杂性和计算复杂性是不同的概念。算法复杂性衡量的是某一个算法的执行时间长短，而计算复杂性是求解某一个问题的计算量的多少算法复杂性和计算复杂性是不同的概念，算法复杂性是对问题求解某一个算法执行时间的度量，而计算复杂性是对问题求解的计算量的度量，是求解该问题精确解最快的那个算法的复杂性算法复杂性和计算复杂性是不同的概念。计算复杂性衡量的是某一个算法的执行时间长短，而算法复杂性是求解某一个问题的计算量的多少算法复杂性和计算复杂性是相同的概念，都是问题求解算法执行时间的一种度量ABCD提交单选题1分【P类问题】多项式问题(PolynomialProblem)，即：可以找出一个呈现O(na)复杂性算法求出精确解的问题，其中a为常数。P类问题是指计算机可以在有限时间内能求出精确解的问题，【NP类问题】非确定性多项式问题(Non-deterministicPolynomial)，即：可以找出一个呈现O(na)复杂性算法来验证一个可能解是否是正确的问题。

有些问题，其答案无法直接计算得到，但可通过间接的猜算/试算来得到，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于求解，但给定一个解却不难在多项式时间内验证其正确性的问题，即是NP类问题。【NPC类问题】完全非确定性多项式问题(NP-Complete)，即：(1)如果NP问题的所有可能解都可以在多项式时间内进行验算，(2)求精确解需要遍历所有可能解，(3)遍历所有可能解的复杂度是指数或阶乘级别的；则为NP-Complete问题。一个NP问题，并非其每个解都可以在多项式时间内验算，即：有些解是可以验算的，而有些解是不能验算的。如果一个NP问题其需要验算的解空间是用非多项式函数(指数函数或阶乘函数)来表达的，则是NP-Complete问题。如果一个NP问题经过约简后得到的问题仍旧是NP问题，则是NP-Complete问题。问：加密算法应该设计成一个什么问题呢？可求解与难求解问题用计算复杂性划分问题注意：这里给出的是易于理解的表述。严格的定义需要学习计算理论课程！NP-Hard/NP难问题可求解与难求解问题可解性问题与难解性问题P类问题（多项式时间内能求精确解）NP类问题（多项式时间内能验证一个解）NPC类问题（1)多项式时间内能验证每一个解,(2)求精确解需要遍历解空间,(3)指数时间遍历解空间难解性问题非NP问题多项式时间内不一定能验证一个解穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果---精确解可能是O(n!)或O(an)近似解求解算法---近似解应该是O(na)∆=|近似解–精确解|满意解：∆充分小时的近似解TSP问题的遍历算法TSP问题的贪心算法仿生学算法进化算法，遗传算法，蚁群算法，蜂群算法,…TSP问题是NPC类问题NPC类问题可求解与难求解问题NPC类问题如何求解测练题：关于P类问题，下列说法正确的是。P类问题是能够用多项式方法求解且其复杂性为多项式的问题P类问题是指这样的问题，即能够找出求解该问题的一个算法，且该算法的时间复杂性为多项式P类问题是能够用多项式方法求解的问题P类问题是可以在有限时间内求解的问题ABCD提交P类问题是指这样的问题，即能够找出求解该问题的一个算法，且该算法与某个多项式有关E多选题1分测练题：关于NP类问题，下列说法正确的是___________。NP类问题是不能够用多项式方法求解且其复杂性不为多项式的问题NP类问题是指不确定其能否在多项式时间内求解，但能够在多项式时间内判定一个解是否是问题的解的问题NP类问题是不能够用多项式方法求解的问题NP类问题是不能在有限时间内求解的问题ABCD提交NP类问题是指既能够在多项式时间内判定，又能够在多项式时间内求解的问题E单选题1分测练题：关于NPC类问题，下列说法正确的是___________。NPC类问题是不可求解的问题NPC类问题是难以在有限时间内求解的问题NPC类问题，是目前已知其精确解求解算法都是指数级算法的问题NPC类问题是最难求解的NP类问题ABCD提交NPC类问题是当问题规模很大时难以在有限时间内求解的问题E多选题1分测练题：关于P类问题和NP类问题，下列说法正确的是___________。如果一个问题是P类问题，则该问题不是NP类问题如果一个问题是NP类问题，则该问题也是P类问题如果一个问题是P类问题，则该问题也是NP类问题P类问题是能在有限时间内求解的问题，NP类问题是不能在有限时间内求解的问题ABCD提交如果一个问题是NP类问题，则该问题也可能是P类问题E多选题1分第9讲难解性问题求解与算法一、算法类思维概述二、可求解与难求解问题三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、遗传算法为什么可以求解NPC问题六、遗传算法的应用关于生物遗传进化的基本观点(i)生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；(ii)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；(iii)生物的繁殖过程是由其基因的复制过程来完成的；(iv)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(v)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。遗传与进化优胜劣汰遗传算法的缘起--生物学中的遗传与进化生物学中的遗传和进化繁衍后的种群种群新一代种群基因重组新个体的染色体个体A的染色体个体B的染色体染色体B的基因片段染色体A的基因片段个体对环境的适应性:优胜劣汰两个个体新个体

染色体与基因遗传算法的缘起--生物学中的遗传与进化将生物体的遗传与进化理解为【过程】种群(Population)

vs.个体(Individual)

vs.染色体(chromosome)染色体(chromosome)vs.基因(gene)基因型(Genotype)vs.表现型(Phenotype)个体的适应度(Fitness)选择(Selection)复制((Reproduction)交配/杂交(Crossover)突变(Mutation)遗传算法的缘起--生物学中的遗传与进化识别基本概念测练题：关于生物遗传，你理解了哪些内容___________。个体对环境要有适应性，优胜劣汰，适者生存，形成优化后的种群。--此过程可以用一个单调递增函数来模拟，函数值越高，适应性越强选择，是个体配对的选择、是环境对个体的选择(优胜劣汰，适应性强的个体被选择)。--此过程可以用概率来模拟基因重组，是基因片段的复制、交叉/组合和变异的过程。--这些方法就是产生新的可能解的方法生物的遗传过程：种群

个体

基因

基因重组

新基因

新个体

新种群。--这个过程可以转变为一种求解NPC问题的一种算法ABCD提交投票最多可选4项生物学中的问题求解思想生物学中的问题求解过程与步骤计算学科中的问题求解过程与步骤NPC类问题NPC类问题的解过程/步骤中的设计技巧具体问题遗传算法的缘起--生物学中的遗传与进化类比中创新问题求解的算法第9讲难解性问题求解与算法一、算法类思维概述二、可求解与难求解问题三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、遗传算法为什么可以求解NPC问题六、遗传算法的应用【示例】求多项式函数的最小值：

MinF(X)=X2-19X+20,其中X=1,…,64之间的整数。注：此题不难求出精确解，其精确解为X=9或者X=10。

如何用遗传算法进行求解?计算学科的遗传算法模拟小规模问题求解理解遗传算法生物学中的概念计算学科中的概念解释种群解集/种群若干可能解的集合个体解/个体一个可能解的表现型，本例中即是十进制的X染色体编码解/染色体一个可能解的基因型，本例即是X的二进制编码。X=b6b5b4b3b2b1，其中bi=0或1。基因基因解编码中的若干位的bi适应度适应度一个可能解接近最优解的一个度量，本例直接用F(X)作为其适应度的度量，其值越小越接近最优解选择选择指从种群(解集)中依据适应度按某种条件选择某些个个体(可能解)复制复制将一个解从一个解集复制到另一个解集交配/杂交交叉即交配/杂交，是新可能解的一种形成方法，即是对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作突变变异也是新可能解的一种形成方法，它是通过随机地改变一个可能解的编码的某些片段(或基因)而使一个可能解变为一新的可能解的遗传操作计算学科的遗传算法将生物学中的概念映射为计算学科中的概念求X,满足MinF(X)=X2-19X+20forX=1,…,64之间的整数；个体(可能解)的表现形式：

X=1,…,64个体(可能解)的基因形式：染色体

X=B6B5B4B3B2B1,其中Bi=0or1初始种群(初始解集)010101101010001000111001产生010101101010001000111001010101101010001000111001繁衍:交叉/变异001000111001001100101001交叉交叉变异变异计算学科的遗传算法仿生物学过程进行问题求解010101101010001000111001010101101010001000111001繁衍:交叉/变异001000111001001100101001交叉交叉变异变异繁衍种群(候选解集)011010100101001001111000010101101010001000111001原有解新产生的解001100101001计算学科的遗传算法仿生物学过程进行问题求解例如：将X的染色体转为其个体表现形式，取个体的适应度函数为F(X)，即计算F(X)繁衍种群(候选解集)011010100101001001111000010101101010001000111001原有解新产生的解001100101001繁衍种群(候选解集)的适应性评价01101010010100100111100001010110101000100011100126,F(26)=20237,F(37)=6869,F(9)=-7056,F(56)=209221,F(21)=6242,F(42)=14068,F(8)=-6857,F(57)=218600110010100112,F(12)=-6441,F(41)=922MinF(X)=X2-19X+20计算学科的遗传算法仿生物学过程进行问题求解繁衍种群(候选解集)的适应性评价01101010010100100111100001010110101000100011100126,F(26)=20237,F(37)=6869,F(9)=-7056,F(56)=209221,F(21)=6242,F(42)=14068,F(8)=-6857,F(57)=2186选择:选优汰劣例如：选取F(X)最小的4个个体001100100101010100001000下代种群(下代解集)例如：将X的染色体转为其个体表现形式，取个体的适应度函数为F(X)，即计算F(X)00110010100112,F(12)=-6441,F(41)=922MinF(X)=X2-19X+20计算学科的遗传算法仿生物学过程进行问题求解选择:选优汰劣例如：选取F(X)最小的4个个体001100100101010100001000下代种群(下代解集)可终止001001终止后，取F(X)最小的个体作为最优解结果最优解结果的表现形式：

X=

9最优解的基因形式：染色体

X=001001001100010101001001001000001100010101001001001000可下一轮繁衍001000001000001100011000交叉交叉变异变异计算学科的遗传算法仿生物学过程进行问题求解计算学科的遗传算法仿生物学过程进行问题求解（一张图显示）表达成算法遗传算法基本框架及其设计要点begin/*遗传算法*/ t←0；/*进化的种群代数*/

生成初始种群P(t)；

计算初始种群P(t)中每个个体的适应值；

while（不满足终止条件）do/*利用下述操作生成新个体，并选择更优个体组成新种群*/ (1)通过复制、交叉或变异操作重组种群P(t)中 的个体，产生新个体，形成候选种群C(t)；/*注意此处C(t)并未包含P(t)中的个体*/

(2)计算C(t)中每个个体的适应值；

(3)根据适应值从C(t)和P(t)中选择更优的个体 组成新种群P(t+1)； (4)t←t+1；

endwhile

选择P(t)中最优个体为所求的解；endbegin计算学科的遗传算法测练题：关于遗传算法，你理解了哪些内容呢，请选择_____________?交叉、变异产生的解仍然很多怎么办，可借助于概率随机选择以降低枚举的数量遗传算法的本质，通过组合、变异产生新的可能解，通过概率随机降低枚举可能解的数量怎样由一个解集产生更多的可能解？可通过交叉和变异的手段来处理只要能给出可能解的形式，便可采用枚举-计算-验证的思路设计算法求解ABCD提交枚举的数量太多，怎么办？随机选择，降低可能解枚举的数量？E投票最多可选5项测练题：关于遗传算法，你认为下列说法哪一个最适合，请选择_____________?遗传算法能求解任何可计算的问题，但不一定能求得精确解，也不一定能求得满意的近似解遗传算法不能求解任何可计算的问题遗传算法能求解任何可计算的问题，只要其可能解能够表达出来且能够度量一个解是偏向于还是偏离于最优解（即能用一个适应度函数来表征解的质量的好坏）遗传算法能求解任何可计算的问题ABCD提交遗传算法能求解任何可计算的问题，只要其可能解能够表达出来E多选题1分第9讲难解性问题求解与算法一、算法类思维概述二、可求解与难求解问题三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、遗传算法为什么可以求解NPC问题六、遗传算法的应用假设一个问题的解的形式为x，则：可能解：由x的取值空间/定义域给定的任何一个x值可行解：问题通常有很多约束。满足问题所有约束的x值，才是有效的、可行的近似解：由一个算法在任何一组可行解中求出的最优解满意解：符合用户期望的近似解

精确解：所有可行解中的最优解，是问题的最优解【可能解】集合

【可行解】集合

【近似解】集合

【满意解】集合

【最优解/精确解】集合遗传算法为什么可以求解NPC问题关于【解】的一组概念(a)穷举/遍历搜索所有,可找到精确解穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有可能的解都被验证是否正确，便能得到精确的结果---精确解可能是O(n!)或O(an)NPC问题求解初始思路：遍历算法“枚举-验证”可能解能表达出来遗传算法为什么可以求解NPC问题NPC问题求解的初始思路(b)完全随机搜索随机点之间完全没有联系随机搜索法：在解空间中随机选择一些可能解进行验证，求出所选择可能解(子解空间)中的最优解---近似解/可行解(满足问题求解约束)，力争近似解为满意解1.基于概率：随机选择2.子解空间越大，求得满意解的可能性越大，但耗时也会加长3.求出的近似解并不能保证是满意解不求精确解，而求近似解-满意解：随机搜索法遗传算法为什么可以求解NPC问题算法的追求：以质量换速度(c)导向性随机搜索随机点之间形成一路径导向性随机搜索法：对随机点的选取进行导向，导向到接近最优解的方向或路径1.基于概率：随机选择2.随机选择的可能解与前一可能解相比，更偏向于满意解3.万一初始解就很差怎么办?为提高近似解的质量：导向性随机搜索法遗传算法为什么可以求解NPC问题算法的追求：既要速度，还要质量(d)导向性群(体)随机搜索多随机点同步进行导向性搜索导向性群(体)随机搜索法：同时对多个随机点的选取进行导向(导向到接近最优解的方向或路径)，多条搜索路径

基于概率：随机选择多条路径下的最优，总比一条路径的最优要更优一些同一时刻多条路径上的解集合,即为一个种群。多次选择，即多代进化为进一步提高近似解的质量，可采取导向性群(体)随机搜索法遗传算法是否是这样呢遗传算法为什么可以求解NPC问题算法的追求：既要速度，还要质量对于NPC问题，当没有其他更好的算法可以使用时，可以考虑选择遗传算法。遗传算法的适用条件：(1)已知【解空间】。即:【可能解】能够被表达、被枚举(2)已知关于可能解的【适应度】的计算方法。即：能够判断一个可能解是接近精确解还是偏离精确解。适应度用于判断一个可能解接近精确解的程度或方向。遗传算法提供了一种求解复杂系统问题的通用框架遗传算法为什么可以求解NPC问题什么情况下可用遗传算法求解问题?遗传算法蚁群算法蜂群算法…算法遗传算法为什么可以求解NPC问题怎样研究算法第9讲难解性问题求解与算法一、算法类思维概述二、可求解与难求解问题三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、遗传算法为什么可以求解NPC问题六、遗传算法的应用【示例1】“会议室”租用问题<x1,x2,…,xn>约束矩阵aijij可能解目标函数约束遗传算法的应用一些需要求解的现实问题【示例2】“航班机组成员”选择问题<x1,x2,…,xn>约束矩阵aijij可能解目标函数约束遗传算法的应用一些需要求解的现实问题【示例3】“软件测试用例”选择问题

<x1,x2,…,xn>约束矩阵aijij可能解目标函数约束遗传算法的应用一些需要求解的现实问题【示例1】“会议室”租用问题<x1,x2,…,xn>可能解目标函数约束【示例2】“航班机组成员”选择问题【示例3】“软件测试用例”选择问题

它们是同一个问题：一维的集覆盖问题遗传算法的应用一些需要求解的现实问题其中：F(x)取z(x)x要满足相应的约束遗传算法的应用用遗传算法求解一维解覆盖问题测练题：如图，有一个背包，可装载重量有限制，有物品如图示意且其重量和价值，选择物品放入背包使背包中物品价值最大。问该问题的可能解有多少？25个32个24个2个ABCD提交9个E单选题1分【背包问题】有1个背包，可装载重量有限制。有n种物品，每种物品最多1件，且其重量和价值已知。怎样选择物品放入背包，才能使背包中物品价值最大？遗传算法的应用问题数学建模方法的总结

第9讲难解性问题求解与算法【自学&拓展】哈尔滨工业大学计算学部教学委员会主任国家教学名师战德dechen@第9讲难解性问题求解与算法【自学&拓展】一、问题及其建模二、算法设计要点与解的编码三、策略选择的多样性四、策略选择的随机性五、遗传算法的其他方面【示例】“课程表”优化问题8门课程需安排教室，记为Li，i=1,…,8；6个教室可被使用，记为Rj，j=1,…,6；要求每门课只能安排在一个教室，而每个教室最多只能安排两门课。教室与课程班之间的约束矩阵A如下表给出，其中aij=1表示该课程班可以安排在该教室，aij=0则不可安排。费用为教室容纳人数/课程班人数，即Cij=Kj/Li。约束矩阵问题及其建模一个优化问题可能解是二维矩阵问题及其建模问题的数学建模【示例】“课程表”优化问题8门课程需安排教室，记为Li，i=1,…,8；6个教室可被使用，记为Rj，j=1,…,6；要求每门课只能安排在一个教室，而每个教室最多只能安排两门课。教室与课程班之间的约束矩阵A如下表给出，其中aij=1表示该课程班可以安排在该教室，aij=0则不可安排。费用为教室容纳人数/课程班人数，即Cij=Kj/Li。示例一维集覆盖问题二维集覆盖问题使每一行都被选出的列覆盖，被哪一列或几列覆盖不重要，要满足约束矩阵使每一行都确定安排在某一列上，使被选中的行-列覆盖所有的行，要满足约束矩阵可能解是一维向量可能解是二维矩阵<x1,x2,…,xn>问题及其建模问题的数学建模第9讲难解性问题求解与算法【自学&拓展】一、问题及其建模二、算法设计要点与解的编码三、策略选择的多样性四、策略选择的随机性五、遗传算法的其他方面NPC求解:产生一个或一批可能解判断可能解是否是问题的解可能解的形式是怎样的?怎样产生待判定的可能解?产生多少个待判定可能解?怎样判定一个解是否是所求的解?解的表现型和基因型交叉、变异随机(概率)解集的规模进化的代数随机(概率)适应度选择(标准)满意解算法设计要点及解的编码遗传算法的设计要点

实际问题分析:解的形式,解的约束,解空间问题解的编码与解码规则设计:个体(解)的表现型与基因型的变换函数初始种群的规模与生成规则设计种群个体的适应度函数设计遗传规则的设计：交叉、变异终止条件及最终解产生繁衍种群的策略设计解的满意度评估,算法效率的评估以及算法的改进优质个体的选择(汰选)方法设计算法设计要点及解的编码遗传算法的设计要点

x11x12…x1nx21x22…x2n………xm1xm2…xmn可能解的一般形式课程教室Xij=1课程i被安排在教室j;=0课程i未被安排在教室j000010010000100000000100010000100000000100000010可行解1100000001000000010000100010000100000000100010000可行解2示例问题的解的形式(表现型)与编码(基因型)算法设计要点及解的编码为什么要考虑解的形式与解的编码行优先编码:课程分段编码,一门课程相关的划为一段，有多少课程就有多少段列优先编码:教室分段编码,一个教室相关的划为一段，有多少教室就有多少段(解的)编码方案不同，交叉、变异(产生新可能解)的规则也可能不同算法设计要点及解的编码可能解的不同的编码方案第9讲难解性问题求解与算法【自学&拓展】一、问题及其建模二、算法设计要点与解的编码三、策略选择的多样性四、策略选择的随机性五、遗传算法的其他方面NPC求解:产生一个或一批可能解判断可能解是否是问题的解可能解的形式是怎样的?怎样产生待判定的可能解?产生多少个待判定可能解?怎样判定一个解是否是所求的解?解的表现型和基因型交叉、变异随机(概率)解集的规模进化的代数随机(概率)适应度选择(标准)满意解为什么要“交叉”?策略选择的多样性以交叉规则为例，看策略选择的多样性010101101010010101101010交叉010101101010010101101010交叉点010101101010010101101010交叉010101101010010101101010两段交叉，一个染色体(可能解)被分成两段，两个染色体的同位置段进行交叉重组是否只有这一种交叉方案呢?策略选择的多样性两段交叉010101101010010101101010交叉0101011010100101011010101-2段交叉点2-3段交叉点距离1-2段交叉点2-3段交叉点距离等距离多段交叉010101101010010101101010交叉010101101010010101101010多段交叉，一个染色体被分成多段，两个染色体的同位置段进行交叉重组策略选择的多样性等距离多段交叉010101101010010101101010交叉0101011010100101011010101-2段交叉点2-3段交叉点距离010101101010010101101010交叉0101011010100101011010101-2段交叉点2-3段交叉点距离不等距离多段交叉多段交叉，一个染色体被分成多段，两个染色体的同位置段进行交叉重组策略选择的多样性不等距离多段交叉行交叉是指对两个染色体同位置的两个课程段基因进行交叉重组列交叉是指对不同段的相同位置的两个染色体的基因进行交换块交叉则是对两个染色体的任何位置的两个块基因进行交换点交叉则是对两个染色体按某一概率交换其位基因000010010000100000000100010000100000000100000010100000001000000010000100010000100000000100010000交换窗口,可自左至右移动,可按位移动或按段移动.000010010000100000000100010000100000000100000010100000001000000010000100010000100000000100010000同步交换的各位,可按位自左至右同步移动000010010000100000000100010000100000000100000010100000001000000010000100010000100000000100010000交叉交叉交叉交叉策略选择的多样性结合具体问题的解的编码方式的交叉策略组合的多样性交叉两段交叉、等距离多段交叉、不等距离多段交叉点交叉、行交叉、列交叉、块交叉结合具体问题的解的编码方式的交叉策略策略选择的多样性小结第9讲难解性问题求解与算法【自学&拓展】一、问题及其建模二、算法设计要点与解的编码三、策略选择的多样性四、策略选择的随机性五、遗传算法的其他方面交叉操作本质上是一种组合，组合所形成的可能解空间依然是庞大的，难以确定性的遍历每个组合基于概率的随机处理方法：是遗传算法的核心处理机制交叉概率：在一个群体中，个体被选择出进行交叉的概率010101101010010101101010交叉010101101010010101101010交叉点总计12个,取几个?种群策略选择的随机性以交叉规则为例，看策略选择的随机性(1)种群中个体的配对分组问题，即哪两个个体进行配对交叉(2)两段交叉中交叉点位置的选择(3)多段交叉中的交叉点距离的变化与不变，即两个或多个交叉点间等距离和不等距离的多段选择问题(4)子空间中的待判定解(候选解)的选择(5)结合问题解编码的交叉与随机策略010101101010001000111001010101101010种群(解集)010101101010001000111001001000111001繁衍:交叉交叉交叉随机与概率策略选择的随机性交叉与随机【示例】点交叉设P1和P2表示两个n位的父代染色体，f(P1)和f(P2)分别表示两个父代的适应值，C表示子代染色体。点交叉操作如下： step1:i=1 step2:如果P1[i]=P2[i]，则C[i]=P1[i]=P2[i] step3:如果P1[i]

P2[i]，则 step3.1:以概率p=

f(P1)/(f(P1)+f(P2))

让C[i]:=P1[i] step3.2:以概率1-p让C[i]:=P2[i] step4:如果i=n，停止；否则i=i+1，返回step2交叉策略按前述的各种策略进行，每一种策略都是一子解空间。随机可依据问题选择不同的概率模型，进行处理。策略选择的随机性怎样将随机和交叉结合在一起呢【示例】行交叉

设P1和P2表示两个k*h位的父代染色体，其中k为每一段的位数，h为染色体的分段数目，f(P1)和f(P2)分别表示两个父代的适应度值，C表示子代染色体。 step1:产生一个0至h-1的随机数x；

step2:如果P1[x*k+i]=P2[x*k+i]foralli=1,…,k，则不产生后代；

step3:如果P1[x*k+i]

P2[x*k+i]foranyi=1,…,k，则以概率p=f(P1)/(f(P1)+f(P2))让P1[x*k+i]与P2[x*k+i]fori=1,…,k交换；//注：两个染色体的x段如相同,则不交换,否则以概率p进行交换。策略选择的随机性怎样将随机和交叉结合在一起呢【示例】列交叉

设P1和P2表示两个k*h位的父代染色体，其中k为每一段的位数，h为染色体的分段数目，f(P1)和f(P2)分别表示两个父代的适应度值，C表示子代染色体。 step1:产生一个0至k-1的随机数x；

step2:如果P1[i*k+x]=P2[i*k+x]foralli=1,…,h，则不产生后代； step3:如果P1[i*k+x]

P2[i*k+x]foranyi=1,…,h，则以概率f(P1)/(f(P1)+f(P2))让P1[i*k+x]与P2[i*k+x]交换foralli=1,…h；//注：两个染色体的各段的x位如都相同，则不交换，否则以概率p进行交换。策略选择的随机性怎样将随机和交叉结合在一起呢“点交叉”将覆盖更大的可能解空间，产生更多种新可能解，增加获得最优解的机会；“行交叉”、“列交叉”大大地压缩了可能解的解空间，产生的可能解都是可行解(编码方案将约束条件考虑进去了)

；策略的选择需要折中：选择搜索更加广泛的解空间呢，还是选择压缩搜索空间呢？需要折中。不同的交叉策略对算法的求解质量和收敛速度等是有影响的。没有一种设计能够面面俱到，因此如何在算法不同方面性能之间权衡，也是遗传算法设计过程的关键所在，体现了一定程度的技术性和艺术性。策略选择的随机性不同的交叉随机策略有什么特点策略选择的随机性庞大的解空间子解空间随机/概率结合问题特点的随机/概率模型策略选择的随机性小结第9讲难解性问题求解与算法【自学&拓展】一、问题及其建模二、算法设计要点与解的编码三、策略选择的多样性四、策略选择的随机性五、遗传算法的其他方面实际问题分析:解的形式,解的约束,解空间问题解的编码与解码规则设计:个体(解)的表现型与基因型的变换函数初始种群的规模与生成规则设计种群个体的适应度函数设计遗传规则的设计：交叉、变异终止条件及最终解产生繁衍种群的策略设计解的满意度评估,算法效率的评估以及算法的改进优质个体的选择(汰选)方法设计其他方面回顾：遗传算法的设计要点引入变异操作的目的：一是使遗传算法具有局部的随机搜索能力。二是使遗传算法可维持群体多样性。变异操作是对群体中的某些个体染色体的某些基因进行突变处理变异概率(PM,probabilityofmutation)，控制算法中变异操作的使用频率。变异操作的基本步骤：a)对种群中所有个体以事先设定的变异概率判断是否进行变异；b)对进行变异的个体随机选择变异位置进行变异。其他方面变异适应度函数

1.主要用于度量一个【可能解】接近【最优解】的程度和方向。2.适应度的值通常是非负数，即：适应度越大，可能解越好；反之，适应度越小，可能解越差。（依据适应度的大小对可能解进行选择，以保证适应性能好的可能解有更多的机会繁殖后代）。3.在实际问题中，求解目标通常是费用最小，此时需将求最小目标转换为求最大目标的形式。初始种群中的个体通常是随机产生的。初始种群的规模与个体解，可依据问题解空间的分布特性来选择。其他方面适应度函数与初始种群遗传算法什么时候终止运行？(1)进化次数限制----进化到指定的代数即可终止算法(2)计算耗费的资源限制（如计算时间、计算占用的内存等）--当达到一定的资源占用量时可终止算法。如当产生超过一定数量的不重复可行解后即可终止(3)某一个个体已经满足最优值的条件，即最优值已经找到(4)适应度已经达到饱和，继续进化不会产生适应度更好的个体(5)人为干预(6)以上两种或更多种的组合其他方面终止条件思考1：遗传算法的收敛速度和解的质量有什么关系呢？解的质量，可以使用“近似率”来衡量，所谓近似率是指算法求得的解与问题最优解的近似程度。收敛速度，是指对于具有迭代特征的近似算法，在迭代多少次后能够使得结果稳定(通俗来讲，即结果不再随进一步迭代而发生变化或发生极小的可以被忽略的变化)，它从一定程度反映了算法求解的“快慢”“在执行相同次数的迭代后，近似率高的算法更好”“在达到期望的满意解的前提下，迭代次数越少越好”算法的比较：当不同算法均应用多次后，求得满意解次数越多的算法越好！其他方面遗传算法究竟要研究什么？思考3：染色体编码中什么是“遗传基因”，怎样发现种群的遗传基因，怎样使遗传基因被遗传被继承？一般，染色体基因就是一个二进制位。一个种群的优质个体的编码中：“值相同位”越多的是否就是遗传基因呢？“0、1组合相同的片段”越多是否就是遗传基因呢？例如{00101011,00101001,10100101,01100100}自左而右第3-4位“10”有4个相同，它是否是遗传基因呢？发现了遗传基因后，在交叉变异重组时又怎样使其不受破坏呢？思考2：遗传算法各项参数对算法收敛速度和解的质量有什么影响？各次迭代的种群规模大小，尤其是初始种群规模大小对算法的性能有什么影响呢？不同的交叉变异规则反映了算法对可能解空间的覆盖范围，覆盖范围越大则获得最优解的概率也越大。此外，如变异率、交叉率等，对算法的性能又有什么影响呢？其他方面遗传算法究竟要研究什么？第10讲软件思维：结构-对象-组件-服务哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣第10讲软件思维：结构-对象-组件-服务一、软件系统构造方法的演变二、计算机语言与软件构造能力三、结构化程序设计四、面向对象的核心概念五、面向对象的程序设计六、基于对象框架构造软件结构化程序构造60’s,70’s年代的软件:

结构化程序编程语言：C语言，Fortran语言函数=算法+数据结构系统=函数+函数调用简单的平房Main(){intj;j=HowMuchBeer();}intHowMuchBeer(){int

BeerBottle=1000;int

EmptyBottle=0;fori=0toBeerBottle{EmptyBottle=EmptyBottle+1;if(EmptyBottle==3)then{BeerBottle=BeerBottle+1;

EmptyBottle=0;}}if(EmptyBottle==2) {BeerBottle=BeerBottle+1;

EmptyBottle=0;}Printf(“EmptyBottle=%d”,EmptyBottle);Printf(“BeerBottle=%d”,BeerBottle);}主函数(){

函数1();

函数2();}函数1(){…}函数2(){…}数据结构算法软件系统构造方法的演变面向对象的程序构造消息数据函数函数消息对象=函数+数据结构系统=对象+消息80’s年代的软件:

面向对象的程序编程语言：C++(83)，Java(95)，Visual系列语言(90)等复杂的特色建筑如：巨大拱顶和圆顶如何建设?对象(类)数据函数函数对象(类)数据函数函数对象(类)软件系统构造方法的演变构件化的程序构造构件=实现体+接口实现体=对象+消息系统=构件+连接件90’s年代的软件:

构件化系统编程语言：Visual系列语言；Windows操作系统现代化复杂的高楼如：地基、承重、结构怎样?数据消息函数函数数据函数函数对象1对象2构件的接口构件1构件的接口构件2构件(实现体)软件系统构造方法的演变构件的接口构件化的程序构造90’s年代的软件:

构件化系统基于体系结构与设计模式的软件开发J2EE：Springs，Rails等.NetCORBA中间件予以支撑：Weblogic(BEA)WebSphere(IBM)Tomcat(开源)

…现代化复杂的高楼如：地基、承重、结构怎样?软件系统构造方法的演变服务化的程序构造服务1服务nAB服务1服务m服务1(需求)服务总线:

控制并切换<服务1(需求)>是调用构件A的服务1还是构件B的服务1服务=构件的公共标准的接口系统

=服务

+服务总线构件

=对象

+消息系统

=构件

+连接件如：各建筑之间的互连互通?城镇与城市的构建2000’s年代的软件:

面向服务的体系结构SOA

基于Internet/云计算的体系结构软件系统构造方法的演变简单的平房复杂的特色建筑如：巨大拱顶和圆顶如何建设?不能倒塌是第一位的现代化复杂的高楼如：地基、承重、结构怎样?如：各建筑之间的互连互通?城镇与城市的构建结构化程序：算法+数据结构子程序+函数调用对象化程序：对象+消息构件化程序:构件+体系结构服务化程序：服务+服务总线软件的可靠性、可用性等软件系统构造方法的演变软件系统构造方法的演变过程基于组件/构件的构造对象类对象框架基于对象框架的构造结构框架(中间件)软件系统面向服务的软件系统构造VisualBasic基于VisualBasic的软件开发面向对象的程序设计语言C++，Java，Python，…Springs框架Hibernate框架Struts框架Rails框架--中间件环境……基于xx框架的软件开发WebService&SOASoftwareforCloudSoftwareasaService云环境移动/嵌入环境电脑环境结构化程序设计语言C,Fortran,…高级语言程序设计计算机语言与软件构造能力不同的计算机语言分层架构/事件驱动架构/微核架构/微服务架构/云架构……软件构造能力是计算机/软件工程学科学生未来的主要竞争力软件构造方法发生了很大的变化关于本讲，要注意：内容较多，不能够做到完全理解---导论注重构造思维的理解，不要在意一些细节的不理解---指南进一步学习：MOOC《软件工程专业导论》（中国大学MOOC平台）第5讲软件系统构造--函数-对象-组件与软件框架第6讲软件生命周期第7讲理解问题--软件需求第8讲软件的艺术--软件设计计算机语言与软件构造能力软件系统构造能力的培养决策者(CEO)信息主管(CIO)软件总设计师(CTO)软件架构师项目经理软件设计师软件构造师软件咨询师软件测试师软件配置与维护师IT系统维护师……测练题：关于软件系统开发方法，你理解了哪些_________？构件化程序的编程单位扩大为构件和连接件(框架)（一个构件是将若干个对象/类封装后的程序体，其他对象以接口的形式来访问构件中的对象/类及其函数）。【类比建筑技术：是工业化批量化构造复杂建筑的技术】服务化程序的编程单位扩大为服务和服务总线（一个服务，是构件对外开放的标准的接口，而服务总线是服务能够被调用和执行的基础设施）。【类比建筑技术：是建立互联互通建筑的技术】面向对象程序的编程单位扩大为对象/类和消息传递（一个对象就是若干函数被封装后的程序体）。【类比建筑技术：是构造复杂建筑的技术】结构化程序的编程单位是函数和函数调用(一个函数就是一组数据结构基础上的算法表达)。【类比建筑技术：是盖平房的技术】ABCD提交投票最多可选4项结构化程序设计，也被称为面向过程的程序设计基本语法要素：变量与常量、表达式、语句与函数。主函数main()：主程序函数定义：定义一个新函数，即自己编写的程序段落函数调用：调用一个函数完成一个计算结构化程序设计程序的基本语法要素为控制复杂性，先以函数来代替琐碎的细节，着重考虑函数之间的关系，以及如何解决问题在前一阶段考虑清楚后或编制完成后，再编写其中的每一个函数。而函数的处理同样采取这种思路结构化程序设计传统程序构造及其表达方法----由粗到细上一层次的函数依据下层函数来编写，确认正确后再转至更上层问题处理首先编写一些基础性的函数，并确定其正确后，再处理上一层次的问题。结构化程序设计传统程序构造及其表达方法----也可以由细到粗程序

是若干函数的集合；函数

是若干语句的集合，是具有先后次序的若干语句的集合。函数=算法+数据结构系统=函数+函数调用结构化程序设计再看：什么是程序？测练题：你是如何理解结构化程序的，请选择_________？结构化程序可以自底向上地构造—即先完成基础功能，将基础功能实现为一个个函数；然后再用这些函数构造更为复杂的功能；一层层扩展功能完成最终系统的构造。结构化程序的核心是函数的编写，而函数就是定义了数据结构后，对该数据结构数据的处理算法，算法就是一条条程序语句。因此可以说，函数就是数据结构+算法。结构化程序可以自顶向下地构造—即先将细节性功能定义为一个函数名，然后用函数名的调用来构造复杂功能，待处理完复杂功能后，再来编写细节性功能的程序（即编写该函数的函数体），一层层细化，直到能够被实现。结构化程序的编程单位是语句和函数，函数是将若干语句封装后形成的以函数名来调用的语句的集合。ABCD提交投票最多可选4项现实世界(或者说系统)是由可区分的“对象”构成的…(从系统来看)对象可被看作是一个个具有某种功能/行为的个体

“(从软件系统来看)对象可被看作是一个个可执行某种程序的个体”--对象的“独立性/自主性”对象自己执行自身的动作而无需其他对象干预…“对象自己执行自身的程序而独立于其他对象…”--对象之间的“交互性”面向对象的核心概念为什么要理解面向对象的思维“对象”是相互可区分的一个个“个体”每一对象有唯一的“对象标识”区分于其他对象“对象”是有状态属性的个体每一对象有一组状态属性，即相当于一组数据来刻画其自身的状态信息--对象的属性“对象”是有独立行为或功能的个体每一对象有自己的可以执行的程序--对象的函数(又称为方法)“对象”在接收到需服务的请求时，可为其他对象提供服务…每一对象有一组其可以处理的消息—对象的消息，而响应“消息”的则是对象的函数(或称方法)。张三李四王五面向对象的核心概念核心概念：对象有些对象具有相似的特性描述，组成“类”。各自独立运行的类的实例同类对象的共性形式或者说对象的类型张三王五类是对象的抽象或称对象的“类型”，定义了同类型对象的框架(名字、属性和功能)；对象是类的实例，是实际运行的个体。类对象对象面向对象的核心概念核心概念：类与对象“对象”可隐藏其内部的各种细节对象可将其内部的属性和函数进行隐藏，即所谓的“封装”。对外只通过消息进行交互。苹果

数据：常量、变量一箱苹果----对象A对象A的函数装入一个苹果()，取出一个苹果()移动一箱苹果()一车苹果----对象B对象B的函数行驶()，暂停()装载()，卸载()一车苹果.一箱苹果.一个苹果对象B.对象A.常量对象B.对象A.变量对象B.对象A.函数();对象B.函数();面向对象的核心概念核心概念：封装消息是对象之间传递的内容，如指示、打听、请求……消息是对象之间交互的唯一的内容消息是对象.函数()的调用和执行张三王五请问...(消息)您问…的解答是…(消息)Call王五.回答身高()Execute：

王五.回答身高(){Return(“身高是1.64m”);}面向对象的核心概念核心概念：消息事件是外界产生的一种能够激活对象功能的特殊消息。当发生事件后将给所涉及对象发送一个消息，对象便可执行相应的功能---事件驱动；有人敲门电话铃响张三.电话铃响(){//不接；自动回复在上课；…}张三.有人敲门(){//暂停课程；询问并处理；…}张三.其他(){…….}面向对象的核心概念核心概念：事件继承：一个对象(类)继承另一个对象(类)的属性与函数多态：不同对象对同一消息的不同响应，即允许方法重名。有：虚函数型多态—子类可以重定义父类的函数；重载型多态--同一函数名的函数参数可以有不同的形式。……注意：这些特性不急于在本门课程中理解，本门课程要理解这种面向对象的思维…学习面向对象的思维不仅仅是理解这些概念，更重要的是运用其进行构造…计算机语言如何实现面向对象的思维呢?面向对象的核心概念其它核心概念类与对象，消息与事件，函数或称方法类一个个对象面向对象的程序设计面向对象程序设计的基本要素对象占用相对独立的内存区域怎样实现“若干同类别对象，虽有相同的程序，但却处理不同的数据而产生不同的结果呢?”两方面技术：一是封装，二是对象的自动产生与运行。对象：a1对象：a2类：A1数据D1,D2；函数f1(),f2()；a1.D1,a1.D2；a1.f1()；a1.f2()a2.D1,a2.D2；a2.f1()；a2.f2()对象：a11a11.D1,a11.D2；a11.f1()；a11.f2()数据结构封装了若干个变量；函数封装了若干行的语句；类/对象封装了若干数据结构和函数。定义创建与运行面向对象的程序设计面向对象程序的技术本质类：A1数据D1,D2；函数f1(),f2()；Class

A1

//定义一个类{intD1,D2

//定义变量

intf1();

//定义类中的函数

intf2(); //定义类中的函数

intf1() //类A1的函数f1的程序{//f1的程序语句块}intf2() //类A1的函数f2的程序{//f2的程序语句块1a4=newA2;

//创建类A2的对象a4

//f2的程序语句块2D1=calla4.f3();//调用另一对象的某一函数

//f2的程序语句块3

}}定义“类”，即相当于定义一系列对象的对象结构。用“类”，创建一个个对象对象之间进行交互面向对象的程序设计像定义函数一样，定义“类”对象：a1对象：a2类：A1数据D1,D2；函数f1(),f2()；a1.D1,a1.D2；a1.f1()；a1.f2()a2.D1,