下载掌阅APP，畅读海量书库
立即打开
对于图像特征选取的组合优化问题，采用了求解组合优化问题的两种现代优化算法，即遗传算法和分散搜索算法。
遗传算法 [10] （GA，Genetic Algorithm）模拟了达尔文的“优胜劣汰”进化过程，即模拟了自然选择和遗传进化中发生的繁殖、交配和突变现象。从一个初始种群出发，通过随机选择、交叉和变异操作，产生一群新的更适合环境的个体；再使群体进化到搜索空间中越来越好的区域，这样一代代不断进化；最后，收敛到一个最适应环境的个体上，求得问题的近优解。
在遗传算法中，需要用到适应度函数、选择算子、交叉算子和变异算子等概念。适应度是为实际问题预先定义的数学度量，用于测试每个个体的优劣程度。选择算子保证父种群和子种群个体的连续性，也使得子种群继承父种群适应度函数高的个体。交叉算子和变异算子用在种群进化中，交叉算子使得下一代种群中的个体不但继承上代种群中父体的基因，而且还要继承母体的基因；变异操作对应着生物界的基因突变，增加种群中个体的多样性。
每个用二进制串编码的个体叫作染色体。遗传算法的具体步骤如下：
1）建立初始种群，由 P 个个体组成，每个个体为 d 位基因码，计算每个个体的适应度（Fitness）函数值。
2）选择算子（如轮盘法、锦标赛选择等方式）：从当前种群中选择繁衍到子种群的个体。
3）从2）选择的个体经过交叉算子（如两点交叉、均匀交叉等方式）和变异算子（如“位”突变），产生后代种群。
4）从3）中选择前 P 个适应度函数值最大的个体作为当前种群。重复步骤2）～4）直到终止条件被满足。
步骤中的终止条件可以是事先定义的最多迭代次数和求解精度等。
与遗传算法类似，分散搜索（SS，Scatter Search） [11] 算法也是一种基于种群的进化算法。不同的是，分散搜索算法在种群的选择中，不仅考虑个体解的质量，还要考虑整个种群的分散性。通过控制参考集中解的质量和分散性，使得搜索过程具有良好的广泛性，不容易陷入局部最优。算法包括5个部分：初始种群的产生策略、子集产生策略、解的组合策略、解的改进策略和参考集更新策略。
初始种群的产生策略必须能产生具有良好质量和分散性的初始种群，这样从中精选出的参考解集，才能广泛地分布在整个解空间，且具有良好的多样性。子集产生策略构造若干个参考集的子集，而解的组合策略分别组合这些子集中的解产生新解。产生的这些新解经改进策略进行改进后，用于更新参考集。分散搜索算法步骤如下：
1）以初始种群产生策略建立初始种群。
2）使用参考集更新策略从初始种群构造参考集，其过程（参考集包含新解）如下：
①用子集产生策略产生参考集的子集集合NewSubsets。
②对NewSubsets中的各个子集分别使用组合策略产生新解，并以改进策略进行改进。
③用改进后的这些新解更新参考集。