  Evolutionary algorithms (EAs) have found many successful real-world
applications, where the optimization problems are often subject to a wide range
of uncertainties. To understand the practical behaviors of EAs theoretically,
there are a series of efforts devoted to analyzing the running time of EAs for
optimization under uncertainties. Existing studies mainly focus on noisy and
dynamic optimization, while another common type of uncertain optimization,
i.e., robust optimization, has been rarely touched. In this paper, we analyze
the expected running time of the (1+1)-EA solving robust linear optimization
problems (i.e., linear problems under robust scenarios) with a cardinality
constraint $k$. Two common robust scenarios, i.e., deletion-robust and
worst-case, are considered. Particularly, we derive tight ranges of the robust
parameter $d$ or budget $k$ allowing the (1+1)-EA to find an optimal solution
in polynomial running time, which disclose the potential of EAs for robust
optimization.
