How to fix 'Android is starting' optimization on every boot? I recently updated to Lollipop on a Moto G (1st Gen). 

It was running a bit slow, so I wiped by cache then performed a factory reset as recommended.

I now receive the 'Android is starting optimising app xx of xx' every time I boot. 

Obviously not life and death, but it's annoying to have to wait 10 minutes for every reboot. 

Is this a known issue and is there any way to fix this?
I just had the same exact issue on the same exact phone. After doing some digging it seems like this happens when Android has a problem optimizing one or more apps, so it stubbornly retries all of them. So I uninstalled apps one-by-one and rebooted, and the problem went away after uninstalling SuperSU.

Not wanting to leave my phone unrooted, I noticed I had installed the latest SuperSU (2.79 SR3), so I went here and downloaded the latest stable release (2.79):

https://forum.xda-developers.com/apps/supersu

After installing it I no longer had any issues.

During my troubleshooting I also cleared the cache, although I'm not sure if it helped or not:


Boot to recovery
For the Moto G 1st generation:


Power off the phone
Press and hold volume down button, press and hold power button, wait for about 4 seconds and then release both buttons
Press volume down to select Recovery and press volume up to boot to recovery

Clear the cache
For the Moto G 1st generation (stock recovery):


If you get to a screen that says "No command"


Press and hold the power button for 2-3 seconds
Without releasing power button, press volume up button and release the volume up button
Release the power button

Use the volume buttons to move down to wipe cache partition and select it with the power button
Wait for it to finish (it can take a while) then reboot