In a solaceon city beside pokemon center, there is a man that give you a heart scale if you bring a pokemon that he want... or, you can search it trough the game!
You can either go to solaceon town and show the pokemon the news
guy asked for or you go underground they are quite common so it
won't be too hard.
You can go find some underground or as wobuffet33 said.
