Traffic Matrix (TM) is a representation of all traffic flows in a network. It is helpful for traffic engineering and network management. It contains the traffic measurement for all parts of a network and thus for larger network it is difficult to measure precisely. Link load are easily obtainable but they fail to provide a complete TM representation. Also link load and TM relationship forms an under-determined system with infinite set of solutions. One of the well known traffic models Gravity model provides a rough estimation of the TM. We have proposed a Genetic algorithm (GA) based optimization method to further the solutions of the Gravity model. The Gravity model is applied as an initial solution and then GA model is applied taking the link load-TM relationship as a objective function. Results shows improvement over Gravity model.