群体智能

“本书内容丰富，富于启发性和思想性，强烈推荐给所有的演进计算研究人员。”

——Genetic Programming and Evolvable'Machines

“这本书极为出色，不愧为PSO和群体智能的最佳参考书：”

——Konstantions E.Parsopoulos 希腊Palras大学

群体智能是发展迅速的人工智能学科领域。通过研究分散、自组织的动物群体和人类社会的智能行为，学者们提出了许多迥异于传统思路的智能算法，很好地解决了不少原来非常棘手的复杂工程问题。与蚁群算法齐名的粒子群优化（particle swarm optimizatiotl，简称PSO）算法就是其中最受瞩目、应用最为广泛的成果之一。

《群体智能》由粒子群优化算法之父撰写，是该领域毋庸置疑的经典著作。作者提出，人类智能来源于社会环境中个体之间的交互，这种智能模型可以有效地应用到人工智能系统中去。书中首先从社会心理学、认知科学和演化计算等多个角度阐述了这种新方法的基础，然后详细说明了应用这些理论和模型所得出的新的计算智能方法——粒子群优化，进而深入地探讨了如何将粒子群优化应用于广泛的工程问题。

《群体智能》的C及ViSLlaI Basic源代码可以在图灵网站《群体智能》网页免费注册下载。

群体智能是通过模拟自然界生物群体行为来实现人工智能的一种方法。《群体智能》综合运用认知科学、社会心理学、人工智能和演化计算等学科知识，提供了一些非常有价值的新见解，并将这些见解加以应用，以解决困难的工程问题。书中首先探讨了基础理论，然后详尽展示如何将这些理论和模型应用于新的计算智能方法(粒子群)中，以适应智能系统的行为，最后描述了应用粒子群优化算法的好处，提供了强有力的优化、学习和问题解决的方法。

《群体智能》主要面向计算机相关学科的高年级本科生或研究生以及相关领域的研究与开发技术人员。

James Kennedy社会心理学家。自1994年起，他一直致力于粒子群算法的研究工作，并与Russell C．Eberhart共同开发了粒子群优化算法。在美国劳工部从事调查方法的研究工作。他在计算机科学和社会科学杂志和学报上发表过许多关于粒子群的论文。

RusselI C．Eberhart　普度大学电子与计算机工程系主任。IEEE会士。与JamesKennedy共同提出了粒子群优化算法。曾任IEEE神经网络委员会的主席。除了本书之外，他还著有《计算智能：从概念到实现》（影印版由人民邮电出版社出版）等。

Yuhui Shi (史玉回)国际计算智能领域专家，现任Joumal ofSwarm Intellgence编委，IEEE CIS群体智能任务组主席，西交利物浦大学电子与电气工程系教授。1992年获东南大学博士学位，先后在美国、韩国、澳大利亚等地从事研究工作，曾任美国电子资讯系统公司专家长达9年。他还是《计算智能：从概念到实现》一书的作者之一。

part one Foundations

chapter one　Models and Concepts of Life and Intelligence　3

The Mechanics of Life and Thought　4

Stochastic Adaptation: Is Anything Ever Really Random"para" label-module="para">

The “Two Great Stochastic Systems”　12

The Game of Life: Emergence in Complex Systems　16

The Game of Life　17

Emergence　18

Cellular Automata and the Edge of Chaos　20

Artificial Life in Computer Programs　26

Intelligence: Good Minds in People and Machines　30

Intelligence in People: The Boring Criterion　30

Intelligence in Machines: The Turing Criterion　32

chapter two　Symbols, Connections, and Optimization by Trial and Error　35

Symbols in Trees and Networks　36

Problem Solving and Optimization　48

A Super-Simple Optimization Problem　49

Three Spaces of Optimization　51

Fitness Landscapes　52

High-Dimensional Cognitive Space and Word Meanings　55

Two Factors of Complexity: NK Landscapes　60

Combinatorial Optimization　64

Binary Optimization　67

Random and Greedy Searches　71

Hill Climbing　72

Simulated Annealing　73

Binary and Gray Coding　74

Step Sizes and Granularity　75

Optimizing with Real Numbers　77

Summary　78

chapter three　On Our Nonexistence as Entities: The Social Organism　81

Views of Evolution　82

Gaia: The Living Earth　83

Differential Selection　86

Our Microscopic Masters"para" label-module="para">

