第6章1讲概率算法介绍

第六章概率算法每节一经典走好运，造机遇----随机算法第1讲概率法§1.1引言故事：想象自己是神化故事的主人公,你有一张不易懂的地图,上面描述了一处宝藏的藏宝地点.经分析你能确定最有可能的两个地点是藏宝的地点,但二者相距甚远.假设：你到达其中一处,就立即知道该处是否为藏宝地点（一看便知）.从其中一处到另一处的距离是5天的行程.进一步假设有一条恶龙,每晚光顾宝藏并从中拿走一部分财宝（d）。假设你取宝藏的方案有两种：第1讲概率法§1.1引言5天5天5天??

藏宝地点藏宝地点走哪边最容易找到宝藏？第1讲概率法§1.1引言方案1

花4天的时间计算出准确的藏宝地点,然后出发寻宝,一旦出发，不能返回。方案2

有一个小精灵告诉你地图的秘密,但你必须付给他报酬,相当于恶龙3晚上拿走的财宝。若忽略可能的冒险和出发寻宝的代价,你是否接受小精灵的帮助？显然,应该接受小精灵的帮助,因为你只需给出3晚上被盗窃的财宝量(3d),否则你将失去4晚被盗财宝量(4d)。方案3:但是,若冒险,你可能做得更好！问题理解第1讲概率法§1.1引言设x是你决定之前当日的宝藏价值，设y是恶龙每晚盗走的宝藏价值，并设x>9y

方案1：4天计算确定地址，行程5天，你得到的宝藏价值为：x-9y

方案2：3y付给小精灵，行程5天失去5y，你得到的宝藏价值为：x-8y

方案3：投硬币决定先到一处，失败后到另一处(冒险方案)

一次成功所得：x-5y，机会1/2

二次成功所得：x-5y-5y=x-10y，机会1/2}期望赢利:x-7.5y数学模型平均（期望）赢利=(x-5y)*(1/2)+(x-10y)*(1/2)=x-7.5y第1讲概率法§1.1引言该故事告诉我们：当一个算法面临某种选择时,有时随机选择比花费更多时间（耗时）做最优选择更好,尤其是当最优选择所花的时间大于随机选择的平均时间的时侯。第1讲概率法概率算法是指选择下一步执行步骤时，用随机（概率）方法进行选择，而不是用逻辑上确定的方法进行选择.§概率算法定义允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。

p1p2p3p4p5第1讲概率法随机决策不可再现性

在同一实例上执行两次其结果可能不同;在同一实例上执行两次的时间亦可能不太相同。分析困难要求有概率论，统计学和数论的知识。§概率算法的特点第1讲概率法§概率算法的分类数值概率算法（Numerical）蒙特卡罗算法（MonteCarlo)拉斯维加斯算法（LasVegas）舍伍德算法（Sherwood）很多人将所有概率算法(尤其是数值概率算法)称为MonteCarlo算法第1讲概率法

数值概率算法数值算法常用于数值问题的求解.最早用于求数值问题的近似解。

特点:概率算法获得的答案一般是近似的,但通常算法执行的时间越长,精度就越高,误差就越小.使用的理由：

精确解存在但无法在可行的时间内求得。

有时答案是以置信区间的形式给出的。经典实例

投币法计算π值

计算定积分

解非线性方程组第1讲概率法

MonteCarlo算法(MC算法)蒙特卡洛算法，1945年由J.VonNeumann进行核武模拟提出的.它是以概率和统计的理论与方法为基础的一种数值计算方法,它是双重近似:一是用概率模型模拟近似的数值计算,二是用伪随机数模拟真正的随机变量的样本.这里我们指的MC算法是:若问题只有1个正确的解,而无近似解的可能时，使用MC算法。例如,判定问题只有真或假两种可能性,没有近似解,如因式分解,我们不能说某数几乎是一个因子。第1讲概率法

特点:MC算法总是能给出一个答案,但该答案未必正确,成功(即答案是正确的)的概率正比于算法执行的时间。一般不能有效地确定算法的答案是否正确。

经典实例:

主元素问题

素数测试

MonteCarlo算法(MC算法)第1讲概率法

LasVegas算法(LV算法)LV算法绝不返回错误的答案。特点：获得的答案必定正确,但有时找不到答案，和MC算法一样,成功的概率亦随算法执行时间增加而增加.无论输入何种实例,只要算法在该实例上运行足够的次数,则算法失败的概率就任意小。

