Finding globally optimal structures of nanoclusters is critically important to understand their physicochemical properties but remains prohibitively expensive even with comparatively efficient density functionals. Semi-empirical methods such as density functional tight-binding (DFTB), on the other hand, offer a better accuracy-efficiency trade-off but require suitable parametrization. In the present work, we present a largely automatic scheme where, starting from initial guesses based on bulk properties, the atomic confinement, and repulsive potentials are further refined so as to accurately represent the potential energy landscapes of 13-and 55-atom nanoclusters of the late transition metals (Ni, Cu, Pd, Ag, Pt, and Au). With the exception of Ni-13, Ni-55, Cu-55, and Ag-55, low-symmetry (often disordered) structures are found to be preferred over the symmetric icosahedral arrangement. Similar to what has been previously reported for Au-55 the lowest-energy Pt-55 structures also appear to contain small cavities below the outer shell.