Here are results from 1000 iterations for the same matrix:

Robinson matrix 500x500

iterations: 1000

average spearman rank correlation with known order: 0.9999475903183612

its standsrd deviation: 0.0007589340316943732

proportion of seriated matices being robinson: 0.988

proportion of perfect recoveries of known ordeing: 0.988

proportion of perfect position recoveries: 0.994698

=== Total time: 127h18m33.066058s ===

I have even better solution,

it is here:

https://www.researchgate.net/publication/259885785_Seriation500.2.tar

Here are the best so far results from 1000 iterations of seriation for pre-Robinson matrix:

Robinson matrix 500x500

iterations: 1000

average spearman rank correlation with known order: 0.9999992081888328

its standard deviation: 2.5039267652515825e-05

proportion of seriated matices being robinson: 0.999

proportion of perfect recoveries of known ordeing: 0.999

proportion of perfect position (rank) recoveries: 0.999792

total time: 204h41m39.906347s

Data Seriation500.2.tar