人工智能第5章约束满足问题精品PPT课件

借鉴物理退火过程的随机搜索 算法，通过概率接受劣解探索
最优解。
03
CHAPTER
常见约束优化问题
线性规划问题
总结词
线性规划问题是最常见的约束优化问题之一，它通过线性不等式或等式约束来 限制决策变量的取值范围，使得目标函数达到最优解。
详细描述
线性规划问题通常用于资源分配、生产计划、运输和分配等问题，其目标函数 和约束条件都是线性函数。求解线性规划问题的方法包括单纯形法、对偶理论 和分解算法等。
约束优化问题的可解释性与鲁棒性研究
总结词
为了更好地应用约束优化问题，需要研究其可解释性 和鲁棒性，以提高模型的可靠性和稳定性。
详细描述
在许多领域中，模型的解释性和鲁棒性是非常重要的 。为了更好地应用约束优化问题，需要研究其可解释 性和鲁棒性，例如通过建立模型的可解释性框架、设 计鲁棒性强的算法等，以提高模型的可靠性和稳定性 。
拉格朗日乘数法
总结词
一种求解约束优化问题的数学方法
详细描述
通过引入拉格朗日乘数，将约束优化问题转化为无约束优化问题，然后利用无约束优化 方法求解。在每一步迭代中，根据当前点的拉格朗日函数值更新拉格朗日乘数和迭代点
，直到满足收敛条件。
拉格朗日乘数法
要点一
适用范围
适用于具有线性约束的优化问题。
要点二
执行。
时间限制
生产计划需要在规定的时间内完 成，因此时间限制也是一个重要 的约束条件。通过约束优化问题 ，可以找到在满足时间限制下的
最优生产计划。
质量限制
在生产过程中，质量是一个重要 的考量因素。通过约束优化问题 ，可以在保证质量的前提下，实
现生产计划的最优配置。
物流配送优化
时间限制

Constraint Propagation
3 4 4 3 3 3 4 5
4
3 3 5
重复前述过程
Constraint Propagation
3 3 4 3 4 3
3
2 3 4
Constraint Propagation
3 3 4 3 1
2
2 1 3
Constraint Propagation
The The The The The The The The The The The The The The
Englishman lives in the Red house i,j[1,5], Spaniard has a Dog Japanese is a Painter ... Italian drinks Tea Norwegian lives in the first house on the left owner of the Green house drinks Coffee Green house is on the right of the White house Sculptor breeds Snails Diplomat lives in the Yellow house owner of the middle house drinks Milk Norwegian lives next door to the Blue house Violinist drinks Fruit juice Fox is in the house next to the Doctor’s Horse is next to the Diplomat’s
1 2 3 4 5
Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra}

循环神经网络原理
循环神经网络（RNN）是一种具有循 环结构的神经网络，能够处理序列数据。 它通过在网络中引入循环连接，使得网 络可以记住先前的信息，并将其应用于
当前的任务。
RNN的基本结构包括输入层、隐藏层 和输出层。隐藏层的状态会在每个时间 步长中更新，从而捕捉序列中的动态信
息。
RNN的训练过程采用反向传播算法 （BPTT），通过计算损失函数对模型 参数的梯度来更新模型参数，以最小化
通过不断地试错和学习，使得智能体能够找到一 种最优的行为策略，以最大化获得的累计奖励。
马尔可夫决策过程
马尔可夫决策过程的定义
马尔可夫决策过程（Markov Decision Process，MDP）是一种 用于描述强化学习问题的数学模型，具有马尔可夫性质。
马尔可夫决策过程的组成
包括状态集合、动作集合、转移概率、奖励函数和折扣因子等。
Q-Learning算法的应用
可用于解决各种离散状态和动作空间的强化 学习问题，如迷宫寻路、倒立摆控制等。
Policy Gradient算法
Policy Gradient算法的原理
Policy Gradient是一种基于策略迭代的强化学习算法，通过梯度上升法来优化策略参数，使得期 望回报最大化。
Policy Gradient算法的流程
人工智能课件第5章
目录
• 深度学习基础 • 卷积神经网络 • 循环神经网络 • 生成对抗网络 • 强化学习基础 • 人工智能伦理与安全性问题
01 深度学习基础
神经网络概述
神经网络的定义
神经网络的工作原理
一种模拟人脑神经元连接方式的计算 模型，通过多层神经元的组合和连接 实现复杂的功能。
通过前向传播计算输出结果，再根据 误差反向传播调整权重，不断迭代优 化网络参数。

