A deep learning based interactive method for surrogate multi-Objective evolutionary algorithms - Nguyen Duc Dinh

Công nghệ thông tin N. D. Dinh, N. Long, N. H. Thuy, “A deep learning based interactive algorithms.” 140 A DEEP LEARNING BASED INTERACTIVE METHOD FOR SURROGATE MULTI-OBJECTIVE EVOLUTIONARY ALGORITHMS Nguyen Duc Dinh1*, Nguyen Long2, Nguyen Hong Thuy3 Abstract: In the real world, especially in the field of engineering, multi-objective evolutionary algorithms (MOEAs) has been effective solvers for optimization problems. Because, MOEAs work on the concepts of evolutionary process of the population, so it can work on difficult, expensive problems with set of feasible solutions. However, with some expensive problems in the real world, it requires many evaluations of objective functions. Sometimes, it costs a lot of times for even a single evaluation. Overall, this can make difficult to use MOEAs. Many researchers suggest alleviating this is the integration of surrogate functions which learn to approximate the fitness landscape from a training set of example evaluations. One of the most approaches is the usage of Artificial Neural Networks (ANNs) for the approximation task with deeper networks. In multi-objective optimization, Decision Makers (DMs) have important role to get the best solution for the problems in the real world, DMs can give their preference information before, during or after the search. In the most cases, DMs can interact with the evolutionary process to guide the search to get more solutions in their preferred regions in objective space. Analyst the principle of ANNs, this paper we suggest having a new deep learning based interactive method for the alternative approach of MOEAs with ANNs. The proposal will improve the quality of obtained solutions belong the DM's expectation. Keywords: Surrogate models; Artificial Neural Networks; Deep Learning; MOEAs. 1. MULTI-OBJECTIVE PROBLEMS A multi-objective problem (MOP) is formed as follows [12]: minimize {f1(x), f2(x), , fk(x)} (1) subject to x  S, where k ( 2) is the number of objectives, fi: R n  R are objective functions. The vector of objective functions are denoted by f(x) = (f1(x), f2 (x),..., fk(x)) T. The decision (variable) vector x = (x1, x2,..., xn) T belongs to the feasible region (set) S, which is a subset of decision variable space Rn. The term “minimize” means all objective functions are minimized simultaneously. If there is no conflict between objective functions, then a solution can be found where every objective function attaints its optimum. In this case, no special methods are needed. To avoid such trivial cases we assume that there does not exist a single solution that is optimal with respect to every objective function. This means that the objective functions are at least partly conflicting. The image of the feasible region is denoted by Z(= f(S)) and called feasible objective region, which is a subset of objective space Rk. The elements of Z are called objective (function) vectors or criteria vectors and denoted by f(x) or z = (z1, z2,..., zk) T where zi = fi(x) for I = 1 , , k are objective (function) values or criteria values. For clarity and simplicity, it assumes that all objective functions are to be minimized. If an objective function fi is to be maximized, it is equivalent to Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 141 minimize its function - fi. 2. SURROGATE MULTI-OBJECTIVE EVOLUTIONARY ALGORITHMS MOEAs are stochastic techniques being used to find Pareto optimal solutions for MOPs. There are two key problems that MOEAs have to deal with [4]. The first one is how to get as close as possible to Pareto Optimal Fronts (POFs). This is challenging due to the stochastic convergence process. The second one is how to keep solutions diverse. A diverse set of solutions will provide DMs, designers, etc with more choices. However, working on a set of solutions instead of only one, makes the measurement of MOEA convergence more difficult because one individual’s closeness to POFs does not act as a measurement for the entire set. Unsurprisingly, then, convergence and diversity are commonly used performance criteria when algorithms are assessed and compared to each other [23]. In the real world, with expensive optimization problems in the real world, it has to use a lot of fitness function evaluations during the search. To avoid the expensive physical experiments, we can use computer simulations methods to solve the difficult MOPs. In fact, this way often costs expensive in computation and times for the simulation. In these cases, researchers discussed on the usage of surrogate models for evolutionary algorithms, especially for MOEAs to minimize the number of fitness callings. A surrogate function is a function that can be used instead of the real fitness functions. Such a function takes a solution x  as input and returns an objective vector that approximates the real objective vector. For a surrogate function to be effective, the surrogate function should have the same global optimum and should not introduce false optima. In this case, to optimize the problem based on the surrogate, it requires to find the global optimum where MOP has only a sub optimal local optimum. With expensive problems, there are no more information other than the predefined objective function. Many research show the effective way to use statistical methods and machine learning (ML) to learn the fitness landscape based on the number of data points x  , ( )f x  in a training set from a real fitness function. We have '( )f x  is a meta function, which is indicated as below: '( ) ( ) ( )f x f x e x     (2) The function ( )e x  is the approximated error. In this case, the fitness function ( )f x  is not to be known, the values (input or output) are cared. Based on the responses of the simulator from a chosen dataset, a surrogate is constructed, then the model generates easy representations that describe the relations between preference information of input and output variables. There are some approaches for the surrogate models, which are: The radial basis function (RBF); The polynomial response surface (PRS); The support vector machine (SVM); The kriging (KRG). This paper we discuss on the usage of SVM approach with ANNs. Công nghệ thông tin N. D. Dinh, N. Long, N. H. Thuy, “A deep learning based interactive algorithms.” 142 3. ARTIFICIAL NEURAL NETWORKS 3.1. The principle of artificial neural networks The needed information for systems to process such as approximated function is information of ANNs, the operating search bases on principle of mammalian brains. There is a neuron which collects and transmits electrical signals, a neuron has a cell body with a nucleus and it connects to others by dendrites and axons. Here, the outputs of the neurons are the axons which lead to the inputs (the dendrites) of others. There are several terminal buttons at the end of an axon, which are positioned very close to a dendrite of another neuron. A synapse is a connection point at the crossed point between the terminal button and the dendrite. Here, an used chemicals is known as neurotransmitters, then a terminal button can adjust the potential difference of the target dendrite, these signal are called excitatory or inhibitory signals, respectively. As a metaphor, excitatory effects can be counted as positive and inhibitory effects as negative, and all incoming signals can be accumulated. If a neuron accumulates enough positive signals, a sudden reaction occurs and the neuron transmits an electric signal along its axons to the next neuron [2]. In mathematical models with similar functions, an ANN can simulate the working actions of the brain. In [11, 8], biological brains were recreated at the first steps is known as basic models in this area. In [17], the perceptron was created, which is known as the first generation, a physical machine which was based on neurological models, the first generation was able to be adaptive with its weights. In [18, 22], researchers proposed backpropagation algorithms which could efficiently train networks with more than one hidden layer, so these algorithms were became second generation. This is the reason of many topics on the usage of ANNs, then other machine learning overtook them in the area. The third generation, which is still ongoing with term “deep learning” was introduced. The term emphasizes the focus of the related research on the benefits of using multiple hidden layers. An artificial neuron is the basic building block of an ANN, the processes are called neuron processes when they receive signals, produce an output and send the other output to other connected neurons. Figure 1. An illustration of an artificial neuron. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 143 In Figure 1, u is a schematic of the function of an artificial neuron, ( )uia are input signals which coming from other artificial neurons. ( )uiw are weights for each the incoming connections. Here, the products of ( ) ( ).u ui ia w (with all i from 1 to n) are then summed up and a bias ( )ub is added. Then, the result is subjected to an non-linear mapping by an activation function ( ) ( ).u uy is the output. ( ) ( )( ) ( ) ( ).( . ) u uu u uy a w b    (3) In fact, to approximate the objective function, multiple neurons or ANNs are needed to use. In Figure 2, simulates an artificial neuron network with n = 4 and m = 2 objectives. See Figure 2, the neurons vertices and the connections edges are constructed in a directed acyclic graph. The objective functions (with n = 4 search variables and m = 4 objective functions) are approximated by the ANN. Figure 2. An illustration of an artificial neuron network. Here, all neurons uij are grouped into three layers: 1. The input layer Uinput: all 1u i neurons which receive the elements of the solution vector x  as inputs. 2. The hidden layer Uhidden: all 2u i neurons which do some computations on the signals received from input layers. 3. The output layer Uoutput: all 3ui neurons which do learning defined calculations and produce the final output values that approximate the objective vectors. Công nghệ thông tin N. D. Dinh, N. Long, N. H. Thuy, “A deep learning based interactive algorithms.” 144 Further, all neurons in a layer are connected with next layers by incoming edges (except the output layer). To calculate the approximated function '( )f x   , we compute in order as below: 13 23 3( ) ( ) ( ) 1 2'( ) [ ' ( ), ' ( ),... ' ( )] [ , ,..., ] mu u u mf x f x f x f x y y y       (4) Incorporating with Equation 3, we can calculate the final outputs can now be used as objective vector:          2 3 2 1 3 2 33 , ,( ) 1 1 ' ( ) inputhidden h i h i h h kk UU u u u u u u uu k i h i f x w w x b b                     (5) In the model, the process of computing the correct weights and biases is commonly known as learning. 3.2. Machine learning Now, we have an optimization problem is learning the weights and biases when the objective function is too expensive to compute the gradient. Then evolutionary algorithms are suitable to optimize these problems. The optimization problem posed by ANNs, however, allows us to compute a gradient. Therefore, in ANN learning gradient descent is popular to apply optimization algorithm. Because biases are modeled as weights and the weight vector contains the weights and biases so we can calculate the cost function ( )C w  with weight vector w  with N is number of samples in a training set as below:   2( ) ( ) 1 1 ( ) '( ( ) 2 N i i i C w f x f x N         (6) Here, the training set contains pairs ( , ( ))x f x    of solutions and their respective objective vectors, which were evaluated with the real objective function. The cost function needs to be minimized belong the weight vector w  . In this case, the average of the distances (the errors) between the real objective vectors and the approximated objective vectors are calculated. This average will be high if the weights are set poorly and the approximated objective vectors a far from the real ones. If the average is close to zero, the weights are set correctly. If the gradient descent approach is used, the gradient of the cost function needs to be calculated. In the case of neural networks, this is done using the back-propagation algorithm. In back-propagation algorithm [19], the partial derivatives of the cost function with respect to any of the adaptable parameters (weights and biases) of an ANN are calculated. At begin, the gradients each example in the training set are computed and then averaged to recover gradient for the whole training set. To compute the gradient for a single example, the training example is presented to the neural network as input, which then computes an approximated output ( ) '( ) i f x   (Equation 5). Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 145 The error 0 0 0' ( ) ( )e f x f x    guides us how to change the output value of the output neuron u0 to achieve the desired output value. The outputs of the neurons in the hidden layer have to be adjusted to archive the required change in u0, it called error back-propagation. The back-propagated error scales with influence the hidden neuron uh has on the output value of u0. If the influence of uh is high, its contribution to the error e0 of the output neuron u0 is also high. Therefore the hidden neurons have to be changed to have little influence on u0. The error back- propagation step has to be repeated in case of having more hidden layers. At the end of back-propagation, every neuron has an associated error value depending on the influence it has on the output value of u0. The biases and weights are required to be changed from the errors. It repeats for each neuron in case of having multiple output neurons. The change of biases and weights must be averaged. For each output neuron, we repeat above tasks and average all changes of biases and weights to recover the gradient which is used to optimize the cost function. 4. A DEEP LEARNING BASED INTERACTIVE METHOD FOR SURROGATE MULTI-OBJECTIVE EVOLUTIONARY ALGORITHMS Due to the conflicts among the objectives in MOPs, the total number of Pareto optimal solutions might be very large or even infinite. However, the DM may be only interested in preferred solutions instead of all Pareto optimal solutions. To find the preferred solutions, the preference information is needed to guide the search towards the region of the Pareto Front of interest to the DM, based on the role of the DM in the solution process. In an interactive method, the intermediate search results are presented to the DM to investigate; then the DM can understand the problem better and provide more preference information for guiding the search. There are many discusses about the way which helps DM interactive with evolutionary process such as [21, 10, 1, 16, 7, 20], later with [13, 14, 15]. However, with surrogate multi-objective evolutionary algorithms, this paper we suggest using a deep learning based interactive method for surrogate MOEAs. The idea to use concept of deep learning for interaction between DM and evolutionary process is to learn such hierarchical algorithm by DM’s preference with the help of deep networks. The deep network is constructed by one ANN with at least two hidden layer. Normally, an ANN with only one hidden layer can learn any reasonable function in case of enough neurons [3, 9]. A deep ANN with DM’s preference information can discover the headachy of given preferred of DM during the training. This discovery causes the deep ANN to learn and guide evolutionary process exploit closed DM’s preferred region than the case of without DM’s preference information. It shows more depth adds exponentially more expressive power than width to a normal neural network. It is suitable with expensive problems in the real world. The discovery of giving DM’s preference information and the mapping from this information to the outputs is Công nghệ thông tin N. D. Dinh, N. Long, N. H. Thuy, “A deep learning based interactive algorithms.” 146 used as representation learning. In this case, the DM’s preference is set of m point in the decision space. 1 2 1 2 1 2 1 2( , ,..., ) , ( , ,..., ) ,..., ( , ,..., ) R R Rm n n nPR x x x x x x x x x (7) Then, evolutionary process learns representations are usually created moving faster and stronger converged to DM’s preferred region in the objective space. That is because the machine learning process is better at sifting through the vast amounts of available data to properly identify underlying factors that influence the given DM’s information, even if those underlying factors are not given by DM. In this model, each hidden layer is a DM’s preference information in the hierarchy and uses previous layers which are representations to express a higher level concept. The input layer is the representation data which contains DM’s preference information, and the next layers would compute the edges. The layers after that would use the output of the edge-representing layers to compute the corners and contours, and so on. The applying of deep learning to interactive method for surrogate multi- objective evolutionary algorithms is suitable for many-objective problems. This case, the number of relevant dimensions increases the number of DM’s preferred region grows exponentially. For each DM’s preferred region, a training of example should be provided. At many-objective problems, this curses leads to the existence of many more DM’s preferred than training examples. To validate the proposal, we setup a experiment with NSGA-II [5], a popular multi-objective algorithm on well-known expensive problems: ZDT4, DTLZ1, DTLZ2, WFG1, WFG2 [23, 6] with over 5 interactive times during the search. Analyzing the results, it is indicated as below: • Final solutions are strongly converged to region that DM prefers. • The diversity of population is improved in DM’s region, the principle of the NSGA-II is not changed. Compare the results with the results of running without interactive (in some last generations), it is shown the process is moved faster to DM’s regions and strong converged in the obtained solutions. However, it is more difficult for DM’s to express their preferred region in decision space, it requires the knowledge of the DM in the problems. 5. DISCUSSION AND CONCLUSION Comparison with legacy methods, there are some different features: the first, the legacy methods often give DM’s preference information in form of points [13, 15], directions [21, 10, 1, 14] and other kind of user preference information. In the machine learning based method, the set of points in the decision space is used as representations of the ANNs in input layer, which information is learnt in hidden layers to make the search moving faster and stronger converged to DM’s preferred region in objective space. The given data is used with existed training sets for the Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 147 deep learning and its one is given continuously during generations too. The legacy methods use DM’s given information in such as ways: penalty functions, aggregate functions, extra reference points, niching.... But in the method, the DM’s given data is posed as training data for the machine learning, it makes MOEAs more depth adds exponentially more expressive power than width to a normal neural network. It is suitable with expensive problems, when the surrogate MOEAs is suggested to use in the real world. In this paper, we suggest using a deep learning based interactive methods for surrogate MOEAs, especially which use machine learning in the approximated model. With proposed method, DM’s preferred information is used as learning data for the process, it guides the process moving faster and more converged belong to DM’s preferred regions. With the principle of deep learning with multiple hidden layers, it is suitable with the high dimensions and expensive problems. Acknowledgments: The work is acknowledged by MOD project with code: 2018.76.040. REFERENCES [1]. Wierzbicki A. The use of reference objectives in multi-objective optimization. MCDM Theory and Application, Proceedings. No. 177 in Lecture notes in economics and mathematical systems, pages 468-486, 1980. [2]. John R Anderson. Cognitive psychology and its implications. Worth publishers, 2000. [3]. George Cybenko. Approximation by super-positions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989. [4]. K. Deb. Multi-objective Optimization using Evolutionary Algorithms. John Wiley and Son Ltd, New York, 2001. [5]. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 6(2):182-197, 2002. [6]. K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable test problems for evolutionary multi-objective optimization, TIK-Report no. 112. Technical report, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, 2001. [7]. Maoguo Gong, Fang Liu, Wei Zhang, Licheng Jiao, and Qingfu Zhang. Interactive moea/d for multi-objective decision making. In GECCO’ 2011, pages 721-728, 2011. [8]. Donald O Hebb. The organization of behavior. A neuropsychological theory. 1949. [9]. Kurt Hornik. Approximation capabilities of multilayer feed-forward networks. Neural networks, 4(2):251-257, 1991. [10]. Ed. Branke J., Deb K., Miettinen K., Slowinski R., and Berlin. Consideration Công nghệ thông tin N. D. Dinh, N. Long, N. H. Thuy, “A deep learning based interactive algorithms.” 148 of partial user preferences in evolutionary multi-objective optimization. Multi-objective optimization: interactive and evolutionary approaches. OR Spectrum, 2008. [11]. Warren S McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics, 5(4):115- 133, 1943. [12]. K. Miettinen. Non-linear Multi-objective Optimization. Kluwer Academic Publishers, Boston, USA, 1999. [13]. Long Nguyen and Lam Thu Bui. A multi-point interactive method for multi- objective evolutionary algorithms. In Knowledge and Systems Engineering (KSE), 2012 Fourth International Conference on, pages 107-112. IEEE, 2012. [14]. Long Nguyen and Lam Thu Bui. A ray based interactive method for direction based multi-objective evolutionary algorithm. In Knowledge and Systems Engineering, pages 173-184. Springer, 2014. [15]. Long Nguyen, Lam Thu Bui, and Anh Quang Tran. Toward an interactive method for dmea-ii and application to the spam-email detection system. VNU Journal of Science: Computer Science and Communication Engineering, 30(4), 2016. [16]. Eskelinen Petri and Miettinen Kaisa. Trade-off analysis approach for interactive nonlinear multi-objective optimization. In OR Spectrum, pages 1-14, 2011. [17]. Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958. [18]. David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning internal representations by error propagation. Technical report, California Univ San Diego La Jolla Inst for Cognitive Science, 1985. [19]. David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. Nature, 323(6088):533, 1986. [20]. L. Thiele, K. Miettinen, P. J. Korhonen, and J. Molina. A preference based evolutionary algorithm for multi-objective optimization. Pages 411-436, 2009. [21]. Belton V., Branke J., Eskelinen P., Greco S., Molina J., Ruiz F., and Slowinski. Interactive multiobjective optimization from a learning perspective. multi-objective optimization: interactive and evolutionary approaches. OR Spectrum, 2008. [22]. PJ Werbos. New tools for prediction and analysis in the behavioral sciences. Ph. D. dissertation, Harvard University, 1974. [23]. E. Zitzler, L. Thiele, and K. Deb. Comparision of multi-objective evolutionary algorithms: Em-prical results. Evolutionary Computation, 8(1):173- 195, 2000. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 149 TÓM TẮT PHƯƠNG PHÁP TƯƠNG TÁC DỰA TRÊN HỌC SÂU CHO GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU Trong thực tế, đặc biệt trong kỹ thuật, giải thuật tiến hóa tối ưu đa mục tiêu được biết đến là giải thuật hiệu quả cho các bài toán tối ưu. Vì giải thuật tiến hóa tối ưu đa mục tiêu làm việc trên lý thuyết tiến hóa của quần thể, nên nó có thể giải các bài toán khó, chi phí lớn với tập giải pháp khả dụng. Tuy nhiên, với các bài toán khó trong thực tế, nó đòi hỏi số lượng lớn phép đánh giá của hàm mục tiêu. Đôi khi, nó đòi hỏi thời gian rất lớn đối với mỗi đánh giá ước lượng đơn. Nói chung, có thể gặp khó khăn khi áp dụng giải thuật tiến hóa đa mục tiêu. Nhiều phương pháp đã được đề xuất như tích hợp hàm đại diện và học máy để xấp xỉ việc đánh giá thích nghi. Và một cách tiếp cận phổ biến đó là sử dụng mạng nơ-ron nhân tạo cho việc xấp xỉ với mạng học sâu. Trong tối ưu đa mục tiêu, người ra quyết định có vai trò quan trọng để đạt được giải pháp tốt nhất cho bài toán thực tế và người ra quyết định có thể cung cấp thông tin tham chiếu của họ trước, trong và sau quá trình tìm kiếm. Nhiều trường hợp, người ra quyết định tương tác với tiến trình tiến hóa để chỉ dẫn cho quá trình tìm kiếm để có nhiều giải pháp vào vùng mong muốn hơn trong không gian mục tiêu. Qua phân tích nguyên lý của mạng nơ-ron nhân tạo, bài báo đề xuất một phương pháp dựa trên học sâu để tương tác với giải thuật tối ưu đa mục tiêu sử dụng mạng nơ-ron nhân tạo. Đề xuất này sẽ giúp cải thiện chất lượng giải thuật theo mong muốn của người ra quyết định. Từ khóa: Mô hình đại diện; Mạng nơron nhân tạo; Học sâu; Giải thuật tiến hóa đa mục tiêu. Nhận bài ngày 28 tháng 12 năm 2018 Hoàn thiện ngày 28 tháng 02 năm 2019 Chấp nhận đăng ngày 25 tháng 3 năm 2019 Address: 1MITI, Military Academy of Science and Technology; 2National Defense Academy; 3Hanoi Community College. *Email: nddinh76@gmail.com.