OctopusOS 算法分析

基于 kernel 域模块和 shared 层的真实代码实现，梳理 OctopusOS 使用的核心算法。

1. 贝叶斯 Beta 信念更新（Bayesian Beta Belief Update）

用途

评估每个 Capability 的可靠性，动态调整信任度，驱动自动晋升/降级决策。

代码位置

• kernel/contracts/capability_belief.py — CapabilityBelief 冻结数据类
• kernel/domains/capability_learning/execution_feedback.py — 核心更新算法（第 54-210 行）

算法原理

采用 Beta 分布（Beta(α, β)）建模 Capability 成功概率的先验与后验：

# 每次执行结果反馈
def update_belief(belief: CapabilityBelief, success: bool) -> CapabilityBelief:
    if success:
        return replace(belief, alpha=belief.alpha + 1)  # α += 1
    else:
        return replace(belief, beta=belief.beta + 1)    # β += 1

计算属性（computed properties）：

晋升/降级决策

代码证据： kernel/domains/capability_learning/execution_feedback.py 第 187-210 行

晋升条件（shadow → learned）：

• 执行次数 ≥ 10
• 成功率 ≥ 80%
• belief_mean ≥ 0.7
• runtime_score ≥ 0.6

降级条件（learned → shadow）：

• 执行次数 ≥ 5 且失败率 > 50%
• 或 belief_mean < 0.3
• 或遭遇关键失败类别（TIMEOUT、DATA_LOSS、CORRUPTION、SECURITY）

反馈综合评分

score = (success_rate * 0.5) + (reliability * 0.2) + (latency_score * 0.2) + (retry_penalty * 0.1)

延迟评分映射：

• ≤1s → 1.0
• ≤5s → 0.7
• ≤15s → 0.4

• 15s → 0.1

2. AC-3 弧一致性约束求解（Arc Consistency CSP Solver）

用途

解决调度、资源分配、任务排列等约束满足问题（CSP）。

代码位置

• kernel/domains/constraint_solver/solver.py — AC-3 算法 + MRV 启发式（第 1-200 行）
• kernel/domains/constraint_solver/validator.py — 约束验证

算法实现

Phase 1: AC-3 弧一致性预处理

def _ac3(variables, constraints):
    """删除不可能的值，缩小搜索空间"""
    queue = deque(all_arcs)
    while queue:
        (xi, xj) = queue.popleft()
        if _revise(xi, xj):       # 如果 xi 的域被缩减
            if len(xi.domain) == 0:
                return False       # 无解
            for xk in neighbors(xi) - {xj}:
                queue.append((xk, xi))
    return True

Phase 2: MRV（Most Restrained Variable）回溯搜索

选择剩余域最小的变量优先赋值，结合前向检查（Forward Checking）剪枝。

支持的比较器：

• 数值：eq, ne, gt, lt, gte, lte
• 时间：before, within（时序约束）

代码证据

• solver.py 第 103-130 行 — _revise() 函数实现弧修剪
• solver.py 第 135-180 行 — _evaluate_constraint() 支持 8 种比较器

3. BM25 全文检索

用途

文档知识库的关键词检索，作为混合搜索的精确匹配分支。

代码位置

• kernel/domains/docset/bm25.py — BM25 完整实现

算法公式

$$score(D, Q) = \sum_{i=1}^{n} IDF(q_i) \cdot \frac{tf(q_i, D) \cdot (k_1 + 1)}{tf(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{avgdl})}$$

参数：

• k1 — 词频饱和度（默认 1.2-2.0）
• b — 文档长度归一化因子（默认 0.75）
• IDF — 逆文档频率

混合搜索融合

代码位置： kernel/domains/docset/hybrid_search.py

将 BM25 分数与向量嵌入余弦相似度按权重融合：

final_score = α * bm25_score + (1-α) * embedding_similarity

4. 风险评分算法（Risk Scoring）

用途

对外部学习的 Capability 进行安全风险量化评估。

代码位置

• kernel/domains/capability_learning/risk_evaluator.py — 第 11-148 行

评分规则

风险分级

代码证据： risk_evaluator.py 第 120-148 行 — 分级阈值和路由逻辑

5. 屏幕操作风险分类（Screen Risk Classification）

用途

GUI 操作前的安全评估，阻止高风险 UI 交互。

代码位置

• kernel/domains/screen_os/risk_classifier.py — 风险分类器
• kernel/contracts/screen_os.py — ScreenRiskAssessment 冻结类

风险因子累加

风险等级

6. 资源放置算法（Resource Placement）

用途

收集主机硬件快照，为任务调度提供资源感知。

代码位置

• kernel/core/orchestration/central_orchestrator.py — 第 33-99 行

指标采集

# CPU 使用率 = 1 分钟负载均值 / 逻辑核心数
cpu_usage = load_avg_1m / os.cpu_count()
cpu_usage = min(cpu_usage, 1.0)  # 归一化到 [0, 1]