学习的定义
对于某类任务T和性能度量P，如果一个计算机程 序在T上以P衡量的性能随着经验E而自我完善，那 么我们称这个计算机程序在从经验E中学习
11
学习问题的标准描述
西洋跳棋学习问题
任务T：下西洋跳棋 性能标准P：比赛中击败对手的百分比 训练经验E：和自己进行对弈
手写识别学习问题
任务T：识别和分类图像中的手写文字 性能标准P：分类的正确率 训练经验E：已知分类的手写文字数据库
Humidity Normal
High High High
Wind Strong Strong Strong Strong
Water Warm Warm Warm Cool
Forecast Same Same Change Change
EnjoySport Yes Yes No Yes
29
概念学习任务
< , , , , , >
// 所有的样例都是反例
30
概念学习任务
形式化描述 已知 实例集X ▪ 每个实例x由6个属性描述，每个属性的取值范围已确定 假设集H ▪ 每个假设h描述为6个属性的取值约束的合取 （∩） 目标概念c ▪ 一个布尔函数，变量为实例，即： c:x->{1,0} 训练样例集D ▪ 目标函数（或目标概念）的正例和反例 求解 H中的一假设h，使对于X中任意x，h(x)=c(x)
问题产生器
以当前的假设作为输入，输出一个新的问题，供执行系统去 探索。
23
小结：设计一个学习系统
基本设计方法和步骤
Step1: 明确任务T、性能度量P Step2: 训练经验E Step3: 选择目标函数及其表示 Step4: 选择目标函数的学习算法 Step5: 最终设计

理论研究和应用研究也有了新的突破，机器学习的研究进入了全 面的、系统化的时期。
主要成果有：
一方面传统的符号学习的各种方法已日臻完善。Michalski等 将AQ11扩充为一个多功能学习系统AQ15，ID3算法中使用了熵，从 而使决策树归纳得到了很大的改进。
科学发现系统BACON开辟了无导师学习的两个重要研究领域。
神经网络学习在消沉了一段时期后又重新蓬勃发展起来了，同时 计算机硬件技术的高速发展也为开展大规模和高性能的人工神经 网络提供了保障，使得基于神经网络的连接学习从低谷走出，发 展迅猛。其中Rumelhart等人提出的BP模型，提供了一个训练多层 网络的实际可行的方法，克服了Perceptron的大部分局限性。
史忠植 人工智能： 机器学习
13
归纳学习
• 归纳学习的分类和研究领域：
–符号学习
• 监督学习： –实例学习：系统事先将训练例子（经验数据）分类：正 、负例子。由于它产生规则，所以也称为概念学习
• 无监督学习：事先不知道训练例子的分类 –概念聚类： –机器发现
• 神经网络：本质上是实例学习，为区别起见，称为联结学习
2020/12/18
史忠植 人工智能： 机器学习
7
机器学习发展阶段
七十年代的发展阶段：
由于当时专家系统的蓬勃发展，知识获取成为当务之 急，这给机器学习带来了契机，主要侧重于符号学习 的研究。机器学习的研究脱离了基于统计的以优化理 论为基础的研究方法，提出了基于符号运算为基础的 机器学习方法，并产生了许多相关的学习系统，
–环境提供给学习环境的例子是低水平的信息，这是 在特殊情况下执行环节的行为。学习环节归纳出的 规则是高水平的信息，可以在一般情况下用这些规 则指导执行环节的工作

