In Ambrette town, there is a path behind the Pokémon Centre, go to the right of it and you will find one Heart Scale.
In Cyllage City, go south along route 8 until you reach the stairs. Turn on the Dowsing Machine and a Heart Scale should be found around there.
Also, after getting the old rod from the guy in Ambrette Aquarium, go to the beach on route 8 and use it; all you will encounter is Luvdisc' (many of which are holding Heart Scales) - catch them or use Covet / Thief on them to obtain Heart Scales.
Note: Make sure the Pokémon using Covet / Thief has no held item when you are thieving the Heart Scales or else you will not obtain any.
Furthermore, smashing rocks (by using Rock Smash) is an additional method of finding Heart Scales.