# 内存压力 = 已用内存 / 总内存
# 从 /proc/meminfo 读取 MemTotal, MemAvailable
memory_pressure = used_mb / total_mb

# 磁盘使用 = 通过 os.statvfs 获取
disk_used_ratio = 1.0 - (free_blocks / total_blocks)

7. 发现候选评分（Discovery Candidate Scoring）

用途

对自动发现的外部 Capability 进行排名，确定学习优先级。

代码位置

• kernel/domains/capability_learning/discovery_strategy.py — 候选排名算法

评分公式

# 流行度：对数缩放（避免大数主导）
popularity_score = log(1 + stars_or_downloads) / log(1 + max_stars)

# 新鲜度：基于年龄衰减
recency_score = max(0, 1.0 - age_days / max_age_days)

# 信任权重（来自 discovery_policy.py）
trust_weights = {
    "official": 1.5,    # 官方来源加权
    "community": 1.0,   # 社区来源
    "unknown": 0.6      # 未知来源降权
}

# 最终得分
final_score = (popularity_score * w1 + recency_score * w2) * trust_weight

去重逻辑： 基于 (source_type, name) 元组去重，保留最高分候选。

8. 版本漂移检测（Version Drift Detection）

用途

追踪已学习 Capability 的源版本变化，触发重新验证。

代码位置

• kernel/contracts/source_versioning.py — SourceFingerprint, VersionDrift, StalenessWarning
• kernel/domains/capability_learning/version_tracker.py — 指纹比对

内容寻址指纹

# SHA256 内容哈希
fingerprint = hashlib.sha256(content_bytes).hexdigest()

漂移分级

过期预警（Staleness）

基于风险等级的最大有效期：

9. 质量剖面分析（Quality Profiling）

用途

检测 Capability 的不稳定性和性能退化趋势。

代码位置

• kernel/contracts/outcome_quality.py — OutcomeGrade, QualityProfile
• kernel/domains/capability_learning/outcome_quality.py — 质量计算函数

结果分级（6 级）

不稳定性指数（Flakiness Index）

# 将执行历史分为子窗口，计算各窗口成功率的标准差
flakiness_index = std_dev(sub_window_success_rates)  # 范围 [0.0, 1.0]

退化评分（Degradation Score）

degradation_score = current_mean - baseline_mean  # 负值 = 退化

脆弱性检测

is_brittle = (flakiness_index >= 0.4) and (success_rate >= 0.6)
# 解读：整体看起来还行，但表现极不稳定

10. 断路器（Circuit Breaker）

用途

防止故障级联，在 Capability 连续失败时快速断开。

代码位置

• server/shared/ports_impl/dispatch_router.py — 第 66-74 行

状态机

CLOSED  ──(连续失败达阈值)──▶  OPEN
  ▲                              │
  │                        (超时后)
  │                              ▼
  └──────(成功)──────── HALF_OPEN

每个 Skill 独立维护断路器状态，防止一个故障 Skill 影响其他。

11. 显示偏好学习（Display Preference Learning）

用途

学习用户偏好的输出格式（表格/图表/卡片等），跨会话持久化。

代码位置

• products/cli/preferences.py — CLI 端实现
• products/web/src/hooks/useFormatPreferences.ts — Web 端实现

置信度模型

confidence = count / (count + 2)   # 拉普拉斯平滑
threshold = 0.6                     # 置信阈值

# 当 confidence >= threshold 时自动应用偏好
# count=3 → confidence=0.6 → 刚达阈值

三端（CLI / Web / Mobile）使用完全相同的置信度公式，确保行为一致。

12. UI 节点模糊匹配（Fuzzy Node Matching）

用途

在 GUI Accessibility Tree 中定位目标 UI 元素。

代码位置

• kernel/domains/screen_os/node_matcher.py — XPath 风格匹配

匹配维度

1. 角色匹配 — 按 NodeRole 过滤（28 种角色：button, text_field, checkbox 等）
2. 文本匹配 — name/value 模糊匹配
3. 边界检查 — 坐标范围内的可见性验证
4. 层级路径 — 类 XPath 的祖先链匹配

算法全景图

┌──────────────────────────────────────────────────────┐
│                  学习与进化层                          │
│  Bayesian Beta ─▶ 晋升/降级 ─▶ 发现评分 ─▶ 版本漂移   │
│  风险评分 ─▶ 质量剖面 ─▶ 不稳定性检测                   │
├──────────────────────────────────────────────────────┤
│                  知识与检索层                          │
│  BM25 + Embedding ─▶ 混合搜索 ─▶ 文档分块              │
├──────────────────────────────────────────────────────┤
│                  调度与约束层                          │
│  AC-3 CSP ─▶ MRV 回溯 ─▶ 资源放置 ─▶ 断路器            │
├──────────────────────────────────────────────────────┤
│                  感知与交互层                          │
│  屏幕风险分类 ─▶ 节点模糊匹配 ─▶ 偏好学习               │
└──────────────────────────────────────────────────────┘