Since the phone syncs with iCloud, the contacts are now screwed up there, too.
The only way to get back where you were is if you exported your contacts to a file that is backed up on another drive, before running the AI app. Then you bring that data back in.
Too late now, but virtually any experienced user here will tell anyone they can to never use cleaners, optimizers, or whatever other garbage is out there. Cleaners in particular are dangerous as they can't know what's important to you and what isn't. And this app went out of its way to show how badly written it is by scrambling your contacts.