下载掌阅APP，畅读海量书库
立即打开
在分散搜索（SS，Scatter Search）算法中，解的编码表示和上节中改进GA算法的染色体相同。其具体步骤如下：
1）随机产生 P Size（ P Size=100）个解组成初始种群 P ，并按照解的适应度从大到小的顺序对 P 中的解排序。
2）从种群 P 中取前 b 1 个解（ b 1 =6）加入参考集RefSet，并从 P 中去除这些解。
3）对 P 中的各个解分别求到参考集RefSet中解的最小距离，选择该最小距离最大的解加入参考集RefSet，并从 P 中去除这些解。重复这个过程 b 2 次（ b 2 =4），使得参考集RefSet的规模达到 b = b 1 + b 2 。
4）对参考集RefSet中的解两两交叉进行组合，产生90个新解。并对新得到的解进行改进。
5）用新得到的这些解更新种群 P ，更新时要保留参考集中的最好解。
6）步骤3）～5）重复执行MaxIter次。
（1）解的组合 上面步骤中需要用到解的组合过程，即利用输入的两个解，产生一个新的、具有这两解共同特征的解。在具体实现时，对于表示输入解的2个二进制字符串的各个位，分3种情况处理：①如果两个输入解某位对应的数值都为1（即都包含该特征），则新解的相应位置取1；②若都为0，则取0。③如果两个输入解该位的数值不一致，则随机选取0或1。
（2）解的距离 SS算法需要精确度量解与解之间的差异（距离），这里选择文献[11]方法度量解之间的距离，即两解选用的共同特征个数与两解选择的特征总数之间的比。设2个解选择的特征组合分别为 X 1 和 X 2 ，则两解之间的距离定义为 D （ X 1 ， X 2 ）=丨 X 1 ∩ X 2 丨 / 丨 X 1 ∪ X 2 丨，其中，丨·丨表示组合中包含的元素个数。
（3）解的改进 SS算法在迭代过程中，需要对产生的所有解进行改进。这里采用简单的局部搜索改进方法，即依次对解的各位取反并计算改变后解的适应度函数值，如果提高了解的适应度函数值就接受改变，否则该位改回原值。