A solution to combinatorial optimization problem of constructing optimal circulant networks with the minimum diameter under given degree and number of graph nodes is considered. The circulant networks and their different applications are the object of intense investigations. Under degree of a graph δ > 4 and large number of nodes it is necessary to develop new effective methods of the optimal circulant designs synthesis. The application to decision of given problem a heuristic algorithm and a genetic algorithm based on simulation of natural evolution process is considered. The comparison of the algorithms and their different versions of realization is obtained. The results of computer experiments and catalogues of optimal circulants with N > 1000 and δ > 4 are presented.