大数据分析方法与应用 课件 第7章 启发式算法

大数据分析方法与应用上海理工大学主讲人：耿秀丽

教授第七章启发式算法7.1

启发式算法的基本原理目录CONTENTS7.2

启发式算法的类型7.3

遗传算法及其实现7.4

粒子群算法及其实现7.5物流配送中心选址案例分析第七章学习结构框架启发式算法

什么是启发式算法？启发式算法是一种通过模拟自然现象或人类的经验、知识和智慧，来寻求解决方案较优或近似最优的问题求解方法。它能够在有限时间内找到接近最优解的可行解，具有计算效率高、适应性强、鲁棒性强、可并行化等特点，并被广泛应用于组合优化、机器学习、图论等实际问题中。7.1

启发式算法的基本原理

组合优化问题人工智能领域数学优化领域数据挖掘和模式识别领域最小生成树调度和资源分配问题多目标优化问题通过引入启发式准则和寻找合适的搜索策略，可以在多个领域获得较好的解决方法。在实际问题中有着广泛的应用前景。启发式算法的原理主要分为两个方面：启发式函数和搜索策略。7.1

启发式算法基本原理

7.1.1

启发式函数启发式函数是一种评估函数，它根据特定问题的信息来评估解的质量，并指导算法搜索解空间。在搜索空间中，每个状态都有一个相应的评估值，而启发式函数本身可以根据搜索问题的特点来设计和选择。实践中，设计好的启发式函数可以在找到最优解或接近最优值的同时，有效降低搜索空间的大小，从而使算法具有更快的搜索速度。一个好的启发式函数应该满足以下条件：1）启发式函数应该准确地评估每个状态，以便在搜索空间中找到最优解或接近最优值；2）启发式函数应该能够快速计算，以便算法具有较快的搜索速度；3）启发式函数应该合理有效地指导算法搜索，以便算法能够充分利用先前找到的最优解。常用的启发式函数包括曼哈顿距离（ManhattanDistance）、欧几里得距离（EuclideanDistance）、切比雪夫距离（ChebyshevDistance）等。这些启发式函数可以用于许多优化问题，如旅行商问题、路径规划等。7.1启发式算法基本原理

7.1.2

搜索策略一、定义搜索策略作为一种指导搜索过程的规则集合，也扮演着启发式算法的重要组成部分。搜索策略是指在解空间中进行搜索，并从中选择有可能是最佳解的解。二、分类实现方式搜索顺序随机搜索深度优先搜索局部搜索广度优先搜索全局搜索遗传算法7.2

启发式算法的类型

启发式算法仿植物类算法：模拟植物的生长、繁殖和适应环境的过程仿动物类算法：模拟动物的行为、交流和适应环境的过程。0102蚁群算法鸟群算法粒子群算法蜂群算法鱼群算法蝙蝠算法向光性算法杂草优化算法模拟植物生长算法特点：具有较强的自适应性和鲁棒性。（鲁棒性：系统或算法在面对异常情况或输入变化时能够保持良好性能的能力）7.2

启发式算法的类型

7.2.1

仿动物类启发式算法——蚁群算法（AntColonyOptimization,ACO）仿动物类启发式算法利用生物进化、个体行为、群体行为等动物的特征来进行优化求解，其最主要的特点是能够考虑群体的可行性，解决发现局部最优的问题，提高搜索算法的效率。蚁群算法是基于蚂蚁的运动规律，通过模拟蚂蚁在搜索过程中沿路径释放信息素、挥发信息素等行为模式，来搜索全局最优或局部最优解。蚂蚁在移动过程中会释放信息素，信息素越高表示该路径被蚂蚁选择的概率越大，所以蚂蚁更倾向于选择信息素浓度高且长度短的路径。应用：组合优化问题、路径规划问题、调度问题，易陷入局部最优7.2

启发式算法的类型

7.2.1

仿动物类启发式算法——粒子群算法（ParticleSwarmOptimization,PSO）粒子群算法是基于鸟类在寻找食物等过程中的觅食行为而设计的，这种算法通过模拟鸟类协作寻找最优优化结果；粒子群算法的基本思想是将待优化问题转化为一个多维搜索空间中的优化问题，每个粒子代表一个可能的解，并根据自身的经验和群体的经验来更新自己的位置和速度。粒子的位置表示解的值，速度表示解的搜索方向和步长。更新速度过程包括粒子向自己历史最优位置靠近和向群体历史最优位置靠近。应用：函数优化、组合优化、参数优化、非线性优化问题7.2启发式算法的类型

7.2.1

仿动物类启发式算法——蜂群算法（BeeAlgorithm）蜂群算法是由国外学者于2005年首次提出，是一种基于蜜蜂觅食行为的启发式优化算法。蜜蜂觅食行为中包含了一系列的搜索、选择和通信过程，这些行为被模拟为算法的操作。基本思想：通过模拟蜜蜂在搜索食物源时的行为寻找问题的最优解。蜂群算法的搜索过程是一个迭代的过程，每一次迭代中，蜜蜂们根据一定的规则进行搜索，并根据搜索结果更新自己的位置和状态。具有较好的全局搜索能力和收敛性能。它可以应用于多种优化问题，如函数优化、组合优化、路径规划等。（引领蜂）7.2

