A Hillclimbing Technique Using Piecewise Cubic Approximation

摘要

Three distinct types of hillclimbing techniques are studied in this thesis. The first is variations of the conventional discrete search as proposed by Bocharov and Fel'dbaum. The second is Kushner's method. The third is the piecewise cubic method, which is developed herein. The last two methods operate by building a model from the measurements obtained. The concept of testing various hillclimbing methods on a relatively large number of randomly selected hills is proposed. A class of such hills is presented, the members of which are capable of exhibiting most of the troublesome features of practical hills. This concept is then applied to evaluate the performance of the three types of hillclimber with respect to five criteria: (1) Average minimal hill height; (2) Average number of measurements; (3) Average integral of the Index of Performance; (4) Reliability; and (5) Noise sensitivity. With regard to these criteria, experimental evidence via digital simulation is presented for the superiority of the two model building techniques over the Bocharov and Fel'dbaum methods. The piecewise cubic method is extended to two dimensions and a limited amount of experimental data is presented on its performance compared to the Bocharov and Fel'dbaum methods.