This paper presents a hybrid optimization algorithm which combines an external call type optimization method and a general stochastic iterative algorithm for the nonlinear integer programming with genetic algorithm (GA). GA can rapidly search the approximate global optimum under a complicated design environment such as a ship structure. Meanwhile it can handle optimization problems involving discrete design variables. In addition, there are many parameters that have to be set for GA which greatly affect the accuracy and calculation time of the optimum solution. However, the setting process is difficult for users, and there are no rules to decide these parameters. Therefore, to overcome these difficulties, the optimization of these parameters has been also conducted by using GA itself. It is proven using the trial function that the parameters are optimal. Finally, the verification of validity and usefulness of nonlinear integer programming is performed by applying this method to the compass deck of a ship where the vibration problem is frequently occurs.