I suggest going to the desert on the continent below Estar and fighting cactuars. They don't give very much Exp but give 10 Ap each. While doing that, get Diablos to learn the Enc-None ability. That way no more random battles forever!!