经典实例:

n后问题

整数因子分解

模p平方根第1讲概率法Sherwood算法总是给出正确的答案。当某些确定算法解决一个特殊问题的平均时间比最坏情况下所需时间快得多时,我们可以使用

Sherwood算法来减少甚至是消除“好的”和”坏的”

实例之间的差别。

Sherwood算法

经典实例:

线性时间选择算法

跳跃表

随机的预处理第1讲概率法智能优化算法

模拟自然过程“优胜略劣汰”的算法一般称之为智能算法。例如，根据动植物繁衍过程原理、物理或化学现象原理等设计的解决困难计算问题的算法，都可以称为智能优化算法。例如：

模拟退火算法

遗传算法

神经网络算法

蚁群优化算法

粒子群优化算法

鱼群算法……第1讲概率法计算智能智能计算演化计算仿生计算进化计算……现代计算新方向：（以下含义基本相同）第1讲概率法模拟退火算法物理学中，通过对固体退火过程的研究知道：高温状态下的物质降温时其内能随之下降；如果降温过程充分缓慢，则在降温过程中物质体系始终处于平衡状态；当降到某一低温时，其内能可能达到最小；称这种降温过程为退火过程，模拟退火过程的寻优方法称为模拟退火算法（simulatedannealing,SA）.Metropolis1953年提出。第1讲概率法遗传算法遗传算法是模拟生物进化过程的智能优化算法，由J.H.Holland60年代提出。关键思想是：1）对问题的解用染色体编码表示（0，1编码）；2）染色体结合时，双亲的遗传基因的结合使子女具有双亲特征；3）染色体结合时，随机的变异造成子女与双亲的不同。4）算子：选择，交叉，变异例如：解编码：双亲—交叉(后三位)—子女10011101111111111011

第1讲概率法神经网络算法根据人脑组织结构和运行机制，40年代心理学家McCulloch和数学家Pitts提出了人工神经网络的数学模型。神经网络由大量神经元互连而成，具有高速信息处理能力。例如：特点：分布并行第1讲概率法神经网络算法根据人脑组织结构和运行机制，40年代心理学家McCulloch和数学家Pitts提出了人工神经网络的数学模型。神经网络由大量神经元互连而成，具有高速信息处理能力。例如：特点：分布并行第1讲概率法粒子群优化算法粒子群优化算法(PSO)是一种进化计算技术(evolutionarycomputation)，由Eberhart博士和kennedy博士发明（1995）。源于对鸟群捕食的行为研究.PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)操作（需要选择操作）。而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。第1讲概率法粒子群优化算法“人工生命”研究具有某些生命基本特征的人工系统.人工生命研究包括两方面的内容：如何利用计算技术研究生命现象；如何利用生物技术研究计算问题。计算机人关注的是第二部分的内容.现在已经有很多源于生物现象的计算技术.例如,人工神经网络是简化的大脑模型.遗传算法是模拟基因进化过程的。第1讲概率法粒子群优化算法蚁群算法第1讲概率法粒子群优化算法蚁群算法第1讲概率法粒子群优化算法雁群算法第1讲概率法鱼群算法第1讲概率法粒子群优化算法群体智能：另一种生物系统-社会系统.它是由简单个体组成的群落与环境以及个体之间的互动行为.也可称为“群智能”(swarmintelligence).这些模拟系统利用局部信息从而可能产生不可预测的群体行为。在计算智能(computationalintelligence)领域目前有两种行之有效的群智能算法：蚁群优化算法(antcolonyoptimization,ACO)

:对蚂蚁群落食物采集过程的模拟.已经成功运用在很多离散优化问题上.

粒子群优化算法(particleswarmoptimization，PSO)：对简单社会系统的模拟.最初设想是模拟鸟群觅食的过程.但后来发现PSO是一种很好的优化工具。

第1讲概率法粒子群优化算法粒子群优化算法实例：设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是它们各自知道自己当前的位置离食物还有多远(可能通过嗅觉判断)。那么找到食物的最优策略是什么呢？最简单有效的办法就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。第1讲概率法粒子群优化算法粒子群优化算法实例：PSO初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分粒子的邻居，那么在所有邻居中的极值就是局部极值。第1讲概率法粒子群优化算法粒子群优化算法研究现状：粒子群优化算法的研究还处于初期阶段,还有很多未知的领域需要