Genetic Algorithm to Draw a Graph? Position assignment problem
I don't think it is wise to use local search techniques. There are many (fast) methods which work pretty good for many classes of graphs. Of course you can also test local search methods.

A few comments:


  
  Number of intersecting edges should be minimal
  


Is your graph planar? If yes, there are many good methods for planar graphs (e.g. dominance drawings). 

Is it a general digraph? In this case a hierarchical approach may be suitable (more information later).


  
  All edges flow in one direction (i.e from left to right)
  


Does it contain cycles? If yes, this is not possible. 

A great source for graph drawing algorithms is Graph Drawing: Algorithms for the Visualization of Graphs.

In my opinion a good first approach to this problem is the hierarchical approach. Check the paper by Sugiyama et. al Methods for Visual Understanding of Hierarchical System Structures (chapter 9 in 1 describes such methods).

If you go with the local optimization methods, I would definitely use the initial configuration to start with (since it should be close to a good local optimum).