复杂网络在土壤墒情预测中的应用

复杂网络在土壤墒情预测中的应用 学号:2009021284 姓名:马晓慧 :1XXXXXXXXXX Email :iaohui2007@163 所在学院:信息科学与工程 单 位 代 码 10445 学 号 2009021284 分 类 号 TP39 1 研究生类别 全日制 硕 士 学 位 论 文 论文题目 复杂网络在土壤墒情预测中的应用 学科专业名称: 计算机软件与理论 申请人姓名: 马晓慧 指 导 教 师: 王红 教授 论文提交时间: 2012 年6 月15 日 独 创 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 (注:如没有其他需要特别声明的，本 栏可空)或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名: 导师签字: 学位论文版权使用授权书 本学位论文作者完全了解 学校 有关保留、使用学位论文的 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 ，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 学校 可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书) 学位论文作者签名: 导师签字: 签字日期: 年 月 日 签字日期: 年 月 日 I 目 录 摘 要...................................................................... i ABSTRACT.................................................................. iii 第一章 绪 论................................................................ 1 1.1 研究背 景 ............................................................ 1 1.2 研究意 义 ............................................................ 1 1.3 国内外研究现 状...................................................... 2 1.4 主要研究内 容 ........................................................ 3 1.5 创新 点 .............................................................. 4 1.6 组织结 构 ............................................................ 4 1.7 本章小 结 ............................................................ 4 第二章 复杂网络和智能优化算 法.............................................. 5 2.1 复杂网 络 ............................................................ 5 拓扑特 性....................................................... 5 社团结 构....................................................... 7 小世界网络模 型 ................................................. 8 2.2 粒子群算 法.......................................................... 10 速度和位置的更新公 式.......................................... 10 适应度与适应度函 数............................................ 11 流程 图........................................................ 11 伪代 码........................................................ 12 特 点.......................................................... 12 2.3 遗传算 法 ........................................................... 12 基本操 作...................................................... 13 运行参 数...................................................... 13 执行步 骤...................................................... 13 流程 图........................................................ 14 伪代 码........................................................ 14 特 点.......................................................... 15 2.4 本章小 结 ........................................................... 16 第三章 GA-PSO 算法及其在TSP 中的应 用...................................... 17 3.1 TSP 问 题............................................................ 17 3.2 对粒子的位置、速度以及操作重新定 义 ................................. 17 3.3 GA-PSO 算 法......................................................... 18 3.4 实例验 证 ........................................................... 19 3.5 本章小结 ........................................... 错 误～未定义书签。 第四章 智能合作网络模型在墒情预测中的应 用................................. 21 4.1 确定目标函 数 ....................................................... 21 4.2 智能合作网络模 型 ................................................... 21 引入“社区”和“社区极 值”.................................... 21 对惯性权重w 进行更 新.......................................... 22 小世界特性的应 用.............................................. 22 边与权重的应 用................................................ 23 BT 网络的传销性质的应 用....................................... 23 4.3 模型建 立 ........................................................... 25 I 山东师范大学硕士学位论文 4.4 执行步 骤............................................................26 4.5 流程 图..............................................................26 4.6 本章小 结............................................................27 第五章 实验验 证...........................................................28 5.1 仿真实 验............................................................28 5.2 实验结 论............................................................29 5.3 本章小 结............................................................30 第六章 总结与展 望.........................................................31 6.1 本文所做的主要工 作..................................................31 6.2 下一步工作展 望......................................................31 参考文 献................................................................... 32 攻读硕士学位期间的论文发表情 况.............................................35 致 谢................................................................... ..36 II 山东师范大学硕士学位论文 复杂网络在土壤墒情预测中的应用 摘 要 目前，水资源紧缺已成为许多国家或地区农业发展的障碍，在农业生产 中，如何有效 地利用水资源将是各国研究者的重点研究课题。土壤墒情是指土壤的含水量情况，表明了 土壤的水分分布状况。墒情往往会受多种气候条件的影响，例如温度、空气湿度、降雨量、 光照等。墒情预测指的是以当前土壤含水量和与墒情有关的因素为基础，推测土壤水分未 来的变化趋势。通过墒情预测在提高水资源的利用率的同时还可以提高农业抗旱、防旱能 力。随着灌溉技术的飞速发展，我们对土壤墒情监测与预报的研究工作也提出了更高的要 求。如何提高墒情监测和预报的准确性将成为我们面临的重要课题。 以往的墒情预测 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 主要依靠经验推断和理论研究，经验推断法需要的参数少，但是 需要长期的经验积累，并且其理论研究常常需要依靠非常理想的条件和过多的参数，需要 投入大量的人力和物力。如何构建一个具有较好的理论支撑，参数容易获取，而且能快速 投入实际应用的墒情预测模型是我们的研究方向。 在本论文中，我们主要做了以下几方面的工作: 1、首先简要介绍了土壤墒情的研究背景和意义、以及复杂网络、智能算法和墒情预 测的研究现状，进而提出本论文的主题。 2 、重点介绍了复杂网络和BT 网络。首先讲述了复杂网络的拓扑特性，然后仔细 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了复杂网络的小世界特性、社团结构和BT 网络的传销特性。 3、详细介绍了智能优化算法中的两个经典算法，即粒子群算法和遗传算法。 针对智 能算法中存在的问题，本文将遗传算法的思想融入了粒子群算法中，并通过 TSP 问题验证 了二者的结合有一定的意义。 4 、建立智能合作网络模型。此模型的独特之处是它运用了复杂网络中的小世界模型、 社团结构和BT 网络中的传销特性，并且使得三者和智能优化算法进行了结合。 5、详细介绍了智能合作网络模型在墒情预测中的具体执行过程。通过相关实验证明 了此网络模型的有效性。 本文的创新点主要有以下几点: 1、提出了改进的GA-PSO 算法，并通过TSP 问题证明GA 和PSO 的一定结合可以很 好的解决离散性问题。 2 、建立了智能合作网络模型。此模型的原理主要是运用了智能优化算法、复杂网络 中的小世界模型、社团结构和BT 网络等方面的独特优势。 3、建立了智能合作网络模型预测墒情时用到的适应度函数。我们分别利用基本 PSO 算法和智能合作网络模型对墒情预测进行了模拟仿真，实验结果证明，后者获得的墒情值 与实际结果更加吻合。 i 山东师范大学硕士学位论文 关键词:复杂网络;BT 网络;墒情预测;智能优化算法 分类号:TP391 ii 山东师范大学硕士学 位论文 The Application of Complex Network in Soil Moisture Prediction ABSTRACT At present, the shortage of water resources has become the obstacles of agriculture developments in many countries and regions, how to use the water resources more effectively in agriculture production, has become the key research project for the researchers in different countries. Soil moisture, which shows the water distributions of soil, refers to the soil water content; moisture is influenced by various climate conditions, such as temperature, air humidity, rainfall and light. Soil moisture forecast speculates the future trend of the soil moisture, based on current soil moisture and other related factors. Through the moisture prediction, we can improve the utilization ratio of water resources and the ability of drought resistance in agriculture. Along with the rapid development of irrigation technology, new and higher requests of the soil moisture monitor and forecast are also put forward, how to improve the precision and accuracy of soil moisture monitor and forecast has become an important issue that we are faced with. The previous moisture prediction methods relied mainly on experience inference and theoretical research. Experience inference method needs less parameter, but long-term accumulation of experience, while theoretical research method usually needs ideal conditions and too many parameters, requiring a lot of manpower and material resources. How to build a good soil moisture prediction model based on better theoretical support, for which those parameters can be easily obtained, and can be quickly put into practical applications, is our research direction. In this paper, main research works are done as follows: 1. Firstly, we briefly introduced the backgrounds, significances of the soil moisture. Then we did the analysis of the developments of researching the neural network, Swarm Intelligence and the forecast of the soil moisture. At the same time, we put forward the theme of this paper. 2. In this paper, we mainly gave an account of the complex network and BT network. In the first place, we introduced the topological characteristics of the complex network, and then, we analyzed the small world characteristics and the community structure in complex network, as well as, the multi-level marketing properties in BT network. 3. We introduced two classical algorithms of intelligent optimization algorithm in detail. They are the particle swarm algorithm and genetic algorithm. We put the idea of the genetic algorithm to the particle swarm algorithm aiming at the problems we faced in the intelligent optimization algorithm. The experiment verified that the new algorithm can well solve discrete problems by TSP. 4. We also established an intelligent cooperation network model. The unique place of the model is that it uses the small world model, the community structure of complex network and the multi-level marketing properties in BT network. As well, these three factors have a very good show in the new model. 5. We described the application methods of the intelligent cooperation network model in the process of predicting the moisture in detail. The experiments show the effectiveness of this iii 山东师范大学硕士学位 论文 model. The innovations of this paper are mainly as follows: 1. We proposed an improved GA-PSO algorithm, and improved that the improved algorithm can well solve the discrete problems by TSP. 2. We established an intelligent cooperation network model. It mainly use the unique advantages of the small world model, the community structure in complex network and BT network. 3. We established the fitness function in the process of predicting the moisture by the intelligent cooperation network model. We simulated the effect of the two ideas ,which are the standard PSO and the intelligent cooperation network model. The experimental results show that the latter idea is better than the former. Key Words: Complex Network; Bit Torrent Network; Moisture Prediction; Intelligent Optimization Algorithm Classification: TP391 iv 山东师范大学硕士学位论文 第一章 绪论 1.1 研究背景 我国是一个水资源短缺的季风气候国家，这种气候的典型特点是降水分布不均、年际 [1] 之间变化较大，受海陆和地形等各方面因素的影响易造成旱灾频繁 ，特别是对于主要依 靠灌溉农作物才能正常生长的干旱和半干旱地带。建国前，我国的有效灌溉面积很少，70 年代以后，随着农业技术的提高，灌溉为我国的粮食安全和国民经济的发展做出了重大贡 献。水是生命之源，人们的生活离不开水资源。但是在现实生活中经常出现人类对水资源 的滥用等现象，致使水资源危机仍然在不同程度的影响和威胁着世界各地经济的发展和生 态环境系统的安全。如何使水资源得到合理地开发和有效的利用已经成为了当今世界性的 [2] 热点话题之一。解决此问题的一个直接答案就是节约用水 ，因此，节约水资源已成为当 务之急。在所有需要用到水资源的方面中，可以说农业灌溉是一个用水大户。在我国，农 业用水约占水资源总利用量的70% 。 如今，随着全球性气温的普遍升高，干旱已经遍及世界许多国家，其使得全球粮食短 缺、农作物大幅度减产，进而影响经济的正常发展，这已成为当今人类所面临的重大自然 [3] 灾害之一 。近百年来，世界各国的工业、农业等均得到了快速发展。与此同时，人类也 向自然生态系统释放了大量的二氧化碳、甲烷等温室气体，引起全球温度增温，并产生了 十分严重的后果，特别是对各国的农业发展产生深刻的影响。随着这种现象的日趋严重， 干旱越来越成为困扰人类社会正常发展的重大自然灾害之一，全球正面临着不同程度的自 然灾害的威胁。 1.2 研究意义 众所周知，复杂网络是对大量真实复杂系统的一种高度抽象，现已成为国际学术界的 研究热点。复杂网络的研究为我们提供了一种复杂性研究的新视角、新方法，并且提供了 一种比较的视野。网络的现象涵盖极其广泛，科学家发现大多数市级及以上的系统都是复 杂网络，从细胞核蛋白质系统到日常生活中人与人之间的合作，再到大型的 Internet 和 网络等，它们在一定程度上都构成了某种复杂网络系统。复杂网络是研究复杂系统的 一种角度和方法，它关注系统中个体相互关联作用的拓扑结构，是理解复杂系统性质和功 能的基础。 近年来，科学家对复杂网络进行了大量的深入研究。实验表明，只要是复杂网络，在 一定意义上就具有共同特征。因此，如果我们发现了一种能够概括它们的共同特性的观点 或者方法，那么就可以掌握这类网络的关键，进而对各种复杂网络进行多方面的比较、研 究和综合概括。目前，复杂网络研究正逐步渗透到智能优化、生命科学和信息科学等众多 不同的领域。换句话说，这些领域内部都存在着具有复杂的拓扑结构特征的网络结构。因 1 山东师范大学硕士学位论文 此，人们对网络的研究具有重要的研究意义和极大的科研价值，使得复杂网络的特性与其 他领域的优势进行充分的有机结合已成为网络时代科学研究中一个极其重要的挑战性课 题。 若要能够达到节约用水，重点是在用水大户――农业灌溉这一方面做到合理用水。合 理用水离不开对墒情预测的研究。顾名思义，墒情预测即墒情的监测和预报，是灌溉预报 [4] 的基础。墒情预测 是以土壤水分动态模拟模型为基础，对某一区域的土壤水分的增长和 消退程度所进行的预报，它是制定合理的灌溉 制度 关于办公室下班关闭电源制度矿山事故隐患举报和奖励制度制度下载人事管理制度doc盘点制度下载 从而进行适时适量灌水的基础。墒情预 报的关键是掌握田间根系层土壤水分的消退规律。土壤水分消退过程不仅与土壤特性有 关，还涉及到根系层与环境间的水分交换。 通过前期工作，即对土壤水分的监测和墒情预报，我们就可以严格地根据预测结果浇 关键水，进而，使灌溉水得到充分利用，以达到节水高产的目的。因此，区域墒情预报是 农田用水和区域水资源管理的一项基础工作，对于农田灌溉排水的合理实施和提高水资源 的利用率等有着至关重要的作用。这时，使用土壤墒情监测系统对墒情进行一定的监测分 析则是必不可少的。众所周知，在农业生产中，灌溉时间和灌溉水量的控制等都要以农田 土壤墒情与旱情监测数据作为基础，这些实验数据均为抗旱减灾、安全生产等提供了科学 的依据。 1.3 国内外研究现状 在当今电子科技时代，复杂网络这个词对我们来说已经不再陌生。纵观科研学者对复 [5] 杂网络的研究过程，主要是从复杂网络 的拓扑特性、网络建模和动力学机制等方面对其 进行的不同深度的分析。在其发展的起步阶段，科学家们认为网络中各个节点之间的关系 可以用规则的结构表示，例如著名的欧几里德格网。上世纪五十年代末，拓扑特性相对简 单的随机网络诞生，此网络的思想主宰了整个复杂网络长达 40 年之久的研究历程。直至 最近几年，科学家才逐步发现现实生活中有相当一部分的网络既不是规则网络，也不是随 [6] 机网络，而是具有特殊统计性质的网络 。其中影响范围最广且研究价值最高的是小世界 网络和无标度网络。这两种网络的出现使得国内外均掀起了对复杂网络研究的热潮，使得 其应用领域逐渐扩大。其中，我国科研人员提出了局域世界网络模型，并将其与具有加权 性质的无标度网络进行结合，进而构建了加权局域世界网络模型。随后，有些学者使复杂 网络理论与鲁棒自适应控制理论、非线性动力学理论进行了相应的有机结合，在混沌复杂 动态网络和神经网络的复杂动力学行为等方面验证了此方法的有效性。近几年，在复杂网 络的结构负载与网络抗毁性等方面也均做了大量的研究工作，并取得了一定 的科研成果。 [7] 群智能 (Swarm Intelligence，简称SI )一词最早由Beni 和Hackwood 在分子自动机 系统中提出。1999 年，Bonabeau 、Dorigo 和Theraulaz 在《Swarm Intelligence: From Natural to Artificial Systems》中对群智能进行了详细的论述和分析。随后，James Kennedy 和Russell [7] C.Eberhart 在2001 年出版了《Swarm Intelligence》 ，这是群智能发展的一个重要历程碑。 近些年，大量研究证明群智能方法是一种可以有效解决大多数优化问题的新方法。SI 的两 2 山东师范大学硕士学位论文 个典型特点是并行性和分布式，其优越性在优化过程中得到了充分的体现。但由于SI 是源 于对生物群落的模拟，因此其相关数学分析还比较薄弱。目前，科学家对SI 的研究主要侧 重点是其理论基础、适用范围和系统框架构建等。随着科学技术的发展，实际应用中接触 到的大型数据库日益增多，且其关系越来越复杂，可以说SI 将具有重要的研究意义。 我国土壤监测工作始于二十世纪五十年代中期，七十年代才开始较为对墒情预报(即 土壤含水量)进行较为专业化的研究。如曹志斌等研究了时段末土壤含水量与时段初土壤 [8] 含水量及降水量的相关关系，土壤水分消退系数与土壤含水量、月份之间的相关关系 。 八十年代，康绍忠研究了应用初始土壤含水量、参考作物蒸发蒸腾量和叶面积指数估算出 时段末土壤含水量的水量平衡模型以及用饱和差、气温、降雨等因子建立了预报土壤含水 量的经验模型。九十年代以来，罗长寿等分别考虑土壤水分变化的随机性特点，用随机模 [9] 拟方法探讨了有较长时段土壤含水量实测资料时土壤含水量的预报方法 。刘洪斌等分析 了利用神经网络进行时间序列预测的方法及其基本工作原理，并利用神经网络建立了土壤 [9] 含水量预报模型 。从形式上看，这些方法大多都能估算出某一时期末的墒情，但它们也 各有优缺点。有的预测方法中涉及到的变量可以直接通过测量得出，较为方便，但往往计 算出的预测值与实际结果相差甚远，即有较大的误差;有的虽然可以得到较为准确的公式， 但需要大量的时间和长期积累的数据。 随着智能算法的发展，群智能在求最优解方面显示出独特的优势。在经验公式法中， 我们只要确定了经验系数的最优解或者较优解，即可较为准确地预测某一地域的墒情。由 于群智能中的粒子数目往往能够达到成百上千，这样若从整个群体来分析则效率明显很 低，而复杂网络中的规模一般较大，并且具有网络进化、节点多样性、连接多样性和社团 结构等特性，所以在分析其具体拓扑结构上具有很大的优势。近些年，许多学者开始利用 神经网络和最大误差学习法等基本工作原理，对墒情预测做出了巨大贡献。在此，我们通 过在复杂网络和 BT 网络性质的基础上加上一定的智能算法，建立新的网络模型来解决这 一难题，这是本文中我们的主要研究问题。 1.4 主要研究内容 1、首先简要介绍了土壤墒情的研究背景和意义、以及复杂网络、智能算法和墒情预 测的研究现状，进而提出本论文的主题。 2 、重点介绍了复杂网络和BT 网络。首先讲述了复杂网络的拓扑特性， 然后仔细分析 了复杂网络的小世界特性、社团结构和BT 网络的传销特性。 3、详细介绍了智能优化算法中的两个经典算法，即粒子群算法和遗传算法。 针对智 能算法中存在的问题，本文将遗传算法的思想融入了粒子群算法中，并通过TSP 问题验证 了二者的结合有一定的意义。 4 、建立智能合作网络模型。此模型的独特之处是它运用了复杂网络中的小世界模型、 社团结构和BT 网络中的传销特性，并且使得三者和智能优化算法进行了结合。 5、详细介绍了智能合作网络模型在墒情预测中的具体执行过程。通过相关实验证明 3 山东师范大学硕士学位论文 了此网络模型的有效性。 1.5 创新点 1、提出了改进的GA-PSO 算法，并通过TSP 问题证明GA 和PSO 的一定结合可以很 好的解决离散性问题。 2 、建立了智能合作网络模型。此模型的原理主要是运用了智能优化算法、复杂网络 中的小世界模型、社团结构和BT 网络等方面的独特优势。 3、建立了智能合作网络模型预测墒情时用到的适应度函数。我们分别利用基本 PSO 算法和智能合作网络模型对墒情预测进行了模拟仿真，实验结果证明，后者 获得的墒情值 与实际结果更加吻合。 1.6 组织结构 本文的组织结构如下: 第一章，绪论。主要介绍了研究背景、墒情的研究现状、常用的墒情预测方法以及本 文研究的主要内容和创新点。 第二章，复杂网络和智能优化算法。首先详细介绍了复杂网络的拓扑特性、小世界网 络模型、社团结构，其次分析了两种经典的智能优化算法，即粒子群算法和遗传算法的基 本原理。 第三章，GA-PSO 算法及其在TSP 中的应用。这一章首先描述了改进的 GA-PSO 算法 的基本原理，然后通过其在具有代表性的离散数学问题――旅行商问题中的实际应用，验 证了此改进算法的有效性。 第四章，智能合作网络模型在墒情预测中的应用。本章我们在智能算法中各个粒子的 合作关系的基础上，把复杂网络的社团特性、小世界网络特性和BT 网络的传销特性加入 了GA-PSO 中，得到了一种新的网络模型，我们称之为智能合作网络模型。这个过程中， 我们通过delta 法则对速度更新公式中的惯性权重做了一定的改进。 第五章，实验验证。首先选取相关实验数据，分别用基本PSO 模型和智能合作网络模 型计算墒情，然后绘制了相关折线图，并对它们的拟合度进行比较，最后得 出实验结论。 第六章，总结与展望。本章主要概况了已经完成的工作以及对下一步工作的展望。 1.7 本章小结 本章首先分析了整篇论文的研究背景、意义、研究现状。其次，重点叙述了本文 的研究内容和创新点。最后，从组织结构角度对文章的内容进行了详细的描述。 4 山东师范大学硕士学位论文 第二章 复杂网络和智能优化算法 2.1 复杂网络 简而言之，复杂网络即呈现高度复杂性的网络。在网络理论的研究中， 复杂网络是有 数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构。用数学的语言来说，就 [10] 是一个有着足够复杂的拓扑结构特征的图 。现实世界中包含着各种类型的复杂网络，如 技术网络、社会网络、生物网络等。这种网络结构的形式既不是完全规则，也不是完全随 机的。 复杂网络有多种网络拓扑模型，例如规则网络模型、随机网络模型等。其中最著名也 [11] 是最有影响力的两类复杂网络模型是小世界 (small-world )网络与无标度(scale-free ) [12,13] 网络 。前者的特性是度分布的幂定律递减，后者的特性则是短特征路径长度与高集聚 系数。 拓扑特性 (1)平均路径长度 average path length 在网络中，最短路径是指从始点到终点的所有路径中总权最小的一条路径。两个节点 i j dij 和 之间的距离 定义为连接着两个节点的最短路径上的边数。任意两个节点间的距离 的最大值称为网络直径(diameter )，记为D ，即: D d (2-1) ij i, j 网络的平均路径长度L[14]是指所有点对之间的最短路径的算术平均 值，这是网络的全 局特征，其公式为: 1 l 1 ?dij N N ?1 i?j 2 (2-2 ) 其中，N 表示网络节点数，平均最短路径描述了节点之间的平均距离， 同时也反映了 网络的尺寸，因此也称为网络的特征路径长度。一个含有N 个节点和M 条边的网络的平 均路径长度可以用时间级为O MN 的广度优先搜索 BFS 算法来确定。 (2 )聚类系数 clustering coefficient 假设某个节点有k 条边，则这k 条边连接的节点(k 个)之间最多可能存在的边的个 数为k k ?1 2 ，用实际存在的边数除以最多可能存在的边数所得到的分数值，定义为这个 ? ? 节点的聚类系数Ci [15]，也称为簇系数，即 2E C i (2-3 ) i k k ?1 ? i ? i 5 山东师范大学硕士学位论文 网络的集聚系数C 是指此网络中所有节点的集聚系数的平均值，它反映的是网络的局 部特征。映射到日常生活的人际关系网中，其表示该节点的朋友之间也是朋友的程度。从 网络的形成结构方面分析，它描述了网络中开始的各个孤立的点逐步集结成团的过程。当 C 0 时其表示目前网络中所有的节点均是孤立节点，即所有节点间没有任何 连接边;当C 1 时，整个网络是全局耦合的，即网络中任意的两个节点都是直接相连的。对 于一个含有N 个节点的完全随机的网络，聚集系数可以通过C O N?1 公式计算得到，它们在某种程度 上具有类似于社会人际关系网络中“物以类聚，人以群分”的特性。 对于节点间的边数K 的值较大的最近邻耦合网络来说，其聚类系数为: 3 K ?2 3 C (2-4 ) 4 K ?1 4 由此可以说明，这类网络具有高度聚类特性。 (3 )度与度分布 degree and degree distribution i [16] 网络中节点 的度ki 定义为与该节点相连接的边的数目。网络中节点的度分布是复 杂网络的一个重要属性，它是指一个随机选定的节点与网络中其它 k 个节点连接的概率 P k 。它反映出了网络中度为k 的节点的概率P k 随节点度k 的变化规律。下面我们以随 [17] 机网络模型 为例介绍度分布这个概念。 Erd?s 和Rényi 于1959 年提出了具有N 个结点和K 条连线的一个随机图模型，现在称 此为ER 随机图。其构造过程如下，开始假定有N 个互不连通的结点，随机地选取两个结 点用一条连线把它们连接起来(两个节点之间的连边最多为1)，一直到做完K 条连线。虽 然其中的节点之间的连接是随机的，但绝大部分节点的连接数目呈现大致相同的特点，也 [18] 就是说，此类网络中节点的分布基本符合钟形的泊松分布 ，即有一个特征性的“平均数”。 由于随机网络的这个特点，也被人们称为指数网络。下面我们对ER 随机图的度分布做进 i k k [19] 一步分析，网络中节点 的度 i 的概率是服从二项式分布 的，即 k k N1 k p k i k C N ?1p ?1p 。由于在此类网络中所取的各个结点在数学 的统计意义下均是 等价的，所以它们都具有上述相同性质的二项式分布特点。因此当N ?? 时，二项式分布 可以化为: k k N 1 k N ?1 ! k N 1 k p k i k C N ?1p 1?p p 1p k ! N ?1?k ! k k 1 N k N 1 k Np ?p ?p N 1 k ? p 1?p 1p (2-5 ) k ! k ! Np k ?pN ?k ?k k ? ? e e k ! k ! 我们可以近似地认为度分布服从Poisson 分布，如图 2-1 所示。 6 山东师范大学硕士学位论文 图2-1 随机网络的节点度服从泊松分布 (4 )介数 betweenness centrality [20] 介数 一般可以分为边介数和节点介数两类。节点介数是指网络中所有 最短路径中经 过该节点的路径的数目占最短路径总数的比例，它反映了节点的影响力，各种交通枢纽都 是介数较大的节点。 边介数是指网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。它 反映了该边在其所在的整个网络中的作用和影响力，并且可以用来分析顶点的聚类，这对 于在现实网络中发现和保护关键资源具有重要意义。Goh 等人曾做过相关研究，结果表明 介数遵循一定的幂律分布。 社团结构 大量实证研究表明，许多网络是异构的，即复杂网络不是大批性质相同的节点的随机 连接，而是许多类型的节点的一种组合。其中一个重要的特点是相同类型的节点存在较多 的连接，而不同类型节点的连接则相对较少。我们把同一类型节点以及这些节点之间的边 [21] 所构成的子图称为网络中的社团 。社团结构是反映网络结构整体性质的重要特征，对于 了解网络结构和网络特性都非常重要。 (1)定义 研究社团结构 Community structure 首先最重要的问题就是如何精确的定义什么是一 个社团，社会网络学家根据各种各样节点之间内部联系的度给出了子群，即社团的很多定 [22] 义。还有一些定义 是由计算机学家和物理学家所提出的。总体来说，这些定义可以分为 三种主要的类型。 首先是局部定义:这一类定义主要是集中关注所研究中的子图的顶点以及与它们直接 相邻的邻居节点，而不考虑图的其他部分。如派系的定义，就是一个圈耦合的最大子图， 即其中一个节点和其他所有的节点都相邻。 其次是全局定义:通常是从一个空模型开始，将原始图中的子图的连接特性与相对应 的空模型中的子图进行比较，当子集中边的数目超过了空模型中所预测的边数时，这些顶 7 山东师范大学硕士学位论文 点的子集就构成了一个社团。 最后是基于顶点相似性的定义:社团是由一组有着相似性的顶点所构成的，不论它们 是否相连接，均可给出定量的判据来评价每一对节点之间的相似性。 尽管有各种各样的定义，但在很多寻找社团结构的算法中，并没有给出社团的精确定 义，其仅仅是整个算法在分析具体网络时所得到的一个结果而已。 (2 )层次性 网络中的节点可能具有不同层次的组织结构，比如大的社团内部可能包含较小规模的 社团，而这些小社团还可能包含其他更小规模的社团，以此类推。在这种情况下，就称此 [23] 网络具有层次性 。一种最简单体现网络层次性结构的方法就是画出该网络所对应的系统 [24] 树图 。在最底层，每一个节点就看作一个社团，节点不断聚合从而形成较大规模的社团， 最顶层则表示将整个网络看作一个大的社团。而每一个低层次的社团都被完全包含在高一 层的社团当中。系统树图在生物学和社会学中应用较广泛，其系统结构如图(2-2 )所示。 图2-2 社团结构的层次性 小世界网络模型 为了描述从一个局部有序系统到一个随机网络的变化过程，科学家 Watts 和 Strogatz 于1998 年在杂志《Nature 》中提出了构造小世界网络结构的方法，后来，人们通常称此模 [25] 型为WS 小世界模型 。WS 小世界模型始于规则图，即使得一维最近邻耦合网络中的各 个节点与其左右相邻的各K/2 节点相连，K 是偶数。然后，每个节点又以概率p 随机地连 接此网络中的其他节点，即将边的一个端点保持不变，而在网络中其他节点中随机选择一 [26] 个作为这条边的另一个端点 。其中规定节点间无重边，且无自环，其结构如图(2-3 )所 示。 8 山东师范大学硕士学位论文 图2-3 WS 小世界模型 当重连概率p 为1 时，此网络是完全随机网络，概率p 等于0 时，此网络将成为完全 规则网络。其中，复杂网络由完全规则网络转化为完全随机网络可以通过调节重连概率 p 的值来间接控制。当概率p 较小时(0 p 1 )，此网络有下面这两个特点。首先，重新连 线后得到的网络的平均路径长度下降很快，此性质类似于随机网络;其次，它的聚类系数 依旧相当高，这个性质又相似于规则网络。针对这种具有较短的平均路径长度又具有较高 的聚类系数的特殊性质的网络，我们把它单独列出来，并称为小世界网络。小世界网络的 判定准则主要有两个，分别是特征路径长度短和高集聚系数。下面我们具体分析一下小世 [27] 界网络的三个基本拓扑特性 。 (1)平均路径长度 目前，人类还没有研究出可以精确求解WS 小世界模型的平均路径长度L 的表达式， 不过可以利用重正化群方法得到如下公式。 2N L p f NK p / 2 (2-6 ) 1 K 1 其中， 是此网络的节点总数， 是与此节点左右相邻的节点的总数，f u 是一个 N K 1 普适标度函数，它的取值情况为: constant for u 1 f u (2-7 ) ? ? ? lnu / u for u 1 ? (2 )聚类系数 WS 小世界模型的集聚系数可以用公式(2-8 )计算。 3 k ?2 C p ? ? 1p 3 (2-8 ) ? ? ? ? 4 k ?1 ? ? (3 )度分布 [28] 在WS 小世界模型中，当k ?K 2 时，其度分布可以用公式(2-9 )计 算 。 2m m ?1 ? ? 2 ?3 (2-9 ) p k 2m k ? ? k k ?1 k ?2 ? ? 9 山东师范大学硕士学位论文 2.2 粒子群算法 [29] 智能计算 是人们从生物界得到启发，根据其原理进行模仿求解相关问题的一种算 法。优化是一种在合理的时间范围限制下为一个优化问题寻找最优可行解的过程。在优化 领域，由于智能计算的构造具有自然机制和一定的直观性，因而通常被称为智能优化算法 (intelligent optimization algorithms )。这类算法进行时均从经验范围内的任一初始解出发， 然后按照相应的优化机制，逐步探索最优解。由于它们具有分布式、鲁棒性等特点，且可 以把搜索空间扩展到整个问题空间，所以，它们同时也具有全局优化的性能。智能优化算 法来源于对生物群落社会性的模拟，设置参数的初始解时并没有明确的理论依据，并且其 数学分析相对比较薄弱，我们需要对其进行深入研究。 随着科技的飞速发展，智能计算的应用也逐步扩大到各个研究领域。智能优化技术给 我们人类开辟了一个全新的研究领域，同时，也给我们留下了许多很有意义的思考问题的 方法。从目前的研究现状我们可以推测，智能计算将有很广的发展空间，它将在越来越多 的领域获得重要成就，让我们一起拭目以待。粒子群算法(Particle Swarm Optimization [30] algorithm，PSO )由Kennedy 和Eberhart 于1995 年提出 ，源于对鸟群捕食的行为研究。 它的基本原理是在群体搜寻最优目标时，每个个体将参照当前群体中的最优个体，和自身 曾经达到的最优位置来调整下一步的搜寻方向，即通过跟踪“个体极值 pbest ”和“全局 [31] 极值(gbest )”来更新自己的位置 ，以便向更好的位置“飞行”，通过反复学习，直到发 现最优解。 速度和位置的更新公式 [32] [33] 为改善算法的收敛性能 ，Kennedy 和Eberhart 在 1998 年引入了惯 性权重 和压缩 [34] 因子 (constriction factor )的概念，将速度 V 和位置 X 更新公式更 改为: Vd t ?1 wVd t c r pBestd ?Xd t ?c r gBestd ?Xd t (2-10) i ? ? i ? ? 1 1 ? i i ? 2 2 ? i ? X d t ?1 X d t nV d t (2-11) i ? ? i ? ? i ? ? 2 n ， f c 1 c 2 (2-12) 2 ?f ? f 2 ?4f 其中， 表示粒子个数， 表示需要优化的参数个数， 和 是伪随机数， 服从 0,1 i d r r 1 2 上的均匀分布。惯量权重w 的大小决定了对粒子当前速度继承的多少，学 习因子 和 分 c c 1 2 别是“认知”加速常数和“社会”加速常数，大量实验表明，c1 c2 2.0 时往往具有很好 的收敛效果。 速度更新公式一般由以下三部分组成: ?惯性部分:表示粒子对自身运动状态的信任，其前面经常带有一个权值，即惯性权 重，它的大小决定了粒子对自身的信任达到的程度。 ?认知部分(cognition ):表示粒子对自身的思考与总结，也是对自身经验的认定。 10 山东师范大学硕士学位论文 ?社会部分(social ):表示粒子间需要进行一定的信息共享，来源于整个群体中优秀 粒子的经验。 适应度与适应度函数 [35] (1)适应度 (fitness ):又称为适应值，它是衡量一个生物个体存活和生殖机会的尺 度，也是表征生物个体优劣的一种指标。 (2 )适应度函数(fitness function ):指涉及此问题的全体个体与其适应度之间的一个 对应关系。这个关系一般可以用数学方面的一个实值函数表示，该函数有一定的指导作用， 它是智能算法中带领整个群体搜索其内部更优粒子的评价函数。 流程图 开 始 在经验范围内随机初始化每个粒子 评估每个粒子并得到最优 是 满足结束条件 否 更新每个粒子的速度和位置 评估每个粒子的函数适应 更新每个粒子的历史最优位置 更新整个群体的历史最优位置 结 束 图2-4 PSO 算法流程图 11 山东师范大学硕士学位论文 伪代码 初始化粒子群; do for 每个粒子 计算其适应度; if (适应度优于粒子个体最优值) 用x 更新历史最优个体p ; i i end 选取当前粒子群中最优粒子; if (当前最优粒子优于群体的全局最优粒子) 用当前群最优粒子更新p ; g for 每个粒子 按公式(2-10 )更新粒子的速度; 按公式(2-11)更新粒子的位置; end while 未达到最大迭代数或者最小误差。 特点 PSO 智能算法具有原理简单、可记忆性和并行性等优势，所以人们经常 用它来处理多 [36] 目标优化问题。但PSO 搜索精度不高 ，粒子寻优时由于过分集中而陷入到局部最优解中， [37] 结果导致算法“早熟”，因此，PSO 不能用于多模态函数优化 。同时，求解带离散变量 的优化问题时需要对离散变量的取整，这样往往会导致较大的误差。为了使PSO 能够适应 更多的运算环境，人们相继提出了多种改进的PSO 算法。 2.3 遗传算法 [38] 遗传算法 (Genetic Algorithm，GA )是由美国Michigan 大学的J.Holland 教授于1975 年首先提出的一种随机化搜索算法，它主要借鉴了生物界的自然选择(达尔 文)和自然遗 传机制(Mendel )，又被称为 GA 算法。遗传算法是一个用数码串的数码位来表示生物中 [39] 的每个染色体，进而通过选择、交叉和基因突变现象为基础模拟生物体进化的过程 。它 通过每个粒子的适应度函数值来表示相应染色体的优与劣。这样，通过粒子的多次迭代和 相应种群的“更新换代”，提高了每代种群的平均适应度。适应度函数可以确定整个种群 [40] 的进化方向，使得群体中的所有粒子能够以更快地步速接近全局最优解 。 12 山东师范大学硕士学位论文 基本操作 (1)编码:在求解问题之前首先需要将问题的解编码成字符串的形式， 这种前提之 [41] 下我们才能使用遗传算法。普遍使用的一种编码方式是二进制编码 ，即将 问题的解写成 二进制位串的形式，即位串中的每一位均用0 或者1 表示，主要原因是便 于用交叉和变异 等遗传算子来操作。评价某一种编码策略的优与劣时经常使用完备性 completeness 、健 [42] 全性 soundness 和非冗余性 nonredundancy 这三项指标 。 (2 )选择:指在遗传算法空间中选择某一部分染色体来产生下一代。常用的选择策 略是 “比例选择”策略，即 “轮盘赌算法”(Roulette Wheel Selection ，该策略中个体被选 中的概率与其适应度函数值成正比。 (3 )交叉 Crossover :指从两个双亲串通过复制选定位而产生两个新的后代，后代的 每一位的信息必定是来自其某一双亲中相对应的那一位。交叉算子的主要任务是对群体内 现有的信息进行重组，以便发现更优的个体。 (4 )变异 Mutation :指从双亲中的一方出发，使其产生后代，对位串只做一些随机 的小变化。此操作的具体方法是选取位串中的某一个位，然后对其取反即可。 变异算子能 够给群体带来新的遗传基因，弥补了由于选择操作而失去的个体多样性的缺陷。 (5 )确定适应度函数 Fitness Function :这类函数主要用于评价某一染色体的适应 度，常用f x 表示，它的确定在一定程度上取决所求问题的目标。 运行参数 [43] GA 算法可以用一个7 元组 来表示，即: GA , M, F, s, c, m, P , P c m ? M――群体大小; ? F――个体适应度评价函数; ? s――选择操作算子; ? c――交叉操作算子; ? m――变异操作算子; ? P ――交叉概率; c ? Pm――变异概率。 执行步骤 (1) 初始化须提前设定好的运行参数，即种群规模 M ，终止迭代次数 T， 交叉概率 Pc 和变异概率Pm ; (2 ) 按照问题的特点随机产生一个初始种群S S , S , „, S ，置迭代次数计数器m 为 1 2 M 1; 13 山东师范大学硕士学位论文 (3 ) 用适应度函数值F 计算每一个体的适应度函数值; (4 ) 若满足终止条件，则算法结束，反之继续执行(5 ); (5 ) 产生新一代种群:重复执行(6 )(7 )(8 )，直至新的种群建立起来; (6 ) 选择:按照一定的原则，根据每个个体的适应度函数值选择其中两个作为父代个体; (7 ) 交叉:以交叉概率P 交叉上一步所选择的两个父代个体 的基因，从而产生子代S ; c 2 (8 ) 变异:以变异概率Pm 从子代S2 中选定m 个染色体，分别对它们进行变异操作，产 生新的群体S ; 3 (9 ) 计算新得到的子代的适应度函数值，将新产生的子代放到新的种群中，判断其是否 满足迭代结束条件，否则转到(3 )。 流程图 确定实际问题参数集 对参数集进行编码 初始化群体 1、位串解码的参数 产生新一代群体 2 、计算目标函数 3 、函数值映射到适应 值 评价群体 4 、适应值调整 是 满足停止规则 结束 三个基本算子: 否 1、选择 2 、交叉 遗传操作 3、变异 图2-5 遗传算法流程图 伪代码 /* *P :交叉发生的概率 c *Pm :变异发生的概率 *M:种群规模 14 山东师范大学硕士学位论文 *F i :适应度函数 *G:终止进化的代数 *T :最初设置的合格粒子所需达到的适应度函数值。进化产生 的任何一个个体的适应度函数 f 一旦超过T ，则可以终止进化过程。 f */ 初始化P 、P 、M 、G、T 等参数，并随机产生第一代种群Pop 。 m c f repeat 计算Pop 中每个个体的适应度F i ; 初始化空种群newPop; repeat 根据F i 以比例选择算法从种群Pop 中选出两个个体; if (random (0,1 ) P ) c 对两个个体按交叉概率P 执行交叉操作; c if (random (0,1 ) Pm ) 对两个个体按交叉概率Pc 执行交叉操作; 将两个新个体加入种群newPop 中; until (M 个子代被创建) 用newPop 取代Pop ; until (任何染色体得分超过T ，或繁殖代数超过G ) f 特点 [44] GA 算法具有自组织、自学习性和并行性 ，较适合于全局搜索，多数 情况下能从离 散、多极值化等问题中找到全局最优解。但GA 毕竟是一种对种群基于概率 的启发式随机 [45] 搜索方法，所以也有一定的缺陷。此算法不适于局部寻优 ，且在寻优后期， 对群体的搜 索效果和速度方面都较差。若GA 中的参数设置地不妥当，则很可能会出现 我们所不希望 得到的“早熟收敛”等现象。 凭借遗传优化方法具有强有力的随机搜索能力及其应用的普及化，GA 已被广泛应用 [46] 于许多领域 ，可以说GA 是目前影响最为广泛的进化计算方法之一。例如，规划、调度 [47,48] [49] [50] (如作业车间调度、运输问题)、组合优化 (如TSP )、函数极值 以及图像 、信号 处理等。 15 山东师范大学硕士学位论文 2.4 本章小结 本章重点分析了复杂网络的重要拓扑特性，并详细讲述了社团结构、小世界网络模型。 然后介绍了两种经典的智能优化算法，即粒子群算法(PSO )和遗传算法 GA ，主要包括 它们的基本原理、算法流程、伪代码和特点等。 16 山东师范大学硕士学位论文 第三章 GA-PSO 算法及其在TSP 中的应用 3.1 TSP 问题 [51] [52-53] [54] 基本 PSO 易陷入局部最优，且处理多元方程组 、非线性方程组 、离散问题 时经常无能为力，鉴于这些缺点出现了许多改进版本的PSO 。例如，合作粒子群、PSO 和 GA[55-60] 、PSO 和人工神经网络等的结合。本章节我们将以基于GA 思想的PSO(即GA-PSO 算法)解决旅行商问题(即TSP，Traveling Salesman Problem )为例介绍此改进算法机制 的实际应用。 [61] 旅行商问题 也被称之为Hamilton 回路问题，与它相对应的就是我们现实生活中经常 提到的邮递员路径问题，在运筹学、图论和组合优化中，它是一个相当经典的NP 难问题， 许多科学家都曾经对其进行过不同广度和深度的研究。此问题的描述如下:已知有n 座城 市及各城市间的相对距离，一个旅行商 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 从现在所在的城市到其他城市推销某一商品。 整个过程中有一定的游戏规则:即需要访问完所有城市，且对于每个城市当且仅能访问一 次，最后返回至起始点。此游戏所研究的问题是旅行商若要完成这个重要任务，他应该如 何安排他的旅行程序，即每个城市的访问次序，并且使得他所走的旅行路线的总距离最短。 TSP 的实质是求出一条通过已知图中的所有顶点，且每个顶点只能被访问一次的具有最短 距离的Hamilton 回路。 3.2 对粒子的位置、速度以及操作重新定义 (1)位置 它可以定义为一个具有所有节点的哈密尔顿圈，设一共有N 个节点，它们之间有一定 的边，粒子的位置可表示为序列x ?n ,n ,...,n ,n ?。 1 2 N 1 (2 )速度 在TSP 问题中，此概念可以定义为在求解过程中，粒子群的每个个体 的位置需要进行 变换这一动作的集合。这个集合可以被表示成是一个有序列表，列表中有一 组置换序列， 它可以用公式(3-1)表示为: v i , j , i , j 1, 2, N, k,? 1,2 ,m , ? ? ? ? k k k k (3-1) 其中，i 和j 代表群体中的不同的两个粒子，m 表示这一个动作集合 中所包含的交换操 作的数目。在整个交换序列中要先执行第一个交换子，再执行第二个交换子，然后以此类 推，直至所有交换子执行完毕。 (3 )粒子的位置与速度的加法操作 这种操作的意思是将一组有序的置换序列从前到后依次作用于群体中处于的某一具 体位置的粒子，执行完毕后使得该粒子产生一个新的相对位置。例如，某一粒子的初始位 17 山东师范大学硕士学位论文 置为 x 1,8,6,5,2,1 ，现在对其进行一个速度操作，若此速度为 v 5,2 , 3,2 ，则此粒子 的初始位置 x 与这个速度 v 进行加法运算后的结果将是粒子在该群体中的一个新位置 x 1,6,2,5,8,1 。 (4 )粒子的位置与位置的减法操作 这种减法操作实质上是指一组置换序列，只不过它是有这个粒子的终止位置与初始位 置逐步相减后得到的，计算出来的结果，即这个置换序列也称为该粒子的运行速度。例如， 群体中某一个粒子的初始位置 x 1,8,2,5,7,1 ，其终止位置 y 1,2,7,5,8,1 。在此，我们设 其置换序列(即粒子的运行速度v )S S1 S2 ，那么初始位置x 、终止位置y 和置换序列 三者之间就存在这样一个关系，那就是:x+S +S y ，其中 S 5,2 ，S 3,2 ，所以 1 2 1 2 v y-x 5,2 , 3,2 。 (5 )粒子的速度与速度的加法操作 这个操作的运行结果的性质同样也是一个新的置换序列，运算规则相对前面几个操作 要简单的多，它是两个置换序列的并集，这样得到的是一个新的速度。例如，群体中某一 粒子的初始速度 v 1,3 , 4,6 ，而后又有一个速度 v 2,7 。则 该粒子的初始速度 v 1 2 1 与后面的速度v 相加后得到的将是新的置换序列，即v +v 1,3 , 4,6 , 2,7 。当然这些 2 1 2 粒子的编号大小要在整个群体的粒子总体数目的范围之内。 (6 )具体实数与粒子速度的乘法操作 一般而言，具体实数c 是一个范围在 0,1 之间的随机数。设某一粒子 的速度v 为一个 置换序列，这个序列是由m 个已知交换子组成的。实数与速度的乘法操作 的实质即对这个 置换序列进行一定的截取操作，其结果仍然是一个速度，即一个置换序列， 只不过这个新 速度的置换序列的长度发生了一定的变化，序列的长度为对实数c 和交换 子的个数m 相乘 所得到的具体数值进行下取整操作后的结果。例如，v 1,5 , 3,6 , 2,1 , 3,4 , m 7,若 1 c 0.4 ，则实数 c 与粒子速度 v1 的乘法操作的结果是一个拥有新置换序列的速度 v 1,5 , 3,6 。 2 3.3 GA-PSO 算法 基本PSO 中粒子的迭代次数一般过多，并且很多粒子的函数值只是在前面几次迭代中 能够得到更优解，而后连续若干次不再更新，以至于算法的执行效率过低。因此，我们把 GA 思想中的选择操作和PSO 进行结合，当粒子在连续多次未出现更优解时就将其删掉， 然后加入新的初始值的粒子，这样就可以使搜索域扩大，且效率能够得到一定的提高。科 学家对传统的PSO 中的位置公式加入收缩因子后，其效率的确提高了很多， 有效控制了收 [37] 敛的速度 。在此，我们把GA 中的选择操作、收缩因子和基本PSO 相结合， 并将其用在 TSP 问题中。此时，粒子的速度和位置更新公式分别为: k ?1 k k k k k V V m P ?X ?n P ?X i i ? i i ? ? g i ? (3-2 ) X k ?1 X k a ?k V k ?1 i i i (3-3 ) 18 山东师范大学硕士学位论文 在粒子的速度和位置更新公式中，m 与n 均表示粒子的加速常数，一般是在 0,1 区间 内随机取值，它们决定了后面的交换子被用到的数目，即表示粒子的速度置换序列的长度。 m 和n 的值可以通过c*k 下取整得到。经过多次实验研究证明，实数c 的取值范围一般在 0.5,1 时整个群体的寻优效果更好。k 为其代表的粒子的速度交换序列中交换子的总个数。 a 一般在(0.4,0.9 )之间取值，鉴于我们是从对传统PSO 的改进得到的启示，故其一般取 值和前者一样为0.729 。同样，k 为其后交换序列中交换子的总个数。 3.4 实例验证 下面以由六个结点 (分别用?，?，„，?代表)组成的路径为例， 对比上述两种离 散型PSO 方法，两种方法的区别在于后者出现了选择操作和收缩因子，其 他相对应变量的 性质完全相同。 1、假设有 A 、B 、C 三个粒子，各节点之间的距离如表(3-1)所示，它们的位置X 和速度V 的初始值如表(3-2 )所示。 表3-1 各节点间的距离 节点 ? ? ? ? ? ? 5 8 4 10 3 ? 6 3 7 6 ? 2 9 1 ? 5 7 ? 2 表3-2 粒子的X 和V 的初始值