算法问题与Julia编程基础

# 算法问题与Julia编程基础 ## 1. 婴儿护理与机器替换问题 ### 1.1 婴儿护理问题 在婴儿护理问题中，不同的照顾方式会带来不同的结果。喂养（feed）总是能让饥饿的婴儿吃饱；忽略（ignore）婴儿可能会使原本吃饱的婴儿变饿，且会让饥饿的婴儿依旧饥饿；唱歌（sing）给婴儿听是一种收集信息的行为，其状态转移动态与忽略类似，但在婴儿吃饱（不饿）时不会引发哭闹，而在婴儿饥饿时哭闹的可能性会增加。 状态转移动态如下： - \(T(\text{sated} | \text{hungry}, \text{feed}) = 100\%\) - \(T(\text{hungry} | \text{hungry}, \text{sing}) = 100\%\) - \(T(\text{hungry} | \text{hungry}, \text{ignore}) = 100\%\) - \(T(\text{sated} | \text{sated}, \text{feed}) = 100\%\) - \(T(\text{hungry} | \text{sated}, \text{sing}) = 10\%\) - \(T(\text{hungry} | \text{sated}, \text{ignore}) = 10\%\) 观察动态如下： - \(O(\text{cry} | \text{feed}, \text{hungry}) = 80\%\) - \(O(\text{cry} | \text{sing}, \text{hungry}) = 90\%\) - \(O(\text{cry} | \text{ignore}, \text{hungry}) = 80\%\) - \(O(\text{cry} | \text{feed}, \text{sated}) = 10\%\) - \(O(\text{cry} | \text{sing}, \text{sated}) = 0\%\) - \(O(\text{cry} | \text{ignore}, \text{sated}) = 10\%\) 奖励函数方面，如果婴儿饥饿，无论采取何种行动，都会给予 -10 的奖励。喂养婴儿会额外增加 -5 的奖励，而唱歌会增加 -0.5 的奖励。作为婴儿照顾者，我们寻求折扣因子 \(\gamma = 0.9\) 的最优无限期策略。 ### 1.2 机器替换问题 机器替换问题是一个离散的部分可观测马尔可夫决策过程（POMDP）。机器正常工作时会为我们生产产品，但随着时间推移，机器的两个主要组件可能会单独或一起损坏，导致生产出有缺陷的产品。 问题的状态 \(S = \{0, 1, 2\}\) 对应机器内部故障组件的数量。在每个生产周期之前，有四种可用的行动： 1. **制造（manufacture）**：制造产品但不检查产品。 2. **检查（examine）**：制造产品并检查产品。 3. **中断（interrupt）**：中断生产，检查并更换故障组件。 4. **替换（replace）**：中断生产后更换两个组件。 当检查产品时，我们可以观察到产品是否有缺陷，而其他行动只能观察到无缺陷的产品。 组件在每个生产周期内独立地有 10% 的概率损坏，每个故障组件会使产品出现缺陷的概率增加 50%。无缺陷的产品获得 1 个奖励，有缺陷的产品获得 0 个奖励。制造行动没有惩罚；检查产品的成本为 0.25；中断生产线检查机器的成本为 0.5，且每有一个损坏的组件会额外产生 1 的成本；直接更换两个组件总是产生 2 的成本，但没有检查成本。 以下是该问题的转移、观察和奖励函数表： | 行动 | \(T(s' | s, a)\) | \(O(o | a, s')\) | \(R(s, a)\) | | --- | --- | --- | --- | | 制造 | \(\begin{bmatrix}0.81 & 0.18 & 0.01 \\ 0 & 0.9 & 0.1 \\ 0 & 0 & 1\end{bmatrix}\) | \(\begin{bmatrix}1 & 0 \\ 1 & 0 \\ 1 & 0\end{bmatrix}\) | \(\begin{bmatrix}0.9025 \\ 0.475 \\ 0.25\end{bmatrix}\) | | 检查 | \(\begin{bmatrix}0.81 & 0.18 & 0.01 \\ 0 & 0.9 & 0.1 \\ 0 & 0 & 1\end{bmatrix}\) | \(\begin{bmatrix}1 & 0 \\ 0.5 & 0.5 \\ 0.25 & 0.75\end{bmatrix}\) | \(\begin{bmatrix}0.6525 \\ 0.225 \\ 0\end{bmatrix}\) | | 中断 | \(\begin{bmatrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0\end{bmatrix}\) | \(\begin{bmatrix}1 & 0 \\ 1 & 0 \\ 1 & 0\end{bmatrix}\) | \(\begin{bmatrix}-0.5 \\ -1.5 \\ -2.5\end{bmatrix}\) | | 替换 | \(\begin{bmatrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0\end{bmatrix}\) | \(\begin{bmatrix}1 & 0 \\ 1 & 0 \\ 1 & 0\end{bmatrix}\) | \(\begin{bmatrix}-2 \\ -2 \\ -2\end{bmatrix}\) | ## 2. 博弈问题 ### 2.1 接球问题 在接球问题中，Johnny 想成功接住父亲的投掷，并且更喜欢接住远距离的投掷。他不确定投掷距离和成功接球概率之间的关系，但知道无论他是投掷还是接球，成功接球的概率是相同的。他有有限的接球尝试次数，目的是在回家前最大化预期效用。 Johnny 用以下公式模拟成功接住距离为 \(d\) 的球的概率： \(P(\text{catch} | d) = 1 - \frac{1}{1 + \exp(-\frac{d - s}{15})}\) 其中，熟练度 \(s\) 未知且不随时间变化。为了便于处理，他假设 \(s\) 属于离散集合 \(S = \{20, 40, 60, 80\}\)。成功接球的奖励等于投掷距离，若接球失败，奖励为 0。Johnny 从对 \(S\) 的均匀分布开始，每次投掷时从离散集合 \(A = \{10, 20, \ldots, 100\}\) 中选择一个距离。 ### 2.2 囚徒困境 囚徒困境是博弈论中的经典问题，涉及两个有冲突目标的参与者。有两个囚犯正在受审，他们可以选择合作（保持沉默）或背叛（指责对方）。不同选择的结果如下： - 如果两人都合作，他们都服刑一年。 - 如果参与者 \(i\) 合作而另一个参与者 \(-i\) 背叛，那么 \(i\) 服刑四年，\(-i\) 无需服刑。 - 如果两人都背叛，他们都服刑三年。 该游戏有两个参与者 \(I = \{1, 2\}\)，行动集合 \(A = A_1 \times A_2\)，其中每个 \(A_i = \{\text{cooperate}, \text{defect}\}\)。游戏可以进行一次或重复多次，在无限期的情况下，使用折扣因子 \(\gamma = 0.9\)。 ### 2.3 石头 - 剪刀 - 布 石头 - 剪刀 - 布是世界各地常见的游戏。有两个参与者，每个参与者可以选择石头、剪刀或布。规则如下： - 石头胜剪刀，出石头的参与者获得 1 个奖励，出剪刀的参与者获得 -1 个奖励。 - 剪刀胜布，出剪刀的参与者获得 1 个奖励，出布的参与者获得 -1 个奖励。 - 布胜石头，出布的参与者获得 1 个奖励，出石头的参与者获得 -1 个奖励。 游戏有两个参与者 \(I = \{1, 2\}\)，行动集合 \(A = A_1 \times A_2\)，其中每个 \(A_i = \{\text{rock}, \text{paper}, \text{scissors}\}\)。游戏可以进行一次或重复多次，在无限期的情况下，使用折扣因子 \(\gamma = 0.9\)。 ### 2.4 旅行者困境 旅行者困境是一个航空公司丢失两个相同行李箱的游戏。航空公司要求两位旅行者写下行李箱的价值，价值范围在 2 美元到 100 美元之间。奖励函数如下： - 如果两人写下的价值相同，他们都获得该价值。 - 如果旅行者 \(i\) 写下的价值低于另一个旅行者 \(-i\)，那么 \(i\) 获得其价值加 2 美元，\(-i\) 获得 \(i\) 的价值减 2 美元。 大多数人倾向于写下 97 美元到 100 美元之间的价值，但反直觉的是，唯一的纳什均衡是 2 美元。 ### 2.5 捕食者 - 猎物六角世界问题 捕食者 - 猎物六角世界问题扩展了六角世界的动态，包含多个由捕食者和猎物组成的参与者。捕食者试图尽快捕获猎物，猎物则试图尽可能长时间地逃脱捕食者。 游戏的初始状态给定，没有终止状态。有一组捕食者 \(I_{pred}\) 和一组猎物 \(I_{prey}\)，状态 \(S = S_1 \times \cdots \times S_{|I|}\) 包含每个参与者的位置，联合行动空间 \(A = A_1 \times \cdots \times A_{|I|}\)，其中每个 \(A_i\) 由六个六角方向的移动组成。 如果捕食者 \(i \in I_{pred}\) 和猎物 \(j \in I_{prey}\) 处于同一个六角格中，猎物将被捕获并被传送到一个随机的六角格，代表其后代出现在世界中。否则，状态转移是独立的，与原始六角世界的描述相同。 如果 \(n\) 个捕食者和 \(m\) 个猎物在同一个格子中，每个捕食者获得 \(m/n\) 的奖励。移动的捕食者会受到 -1 的惩罚，猎物移动没有惩罚，但被捕获会受到 100 的惩罚。 ### 2.6 多照顾者婴儿哭闹问题 多照顾者婴儿哭闹问题是单照顾者婴儿哭闹问题的多智能体扩展。有两个照顾者 \(i \in I = \{1, 2\}\)，状态 \(S = \{\text{hungry}, \text{sated}\}\)，行动 \(A_i = \{\text{feed}, \text{sing}, \text{ignore}\}\)，观察 \(O_i = \{\text{crying}, \text{quiet}\}\)。 状态转移动态与原始问题类似，但任何一个照顾者喂养都能让婴儿吃饱： - \(T(\text{sated} | \text{hungry}, (\text{feed}, \star)) = T(\text{sated} | \text{hungry}, (\star, \text{feed})) = 100\%\) - 若行动不是喂养，则婴儿在吃饱与饥饿状态之间的转移与之前相同。 观察动态也与单智能体版本类似，但模型确保两个照顾者对婴儿的观察相同，但不一定能观察到对方的照顾行动选择。 两个照顾者在婴儿饥饿