1、1/87目录o 第一章第一章绪论绪论o 第二章搜索技术第二章搜索技术o 第三章第三章知识表示知识表示o 第四章推理技术第四章推理技术 o 第五章第五章 机器学习机器学习o 第六章计算智能第六章计算智能 o 第七章数据挖掘第七章数据挖掘o 第八章第八章 智能体技术智能体技术2/87o 可求解与难求解问题o 遗传算法遗传算法o 群智能算法群智能算法3/87现实世界中的问题分类6.1 可求解与难求解问题可求解与难求解问题 计算机在有限时间内能够求解的计算机在有限时间内能够求解的(可求解问题可求解问题)计算机在有限时间内不能求解的计算机在有限时间内不能求解的(难求解问题难求解问题)计算机完全不能求解的
2、计算机完全不能求解的(不可计算问题不可计算问题)计算复杂性是指问题的一种特性，即利用计算机求解问题的计算复杂性是指问题的一种特性，即利用计算机求解问题的难易性或难易程度，其衡量标准：难易性或难易程度，其衡量标准：计算所需的步数或指令条数计算所需的步数或指令条数(即时间复杂度即时间复杂度)计算所需的存储空间大小计算所需的存储空间大小(即空间复杂度即空间复杂度)-通常表达为关于问题规模通常表达为关于问题规模n的一个函数的一个函数 O(f(n)问题的计算复杂性问题的计算复杂性4/87问题规模n计算量10 10！20 20！100 100！1000 1000！10000 10000！20！=1.216
3、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(log n),O(n),O(n log n),O(nb)6.1 可求解与难求解问题可求解与难求解问题5/87P类问题，类问题，NP类问题，类问题，NPC类问题类问题nP类问题类问题：多项式问题多项式问题(Polynomial Problem)，指计算机可以在有限时，指计算机可以在有限时间内
4、求解的问题，即：间内求解的问题，即：P类问题是可以找出一个呈现类问题是可以找出一个呈现O(na)复杂性算法的问复杂性算法的问题，其中题，其中a为常数。为常数。nNP类问题类问题：非确定性多项式问题：非确定性多项式问题(Non-deterministic Polynomial)。有些。有些问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到结果，这就是非确定性问题结果，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项
5、式时间内可以由求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题，就是一个算法验证一个解是否正确的非确定性问题，就是NP类问题。类问题。nNPC问题问题：完全非确定性多项式问题：完全非确定性多项式问题(NP-Complete)。如果。如果NP问题的所问题的所有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非确定性多项式问题，即确定性多项式问题，即NP-Complete问题。问题。6.1 可求解与难求解问题可求解与难求解问题6/876.1 可求解与难求解问题可求解与
6、难求解问题旅行商问题旅行商问题 对于销售员旅行问题（对于销售员旅行问题（Travelling Salesman Problem,TSP），），设有设有n个城市，城市个城市，城市I和城市和城市j之间的距离之间的距离为为d(i,j)，要求找到，要求找到一条遍访每个城市一一条遍访每个城市一次而且恰好一次的次而且恰好一次的旅行线路，使其路径旅行线路，使其路径总长度为最短。总长度为最短。7/87NPC类问题求解类问题求解穷举法或称遍历法穷举法或称遍历法：对解空间中的：对解空间中的每一个可能解进行验证，直到所有每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到的解都被验证是否正确，便能得到精确的
7、结果精确的结果-精确解精确解可能是可能是O(n!)或或O(an)近似解求解算法近似解求解算法-近似解近似解应该是应该是O(na)=|近似解近似解 精确解精确解|满意解：满意解：充分小时的近似解充分小时的近似解TSP问题的问题的遍历算法遍历算法TSP问题的问题的贪心算法贪心算法仿生学算法仿生学算法进化算法，遗传算法，蚁群算法，蜂群算法进化算法，遗传算法，蚁群算法，蜂群算法,6.1 可求解与难求解问题可求解与难求解问题8/87 6.2 遗传算法 生物群体的生存过程普遍遵循达尔文的物竞天择、适者生生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大
8、存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境。自然环境。9/87 6.2 遗传算法 生物染色体用数学方式或计算机方式来体现就是一串数码生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力用对应一个染色体的，仍叫染色体，有时也叫个体；适应能力用对应一个染色体的数值来衡量；染色体的选择或淘汰问题是按求最大还是最小问数值来衡量；染色体的选择或淘汰问题是按求最大还是最小问题来进行。题来进行。遗传算法遗传算法（Genetic AlgorichmsGAGenetic AlgorichmsGA）是模仿生物遗传学和自是模仿生物遗传学和自然选择机理，通过人工方
9、式构造的一类优化搜索算法，是对生然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要形物进化过程进行的一种数学仿真，是进化计算的一种最重要形式。式。10/876.2 遗传算法 遗传算法提出：遗传算法提出：于于2020世纪世纪6060年代由密歇根年代由密歇根(Michigan)(Michigan)大学大学Hollstien,BagleyhHollstien,Bagleyh和和RosenbergRosenberg等人在其博士论文中首先加以等人在其博士论文中首先加以研究；研究；19751975年，美国年，美国J.H.HollandJ.H.Holl
10、and教授在其著作教授在其著作“Adaptation Adaptation in Natural and Artificial Systemsin Natural and Artificial Systems”中系统地阐述了遗传算中系统地阐述了遗传算法，给出了遗传算法的基本定理和大量的数学理论证明。法，给出了遗传算法的基本定理和大量的数学理论证明。遗传算法发展：遗传算法发展：David E.GoldbergDavid E.Goldberg教授教授19891989年出版了年出版了 “Genetic AlgorichmsGenetic Algorichms”一书，这一著作通常被认为是遗传算法一书，
11、这一著作通常被认为是遗传算法的方法、理论及应用的全面系统的总结。从的方法、理论及应用的全面系统的总结。从19851985年起，国际上年起，国际上开始陆续举行遗传算法的国际会议，后来又更名为进化计算。开始陆续举行遗传算法的国际会议，后来又更名为进化计算。参加进化计算国际会议的人数及收录文章的数量、广度和深度参加进化计算国际会议的人数及收录文章的数量、广度和深度逐年扩大。从此，进化计算逐渐成为人们用来解决高度复杂问逐年扩大。从此，进化计算逐渐成为人们用来解决高度复杂问题的新思路和新方法。题的新思路和新方法。11/876.2 遗传算法 遗传算法特点：遗传算法特点：遗传算法是一种基于空间搜索的算法，它
12、通过遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文适者生存的理论，模拟自自然选择、遗传、变异等操作以及达尔文适者生存的理论，模拟自然进化过程来寻找所求问题的解答。遗传算法具有以下特点：然进化过程来寻找所求问题的解答。遗传算法具有以下特点：(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；遗传算法是对参数集合的编码而非针对参数本身进行进化；(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其遗传算法利用目标函数的适应度这一信息而非利用导数或其它
13、辅助信息来指导搜索；它辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。则进行随机操作。12/876.2 遗传算法6.2.1 6.2.1 遗传算法的基本原理遗传算法的基本原理 霍兰德提出的遗传算法通常称为简单遗传算法（霍兰德提出的遗传算法通常称为简单遗传算法（SGA）。）。编码与解码编码与解码 许多应用问题的结构很复杂，但可以化为简单的位串形许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示。将问题结构变换为位串形式编码表示的过程叫编式编码表示。将问题结构变换为位串形式编码表示的过程叫编码；
14、而相反将位串形式编码表示变换为原问题结构的过程叫解码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。码或译码。把位串形式编码表示叫染色体，有时也叫个体。13/876.2 遗传算法对于对于TSP问题，可以按一条回路中城市的次序进行编码。问题，可以按一条回路中城市的次序进行编码。从城市从城市w1开始，依次经过城市开始，依次经过城市w2，wn，最后回到城市，最后回到城市w1，我们就有如下编码表示：，我们就有如下编码表示：w1 w2 wn由于是回路，记由于是回路，记wn+1=w1。它其实是。它其实是1，n的一个循环的一个循环排列。要注意排列。要注
15、意w1，w2，wn是互不相同的。是互不相同的。14/876.2 遗传算法适应度函数适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（色体都能进行度量的函数，叫适应度函数（fitness function）。）。TSP的目标是路径总长度为最短，自然地，路径总长度的倒数的目标是路径总长度为最短，自然地，路径总长度的倒数就可作为就可作为TSP问题的适应度函数问题的适应度函数:其中其中wn+1=w1适应度函数要有效反映每一个染色体与问题的最优解染色适应度函数要有效反映每一个染色体与问题的最优解染色体之间
16、的差距。适应度函数的取值大小与求解问题对象的意义体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。有很大的关系。n1j1jj21)w,d(w/1),.,(nwwwf15/876.2 遗传算法遗传操作遗传操作简单遗传算法的遗传操作主要有有三种简单遗传算法的遗传操作主要有有三种:选择选择(selection)、交叉、交叉(crossover)、变异、变异(mutation)。改进的遗传算法大量扩充了遗传操。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。作，以达到更高的效率。选择操作也叫复制（选择操作也叫复制（reproduction）操作，根据个体的适应度）操作，根据个体的
17、适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。简单遗传算法采用赌轮选择机制，令简单遗传算法采用赌轮选择机制，令fi表示群体的适应度值之表示群体的适应度值之总和，总和，fi表示种群中第表示种群中第i个染色体的适应度值，它产生后代的能力个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额正好为其适应度值所占份额fi/fi。16/876.2 遗传算法交叉操作的简单方式是将被选择出的两个个体交叉操作的简单方式是将被选择出的两个个体P1和和P2作为父母作为父母个体，将两者的部分码值进行交换。个体，将两者的部分码值进行交换。产
18、生一个产生一个17之间的随机数之间的随机数c，假设为，假设为3，则将，则将P1和和P2的低的低3位交换位交换1 0 0 0 1 1 1 0P1：1 1 0 1 1 0 0 1P2：1 0 0 0 1 1 1 0P1：1 1 0 1 1 0 0 1P2：1 0 0 0 1 0 0 11 1 0 1 1 1 1 0Q1：Q2：17/876.2 遗传算法变异操作的简单方式是改变数码串的某个位置上的数码。变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将二进制编码表示的简单变异操作是将0与与1互换：互换：0变异为变异为1，1变变异为异为0。随机产生一个随机产生一个18之
19、间的数之间的数k，假设，假设k=5，对从右往左第，对从右往左第5位变异位变异操作。操作。10100110118/876.2 遗传算法控制参数控制参数交叉发生的概率：交叉发生的概率：0.60.95 变异的概率：变异的概率：0.0010.01 种群的个数：种群的个数：30100 个体的长度：定长和变长个体的长度：定长和变长 19/876.2 遗传算法6.2.2 6.2.2 遗传算法的结构遗传算法的结构选择：由个体适应度值决定选择：由个体适应度值决定 的某个规则。的某个规则。交叉：按概率交叉：按概率Pc进行进行变异：按概率变异：按概率Pm进行进行终止条件：终止条件：完成了预先给定的进化代数完成了预先
20、给定的进化代数 种群中的最优个体在连续若干代种群中的最优个体在连续若干代 没有改进或平均适应度在连续若没有改进或平均适应度在连续若 干代基本没有改进干代基本没有改进开始开始初始化种群初始化种群选择操作选择操作终止条件终止条件否否适应度最有优个体适应度最有优个体计算适应度值计算适应度值交叉操作交叉操作变异操作变异操作结束结束20/876.2 遗传算法6.2.3 6.2.3 遗传算法的性能遗传算法的性能 遗传算法求得的解是一满意解。影响解质量的因素：遗传算法求得的解是一满意解。影响解质量的因素：种群的数量：太小缺少多样性，太多影响效率种群的数量：太小缺少多样性，太多影响效率 适应度函数：提升优良个
21、体的适应度适应度函数：提升优良个体的适应度 交叉和变异：不同的问题需构造性能更优的交叉和变异操作交叉和变异：不同的问题需构造性能更优的交叉和变异操作 交叉概率和变异概率：交叉概率和变异概率：21/87分析：对该问题虽然也可以采用枚举的方法来解决分析：对该问题虽然也可以采用枚举的方法来解决,但枚举法却但枚举法却是一种效率很低的方法是一种效率很低的方法.可运用遗传算法来求解该问题可运用遗传算法来求解该问题.解：首先对问题进行初始化，以获得初始种群解：首先对问题进行初始化，以获得初始种群;（1 1）确定编码方案：将确定编码方案：将x x编码表示为染色体的数字符号串。编码表示为染色体的数字符号串。针对
22、本题自变量针对本题自变量x x定义域定义域,取值范围为取值范围为00，31,31,考虑采用二进考虑采用二进制数来对其编码制数来对其编码,由由2 25 5=32,=32,故使用故使用5 5位无符号二进制数组成位无符号二进制数组成染色体数字字符串染色体数字字符串,用以表达变量用以表达变量x x及问题的解答过程。及问题的解答过程。例例:设有函数设有函数f(xf(x)=)=x x2 2,用遗传算法求其自变量用遗传算法求其自变量x x在区间在区间00，31 31 取整数值时的最大值。取整数值时的最大值。6.2 遗传算法22/87 （2 2）选择初始种群）选择初始种群:通过随机的方法来产生染色体的数通过随
23、机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位字串，并组成初始种群。例如，为得到数字串的某位又称之为基因又称之为基因(genes)(genes)，使用计算机在，使用计算机在0 01 1之间产生之间产生随机数随机数K K，并按照数，并按照数K K的变化区域来规定基因代码如下：的变化区域来规定基因代码如下：0 0，（0 0K K0.50.5）1 1，（0.50.5K K1 1）6.2 遗传算法23/87于是于是随机生成随机生成4 4个个染色体的数字符串为：染色体的数字符串为：0110101101110001100001000010001001110011从而构造了初始种群，
24、完成了遗传算法的准备。从而构造了初始种群，完成了遗传算法的准备。6.2 遗传算法24/876.2 遗传算法染色体染色体标号标号 串串 x 适应值适应值f(x)=x2占整体的百分占整体的百分数数 1 1 0110101101 169169 14.4%14.4%2 2 1100011000 576576 49.2%49.2%3 3 0100001000 6464 5.5%5.5%4 4 1001110011 361361 30.9%30.9%总计总计（初始种群值）（初始种群值）11701170 100.0%100.0%25/87（3 3）复制）复制(选择选择)选择适应值大的串作为母本，使在下一代中
25、有更多的机会繁殖选择适应值大的串作为母本，使在下一代中有更多的机会繁殖其子孙。其子孙。要在四个种子个体中做选择，要求仍然得到四个染色体，可依要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则：据适应度概率比例制定如下规则：低于低于0.1250.125以下的染色体被淘汰；以下的染色体被淘汰；在在0.1250.1250.3750.375之间的染色体被复制一个；之间的染色体被复制一个；在在0.3750.3750.6250.625之间的染色体被复制两个；之间的染色体被复制两个；在在0.6250.6250.8750.875之间的染色体被复制三个；之间的染色体被复制三个；在
26、在0.8750.875以上的染色体可复制四个。以上的染色体可复制四个。6.2 遗传算法26/87对应于上例，按照适应度的计算，经复制操作后，得到新对应于上例，按照适应度的计算，经复制操作后，得到新的染色体种群为的染色体种群为 01101 01101 11000 11000 11000 11000 10011 100116.2 遗传算法27/87某个染色体是否被复制某个染色体是否被复制,可以通过概率决策法、适应度可以通过概率决策法、适应度比例法或比例法或“轮盘赌轮盘赌”的随机方法来断定。对应轮盘赌的随机方法来断定。对应轮盘赌转盘的随机方法转盘的随机方法,根据表根据表6.16.1数据，绘制出的轮盘
27、赌转数据，绘制出的轮盘赌转盘盘,如图所示如图所示:6.2 遗传算法49.230.9%14.4%5.5%28/876.2 遗传算法 初始种群初始种群 x 值值 适应度适应度 选择概率选择概率 期望值期望值 实际复制数实际复制数编号编号 （随机产生）（随机产生）（无符号整数）（无符号整数）f(x)=x2 Pc f(xi)/fA （或转轮法）（或转轮法）1 01101 13 169 0.144 0.58 11 01101 13 169 0.144 0.58 1 2 11000 24 576 0.492 1.97 2 2 11000 24 576 0.492 1.97 2 3 01000 8 64 0
28、.055 0.22 0 3 01000 8 64 0.055 0.22 0 4 10011 19 361 0.309 1.23 1 4 10011 19 361 0.309 1.23 1 1170 1.00 4.00 4.0 1170 1.00 4.00 4.0 平均平均(A(A)293293 0.25 1.00 1.0 0.25 1.00 1.0 MAX MAX 576576 0.49 1.97 2.0 0.49 1.97 2.0初始种群染色体准备复制操作的各项计算数据初始种群染色体准备复制操作的各项计算数据 29/87（4 4）交叉交叉 交叉具体分两步：将新复制产生的交叉具体分两步：将新复
29、制产生的染色体染色体随机两两匹配随机两两匹配,称其为双亲染色体称其为双亲染色体；再把；再把双亲染色体双亲染色体进行交叉繁殖。进行交叉繁殖。交叉的实现交叉的实现:设染色体数字串长度为设染色体数字串长度为L L，把，把L L个数字位间空个数字位间空隙分别标记为：隙分别标记为：1 1，2 2，L L1 1 随机从随机从11，L L11中选取某一整数位置中选取某一整数位置k k，0k0kL L 交换双亲染色体交换点位置交换双亲染色体交换点位置k k右边的部分，就形成了两个新的右边的部分，就形成了两个新的数字符串（也可以只交换其中的第数字符串（也可以只交换其中的第k k基因），得到了两个新基因），得到了
30、两个新的染色体，又称之为下一代染色体。的染色体，又称之为下一代染色体。6.2 遗传算法30/876.2 遗传算法31/876.2 遗传算法编编号号复制操作复制操作后的区配后的区配池池匹配号匹配号(随随机选取机选取)交叉空隙交叉空隙位位(随 机随 机选取选取)交 叉 后交 叉 后新种群新种群新种群新种群x值值适应度适应度f(x)=x21 101101011012 22 201000010008 864642 211000110001 12 211101111012929841841311000110004 44 4110011100125256256254 410011100113 34 410
31、000100001616256256总计（总计（）17861786平均平均(A(A)446.5最大值最大值(MAX(MAX)841841复制、交叉操作的各项数据复制、交叉操作的各项数据 32/87 （5 5）变异）变异 设变异概率取为设变异概率取为0.001,0.001,则对于种群总共有则对于种群总共有2020个基因位个基因位.期望的变异串位数计算期望的变异串位数计算:20:200.001=0.02(0.001=0.02(位位),),故一般来说故一般来说,该例中无基因位数值的改变该例中无基因位数值的改变.从表中可以看出从表中可以看出,每每经过一次复制、交叉和变异操作后经过一次复制、交叉和变异操
32、作后,目标函数的最优值和平均值目标函数的最优值和平均值就会有所提高。就会有所提高。在上例中，种群的平均适应值从在上例中，种群的平均适应值从293293增至增至446.5;446.5;最大的适应最大的适应度数值从度数值从576576增至增至841841。特点：每经一次进化计算步骤特点：每经一次进化计算步骤,问题解答便向着最优方向前进问题解答便向着最优方向前进了一步了一步;若该过程一直进行下去若该过程一直进行下去,就将最终走向全局的最优解就将最终走向全局的最优解.可可见进化计算的每一步操作简单见进化计算的每一步操作简单,并且系统的求解过程是依照计算并且系统的求解过程是依照计算方法与规律来决定方法与
33、规律来决定,与本源问题自身的特性很少相关。与本源问题自身的特性很少相关。6.2 遗传算法33/87 作业调度问题（作业调度问题（jobjob shop scheduling problemshop scheduling problem，JSSPJSSP）对工场内的作业进行组织、调度和管理。对工场内的作业进行组织、调度和管理。例：完成下述三个作业：例：完成下述三个作业：j j1 1：型号：型号a a产品产品3030件；件；j j2 2：型号：型号b b产品产品4545件；件；j j3 3：型号：型号a a产品产品5050件；件；产品产品a,ba,b的生产流程有下述几种选择：的生产流程有下述几种选
34、择：a:a:流程流程a a1 1(opr(opr2 2,opr,opr7 7,opr,opr9 9)；a:a:流程流程a a2 2(opr(opr1 1,opr,opr3 3,opr,opr7 7，opropr8 8)；a:a:流程流程a a3 3(opr(opr4 4,opr,opr6 6)；b:b:流程流程b b1 1(opr(opr2 2,opr,opr6 6,opr,opr7 7)；a:a:流程流程b b2 2(opr(opr1 1,opr,opr9 9)；6.2 遗传算法34/87 作业调度问题（作业调度问题（jobjob shop scheduling problemshop sc
35、heduling problem，JSSPJSSP）此处此处opri 表示第表示第i i种操作过程，每种操作所需要的机器及时间为：种操作过程，每种操作所需要的机器及时间为：opropr1 1 ：(m(m1 1 10)(m 10)(m3 3 20)20)opropr2 2 ：(m(m2 2 20)20)opropr3 3 ：(m(m2 2 20)(m 20)(m3 3 30)30)opropr4 4 ：(m(m1 1 10)(m 10)(m2 2 30)(m 30)(m3 3 20)20)opropr5 5 ：(m(m1 1 10)(m 10)(m3 3 30)30)opropr6 6 ：(m(
36、m1 1 40)40)opropr7 7 ：(m(m3 3 20)20)opropr8 8 ：(m(m1 1 50)(m 50)(m2 2 30)(m 30)(m3 3 10)10)opropr9 9 ：(m(m2 2 20)(m 20)(m3 3 40)40)此处此处(m(mj j t)t)表示占用机器表示占用机器j j共共t t个时间单元。还可以假设机器关机后个时间单元。还可以假设机器关机后的启动时间为的启动时间为 m m1 1:3:3，m m2 2:5:5，m m3 3:7:76.2 遗传算法35/87 作业调度问题（作业调度问题（jobjob shop scheduling probl
37、emshop scheduling problem，JSSPJSSP）编码策略：为每台机器建立一个优先表（编码策略：为每台机器建立一个优先表（preferencepreference listlist）。该表）。该表的第一个元素为机器的启动时刻，接着是个作业的操作顺序，另外两的第一个元素为机器的启动时刻，接着是个作业的操作顺序，另外两项为项为“等待等待”（waitwait）和）和“闲置闲置”（idleidle）。其译码过程为：只要在）。其译码过程为：只要在某机器的启动时刻，该机器可用，则首先选择其优先表中的第一个允某机器的启动时刻，该机器可用，则首先选择其优先表中的第一个允许操作。例如：许操作
38、。例如：m m1 1:（4040 j j3 3 j j1 1 j j2 2 waitwait idleidle）译码为：在第译码为：在第4040时间步从作业时间步从作业j j3 3中找一产品用机器中找一产品用机器m m1 1生产。如不成生产。如不成功，再从功，再从j j1 1中搜索产品进行中搜索产品进行,遗传算子：遗传算子：n闲置（闲置（run-idlerun-idle）：仅从那些已经等待）：仅从那些已经等待1 1小时以上机器的优先表进行操作小时以上机器的优先表进行操作。n交叉：交换所选机器的有先表交叉：交换所选机器的有先表n打乱（打乱（scramblescramble）：该操作）：该操作“打
39、乱打乱”优先表中的成员。优先表中的成员。6.2 遗传算法36/876.3 群智能算法群智能算法37/87 群智能群智能(Swarm Intelligence,SI)：1992年由年由 Beni,Hack-wood 和和 Wang在分子自动机系统中提出。在分子自动机系统中提出。1999 年年,Bonabeau,Dorigo 和和 Theraulaz 在在 Swarm Intel-ligence:From Natural to Artificial Systems中对群智能进行了详中对群智能进行了详细的论述和分析。细的论述和分析。2003年年 IEEE 第一届国际群智能研讨会在美国印第安纳州首府召
40、第一届国际群智能研讨会在美国印第安纳州首府召开。开。群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。发设计出的算法或分布式解决问题的策略均属于群智能。6.3 群智能算法群智能算法38/87 Swarm 可被描述为一些相互作用相邻个体的集合体可被描述为一些相互作用相邻个体的集合体,蜂群、蚁蜂群、蚁群、鸟群、鱼群都是群、鸟群、鱼群都是Swarm的典型例子。社会性动物群体所拥有的典型例子。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远的这种特性能帮助个体很好
41、地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息，而且群内个体还能处理信息，并根据所获得的信息(包括环境信包括环境信息和附近其它个体的信息息和附近其它个体的信息)改变自身的一些行为模式和规范改变自身的一些行为模式和规范,这样这样就使得群体涌现出一些单个个体所不具备的能力和特性就使得群体涌现出一些单个个体所不具备的能力和特性,尤其是对尤其是对环境
42、的适应能力。这种对环境变化所具有的适应能力可以被认为环境的适应能力。这种对环境变化所具有的适应能力可以被认为是一种智能是一种智能,也就是说动物个体通过聚集成群而涌现出了智能。也就是说动物个体通过聚集成群而涌现出了智能。6.3 群智能算法群智能算法39/876.3 群智能算法群智能算法 SI 的定义进一步推广的定义进一步推广（Bonabeau）:无智能或简单无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为智能的主体通过任何形式的聚集协同而表现出智能行为的特性。的特性。群智能理论还非常不成熟群智能理论还非常不成熟,但已成为有别于传统人但已成为有别于传统人工智能中连接主义、工智能中连接主
43、义、行为主义和符号主义的一种新的行为主义和符号主义的一种新的关于智能的描述方法关于智能的描述方法,并成为人工智能领域的新研究热并成为人工智能领域的新研究热点。点。40/876.3.1 蚁群算法蚁群算法 蚁群算法蚁群算法(Ant Colony OptimizationACO)由由 Colorni,Dorigo 和和 Maniezzo 于于 1991 年提出年提出,它是通过模拟自然界蚂蚁社会的寻找食物它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡出一些蚂蚁分头在四周游荡
44、,如果一只蚂蚁找到食物如果一只蚂蚁找到食物,它就返回巢中它就返回巢中通知同伴并沿途留下通知同伴并沿途留下“信息素信息素”(pheromone)作为蚁群前往食物所作为蚁群前往食物所在地的标记。在地的标记。信息素会逐渐挥发信息素会逐渐挥发,如果两只蚂蚁同时找到同一食物如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中又采取不同路线回到巢中,那么比较绕弯的一条路上信息素的气味会那么比较绕弯的一条路上信息素的气味会比较淡比较淡,蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群将倾向于沿另一条更近的路线前往食物所在地。ACO算法设计虚拟的算法设计虚拟的“蚂蚁蚂蚁”,让它们摸索不同路线让它们摸索不同路
45、线,并留下会随时间逐并留下会随时间逐渐消失的虚拟渐消失的虚拟“信息素信息素”。根据。根据“信息素较浓的路线更近信息素较浓的路线更近”的原的原则则,即可选择出最佳路线。即可选择出最佳路线。6.3 群智能算法群智能算法41/876.3 群智能算法群智能算法42/87 其中其中,和和 两个参数分别用来控制信息素和路径长度的相对重要两个参数分别用来控制信息素和路径长度的相对重要程度。当蚂蚁在所有城市走过一遍之后，路径上的信息素浓度将变程度。当蚂蚁在所有城市走过一遍之后，路径上的信息素浓度将变为为:e(t+1)=(1-)e(t)+e 其中，其中，0 1 用于控制信息素随时间挥发的速度，用于控制信息素随时
46、间挥发的速度，e是上次蚂蚁是上次蚂蚁经过此路段所留下的信息素，未经过则为经过此路段所留下的信息素，未经过则为 0。上式以及。上式以及e可以根据问可以根据问题进行设计。题进行设计。6.3 群智能算法群智能算法43/87 ACO算法应用算法应用 车辆路径问题（车辆路径问题（vehicle routing problem，VRP）已知一批客户，各客户点的位置坐标和货物需求已知，供应商已知一批客户，各客户点的位置坐标和货物需求已知，供应商具有若干派送车辆，运载能力给定，每两车都从起点出发，完成若具有若干派送车辆，运载能力给定，每两车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆、
47、最小的车干客户点的运送任务后再回到起点，要求以最少的车辆、最小的车辆总行程完成货物的派送任务。辆总行程完成货物的派送任务。与与TSP区别：区别：TSP中每只蚂蚁均要经过所有节点，中每只蚂蚁均要经过所有节点，VRP中每只中每只蚂蚁并不需要遍历所有节点；蚂蚁并不需要遍历所有节点；TSP中每只蚂蚁移动只需考虑路径距中每只蚂蚁移动只需考虑路径距离和信息量，离和信息量，VRP中还需考虑车辆容量限制；中还需考虑车辆容量限制；TSP中每只蚂蚁构造中每只蚂蚁构造出来的路径均是一个可行解，出来的路径均是一个可行解，VRP中每只蚂蚁所构造的回路仅是可中每只蚂蚁所构造的回路仅是可行解的一部分。行解的一部分。6.3
48、群智能算法群智能算法44/87 ACO算法应用算法应用 机组最优投入问题（机组最优投入问题（unit commitment，UC）机组最优投入是寻求一个周期内各个负荷水平下机组的最优组合方机组最优投入是寻求一个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用最小，它是一个高维度、非凸的、离散式及开停机计划，使运行费用最小，它是一个高维度、非凸的、离散的非线性组合优化问题，很难找出理论上的最优解。的非线性组合优化问题，很难找出理论上的最优解。UC的目标函数中主要包括两个基本部分的目标函数中主要包括两个基本部分：（：（1）机组的发电费用；）机组的发电费用；（2）机组的费用，同时还必须
49、满足一定的约束条件。）机组的费用，同时还必须满足一定的约束条件。6.3 群智能算法群智能算法45/87 ACO算法应用算法应用 PID参数优化（参数优化（proportional-integral-differential，PID）PID控制器本质上是一种对控制器本质上是一种对“过去过去”、“现在现在”和和“未来未来”信息估信息估计的控制算法计的控制算法。在控制工程领域中约。在控制工程领域中约90%的控制回路具有的控制回路具有PID结构。结构。在常规在常规PID控制算法上发展了大量改进控制算法上发展了大量改进PID算法，如非线性算法，如非线性PID、最优、最优PID、智能、智能PID、自适应、
50、自适应PID等。等。任何任何PID控制器的性能取决于其控制参数优化，三个部分（比例控制器的性能取决于其控制参数优化，三个部分（比例-积分积分-微分）参数分别是微分）参数分别是Kp、Ki、Kd，目标函数主要考虑单位阶跃响应，目标函数主要考虑单位阶跃响应超调量超调量、上升时间、上升时间tr以及调整时间以及调整时间ts。6.3 群智能算法群智能算法46/87 ACO算法应用算法应用 其他应用：其他应用：岩土工程：边坡非圆弧临界滑动面搜索技术，边坡稳定性分析，高岩土工程：边坡非圆弧临界滑动面搜索技术，边坡稳定性分析，高填石路堤稳定性和边坡稳定性分析填石路堤稳定性和边坡稳定性分析。化学工程：化学计量学科
