分散搜索算法(Scatter Search Algorithm)是一个基于种群的进化算法。它的基本策略是创建综合决策规则和约束条件,其目的是通过组合两个或多个元素(解)以获取一个更好的新元素。分散搜索算法与遗传算法(Genetic Algorithm)-样同属于进化算法。但分散搜索算法与遗传算法最明显的区别在于它的一系列操作策略不再基于随机性原则,而于运用“分散.收敛集聚”的智能迭代机制。分散搜索算法最初由Glover于20世纪70年代提出,但直近年来才广泛地应用于求解许多组合优化问题,如中位问题,分配问题,旅行商问题等。 在最近几年以来,很多人去关注优化问题的不只是单个目标函数,现实世界中的优化问题通常是多属性的,一般是对多个目标的同时优化。如一个国家的最优良性发展,涉及到经济的快速增长,社会秩序的稳定,环境的保护和改善等多方面,在这里,经济快速增长和社会秩序的稳定这两个优化目标是相辅相成的,互相促进的。在多数情况下,被同时优化的多目标之间是相互冲突的,如在企业生产活动中,产品质量与生产成本是两个相互冲突的目标。 为了达到总目标的最优化,一般需要对相互冲突的子目标进行综合考虑,即对各子目标进行折衷(tradeoffs)。由此,针对多目标的优化问题,出现了多目标进化算法(multi-objective evolutionary algorithm,MOEA)。对于MOEA性能评价方法主要考虑两个标志：一个是MOEA的效率(efficiency),另一个是MOEA的效果(effectiveness)。MOEA的效率主要指它在求取一个多目标优化问题的Pareto最优解集时所有需要的CPU时间,以及它所占用的空间资源。MOEA的效果则是指它所求得的Pareto最优解的质量,主要是指:MOEA的收敛效果和所求解集的分布性效果。此外,MOEA的鲁棒性(robust),求解问题的范围(scalability),以及方便使用等也是考察MOEA效果的重要指标。 随着遗传算法的兴起并广义应用于工程技术中,对于多目标优化问题的遗传算法也提出了NSGA-II算法。虽然NSGA-II算法在求解高质量的性能也有很好的效果,但在分布性和收敛性也有不少的问题。对于分散搜索算法的过程中,它前考虑了分布性和收敛性的问题。就是当它初始解集时创建一个参考集,用于存放分布性的解集。 因此,分散搜索算法和NSGA-II算法相对比较分散搜索算法有更好的分布性,而分散搜索算法具有杂交和变异操作与NSGA-II算法同样。 总之,分散搜索算法有良好的求解的性能和克服了分布性和收敛性的问题。 本文采用分散搜索算法的单目标问题当中改进算法使得该算法可以运行在多目标优化问题,本文下面还提出了算法的设计并做一些测验。该算法的结果不但具有很好的寻找多目标的非支配集或Pareto最优解,而且具有很好的收敛性和分布性。