避免碰撞 速度匹配 中心聚集
AHNU
鸟群觅食模型
Food
Global Best Solution
Past Best Solution
AHNU
谢谢大家
Q/A
有关，缺乏规
AHNU
可应用那些问题
可应用那些问题 NP问题 ………不存在多项式算法的问题,典型问题如背包问题,周游问题,选址 问题等 某些高阶多项式算法问题 ……….如对应算法时间复杂度超过4阶以上,此时利用普通算法在有效 时间内可能不能得到结果 那些问题不适合使用 ……..求解为精确解 …….不是优化模型问题 ……..有低阶多项式算法
AHNU
其它生物启发式计算技术
进化规划算法
进化编程 人工免疫系统
DNA计算
膜计算等
AHNU
群体智能（Swarm Intelligence）
生物学家研究表明：在这些群居生物中虽然每个个体 的智能不高，行为简单，也不存在集中的指挥，但由 这些单个个体组成的群体，似乎在某种内在规律的作 用下，却表现出异常复杂而有序的群体行为。
AHNU
5、动态规划、回溯搜索、分治算法、分支定界等计算机 算法（这些算法是算法设计中比较常用的方法，很多场 合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经 网络、遗传算法（这些问题是用来解决一些较困难的最 优化问题的算法，对于有些问题非常有帮助，但是算法 的实现比较困难，需慎重使用） 7、数值分析算法（如果在比赛中采用高级语言进行编程 的话，那一些数值分析中常用的算法比如方程组求解、 矩阵运算、函数积分等算法就需要额外编写库函数进行 调用） 8、一些连续离散化方法（很多问题都是实际来的，数据 可以是连续的，而计算机只认的是离散的数据，因此将 其离散化后进行差分代替微分、求和代替积分等思想是 非常重要的）
AHNU
现代优化算法简介
安徽师范大学数学计算机科学学院
AHNU
优化问题概述
实际生活中的优化问题 最优化问题模型
min f ( x)
s.t gi ( x) 0 hi ( x) 0 或 >0
x S RD
全局最优与局部最优
AHNU
组合优化问题优化模型
组合优化（combinatorial optimization）:解决离散问题的优 化问题——运筹学分支。通过数学方法的研究去寻找离散事件的 最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、 工业工程、交通运输和通信网络等许多方面。 数学模型：
+
+ = + =
AHNU
神经计算
细胞体 轴突 突触 树突
人工神经网络是由 具有 适应性的简单单元组成的 广泛并行互连的网络，它 的组织能够模拟生物神经 系统对真实世界物体所作 出的交互反应。
电脉冲
输 入
树 突
细胞体 信息处理
形成
轴突 传输
突 触
输 出
图 12.2 生物神经元功能模型
AHNU
神经计算
AHNU
当前进化算法新进展
多目标优化 动态环境下优化 大规模超大规模优化 不确定环境下优化 ………………………………..
AHNU
生物启发式优化方法
生物启发式计算是指以生物界的各种自然现象或过程 为灵感，而提出的一系列启发式智能计算方法。
遗传算法 神经网络 模糊逻辑
。。。。。
AHNU
遗传算法
AHNU
经典的计算方法
17世纪Newtown 微积分 1847年 Cauchy 最速下降法 1939年 Kantorovich下料问题和运输问题 问题求解 1947年 Dantzig 单纯形方法
AHNU 传统运筹学面临新挑战
现代问题的特点 离散性问题——主要以组合优化（针对离散问题，定义见后）理论 为基础 不确定性问题——随机性数学模型 半结构或非结构化的问题——计算机模拟、决 策支持系统 大规模问题——并行计算、大型分解理论、近似理论 现代优化方法 追求满意——近似解 实用性强——解决实际问题 现代优化算法的评价方法 算法复杂性
达到最大循环次数
输出最短路径及其长度
结束
AHNU
鱼群觅食模型
生物社会学家E.O.Wilson指出：“至少从理论上，在搜索食 物过程中群体中个体成员可以得益于所有其他成员的发现 和先前的经历。当食物源不可预测地零星分布时，这种协 作带来的优势是决定性的，远大于对食物的竞争带来的劣 势。”
AHNU
鸟群的飞行行为
min f ( x) s.t.g ( x) 0, x D.
目标函数 约束函数 有限点集, 决策变量
AHNU
组合优化问题
组合优化问题的三参数表示：
( D, F , f ) D : 决策变量定义域 F x | x D, g ( x) 0, 可行域, 有限点集 f :目标函数 x F : 可行解（点） x : 最优解，如果 x F , f ( x ) min f ( x) | x F .
生物进化过程是一个自然， 并行，稳健的优化过程，这 一优化过程的目的在于使生 命体达到适应环境的最佳结 构与效果，而生物种群通过” “优胜劣汰”及遗传变异来 达到进化（优化）目的的。
进化过程 优化过程
AHNU
遗传算法
生物的进化机制
自然选择 适应环境的个体具有更 高的生存能力，同时染 色体特征被保留下来 杂交 随机组合来自父代的染 色体上的遗传物质，产 生不同于它们父代的染 色体 突变 随机改变父代的染色体 基因结构，产生新染色 体
ij (t n) ij (t ) ij (t, t n)
ij = 1/dij
对每只蚂蚁按概率移到下一顶点
更新每个蚂蚁的个体禁忌表

