Metaheuristic algorithm such as BAT algorithm is becoming a popular method in solving many hard optimization problems. This paper investigates the use of Bat algorithm in combination with Back-propagation neural network (BPNN) algorithm to solve the local minima problem in gradient descent trajectory and to increase the convergence rate. The performance of the proposed Bat based Back-Propagation (Bat-BP) algorithm is compared with Artificial Bee Colony using BPNN algorithm (ABC-BP) and simple BPNN algorithm. Specifically, OR and XOR datasets are used for training the network. The simulation results show that the computational efficiency of BPNN training process is highly enhanced when combined with BAT algorithm.