草庐IT

蚁群算法及 TSP 问题上的应用

bringlu 2023-03-28 原文

群智能（Swarm intelligence）

自然界动物群，称之为群。

群的特征：

  • 相互作用的相邻个体的集合
  • 个体的行为简单，既有竞争又有协作
  • 智能化的集体行为（1+1>2）：
    • 个体间不仅能够交互信息，还能够处理信息，根据信息改变自身行为
    • 没有一个集中控制中心，分布式、自组织
    • 作为群体协同工作时，展现出非常复杂的行为特征——智能

任何一种由昆虫群体或其他动物社会行为机制而激发设计出的算法或分布式解决问题的策略都属于群智能算法

典型算法：

  • 粒子群 PSO
  • 蚁群 ACO
  • 人工鱼群 AFSA
  • 人工蜂群 ABCA

算法原理：蚁群觅食

模拟自然界蚁群觅食（从巢穴到食物的最佳路径的行为）的过程。

  • 自然界中，蚂蚁会在觅食路上留下”信息素“来作为前往食物所在地的标记。
  • 信息素会逐渐挥发，蚂蚁倾向于沿着”信息素“浓度更高的路径前往食物所在地。
  • 信息素浓度更高的路径上蚂蚁会更多
  • 最后，几乎所有蚂蚁会选择更短的路径

算法步骤

TSP 问题示例

路径构建/构造解空间

对每只蚂蚁选择下一个城市，直到遍历所有的城市

蚂蚁 \(k\) 从城市 \(i\) 到城市 \(j\) 的概率为：

\[p_{ij}^k = \begin{cases} \frac{\tau_{ij}^\alpha (t)* \eta_{ij}^\beta}{\sum_{s \in \phi_k} \tau_{is}^\alpha (t)* \eta^{\beta}_{is}},& j \in \phi_k \\ 0,& otherwise \end{cases} \]

  • \(i, j\) 分别为起点和终点
  • \(\eta_{ij} = 1 / d_{ij}\) 为能见度，是两点 \(i, j\) 距离的倒数
  • \(\tau_{ij}(t)\) 为时间 \(t\) 时由 \(i\) 到 \(j\) 的信息素强度
  • \(\phi_k\) 为尚未访问过的节点集合
    • 这个尚未访问过的节点集合是什么意思？每只蚂蚁需要存储自己去过哪些城市，直到它走过了所有城市。
  • \(\alpha, \beta\) 为两个常数，分别是信息素和能见度的加权值。

更新信息素浓度

更新各城市间信息素浓度

  • 更新各城市间信息素浓度
  • \(t+1\) 次循环，城市 \(i, j\) 之间的信息素浓度为：\(\tau_{ij}(t+1) = \tau_{ij}(t) * (1- \rho) + \Delta \tau_{ij}(t), 0 < \rho < 1 \\ \Delta \tau_{ij}(t) = \sum_{k=1}^m \Delta \tau_{ij}^k(t)\)
  • \(\Delta \tau_{ij}^k(t)\) 为 t 次循环，蚂蚁 k 在 \((i,j)\) 路径上留下的信息素
  • \(\Delta \tau_{ij}(t)\) 为 t 次循环，\((i,j)\) 路径上新增的信息素
  • \(\rho\) 为信息素挥发常数

计算新增信息素浓度

  • 蚁密模型（Ant-Density）：\(\Delta \tau_{ij}^k(t) = \begin{cases} Q,& if (i, j) \in \psi_k(t) \\ 0,& otherwise \end{cases}\)
  • 蚁量模型（Ant-Quantity）：\(\Delta \tau_{ij}^k(t) = \begin{cases} \frac{Q}{d_{ij}},& if (i, j) \in \psi_k(t) \\ 0,& otherwise \end{cases}\)
  • 蚁周模型（Ant-Cycle）：\(\Delta \tau_{ij}^k(t) = \begin{cases} \frac{Q}{L_k(t)},& if (i, j) \in \psi_k(t) \\ 0,& otherwise \end{cases}\)
  • Q 是信息素常量
  • \(L_k(t)\) 是第 \(t\) 次循环，蚂蚁 \(k\) 遍历所有城市的总路径长度
  • \(\psi_k(t)\) 是第 \(t\) 次循环，蚂蚁 \(k\) 遍历所有城市的路径集合

