Evolutionary algorithms are anytime algorithms, as they can produce a viable solution at any time and, moreover, the quality of the solution improves over time. However, it may be hoped that more information can be gained when a solution is produced, even if the algorithm is stopped before the optimum has been found. For example, one might want to know which of the bit values in the current best solution are necessary for a good result, and which are still uncertain. We propose heuristics for efficiently gaining such information about bit values, in the context of the \((1+1)\) EA. Along the way, we prove two useful general results. The first bounds the runtime for m parallel copies of a process. The second bounds the probability of having a non-optimal bit value at any given position when optimising a weakly monotonic function. Using these results, we prove bounds for the time it takes for our proposed heuristics to correctly identify bit values when the \((1+1)\) EA runs on monotonic and hidden subset problems.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Evolutionary Anytime Algorithms

  • Aishwaryaprajna,
  • Jonathan E. Rowe

摘要

Evolutionary algorithms are anytime algorithms, as they can produce a viable solution at any time and, moreover, the quality of the solution improves over time. However, it may be hoped that more information can be gained when a solution is produced, even if the algorithm is stopped before the optimum has been found. For example, one might want to know which of the bit values in the current best solution are necessary for a good result, and which are still uncertain. We propose heuristics for efficiently gaining such information about bit values, in the context of the \((1+1)\) EA. Along the way, we prove two useful general results. The first bounds the runtime for m parallel copies of a process. The second bounds the probability of having a non-optimal bit value at any given position when optimising a weakly monotonic function. Using these results, we prove bounds for the time it takes for our proposed heuristics to correctly identify bit values when the \((1+1)\) EA runs on monotonic and hidden subset problems.