Hi,
I would say your biggest problem is leads, everyone of them acting as aerials to switching noise.
Everyone of your 595's should have a 0.1uF bypass capacitor soldered as close to the IC, across the Vcc to gnd pins.
The electro cap will help supply dips, but not switching noise.
Also here you have input wiring to the relays in amongst the relays output wiring, this tends to defeat the idea of isolation with the opto and relay.
You should have all those relay boards turned 90degrees, so ALL inputs come up from below and ALL relay outputs got out the top.
Keep the 595 wiring as neat as possible.
I think you will find that some of your problems are that you are still in prototype stage and those jumper/connector wires are not the best when minimising wiring cross-talk and reliable connections.
Tom... 