信息量更新
表示轨迹的相对重要性
ij
表示能见度的相对重要性 轨迹的持久性
表示第K只蚂蚁在本次循环中留在路径ij上的信息量
AHNU
A C
ij (t )] [ij] if j allowed jallowed [ ij (t )] [ij ] k pij (t ) otherwise 0

初始化
N c N c +1
轨迹更新: Visibility:
AHNU
模糊逻辑
x 是 A1
规则1
y 是 B1 y 是 B2
x
x 是 A2 x
是 Ar
规则2
集 结 器
去 模 糊 化
y
规则r
y 是 Br
模糊推理系统是建立在模糊集合理论、模糊if-then规则和模 糊推理等概念基础上的先进的计算框架。 模糊推理系统的基本结构由三个重要部件组成：一个规则库， 包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶 属度函数（Membership Functions, MF）；以及一个推理机制， 按照规则和所给事实执行推理过程求得合理的输出或结论 。
AHNU
9、网格算法和穷举法（网格算法和穷举法都是暴力搜索 最优点的算法，在很多竞赛题中有应用，当重点讨论模 型本身而轻视算法的时候，可以使用这种暴力方案，最 好使用一些高级语言作为编程工具） 10、图象处理算法（赛题中有一类问题与图形有关，即 使与图形无关，论文中也应该要不乏图片的，这些图形 如何展示以及如何处理就是需要解决的问题，通常使用 Matlab进行处理）
AHNU
启发式算法_优点
优点： （1）有可能比简化数学模型解的误差小； （2）对有些难题，计算时间可接受； （3）可用于某些最优化算法（如分支定界算 法）之中的估界； （4）直观易行； （5）速度较快； （6）程序简单，易修改。
AHNU
启发式算法_不足
不足： （1）不能保证求得全局最优解； （2）解的精度不稳定，有时好有时坏； （3）算法设计与问题、设计者经验、技术 律性； （4）不同算法之间难以比较。
AHNU
计算机上的常用算法：
1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机 仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型 的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会 遇到大量的数据需要处理，而处理数据的关键就在于这些算法， 通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以 用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流 二分图等算法，涉及到图论的问题可以用这些方法解决，需要认 真准备）
AHNU
启发式计算方法
【定义1-1】 启发式算法是一种基于直观或经验构造的算 法，在可接受的耗费（指计算时间、占用空间等）下给出待 解决优化问题每一实例的一个可行解，该可行解与最优解的 偏离程度未必可事先估计。 【定义1-2】 启发式算法是一种技术，该技术使得能在可 接受的计算费用内去寻找尽可能好的解，但不一定能保证所 得解的可行性和最优性，甚至在多数情况下，无法描述所得 解与最优解的近似程度。 经典的启发式方法基本原理:根据问题的部分已知信息来启发式 地探索该问题的解决方案，在探索解决方案的过程中将发现的 有关信息记录下来，不断积累和分析，并根据越来越丰富的已 知信息来指导下一步的动作并修正以前的步骤，从而获得在整 体上较好的解决方案。
I1
I2
w 1
w2 w3 w4
IN
x
w
j 1
N
j
Ij
x>T？
S
I3
人工神经网络（Artificial Neural Networks, ANN），一种模范动 物神经网络行为特征，进行分布式并行信息处理的算法数学模型。 这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连 接的关系，从而达到处理信息的目的。人工神经网络具有自学习和 自适应的能力。