Try solving lots of problems. Categorize their difficulty using SA runtime. Trace solution quality over time while using SA. Try other cost functions. Try other algorithms.