Example: Map-Coloring
变量 WA, NT, Q, NSW, V, SA, T 值域 Di = {red,green,blue} 约束: adjacent regions must have different colors
e.g., WA ≠ NT, or (if the language allows this), or (WA,NT) ∈ {(red,green),(red,blue),(green,red), (green,blue), … }
第五章 约束满足问题
Review: Last Chapter
• Best-first search Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy best-first search expands lowest h — incomplete and not always optimal A* search expands lowest g+ h — complete and optimal — also optimally efficient (up to tie-breaks, for forward search) Admissible heuristics can be derived from exact solution of relaxed problems
CSP的种类
离散变量 • finite domains 有限值域:
n 个变量, 值域大小d → O(dn) 完全赋值 e.g., Boolean CSPs/布尔CSP问题(NP-complete) • infinite domains 无限值域 (integers, strings, etc.) e.g., job scheduling, variables are start/end days for each job 不能通过枚举来描述值域，只能用约束语言 , e.g., 线性约束可解, 非线性约束不可解

例如八皇后问题，如果不计算皇后的初始状 态，算法的运行时间大体上独立于问题的大 小。
局部搜索算法的另一个优势是当问题改 变时可用于联机设置
在调度问题中尤其重要
第五章、约束满足问题
约束满足问题（CSP） CSP问题的回溯搜索 约束满足问题的局部搜索 问题的结构
问题的结构：利用来找到问题 的解
对于满足S所有约束条件的S中变量的每 个可能的赋值，
从剩余变量的值域中删除与S的赋值不相容 的值，并且
如果去掉S后的剩余CSP有解，把解和S的赋 值一起返回。
算法的时间复杂度
如果环割集的大小为c，那么总的运行时 间为O(dc(n-c)d2)。
寻找最小环割集是个NP难题
基于合并节点
把约束图分解为相关联的子问题集 独立求解每个子问题 合并结果
约束满足问题
CSP由一个变量集合和一个约束集合组成 问题的一个状态是由对一些或全部变量
的一个赋值定义的
完全赋值：每个变量都参与的赋值
问题的解是满足所有约束的完全赋值， 或更进一步，使目标函数最大化。
例子：澳大利亚地图的染色
对每个区域染上红、绿或蓝色，使得没有相 邻的区域颜色相同。
将问题形式化为CSP
弧相容算法AC-3的 时间复杂度是 O(n2d3)。
推广到k相容
弧相容算法AC-3
k相容
如果对于任何k－1个变量的相容赋值， 第k个变量总能被赋予一个与前k－1个变 量相容的值，那么该CSP问题是k相容的。弧相 Nhomakorabea＝2相容
处理特殊约束：应用专门算法
删除约束中只有单值值域的变量，然后 将这些变量的取值从其余变量的值域中 删去（重复该过程）。
提前发现失败
HW
5.2,5.6

Street Puzzle
1 2 3 4 5
Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra}
约束的清晰表示 约束传播算法
约束满足问题 (CSP) Constraint Satisfaction Problem (CSP)
变量的集合 variables {X1, X2, …, Xn} 每一个变量Xi所有可能的取值，构成该变量 的值域Di；通常Di是有限的 约束的集合 constraints {C1, C2, …, Cp} 每个约束描述了一个变量子集与特定的某些 值合法的结合对应关系 目标: 每一个变量都得到了一个赋值，且所有 的约束得到满足
地图着色问题
NT
WA SA Q NSW T
V
7 个变量 {WA,NT,SA,Q,NSW,V,T} 每个变量的值域是一样的: {red, green, blue} 两个相邻的变量不能取相同的值:
WANT, WASA, NTSA, NTQ, SAQ, SANSW, SAV,QNSW, NSWV
owns the Zebra? drinks Water?
Street Puzzle
1 2 3 4 5
Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra}

❖ 解：该状态空间上的某个具有一致性和完备性的赋值。
❖ 一致性赋值：不违反任何约束的合法赋值。
❖ 完备性赋值：每个变量都被赋值，并且该赋值是一致的、完整的。
人工智能原理
15
约束满足问题
形式化
约束满足问题的值域
值域
离散
连续
有限
地图着色问题（Map coloring problem）
无
无限
整数或字符串集合（Set of integers or strings）
约束满足问题的实例化
约束传播
回溯搜索
局部搜索
问题的改进
13
约束满足问题
约束满足问题（Constraint Satisfaction Problems, CSPs）
一个约束满足问题可看作是一个可能世界中的一组对象（objects），其状态必须满足一些约
束。它将一个可能世界表征为一个对变量进行有限约束的同构集合，采用约束满足方法进行求
无
约束满足问题的约束
约束
一元约束
二元约束
n元约束
线性
, ≠ 3
1 , 2 , 1 ≠ 2
(1 , 2 , … , ), ∀≠ (1 , 2 , … , )
非线性
人工智能原理
算法不存在
16
约束满足问题
状态的表示
状态表示：约束满足问题 vs 经典搜索问题
❖ 经典搜索问题的状态：
局部搜索（local search）
人工智能原理
18
第6章 约束问题求解
目录








