重复囚徒困境的学习和响应模型

囚徒困境问题是博弈论的一个重要范例,对此的研究涉及经济学、社会学、生物学等广泛领域。Axelrod R在文献[1]中从进化的角度研究和探讨了经典囚徒困境的一个扩展--重复囚徒困境。这种博弈要求参与者反复进行囚徒困境的博弈,并且可以记住他们的对抗历史。Axelrod还组织了两次重复囚徒困境的计算机竞赛,最终胜出的都是简单的＂以
牙还牙＂策略[2]。这之后有不少学者试图找到可以击败它的策略,都未能取得显著成功。本文提出了一种学习和响应的理论模型,实际中的许多重复囚徒困境的策略都可以纳入这一模型中。我们分析了实现这一模型的难点和复杂度,同时给出了一种基于树结构的实现方式,并在实验中把它和“以牙还牙”作比较。实验以及分析表明,策略在竞赛中表现的优劣主要取决于如何利用一些启发式规则来权衡学习代价和博弈的总利益,以及在此基础上如何抽取对手的关键信息。     

The Impact of Payoff Function and Local Interaction on the N-Player Iterated Prisoner's Dilemma

The N-player iterated prisoner's dilemma (NIPD) game has been widely used to study the evolution of cooperation in social, economic and biological systems. This paper studies the impact of different payoff functions and local interactions on the NIPD game. The evolutionary approach is used to evolve game-playing strategies starting from a population of random strategies. The different payoff functions used in our study describe different behaviors of cooperation and defection among a group of players. Local interaction introduces neighborhoods into the NIPD game. A player does not play against every other player in a group any more. He only interacts with his neighbors. We investigate the impact of neighborhood size on the evolution of cooperation in the NIPD game and the generalization ability of evolved strategies. Received 18 August 1999 / Revised 27 February 2000 / Accepted 15 May 2000     

Leaving the Prison: Permitting Partner Choice and Refusal in Prisoner's Dilemma Games

We propose a simple rule of thumb on how to choose one's game partner thatallows economic agents who care about the future to learn to cooperate inthe iterated prisoner's dilemma. This rule of thumb uses partner selectionstrategically to reward cooperative behavior and teach defectors a lesson.This reward and punishment scheme leads to higher payoffs of non-exploitivestrategies and slowly converts defectors, who are attracted by the higherpayoffs, into non-exploitive types. Simulations show that the convergence tostable cooperative behavior is rather fast.     

An Adaptive Strategy via Reinforcement Learning for the Prisoner's Dilemma Game

The iterated prisoner's dilemma (IPD) is an ideal model for analyzing interactions between agents in complex networks. It has attracted wide interest in the development of novel strategies since the success of tit-for-tat in Axelrod's tournament. This paper studies a new adaptive strategy of IPD in different complex networks, where agents can learn and adapt their strategies through reinforcement learning method. A temporal difference learning method is applied for designing the adaptive strategy to optimize the decision making process of the agents. Previous studies indicated that mutual cooperation is hard to emerge in the IPD. Therefore, three examples which based on square lattice network and scale-free network are provided to show two features of the adaptive strategy. First, the mutual cooperation can be achieved by the group with adaptive agents under scale-free network, and once evolution has converged mutual cooperation, it is unlikely to shift. Secondly, the adaptive strategy can earn a better payoff compared with other strategies in the square network. The analytical properties are discussed for verifying evolutionary stability of the adaptive strategy.      

时间尺度与选择倾向性协同作用下的演化博弈模型

针对合作行为的涌现与维持问题，基于演化博弈理论和网络理论，提出了一种促进合作的演化博弈模型。该模型同时将时间尺度、选择倾向性引入到演化博弈中。在初始化阶段，根据持有策略的时间尺度将个体分为两种类型：一种个体在每个时间步都进行策略更新；另一种个体在每一轮博弈后，以某种概率来决定是否进行策略更新。在策略更新阶段，模型用个体对周围邻居的贡献来表征他的声誉，并假设参与博弈的个体倾向于学习具有较好声誉邻居的策略。仿真实验结果表明，所提出的时间尺度与选择倾向性协同作用下的演化博弈模型中，合作行为能够在群体中维持；惰性个体的存在不利于合作的涌现，但是个体的非理性行为反而能够促进合作。     

多目标进化算法中选择策略的研究

