n = 4;
lines = n (n - 1)/2;
optimalelements = n - 1;
gridpoints = 100;
grid = Round[Sqrt[gridpoints]];
fitness[x2_, y2_, x3_, y3_, x4_, y4_] :=
  (Clear[fitness, points, linepoints, d, c, penalty, threepoints,
    threetest, fourpoints, fourtest, p];
   points = {{0, 0}, {x2, y2}, {x3, y3}, {x4, y4}};
   linepoints = Subsets[points, {2}];
   d = EuclideanDistance @@@ linepoints;
   c = Sort[Tally[d][[All, 2]]];
   penalty = Total[Abs[Differences[c]]] - Length[c];
   If [c == Range[optimalelements], penalty = penalty + 1];
   p = penalty);
{sol, pts} = Reap[
   NMaximize[{fitness[x2, y2, x3, y3, x4, y4], 0 <= x2 <= grid,
     0 <= y2 <= grid, 0 <= x3 <= grid, 0 <= y3 <= grid,
     0 <= x4 <= grid,
     0 <= y4 <= grid}, {{x2, 0, grid}, {y2, 0, grid}, {x3, 0,
      grid}, {y3, 0, grid}, {x4, 0, grid}, {y4, 0, grid}}, Integers,
    Method -> {"SimulatedAnnealing", "SearchPoints" -> 1,
      "PerturbationScale" -> 1, "RandomSeed" -> 1},
    EvaluationMonitor :> Sow[{{x2, y2}, {x3, y3}, {x4, y4}, c, p}]]] //
   AbsoluteTiming

Out[7] {0.865882, {{-6., {x2 -> 5, y2 -> 6, x3 -> 2, y3 -> 4, x4 -> 7,
    y4 -> 4}}, {{{{0, 4}, {0, 4}, {2, 6}, {1, 1, 1, 1, 1,
      1}, -6}, {{0, 6}, {0, 2}, {4, 5}, {1, 1, 1, 1, 1, 1}, -6}, {{2,
      6}, {0, 4}, {4, 8}, {1, 1, 1, 1, 1, 1}, -6}, {{1, 6}, {0,
      2}, {4, 9}, {1, 1, 1, 1, 1, 1}, -6}, {{3, 7}, {1, 4}, {3,
      7}, {1, 1, 1, 1, 1, 1}, -6}, {{1, 9}, {2, 5}, {2, 7}, {1, 1, 1,
      1, 1, 1}, -6}, {{5, 10}, {4, 7}, {0, 4}, {1, 1, 1, 1, 1,
      1}, -6}...etc