By specifying objective functions defining the two bands to be notched with high roll-off criteria (ROCs), optimization searching for the best fragment-type etch pattern on ultra-wideband (UWB) antenna is implemented by using multi-objective optimization. The optimization with too many objective functions requires special treatment to improve the searching efficiency. In this design, two slits are preset on appropriate positions on different sides of the UWB radiator to constrain the decision space for etch pattern searching and yield two initial notched bands to speed up the optimization. For demonstration, a UWB patch antenna is designed with dual-band notches of ROC = 0.63 at WiMAX band and ROC = 0.65 at WLAN band. Both the simulation and measurement results indicate that there is significant improvement of the selectivity of the dual-band notches.