在多目标进化算法(multiobjective evolutiorlsry algorithms,MOEAs)的文献中,对算法的选择策略进行系统研究的还很少,而MOEAs的选择策略不仅引导算法的搜索过程、决定搜索的方向而且对算法的收敛性有重要的影响,它是算法能否成功求解多目标优化问题的关键因素之一.在统一的框架下,首先讨论了多目标优化问题中适应度函数的构造问题,然后根据MOEAs的选择机制和原理将它们的选择策略重新分成了6种类型.一般文献中很少对多目标进化算法的操作算子采用符号化描述,这样不利于对算子的深层次理解,符号化描述了各类选择策略的操作机制和原理,并分析了各类策略的优劣性.最后,从理论上证明了具备一定特征的多目标进化算法的收敛性,证明的过程表明了将算法运行终止时得到的P known作为多目标优化问题的Pareto最优解集或近似最优解集的合理性.     

基于自适应维度选择的记忆进化算法

提出一种基于自适应选择维度的记忆进化算法。该算法设置一个三维数组保存有用的进化信息,用于引导后续的进化过程,增强局部搜索能力,在变异过程中结合记忆信息自适应地选择维度进行变异,加强变异的有效性,当代种群中的最优个体通过自学习提高算法求解精度。标准函数仿真结果表明,该算法适合求解高维优化问题,局部收敛速度快,全局收敛能力强,算法稳定性高。     

多目标优化特征选择研究综述

特征选择是模式识别领域中有效的降维方法,当特征选择涉及到的多个目标彼此冲突,难以平衡时,将特征选择视为多目标优化问题是时下的研究热点。为方便研究者系统地了解多目标特征选择领域的研究现状和发展趋势,对多目标特征选择方法进行综述。阐明了特征选择和多目标优化的本质;根据多目标优化方法的区别和特点,重点对比剖析各类多目标优化特征选择方法的优劣势;讨论现有多目标优化特征选择研究方法存在的问题以及对未来的展望。     

一种进化算法的应用研究

该文对丛式井组井口定位进行了研究。丛式井就是由同一井场出发打多口井,它可以发挥井场的最大作用,节约用地,提高经济效益。这样如何选择最优点进行打井就成为了一个关键问题。这个问题可以抽象为一个求平面多边形内最优点的问题。该文推导了较有价值的求解本问题最优解的算法,包括目前采用的经验法和基本的穷举法。该文在较新的进化策略算法方面做了一些改进,达到更好的效果。通过实例验证,进化策略算法较以往通常采用的算法有优势。     

基于拟随机序列与克隆选择的进化V-detector 算法

阴性选择(NS)算法是人工免疫的核心方法,检测器生成是其关键。针对其经典V-detector算法中高维数据失效及随机生成初始检测器集过于集中而导致过早收敛等问题,首先采用拟随机序列生成初始检测器;然后通过克隆选择优化检测器集合,以覆盖非自体空间大小及数量作为亲和力标准,克服传统进化阴性选择(ENS)算法的局限性,并采用新型进化算子使得算法生成最优检测器集合;最后,通过实验验证了该方法的有效性。     

An Evolutionary Model of Endogenous Business Cycles

In this paper, we present an evolutionary model of industry dynamics yielding endogenous business cycles with ‘Keynesian’ features. The model describes an economy composed of firms and consumers/workers. Firms belong to two industries. The first one performs R&D and produces heterogeneous machine tools. Firms in the second industry invest in new machines and produce a homogenous consumption good. Consumers sell their labor and fully consume their income. In line with the empirical literature on investment patterns, we assume that the investment decisions by firms are lumpy and constrained by their financial structures. Moreover, drawing from behavioral theories of the firm, we assume boundedly rational expectation formation. Simulation results show that the model is able to deliver self-sustaining patterns of growth characterized by the presence of endogenous business cycles. The model can also replicate the most important stylized facts concerning micro- and macro-economic dynamics. Indeed, we find that investment is more volatile than GDP; consumption is less volatile than GDP; investment, consumption and change in stocks are procyclical and coincident variables; employment is procyclical; unemployment rate is anticyclical; firm size distributions are skewed but depart from log-normality; firm growth distributions are tent-shaped. JEL Classifications: C15, C22, C49, E17, E22, E32.     

演化算法的时间复杂性

演化算法在工程领域取得了广泛的应用,但是其基础理论尚未完全建立。文章讨论了演化算法的时间复杂性,提出一个估计(1+1)EA平均计算时间的简单方法,对几个实例的应用显示了该方法分析演化算法计算时间的有效性。     

Analyzing the Simple Ranking and Selection Process for Constrained Evolutionary Optimization

Many optimization problems that involve practical applications have functional constraints,and some of these constraints are active,meaning that they prevent any solution from improving the objective function value to the one that is better than any solution lying beyond the constraint limits.Therefore,the optimal solution usually lies on the boundary of the feasible region.In order to converge faster when solving such problems,a new ranking and selection scheme is introduced which exploits this feature ...     

基于量子进化算法的包装式特征选择方法

