This paper describes the design optimization of a sport shoe sole structure by evolutionary computation coupled with eigenmode analysis based on the finite element method. A genetic algorithm assisted by the Kriging response surface model was used for global and efficient optimization. The present study implemented two optimization cases based on equivalent design problem formulations: the single-objective constrained problem and multi-objective non-constrained problem. The optimization described here provided a midsole structure with optimal material properties, in which the elastic modulus should be reduced in rearfoot→midfoot→forefoot-centre domains sequentially as the midsole weight becomes lighter. In addition, a comparison of the results between the two cases yielded insight into constraint handling for faster convergence in midsole design optimization by evolutionary computation.