This paper presents a new variant of the Harmony Search (HS) algorithm. This Hybrid Harmony Search (HHS) algorithm follows a new approach to improvisation: while retaining HS algorithm Harmony Memory and pitch adjustment functions, it replaces the HS algorithm randomization function with Global-best Particle Swarm Optimization (PSO) search and neighbourhood search. HHS algorithm performance is tested on six discrete truss structure optimization problems under multiple loading conditions. Optimization results demonstrate the excellent performance of the HHS algorithm in terms of both optimum solution and the convergence behaviour in comparison with various alternative optimization methods.