心理偏好最佳化框架：針對涉及人類偏好的限制性問題所設計的演化式計算

Psychological Preference-based Optimization Framework: An Evolutionary Computation Approach for Constrained Problems Involving Human Preference

游穎萱(Ying-Shiuan You)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.02649

摘要

演化式計算(Evolutionary Computations, ECs)被應用在許多實際問題上。由於有限的資源及不同的需求，要解決實際問題，其中一個困難是限制(Constraints)。另一個挑戰發生在實際問題涉及了人類偏好(Preference)。在演化式計算的研究中，第一個困難的典型解決做法就是採用限制解決方法(Constraint-handling Techniques)，如：解碼器(Decoder)。
研究者解決第二個困難的典型做法就是自己手造出人類偏好的目標函式(Objective Functions)。然而，手造的目標函式背後有太強的假設：研究者手造出的目標函式很接式人類心中的偏好。這篇論文了提出心理偏好最佳化框架(Psychological Preference-based Optimization Framework, PPOF)來解決涉及了人類偏好的限制性問題。心理偏好最佳化框架結合互動式基因演算法(Interactive Genetic Algorithms)和演化式計算中限制解決方法。心理偏好最佳化框架有三個構成的元件：快速可引導式搜尋(Guidable Fast Search)、代理適度式合成者(Surrogate Fitness Synthesizer)、和演化式計算演算法(EC Methods)。這篇論文討論了三個元件的特性及其背後的假設。除此之外，這篇論文也展示了心理偏好最佳化框架在兩個問題上的實作：護士排班問題(Nurse Scheduling Problems)和空間規劃問題(Space Layout Problems)。實驗結果顯示，在護士排班問題上心理偏好最佳化框架可以進行臺灣大學附設醫院的護士月排班，在空間規劃問題上，心理偏好最佳化框架也能夠找出喜歡的規劃。

關鍵字

演化式計算 ； 互動式演化式計算 ； 基因演算法 ； 互動式基因演算法 ； 人類偏好 ； 護士排班 ； 空間規劃

並列摘要

Evolutionary computations (ECs) have been applied to many real-world problems. One of the challenges of real-world problems is the constrained search space resulted from limited resources, requirement, et al., and another challenge is that some problems are involving human preference. Typically, solutions to conquer the first challenge in ECs rely on constraint-handling techniques such as decoder, and the second challenge is usually conquered with manually constructed objective functions by researchers. However, it is too strong such an assumption that the constructed objective function is close to the psychological preference in the human mind. This thesis presents a psychological preference-based optimization framework (PPOF) to solve the problems which are constrained and where the objective functions is involving human preference. PPOF combines interactive ECs and constraint-handling techniques in ECs. PPOF consists of three components: guidable fast search, surrogate fitness synthesizer, and EC method. This thesis discussed the characteristics of the three components and the assumptions behind them. Moreover, this thesis presents two implementations of PPOF on real-world problems: nurse scheduling problem (NSP) and space layout problem (SLP). The experiment shows that PPOF is able to arrange monthly schedules of realistic NSPs of the National Taiwan University Hospital, and PPOF also has the ability to find preferred layouts in SLP.

並列關鍵字

Evolutionary Computation ； Interactive Evolutionary Computation ； Genetic Algorithm ； Interactive Genetic Algorithm ； Human Preference ； Nurse Scheduling ； Space Layout

參考文獻

Abernathy, W., Baloff, N., Hershey, J., & Wandel, S. (1973). A three-stage manpower planning and scheduling model-a service-sector example. The Journal of the Operational Research Society, 21 , 693–711.

Aickelin, U., & Dowsland, K. (2004). An indirect genetic algorithm for a nurse scheduling problem. Comput. Oper. Res., 31 , 761–778.

Aickelin, U., & Li, J. (2007). An estimation of distribution algorithm for nurse scheduling. Annals of Operations Research, 155 , 289.

Beasley, J. E., & Chu, P. C. (1996). A genetic algorithm for the set covering problem. European Journal of Operational Research, 94 , 392 – 404.

Br’elaz, D. (1979). New methods to color the vertices of a graph. Commun. ACM, 22 , 251–256.