基于SS和SVM求解模型的优化方法

在分散搜索（SS，Scatter Search）算法中，解的编码表示和上节中改进GA算法的染色体相同。其具体步骤如下：

1）随机产生P Size（P Size=100）个解组成初始种群P，并按照解的适应度从大到小的顺序对P中的解排序。

2）从种群P中取前b₁个解（b₁=6）加入参考集RefSet，并从P中去除这些解。

3）对P中的各个解分别求到参考集RefSet中解的最小距离，选择该最小距离最大的解加入参考集RefSet，并从P中去除这些解。重复这个过程b₂次（b₂=4），使得参考集RefSet的规模达到b=b₁+b₂。

4）对参考集RefSet中的解两两交叉进行组合，产生90个新解。并对新得到的解进行改进。

5）用新得到的这些解更新种群P，更新时要保留参考集中的最好解。(www.xing528.com)

6）步骤3）～5）重复执行MaxIter次。

（1）解的组合 上面步骤中需要用到解的组合过程，即利用输入的两个解，产生一个新的、具有这两解共同特征的解。在具体实现时，对于表示输入解的2个二进制字符串的各个位，分3种情况处理：①如果两个输入解某位对应的数值都为1（即都包含该特征），则新解的相应位置取1；②若都为0，则取0。③如果两个输入解该位的数值不一致，则随机选取0或1。

（2）解的距离 SS算法需要精确度量解与解之间的差异（距离），这里选择文献[11]方法度量解之间的距离，即两解选用的共同特征个数与两解选择的特征总数之间的比。设2个解选择的特征组合分别为X₁和X₂，则两解之间的距离定义为D（X₁，X₂）=丨X₁∩X₂丨/丨X₁∪X₂丨，其中，丨·丨表示组合中包含的元素个数。

（3）解的改进 SS算法在迭代过程中，需要对产生的所有解进行改进。这里采用简单的局部搜索改进方法，即依次对解的各位取反并计算改变后解的适应度函数值，如果提高了解的适应度函数值就接受改变，否则该位改回原值。