After upgrading to Android Studio 3.1 this error started happening frequently when attempting to deploy an application or run unit/UI tests. Apparently Android Studio is attempting to use a cached apk that hasn’t been generated.

Workaround
Edit the build configuration using the drop down at the top of Android Studio:

Add “Gradle-aware Make” to the “Before Launch” section using the + button:

Leave the text box empty and press the OK button:

Run the job again. Android Studio should generate the missing apk and run the job successfully.