这里一般常用的是蚁周模型，这个式子有点奇怪，为什么所有经过的路都是平分信息素的？

参数分析

蚂蚁数量 \(m\)

  1. 过大：收敛速度减慢
  2. 过小：搜索范围减小，易过早收敛，陷入局部最优
  3. 参考值：目标图的节点数量的 1.5 倍

信息素常量 \(Q\)

  1. 过大：搜索范围减小，易过早收敛，陷入局部最优
  2. 过小：每条路径上信息含量差别较小，容易陷入混沌状态
  3. 参考值：\([0, 1000]\)

最大迭代次数

  1. 过大：运算速度过长
  2. 过小：可选路径较少，易陷入局部最优
  3. 参考值：\([0,500]\)

信息素因子 \(\alpha\)

  1. 过大：蚂蚁选择以前已经走过的路可能性加大，容易使随机搜索性减弱
  2. 过小：蚁群易陷入纯粹的随机搜索，使种群陷入局部最优
  3. 参考值：\([1, 4]\)
    • 为了使它是蚁群算法，因此参考值最小值是 \(1\) 而不是 \(0\)。

启发函数因子 \(\beta\)

  1. 过大：选择局部最短路径的可能性较大，
  2. 过小：蚁群易陷入纯粹的随即搜索，很难找到最优解
  3. 参考值：\([0,5]\)

信息素挥发因子 \(\rho\)

  1. 过大：信息素挥发过快，容易导致较优路径被排除，降低算法收敛速度
  2. 过小：以前搜索过的路径被再次选择的可能性较大，易降低算法随机性和全局搜索能力
  3. 参考值：\([0.2,0.5]\)

总结

调参的目的是在寻优和随机上找个平衡。

需要一个离群者寻找最短路径。

由于不清楚公式中值域是多少，因此这个算法事实上调参后会导致某一部分做幂次后增大/减小的不明确。

TSP蚁群spaninlineli人工智能

有关蚁群算法及 TSP 问题上的应用的更多相关文章

  1. ruby - 将差异补丁应用于字符串/文件 - 2

    对于具有离线功能的智能手机应用程序，我正在为Xml文件创建单向文本同步。我希望我的服务器将增量/差异(例如GNU差异补丁)发送到目标设备。这是计划:Time=0Server:hasversion_1ofXmlfile(~800kiB)Client:hasversion_1ofXmlfile(~800kiB)Time=1Server:hasversion_1andversion_2ofXmlfile(each~800kiB)computesdeltaoftheseversions(=patch)(~10kiB)sendspatchtoClient(~10kiBtransferred)Cl

  2. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  3. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  4. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  5. ruby - 无法运行 Rails 2.x 应用程序 - 2

    我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby​​:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r

  6. ruby-on-rails - Rails 应用程序中的 Rails : How are you using application_controller. rb 是新手吗？ - 2

    刚入门rails，开始慢慢理解。有人可以解释或给我一些关于在application_controller中编码的好处或时间和原因的想法吗？有哪些用例。您如何为Rails应用程序使用应用程序Controller？我不想在那里放太多代码，因为据我了解，每个请求都会调用此Controller。这是真的？ 最佳答案 ApplicationController实际上是您应用程序中的每个其他Controller都将从中继承的类(尽管这不是强制性的)。我同意不要用太多代码弄乱它并保持干净整洁的态度，尽管在某些情况下ApplicationContr

  7. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  8. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  9. ruby-on-rails - date_field_tag，如何设置默认日期？ [ rails 上的 ruby ] - 2

    我想设置一个默认日期，例如实际日期，我该如何设置？还有如何在组合框中设置默认值顺便问一下，date_field_tag和date_field之间有什么区别？ 最佳答案 试试这个:将默认日期作为第二个参数传递。youcorrectlysetthedefaultvalueofcomboboxasshowninyourquestion. 关于ruby-on-rails-date_field_tag，如何设置默认日期？[rails上的ruby]，我们在StackOverflow上找到一个类似的问

  10. ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby​​ 变量的内容？ - 2

    我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby​​中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R

随机推荐