Optimization of Discrete Problems using Artificially Smoothed Objective Function and Sectioning Method

摘要

One may apply a global search algorithm like GA (genetic algorithm) in stepwise problems; however, the gradient method is difficult to apply because of the jump in the objective function at the boundary between each section. For rapid computation through the adaptation of the gradient method in a stepwise problem, the objective function could be modified to an artificially continuous function for a large-sized problem accepting the risk of local convergence. The artificially continuous objective function exhibits poor performance with a global search algorithm like GA. In this study, a new method of modifying the objective function to an artificially smoothed function is proposed, and its effectiveness is tested. These artificially smoothed objective functions have no discontinuity with respect to the continuous variable of discrete condition; thus, they can be readily applied to gradient methods. The method of an artificially smoothed objective function does not exhibit any certain defect occurring in the method of the artificially continuous objective function. Its performance is almost the same as that of the original stepwise objective function, which results successfully for any global search. Finally, the sectioning method is proposed which can search in different densities along variables according to the behavior of objective function to reduce computational time with the order 10 or 100.