The random swapping approach (simulated annealing with extremely low temperature) yields to a score of 64496 (20 minutes or so with Python and seed 0, ~60s with C++ and playing with seeds by a friend -.-). The permutation is
[213, 201, 367, 34, 368, 174, 249, 193, 159, 275, 225, 276, 194, 300, 191, 362, 113, 230, 158, 5, 4, 16, 352, 126, 265, 49, 224, 139, 187, 221, 228, 192, 156, 205, 204, 203, 241, 208, 214, 166, 67, 40, 52, 283, 124, 354, 133, 152, 173, 206, 235, 231, 237, 223, 217, 138, 118, 277, 361, 269, 344, 98, 258, 251, 30, 119, 122, 339, 309, 240, 245, 26, 226, 242, 232, 218, 110, 172, 86, 282, 297, 137, 21, 146, 62, 29, 293, 189, 171, 210, 84, 250, 136, 3, 304, 335, 154, 292, 78, 11, 266, 116, 164, 129, 148, 144, 195, 327, 306, 337, 9, 47, 168, 120, 128, 259, 261, 323, 254, 121, 200, 183, 256, 246, 85, 72, 305, 77, 76, 255, 336, 55, 46, 89, 73, 341, 100, 294, 145, 163, 87, 37, 185, 199, 15, 313, 88, 268, 264, 273, 69, 59, 44, 2, 106, 303, 82, 149, 326, 197, 279, 111, 38, 366, 57, 329, 68, 340, 257, 334, 93, 295, 286, 353, 365, 298, 285, 364, 91, 92, 90, 316, 252, 19, 165, 342, 125, 274, 176, 143, 239, 288, 95, 96, 324, 325, 28, 212, 253, 81, 79, 80, 318, 94, 299, 71, 291, 64, 132, 23, 278, 338, 308, 160, 7, 115, 247, 347, 147, 271, 188, 281, 272, 280, 155, 35, 349, 157, 177, 180, 202, 108, 350, 345, 97, 51, 141, 284, 355, 179, 42, 33, 70, 99, 45, 109, 178, 181, 103, 207, 220, 102, 211, 209, 196, 127, 41, 346, 351, 359, 320, 311, 13, 43, 287, 328, 357, 83, 310, 12, 161, 135, 131, 360, 39, 302, 1, 322, 123, 167, 6, 117, 31, 330, 356, 74, 75, 151, 104, 262, 289, 296, 140, 101, 236, 312, 343, 150, 348, 56, 234, 27, 14, 114, 331, 260, 314, 17, 54, 321, 105, 263, 130, 20, 186, 190, 63, 22, 162, 134, 363, 333, 301, 0, 169, 170, 175, 10, 112, 317, 61, 50, 248, 18, 315, 60, 32, 222, 244, 290, 48, 36, 307, 184, 58, 233, 238, 229, 227, 219, 153, 66, 319, 332, 358, 25, 53, 270, 182, 8, 216, 65, 24, 267, 107, 215, 142, 198, 243]
which corresponds to the symbol classes
['\blacktriangleright', '\nvDash', '\AE', '7', '\guillemotleft', '\perp',
'\bot', '\therefore', '\boxtimes', '\vdots', '\Leftarrow',
'\ddots', '\because', '\iddots',
'\multimap', '\L', '+', '\nearrow', '\boxplus', 'F', 'E', 'Q', '\checked', '\checkmark', '\rceil', 'h', '\uparrow',
'\div', '\doteq', '\longmapsto', '\mapsto', '\pitchfork', '\boxdot',
'\varsubsetneq', '\subsetneq', '\nsubseteq', '\nRightarrow', '\gtrless', '\triangleq', '\parr', '\Sigma', '\sum', 'k', '\sharp', '\#', '\sun', '\ast', '\star', '\not\equiv', '\neq', '\rightleftarrows',
'\rightleftharpoons', '\rightrightarrows', '\Longrightarrow', '\Rightarrow', '\pm',
'\dots', '\dotsc', '\aa', ']', '\ohm', '\Omega',
'\exists', '\ni', '3', '\}', '\pounds', '\mathscr{L}', '\mathcal{L}',
'\twoheadrightarrow', '\shortrightarrow', '\rightarrow', '\longrightarrow',
'\nrightarrow', '\rightharpoonup', '\hookrightarrow', '\cong', '\equiv',
'\Xi', '\diamondsuit', '\lozenge', '\diamond', 'V', '\vee', 'v', '2', '\sphericalangle', '\simeq', '\approx', '\gtrsim', '\nu', '\forall', '\triangleright',
'D', '\mathcal{D}', '\mathscr{D}',
'\barwedge', '\sqrt{}', '\iota', 'L', '\lfloor', '\{', '\coprod', '\amalg', '\sqcup', '\mp', '\between', '\mathds{E}', '\mathcal{F}', '\mathscr{F}', 'J', 'f', '\fint', '\S', '\mathsection', '\Im', '\nexists', '\mathfrak{X}', '\hbar', '\dag', '\nmid', '\vdash', '\notin', '\lightning', '\xi', '\zeta', '\mathcal{E}', '\varepsilon', '\epsilon', '\in', '\mathscr{E}', 'n', 'e', '\varrho', '\eta', '\mathscr{S}', '\int', '\square', '\sqcap', '\prod', '\Pi', '\pi', '\models', '\vDash', 'P', '\mathcal{P}', '\rho', '[', '\lceil', '\llbracket', '\Gamma', 'r', 'c', 'C', '\subset',
'\mathcal{C}', '\Lambda', '\wedge', '\mathds{C}', '\varpropto', '\infty', '\propto', '\alpha', '\ae', 'p', '\mathds{P}', '\gamma', '\mathscr{P}',
'\wp', '\mathscr{C}', '\varphi', '\triangledown', '\nabla', '\diameter',
'\o', '\varnothing', '\emptyset', '\O', '\phi', '\Phi', '\tau',
'\mathcal{T}', '\top', 'T', '\oint', '\celsius', '\%', '\rrbracket', '\frown', '\cap', '\curvearrowright', '\clubsuit', '\psi', '\Psi', '\mathbb{1}', '\mathds{1}', '1', '\trianglelefteq', '\ell', '\lambda',
'\kappa', '\varkappa', '\mathcal{X}', '\chi', '\vartriangle', '\Delta',
'\triangle', 'x', '\times', 'X', '\aleph', '\mathscr{H}', '\mathcal{H}',
'\rtimes', 'H', '\$', '\vartheta', '\astrosun', '\odot',
'\|', '\parallel', '\angle', '/', '\prime', '\circledcirc', '8', '\leftmoon',
'\ltimes', '\prec', '\preceq', '\sqsubseteq', '\subseteq', '\female',
'\venus', '\omega', 'j', '\setminus', '\backslash', '\Bowtie', '\bowtie',
'a', '6', '\delta', '\partial', 'd', '\supseteq', '\succ', '\succeq',
'\geq', '\geqslant', '\searrow', '\leq', '\leqslant', '\lesssim',
'\preccurlyeq', '\circledR', '\sigma', '\mars', '\male', '\mathbb{H}',
'\mathfrak{A}',
'\mathcal{N}', 'N', 'b', '\flat', '\mathds{N}', '\mathbb{N}', '\mu', '\mathcal{M}', 'M',
'\circledast', '\otimes',
'\oplus', '\ss', '\beta', '\mathcal{B}', 'B', '\mathfrak{S}', '\&',
'\with', 'G', '\copyright', '4', '\mathds{Q}', '\mathbb{Q}', '\theta',
'\Theta', '\ominus', '<', '\langle', '\heartsuit', '\blacksquare',
'\bullet', '\cdot', '\circlearrowright', '\mathcal{O}', '\degree',
'\circ', '\fullmoon', 'o', '\circlearrowleft', '0', 'O',
'\mathbb{R}', '\mathds{R}', '\Re', '\mathcal{R}', 'R',
'm', '\mathfrak{M}', '>', '\rangle', '\cup', 'U', '\sim', '\backsim', 'w', 'W', '\lhd', '\triangleleft', '\AA', '\mathscr{A}', '\mathcal{A}', 'A', '\varoiint', '\oiint', '\asymp', 'K', '-', '\mathcal{U}', 'u', 'i', '\varpi', 'S',
'\mathcal{S}', 's', '5', '\leftarrow', '\mapsfrom', '\neg', 'g', '9',
'\mathcal{G}', '\dashv', 'q',
'\leadsto', '\rightsquigarrow', '\leftrightarrow', '\Leftrightarrow', '\Longleftrightarrow',
'\wr', 'z', '\mathcal{Z}', '\mathds{Z}', '\mathbb{Z}', 'Z',
'l', '|', '\mid', 'I', '\downarrow',
'y', 'Y', '\rfloor', '\supset', '\Downarrow', '\uplus', '\Vdash', '\upharpoonright']
As expected, this method automatically finds groups of classes which are similar, such as 'D', '\mathcal{D}', '\mathscr{D}'.
It leads to the following confusion matrix:
Thoughs about good solutions / minima
This optimization problem will most likely get the best results if all groups of similar classes are together. For this dataset, the groups are D-shaped, O-shaped, arrow-shaped, ...
For a good classifier, it is expected that there are many errors between members of a group and few (even none) between groups. Hence the ordering of groups does not matter (much).
If the classifier can distinguish many classes really well, a lot of groups exist. If there are $k$ groups, there will be $k!$ solutions to the confusion matrix optimization problem which will have almost the same score. For the HASYv2 dataset and the CNN classifier I expect there to be at least 50 groups (hence $50! \approx 10^{64}$ similar solutions which are all close to the minima / minimum.
