Change the incentives of the patent office
Currently, the USPTO has all the incentives to accept just about anything as a patent. More patents accepted is seen as more productive; I believe applicants even have to pay more, once a patent is accepted, to actually get the patent, than if the patent is rejected.
Instead, ask full price to apply for a patent, and give back a small percentage if the patent is accepted. The incentive to apply for real patents instead of bullshit is not very important; the important part is that now the USPTO gets more money for rejecting a patent than for accepting it.