人工智能-第5章-高级搜索ppt课件

高级搜索基本概念遗传算法蚁群算法1基本概念—1)组合优化问题很多问题都属于优化问题，或者可以转化为组合优化问题，如TSP问题.设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合，则优化问题可以示为:求解满足g(x)的f(x)最小（大）值问题.如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题.2)算法的时间复杂度对于组合优化问题，由于其可能的解是有限的，当问题的规模(n)比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，就难于求解了.算法复杂度函数(衡量算法复杂性的量级)时间复杂性函数比较（10亿次/秒）一些难的组合优化问题旅行商问题背包问题考试时间安排问题...寻求在可以接受的时间内得到满意解的方法牺牲精度,换取效率3)邻域的概念邻域，简单的说就是一个点附近的其他点的集合.在距离空间，邻域就是以某一点为中心的圆.组合优化问题中的定义：设D是问题的可行解集合,s为其中一可行解,若存在一个映射N，使得：则称N(s)为s的邻域,每个解为s的邻居(邻近解).含义是,对每个解s,有一个解的集合N(s),集合中的解在某些意义上是邻近s的.例：皇后问题S={Si}表示一个可行解，其中Si表示在第i行，第Si列有一个皇后。如四皇后问题的一个解：S=(2,4,1,3)定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置。例：当S=(2,4,1,3)时，其邻域为：N(S)={(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1)}例：旅行商问题求遍历所有n个城市后回到出发点的一个最短路径全连通图，G（n，A），A可表示为是城市间两两相连的一组边.通常用一个城市的序列表示一个可能的解S.通过交换两个城市的位置获取S的邻居例：简单交换方法设S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)通过交换xi和xj两个城市的位置可以得到S的一个邻居：S'=(x1,x2,…xi-1,xj,xi+1,…,xj-1,xi,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1例：逆序交换方法设xi、xj是选取的两个城市，所谓的逆序交换方式是指:通过逆转xi、xj两个城市之间的城市次序来得到S的邻居.设：S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)则：S'=(x1,x2,…xi-1,xi,xj-1,xj-2…,xi+1,xj,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+12遗传算法达尔文进化论：“物竞天择、适者生存”70年代由美国的密执根大学的Holland教授首先提出.近年来，遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中.1)生物进化与遗传算法循环起点优胜劣汰不适应的优良的繁衍多样化生物进化与遗传算法之间的对应关系2)遗传算法的三个主要操作选择交配变异“轮盘赌”法：设群体的规模为N，F(xi)(i=1,...,N)是其中每个染色体的适应值,则第i个染色体被选中的概率由下式给出：选择模拟“轮盘赌”算法（1）r=random(0,1)，s=0，i=0；（2）如果s≥r，则转（4）；（3）s=s+p(xi)，i=i+1,转（2）（4）xi即为被选中的染色体，输出i（5）结束.交配交配发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体.例:采用二进制形式编码时，交配过程如下：a1a2...aiai+1...anb1b2...bibi+1...bna1a2...aibi+1...bnb1b2...biai+1...an交配前交配后交配位置变异变异发生在染色体的某一个基因上，当以二进制编码时，变异的基因由0变成1，或者由1变成0。染色体x=11001，变异位发生在第三位，y=11101.遗传算法（1）给定群体规模N，交配概率pc和变异概率pm，t＝0；（2）随机生成N个染色体作为初始群体；（3）对于群体中的每一个染色体xi分别计算其适应值F(xi)；（4）如果算法满足停止准则，则转（10）；（5）对群体中的每一个染色体xi计算概率；（6）依据计算得到的概率值，从群体中随机地选取N个染色体，得到种群；（7）依据交配概率pc从种群中选择染色体进行交配，其子代进入新的群体，种群中未进行交配的染色体，直接复制到新群体中；（8）依据变异概率pm从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体；（9）用新群体代替旧群体，t=t+1转（3）；（10）进化过程中适应值最大的染色体，经解码后作为最优解输出；（11）结束.3)遗传算法的特点1）遗传算法是一个随机搜索算法，适用于求解具有多参数、多变量、多目标等复杂的最优化问题.2）遗传算法对待求解问题的指标函数没有什么特殊的要求，如连续性、导数存在、单峰值假设等。甚至于不需要显式地写出指标函数.3）在经过编码以后，遗传算法几乎不需要任何与问题有关的知识，唯一需要的信息是适应值的计算。它通过选择、交配和变异等简单的操作求解复杂的问题，是一个比较通用的优化算法.4）遗传算法具有天然的并行性，适用于并行求解.收敛性定理：如果在代的进化过程中，遗传算法每次保留到目前为止的最好解，并且算法以交配和变异为其随机化操作，则对于一个全局最优化问题，当进化代数趋于无穷时，遗传算法找到最优解的概率为1.4)遗传算法的实现问题编码评价适应函数交配规则变异规则4.1编码举例：旅行商问题对于n个城市的旅行商问题，可以用一个矩阵来表示一个可行解[BADCB].如果按行展开该矩阵，则该可行解可以用一个4×4的二进制向量表示为：0100100000010010二进制表示存在的问题采用这样的表示方法，对于n城市的TSP问题，至少需要用n×n位二进制向量表示一个可行的旅行路线.一个n×n位二进制向量，所有可能的编码个数为，而一个对称的n城市旅行商问题的可行解个数为n!/2，可见,只占编码个数非常小的比例.以n＝10为例，编码个数为可行解个数的7.0×1023倍。可行解在整个状态空间中，是非常稀疏的，所以,交配和变异所产生的是大量的非可行解.4.2遗传算法的评价前面定理给出了当进化代数趋于无穷时，遗传算法找到最优解的概率为1。即保证了遗传算法的收敛性.而在实际计算时，希望随时了解遗传算法的进展情况，监视算法的变化趋势.当前最好法该方法在每一代进化过程中，记录得到的最好解，通过最好解的变化，了解算法的变化趋势.不同的算法之间，也可以通过该最好解的变化情况进行横向比较.在线比较法该方法用当前代中染色体的平均指标函数值来刻画算法的变化趋势.计算方法如下：其中T为当前代中染色体的个数.离线比较法与在线比较法相似，但是用进化过程中每代最好解的指标函数值的平均值，来评价算法的进化过程.计算方法如下：其中N是到目前为止的进化代数，f*(t)是第t代中，染色体的最好指标函数值.4.3适应函数通常，直接选取问题的指标函数作为适应函数。如,求函数f(x)的最大值，就可以直接采用f(x)为适应函数.但有些时候，函数f(x)在最大值附近的变化可能会非常小，以至于他们的适应值非常接近，很难区分出那个染色体占优。此时，便需要定义新的适应函数，且要求该适应函数与问题的指标函数具有相同的变化趋势，但变化的速度更快.-非线性加速适应函数其中f(x)是问题的指标函数，fmax是当前得到的最优指标函数值，M是一个充分大的数.-线性加速适应函数上式中的第一个方程表示变换前后的平均值不变，第二个方程表示将当前的最优值放大为平均值的M倍.4.4二进制编码的交配规则双亲双子法a1a2...aiai+1...anb1b2...bibi+1...bna1a2...aibi+1...bnb1b2...biai+1...an交配前交配后交配位置变化交配法11010011100010由于两个父染色体的前三位完全一致，因此当交配位选择在前三位时，其子染色体将与两个父染色体完全一致。变化交配法就是在随机产生交配位时，排除掉这样的交配位.多交配位法产生多个交配位进行交配,且在交配时采用交配区间交替进行的方法.例:1101001110000011000101101011交换区间不交换区间整数编码的交配规则下面以旅行商问题为例，介绍几种整数编码的交配规则.常规交配法随机选取一个交配位，子代1交配位之前的基因选自父代1交配位之间的基因，交配位之后的基因，从父代2中按顺序选取那些没有出现过的基因.例:交配位交配位 父代1：12345678子代1：12345786父代2：52173846子代2：52173468基于次序的交配法首先在父代中随机地选定一组位置,从一父代中把该组位置上的数字依次取出;然后从另一父代中把所含的这些数字都暂时去掉(空位);最后按数字取出次序将另一父代的空位填充.例如:父代1:12345678910父代2:59246110738所选位置:****父代1中取出的数字为：2、3、5、8。从父代2中找出这些数字，并去除它们，其中b表示空位置：父代2:b9b461107bb用2、3、5、8依次填入上述父代2的空位置中，得到子代1：子代1:29346110758基于位置的交配法首先随机产生一组位置。对于这些位置上的基因，子代1从父代2中直接得到，子代1的其他位置的基因，按顺序从父代1中选取那些不相重的基因。子代2也类似处理。如：父代1：123456789父代2：592461738****子代1：192465738子代2:923456187基于部分映射的交配法对于两个选定的父代染色体父代1和父代2，随机产生两个位置，两个父代在这两个位置之间的基因产生对应对，然后用这种对应对分别去替换两个父代的基因，从而产生两个子代。父代1：264381579父代2：851762439**子代1：184762539子代2：6523814793个对应对：3:78:61:24.5变异规则二进制编码中的变异整数编码中的变异二进制编码中的变异当问题以二进制编码形式表示时，随机地产生一个变异位，被选中的基因由“0”变为“1”，或者由“1”变为“0”.变异前变异后11011011101001变异位整数编码中的变异基于位置的变异随机地产生两个变异位，然后将第二个变异位上的基因移动到第一变异位之前.21364572413657变异前变异后基于次序的变异随机地产生两个变异位，然后交换这两个变异位上的基因.21364572436157变异前变异后打乱变异随机选取染色体上的一段，然后打乱在该段内的基因次序.21364572463157变异前变异后逆序交换方式可以认为是打乱变异的一个特例.仿生学的研究给人类自然科学技术的发展和进步带来了许多启示和重要贡献.群集智能（Swarmintelligence）作为一种新兴的广为研究的演化计算技术,成为计算智能中的一个研究领域.蚁群算法（antcolonyoptimization）是其中的一个研究热点,它是模仿蚂蚁群体在觅食过程中所体现出的智能行为而提出的一种搜索方法。3.蚁群算法觅食现象蚁群在觅食过程中虽然没有直接的语言交流，但却总是能够找到从食物源到蚁穴间的最短道路.觅食原理蚁群对路径信息的散播是通过一种叫信息素（pheromone）的物质来完成的.蚂蚁在觅食的过程中会在它所经过的路径上留下一定数量的信息素，某条路径上信息素的多少（浓度）与通过该路径的蚂蚁数成正比.一种自催化的信息正反馈：某一路径上信息素浓度越高，后面的蚂蚁选择该路径的概率就越大，该路径的信息素浓度增长就会越快，从而使所有蚂蚁都能够较快地选择较短的觅食路径.蚁群算法--要点(旅行商为例)利用人工蚂蚁的行走构成问题的解.状态变迁规则:蚂蚁k在自己周游的过程中，根据可行的候选路径上的信息量(启发+信息素)随机选择自己前进的方向(下一个要到达的城市).信息素的更新:蚁群在觅食过程中，一方面通过蚂蚁的行走会在路径上留下新的信息素，另一方面随着时间的推移已有的信息素会逐渐挥发，所以各条路径上的信息素会根据蚁群的行动和时间变化不断更新.核心变量:信息素浓度启发信息蚁群算法--要点(续)从城市i走向城市j的转移概率为：蚁群中的每只蚂蚁从出发城市开始，经过n次路径选择后，回到出发点(完成一次周游)后，AS算法对蚁群所经过的每条路径进行一次信息素的更新:k大于m满足结束条件NYNY完成旅行Y蚁群算法-优缺点优点:良好的鲁棒性、正反馈、及分布式并行计算等.缺点:迭代次数过多,尤其对城市数大于100的TSP问题.易陷入局部最优,精度欠佳.一些新尝试--蚁恒模型信息素的增量公式：该式能体现在一次周游中蚂蚁所消耗能量Q在各段路径上的分配，并反映了由于各段路径长度的不同，一只蚂蚁在同次周游中留在不同路径上的信息素增量各不相同的事实。而且对于蚂蚁的任何一次周游，都有即每只蚂蚁在各自周游中所产生的信息素总量为Q，服从能量守恒与转换定律.信息素增量模型的收敛性能比较蚁群算法--信息素扩散思想：在蚂蚁进行路径选择时，适当考虑相近路径上信息素的相互作用。即一只蚂蚁在某条路径上留下的信息素，一方面会直接影响连接该路径的两个城市上的其它蚂蚁选择下一个城市的行为，另一方面，它会以这两个城市为中心向外扩散，影响该城市附近的其他城市上蚂蚁的选路行为.扩散示意图简化的扩散模型（a）原算法：以城市为信源（b）以路径为信源不同算法在dantzig42上的最优解图蚁群算法--TSP问题的多粒度描述模型--多粒度TSP问题求解算法过程图解实验结果比较编程作业(任选)1.用遗传算法或蚁群算法求解旅行商问题.(http://elib.zib.de/pub/mptestdata/tsp/tsplib/tsplib.html)2.实现五子棋最佳走步程序，要求使用剪枝算法，搜索深度可以设置.作业要求:程序的运行源码的讲解等此下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！