介绍

进化计算领域涉及各种进化算法的研究。这些算法可用于各种目的。也许可以使用它们的最流行的目的是函数优化。在函数优化中，进化算法可以被视为启发式算法，可替代组合优化和数学规划领域的更传统技术。进化算法可用于的另一个重要目的是生物和社会现象的建模，这是本文关注的主题，本文旨在使用进化算法来建模社会现象。

模拟有限理性行为的新视角

在社会建模环境中使用进化算法时，人们所做的一个假设是，其行为被建模的代理是有限理性的。这基本上意味着假定代理的行为不是效益最大化的方式。有许多方法可以对有限理性行为进行建模。一种流行的方法是依靠进化的隐喻，这是进化算法采用的方法。

在最简单的形式中，进化方法假设存在一个代理群体，并且对于群体中的每个代理，它使用的策略取决于策略在总体上过去的表现。策略的过去表现越好，该策略再次使用的可能性就越大。进化方法还假设代理尝试新策略的可能性总是很小。

模拟有限理性行为的进化方法引起了很多关注，不仅来自进化计算领域的研究人员，也来自社会科学的研究人员，特别是经济学家。传统上，经济学家通常依靠博弈论模型来分析主体之间的相互作用。这些模型假设代理以完全理性的方式行事。

然而，如今，博弈论模型的局限性已得到充分认可，许多经济学家已经开始研究主体行为的进化模型。这些模型基于这样的假设，即使用某种进化机制而不是使用完全理性的概念来最好地描述代理的行为。

在经济学领域，有两个完全独立的研究流派都关注模拟有限理性行为的进化方法。一种研究流，通常被称为基于代理的计算经济学，利用进化计算领域的技术。特别是遗传算法（GA）经常被使用。

另一个研究流与传统博弈论关系更密切，被称为进化博弈论。与传统的博弈论方法一样，进化博弈论方法是基于模型的，并且严重依赖于数学分析。计算机模拟的使用在进化博弈论中并不常见。

本文的目的不是支持强调算法和计算机模拟的基于代理的计算经济学方法，也不是强调模型和数学分析的进化博弈论方法。相反，本文想展示前一种方法如何从后一种方法中使用的数学技术中受益。更具体地说，我们想展示如何使用进化博弈论中流行的技术对用于建模社会现象的进化算法进行数学分析。本文的重点是一种特定类型的进化算法，即具有二进制编码的GA。

然而要强调的是，采取的方法也可以应用于其他类型的进化算法。关注具有二进制编码的 GA 的原因是，这似乎是最常用于建模社会现象的进化算法类型。

在本文中介绍的数学分析涉及使用二进制编码的 GA 的长期行为。假设 GA 用于社会建模上下文。在Vriend的术语中，我们关注的是用于建模社会学习（而不是个人学习）的GA。我们的工作可以看作以往工作的延伸，他得出了许多关于GA行为的重要数学结果，与使用计算机模拟相比，本文的数学结果至少具有三个优势：

我们的数学结果可用于精确计算 GA 的长期行为，而计算机模拟只能用于估计 GA 的长期行为。使用计算机模拟时，可能很难确定需要多少次迭代才能合理地接近 GA 的长期行为。我们的数学结果没有这个问题。使用我们的数学结果计算 GA 的确切长期行为比使用计算机模拟获得对 GA 长期行为的合理准确估计需要更少的计算时间。

本文的数学结果有一个重要的限制，那就是在当今的大多数计算机上，只有在染色体长度不大于约24位的情况下才能使用它们。如果染色体长度大于24位，使用我们的数学结果来计算 GA 的长期行为很可能需要大量的计算机内存。

与Dawid（1996）一样，本文提出的数学分析依赖于突变率为正但无限小的假设。换句话说，分析涉及突变率接近零的极限情况。在使用 GA 的模拟研究中，研究人员通常使用 0.001 到 0.01 之间的突变率值。这似乎是一个相当务实的选择。

一方面，较低的突变率值会导致收敛非常慢，从而导致非常长的仿真运行。另一方面，突变率的较高值将导致收敛到不稳定，难以解释的结果。相信对无限小突变率的假设是合理的，因为无限小的突变率比突变率更不武断，后者的值完全基于实用性基础确定。

无限小突变率的假设也符合进化博弈论中的常见做法，其中几乎总是做出类似的假设。假设无限小的突变率的优点是，它大大简化了GA长期行为的数学分析。

事实上，具有无限小突变率的GA可以以与进化博弈论中众所周知的模型类似的方式进行分析。与进化博弈论一样，Freidlin和Wentzel提供的数学结果是分析收敛将发生的长期行为的关键工具。注意到，除了无限小突变率的假设之外，数学分析还依赖于其他一些技术假设，这些假设中的大多数都不是很强大，大多数大会可能会满足这些假设。

