基于博弈论的协同演化算法研究.doc

分类号：密级：编号：U D C：工学博士学位论文基于博弈论的协同演化算法研究博士研究生：侯薇指导教师：印桂生教授学科、专业：计算机应用技术哈尔滨工程大学2014年3月 分类号：密级：编号：U D C：工学博士学位论文基于博弈论的协同演化算法研究博士研究生：侯薇指导教师：印桂生教授学位级别：工学博士学科、专业：计算机应用技术所在单位：计算机科学与技术学院论文提交日期：2013年9月论文答辩日期：2014年3月学位授予单位：哈尔滨工程大学 基于博弈论的协同演化算法研究Classified Index:U.D.C:A Dissertation for the Degree of D.EngResearch on Co-evolutionary Algorithm Based on Game Theory Candidate: Hou WeiSupervisor: Prof. Yin GuishengAcademic Degree Applied for: Doctor of EngineeringSpecialty: Computer Applied TechnologyDate of Submission: September, 2013Date of Oral Examination: March, 2014University: Harbin Engineering University 哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者（签字）：日期：年月日哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文，可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。本论文（在授予学位后即可在授予学位 12个月后解密后）由哈尔滨工程大学送交有关部门进行保存、汇编等。作者（签字）：导师（签字）：日期：年月日年月日 哈尔滨工程大学博士学位论文 基于博弈论的协同演化算法研究摘要协同演化算法是近年来计算智能研究的一个热点，本文将协同演化算法的构建机理进行拓展，将演化算法和博弈论相结合，基于博弈论的混合策略思想来设计新的协同演化算法，对原有的混合策略框架加以改进，将混合变异策略扩展到混合交叉策略，对演化算法的遗传算子、选择算子和搜索机制等提出新的协同策略，建立高效的协同演化模型和算法，并将新的协同演化算法用于函数优化、演化聚类、多议题协商和组合拍卖竞胜标确定问题等优化问题的求解。研究内容主要体现在以下几个方面：（1）在博弈论的混合策略思想的启发下，设计了新的混合策略，将新的变异算子加入到混合策略框架中，并将混合策略扩展到混合交叉策略，提出了基于混合交叉、混合变异策略的新的协同演化算法。所提的算法能够自动进行算子选择，可以在不同的演化阶段动态地利用最有效的算子。算法中同时采用多种进化模式，具有隐含的多子种群特性，新一代种群是在多种进化模式协同作用下产生的。（2）多目标优化问题一直以来都是研究学者们关注的热点，演化多目标优化的领域越来越多地引入了一些具有创新思想的优化框架。基本的演化多目标优化算法在复杂空间上的局部搜索能力较弱，通过引入适当的局部搜索可以保持对于搜索空间探索和开发间的平衡。本文利用基于分解的多目标进化算法框架（ MOEA/D），将混合策略的进化算法用于求解分解后的若干单目标优化子问题，提出了一种带局部搜索的基于分解的多目标混合策略进化算法（LMS-MOEA/D）。算法利用均匀设计的方法产生子问题的聚合权重向量，混合交叉策略能够充分利用不同交叉算子的优势，同时算法针对演化过程收敛的特点，结合局部搜索策略，获得逼近 Pareto前沿的最优解集。（3）针对 FCM中数据点隶属度的计算是影响算法执行效率的主要因素，提出一种新的加速 FCM算法（Accelerated fuzzy c-means, AFCM），用于加速 FCM及基于 FCM的演化聚类算法。AFCM算法采用抽样初始化操作，产生较好的初始聚类中心，对于拥有较大隶属度的数据点，通过一步 k-means操作更新模糊聚类中心，同时仅更新小隶属度来达到加速 FCM算法的目的。为了验证所提出方法的有效性并提高聚类算法的效率，将 AFCM应用于基于演化算法的模糊聚类算法，提出了基于隶属度优化的演化聚类算法。在保持良好的聚类结果前提下，能够减少大规模数据集上聚类算法的计算时间。（4）现实的复杂协商环境中，关于对手的许多信息都是未知的，不利于满足各方的利益需求，甚至难以使协商达成一致。实际的协商系统应该具有有效的学习和决策机 哈尔滨工程大学博士学位论文制，以便从可能变化的协商环境中获得动态的领域知识，本文提出了一种时间依赖的双边多议题优化协商模型，将 Bayesian学习和基于混合策略的演化算法相结合，通过只观察对手的历史报价，所提模型使得协商 agent能够对于对手协商参数的概率分布有更精确的估计（如期限、保留报价和议题权重等），能够适应性地调整让步策略使协商双方都受益，提高了协商的效率和成功率。（5）组合拍卖的竞胜标确定问题（WDP）的计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。本文提出适合于离散空间变异的新的混合变异策略集，并结合自组织优化算法对 WDP问题进行求解，解决优化问题中容易局部收敛，求解速度和精度较低等问题。关键词：协同演化算法；混合策略；模糊演化聚类；优化协商模型；竞胜标确定问题 基于博弈论的协同演化算法研究AbstractCo-evolutionary algorithms are a very active research area of computational intelligencein recent years, this work develops construction mechanism of co-evolutionary algorithms bycombining evolutionary algorithm with game theory, and designs new co-evolutionaryalgorithms based on the idea of mixed strategy in game theory. This work modifies previousmixed strategy framework, adding new mutation operators and extending to crossoveroperation, and proposes co-evolutionary algorithms based on mixed strategy. The algorithmspresent new collaborative strategy for mutation operators, crossover operators, selectionoperator of EA and search mechanisms, and builds efficient co-evolutionary model. Theproposed algorithms is applied to solve the optimization questions, such as functionoptimization, evolutionary clustering, multi-issue negotiation and winner determinationquestion in combinatorial auction. Detail works are listed as below:(1) Inspired by evolutionary game theory, this paper modifies previous mixed strategyframework, adding a new mutation operator and extending to crossover operation, andproposes co-evolutionary algorithms based on mixed crossover and/or mutation strategy. Thenovel algorithms automatically select crossover and/or mutation operators from a given mixedstrategy set, and improve the evolutionary performance by dynamically utilizing the mosteffective operator at different stages of evolution. The algorithms possess potential multiplesub-populations due to different evolution patterns simultaneously, next generation populationis generated under co-operation of various evolution patterns.(2) With the developments of research for multi-objective optimization problem, moreand more novel algorithm frameworks are introduced into the area of multi-objectiveoptimization. Due to slow convergence of basic evolutionary multi-objective optimizationalgorithms in complex space, the local search is introduced to maintain a balance betweenexploration and exploitation. A novel algorithm, called multi-objective mixed strategyevolutionary algorithm with local search, is presented based on the frame of MOEA/D(multi-objective evolutionary algorithm based on decomposition), to solve a set of scalaroptimization sub-problems. The uniform design method is applied to generate the aggregationcoefficient vectors, the mixed strategy can make full use of the advantage of each crossover 哈尔滨工程大学博士学位论文operator, the algorithm combines local search strategy, to approximate the Pareto-optimal set.(3) Though FCM has already been widely used in clustering, its alternative calculation ofthe membership and prototype matrix causes a computational burden for large-scale data sets.An efficient algorithm, called accelerated fuzzy C-means (AFCM), is presented for reducingthe computation time of FCM and FCM-based clustering algorithms. The proposed algorithmworks by sampling initiation to generate better initial cluster centers, and motivated by theobservation that there is the increasing trend for large membership degree values of datapoints at next iteration, updating cluster center using one step k-means for those data pointswith large membership degree values and only updating membership of data points with smallvalues at next iteration.(4) In complex automated negotiations, a challenging issue is how to design effectivelearning mechanisms of agents that can deal with incomplete information and dynamicnegotiation scenarios. In this paper, we present a time dependent, bilateral multi-issueoptimized negotiation model by combining Bayesian learning with evolutionary algorithmbased on mixed strategy. Using the historical offers only, the proposed model enable agents toestimate accurately about the probability distribution of its opponents negotiation parameters(i.e., the deadline, reservation offer, issue weight) and to adjust adaptively concession strategyto benefit two partners to improve the utility and success rate of negotiation agreement.(5) To address computational complexity of winner determination in combinatorialauction, two new co-evolutionary algorithms are developed based on mixed mutation andself-organization optimization for finding high quality solutions quickly. Mixed mutationstrategy can select adaptively mutation operators which are suitable for discrete space.Self-organization optimization makes the search to jump out of local optima. This paperproposes and investigates two ways to combine mixed mutation with self-organizationoptimization, the results of experiment show the effectiveness of the second way thatself-organization optimization is added to mixed mutation strategy set as a pure mutationoperator.Key words：Co-evolutionary algorithm; Mixed strategy; Fuzzy evolutionary clustering;Optimal negotiation model; Winner determination problem 基于博弈论的协同演化算法研究目录第 1章绪论 11.1论文的选题背景及意义 11.2协同演化算法的研究现状 21.2.1竞争型协同演化算法 31.2.2合作型协同演化算法 41.2.3其他类型协同演化算法 51.3协同演化算法的优势和存在的问题 61.4论文主要研究内容和组织结构 61.4.1论文主要内容 61.4.2论文结构安排 8第 2章基于单目标的混合策略协同演化算法 92.1引言 92.2基于博弈论的混合策略102.2.1博弈论和纳什均衡102.2.2博弈论中的混合策略112.2.3基于博弈论的混合变异策略设计进化规划122.3基于混合策略的协同演化算法框架142.3.1混合变异策略集 142.3.2混合交叉策略集 162.3.3混合策略的更新规则 172.3.4基于混合策略的协同演化算法框架 172.4基于混合策略的协同演化算法182.4.1基于混合变异策略的协同演化算法 182.4.2基于混合交叉策略的协同演化算法 192.4.3基于混合交叉或变异策略的协同演化算法192.4.4基于先混合交叉再混合变异策略的协同演化算法202.5实验结果及分析212.6本章小结32第 3章基于分解的多目标混合策略协同演化算法 33 哈尔滨工程大学博士学位论文3.1引言333.2基于分解的多目标进化算法框架343.3基于分解的多目标混合策略协同演化算法 353.3.1均匀设计的权向量 353.3.2混合交叉策略 363.3.3局部搜索策略 363.3.4带局部搜索的基于分解的多目标混合策略协同演化算法373.4实验结果与分析383.4.1测试问题和评价指标 383.4.2 2目标问题上的性能测试393.4.3 3目标（以上）问题上的性能测试 403.4.4复杂问题上的性能测试 413.5本章小结45第 4章基于混合策略的演化模糊聚类算法464.1引言464.2模糊聚类过程分析494.3加速的模糊聚类算法514.4加速的演化模糊聚类算法524.4.1加速的差分演化模糊聚类算法 524.4.2适应性模糊聚类的有效性函数指标 524.4.3加速的混合策略的进化规划模糊聚类算法544.5算法时间复杂度分析554.6实验结果及分析554.6.1经典的 FCM与 AFCM的比较 564.6.2 AFCM与其他改进的高效 FCM算法的比较594.6.3 AFCM应用于基于 DE的模糊聚类的效果 604.6.4 AFCM应用于混合策略进化规划模糊聚类算法的效果 614.7本章小结64第 5章基于 Bayesian学习的适应性优化协商模型655.1引言655.2基于时间依赖的双边多议题的协商框架 66 基于博弈论的协同演化算法研究5.3基于 Bayesian学习的适应性优化协商模型 675.4估计对手效用695.4.1基本定义 695.4.2对手保留报价和协商期限的估计 695.4.3对手保留点的局部优化 715.4.4对手议题权重的估计 725.5基于混合策略进化规划的最优协商策略 735.5.1求解最优报价的约束优化的混合策略进化规划735.5.2产生最优让步策略 745.6实验结果及分析755.7本章小结78第 6章基于混合变异策略和自组织优化的协同演化算法 796.1引言796.2问题描述806.3适合于离散空间求解 WDP的混合变异策略集 816.4混合策略优于纯策略的理论分析816.5自组织优化846.6基于混合变异策略和自组织优化的协同演化算法 876.6.1启发式修复算子 876.6.2基于混合变异策略和自组织优化的演化算法876.7实验结果与分析896.8本章小结94结论 95参考文献 97攻读博士学位期间发表的论文和取得的科研成果 110致谢 111个人简历 112 第 1 章绪论第1 章绪论1.1论文的选题背景及意义演化算法（Evolutionary Algorithms，EAs)是受生物演化过程启发而提出的一种计算智能算法，对求解空间具有自适应性，适用于求解复杂空间的搜索问题和优化问题。自然界的生物进化本质上是一种优化过程。演化计算近年来在许多数值和组合优化问题上已获得了很大的成功，但是，当演化算法应用于大规模、复杂的或高度结构化约束问题时，它们的可扩展性就面临着急迫的挑战。通常，传统 EAs的绩效随着搜索空间维度的增加而急剧恶化；或者当没有内在的目标度量个体适应度时，很难应用 EAs，如博弈策略的演化；或者当搜索空间结构复杂时，如果没有对特定领域的修改，EAs将很难对搜索有直接的帮助。协同演化算法（Co-evolutionary Algorithms，CoEA）与传统的演化算法的起源相同，都是模拟 Darwinian的遗传学和适者生存的思想来求解问题，是近年来计算智能研究的一个热点，协同演化是指在生态上联系非常密切的两个或多个物种，在演化的过程中彼此依赖，当一个物种演化时，物种间的选择压力发生改变，其他物种将对这种改变做出适应性的反应，从而产生物种间高适应性的演化，分为合作型协同演化算法和竞争型协同演化算法。协同演化搜索涉及一个或两个种群，在一个种群的协同演化中，个体的适应度基于种群中个体间的竞争，两个种群的协同演化中，个体的适应度是基于其他种群个体的行为来评价的。为了适应复杂、动态的演化系统环境，个体或种群之间通过建立竞争或合作关系，来演化出最优的种群。近年来，协同演化作为一种启发式算法为许多领域提供了有希望的求解方法1，在很多领域取得了一系列的成功应用，如函数优化、智能控制、数据挖掘、电子商务和工程设计等，CoEA已引起越来越多的学者们的兴趣。博弈论是研究和帮助在互动情形中理性人应当如何做决策的数学理论分支，是利用严谨的数学模型，对具有冲突条件下最优决策问题的理论研究。从博弈者所采用的策略的角度划分，分为非合作博弈理论和合作博弈理论。在 1952年 Nash给出了博弈均衡的定义，给出了博弈均衡存在的证明，奠定了现代非协同博弈论的基础。非合作博弈主要是指博弈的参与方在利益冲突时如何选择策略使得自己的收益最大，强调的是个体理性，根据纳什的理论，每个博弈者都有其自己的策略集和目标函数，在博弈过程中，每个博弈者在其他博弈者博弈策略确定的情况下选择自己的最佳策略；而群体理性是合作1 哈尔滨工程大学博士学位论文博弈所关注的，其核心参与人能够协调他们之间的策略，合作时他们的收益就会实现最大化。目前，博弈论被广泛应用于生态、军事、社会学及金融学等领域来对群体行为的演化过程及其结果进行研究。从博弈论的观点来看，生物进化是一个优化的过程，生物进化过程是否达到稳定状态取决于进化是否达到了一种相对优势的状态，直到下一个进化模式发生，即启动下一次优化。博弈论的中心议题是参与者的相互作用，以及采用的策略。混合策略是指，如果一个策略规定参与人在给定的信息情况下，以某种概率分布随机地选择不同的行动。参与人采取的不是明确唯一的策略，而是其策略空间上的一种概率分布。本课题在博弈论混合策略的启发下，设计基于博弈论混合策略的新的协同演化算法，对演化算法的遗传算子、选择算子和搜索机制等提出新的协同策略，建立高效的协同演化模型和算法，并将新的协同演化算法用于函数优化和演化聚类、多议题协商和组合拍卖竞胜标确定等优化问题的求解，提高其求解的精度和效率，为求解现实中的优化问题提供可靠的理论依据。本课题来源于国家自然科学基金资助项目“基于贝叶斯博弈的协同演化算法及其在交易 Agent中的应用研究”和黑龙江省自然科学基金资助项目“基于博弈论的协同演化算法及其在交易 Agent中的应用研究”。1.2协同演化算法的研究现状当从生态学的观点看起来生物的关系比较密切，就会影响生物彼此间的演化，比如，捕食者与被捕食者，宿主和寄生虫，或昆虫与花间的授粉等，这时我们称协同演化发生了。模拟协同演化行为初始的思想是由 Maynard Smith2和 Axelrod3提出的，协同演化算法（CoEA）就是受这种自然过程的启发而提出的，即在种群中或种群间的个体会受另一种群个体的影响，而发生适应性的改变，不断相互作用，共同演化。交互的个体可以来自同一个种群（如，协同演化双陆棋博弈4，重复囚徒困境5），也可以来自两个或两个以上的种群（如，协同演化捕食者与被捕食者机器人6）。传统的演化算法的个体适应度评价独立于另一个体，是一种绝对的适应度评价，从协同演化算法中个体适应度是与其他个体交互的函数的角度看，协同演化算法中个体的适应度是不固定的，而是耦合的。协同演化算法将一种自然的方法应用于演化计算来优化多种群行为。协同演化算法分为竞争型和合作型，分别模拟共生和寄生现象。竞争的协同演化中交互的个体彼此竞争，而合作的协同演化中个体互相合作。协同演化算法相对于传统的 EA方法来说，有许多特定的优点，已成功应用于许多困难的工程问题中，如无线传感器网络的动态调度，电力市场的均衡分析，金融市场的预测和交易，神经网络的分类学习，超大规模集成电2 第 1 章绪论路布图规划等。由于它们的并行性和个体间交换信息的高效性，这些算法表现出了比标准 EA方法更好的绩效。1.2.1竞争型协同演化算法对 CoEA值得关注的研究始于 1990年 Hillis把捕食现象作为计算模型引入计算科学，从而诞生了竞争型的协同演化算法7，竞争型的方法，不同种群在求解全局问题中竞争，对个体的奖励以与之交互的个体为代价。竞争型协同演化本质上通常用于模拟竞争的行为，如捕食者与被捕食者，对被捕食者来说，存在一个很强的进化压力可以更好地保护自己，而捕食者的下一代会生成更好的进攻策略。竞争的协同演化能够导致军备竞赛，两个种群有相反的利益，一个种群的成功取决于另一个的失败，其思想是某些个体持续的较小适应将会迫使其他个体产生竞争性的适应，这些相互的作用力将驱使算法产生永久增加绩效的个体。个体适应度通过在种群中与其他个体的竞争来评价。换句话说，适应度只显示了解的相对强度；一个解适应度的增加导致另一个解适应度减小。这种倒转的适应度交互会增加每个种群的能力，直到获得全局最优解8