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.

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 trang 1

Trang 1

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 trang 2

Trang 2

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 trang 3

Trang 3

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 trang 4

Trang 4

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 trang 5

Trang 5

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 trang 6

Trang 6

pdf 6 trang duykhanh 6920
Bạn đang xem 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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

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

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:

  • pdfthuat_toan_tien_hoa_vi_phan_dua_tren_cac_quy_luat_kha_thi_ph.pdf