Based on the inclusion monotone property of intervalfunctions, a global optimization method is proposed to compute the upper andlower bounds of the natural frequencies of uncertain structures. Twocomputational models are presented, in which the interaction among uncertainparameters in the stiffness matrix and the mass matrix was neglected ortaken into consideration respectively. A real code genetic algorithm is usedto solve these optimization models. A monotone analysis method, which canobtain the exact frequencies' intervals of shear-frame structures andmulti-mass-spring systems, is introduced to illustrate the effectiveness ofthe proposed method. Numerical examples showed that the interaction amongthe uncertain parameters in the stiffness matrix and the mass matrix shouldbe taken into consideration and the results of interval perturbation methodcould be improved distinctly. The method to form the interval stiffnessmatrix and the interval mass matrix firstly and then consider theeigenvalues' intervals of the general interval matrix eigenvalue problemabout the obtained interval matrices as the solution of the uncertainstructures may enlarge the solution domain of the original problem.