Optimal Contraction Theorem for Exploration-Exploitation Tradeoff in Search and Optimization

• Published in: IEEE transactions on systems, man and cybernetics. Part A, Systems and humans man and cybernetics. Part A, Systems and humans, 2009-05, Vol.39 (3), p.680-691
• Main Authors: Jie Chen, Jie Chen, Bin Xin, Bin Xin, Zhihong Peng, Zhihong Peng, Lihua Dou, Lihua Dou, Juan Zhang, Juan Zhang
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Computational efficiency; Convergence; Cost function; Educational technology; Evolutionary computation; Exploitation; exploration; global optimization; Machine learning; Machine learning algorithms; optimal contraction theorem; optimization hardness; Sampling methods; Testing
• ISSN: 1083-4427; 2168-2216; 1558-2426; 2168-2232
• DOI: 10.1109/TSMCA.2009.2012436

Global optimization process can often be divided into two subprocesses: exploration and exploitation. The tradeoff between exploration and exploitation ( T:Er&Ei ) is crucial in search and optimization, having a great effect on global optimization performance, e.g., accuracy and convergence speed of optimization algorithms. In this paper, definitions of exploration and exploitation are first given based on information correlation among samplings. Then, some general indicators of optimization hardness are presented to characterize problem difficulties. By analyzing a typical contraction-based three-stage optimization process, optimal contraction theorem is presented to show that T:Er&Ei depends on the optimization hardness of problems to be optimized. T:Er&Ei will gradually lean toward exploration as optimization hardness increases. In the case of great optimization hardness, exploration-dominated optimizers outperform exploitation-dominated optimizers. In particular, random sampling will become an outstanding optimizer when optimization hardness reaches a certain degree. Besides, the optimal number of contraction stages increases with optimization hardness. In an optimal contraction way, the whole sampling cost is evenly distributed in all contraction stages, and each contraction takes the same contracting ratio. Furthermore, the characterization of optimization hardness is discussed in detail. The experiments with several typical global optimization algorithms used to optimize three groups of test problems validate the correctness of the conclusions made by T:Er&Ei analysis.