本书以降低算法时间复杂度和空间复杂度为主线。首先，简单介绍群智能计算的专业基础知识，从降低算法时间复杂度的角度来陈述量化蚁群算法的设计思路，并用其来解决旅行商问题。然后，重点介绍基于gamma分布的扰动向量设计，并进一步改进猫群算法，减少算法的计算量，提高算法寻优能力。最后，利用简洁式猫群算法和支持向量机方法结合来解决人脸表情的识别问题，进一步扩展简洁式猫群算法的应用空间。


目录
第1章 绪论 1
1.1 群智能计算基础 3
1.1.1 概述 3
1.1.2 **化问题 3
1.1.3 计算复杂性与NP理论 4
1.1.4 群智能计算优化算法 6
1.2 国内外的发展现状及趋势 10
1.2.1 蚁群算法的发展概况 10
1.2.2 粒子群算法的发展概况 12
1.3 简洁式群智能计算优化算法 14
第2章 量化蚁群算法及其在旅行商问题中的应用 16
2.1 蚂蚁系统 17
2.1.1 状态转移规则与路径构建 18
2.1.2 信息素更新规则 19
2.2 量化蚁群算法 19
2.2.1 信息素的编码 20
2.2.2 信息素的更新规则 20
2.2.3 算法流程 21
2.3 实验结果与分析 22
2.3.1 基于收敛结果与迭代次数的比较 24
2.3.2 基于收敛结果与运行时间的实验结果比较 26
2.3.3 基于相同收敛结果与不同迭代次数比较 27
2.3.4 基于相同迭代次数与不同收敛结果的比较 29
第3章 简洁式猫群算法及其在灰度图像切割中应用 31
3.1 猫群算法与虚拟种群的取样机制 33
3.1.1 猫群算法 33
3.1.2 虚拟种群的取样机制 36
3.1.3 扰动向量更新规则 38
3.2 简洁式猫群算法 39
3.2.1 初始化与扰动向量更新 39
3.2.2 搜寻模式更新规则 41
3.2.3 跟踪模式更新规则 41
3.2.4 算法实现过程 42
3.3 实验结果及其分析 43
3.3.1 算法运行空间比较 44
3.3.2 节省运行空间算法收敛结果比较 45
3.3.3 cCSO与基于种群的优化算法收敛结果比较 49
3.3.4 基于迭代次数的收敛结果比较 52
3.3.5 实验结果分析 53
3.4 案例分析 53
3.4.1 多阈值法与适应度函数设计 54
3.4.2 图像切割效果 56
3.4.3 应用案例小结 61
第4章 基于Γ分布的简洁式猫群算法及其在音乐水印嵌入中的应用 63
4.1 基于Γ分布的扰动向量设计 64
4.1.1 扰动向量设计 64
4.1.2 扰动向量的更新规则 66
4.1.3 虚拟种群的取样机制 66
4.2 基于Γ分布的简洁式猫群算法 67
4.2.1 算法的初始化 67
4.2.2 搜寻模式的更新规则 68
4.2.3 跟踪模式的更新规则 70
4.2.4 算法流程 70
4.3 实验结果与分析 71
4.3.1 算法运行空间比较 73
4.3.2 节省运行空间的算法实验结果比较 73
4.3.3 基于种群的相关算法和简洁式猫群算法之间的实验结果比较 80
4.3.4 基于相同收敛结果下迭代次数的比较 83
4.3.5 基于标准测试函数的不同维度下的实验结果统计分析 84
4.3.6 实验结果小结 85
4.4 应用案例：音频水印嵌入 86
4.4.1 基于优化的水印嵌入与提取策略 87
4.4.2 实验结果与分析 90
4.4.3 案例分析小结 96
第5章 基于简洁式猫群算法与支持向量机的人脸表情识别与优化 97
5.1 基于活动基模型的分类器训练基础 98
5.1.1 方块图中的眼睛与嘴唇的捕捉 98
5.1.2 模型表示：活动基模型 99
5.1.3 模型训练：Shared Sketch算法 100
5.1.4 基模板构建 101
5.1.5 特征向量 102
5.1.6 支持向量机 102
5.1.7 简洁式猫群算法 105
5.2 cCSO-SVM策略 107
5.3 实验结果与分析 108
参考文献 111
附录 124


