Large Language Models (LLMs) are increasingly deployed in adversarial environments, yet current automatic prompt optimization methods often suffer from "shortcut learning"—overfitting to specific samples rather than learning generalizable principles. We argue that, compared to scalar reward optimization or few-shot enumeration alone, the interpretability of language offers a useful medium for inducing robust decision logic. To study this, we introduce PROSE, a robust prompt optimizer that uses semantic reflection and multi-objective evolution to reduce over-reliance on enumerated examples. Facing adversarial tasks, PROSE employs an operational proxy for explicit case enumeration as an additional optimization objective. By exploring the Pareto frontier between performance and this proxy, it adds a regularization signal against sample fitting and favors more reusable rule descriptions. It employs ensemble-based de-biasing strategies and a semantic greedy selection mechanism to reduce inductive bias and premature "semantic collapse," while leveraging LLM-based reflection to summarize concise, high-level rules from failure patterns. Across the evaluated benchmarks, PROSE achieves higher average performance than the strongest baseline by up to 14.6 percentage points in accuracy on Short-Text and up to 11.84 percentage points in F1 score, while showing stronger held-out content-category generalization and reducing the F1 degradation from 29.7 points for GEPA to 13.0 points.