This paper presents three heuristic algorithms for optimal polygonal approximation of digital planar curves. We use genetic algorithm (GA), improved genetic algorithm based on Pareto optimal solution (GAP) and tabu search (TS) to obtain a near optimal polygonal approximation. Compared to the famous Teh-Chin algorithm, our algorithms have obtained the approximated polygons with less number of vertices and less approximation error. Compared to the dynamic programming algorithm, the processing time of our algorithms are much less.