混合算法的邻域结构变更研究及在排样问题上的应用

Research on the Variable Neighborhood Structures of a Hybrid Algorithm and Its Application in Parking

本文研究了全局搜索算法和局部搜索算法的混合机制,设计了基于邻域搜索和遗传算法的混合搜索算法。该算法结合了遗传算法的全局搜索特性和邻域局部贪婪搜索特性;在分析排样问题碰靠过程特征的基础上,构建了排样问题邻域假设,当邻域假设满足时,遗传算法+邻域搜索能很好发挥作用;当不能判断邻域结构是否满足邻域假设时,提出了建立遗传算法+匹配变邻域的搜索算法,该算法兼顾了组合优化中邻域搜索的局部搜索无效的情况,实现了匹配的变邻域混合算法在排样优化问题中的应用。实例结果标明,排样图形不一样,其求解难度不一样,该算法均搜索到了更好的排样模式,验证了算法的有效性。

A hybrid method based on global search and local search is discussed and a hybrid algorithm based on neighborhood search and genetic algorithms is built. The hybrid algorithm is of good searching performance including global and local greedy search. Based on an analysis of the graph contacting characteristics in parking, a neighborhood assumption of parking is given. When the neighborhood assumption is met, the genetic algorithm ＋ neighborhood search could work well. And when it is hard to judge the neighborhood assumption of parking, a genetic algorithm ＋ matching neighborhood hybrid algorithm mechanism is built. And the genetic algorithm and matching variable neighborhood search is applied in parking to solve the problem that local search can not work. When parking graphics are different, the complexity of solving the problem is different. The results of example parking show that a better parking scheme is found in different parking problems and it shows the hybrid algorithm is effective.