基于区间适应值交互式遗传算法的加权多输出高斯过程代理模型
|
摘要
融合了用户认知和智能评价的交互式遗传算法(Interactive genetic algorithm,IGA)是解决一类定性性能指标优化问题的有效方法,但是,评价不确定性和易疲劳性极大地限制了该算法解决实际问题的能力.基于用户已评价信息,采用合适的机器学习方法,构建用户认知代理模型是解决上述问题的常用方法之一.但是,现有研究成果均没有考虑用户评价不确定性对学习样本、代理模型的影响,以及模型拟合不确定性对基于适应值的进化操作有效性的影响.针对上述问题,本文提出基于加权多输出高斯过程(Gaussian process,GP)代理模型的交互式遗传算法.首先,在区间适应值评价模式下,提取学习样本的噪声特性,以确定相应学习样本对代理模型的影响度权重系数,构建两输出高斯过程代理模型;然后,利用代理模型提供的预测值及预测置信水平,给出一种新的个体适应值估计方法和个体选择方法;基于模型预测信息,实现模型更新管理.将所提算法分别应用于含噪函数和服装设计问题中,所得结果表明本文算法可更好地拟合和跟踪用户认知,减小对进化搜索的误导,更快找到用户满意解.
An interactive genetic algorithm(IGA), combining a user s intelligent evaluations with traditional genetic operators, is developed to optimize problems with aesthetic indicators. However, the evaluation uncertainties and burden greatly restrict the applications of IGA in complicated situations. Surrogate models constructed with appropriate machine learning methods have been successfully used to alleviate the user evaluation burden of IGAs. However, the uncertainties resulted from the user s evaluations and model s approximation are not taken into account in the existing research. To tackle such problems, a weighted multi-output Gaussian process(GP) is proposed to build a surrogate model to improve the performance of IGA. First, the evaluation noise is defined when an individual s fitness is represented as an interval.With the evaluation noise, the contribution of a training sample to construct the surrogate model is calculated, and used to train a GP with two outputs to approximate the upper and lower values of the interval fitness. A novel fitness approximation method is proposed by combining the predicted value with its associated predictive confidence. Based on the predictive confidence, the surrogate model is well managed during the evolution. The proposed algorithm is used to optimize a benchmark function and a real-world fashion design case to experimentally demonstrate that the surrogate model outperforms others in prediction fitting and tracking user s evaluations, and is beneficial to less misleading the search and faster finding the optima.
An interactive genetic algorithm(IGA), combining a user s intelligent evaluations with traditional genetic operators, is developed to optimize problems with aesthetic indicators. However, the evaluation uncertainties and burden greatly restrict the applications of IGA in complicated situations. Surrogate models constructed with appropriate machine learning methods have been successfully used to alleviate the user evaluation burden of IGAs. However, the uncertainties resulted from the user s evaluations and model s approximation are not taken into account in the existing research. To tackle such problems, a weighted multi-output Gaussian process(GP) is proposed to build a surrogate model to improve the performance of IGA. First, the evaluation noise is defined when an individual s fitness is represented as an interval.With the evaluation noise, the contribution of a training sample to construct the surrogate model is calculated, and used to train a GP with two outputs to approximate the upper and lower values of the interval fitness. A novel fitness approximation method is proposed by combining the predicted value with its associated predictive confidence. Based on the predictive confidence, the surrogate model is well managed during the evolution. The proposed algorithm is used to optimize a benchmark function and a real-world fashion design case to experimentally demonstrate that the surrogate model outperforms others in prediction fitting and tracking user s evaluations, and is beneficial to less misleading the search and faster finding the optima.
引文
1 Holland J H.Adaptation in Natural and Artificial Systems.Michigan,USA:The University of Michigan Press,1975
2 Kim H S,Cho S B.Application of interactive genetic algorithm to fashion design.Engineering Applications of Artificial Intelligence,2000,13(6):635-644
3 Simons C L,Parmee I C.Elegant object-oriented software design via interactive,evolutionary computation.IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2012,42(6):1797-1805
4 Solomon C J,Gibson S J,Mist J J.Interactive evolutionary generation of facial composites for locating suspects in criminal investigations.Applied Soft Computing,2013,13(7):3298-3306
5 Takagi H.Interactive evolutionary computation:fusion of the capabilities of EC optimization and human evaluation.Proceedings of the IEEE,2001,89(9):1275-1296
6 Liu Xiao-Lu,Chen Ying-Guo,He Ren-Jie,Chen Ying-Wu.Application of Kriging surrogate model to optimization of earth observation satellite system.Acta Automatica Sinica,2012,38(1):120-127(刘晓路,陈盈果,贺仁杰,陈英武.Kriging代理模型在对地观测卫星系统优化中的应用.自动化学报,2012,38(1):120-127)
7 Sun Xiao-Yan,Ren Jie,Gong Dun-Wei.Interval-fitness interactive genetic algorithms with varying population size based on semi-supervised learning.Control Theory and Applications,2011,28(5):610-618(孙晓燕,任洁,巩敦卫.基于半监督学习的变种群规模区间适应值交互式遗传算法.控制理论与应用,2011,28(5):610-618)
8 Li Hong-Wei,Liu Yang,Lu Han-Qing,Fang Yi-Kai.Gaussian processes classification combined with semi-supervised kernels.Acta Automatica Sinica,2009,35(7):888-895(李宏伟,刘扬,卢汉清,方亦凯.结合半监督核的高斯过程分类.自动化学报,2009,35(7):888-895)
9 Gong D W,Guo G S.Interactive genetic algorithms with interval fitness of evolutionary individuals.Dynamics of Continuous.Discrete and Impulsive Systems,Series B,2007,14 (S2):446-450
10 Biles J A,Anderson P G,Loggi L W.Neural network fitness functions for a musical IGA.In:Proceedings of the1996 International Symposium on Intelligent Industrial Automation and Soft Computing.Berlin,Germany:Springer,1996.39-44
11 Zhou Yong,Gong Dun-Wei,Hao Guo-Sheng,Guo Yi-Nan,Sun Xiao-Yan.Neural network based phase estimation of individual fitness in interactive genetic algorithm.Control and Decision,2005,20(2):234-236,240(周勇,巩敦卫,郝国生,郭一楠,孙晓燕.交互式遗传算法基于NN的个体适应度分阶段估计.控制与决策,2005,20(2):234-236,240)
12 Wang S F,Wang X F,Takagi H.User fatigue reduction by an absolute rating data-trained predictor in IEC.In:Proceedings of the 2006 IEEE Congress on Evolutionary Computation.Vancouver,B.C.,Canada:IEEE,2006.2195-2200
13 Llor`a X,Sastry K,Goldberg D E,Gupta A,Lakshmi L.Combating user fatigue in iGAs:Partial ordering,support vector machines,and synthetic fitness.In:Proceedings of the 2005 Conference on Genetic and Evolutionary Computation.Washington DC:IEEE,2005.1363-1370
14 Ecemis I,Bonabeau E,Ashburn T.Interactive estimation of agent-based financial markets models:modularity and learning.In:Proceedings of the 2005 Genetic and Evolutionary Computation Conference.New York:ACM,2005.1897-1904
15 Gong Dun-Wei,Ren Jie,Sun Xiao-Yan.Neural network surrogate models of interactive genetic algorithms with individual s interval fitness.Control and Decision,2009,24 (10):1522-1525,1530(巩敦卫,任洁,孙晓燕.区间适应值交互式遗传算法神经网络代理模型.控制与决策,2009,24(10):1522-1525,1530)
16 Wang K,Bui V,Petraki E,Abbass H A.Evolving story narrative using surrogate models of human judgement.Advances in Intelligent Systems and Computing,2013,208(1):653-661
17 Sun X Y,Gong D W,Ma X P.Directed fuzzy graph-based surrogate model-assisted interactive genetic algorithms with uncertain individual s fitness.In:Proceedings of the 2009IEEE Congress on Evolutionary Computation.Trondheim:IEEE,2009.2395-2402
18 Boyle P,Frean M.Multiple Output Gaussian Process Regression.Technical Report CS-TR-05/2,School of Mathematical and Computing Sciences,Victoria University of Wellington,Wellington,New Zealand,2005
19 Sun X Y,Gong D W,Jin Y C,Chen S S.A new surrogateassisted interactive genetic algorithm with weighted semisupervised learning.IEEE Transactions on System,Man,and Cybernetics:Part B,2013,43(2):685-698
20 Multi-output Gaussian Process,Matlab Software[Online],available:http://staffwww.dcs.shef.ac.uk/people/N.Lawrence/multigp/,March 25,2013
2 Kim H S,Cho S B.Application of interactive genetic algorithm to fashion design.Engineering Applications of Artificial Intelligence,2000,13(6):635-644
3 Simons C L,Parmee I C.Elegant object-oriented software design via interactive,evolutionary computation.IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2012,42(6):1797-1805
4 Solomon C J,Gibson S J,Mist J J.Interactive evolutionary generation of facial composites for locating suspects in criminal investigations.Applied Soft Computing,2013,13(7):3298-3306
5 Takagi H.Interactive evolutionary computation:fusion of the capabilities of EC optimization and human evaluation.Proceedings of the IEEE,2001,89(9):1275-1296
6 Liu Xiao-Lu,Chen Ying-Guo,He Ren-Jie,Chen Ying-Wu.Application of Kriging surrogate model to optimization of earth observation satellite system.Acta Automatica Sinica,2012,38(1):120-127(刘晓路,陈盈果,贺仁杰,陈英武.Kriging代理模型在对地观测卫星系统优化中的应用.自动化学报,2012,38(1):120-127)
7 Sun Xiao-Yan,Ren Jie,Gong Dun-Wei.Interval-fitness interactive genetic algorithms with varying population size based on semi-supervised learning.Control Theory and Applications,2011,28(5):610-618(孙晓燕,任洁,巩敦卫.基于半监督学习的变种群规模区间适应值交互式遗传算法.控制理论与应用,2011,28(5):610-618)
8 Li Hong-Wei,Liu Yang,Lu Han-Qing,Fang Yi-Kai.Gaussian processes classification combined with semi-supervised kernels.Acta Automatica Sinica,2009,35(7):888-895(李宏伟,刘扬,卢汉清,方亦凯.结合半监督核的高斯过程分类.自动化学报,2009,35(7):888-895)
9 Gong D W,Guo G S.Interactive genetic algorithms with interval fitness of evolutionary individuals.Dynamics of Continuous.Discrete and Impulsive Systems,Series B,2007,14 (S2):446-450
10 Biles J A,Anderson P G,Loggi L W.Neural network fitness functions for a musical IGA.In:Proceedings of the1996 International Symposium on Intelligent Industrial Automation and Soft Computing.Berlin,Germany:Springer,1996.39-44
11 Zhou Yong,Gong Dun-Wei,Hao Guo-Sheng,Guo Yi-Nan,Sun Xiao-Yan.Neural network based phase estimation of individual fitness in interactive genetic algorithm.Control and Decision,2005,20(2):234-236,240(周勇,巩敦卫,郝国生,郭一楠,孙晓燕.交互式遗传算法基于NN的个体适应度分阶段估计.控制与决策,2005,20(2):234-236,240)
12 Wang S F,Wang X F,Takagi H.User fatigue reduction by an absolute rating data-trained predictor in IEC.In:Proceedings of the 2006 IEEE Congress on Evolutionary Computation.Vancouver,B.C.,Canada:IEEE,2006.2195-2200
13 Llor`a X,Sastry K,Goldberg D E,Gupta A,Lakshmi L.Combating user fatigue in iGAs:Partial ordering,support vector machines,and synthetic fitness.In:Proceedings of the 2005 Conference on Genetic and Evolutionary Computation.Washington DC:IEEE,2005.1363-1370
14 Ecemis I,Bonabeau E,Ashburn T.Interactive estimation of agent-based financial markets models:modularity and learning.In:Proceedings of the 2005 Genetic and Evolutionary Computation Conference.New York:ACM,2005.1897-1904
15 Gong Dun-Wei,Ren Jie,Sun Xiao-Yan.Neural network surrogate models of interactive genetic algorithms with individual s interval fitness.Control and Decision,2009,24 (10):1522-1525,1530(巩敦卫,任洁,孙晓燕.区间适应值交互式遗传算法神经网络代理模型.控制与决策,2009,24(10):1522-1525,1530)
16 Wang K,Bui V,Petraki E,Abbass H A.Evolving story narrative using surrogate models of human judgement.Advances in Intelligent Systems and Computing,2013,208(1):653-661
17 Sun X Y,Gong D W,Ma X P.Directed fuzzy graph-based surrogate model-assisted interactive genetic algorithms with uncertain individual s fitness.In:Proceedings of the 2009IEEE Congress on Evolutionary Computation.Trondheim:IEEE,2009.2395-2402
18 Boyle P,Frean M.Multiple Output Gaussian Process Regression.Technical Report CS-TR-05/2,School of Mathematical and Computing Sciences,Victoria University of Wellington,Wellington,New Zealand,2005
19 Sun X Y,Gong D W,Jin Y C,Chen S S.A new surrogateassisted interactive genetic algorithm with weighted semisupervised learning.IEEE Transactions on System,Man,and Cybernetics:Part B,2013,43(2):685-698
20 Multi-output Gaussian Process,Matlab Software[Online],available:http://staffwww.dcs.shef.ac.uk/people/N.Lawrence/multigp/,March 25,2013