启发式算法的类型

7.2.1仿动物类启发式算法——鱼群算法（FishSchoolSearch,FSS）鱼群算法是由李晓磊博士于2003年提出的，是一种基于模拟自然界鱼群食物搜索行为的启发式优化算法。该算法受到鱼群行为的启发，模拟了鱼群中鱼的个体行为和群体行为，用于解决优化问题。基本思想：通过个体之间的相互作用和信息交流，以及对环境的感知和适应，实现问题的求解。具有较强的全局搜索能力和较快的收敛速度。（一片水域，如果某个地方的鱼类数目最多，那么这个地方一般来说就是水域内富含营养物质最多的地方，依据这一特点来模仿鱼群的觅食、聚群、追尾、随机行为，以实现全局寻优的目的。）应用：各种需要寻找最优解的问题，尤其是那些复杂、高维、非线性的优化问题。优点：并行性强、全局搜索能力强、适应性强、算法简单易实现。7.2

启发式算法的类型

7.2.1

仿动物类启发式算法——蝙蝠算法（BatAlgorithm）蝙蝠算法是由英国科学家Yang教授于2010年提出的一种模拟蝙蝠群体行为的启发式优化算法。基本思想：模拟蝙蝠在寻找食物和繁殖过程中的行为。蝙蝠在夜间通过发出超声波信号来探测周围环境，并根据接收到的回声来判断目标的位置。发现目标后，它会朝着目标飞去，并通过调整频率和声音的强度来调整自己的飞行方向和速度。应用：各种优化问题，特别是连续优化问题优点：算法基本思想简单，易于理解和实现缺点：存在多个参数需要去设置，如蝙蝠个体的速度、频率等，对初始解敏感，不同的初始解可能导致不同的搜索结果7.2

启发式算法的类型

7.2.1

仿植物类启发式算法算法名称概念基本思想应用向光性算法（PhototaxisAlgorithm）用于解决优化问题的算法，也称为光子算法。该算法模拟了光在环境中的传播和反射过程，通过光的传播路径来搜索最优解通过模拟生物体对光的感知和移动来解决优化问题连续优化问题和多模态优化问题杂草优化算法（WeedOptimizationAlgorithm,WOA）一种基于仿生学的优化算法通过模拟杂草的生长过程来求解优化问题机器学习、图像处理、电力系统优化模拟植物生长算法(PlantGrowthSimulationAlgorithm,PGSA)一种以植物向光性机理（形态素浓度理论）为启发准则的智能优化算法。通过模拟植物的生理机制和生长规律来解决问题，可以应用于多种问题的求解函数优化、组合优化、图像处理（全局搜索）7.3

遗传算法及其实现

7.3.1

遗传算法的原理一、概念遗传算法（GeneticAlgorithm,GA）起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法。二、原理遗传算法通过模拟自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体，从而求得问题的优质解。三、优势在求解较为复杂的组合优化问题时，相对一些常规的优化算法，遗传算法通常能够较快地获得较好的优化结果。四、应用车间调度、机器仿真、信号处理

7.3

遗传算法及其实现

7.3.1

遗传算法的原理四、常用术语算法名称概念染色体（Chromosome）染色体又可称为基因型个体（Individuals），一定数量的个体组成了群体（Population），群体中个体的数量叫作群体大小（Populationsize）。位串（BitString）个体的表示形式，对应于遗传学中的染色体。基因（Gene）基因是染色体中的元素，用于表示个体的特征。例如有一个位串（即染色体）S=1011，则其中的1，0，1，1这4个元素分别称为基因。特征值（Feature）在用位串表示整数时，基因的特征值与二进制数的权一致，例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8适应度（Fitness）各个体对环境的适应程度叫作适应度。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数通常会被用来计算个体在群体中被使用的概率。基因型（Genotype）或称遗传型，是指基因组定义遗传特征和表现，对应于GA中的位串表现型（Phenotype）指的是生物体的基因型在特定环境下的表现特征，对应于GA中的位串解码后的参数。7.3

遗传算法及其实现

7.3.2

遗传算法的步骤初始化种群：随机生成一组初始个体，形成初始种群。评估适应度：适应度函数表明个体或解的优劣性。根据具体问题计算群体P(t)中各个个体的适应度。遗传算子：选择操作、交叉操作、变异操作、终止判断条件7.3

遗传算法及其实现

7.3.3

遗传算法的计算机实现常用软件MATLAB是一种高级的数学计算软件，它提供了丰富的工具箱和函数，可以方便地实现遗传算法。Python是一种通用的编程语言，拥有丰富的科学计算库，如NumPy、SciPy和DEAP等，可以用于实现遗传算法。Java是一种广泛使用的编程语言，它提供了强大的面向对象的编程能力，可以用于实现遗传算法。7.3

