一個互動式演化計算運行框架：以最佳化產品設計為例

An Interactive Evolutionary Computation Framework: A Case Study of the Optimal Product Design

10.6188/JEB.2011.13(1).05

王柳鋐(Leuo-Hong Wang)；廖峻德(Jun-De Liao)

疲勞問題 ； 互動式演化計算 ； 演算式機率 ； 適應值預測 ； human fatigue problem ； interactive evolutionary computation ； algorithmic probability ； fitness prediction

電子商務學報

13卷1期（2011 / 03 / 01）

77 - 97

繁體中文

疲勞問題(fatigue problem)一直是互動式演化計算(interactive evolutionary computation, IEC)領域中重要的研究問題之一。本文以解決IEC疲勞問題常見的適應值預測(fitness prediction)策略為出發點，提出一套以演算式機率(algorithmic probability, ALP)為基礎的IEC系統(ALP-IEC)。ALP-IEC以多目標遺傳演算法(multi-objective genetic algorithm, MOGA)實作ALP理論，作為系統的學習模組。當ALP-IEC與受測者(respondent)互動時，學習模組便會以受測者的評估結果做為訓練資料，並習得受測者的效用函數，以進行適應值預測。透過產品設計問題的應用研究，本文比較了ALP-IEC與傳統IEC的效率與效果；ALP-IEC與IEC常見的適應值預測方法－類神經網路(neural network, NN)學習模組的效率與效果。統計檢定顯示ALPIEC在效率與效果上，均優於傳統IEC。換句話說，ALP-IEC在不犧牲效果的情況下，可以提升IEC運行效率，降低疲勞問題發生的可能性。另外，ALP-IEC在產品組合的個案上，其預測誤差的表現，也較NN為佳。

Human fatigue problem is one of the most important research topics in the interactive evolutionary computation (IEC) research discipline. Following the fitness prediction approach proposed in literatures, an algorithmic probability (ALP) based IEC system named as ALP-IEC has been developed in this paper. ALP-IEC has an ALP-based learning module that fulfills the ALP theory and is actually implemented by a multi-objective genetic algorithm (MOGA). The ALP-based learning module is trained by the evaluation results and generates respondent's utility function while the respondent interacts with the system. The fitness prediction is then accomplished by using the utility function. The optimal product design problem has been studied in this paper to compare (1) the effectiveness and efficiency of ALP-IEC with the canonical IEC; (2) the effectiveness and efficiency of ALP-IEC with an IEC system incorporated with a neural network (NN) learning module. The statistical tests indicated that ALP-IEC is statistically significant superior to the canonical IEC for both effectiveness and efficiency. ALP-IEC is capable of, in other words, improving the efficiency of IEC without degrading the effectiveness. In addition, the prediction errors caused by the ALP-based learning module are also less than the errors of NN based learning module.

1. Biles J. A.,Anderson, P. G.,Loggi L. W.(1996).Neural network fitness functions for a musical IGA.International ICSC Symposium on Intelligent Industrial Automation and Soft Computing
2. Caldwell, C.,Johnston, V. S.(1991).Tracking a criminal suspect through facespace with a genetic algorithm.4th International Conference on Genetic Algorithms (ICGA '91),San Diego, CA:
3. Chiclana, F.,Herrera, F.,Herrera-Viedma, E.(2001).Integrating multiplicative preference relations in a multipurpose decision-making based on fuzzy preference relations.Fuzzy Sets and Systems,122,277-291.
4. Coello, C. A. C.(2000).Handling preferences in evolutionary multiobjective optimization: a survey.2000 Congress on Evolutionary Computation
5. Deb K.,Pratap, A.,Agarwal, A.,Meyarivan, T.(2000).Kan GAL Report Number 2000001Kan GAL Report Number 2000001,未出版
6. Dozier, G. V.(2001).Evolving robot behavior via interactive evolutionary computation: from real-world to simulation.Proceedings of the 2001 ACM Symposium on Applied Computing (SAC),Las Vegas:
7. Goldberg, D. F.(1989).Genetic algorithms for search, optimization, and machine learning.Addison-Wesley.
8. Hsu, F. C.,Chen, J. S.(1999).A study on multi criteria decision making model: interactive genetic algorithms approach.Proceedings of 1999 IEEE Systems, Man, and Cybernetics Conference (SMC '99)
9. Hsu, F. C.,Huang, P.(2005).Providing an appropriate search space to solve the fatigue problem in interactive evolutionary computation.New Generation Computing,23(2),114-126.
10. Johanson B.,Poli, R.(1998).GP-music: an interactive genetic programming system for music generation with automated fitness raters.Genetic Programming 1998: Proceedings of the Third Annual Conference
11. Kamalian, R. R.,Yeh, R.,Zhang, Y.,Agogino, A. M.,Takagi, H.(2006).Reducing human fatigue in interactive evolutionary computation through fuzzy systems arid machine learning systems.2006 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE2006)
12. Kanal, L. N.(ed.),Lemmer, J. F.(ed.)(1986).Uncertainty in Artificial Intelligence.Elsevier Science Publishers B. V..
13. Keeney, R.,Raiffa, H.(1993).Decisions with Multiple Objectives: Preferences and Value Tradeoffs.Cambridge University Press.
14. Kohli, R.,Krishnamurti, R.(1987).A heuristic approach to product design.Management Science,33(12),1523-1533.
15. Llorá, X.,Sastry, K.,Goldberg, D. E.,Gupta, A.,Lakshmi, L.(2005).GECCO '05: Proceedings of the 2005 conference on Genetic and evolutionary computation.New York:ACM Press.
16. Machwe, A. T.,Parmee, I. C.(2007).Towards an interactive, generative design system: integrating a 'build and evolve' approach with machine learning for complex freeform design.EvoWorkshops 2007
17. Mitchell, T.(1997).Machine Learning.McGraw Hill.
18. Parmee, I. C.,Cvetkovic, D.(2002).Preferences and their application in evolutionary multiobjective optimization.IEEE Transactions on Evolutionary Computation,6(1),42-57.
19. Phelps, S. P.,Köksalan, M.(2003).An interactive evolutionary metaheuristic for multiobjective combinatorial optimization.Management Science,49(12),1726-1738.
20. Saez, Y.,Isasi, P.,Segovia, J.,Hernandez, J. C.(2005).Reference chromosome to overcome user fatigue in IEC.New Generation Computing,23(2),129-142.
21. Solomonoff, R.(1964).A formal theory of inductive inference.Information and Control, Part I,7(1),1-22.
22. Solomonoff, R.(2003).Technical reportTechnical report,IDSIA.
23. Takagi, H.(2001).Interactive evolutionary computation: fusion of the capacities of EC optimization and human evaluation.Proceedings of the IEEE,89(9),1275-1296.
24. Wang L.-H.(2007).A comparison of three fitness prediction strategies for interactive genetic algorithms.Journal of Information Science and Engineering,23(2),605-616.