地铁闸机检测系统中特定数目传感器布置方法(6)
4.1 遗传算法简介
4.1.1 遗传算法的一般结构
遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。和传统的算法不同，遗传算法从一组随机产生的初始解，成为“种群”，开始所搜。种群中的每个个体是问题的一个解，称为“染色体”。染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适应度”来测量染色体的好坏。生成的下一代染色体称为后代。后代是由前一代染色体通过交叉或变异运算生成的。新一代形成中，根据适应度的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适应度高的染色体被选择的概率较高。这样，经过若干代之后，算法的收敛于最好的染色体，它可能就是问题的最优解或次优解。设 和 分别表示第 代的双亲和后代，遗传算法的一般结构可以描述为图4-1。
通常初始化是随机产生的。重组包括交叉和变异来获得后代。实际上，遗传算法有两类运算：
（1）遗传运算：交叉和变异
（2）进化运算：选择
遗传运算模拟了基因在每一代中创造新后代的繁殖过程，进化运算则是种群驻代更新的过程。
交叉是最主要的遗传运算，它同时对两个染色体操作，组合二者的特性产生新的后代。交叉的最简单方法是在双亲（两个父辈的个体）的染色体上随机选取一个断点，将断点的右段互相交换，从而形成两个新的后代。这种方法对于二进
制表示最为合适。遗传算法的性能在很大程度上取决于采用交叉运算的性能。
图 4-1 遗传算法一般结构
交叉率（即为 ）定义为各个代中交叉产生的后代数与种群中的个体数（通常记为 ）的比。它将参加交叉运算的染色体个体的期望控制为 。较高的交叉率可达到更大的解空间，从而降低停在非最优解上的机会；但是这个比率太高，会使搜索不必要的解空间而耗费大量的计算时间。
变异则是一种基本运算，它在染色体上自发地随机的变化。一种简单的变异方法是替换一个或多个基因。在遗传算法中，变异可以提供初始种群中不含有的
基因，或找回选择过程中丢失的基因，为种群提供新的内容。变异率（记为 ）定义为种群中变异基因数在总基因数中的百分比。变异率控制了新基因导入种群的比例。若变异率太低，一些有用的基因就不能进入选择；若太高，既随机的变化太多，那么后代就可能失去双亲继承下来的好的特性，这样算法就失去了从过去的搜索中学习的能力。
遗传算法在几个基本方面不同于传统的优化方法。
（1）遗传算法运算的是解集的编码，而不是解本事
（2）遗传算法的搜索开始于解的一个种群，而不是单个解
（3）遗传算法只使用适应度函数（适值函数），而不使用导数或者其他辅助知识
（4）遗传算法采用概率的，而不是确定的状态转移规则
4.1.2 遗传算法的搜索策略
搜索是人们对于问题的求解步骤没有先验知识时所采用的一种通用的方法。搜索可以采用盲目策略或者启发策略。盲目搜索策略不使用任何问题的领域信息；而启发式搜索则要使用把搜索引向最好方向的附加信息。搜索策略中包含两个重要方面，即探索最好解和扩展搜索空间。Michalewicz对爬山搜索、随机搜索和遗传搜索做了一个比较[19]。爬山法制注重探索最好的解而忽略了搜索空间的扩展；随机搜索注重搜索空间却忽略了探索空间中最优希望的区域；而遗传算法是一类通用目的的搜索方法，它综合了定向搜索与随机搜索的优点，可以取得较好的区域探索与空间扩展的平衡。在遗传搜索的开始，随机的多样性的种群和交叉运算倾向于扩展搜索空间的大范围搜索，随着高适应度解的获得，交叉运算倾向于在这些解的周围探索。换言之，交叉运算采用何种搜索策略（探索或扩展）取决于遗传系统的环境（种群的多样性）而不取决于运算本事。需要指出的是，简单的遗传运算设计为通用目的的搜索方法，它基本是一种盲目搜索而不能对后代进行改进。所以应根据具体问题，调整参数，选择合理的方案。