Thuật toán tiến hóa vi phân dựa trên các quy luật khả thi phát triển với ngôn ngữ C# để giải các bài toán tối ưu hóa có ràng buộc
Deb [17] proposes an efficient constraint
handling algorithm based on three feasibility
rules:
1. Considering one feasible solution and one
infeasible solution, the feasible solution always
wins.
2. Considering two feasible solutions, the
one having lower objective function value is
preferred.
3. Considering two infeasible solutions, the
one having smaller degree of constraint
violation is considered to be better.
Accordingly, using these rules proposed by
Deb [17], information regarding the feasibility
of solutions is directly included in the selection
phase of metaheuristic algorithms. Moreover,
this advanced method also eliminates the need
of specifying penalty coefficients. Therefore,
metaheuristic algorithms coupled with
feasibility rules often result in good
optimization performances. With such
motivations, this study develops a computer
program used for coping with constrained
optimization problems. This program integrates
the differential evolution metaheuristic [18] and
the aforementioned feasibility rules proposed
by Deb [17]. The feasibility rule based
differential evolution (FRB-DE) has been
developed with Visual C#.NET to facilitate its
implementation. The capability of the newly
developed tool has been verified with two basic
constrained optimization problems.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Tóm tắt nội dung tài liệu: Thuật toán tiến hóa vi phân dựa trên các quy luật khả thi phát triển với ngôn ngữ C# để giải các bài toán tối ưu hóa có ràng buộc
Hoang Nhat Duc / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 02(45) (2021) 103-108 103 02(45) (2021) 103-108 Feasibility rule based differential evolution algorithm developed in visual C# for solving constrained optimization problems Thuật toán tiến hóa vi phân dựa trên các quy luật khả thi phát triển với ngôn ngữ C# để giải các bài toán tối ưu hóa có ràng buộc Hoang Nhat Duca,b* Hoàng Nhật Đứca,b* aInstitute of Research and Development, Duy Tan University, Da Nang, 550000, Vietnam aViện Nghiên cứu và Phát triển Công nghệ Cao, Đại học Duy Tân, Đà Nẵng, Việt Nam bFaculty of Civil Engineering, Duy Tan University, Da Nang, 550000, Vietnam bKhoa Xây dựng, Trường Đại học Duy Tân, Đà Nẵng, Việt Nam (Ngày nhận bài: 22/03/2021, ngày phản biện xong: 26/03/2021, ngày chấp nhận đăng: 29/03/2021) Abstract This study develops an advanced tool for tackling constrained optimization problems based on an integration of feasibility rules and differential evolution metaheuristic. This tool aims at finding a solution with the most desired objective function value and concurrently satisfies all of the problem constraints. The optimization approach, named as feasibility rule based differential evolution (FRB-DE), has been developed in Microsoft Visual Studio with C# programming language. The newly developed tool has been tested with two optimization tasks in the field of civil engineering. Key words: Differential evolution; Constrained optimization; Feasibility rules; Metaheuristic. Tóm tắt Nghiên cứu này phát triển một công cụ để giải quyết các vấn đề tối ưu hóa có ràng buộc dựa trên sự tích hợp các quy tắc khả thi và thuật toán tiến hóa vi phân. Công cụ được xây dựng để tìm ra giải pháp với giá trị hàm mục tiêu tốt nhất và đồng thời thỏa mãn tất cả các ràng buộc. Phương pháp tối ưu hóa, được đặt tên là tiến hóa vi phân dựa trên các quy tắc khả thi (FRB-DE), đã được phát triển trong Microsoft Visual Studio với ngôn ngữ lập trình C #. FRB-DE đã được thử nghiệm với hai bài toán tối ưu hóa cơ bản trong lĩnh vực xây dựng dân dụng. Từ khóa: Tiến Hóa Vi Phân; Tối Ưu Hóa Có Ràng Buộc; Quy Tắc Khả Thi; Thuật Toán Tìm Kiếm. 1. Introduction design tasks e.g. structural design [1-4], Civil engineers frequently encounter schedule/resource planning [5-8] etc. constrained optimization problems in various Constrained optimization tasks are generally * Corresponding Author: Hoang Nhat Duc; Institute of Research and Development, Duy Tan University, Da Nang, 550000, Vietnam; Faculty of Civil Engineering, Duy Tan University, Da Nang, 550000, Vietnam Email: hoangnhatduc@duytan.edu.vn 104 Hoang Nhat Duc / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 02(45) (2021) 103-108 sophisticated since the best found optimal the aforementioned feasibility rules proposed solutions must satisfy a set of pre-specified by Deb [17]. The feasibility rule based restrictions stated in the form of mathematical differential evolution (FRB-DE) has been equations or inequalities [9]. To handle such developed with Visual C#.NET to facilitate its challenges, scholars have resorted to implementation. The capability of the newly metaheuristic to find near optimal solutions for developed tool has been verified with two basic various engineering design tasks [10-12]. constrained optimization problems. Initially, a simple method of penalty functions 2. Feasibility Rule Based (FRB) Differential can be used to handle such restrictions by Evolution (DE) incorporating the constraints into the objective function [13-15]. However, selecting penalty Given that the problem of interest is to coefficients can be problematic for this minimize a cost function f(X), where the approach [16]. Therefore, it is desirable to number of decision variables is D, the utilize advanced approaches that feature optimization process of DE can be separated separation of objective functions and into three main steps: constraints. (i) Mutation: In this step, a vector in the Deb [17] proposes an efficient constraint current population (or parent) called a target handling algorithm based on three feasibility vector is selected. For each parent, a mutant rules: vector is created as follows [18]: V X F(X X ) 1. Considering one feasible solution and one i,g 1 r1,g r2,g r3,g (1) infeasible solution, the feasible solution always where r1, r2, and r3 are three random indexes wins. lying between 1 and NP. r1, r2, and r3 are 2. Considering two feasible solutions, the selected to be different from the index i of the one having lower objective function value is target vector. F is the mutation scale factor. preferred. Vi,g 1 represents a mutant vector. NP is the 3. Considering two infeasible solutions, the number of searching agents. one having smaller degree of constraint (ii) Crossover: A new vector, named as trial violation is considered to be better. vector, is created as follows: Accordingly, using these rules proposed by V j,i,g 1, if rand j Cr or j rnb(i) U j,i,g 1 Deb [17], information regarding the feasibility X j,i,g , if rand j Cr and j rnb(i) of solutions is directly included in the selection (2) phase of metaheuristic algorithms. Moreover, where U is a trial vector. j denotes the this advanced method also eliminates the need j,i,g+1 index of element for any vector. rand is a of specifying penalty coefficients. Therefore, j uniform random number lying between 0 and 1. metaheuristic algorithms coupled with Cr denotes the crossover probability. rnb(i) feasibility rules often result in good denotes a randomly chosen index in optimization performances. With such {1,2,..., NP}. motivations, this study develops a computer program used for coping with constrained (iii) Selection: The selection phase is used to optimization problems. This program integrates compare the fitness of the trial vector and the the differential evolution metaheuristic [18] and target vector. This phase is described as follows: Hoang Nhat Duc / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 02(45) (2021) 103-108 105 Based on the DE metaheuristic and the set of Ui,g if f (Ui,g ) f (X i,g ) X i,g 1 (3) feasibility rules, this study has developed the X if f (U ) f (X ) i,g i,g i,g FRB-DE tool used for constrained Based on the aforementioned feasibility optimization. This tool has been coded in with rules proposed by Deb [17], the formulation of Visual C#.NET programming language within the objective function in the DE metaheuristic the Microsoft Visual Studio integrated is revised in the following manner: development environment. Fig. 1 demonstrates the function interface implementing FRB-DE. F(X ) if g j (x) 0 j The C# delegate type is used to define general F(X ) m (4) fmax g j (x) functional forms of the objective function and j 1 constraints (refer to Fig. 2). Moreover, a C# where fmax denotes the objective function value class is used to store information of an of the worst feasible candidate. optimization problem (refer to Fig. 3.). Fig. 1 The function interface implementing FRB-DE Fig. 2 The use of delegate type 106 Hoang Nhat Duc / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 02(45) (2021) 103-108 Fig. 3 An optimization problem representation 3. Applications of the FRB-DE used to support a load of 20kN at its end. The In the first application, the FRB-DE is used beam is made of steel and its length is 1.5m. to design the cross-section of a cantilever beam The ratio of w-to-t is less than 8 to prevent [19] shown in Fig. 4. There are two parameters local buckling of the cross-section. It is desired of the beam cross-section needed to be to find a set of t and w resulting in a minimal specified: the depth of the section w and the cross-section area. thickness of the cross-section t. The beam is Fig. 4 Optimization problem 1 2 Considering the constraints on bending denote the allowable values. a = 165N/mm . 2 stress, shear stress, and vertical deflection of a = 90N/mm . qa = 10mm. I and Q denote the the free end [19, 20], the optimization task is moment of inertia and moment about the neural formulated as follows: axis (NA) of the area above the NA, respectively [19]. E is the modulus of elasticity Min. f A 4t(w t) (mm2) (5) of steel = 21x104N/mm2. M = PL denotes the s.t. Mw /(2I) a bending moment (N.mm). VQ /(2It) a After 300 generations and with the use of 30 q PL3 /(3EI) q a searching agents, the best found solution is as 8 w/t 0 follows: w = 117.108mm and t = 14.6mm. With where , , and qa are bending stress, shear these variables, all of the four constraint values stress, and vertical deflection of the free end, are satisfied. respectively. The variables with subscript ‘a’ Hoang Nhat Duc / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 02(45) (2021) 103-108 107 The next application involves a preliminary L2) as well as the number of stories (n). This planning of a multistory commercial building optimization problem is modeled as follows: [19] (refer to Fig. 5). The construction site is a Min. f Cost 0.5n3.5 0.001L1L2 (mm2) 100x100-m area. The maximum height of the (6) building is 25 m. Moreover, the parking area s.t. L1 L2 n 20000 0 outside the building is at least 25% of the total floor area. The height of a single story is 3.5 m. 25 n 3.5 0 In addition, the cost of the project is roughly (100 100 L1 L2) (L1 L2 0.25) 0 estimated to be 0.5h + 0.001A where A denotes After 300 generations, the FRB-DE found the floor area. Herein, the decision variables are the following solution: L1 = 90.479m, L2 = the two sides of the constructed area (L1 and 73.682m, and n = 3. Fig. 5 Optimization problem 2 4. Concluding remarks developed tool. Based on the optimization In this study, a FRB-DE program based on results, the newly developed has successfully the DE metaheuristic and a set of feasibility identified good sets of decision variables which rules is developed to deal with constrained satisfy all of the specified constraints. Therefore, optimization tasks. The FRB-DE is programmed FRB-DE can be a promising alternative to assist in Visual C# language. Two basic applications civil engineers in dealing with constrained are used to test the applicability of the newly optimization problems. 108 Hoang Nhat Duc / Tạp chí Khoa học và Công nghệ Đại học Duy Tân 02(45) (2021) 103-108 References Based on a Hybridization of Adaptive Differential Evolution and Support Vector Machine [1] A. Cevik, M. H. Arslan, and M. A. Köroğlu, Classification," Mathematical Problems in "Genetic-programming-based modeling of RC beam Engineering, vol. 2021, p. 6647829, 2021/02/20 torsional strength," KSCE Journal of Civil 2021. Engineering, vol. 14, pp. 371-384, 2010/05/01 2010. [12] N.-D. Hoang and Q.-L. Nguyen, "A Novel [2] C. C. Coello, F. S. Hernández, and F. A. Farrera, Approach for Automatic Detection of Concrete "Optimal design of reinforced concrete beams using Surface Voids Using Image Texture Analysis and genetic algorithms," Expert Systems with History-Based Adaptive Differential Evolution Applications, vol. 12, pp. 101-108, 1997/01/01/ Optimized Support Vector Machine," Advances in 1997. Civil Engineering, vol. 2020, p. 4190682, [3] C. A. Coello Coello, A. D. Christiansen, and F. S. 2020/07/28 2020. Hernández, "A simple genetic algorithm for the [13] H. Nhat-Duc and L. Cong-Hai, "Sử dụng thuật toán design of reinforced concrete beams," Engineering tiến hóa vi phân cho các bài toán tối ưu hóa kết cấu with Computers, vol. 13, pp. 185-196, December 01 với công cụ DE-Excel solver," DTU Journal of 1997. Science and Technology, vol. 03, pp. 97-102, 2019. [4] V. Govindaraj and J. V. Ramasamy, "Optimum [14] C. A. C. Coello, "Constraint-handling techniques detailed design of reinforced concrete continuous used with evolutionary algorithms," presented at the beams using Genetic Algorithms," Computers & Proceedings of the Genetic and Evolutionary Structures, vol. 84, pp. 34-48, 2005/12/01/ 2005. Computation Conference Companion, Kyoto, Japan, [5] M.-Y. Cheng, D.-H. Tran, and N.-D. Hoang, "Fuzzy 2018. clustering chaotic-based differential evolution for [15] C. A. Coello Coello, "Theoretical and numerical resource leveling in construction projects," Journal constraint-handling techniques used with of Civil Engineering and Management, vol. 23, pp. evolutionary algorithms: a survey of the state of the 113-124, 2017/01/02 2017. art," Computer Methods in Applied Mechanics and [6] H.-H. Tran and N.-D. Hoang, "A Novel Resource- Engineering, vol. 191, pp. 1245-1287, 2002/01/04/ Leveling Approach for Construction Project Based 2002. on Differential Evolution," Journal of Construction [16] R. M. John, G. R. Robert, and B. F. David, "A Engineering, vol. 2014, p. 7, 2014. Survey of Constraint Handling Techniques in [7] N.-D. Hoang, "NIDE: A Novel Improved Evolutionary Computation Methods," in Differential Evolution for Construction Project Evolutionary Programming IV: Proceedings of the Crashing Optimization," Journal of Construction Fourth Annual Conference on Evolutionary Engineering, vol. 2014, p. 7, 2014. Programming, ed: MITP, 1995, p. 1. [8] N.-D. Hoang, Q.-L. Nguyen, and Q.-N. Pham, [17] K. Deb, "An efficient constraint handling method "Optimizing Construction Project Labor Utilization for genetic algorithms," Computer Methods in Using Differential Evolution: A Comparative Study Applied Mechanics and Engineering, vol. 186, pp. of Mutation Strategies," Advances in Civil 311-338, 2000/06/09/ 2000. Engineering, vol. 2015, p. 8, 2015. [18] R. Storn and K. Price, "Differential Evolution – A [9] P. W. Christensen and A. Klarbring, An Simple and Efficient Heuristic for global Introduction to Structural Optimization: Springer, Optimization over Continuous Spaces," Journal of 2009 Global Optimization, vol. 11, pp. 341-359, [10] S. M. Nigdeli, G. Bekdaş, and X.-S. Yang, December 01 1997. "Metaheuristic Optimization of Reinforced Concrete [19] J. S. Arora, Introduction to Optimum Design, Footings," KSCE Journal of Civil Engineering, vol. Fourth Edition: Academic Press, 2016. 22, pp. 4555-4563, November 01 2018. [20] J. M. Gere and B. J. Goodno, Mechanics of [11] T. V. Dinh, H. Nguyen, X.-L. Tran, and N.-D. Materials, SI Edition: Cengage Learning, 2013. Hoang, "Predicting Rainfall-Induced Soil Erosion
File đính kèm:
- thuat_toan_tien_hoa_vi_phan_dua_tren_cac_quy_luat_kha_thi_ph.pdf