遗传算法及其实现

7.3.3

遗传算法的计算机实现——验证Python软件的实现初始化种群优胜劣汰7.3

遗传算法及其实现

7.3.3

遗传算法的计算机实现——验证Python软件的实现交配生殖、变异7.3

遗传算法及其实现

7.3.3

遗传算法的计算机实现——验证Python软件的实现生物遗传进化7.4

粒子群算法及其实现

7.4.1粒子群算法的原理一、粒子群算法的灵感来源

粒子群算法被提出的灵感来源于鸟群觅食，鸟群觅食过程中，每只鸟沿着各个方向飞行去寻找食物，每只鸟儿都能记住到目前为止自己在飞行过程中最接近食物的位置，同时每只鸟儿之间也有信息共享，它们会比较到目前为止各自与食物之间的最近距离，从各自的最近距离中，选择并记忆整体的一个最近距离位置。二、数学模型

每只鸟儿就是一个粒子，食物的位置也就是问题的最优解，鸟儿与食物的距离也即当前粒子的目标函数值。7.4

粒子群算法及其实现

7.4.2

粒子群算法的步骤对于每个粒子，它包含的元素：当前时刻位置：(x1,x2,...,xn)当前时刻的目标函数值（也称为适应度）：f(x1,x2,...,xn)该粒子的历史最优位置：(x1_pbest，x2_pbest，...，xn_pbest)该粒子的历史最优目标函数值：f_pbest=f(x1_pbest，x2_pbest，...，xn_pbest)对于全部粒子，它们共有的元素：粒子总数：num迭代总次数：cnt。粒子群算法也是一个迭代的过程，需要多次迭代才能获取到理想的最优解。全局最优位置：(x1_gbest，x2_gbest，...，xn_gbest)全局最优目标函数值：f_gbest=f(x1_gbest，x2_gbest，...，xn_gbest)位置随机化的上下限：xmin，xmax。迭代开始的时候以及迭代的过程中，均需要对粒子的位置进行随机分布，需要设置随机分布的上下限，不然随机分布偏离得太远，会严重影响优化结果。速度的上下限：Vmin，Vmax。迭代过程中，速度也具有一定的随机性，需要限制速度的大小在一定范围内，不然如果速度值太大也会严重影响优化结果。速度计算参数：c1、c2。通常取1.0~1.8的值。速度更新：Vi=w*Vi+c1*rand()*(pbesti+Xi)+c2*rand()*(gbest-Xi)位置更新：Xi=Xi+Vi7.4粒子群算法及其实现

7.4.3粒子群算法的计算机实现——验证设定PSO初始参数本节用Python软件对粒子群算法进行实现，问题描述：求y=x2-4x+3最小值。7.4粒子群算法及其实现

7.4.3粒子群算法的计算机实现——验证设定目标函数及初始化种群7.4粒子群算法及其实现

7.4.3粒子群算法的计算机实现——验证更新粒子速度和位置7.4粒子群算法及其实现

7.4.3粒子群算法的计算机实现——验证图形可视化7.5

物流配送中心案例分析

一、问题：

一共有五个配送中心候选节点，其建设成本和坐标如表7-1所示。供应点有13个，其坐标和运输量如表7-2所示，通过遗传算法分析配送中心可覆盖的供应点。配送中心候选节点建设成本（万元）坐标15495.7（58.9,45.2）23458.8（54.9,117）34226.7（114,135）47294.2（67.7,195）58560.2（176,149）供应点坐标运输量1(106,74.1)67.572(105,117)107.153(74.9,91.5)221.564(81.8,147)293.935(136,161)105.536(192,43.4)191.167(39.9,63.0)285.48续表：8(37.7,85.3)197.079(41.7,152)304.2410(12.4,100)217.8211(31.7,9.80)100.9612(32.9,189)61.4713(159,218)258.37.5

物流配送中心案例分析

二、解题思路——提出假设

1）在一定备选范围内进行配送中心的选取。2）供应点数目多于配送中心数目。3）一个供应点仅由一个配送中心提供配送服务，但一个配送中心可覆盖多个供应点。4）配送中心容量可满足各供应网点的总需求量。5）各供应点配送需求一次性运输完成，且假设匀速行驶。6）只考虑配送中心建设成本、运输成本。符号及定义：

I：表示供应点集合；

J：表示配送中心集合；

Cij：从供应点i到配送中心j的运输成本；

qij：供应点i到配送中心j的运输量；

fj：配送中心j的建设成本；

Dj：配送中心j的需求量；

P：配送中心的最大建设数量；

Mj：配送中心j的最大容量。7.5物流配送中心案例分析

二、解题思路——确定目标函数及约束条件

目标函数：

，表示总费用最小约束条件1：

，配送中心的数量为2个；约束条件2：

从供应点到配送中心的数量大于等于配送中心的需求量；约束条件3：

，配送中心容纳能力限制；约束条件4：

，

，

，变量取值。7.5

物流配送中心案例分析

二、解题思路——Python

运行

由备选中心2