One promising approach for pixel-wise semantic segmentation is based on higher-order Conditional Random Fields (CKFs). We aim to selectively choose segments for the higher-order CRFs in semantic segmentation. To this end, we formulate the selection as an optimization problem. We propose three optimization criteria in relation to the selected segments, namely: a) averaged goodness, b) coverage area and c) non-overlapped area. Essentially, we desire to have best segments with maximum coverage area and maximum non-overlapped area. We apply two evolutionary optimization algorithms, namely: the genetic algorithm (GA) and the particle swarm optimization (PSO). The goodness of segments is estimated using the Latent Dirichlet Allocation approach. Experiment results show that semantic segmentation with GA-or-PSO-selected segments yields competitive semantic segmentation accuracy in comparison to that of naively using all segments. Moreover, the fewer number of segments used in semantic segmentation speeds up its computation time up to six times faster.