针对监督分类中的特征选择问题, 提出一种基于量子进化算法的包装式特征选择方法. 首先分析了现有子集评价方法存在过度偏好分类精度的缺点, 进而提出基于固定阈值和统计检验的两种子集评价方法. 然后改进了量子进化算法的进化策略, 即将整个进化过程分为两个阶段, 分别选用个体极值和全局极值作为种群的进化目标. 在此基础上, 按照包装式特征选择遵循的一般框架设计了特征选择算法. 最后, 通过15个UCI数据集分别验证了子集评价方法和进化策略的有效性, 以及新方法相较于其它6种特征选择方法的优越性. 结果表明, 新方法在80%以上的数据集上取得相似甚至更好的分类精度, 在86.67%的数据集上选择了特征个数更小的子集.     

特征选择稳定性研究综述

随着大数据的发展和机器学习的广泛应用,各行业的数据量呈现大规模的增长,高维性是这些数据的重要特点,采用特征选择对高维数据进行降维是一种预处理方法.特征选择稳定性是其中重要的研究内容,它是指特征选择方法对训练样本的微小扰动具有一定鲁棒性.提高特征选择稳定性有助于发现相关特征,增强特征可信度,进一步降低开销.在回顾现有特征选择稳定性提升方法的基础上对其进行分类,分析比较各类方法的特点和适用范围,总结特征选择稳定性中的相关评估工作,并通过实验剖析其中稳定性度量指标的性能,进而对比四种集成方法的效用,最后讨论当前工作的局限性,指出未来的研究方向.     

混合个体选择机制的多目标进化算法

在多目标进化算法中,如何从后代候选集中选择最优解,显著地影响优化过程.当前,最优解的选择方式主要是基于实际目标值或者代理模型估计目标值.然而,这些选择方式往往是非常耗时或者存在精度差等问题,特别是对于一些实际的复杂优化问题.最近,一些研究人员开始利用有监督分类辅助后代选择,但是这些工作难以准备准确的正例和负例样本,或者存在耗时的参数调整等问题.为了解决这些问题,提出了一种新颖的融合分类与代理的混合个体选择机制,用于从后代候选集中选择最优解.在每一代优化中,首先利用分类器选择优良解;然后设计了一个轻量级的代理模型用于估计优良解的目标值;最后利用这些目标值对优良解进行排序,并选择最优解作为后代解.基于典型的多目标进化算法MOEA/D,利用混合个体选择机制设计了新的算法框架MOEA/D-CS.与当前流行的基于分解多目标进化算法比较,实验结果表明,所提出的算法取得了最好的性能.     

关于进化算法记忆存储方法的探讨

针对进化算法的不同个体表示,分析研究了基于进化个体或其特征的存储表示和基于进化种群的概率记忆存储表示两类存储方法.通过研制分析可以看出,有效的搜索历史记忆存储方法能很好进行数据的存储和管理.如果记忆的存储方法与进化算法的控制过程相配合,则整个进化算法会变得更加有效.     

基于改进轮盘赌策略的交互式演化算法磁

根据轮盘赌策略提出了一种基于改进轮盘赌策略的交互式演化算法（RS-IEA）,并将其应用于求解商业海报的设计上。商业海报的设计问题可建模为一个隐式性能优化问题,传统的优化算法不能直接对该类问题进行求解。由于RS-IEA 算法有用户的参与,它既保留了传统演化算法固有的求解最优化问题的优势,又融入了“人的评价”,能够成功解决该类问题,并获得理想的设计方案。     

演化算法的收敛速率与效率分析

该文讨论了演化算法的收敛速度与效率问题．引入了衡量演化算法收敛快慢的新标准——收敛阶和收敛因子等概念,使用顺序统计方法讨论了收敛阶和收敛因子的计算问题．考虑到演化算法的收敛速度和每代群体的工作量,用收敛阶(或收敛因子)和函数评价次数定义了演化算法的效率．对于常见的球函数模型．推导出(μ,λ)演化策略收敛因子和效率公式．从理论上分析了(μ,λ)演化策略中参数μ,λ的最佳比值．     

演化仿真优化的并行实现及其应用

由于仿真对象的复杂性，一些仿真模型很难用有效的解析函数来表达，同时演化算法不要求优化目标具有连续，可导等特点，因此，演化算法用于仿真优化具有很大的优越性，针对仿真优化这一领域提出了演化仿真优化的概念及其形式化语言描述，并给出了演化仿真优化的算法实现框架，演化仿真优化的模型评估需要大量的计算时间，根据仿真优化的特点，提出主／从模式，粗粒度孤岛仿真优化模型及它在PVM，DCOM下的实现，并给出了两个控制器优化设计的实验，仿真试验的结果表明：对于演化仿真优化来说主／从模式的并行度要高于粗粒度孤岛模型，并得出以下结论，对于演化仿真优化来说仿真模型越复杂，主／从模式的性能越好。