分析

分析的GA的一般形式如图所示，在此图中，以及本文的其余部分中，正整数n和m以及概率γ和\（\varepsilon\）分别表示种群大小，染色体长度，交叉率和突变率。为简单起见，我们假设人口大小 n 为偶数。我们进一步假设交叉率γ和突变率\（\varepsilon\）随着时间的推移保持不变。我们还假设\（\varepsilon\）是正数。

我们分析的GA与规范GA一样，假设使用二进制编码，即染色体对应于GA中的位字符串。与规范 GA 不同，不假设使用特定的选择和交叉运算符。相反，我们分析的 GA 可能使用几乎任何选择运算符，例如轮盘赌选择、锦标赛选择或排名选择，以及任何交叉运算符，例如单点交叉、两点交叉或统一交叉。

此外，在分析的GA中，染色体的适应性可能取决于整个群体，而不仅仅是染色体本身。当使用GA进行社会建模时，染色体的适应性通常取决于整个人群。这被称为状态依赖性适应度。在大多数研究中，用于社会建模的GA与我们在本文中分析的GA具有相同的一般形式。

以下定理陈述了我们分析的主要结果：

首先，在某些假设下，非均匀种群的长期极限概率为零的结果并不新鲜。

其次，在定理的假设下，总体的长期极限概率不依赖于交叉率γ。这是一个非常了不起的结果，据我们所知，在关于大会的理论文献中以前从未报道过。它表明，在极限下，当突变率\（\varepsilon\）接近零时γ对GA的长期行为没有影响。

第三，该定理可用于计算长期极限分布，前提是可以计算中定义的概率对于所有 i 和所有 j，使得 δ（i， j） = 1，这反过来又在很大程度上取决于人们想要使用 GA 建模的特定问题。

讨论

通过对用于建模社会现象的GA的长期行为进行了数学分析。在正突变率但无限小的假设下，该分析提供了具有二进制编码的GA长期行为的完整表征。基于分析，我们推导出了一种计算 GA 长期行为的算法。

例如，在经济背景下，该算法可用于确定是否会发生趋同到均衡，如果是，将出现什么样的均衡。与计算机模拟相比，该算法的主要优点是它可以精确地计算GA的长期行为，计算机模拟仅估计 GA 的长期行为。

为了证明数学分析的有用性，复制了Axelrod的一项著名研究，其中GA用于模拟IPD中策略的演变。使用精确的算法和计算机模拟来复制阿克塞尔罗德的研究。通过比较两种方法的结果，证实了算法的正确性。

此外，还获得了一些有趣的新见解。例如，当玩家的记忆长度为一个时期时，针锋相对的策略就没有有时声称的那么重要。 从长远来看，该策略只有14%的时间被使用。

另一个发现是，GA的长期行为对突变率的值非常敏感。我们认为这是一个严重的问题，因为突变率的值通常是以相当武断的方式选择的，没有任何经验证明。

数学分析还表明，如果突变率无限小，则交叉率对GA的长期行为没有影响。对于突变率的各种值，仿真结果表明交叉率对GA的长期行为没有显著影响。 因此，当GA用于对社会现象进行建模时，交叉率似乎是一个相当不重要的参数，至少当重点是长期时。

在许多情况下，完全省略交叉算子似乎对GA的长期行为没有显著影响。 有趣的是，省略交叉算子使GA非常接近进化博弈论中的知名模型。

最后，本文中提出的分析不仅可以对具有二进制编码的GA进行，还可以对其他类型的进化算法进行。从建模的角度来看，二进制编码在许多情况下具有缺乏明确解释的缺点。因此，使用二进制编码可能难以证明，甚至可能导致伪影。可能由于这些原因，一些研究人员使用没有二进制编码的进化算法。

因此，本文中的分析并不直接适用。然而，当代理的行动空间被假定为离散时，没有二进制编码的进化算法的长期行为仍然可以以类似于本文中所做的方式进行分析。

●—<参考文献>—●

【1】Alkemade F， La Poutré JA， Amman HM （2006） 社会经济模拟的鲁棒进化算法设计。计算机经济学 28（4）：355–370

【2】Alkemade F， La Poutré JA， Amman HM （2007） 关于库尔诺寡头垄断博弈中的社会学习和稳健进化算法设计。计算机信息23（2）：162–175

【3】Alkemade F， La Poutré JA， Amman HM （2009） 社会经济模拟的鲁棒进化算法设计：修正。计算机经济学 33（1）：99–101

【4】Andreoni J， Miller JH （1995） Auctions with artificial adaptive agents.博弈经济行为 10（1）：39–64

【5】Arifovic J （1994） 遗传算法学习和蜘蛛网模型。经济动态控制杂志 18（1）：3–28