Linear functions play a key role in the runtime analysis of evolutionary algorithms and studies have provided a wide range of new insights and techniques for analyzing evolutionary computation methods. Motivated by studies on separable functions and the optimization behaviour of evolutionary algorithms as well as objective functions from the area of chance constrained optimization, we study the class of objective functions that are weighted sums of two transformed linear functions. Our results show that the (1+1) EA, with a mutation rate depending on the number of overlapping bits of the functions, obtains an optimal solution for these functions in expected time O(n log n), thereby generalizing a well-known result for linear functions to a much wider range of problems.
翻译:线性功能在进化算法和研究的运行时间分析中发挥着关键作用,为分析进化计算方法提供了广泛的新洞察力和技术,在对分解功能和进化算法的优化行为以及从机会限制优化领域的客观功能进行研究之后,我们研究了两个转变线性功能的加权总和的客观功能类别。我们的结果显示,根据功能重叠部分的数量而变化速度的(1+1)EA在预期时间O(nlogn n)为这些功能找到最佳解决办法,从而将线性函数的众所周知的结果概括为范围更广的问题。