This paper presents a study on topology optimization of novel material microstructural configurations to achieve directional elastic wave propagation through maximization of partial band gaps. A waveguide incorporating a periodic-microstructure material may exhibit different propagation properties for the plane elastic waves incident from different inlets. A topology optimization problem is formulated to enhance such a property with a gradient-based mathematical programming algorithm. For alleviating the issue of local optimum traps, the random morphology description functions (RMDFs) are introduced to generate random initial designs for the optimization process. The optimized designs finally converge to the orderly material distribution and numerical validation shows improved directional propagation property as expected. The utilization of linear two-dimension phononic crystal with efficient partial band gap is suitable for directional propagation with a broad frequency range.