One strategy you can also try is to bring a Pokemon with the ability Synchronize, with the nature you want in the front of your party.
So for example:
• If you want a Relaxed Lugia, you'd bring a Relaxed nature Alakazam, with the ability Synchronize in the front of your party. It will have a 50% chance to have the same nature as the Alakazam.
This works also with any other Pokemon, and can help you catch Pokemon with good natures depending on how many Synchronizers you have.