地铁闸机检测系统中特定数目传感器布置方法(7)
4.1.3 基于种群的搜索
一般来说，优化算法是收敛于最优解的一系列计算步骤。多数经典的优化方法基于目标函数的梯度或者高阶导数产生一个确定的计算系列。这类方法只作用于解空间中单个解，随着迭代的进行，这个解沿着最速下降方向不断改进。这种
点对点的搜索方法极有可能陷入局部最优解。遗传算法通过保持一个潜在解的种群进行多方向搜索。这种种群对种群的搜索有能力跳出局部最优解。种群进行的是进化的模拟，每代中相对较好的解可得到繁殖的机会，而相对较差的解只得消亡。遗传算法采用概率转移率，以一定的概率选择部分个体繁殖，而令另一些个体消亡，从而将搜索引向解空间中最可能获得改进的区域。
图4-2 传统优化方法与遗传算法的比较
遗传算法处理的对象不是参数本身，而是对参数集进行了编码的个体。许多传统搜索方法都是单点搜索算法，即通过一些规则的变动，问题的解从搜索空间中的当前解移动到另一解。这些点对点的搜索方法，对多峰分布的搜索空间常常会陷入局部最优解。相反，遗传算法是采用同时处理群体中多个个体的方法，即同时搜索空间中的多个解进行评估。这一特点是遗传算法具有较好的全局搜索性能，减少了陷入局部最优解的可能性。同时，遗传算方法本身也有较好的并行性。为计算提供了方便。在标准遗传算法中，基本上不用搜索空间的知识或者其他辅
助信息，而仅用适应度函数来评估个体，并在此基础上进行遗传操作。遗传算法采用的不是确定性规则，而是采用概率的变迁规则来指导它的搜索方向。
上述这些都是遗传算法较之传统算法的特色。这使得遗传算法的技术和方法是用简单，鲁棒性强，易于并行化，从而应用范围更广。遗传算法与传统方法的比较见图4-2。
4.1.4 亚-启发式
最初，遗传算法是一种为许多难解问题设计的一种通用工具。早起的许多工作采用固定长度的二进制串作为通用的表达方式，遗传算子进行领域独立的二进制运算，而不使用任何字串所表达的领域知识。这种通用性反映了对具有广泛用途的鲁棒自适应系统设计的强调。然而，这种简单的遗传算法难以成功地直接用于许多难解的优化问题。对于各种特殊问题，人们创造了各种以遗传算法为亚-启发式的非标准的算法。Michalewicz给他的著作起了个生动的名字：《遗传算法=数据结构+进化程序》[19]，以强调我们不要局限于二进制的定长字串和算子，相反应多运用自然表示（适于给定问题的数据结构）和能用于这种数据结构的有意义的遗传算子。
4.1.5 主要优点
作为一种新的优化技术，遗传算法受到了广泛的注意。它在解最优化问题时有以下三大优点：
（1）遗传算法对于所解的优化问题没有太多的数学要求。由于它的进化特性，它在解的搜索中不需要了解问题的内在性质。遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的，甚至混合的搜索空间。
（2）进化算子的各态经历性使得遗传算子能够非常有效的进行概率意义下的全局搜索，而传统的优化方法则是通过邻近的点比较而移向较好点从而达到收敛的局部搜索过程。这样，只有问题具有凸性时才能找到全局最优解，因为这时任何局部最优解都是全局最优解。
（3）遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造独立的启发式算法，从而保证算法的有效性。
4.2 闸机检测系统传感器布局优化中的遗传算法
本课题可以用以下的数学公式描述：