第1章 绪论
　　大自然是美妙的，更是神奇的。众多奇妙的生物，没有人类复杂的大脑，但一样有着惊人的生存能力；它们通过简单的个体协作完成很多复杂的任务；它们的机体对大自然有着极强的适应性；它们之间的信号传递是那么的精准；它们的分工是那么井然有序。正因为有了这些神奇的生物个体，大自然才多姿多彩而又更具活力。
　　人类比其他生物更聪明、更主动。他们每时每刻都在适应和改造自然。人类时刻在关注大自然，大自然的各种现象给他们太多灵感，他们努力解读自然界生物的每一种行为语言，如蜜蜂圆舞曲的神秘含义、鱼群的洄游规律等。而人类的目的不仅仅是要解读这些规律和特征，他们更希望利用这些规律和特征用以改造和征服大自然。他们坚信更美好的生活来源于创造和创新，来源于对现有工作的不断精益求精。现有的问题，如果在一定程度上加入大自然的启发，会有更加意外的惊喜。
　　在某种确定的价值取向或审美观念的支配下，面对某个问题如何求解一个可行的甚至是**的解决方案，这是我们经常要面临的问题。这类决策性问题通常称为**化问题。如背包问题(knapsack problem)、旅行商问题(travel salesman problem，TSP)就是**化问题的典型代表。
　　长期以来，人们不断探索研究优化问题，生活中的许多重要工程问题都需要用**化的方案来解决。**值最小值问题早在17世纪就被提出来并给出了一些求解方法。随后经过一些研究者不懈的努力，这类传统优化算法得到了很大的发展，包括线性规划和非线性规划、动态与随机规划等在内的算法相继出现。但这类用解析法和数值计算的传统优化算法有着很高的计算复杂度，一般只适合解决小规模的优化问题。
　　随着社会的发展，工程实践问题也变得越来越复杂，面对大型的工程类问题，传统的解析法和数值计算法等方法显然难以满足求解日渐复杂的**化问题的需要，显得有些力不从心；无论是求解时间还是求解精度都难以让人接受。特别是对于NP（nondeterministic polynomial）难类和NP完全类问题，设计应用于解决这些问题的传统精确算法由于其指数级的计算复杂度而无法在正常的工程时间内得到期望的结果。因此，为了在计算精度和求解时间上获得一个相对的平衡，许多科学家把目光投向了神奇的大自然，希望能从大自然中的某种现象中得到启发，找到办法来解决这些问题。
　　随着人们对生物的深入研究，研究者发现一些非常神奇的现象，很多个体行为简单，能力非常有限的生物，却有着明确的分工和惊人的协作能力。许多学者研究这些现象，并归纳总结这些特征，结合不同领域的实际问题，提出了许多基于生物特征的启发式算法，如粒子群优化算法、蚂蚁算法、猫群优化算法、人工鱼群算法等，尽管这类算法都有它们各自的适用范围，但都能在一定的程度上找到问题的相对**解。这些算法或者模仿生物觅食的行为，或者模仿生物的进化过程，或者模仿生物群体迁徙行为，或者模仿生物的生理构造和身体机能等。面对待优化的问题，总是能在一定的工程时间内求得一个相对可以接受的解，我们把这些模仿自然界生物群体的各种生态习性来解决各种难于解决的工程问题的算法叫作生物启发式算法或者群智能计算优化算法。
　　一直以来，群智能计算作为智能计算大家族的主要成员，其归属于人工智能学科领域。它的发展在很大程度上依赖于人工智能学科的发展。而人工智能的部分分支因缺少直接的数学理论支撑而受到太多的质疑。智能计算的重要组成部分人工神经网络技术有着数学理论基础支撑却又无法精确处理应用领域的各类小样本的问题。比较幸运的是，近年来机器学习研究有了较大的进展,特别是支持向量机等相关技术的出现打破了智能计算方法只能处理大样本集的问题的瓶颈，同样也能灵活处理各种小样本集的问题,从而使该项技术能更切合实际的需求，与人工智能其他技术相互补充，进而反哺人工智能学科，相互促进发展。
　　近年来，群智能计算优化算法因高效的优化性能，尤其是不需要待优化问题的特殊信息等特点为更多非计算机领域研究者所接受。其应用领域已经飞速扩展到科学计算、车间排程优化、交通运输配置、组合问题、数字图像处理、工程优化设计等领域,并成为人工智能学科以及计算机科学不可或缺的重要组成部分。然而，群智能计算优化算法和传统的优化算法相比，发展历史还比较短，群智能计算优化算法还有很多不完善的地方；尤其是数学基础一直是其发展的短板；很多算法因为本身搜索逻辑的局限性，导致算法容易陷入局部**；群智能计算领域还有太多的问题等待我们去探索和解决。
　　随着计算机软硬件的飞速发展，普通的计算机应用环境已经基本能够满足群智能计算优化算法所需的软硬件条件。但仍然有一些工程领域，或者因为各种条件的限制，不能提供足够的硬件资源来确保满足优化算法的运行；或者因为工程需要，需要求得实时结果，其硬件构造只能是比较简单的系统；或者因为系统容错的要求，不能提供相应的软硬件环境。在这样的综合条件下，采用传统的群智能优化算法来处理，很难融入工程软硬件环境中，如嵌入式微控制器系统的优化、工业控制实时应答系统的优化、自动对接系统的优化等都是这样。这要求必须在传统的启发式算法的基础上加以改进和创新，来适应特殊条件下的工程优化需求。
　　基于此,本书以上述应用条件为背景，设计新的简洁式群智能计算优化算法，使其能够在内存空间较少，计算能力也不太强的硬件环境中也能正常运行；在传统群智能计算优化算法的基础上，融入新的思想，相对减少对计算机硬件资源的依赖，在相近运行环境下达到可以接受甚至比传统优化算法更好的结果。
　　1.1 群智能计算基础
　　1.1.1 概述
　　群智能计算优化算法是一类模拟自然界中行为简单的个体在相互作用过程中涌现的整体智能行为的算法，因其简单的原理和易于实现等特点为各个领域所接受。以蚁群算法和粒子群算法为代表的群智能计算优化算法得到广泛的关注。解析它们的算法原理将有助于更好地理解群智能计算优化算法。
　　1.1.2 **化问题
　　美好的生活源于创造，源于对生活和工作细节的精益求精，在某种特定的价值取向或审美观念的支配下，如何求解某个问题的一个可行的甚至是**的解决方案，这是我们在生活和工作经常会面对的问题。这类决策问题通常称为**化问题。
　　**化问题的定义一般用式(1-1)来表示。式中：S为待解决问题的集合或者称为搜索空间；X为根据解决问题而设计的一组候选解；f为目标函数或者评价函数；g(X)为约束函数。
　　式(1-1)中的目标函数f取得**值或者最小值时变量X的取值称为**解。在实际的工程和应用中，可行解X称为决策变量,可以表示为X=(x1,x2，…,xn),n为待解决的问题的维度。
　　当待解决问题的目标函数f受到某些条件的限制时，必须在满足限制条件下取得的极值f才有意义，此时变为有约束的优化问题；如果没有g(X)的限制，则为无约束优化问题。
　　不同的工程问题所需解决的优化问题不同，其决策变量X的取值类型和范围也不同。如果变量X为一组连续的实数，则这种类型的优化问题是函数优化问题；若变量X为一组离散的数据，则此类优化问题为组合优化问题。如旅行商问题、背包问题就是组合问题，而标准测试函数峰值寻找就是函数优化问题。实际应用中也会出现部分变量取值为连续型，而另外一部分变量的取值为离散型的情况。因此，决策变量的取值类型并不是对优化问题分类的**标准，可以进一步根据决策变量的约束条件、问题的性质、目标的个数、时间因素、函数关系、极值的个数等多个角度来对优化问题进行分类。显然单目标优化问题和多目标优化问题就是根据需要优化的目标的个数来分类的；而单峰值优化问题和多峰值优化问题的分类则是根据函数可能取得的极值的个数是否多于1个。
　　1.1.3 计算复杂性与NP理论
　　1.计算复杂性
　　为了说明计算复杂性这个问题，需要先说明旅行商问题和背包问题。
　　定义1.1 旅行商问题
　　设现有n座城市，它们构成城市集C={c1,c2,…,cn}，其中任意两座城市之间的距离构成矩阵，TSP就是从某个起点出发，找到一条只拜访每座城市一次且最后回到起点的、路径最短的回路。
　　通常所说的旅行商问题都是对称旅行商问题，即两座城市之间来回是可达的，且距离相等。
　　定义1.2 背包问题
　　设现有n件商品和一个固定容量为C的背包。其中第i件商品的体积为ci，价值为vi，背包问题就是往背包里面不停装商品，在所有装入背包的商品体积总和的情况下，使得所有商品的总价值具有**值，即。其中：xi为0表示不选择第i个商品；xi为1表示选择第i个商品。
　　一般来说，现在的**化问题都是一些难以解决的问题，以非对称旅行商为例，就是1个n座城市排列的问题，有n!种可能。而背包问题则有2n种可能。问题的规模都是呈指数级增长的，单纯靠传统的穷举方法来解决问题显然是不可能的。表面看起来可以实现的问题在实践中不一定可行。
　　计算复杂性通常用来描述待解决问题执行的难易程度。对一个优化问题的计算复杂性进行评价是比较困难的，首先要确认描述问题的函数的规模是什么类型。例如，需要n次穷举才能解决的旅行商问题问题，其计算复杂性可以用指数来描述。如果问题的计算所需要的运算次数需要用n的多项式来度量，则称该问题具有多项式时间复杂性。
　　对于某些具体的问题，其计算复杂性有上下界限。计算复杂性的上限就是解决该问题可能的最快速度时的特例情况。而计算复杂性的下界则很难去证明有多大，很多时间要看具体的环境、条件等。
　　2.NP类问题
　　在计算机学科中，有一类问题可以用确定性算法在多项式时间内来解决，但这类问题前提是判断性问题，这类问题通常称为P类问题。与确定性算法相对的是不确定性算法。一般来说，一个不确定性算法包含两个步骤，其输入就是判断问题的实际例子instant，需要从如下两个过程来实现。
　　（1）非确定过程，也就是猜测阶段。任意产生一个串string，并把它当作判断问题实例的一个候选解solution。
　　（2）确定过程，也就是验证候选解solution的阶段。将实例instant和串string作为算法的输入，若string是instant的一个合法解，则输出“YES”。
　　若一个不确定算法在验证阶段的时间复杂度为多项式级别，则该算法为不确定性多项式算法。
　　根据上述过程，可以这样描述NP类问题：NP类问题就是一类能够用不确定性多项式算法来求解的判断问题，如常见的旅行商问题就是典型的代表，虽然我们还不一定能找到一个多项式的确定性算法来求得最佳解，但可以判断一个在多项式时间内随机生成的闭合回路是否合法。
　　通过比较P类问题和NP类问题的定义，可以得到一个非常明显的结论：但P=NP是否成立则是一个科学界的未解之谜。类似旅行商问题和背包问题的存在使得学术界的学者更趋向于认为P=NP的结论不成立。换句话说，NP类问题中不仅仅包括P类问题，还包括另一问题，而这另外的一种问题就是所谓的NP完全问题，其定义可以概括如下。
　　若某一个判断问题DEP是NP完全问题,则其应该满足条件：
　　（1）DEP是NP类问题。
　　（2）NP中的任何问题都是可以在多项式时间内转为判断问题DEP。
　　若满足条件（2）但不满足条件（1）的问题则称为NP难问题。
　　从上面的结论可以推出，NP难问题不一定是NP类问题，或者更确切地说，一个NP难问题的难易程度是大于等于NP完全问题的。
　　P类问题、NP类问题、NP完全问题以及NP难问题之间的关系可以用图1-1来表示。
　　图1-1问题分类关系示意图
　　1.1.4 群智能计算优化算法
　　经过众多的研究者的努力，群智能计算优化算法不停向前发展，新的算法如雨后春笋般不断提出。这些算法包括进化算法、ACO（蚁群算法）、PSO（粒子群算法）、CSO（猫群算法）、ABC（人工蜂群算法）、ASFA（人工鱼群算法）、BA（细菌觅食算法）、SLSA（混合蛙跳算法）、Memetic算法、AIS（人工免疫算法）、QEA量子进化算法等。这些仿生算法的仿生特点大致可以分为两类：一类模仿生物种群进化过程，通过优胜劣汰的竞争机制来保证留下来的种群向更优的方向移动，如遗传算法就是典型代表、被称为文化基因算法的Memetic算法也是其中成员之一；另一类算法模仿生物特有的行为模式和协同合作机制，依靠群体的随机搜索来完成**解的发现，现有的大多数群智能算法都是遵照此类特点而设计开发出来的。
　　1.群智能计算优化算法的计算机制
　　群智能计算优化算法的整个过程一般可以分为种群初始化、个体更新、群体更新三大步骤。**解在群体更新完成后根据适应度函数的取值挑选出来。
　　1）种群初始化
　　在群智能计算优化算法中，首先必须要有种群的初始化。先确定解的分布空间，在没有任何先验知识指导下，一般都会按照均匀概率分布随机产生若干个个体，默认每一个个体为待优化问题的候选解；如果有先验知识的指导则按照指导产生种群。有先验知识指导而产生的初始化个体会更加有效，算法搜索的盲目性会相对降低，从而使得算法的收敛速度更快。
　　初始化阶段涉及如下4个方面的内容。
　　（1）问题的表现形式。面对优化问题，首先需要找到合适的编码方式与群智能计算优化算法进行匹配。也就是要确定问题的表现形式，是离散型问题，还是连