Looking for the Right Zoom Angle　92

Flocks, Herds, Schools, and Swarms: Social Behavior as Optimization　94

Accomplishments of the Social Insects　98

Optimizing with Simulated Ants: Computational Swarm Intelligence　105

Staying Together but Not Colliding: Flocks, Herds, and Schools　109

Robot Societies　115

Shallow Understanding　125

Agency　129

Summary　131

chapter four　Evolutionary Computation Theory and Paradigms　133

Introduction　134

Evolutionary Computation History　134

The Four Areas of Evolutionary Computation　135

Genetic Algorithms　135

Evolutionary Programming　139

Evolution Strategies　140

Genetic Programming　141

Toward Unification　141

Evolutionary Computation Overview　142

EC Paradigm Attributes　142

Implementation　143

Genetic Algorithms　146

An Overview　146

A Simple GA Example Problem　147

A Review of GA Operations　152

Schemata and the Schema Theorem　159

Final Comments on Genetic Algorithms　163

Evolutionary Programming　164

The Evolutionary Programming Procedure　165

Finite State Machine Evolution　166

Function Optimization　169

Final Comments　171

Evolution Strategies　172

Mutation　172

Recombination　174

Selection　175

Genetic Programming　179

Summary　185

chapter five　Humans—Actual, Imagined, and Implied　187

Studying Minds　188

The Fall of the Behaviorist Empire　193

The Cognitive Revolution　195

Bandura’s Social Learning Paradigm　197

Social Psychology　199

Lewin’s Field Theory　200

Norms, Conformity, and Social Influence　202

Sociocognition　205

Simulating Social Influence　206

Paradigm Shifts in Cognitive Science　210

The Evolution of Cooperation　214

Explanatory Coherence　216

Networks in Groups　218

Culture in Theory and Practice　220

Coordination Games　223

The El Farol Problem　226

Sugarscape　229

Tesfatsion’s ACE　232

Picker’s Competing-Norms Model　233

Latané’s Dynamic Social Impact Theory　235

Boyd and Richerson’s Evolutionary Culture Model　240

Memetics　245

Memetic Algorithms　248

Cultural Algorithms　253

Convergence of Basic and Applied Research　254

Culture—and Life without It　255

Summary　258

chapter six　Thinking Is Social　261

Introduction　262

Adaptation on Three Levels　263

The Adaptive Culture Model　263

Axelrod’s Culture Model　265

Experiment One: Similarity in Axelrod’s Model　267

Experiment Two: Optimization of an Arbitrary Function　268

Experiment Three: A Slightly Harder and More Interesting Function　269

Experiment Four: A Hard Function　271

Experiment Five: Parallel Constraint Satisfaction　273

Experiment Six: Symbol Processing　279

Discussion　282

Summary　284

part two　The Particle Swarm and Collective Intelligence

chapter seven　The Particle Swarm　287

Sociocognitive Underpinnings: Evaluate, Compare, and Imitate　288

Evaluate　288

Compare　288

Imitate　289

A Model of Binary Decision　289

Testing the Binary Algorithm with the De Jong Test Suite　297

No Free Lunch　299

Multimodality　302

Minds as Parallel Constraint Satisfaction Networks in Cultures　307

The Particle Swarm in Continuous Numbers　309

The Particle Swarm in Real-Number Space　309

Pseudocode for Particle Swarm Optimization in Continuous Numbers　313

Implementation Issues　314

An Example: Particle Swarm Optimization of Neural Net Weights　314

A Real-World Application　318

The Hybrid Particle Swarm　319

Science as Collaborative Search　320

Emergent Culture, Immergent Intelligence　323

Summary　324

chapter eight　Variations and Comparisons　327

Variations of the Particle Swarm Paradigm　328

Parameter Selection　328

Controlling the Explosion　337

Particle Interactions　342

Neighborhood Topology　343

Substituting Cluster Centers for Previous Bests　347

Adding Selection to Particle Swarms　353

Comparing Inertia Weights and Constriction Factors　354

Asymmetric Initialization　357

Some Thoughts on Variations　359

Are Particle Swarms Really a Kind of Evolutionary Algorithm"para" label-module="para">

Evolution beyond Darwin　362

Selection and Self-Organization　363

Ergodicity: Where Can It Get from Here"para" label-module="para">

Convergence of Evolutionary Computation and Particle Swarms　367

Summary　368

