This paper presents a Coevolutionary Structure-Redesigned-Based Bacteria Foraging Optimization (CSRBFO) based on the natural phenomenon that most living creatures tend to cooperate with each other so as to fulfill tasks more effectively. Aiming at lowering computational complexity while maintaining the critical search capability of standard bacterial foraging optimization (BFO), we employ a general loop to replace the nested loop and eliminate the reproduction step of BFO. Hence, the proposed CSRBFO only consists of two main steps: (1) chemotaxis and (2) elimination & dispersal. A coevolutionary strategy by which all bacteria can learn from each other and search for optima cooperatively is incorporated into the chemotactic step to accelerate convergence and facilitate accurate search. In the elimination & dispersal step, the three-stage evolutionary strategy with different learning methods for maintaining diversity is studied. An evaluation of the convergence status is then added to determine whether bacteria should move on to the next stage or not. The combination of coevolutionary strategy and convergence status evaluation is expected to balance exploration and exploitation. Experimental results comparing seven well-known heuristic algorithms on 24 benchmark functions demonstrate that the proposed CSRBFO outperforms the comparison algorithms significantly in most of the cases.