FakeOrange随机扩散搜索入门（Stochastic Diffusion Search, SDS）
SDS引入了一种全新的基于概率的多智能体方法，用以寻找全局最优解。
前言
本文属于搬运内容，原作者：Leon Fedden （Salute！）原文链接在文章末尾！
欢迎来到本周关于“受自然启发的算法”系列的文章。以下是前几周的内容链接：
本周的完整代码（基于C++和openFrameworks库）可以在GitHub仓库中找到。
什么是随机扩散搜索（SDS）？
随机扩散搜索（Stochastic Diffusion Search, SDS）属于群体智能算法的大家族。与许多其他受自然启发的算法不同，SDS已经建立了一种数学框架，证明了它具有以下两个特性：
- 收敛性：在足够的时间和计算资源条件下可以达到全局最优解。
- 线性时间复杂度：在搜索效率方面表现出色。
SDS 引入了一种全新的基于概率的多智能体方法，用以寻找全局最优解。
SDS核心概念：两种隐喻
在 SDS 算法中，有两种高层次的比喻来形象化地描述其机制：
- 采矿隐喻（Mining）
- 餐馆隐喻（Restaurants）
本文选取了采矿隐喻来介绍这一算法，并配以对应的代码说明：
采矿隐喻
一群矿工发现附近的山丘中蕴藏着丰富的金矿（全局最优解）。这些贪婪的淘金矿工各自冥思苦想，并随机地提出一个假设，猜测某座山中可能藏有金矿。这些山包含多个潜在的挖掘点，而矿工会随机选择其中一个（即山可以被分割成多个局部搜索区域）。
一天中，矿工们会前往选定的挖掘点，并检查他们的假设是否正确。这个过程称为测试阶段（Test Phase）。
下面是代码实现的核心片段：
for (auto& agent : agents)
{
if (agent->set_happy(partial_grid))
{
happy_agents.push_back(agent);
const size_t hill_index = get_hill_index((*agent), partial_size, grid_size);
if (++most_frequent_hill_indices[hill_index] > max_indices)
{
max_indices = most_frequent_hill_indices[hill_index];
best_index = hill_index;
}
}
else
unhappy_agents.push_back(agent);
}
best_hill_coordinates = get_hill_position(best_index, partial_size, grid_size, draw_scalar);
代码解析
- 智能体的状态更新
- 记录最佳区域
- 更新全局最优解
采矿隐喻的下一步：扩散阶段（Diffusion Phase）
到了晚上，矿工们齐聚当地的酒馆，一边喝酒一边热烈讨论谁找到了金矿。每个未找到金矿的矿工都会感到沮丧，他们会随机问其他矿工是否在自己的山上找到了金矿。
- 如果对方找到了金矿并且感到满意，那么沮丧的矿工会选择该山上的某个随机位置提出新的假设。
- 如果对方也是沮丧的矿工，他们决定完全随机地在新位置上尝试寻找金矿。
这一部分的搜索过程称为扩散阶段（Diffusion Phase）。以下是代码实现的核心逻辑：
for (auto& agent : unhappy_agents)
{
if (happy_agents.size() > 0)
{
size_t random_index = uniform_random.get_next(agent_size - 1);
if (agents[random_index]->happy)
{
set_agent_randomly_in_same_quadrant(agents[random_index],
agent,
agents,
partial_grid,
partial_size,
grid_size,
uniform_random);
}
else
{
agent->x = uniform_random.get_next(grid_size - 1);
agent->y = uniform_random.get_next(grid_size - 1);
}
}
else
{
agent->x = uniform_random.get_next(grid_size - 1);
agent->y = uniform_random.get_next(grid_size - 1);
}
}
代码解析
- 扩散策略对于所有“不开心”的智能体（矿工），他们会随机与其他智能体互动：若找到“开心”的智能体：则将自己随机地调整到相同山丘的某一区域中。若遇到另一个“不开心”的智能体：则完全随机地在新的网格位置生成一个假设。
- 当没有“开心”的智能体存在时所有“不开心”的智能体都会完全随机地选择一个新位置进行搜索。
测试阶段与扩散阶段的循环
**测试阶段（Test Phase）和扩散阶段（Diffusion Phase）**会被反复执行，直到找到解决方案为止。
终止条件
SDS 的退出或终止策略较为灵活，以下是常见的几种方式：
- 手动中断不设置任何终止条件，由用户手动中止算法。这通常适用于问题空间动态变化或没有预定义模式的情况。
- 基于时间的终止条件设置时间或迭代次数的上限，算法在达到上限时自动停止。
- 基于聚类的终止条件通过跟踪稳定聚类的形成，当群体智能体聚集到某个稳定的区域后，停止搜索。
动态问题空间中的随机扩散搜索
当解空间随着时间变化时，问题的复杂性会显著增加。以下展示的是一个经过修改的 SDS，在由**三维柏林噪声（Perlin Noise）**生成的阈值化问题空间上运行的示例。需要注意的是，SDS 只能在给予足够时间的情况下保证找到全局最优解，而对于每一帧来说，算法显然没有足够的时间！
动态问题空间的挑战
在动态问题空间中，智能体可能会过度开发某个已经确定的山丘，即便有更好的山丘或解出现。为了解决这一问题，可以通过引入**上下文敏感机制（Context Sensitive Mechanism）**对算法进行改进，以释放资源并增强搜索的探索性。
上下文敏感机制的改进
该机制的核心思想：智能体的假设复制
这一机制有效防止智能体集中在同一个区域，促进了更全面的探索。
动手尝试
想要进一步研究 SDS 的动态行为？可以下载代码并亲自动手试试！代码行数不多，上手非常容易。
感谢阅读！ 😊
希望本篇文章让你对随机扩散搜索有了更深入的理解。如果有任何问题或想法，欢迎留言讨论！