1、计算智能 可求解与难求解问题 遗传算法 群智能算法现实世界中的问题分类1 可求解与难求解问题 计算机在有限时间内能够求解的(可求解问题) 计算机在有限时间内不能求解的(难求解问题) 计算机完全不能求解的(不可计算问题)计算复杂性是指问题的一种特性，即利用计算机求解问题的难易性或难易程度，其衡量标准： 计算所需的步数或指令条数(即时间复杂度) 计算所需的存储空间大小(即空间复杂度)-通常表达为关于问题规模n的一个函数 O(f(n)问题的计算复杂性问题规模n计算量10 10！20 20！100 100！1000 1000！10000 10000！20！= 1.2161017203 = 8000O(
2、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)1 可求解与难求解问题P类问题，NP类问题，NPC类问题nP类问题： 多项式问题(Polynomial Problem)，指计算机可以在有限时间内求解的问题，即：P类问题是可以找出一个呈现O(na)复杂性算法的问题，其中a为常数。nNP类问题：非确定性多项式问题(Non
3、-deterministic Polynomial)。有些问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到结果，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题，就是NP类问题。nNPC问题：完全非确定性多项式问题(NP-Complete)。如果NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非确定性多项式问题，即NP-Complete问题。1 可求解与难求解问题1 可求解与难求解问题旅行商问题 对于销售员旅行问题（T
4、ravelling Salesman Problem, TSP），设有n个城市，城市I和城市j之间的距离为d(i,j)，要求找到一条遍访每个城市一次而且恰好一次的旅行线路，使其路径总长度为最短。NPC类问题求解穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果-精确解可能是O(n!)或O(an)近似解求解算法-近似解应该是O(na) = | 近似解 精确解 |满意解： 充分小时的近似解TSP问题的遍历算法TSP问题的贪心算法仿生学算法进化算法，遗传算法，蚁群算法，蜂群算法, 1 可求解与难求解问题 2 遗传算法 生物群体的生存过程普遍遵循达尔文
5、的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境。 2 遗传算法 生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力用对应一个染色体的数值来衡量；染色体的选择或淘汰问题是按求最大还是最小问题来进行。 遗传算法（Genetic AlgorichmsGA）是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要形式。 2 遗传算法 遗传算法提出：于20世纪60年代由密歇根(Michigan)大学Hollstien, Bagleyh和Rosenberg等人在其博士
6、论文中首先加以研究；1975年，美国J.H.Holland教授在其著作“Adaptation in Natural and Artificial Systems”中系统地阐述了遗传算法，给出了遗传算法的基本定理和大量的数学理论证明。 遗传算法发展：David E. Goldberg教授1989年出版了 “Genetic Algorichms”一书，这一著作通常被认为是遗传算法的方法、理论及应用的全面系统的总结。从1985年起，国际上开始陆续举行遗传算法的国际会议，后来又更名为进化计算。参加进化计算国际会议的人数及收录文章的数量、广度和深度逐年扩大。从此，进化计算逐渐成为人们用来解决高度复杂问题
7、的新思路和新方法。 2 遗传算法 遗传算法特点：遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文适者生存的理论，模拟自然进化过程来寻找所求问题的解答。遗传算法具有以下特点：(1) 遗传算法是对参数集合的编码而非针对参数本身进行进化；(2) 遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3) 遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；(4) 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。2 遗传算法2.1 遗传算法的基本原理 霍兰德提出的遗传算法通常称为简单遗传算法（SGA）。编码与解码 许多应用问题的结构
8、很复杂，但可以化为简单的位串形式编码表示。将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。2 遗传算法对于TSP问题，可以按一条回路中城市的次序进行编码。从城市w1开始，依次经过城市w2 ，wn，最后回到城市w1，我们就有如下编码表示：w1 w2 wn由于是回路，记wn+1=w1。它其实是1，n的一个循环排列。要注意w1，w2，wn是互不相同的。2 遗传算法n1j1jj21)w,d(w/1),.,(nwwwf适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫
9、适应度函数（fitness function）。TSP的目标是路径总长度为最短，自然地，路径总长度的倒数就可作为TSP问题的适应度函数:其中wn+1=w1适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。 2 遗传算法遗传操作简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。 选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。简单遗传算法
10、采用赌轮选择机制，令fi表示群体的适应度值之总和， fi表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额fi /fi。2 遗传算法1 0 0 0 1 1 1 0交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。 产生一个17之间的随机数c，假设为3，则将P1和P2的低3位交换P1：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：2 遗传算法10100110变异操作的简单方式是改变数码串的某个位置上的
11、数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。随机产生一个18之间的数k，假设k=5，对从右往左第5位变异操作。 12 遗传算法控制参数交叉发生的概率：0.60.95 变异的概率：0.0010.01 种群的个数：30100 个体的长度：定长和变长 2 遗传算法2.2 遗传算法的结构选择：由个体适应度值决定 的某个规则。交叉：按概率Pc进行变异：按概率Pm进行终止条件： 完成了预先给定的进化代数 种群中的最优个体在连续若干代 没有改进或平均适应度在连续若 干代基本没有改进开始初始化种群选择操作终止条件否适应度最有优个体计算适应度值交叉操作变异操作结束2 遗传算法2.3
12、 遗传算法的性能 遗传算法求得的解是一满意解。影响解质量的因素： 种群的数量：太小缺少多样性，太多影响效率 适应度函数：提升优良个体的适应度 交叉和变异：不同的问题需构造性能更优的交叉和变异操作 交叉概率和变异概率：2 遗传算法分析：对该问题虽然也可以采用枚举的方法来解决,但枚举法却是一种效率很低的方法.可运用遗传算法来求解该问题.解：首先对问题进行初始化，以获得初始种群; （1） 确定编码方案：将x编码表示为染色体的数字符号串。针对本题自变量x定义域,取值范围为0，31,考虑采用二进制数来对其编码,由25 = 32,故使用5位无符号二进制数组成染色体数字字符串,用以表达变量x及问题的解答过程
13、。 例: 设有函数f(x)=x2, 用遗传算法求其自变量x在区间0，31 取整数值时的最大值。 2 遗传算法 （2）选择初始种群:通过随机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位又称之为基因(genes)，使用计算机在01之间产生随机数K，并按照数K的变化区域来规定基因代码如下： 0， （0K0.5） 1， （0.5K1）2 遗传算法于是随机生成4个染色体的数字符串为： 01101110000100010011从而构造了初始种群，完成了遗传算法的准备。2 遗传算法染色体标号 串 x 适应值f (x) = x2占整体的百分数 1 01101 169 14.4 % 2
14、11000 576 49.2% 3 01000 64 5.5% 4 10011 361 30.9% 总计（初始种群值） 1170 100.0%2 遗传算法（3）复制(选择)选择适应值大的串作为母本，使在下一代中有更多的机会繁殖其子孙。要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则： 低于0.125以下的染色体被淘汰； 在0.1250.375之间的染色体被复制一个； 在0.3750.625之间的染色体被复制两个； 在0.6250.875之间的染色体被复制三个； 在0.875以上的染色体可复制四个。2 遗传算法对应于上例，按照适应度的计算，经复制操作后，得到新的
15、染色体种群为 01101 11000 11000 100112 遗传算法某个染色体是否被复制,可以通过概率决策法、适应度比例法或“轮盘赌”的随机方法来断定。对应轮盘赌转盘的随机方法,根据表1数据，绘制出的轮盘赌转盘,如图所示:49.230.9%14.4%5.5%2 遗传算法 初始种群 x 值 适应度 选择概率 期望值 实际复制数编号 （随机产生） （无符号整数） f (x) = x2 Pc f(xi)/fA （或转轮法） 1 01101 13 169 0.144 0.58 1 2 11000 24 576 0.492 1.97 2 3 01000 8 64 0.055 0.22 0 4 100
16、11 19 361 0.309 1.23 1 1170 1.00 4.00 4.0 平均(A) 293 0.25 1.00 1.0 MAX 576 0.49 1.97 2.0初始种群染色体准备复制操作的各项计算数据 2 遗传算法（4）交叉 交叉具体分两步：将新复制产生的染色体随机两两匹配,称其为双亲染色体；再把双亲染色体进行交叉繁殖。 交叉的实现: 设染色体数字串长度为L，把L个数字位间空隙分别标记为： 1，2，L1 随机从1，L1中选取某一整数位置k，0kL 交换双亲染色体交换点位置k右边的部分，就形成了两个新的数字符串（也可以只交换其中的第k基因），得到了两个新的染色体，又称之为下一代染色
17、体。2 遗传算法2 遗传算法编号复制操作后的区配池匹配号(随机选取)交叉空隙位(随机选取)交 叉 后新种群新种群x值适应度f(x) = x21011012201000864211000121110129841311000441100125625410011341000016256总计（）1786平均(A)445最大值(MAX) 841复制、交叉操作的各项数据 2 遗传算法 （5）变异 设变异概率取为0.001,则对于种群总共有20个基因位. 期望的变异串位数计算:200.001 =0.02(位), 故一般来说,该例中无基因位数值的改变.从表中可以看出,每经过一次复制、交叉和变异操作后,目标函数
18、的最优值和平均值就会有所提高。 在上例中，种群的平均适应值从293增至445;最大的适应度数值从576增至841。 特点：每经一次进化计算步骤,问题解答便向着最优方向前进了一步;若该过程一直进行下去,就将最终走向全局的最优解.可见进化计算的每一步操作简单,并且系统的求解过程是依照计算方法与规律来决定,与本源问题自身的特性很少相关。 2 遗传算法 作业调度问题（job shop scheduling problem，JSSP） 对工场内的作业进行组织、调度和管理。 例：完成下述三个作业： j1：型号a产品30件； j2：型号b产品45件； j3：型号a产品50件； 产品a,b的生产流程有下述几种
19、选择： a: 流程a1(opr2, opr7, opr9)； a: 流程a2(opr1, opr3, opr7，opr8)； a: 流程a3(opr4, opr6)； b: 流程b1(opr2, opr6, opr7)； a: 流程b2(opr1, opr9)； 2 遗传算法 作业调度问题（job shop scheduling problem，JSSP） 此处opri 表示第i种操作过程，每种操作所需要的机器及时间为： opr1 ：(m1 10)(m3 20) opr2 ：(m2 20) opr3 ：(m2 20)(m3 30) opr4 ：(m1 10) (m2 30)(m3 20) op
20、r5 ：(m1 10)(m3 30) opr6 ：(m1 40) opr7 ：(m3 20) opr8 ：(m1 50) (m2 30)(m3 10) opr9 ：(m2 20)(m3 40) 此处(mj t)表示占用机器j共t个时间单元。还可以假设机器关机后的启动时间为 m1:3，m2:5，m3:72 遗传算法 作业调度问题（job shop scheduling problem，JSSP） 编码策略：为每台机器建立一个优先表（preference list）。该表的第一个元素为机器的启动时刻，接着是个作业的操作顺序，另外两项为“等待”（wait）和“闲置”（idle）。其译码过程为：只要在
21、某机器的启动时刻，该机器可用，则首先选择其优先表中的第一个允许操作。例如： m1:（40 j3 j1 j2 wait idle） 译码为：在第40时间步从作业j3中找一产品用机器m1生产。如不成功，再从j1中搜索产品进行, 遗传算子： 闲置（run-idle）：仅从那些已经等待1小时以上机器的优先表进行操作。 交叉：交换所选机器的有先表 打乱（scramble）：该操作“打乱”优先表中的成员。3 群智能算法3 群智能算法 群智能( Swarm Intelligence, SI)： 1992年由 Beni, Hack-wood 和 Wang在分子自动机系统中提出。 1999 年, Bonabea
22、u, Dorigo 和 Theraulaz 在 Swarm Intel-ligence: From Natural to Artificial Systems中对群智能进行了详细的论述和分析。 2003年 IEEE 第一届国际群智能研讨会在美国印第安纳州首府召开。 群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。 3 群智能算法 Swarm 可被描述为一些相互作用相邻个体的集合体, 蜂群、蚁群、鸟群、鱼群都是Swarm的典型例子。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，
23、其根本原因在于个体之间存在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息 (包括环境信息和附近其它个体的信息)改变自身的一些行为模式和规范, 这样就使得群体涌现出一些单个个体所不具备的能力和特性, 尤其是对环境的适应能力。这种对环境变化所具有的适应能力可以被认为是一种智能, 也就是说动物个体通过聚集成群而涌现出了智能。 3 群智能算法 SI 的定义进一步推广（Bonabeau）: 无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。 群智能理论还非常不成熟, 但已成为有别于传统人工智能中连接主义、 行为主义和符号主义的一种新
24、的关于智能的描述方法, 并成为人工智能领域的新研究热点。3 群智能算法3.1 蚁群算法 蚁群算法(Ant Colony OptimizationACO)由 Colorni, Dorigo 和 Maniezzo 于 1991 年提出,它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。 自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡, 如果一只蚂蚁找到食物, 它就返回巢中通知同伴并沿途留下 “信息素” ( pheromone)作为蚁群前往食物所在地的标记。 信息素会逐渐挥发, 如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中, 那么比较绕弯的一条路上信息素的气味会比较淡,
25、 蚁群将倾向于沿另一条更近的路线前往食物所在地。ACO算法设计虚拟的 “蚂蚁” , 让它们摸索不同路线, 并留下会随时间逐渐消失的虚拟 “信息素” 。根据 “信息素较浓的路线更近” 的原则, 即可选择出最佳路线。 3 群智能算法3 群智能算法 其中, 和 两个参数分别用来控制信息素和路径长度的相对重要程度。当蚂蚁在所有城市走过一遍之后，路径上的信息素浓度将变为: e( t+1) =( 1- )e( t) +e 其中，0 1 用于控制信息素随时间挥发的速度，e是上次蚂蚁经过此路段所留下的信息素，未经过则为 0。上式以及e可以根据问题进行设计。3 群智能算法 ACO算法应用 车辆路径问题（vehi
26、cle routing problem，VRP） 已知一批客户，各客户点的位置坐标和货物需求已知，供应商具有若干派送车辆，运载能力给定，每两车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆、最小的车辆总行程完成货物的派送任务。 与TSP区别：TSP中每只蚂蚁均要经过所有节点，VRP中每只蚂蚁并不需要遍历所有节点； TSP中每只蚂蚁移动只需考虑路径距离和信息量，VRP中还需考虑车辆容量限制；TSP中每只蚂蚁构造出来的路径均是一个可行解，VRP中每只蚂蚁所构造的回路仅是可行解的一部分。 3 群智能算法 ACO算法应用 机组最优投入问题（unit commitment，UC）
27、机组最优投入是寻求一个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用最小，它是一个高维度、非凸的、离散的非线性组合优化问题，很难找出理论上的最优解。 UC的目标函数中主要包括两个基本部分：（1）机组的发电费用；（2）机组的费用，同时还必须满足一定的约束条件。 3 群智能算法 ACO算法应用 PID参数优化（proportional-integral-differential，PID） PID控制器本质上是一种对“过去”、“现在”和“未来”信息估计的控制算法。在控制工程领域中约90%的控制回路具有PID结构。在常规PID控制算法上发展了大量改进PID算法，如非线性PID、最优PI
28、D、智能PID、自适应PID等。 任何PID控制器的性能取决于其控制参数优化，三个部分（比例-积分-微分）参数分别是Kp、Ki、Kd，目标函数主要考虑单位阶跃响应超调量、上升时间tr以及调整时间ts。3 群智能算法 ACO算法应用 其他应用： 岩土工程：边坡非圆弧临界滑动面搜索技术，边坡稳定性分析，高填石路堤稳定性和边坡稳定性分析。 化学工程：化学计量学科的光谱解析，反应动力学参数估计。 生命科学：蛋白质折叠问题是生物信息学中的一个重要问题，它研究蛋白质从一维序列到三维结构的过程。亲-疏水格点（hydrophobic and polarmonomers，HP）模型是研究该复杂过程的一个最重要的
29、简化模型。蛋白质折叠问题已被证明是一个NP-C问题。ACO算法可用于HP模型测试序列求解。3 群智能算法3.2 粒子群算法 粒子群优化算法（Particle Swarm OptimizationPSO)源于 1987 年 Reynolds 对鸟群社会系统boids的仿真研究，boids 也是一个 CAS。 在 boids 中, 一群鸟在空中飞行, 每个鸟遵守以下三条规则: （1）避免与相邻的鸟发生碰撞冲突; （2）尽量与自己周围的鸟在速度上保持协调和一致; （3）尽量试图向自己所认为的群体中心靠近。 仅仅通过使用这三条规则, boids 系统就出现非常逼真的群体聚集行为, 鸟成群地在空中飞行,
30、 当遇到障碍时它们会分开绕行而过, 随后又会重新形成群体。不过 Reynolds 仅仅将其作为 CAS的一个实例作仿真研究, 而并未将它用于优化计算中, 也无任何实用价值。 3 群智能算法3 群智能算法3 群智能算法3 群智能算法3 群智能算法3 群智能算法3 群智能算法3 群智能算法其次， EC中强调“适者生存” , 不好的个体在竞争中被淘汰; SI 强调 “协同合作” , 不好的个体通过学习向好的方向转变,不好的个体被保留还可以增强群体的多样性。EC中最好的个体通过产生更多的后代来传播自己的基因, 而 SI 中的优秀个体通过吸引其它个体向它靠近来传播自己的敏因。 最后，EC的迭代由选择、变异和交叉重组操作组成，而 SI的迭代中的操作是 “跟随”，ACO中蚂蚁跟随信息素浓度爬行,PSO中粒子跟随最优粒子飞行。在某种程度上看，SI 的跟随操作中隐含了选择、 变异和交叉重组操作。
