Can't stop ads from coming up.

Hello,

I have a Samsung Galaxy S5. When I turn on my phone, ads appear. This is not associated with Chrome, as I don't start any browsers. There is no way to suppress it as it keeps coming up when I turn my phone on, or when the phone goes dormant for awhile. I appears I have some malware on the phone, but I can't seem to remove it. I have tried some free-ware ad removal/malware removal apps but they don't work. Can you help?