Simulated Annealing Programming Using Effective Subtrees

シミュレーテッドアニーリング(SA)を木構造が扱えるように拡張したシミュレーテッドアニーリングプログラミング(SAP)という自動プログラミング手法が提案されている。従来のSAPにおける次状態生成では、ランダムに生成した部分木をランダムに選択した交換点に挿入する。本論文では、探索の効率化のために、ランダムに生成した部分木の他に、探索に有効な部分木を挿入する手法を提案する。Santa Fe trail問題およびSymbolic Regression問題に提案手法を適用した結果、提案手法が従来方法より効率的な探索を行うことができるとわかった。Simulated Annealing Programming (SAP), an automatic programming method, is an extension method of Simulated Annealing (SA) that allows SA to handle tree structures. In this method, the point to exchange is chosen randomly, and the subtree to insert is also generated randomly. In this paper, we propose the method that finds out effective subtrees in search and that uses them to generate subtree for inserting. The proposal method can perform search more efficiently than standard SAP in Santa Fe trail problem and Symbolic Regression problem