chapter nine　Applications　369

Evolving Neural Networks with Particle Swarms　370

Review of Previous Work　370

Advantages and Disadvantages of Previous Approaches　374

The Particle Swarm Optimization Implementation Used Here　376

Implementing Neural Network Evolution　377

An Example Application　379

Conclusions　381

Human Tremor Analysis　382

Data Acquisition Using Actigraphy　383

Data Preprocessing　385

Analysis with Particle Swarm Optimization　386

Summary　389

Other Applications　389

Computer Numerically Controlled Milling Optimization　389

Ingredient Mix Optimization　391

Reactive Power and Voltage Control　391

Battery Pack State-of-Charge Estimation　391

Summary　392

chapter ten　Implications and Speculations　393

Introduction　394

Assertions　395

Up from Social Learning: Bandura　398

Information and Motivation　399

Vicarious versus Direct Experience　399

The Spread of Influence　400

Machine Adaptation　401

Learning or Adaptation"para" label-module="para">

Cellular Automata　403

Down from Culture　405

Soft Computing　408

Interaction within Small Groups: Group Polarization　409

Informational and Normative Social Influence　411

Self-Esteem　412

Self-Attribution and Social Illusion　414

Summary　419

chapter eleven　And in Conclusion . . .　421

Appendix A Statistics for Swarmers　429

Appendix B Genetic Algorithm Implementation　451

Glossary　457

References　475

Index　497

……2100433B

第1章 群体智能算法概述 1

1.1 群体智能算法的特点 1

1.1.1 智能性 1

1.1.2 隐含本质并行性 2

1.1.3 解的近似性 2

1.2 群体智能算法的计算模式 2

1.2.1 社会协作机制 3

1.2.2 自我适应机制 3

1.2.3 竞争机制 4

1.3 遗传算法 4

1.3.1 标准遗传算法原理 5

1.3.2 编码机制与主要算子 7

1.4 差异演化算法 8

1.5 粒子群算法 10

1.5.1 粒子群算法的原理 10

1.5.2 PSO算法的计算模型 11

1.6 教—学优化算法 13

1.7 顾问引导搜索算法 13

1.8 本章小结 15

参考文献 16

第2章 人工鱼群算法 18

2.1 人工鱼群算法的数学模型 18

2.2 人工鱼群算法的收敛性分析 21

2.2.1 常用距离 21

2.2.2 基于Markfov链技术的收敛性分析 22

2.2.3 基于压缩映射定理的收敛性分析 25

2.3 人工鱼群算法的相关研究 26

2.3.1 参数的改进 27

2.3.2 与其他智能算法的融合 28

2.3.3 其他的改进方法 29

2.4 本章小结 32

参考文献 32

第3章 人工鱼群算法的改进研究 34

3.1 小生境人工鱼群算法 34

3.1.1 小生境技术 34

3.1.2 算法实现 36

3.1.3 算法的收敛性 36

3.1.4 仿真实验与分析 38

3.1.5 结论 40

3.2 自适应人工鱼群算法 40

3.2.1 参数自适应机制 40

3.2.2 算法实现 42

3.2.3 仿真实验与分析 42

3.2.4 结论 44

3.3 基于种群分类的人工鱼群算法 44

3.3.1 种群分类思想及设置 45

3.3.2 算法实现 46

3.3.3 仿真实验与分析 47

3.3.4 结论 50

3.4 混和反向学习人工鱼群算法 50

3.4.1 反向学习 50

3.4.2 佳点集 51

3.4.3 人工鱼群算法的改进机制 51

3.4.4 仿真实验与分析 54

3.4.5 结论 59

3.5 精英竞争人工鱼群算法 59

3.5.1 基于动态随机搜索的精英训练 59

3.5.2 算法实现 60

3.5.3 仿真实验与分析 61

3.5.4 结论 67

3.6 随机游走人工鱼群算法 67

3.6.1 Lévy Flight机制 67

3.6.2 算法改进思想 68

3.6.3 算法实现 69

3.6.4 仿真实验与分析 70

3.6.5 结论 72

3.7 混合群搜索人工鱼群算法 73

3.7.1 标准群搜索优化算法 73

3.7.2 群搜索优化算法的改进 75

3.7.3 混合群搜索人工鱼群算法 77

3.7.4 仿真实验与分析 78

3.7.5 结论 81

3.8 本章小结 81