人工智能原理
约束问题
可能世界及其约束
约束满足问题

没有绝对的学习方法。许多系统体现 出上述途径的组合。
机器学习 — 概述
机器学习进入新阶段的重要表现： （近十年）
机器学习已成为新的边缘科学并在 高校形成一门课程。它综合应用心理 学、生物学和神经生理学以及数学、 自动化和计算机科学形成机器学习理 论基础。
机器学习 — 概述
机器学习进入新阶段的重要表现： （近十年）
环境提供给学习环节的正例和反例是低水平的信息， 这是特殊情况下执行环节的行为。学习环节归纳出 的规则是高水平的信息，可以在一般情况下用这些 规则指导执行环节的工作。
实例学习
实例学习的两个空间模型
选择例子
例子 空间
规则 空间解释Leabharlann 子实例学习 － 两个空间模型
描述
例子空间的描述语言可以描述所有例子；规则空间的可以描 述所有规则。 例如：纸牌， 同花5张
机器学习 — 概述
机器学习进入新阶段的重要表现： （近十年）
各种学习方法的应用范围不断扩大，一部分 已形成商品。归纳学习的知识获取工具已在 诊断分类性专家系统中广泛应用。连接学习 在声图文识别中占优势。分析学习用于设计 综合性专家系统。遗传算法与强化学习在工 程控制中有较好的应用前景。与符号系统耦 合的神经网络连接学习将在企业的智能管理 与智能机器人运动规划中发挥作用。
机器学习 — 概述
为什么要研究机器学习？
………..
未来的计算机将有自动获取知识的能 力，它们直接由书本学习，通过与人 谈话学习，通过观察学习。它们通过 实践自我完善，克服人的存储少、效 率低、注意力分散、难以传送所获取 得知识等局限性。一台计算机获取的 知识很容易复制给任何其它机器。
机器学习 — 概述
4、All that you do, do with your might; things done by halves are never done right. ----R.H. Stoddard, American poet做一切事都应尽力而为，半途而废永远不行6.17.20216.17.202110:5110:5110:51:1910:51:19

3
加强与其他领域的合作与交流，有助于推动约束 推理的跨学科发展。
06
CATALOGUE
总结与展望
约束推理的重要性和意义
约束推理是一种重要的推理方法，在人工智能 、自然语言处理、数据挖掘等领域具有广泛的 应用。
约束推理有助于解决复杂的问题，提高推理效 率和精度，为人工智能技术的发展提供了有力 支持。
约束推理在智能控制、智能诊断、智能规划等 领域也具有广泛的应用前景，能够为各行业提 供智能化解决方案。
目前研究的不足与未来发展方向
目前约束推理的研究还存在一些不足之处，如算法的 效率、可解释性等方面仍有待提高。
未来研究需要进一步探索约束推理的原理和机制，加 强算法的优化和改进，提高约束推理的应用效果和智
01
随着问题规模的扩大，求解大规模约束满足问题成为一项挑战 。
02
分布式计算、云计算等技术为大规模问题的求解提供了新的解
决方案。
优化算法、启发式搜索等策略在求解大规模问题中具有重要应
03
用价值。
约束推理在其他领域的应用拓展
1
约束推理在生产调度、物流优化等领域具有广泛 的应用前景。
2
拓展约束推理在其他领域的应用，需要深入了解 相关领域的具体问题和需求。
束条件下，寻找满足所有约束条件的解的问题。
02常Biblioteka 的约束满足问题包括排课表、工作分配、旅行商
问题等。
03
约束满足问题求解算法包括局部搜索、分支定界、遗
传算法等，旨在寻找满足所有约束条件的解。
启发式搜索算法
01
启发式搜索算法是一种基于启 发式信息的搜索算法，通过评 估解的质量来指导搜索方向， 以减少搜索空间。
能化水平。