下载掌阅APP，畅读海量书库
立即打开
不同的群智能优化算法虽然在搜索方式和进化策略上各有特色，但算法在总体结构和仿生计算机制方面还是有许多共同或相似之处的。群智能优化算法通常包含算法初始化、个体位置更新和竞争选择机制等过程，这些是群智能优化算法仿生计算机制中非常重要的环节。
在任何群智能优化算法中，都需要进行算法初始化，主要包括：确定问题解的形式、初始化算法参数、初始化种群的位置、选定适应度函数等。
1.确定问题解的形式
群智能优化算法求解复杂优化问题时，必须将求解问题转换到解空间，将具体问题的解以某种形式给出，这就需要对问题的解进行编码操作。不同的问题和群智能优化算法，对问题解的编码方式也有所不同。目前常用的编码方式主要有二进制编码、十进制（实数）编码和自然数（顺序）编码三种。对于求解0-1背包问题或求解一维问题，常采用二进制编码；对于求解多维问题，常采用实数编码；对于求解TSP问题，常按城市序号采用顺序编码。根据具体求解问题，选择合适的编码方式可以便于问题求解，提高编码的转换速度、算法的计算效率和收敛速度。编码的逆过程就是解码，即将编码对应为问题的解。
2.初始化算法参数
在群智能优化算法中，算法开始执行前一般都需要给定某些相关参数的取值，如在遗传算法中需要给定种群数量、编码长度、交叉概率、变异概率和最大进化代数等，在蚁群优化算法中需要给定种群数量、信息素重要度参数、启发因子重要度参数、信息素挥发系数、信息素强度系数和最大进化代数等。合理选取算法参数取值对算法性能和求解结果有很大的影响，但给定算法参数取值本身也是一个重要的最优化问题。
适当的参数值能够提高算法的准确性，如果参数选取不当，则会使算法的适应性变差，甚至影响算法的整体性能。例如，种群数量过大，将会增加算法的时间复杂度，降低算法的效率；如果取值过小，则很容易使算法出现“早熟”现象，陷入局部最优而找不到最优解。变异概率取值太小，不容易产生新解；如果取值太大，又容易造成个体发散。最大进化代数取值太小，往往求解精度不高；如果取值太大，则容易出现算法已经收敛到全局最优解而还将继续执行的现象。实践证明，算法参数取值通常需要根据具体求解问题和多次试验来确定，没有绝对的最优参数值。针对不同的求解问题，只有通过反复试验，才能选取较合适的参数，获得更好的算法性能。
3.初始化种群的位置
确定了问题解的形式和种群数量之后，需在搜索范围内给定种群中所有个体的初始位置。初始化种群的位置通常有两种方式：一种是随机初始化种群的位置，通过在搜索范围内产生随机数或随机编码的方式给定种群的初始位置；另一种是结合先验知识初始化种群的位置，如果预知最优解的大体位置，可以将更多的个体部署在最优解附近。在没有任何先验知识的情况下通常采用第一种方式，而第二种方式可以使算法较快地收敛到最优解。给定所有个体的初始位置后，种群可用一个二维矩阵表示：
式中， N 为问题的维数或解的编码长度；NP为种群数量。矩阵 X 的每个行向量为
就表示种群中的一个个体、一个个体的位置或问题的一个解。当然，根据个人编程习惯，也可用 N ×NP矩阵表示种群，矩阵的每个列向量就表示种群中的一个个体或问题的一个解。在此也需要说明：书中描述“解”“个体”“向量”“位置”“路径”等没有严格区分。
4.选定适应度函数
在所有群智能优化算法中，对个体的位置或所求问题的解，都需要进行评价，以便在群体进化过程中选择出优良个体，及早地剔除较差个体。评价个体或问题解的优劣，在群智能优化算法中一般采用适应度函数fit（ X i ）作为评价函数。适应度函数的选定对算法求解有着重要影响，好的适应度函数不但可以提高个体评价的准确性，而且还能提高算法的执行效率。
适应度函数需要根据求解问题的实际情况进行选定。在函数优化问题求解中，有时可将目标函数 f （ X i ）直接作为适应度函数，但有时需要在目标函数的基础上进行必要的改进。例如，当目标函数值有正有负，同时涉及依据概率的个体选择问题时，可以在目标函数上加上一个常数使之都具有正值作为适应度函数；当需要将最小值优化问题转化为最大值优化问题时，可以对目标函数直接取倒数或给目标函数加上一个常数后取倒数，也可以用较大的常数减去目标函数作为适应度函数。当然，如果目标函数的计算较为复杂，也可选取计算相对简单且与目标函数取值同向的某个特征函数作为适应度函数。
在群智能优化算法中，个体位置更新是实现搜索非常重要的环节，是种群进化得到最优解的关键所在，也是算法设计的核心问题。因为种群中的所有个体是利用编码方式用向量来表示的，在寻优搜索时需要对个体向量进行操作，实现个体位置更新。这些个体位置更新操作有时称为“算子”，在不同的群智能优化算法中构造了不同的位置更新算子。例如，在遗传算法中有选择算子、交叉算子和变异算子；在人工鱼群算法中有聚群算子、追尾算子和觅食算子等。
1.个体位置更新数量
根据个体位置更新数量的不同分为两种情况：一是所有个体都要进行位置更新，二是只有个别个体进行位置更新。
（1）所有个体都要进行位置更新。种群中的所有个体都要进行位置更新，然后通过竞争选择，得到进入下一代的种群。
（2）个别个体进行位置更新。只有种群中的个别个体进行位置更新，如混合蛙跳算法就只更新模因分组中最差青蛙的位置。
2.个体位置更新方式
个体位置更新方式主要有：从父辈中选择个体进行位置更新、受到特殊解的影响进行位置更新和随机位置更新等。
（1）从父辈中选择个体进行位置更新。从父辈中选择个体进行位置更新的方式较为普遍，如在基本差分进化算法中，每个目标向量的变异向量是由随机选择的三个互不相同，且与目标向量也互不相同的父辈个体得到的。
（2）受到特殊解的影响进行位置更新。这里的特殊解主要是指邻居集合的中心位置、邻居集合中的最优解、当前个体的最优解（个体极值）和当前种群的最优解（全局极值）等。当前个体位置更新利用这些特殊解的信息，正是群智能优化算法中信息交流和协助机制的一种重要体现。例如，在差分进化算法的其他形式中会用到当前最优个体；在粒子群优化算法中，当前粒子飞行速度的改变，要用到当前粒子搜索到的最优解和当前种群的最优解；在人工鱼群算法中，每条人工鱼执行聚群算子，要向邻居集合的中心位置移动，执行追尾算子要向邻居集合中的最优解移动；在混合蛙跳算法中，执行局部位置更新算子时，模因分组中处于最差位置的青蛙要向本组中处于最优位置的青蛙移动，如果不能产生一个更好的位置，则向全局最优位置的青蛙移动。
（3）随机位置更新。随机位置更新具有较强的随机性，往往会造成盲目搜索，但在一定程度上提高了种群的多样性，扩大了对解空间的搜索范围，有利于求得全局最优解，同时也是使算法跳出局部最优的一种重要方式。例如，在人工蜂群算法中，当蜜源开采超过最大开采次数后，就会放弃该蜜源，在解空间内随机产生一个新解替代当前解；在人工鱼群算法中，当每条人工鱼尝试聚群算子和追尾算子后，若其适应度函数值没有得到改善，则执行觅食算子，然而在尝试一定次数的觅食算子后，其适应度函数值还是没有得到改善，此时人工鱼将在解空间中随机移动更新位置作为一个新解；在人工蜂群算法中，跟随蜂的位置更新是在引领蜂位置基础上加一个随机扰动实现的，当蜜源枯竭时，即当前位置附近没有比引领蜂所在位置更好的蜜源时，则引领蜂变为侦察蜂，随机地在解空间中产生一个新的解。
3.惯性权重和步长权重
在个体位置更新中，有时需要在个体原始位置乘以一个惯性权重，有时需要在位置或速度增量上乘以一个步长权重。惯性权重和步长权重通常随着进化代数递减，算法开始时取较大的值，随着进化代数的增加，取值逐渐衰减到零或一个很小的值。这样有助于在进化后期，避免在最优解附近产生较大的摆动，有助于提高收敛速度和求解精度。
在群智能优化算法中，群体更新是种群中个体更新和优胜劣汰进化机制的宏观表现，它对于算法的搜索效果和收敛性能具有重要作用。常用的竞争选择机制包括以下几种。
1.“一对一”方式的贪婪竞争选择
当前个体通过位置更新得到一个解，如果新解的适应度函数值优于当前解的适应度函数值，则用新解替代当前解，这种竞争选择的方式就是当前位置和新位置的“一对一”方式的贪婪竞争选择。种群中的所有个体都经历了这种竞争选择后，种群自然也就实现了更新，得到进入下一代的新种群。这种竞争选择方式能够保留较优的个体，使个体自身不断优化，趋向最优解，从而使群体的质量得到改善，但也容易在种群进化过程中淘汰一些较好的解。
2.群体竞争选择
将当前种群中的个体通过位置更新得到的解都记录下来，组成一个新种群，然后把当前种群和新种群混合，按照适应度函数值进行排序，从中选择适应度函数值较好的部分个体组成进入下一代的种群。选取数量通常与种群数量一致，使种群数量在进化过程中保持不变。这种群体竞争选择进行种群更新的方式，能够充分保留进化过程中出现的优质解的信息，但也容易出现解的多样性不够、收敛速度过快、陷入局部最优的问题。
3.允许接受劣质解
在竞争选择中，如果一味地选择优质个体，很易造成种群内部的多样性枯竭，使算法出现早熟，搜索陷入局部最优。有时也有必要让一些较差个体保留下来，以扩充种群多样性，保证种群进化的整体方向。例如，在遗传算法中选择算子常采用轮盘赌方法，依据个体的适应度函数值以概率方式选择个体，使一些适应度函数值较差的个体也有机会被选中进行交叉变异操作。这种算法一方面保证了群体向更优的方向进化，另一方面保证了基因库的多样性，为搜索出更好的解提供了保证。
4.最优解保留策略
最优解保留策略就是将种群中适应度函数值最优的个体保留到下一代种群中，可以确保最优解不会出现退化现象，也是使算法收敛的一个重要手段。在算法迭代过程中，需要找出当前最优解，用当前最优解替代下一代种群的第一个解或最差解的方式，把当前最优解保留到下一代种群中。同时，如果当前最优解好于全局最优解，则记录和更新全局最优解，用当前最优解替代全局最优解。