基于二维可变邻域编码方式的混合遗传算法

针对现有混合遗传算法无法兼顾有效性及高效性的问题,提出一种基于二维可变邻域编码方式的新型混合遗传算法(VNHGA)。首先提出了一种将个体“基因型”与“邻域型”分开编码、同步遗传的新型编码方式,以替换传统二进制编码方式;然后设计了一种稳定变异算子,以替换传统变异算子来提高效率。通过多维函数最小值问题对VNHGA进行测试:首先验证采用所提二维可变邻域编码方式后,使用“鲍德温(Baldwin)效应”作为将局部搜索嵌入传统遗传算法策略时,相对于基于“拉马克(Lamarckian)进化”的嵌入策略,仍然具有采用传统二进制编码方式时的特性,即具有良好有效性但高效性不足;其次验证引入稳定变异算子后,算法在保持其有效性的同时提升了效率,运行时间缩短到之前的50%左右;最后,与两种改进混合遗传算法进行比较,验证所提算法优势。结果表明VNHGA兼具有效性与高效性特点,可用于解决最优化问题。

Hybrid genetic algorithm based on two-dimensional variable neighborhood coding

Concerning that the general hybrid genetic algorithms cannot give attention to both effectiveness and efficiency, a new hybrid genetic algorithm using two-dimensional variable neighborhood coding named VNHGA was proposed. Firstly, the traditional binary coding method was replaced by a new coding method, which was designed to separate coding and synchronous inheritance for individuals. Secondly, the traditional mutation operator was replaced by a new stable mutation operator to improve efficiency. VNHGA was tested by optimization problem of multi-dimensional functions. It was verified that, after adopting the new coding method, features with more effectiveness and less efficiency were maintained when using "Baldwin effect" relative to using "Lamarckian evolution" as embedding strategy. After introducing the stable mutation operator, effectiveness was maintained and efficiency was improved at the same time, and the running time was shortened about half of before. VNHGA was also compared with other two modified hybrid genetic algorithms to exhibit its advantages. The results indicate that VNHGA is both effective and efficient, and it can be used to solve optimization problems.