参考文献 82

第4章 烟花爆炸优化算法及改进 83

4.1 烟花爆炸优化算法 83

4.2 混沌烟花爆炸优化算法 86

4.2.1 混沌搜索算法 86

4.2.2 算法实现 87

4.2.3 仿真实验与分析 87

4.2.4 结论 91

4.3 混合动态搜索烟花爆炸优化算法 91

4.3.1 算法实现 91

4.3.2 仿真实验与分析 92

4.3.3 结论 96

4.4 混合反向学习烟花爆炸优化算法 96

4.4.1 精英反向学习 96

4.4.2 基于模拟退火机制的种群选择 97

4.4.3 算法实现 97

4.4.4 仿真实验与分析 98

4.4.5 结论 102

4.5 随机游走烟花爆炸优化算法 102

4.5.1 基于随机游走机制的变异算子 103

4.5.2 基于Boltzmann 子个体选择 103

4.5.3 算法实现 104

4.5.4 仿真实验与分析 105

4.5.5 结论 109

4.6 本章小结 109

参考文献 109

第5章 群体智能算法的应用 110

5.1 物流配送中的车辆调度问题 110

5.1.1 问题的提出 110

5.1.2 组合优化 111

5.1.3 车辆调度问题的数学模型 111

5.1.4 求解VRP的混合人工鱼群遗传算法 112

5.1.5 仿真实验结果 113

5.2 求解SVM反问题的差异演化算法 113

5.2.1 问题的提出 113

5.2.2 差异演化算法的设计 114

5.2.3 差异演化算法的改进 114

5.2.4 仿真实验结果 116

5.3 求解聚类问题的人工鱼群算法 118

5.3.1 聚类模型 118

5.3.2 算法的设计 119

5.3.3 算法实现 120

5.3.4 仿真实验结果 121

5.4 求解测试用例自动化问题的人工鱼群算法 123

5.4.1 路径测试模型 123

5.4.2 混沌搜索 125

5.4.3 算法的设计 125

5.4.4 仿真实验结果 127

5.5 求解关联规则挖掘的差异演化算法 129

5.5.1 规则挖掘 129

5.5.2 算法的设计 131

5.5.3 仿真实验结果 133

5.6 求解特征选择的人工鱼群算法 136

5.6.1 特征选择 136

5.6.2 算法的设计 136

5.6.3 仿真实验结果 137

5.7 求解网络安全态势预测的人工鱼群算法 139

5.7.1 网络安全态势预测模型 140

5.7.2 算法的设计 141

5.7.3 仿真实验结果 143

5.8 求解图像边缘检测的遗传算法 146

5.8.1 数字图像边缘 146

5.8.2 Sobel边缘检测算子 148

5.8.3 面向图像边缘检测的遗传算法 149

5.8.4 仿真实验结果 151

5.8.5 结论 155

5.9 本章小结 155

参考文献 157

第6章 总结与展望 159 2100433B

本书面向智能信息处理研究的前沿领域，针对群体智能优化算法及其应用中的关键问题，系统地讨论了新型群体智能优化算法以及群体智能优化算法在三维模型处理和可信软件测试中的应用，比较全面地反映了国内外在三维模型智能处理和基于搜索的可信软件测试领域的最新研究进展。本书主要内容包括经典群体智能优化算法、社会认知优化算法、自然社会认知优化算法、细菌群体趋药性算法、混沌细菌群体趋药算法、三维模型多特征提取、基于证据和区间数的智能三维模型融合匹配识别方法、基于群体智能的文物三维模型全局最优匹配算法、基于群体智能的三维模型配准算法、基于粒子群算法的测试数据生成及优化、基于改进粒子群优化的测试用例扩增方法和基于蚁群算法的组合测试数据生成与优化。

本书以人工鱼群算法、烟花爆炸优化算法两个典型的群体智能算法为主，系统介绍了算法的原理，建立了基于协作、竞争机制的群体智能算法的数学模型。全书着重分析了人工鱼群算法和烟花爆炸优化算法的弱点，并提出了多种新颖的改进机制，给出了算法的详细实现步骤。本书还详细探讨了部分群体智能算法在VRP问题、图像边缘检测、SVM反问题、网络态势预测、数据聚类、特征选择等领域内的应用，并介绍了近年来出现的两个比较新颖的群体智能算法，顾问引导搜索算法和教—学优化算法。