交互式进化计算的适应值噪声及收敛鲁棒性

Interactive Evolutionary Computation with Fitness Noise and Its Convergence Robustness

噪声是影响进化计算(evolutionary computation,简称EC)算法性能的一个重要因素.对于传统EC中的噪声,已有许多研究成果,但交互式进化计算(interactive evolutionary computation,简称IEC)的噪声研究成果却较少.首先回顾了传统EC中噪声的定义、来源、类型及各种处理噪声的方法;其次,从IEC的理性用户观点出发,研究了IEC的适应值噪声及收敛鲁棒性.其中,空间的映射关系、个体间的占优关系以及IEC的收敛等是研究收敛鲁棒性的两个定理(强条件定理和弱条件定理)的基础.这两个定理表明,理性用户条件下的噪声不会影响算法全局收敛性.在这两个定理的基础上进一步得出了如下结论:有效的适应度尺度变换是弱条件定理的一部分,IEC中"真"适应值是用户偏好等.并以不满足弱条件定理,即破坏算法收敛性为依据,给出了IEC中适应值噪声的狭义定义.实验进一步验证了这两个定理.上述结论为进一步研究IEC作了必要的铺垫.

Noise is an important factor that influences the performance of evolutionary computation （EC）. Much research on noise was reported in traditional EC, but less in IEC （interactive evolutionary computation）. The definition, source, type of noise and methods to deal with noise in EC are reviewed firstly. Secondly, related with the rational user in IEC, the convergence robustness against fitness noise in IEC is studied. Mapping among spaces, dominating relationship and convergence in IEC are discussed to establish bases for two theorems： Strong condition theorem and weak condition theorem. These two theorems imply that the noise caused by the rational user will not prevent the algorithm from converging to the global optima. Thirdly, as the successive issue, the conclusions that the effective fitness scaling method is part of the weak condition and the user preference is the true fitness in IEC are discussed. The narrow definition of fitness noise based on the weak condition is also given. The experimental results validate the theorems, and the results establish a necessary foundation for future research.