Question

科学家如何把蚂蚁的信息素转换为数学公式?

昨天看纪实频道,他说蚂蚁公式可以更方便的调节交通,运输等,我很好奇,请问下哪位知道,蚂蚁公式是什么样的?而且怎么转换的啊?谢谢了

Answer 1

看样子楼主已经知道了信息素这个概念，在此我也不赘述了。

目前蚁群算法主要用在组合优化方面，基本蚁群算法的思路是这样的：
1. 在初始状态下，一群蚂蚁外出，此时没有信息素，那么各自会随机的选择一条路径。
2. 在下一个状态，每只蚂蚁到达了不同的点，从初始点到这些点之间留下了信息素，蚂蚁继续走，已经到达目标的蚂蚁开始返回，与此同时，下一批蚂蚁出动，它们都会按照各条路径上信息素的多少选择路线(selection)，更倾向于选择信息素多的路径走（当然也有随机性）。
3. 又到了再下一个状态，刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation)，而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁，重复第2个步骤。
每个状态到下一个状态的变化称为一次迭代，在迭代多次过后，就会有某一条路径上的信息素明显多于其它路径，这通常就是一条最优路径。

关键的部分在于步骤2和3：
步骤2中，每只蚂蚁都要作出选择，怎样选择呢？
selection过程用一个简单的函数实现：
蚂蚁选择某条路线的概率＝该路线上的信息素÷所有可选择路线的信息素之和
假设蚂蚁在i点，p(i,j)表示下一次到达j点的概率，而τ(i,j)表示ij两点间的信息素，则：
p(i,j)＝τ(i,j)/∑τ(i)
（如果所有可选路线的信息素之和∑τ(i)＝0，即前面还没有蚂蚁来过，概率就是一个[0,1]上的随机值，即随机选择一条路线）
步骤3中，挥发和增强是算法的关键所在（也就是如何数学定义信息素的）
evaporation过程和reinforcement过程定义了一个挥发因子，是迭代次数k的一个函数
ρ(k)＝1－lnk/ln(k+1)
最初设定每条路径的信息素τ(i,j,0)为相同的值
然后，第k+1次迭代时，信息素的多少
对于没有蚂蚁经过的路线：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)，显然信息素减少了
有蚂蚁经过的路线：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)＋ρ(k)/|W|，W为所有点的集合

为什么各个函数要如此定义，这个问题很难解释清楚，这也是算法的精妙所在。如此定义信息素的挥发和增强，以及路径选择，根据马尔可夫过程（随机过程之一）能够推导出，在迭代了足够多次以后，算法能够收敛到最佳路径。

组合优化很有意思的，像禁忌搜索、模拟退火、蚁群算法、遗传算法、神经网络这些算法能够解决很多生活中的实际问题，楼主有空可以招本书看看。

Answer 2

人工蚂蚁系统（Ant System）是对自然界蚁群（Ant Colony）的一个较好人工模拟。这里每个蚂蚁就是一个很简单的主体（Agent），通过蚂蚁与环境之间的气味等信息素的交互作用，使得系统在整体上具有较高的智能（Intelligent Emergence）。这一系统在诸如TSP问题、二次分配问题和网络的路由优化问题都有很好的应用前景。

关于这个系统和复杂性的研究，我有三个问题：

（1）蚂蚁算法在迭代多少次后才能产生第一个好解？具体来说，在一个解已知的TSP问题中，蚂蚁算法要迭代多少次才能产生这个解。有没有一个关于迭代次数的确定的数学公式？怎样找到？这是一个关系到人工蚂蚁系统效率的比较重要的问题。目前的文献并没有给出明确的回答。

（2）蚂蚁算法本身不具备并发性。蚂蚁都是一个接着一个的完成任务，快的蚂蚁总是要等待慢的。而实际的蚁群是并行工作的，虽然在单处理器不能并行工作，但可以建立一种并发机制来改善目前蚂蚁算法效率不太高的缺陷。那么怎样建立这种机制呢？

Answer 3

关于这个系统和复杂性的研究，我有三个问题：

（1）蚂蚁算法在迭代多少次后才能产生第一个好解？具体来说，在一个解已知的TSP问题中，蚂蚁算法要迭代多少次才能产生这个解。有没有一个关于迭代次数的确定的数学公式？怎样找到？这是一个关系到人工蚂蚁系统效率的比较重要的问题。目前的文献并没有给出明确的回答。

（2）蚂蚁算法本身不具备并发性。蚂蚁都是一个接着一个的完成任务，快的蚂蚁总是要等待慢的。而实际的蚁群是并行工作的，虽然在单处理器不能并行工作，但可以建立一种并发机制来改善目前蚂蚁算法效率不太高的缺陷。那么怎样建立这种机制呢？

（3）目前国际上对复杂性、混沌、分形以及非线形动力系统的研究都很活跃，并且这些领域的研究工作都被相互引用，那么这些领域之间到底有什么联系与差别呢？

Answer 4

人工蚂蚁系统（Ant System）是对自然界蚁群（Ant Colony）的一个较好人工模拟。这里每个蚂蚁就是一个很简单的主体（Agent），通过蚂蚁与环境之间的气味等信息素的交互作用，使得系统在整体上具有较高的智能（Intelligent Emergence）。这一系统在诸如TSP问题、二次分配问题和网络的路由优化问题都有很好的应用前景。

关于这个系统和复杂性的研究，我有三个问题：

（1）蚂蚁算法在迭代多少次后才能产生第一个好解？具体来说，在一个解已知的TSP问题中，蚂蚁算法要迭代多少次才能产生这个解。有没有一个关于迭代次数的确定的数学公式？怎样找到？这是一个关系到人工蚂蚁系统效率的比较重要的问题。目前的文献并没有给出明确的回答。

（2）蚂蚁算法本身不具备并发性。蚂蚁都是一个接着一个的完成任务，快的蚂蚁总是要等待慢的。而实际的蚁群是并行工作的，虽然在单处理器不能并行工作，但可以建立一种并发机制来改善目前蚂蚁算法效率不太高的缺陷。那么怎样建立这种机制呢？

（3）目前国际上对复杂性、混沌、分形以及非线形动力系统的研究都很活跃，并且这些领域的研究工作都被相互引用，那么这些领域之间到底有什么联系与差别呢？

Answer 5

“蚂蚁公式是什么样的?而且怎么转换的啊?”
面对着百度，还对这样教科书般的概念问题发愁？
直接搜索不就完了吗？各色答案千奇百怪，肯定有你想要的。