Rational User — A Sufficient Condition for Global Convergence in Interactive Evolutionary Computation
HAO Guo-Sheng1,2, HUANG Yong-Qing1,3, ZHANG Yong2, YAN Jun-Rong1
1.School of Computer Science and Technology, Xuzhou Normal University, Xuzhou 2211162. School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 2210083. Institute of Computer Network Systems, Hefei University of Technology, Hefei 230009
Abstract：In interactive evolutionary computation (IEC), the relationship between user evaluation and user preference is an important factor of the convergence. Firstly, based on the dominated relationship between user evaluation and user preference, four kinds of users in IEC are put forward: absolute rational user, limited rational user, limited nonrational user and absolute nonrational user. Secondly, four theorems about the global convergence of IEC are proved. They illustrate the idea that the rational user is a sufficient condition for the global convergence of IEC. The theorems also point out that two kinds of elitist preservation strategies are necessary for the global convergence of IEC: fitness elitist preservation and satisfaction elitist preservation. Finally, the experimental results validate the above conclusion and show that it is a sufficient condition that as long as the user keeps rational, the algorithm convergence is ensured when other conditions are ready for the convergence.
[1] Kita H, Sano Y. Genetic Algorithms for Optimization of Noisy Fitness Functions and Adaptation to Changing Environments [EB/OL]. [2006-03-05]. http://www.smapip.is.tohoku.ac.jp/~smapip/ 2003/hayashibara/proceedings/HajimeKita.pdf [2] Büche D, Stoll P, Dornberger R, et al. Multi-Objective Evolutionary Algorithm for the Optimization of Noisy Combustion Processes. IEEE Trans on System, Man and Cybernetics, 2002, 32(4): 460-473 [3] Takagi H. Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evolution. Proc of the IEEE, 2001, 89(9): 1275-1296 [4] Kim H S, Cho S B. Application of Interactive Evolutionary Computation to Fashion Designs. Engineering Applications of Artificial Intelligence, 2000, 13(6): 635-644 [5] Takagi H, Kishi K. On-line Knowledge Embedding for an Interactive EC-Based Montage System // Proc of the 3rd International Conference on Knowledge-Based Intelligent Information Engineering Systems. Adelaide, Australia, 1999: 280-283 [6] Iwasaki T, Kimura A, Todoroki Y, et al. Interactive Virtual Aquarium // Proc of the 5th Annual Conference of the Virtual Reality Society of Japan. Gifu, Japan, 2000: 141-144 [7] Wang Jiachuan, Terpenny J. Interactive Evolutionary Solution Synthesis in Fuzzy Set-Based Preliminary Engineering Design. Journal of Intelligent Manufacturing, 2003, 14(2): 153-167 [8] Dozier G. Evolving Robot Behavior via Interactive Evolutionary Computation from Real-World to Simulation // Proc of the 16th ACM Symposium on Applied Computing. Las Vegas, USA, 2001: 340-344 [9] Guo Dongwei, Liu Dayou, Zhou Chunguang, et al. Dynamic Analysis of GA's Constringency and Its Application. Journal of Computer Research and Development, 2002, 39(2): 225-230 (in Chinese) (郭东伟,刘大有,周春光,等.遗传算法收敛性的动力学分析及其应用.计算机研究与发展, 2002, 39(2): 225-230) [10] He Lin, Wang Kejun, Li Guobin, et al. The Discussion about the Paper “The Analysis of Global Convergence and Computational Efficiency for Genetic Algorithm”. Control Theory and Applications, 2001, 18(1): 142-145 (in Chinese) (何 琳,王科俊,李国斌,等.关于“遗传算法的全局收敛性和计算效率分析”一文的商榷.控制理论与应用, 2001, 18(1): 142-145) [11] Yu Zhigang, Song Shenmin, Duan Guangren. On the Mechanism and Convergence of Genetic Algorithm. Control and Design, 2005, 20(9): 971-980 (in Chinese) (于志刚,宋申民,段广仁.遗传算法的机理与收敛性研究.控制与决策, 2005, 20(9): 971-980) [12] Liu Yong, Kang Lishan, Chen Yuping. Nonnumeric Parallel Algorithms (II)— Genetic Algorithm. Beijing, China: Scientific Press, 1995: 6-10 (in Chinese) (刘 勇,康立山,陈毓屏.非数值并行算法(二)——遗传算法.北京:科学出版社, 1995: 6-10) [13] Wang Xiaoping, Cao Liming. Genetic Algorithm and Its Theory, Application and Realization. Xi'an, China: Xi'an Jiaotong University Press, 2003 (in Chinese) (王小平,曹立明.遗传算法理论、应用与软件实现.西安:西安交通大学出版社, 2003) [14] Hao Guosheng. Theory and Application of Interactive Genetic Algorithm. Master Dissertation. Xuzhou, China: China University of Mining and Technology. College of Information and Electricity, 2005 (in Chinese) (郝国生.交互式遗传算法理论与应用.硕士学位论文.徐州:中国矿业大学.信息与电气工程学院, 2005) [15] Hao Guosheng, Shi Youqun, Huang Yongqing, et al. Interactive Evolutionary Computation with Fitness Noise and Its Convergence Robustness. Journal of Software, 2007, 18(9): 2183-2193 (in Chinese) (郝国生,史有群,黄永青,等.交互式进化计算的适应值噪声及收敛鲁棒性.软件学报, 2007, 18(9): 2183-2193) [16] Wang Zhengzhi, Bo Tao. Evolutionary Computation. Changsha, China: National University of Defense Science Press, 2000: 26-162 (in Chinese) (王正志,薄 涛.进化计算.长沙:国防科技大学出版社, 2000: 26-162) [17] Hao Guosheng, Zhang Yong, Zhang Jianhua, et al. Interactive Genetic Algorithm Based on Extinction Mechanism. Control Theory and Applications, 2006, 23(5): 665-670 (in Chinese) (郝国生,张 勇,张建化,等.基于灭绝机制的交互式遗传算法.控制理论与应用, 2006, 23(5): 665-670)
2008, Vol. 21 
