Thuật toán tiến hóa vi phân sử dụng phương pháp ε phát triển trong Excel VBA để giải bài toán tối ưu hóa có điều kiện ràng buộc trong ngành Xây dựng

 TRƯỜNG ĐẠI HỌC DUY TÂN
DTU Journal of Science and Technology 07(38) (2020) .........
 Differential Evolution with ε constrained handling method developed 
 in Excel VBA for solving optimization problem in civil engineering
 Thuật toán tiến hóa vi phân sử dụng phương pháp ε phát triển trong Excel VBA để giải bài 
 toán tối ưu hóa có điều kiện ràng buộc trong ngành xây dựng
 Nhat Duc Hoanga,*, Huy Thanh Nguyenb
 Hoàng Nhật Đức, Nguyễn Huy Thành
 aInstitute of Research and Development, Duy Tan University, Da Nang, Vietnam
 Viện Nghiên cứu và Phát triển Công nghệ cao, Trường Đại học Duy Tân, Đà Nẵng, Việt Nam
 bDa Nang Road and Bridge Management Company, Da Nang, Vietnam
 Công ty Quản lý Cầu đường Đà Nẵng, Đà Nẵng, Việt Nam
(Ngày nhận bài: 27/08/2019, ngày phản biện xong: 06/12/2019, ngày chấp nhận đăng: 20/02/2020)
Abtract
Constrained optimization is an important task in civil engineering. The objective of this task is to determine a solution 
with the most desired objective function value that guarantees the satisfaction of constraints. The Differential Evolution 
(DE) is a powerful evolutionary algorithm for solving global optimization tasks. Our research develops an optimization 
model based on the DE and ε rules proposed by Takahama, et al. [1]. To facilitate the application of the optimization 
model, a DE Solver, named as ε CHDE, has been developed in Microsoft Excel VBA platform. Experimental outcomes 
with several basic constrained design problems prove that the ε CHDE developed in this study can be a useful tool for 
solving constrained optimization problems.
Keywords: Constrained handling, Differential Evolution, ε Rules, Stochastic search.
Tóm tắt 
Tối ưu hóa có ràng buộc là một nhiệm vụ quan trọng trong xây dựng dân dụng. Mục tiêu của nhiệm vụ này là xác định 
một giải pháp có giá trị hàm mục tiêu tốt nhất, đồng thời đảm bảo sự thỏa mãn của các ràng buộc. Tiến hóa vi phân (DE) 
là một thuật toán tiến hóa mạnh mẽ để giải quyết các nhiệm vụ tối ưu hóa toàn cục. Nghiên cứu của chúng tôi phát triển 
một mô hình tối ưu hóa dựa trên các thuật toán DE và phương pháp ε được đề xuất bởi Takahama, et al. [1]. Để tạo điều 
kiện cho việc áp dụng mô hình tối ưu hóa, một DE Solver, được đặt tên là ε CHDE, đã được phát triển trong nền tảng VBA 
của Microsoft Excel. Kết quả thử nghiệm với một vấn đề thiết kế đơn giản đã chứng tỏ rằng ε CHDE được phát triển trong 
nghiên cứu này có thể là một công cụ thuận tiện để giải quyết các vấn đề tối ưu hóa bị ràng buộc. 
Từ khóa: Xử lý ràng buộc, Tiến hóa vi phân, Quy tắc ε, Tìm kiếm ngẫu nhiên.
1. Introduction maximized under certain constraints, are crucial 
 Constrained optimization tasks, especially and ubiquitously appear in the field of civil 
nonlinear and complex optimization ones, engineering. Civil engineers have to resort 
where objective functions are minimized or to capable metaheuristic algorithms to tackle 
Email: hoangnhatduc@dtu.edu.vn
108
a variety of complex decision making tasks Evolution and constructed as an Add-In used in 
including structural optimization [2, 3], schedule Microsoft Excel by [19]. In this study, we aim at 
optimization [4-7], resource utilization [8-10], developing another Microsoft Excel Add-In that 
etc. Notably, a constrained optimization task is employs the DE algorithm and the ε constraint-
typically more difficult than an unconstrained one; handling method proposed by Takahama, et al. 
the reason is that the process of finding optimal [1]. The newly developed Excel Add-In has been 
solutions must be performed by metaheuristic tested with a simplified retaining wall design 
algorithms within the feasible domains [11, 12]. problem.
 A constrained optimization task can be stated 2. Research Methodology
generally as follows [13, 14]:
 2.1 Differential Evolution (DE)
 Min. f(x):f(x x , x ,,x ), d = 1,2,,D (1)
 1, 2 d D Given that the problem at hand is to minimize 
 Subjected to: an objective function f(X), where the number of 
 gq(x1, x2, xd,,xD) ≤ 0, d = 1,2,,D, q = decision variables is D, the DE [20, 21] algorithm 
1,2,,M (2) for unconstrained optimization consists of four 
 hr(x1, x2, xd,,xD) = 0, d = 1,2,,D, r = main steps: initialization, mutation, crossover, 
1,2,,N (3) and selection. The searching process of the DE 
 L ≤ ≤ U (4) algorithm is repeated until a stopping condition is 
 xd xd xd 
 met. Usually, the algorithm terminates when the 
where, f(x x ,,x ) represents the objective 
 1, 2 d generation counters reach the maximum number 
function; x x ,,x denotes a set of decision 
 1, 2 d generations (G ). The four steps of the DE are 
variables; g (x x ,,x ) and h (x x ,,x ) are max
 q 1, 2 d r 1, 2 d shortly described as follows:
inequality and equality constraints, respectively. 
 L U (i) Initialization: This step randomly generates 
xd and xd denote lower and upper boundaries 
 a set of PS D-dimensional vectors X i,g where i = 
of xd, respectively. D is the number of decision 
variables; and finally, M and N represent the 1, 2, , PS and g is the generation counter.
numbers of inequality and equality constraints, (ii) Mutation: A target vector is selected. For 
respectively. each target vector, a mutant vector is created as 
 The conventional penalty function is often follows:
utilized for dealing with constrained optimization Vi,g+1 = X r1,g + F(X r 2,g − X r3,g ) (5)
problems by converting them to unconstrained where r1, r2, and r3 are 3 random indexes ranging 
ones [14-17]. Nhat-Duc and Cong-Hai [18] from 1 to PS; F is the mutation scale factor which 
developed a Differential Evolution (DE) based is often selected as a fixed number (e.g. 0.5) or 
constrained optimization solver using the penalty can be generated from a Gaussian distribution 
function. The penalty function approaches [22].
are simple and therefore easy to utilize. 
 (iii) Crossover: A trial vector is created as 
Nevertheless, this method cannot satisfactorily 
 follows:
handle complex constraints and requires a 
proper setting of the penalty factors [17]. To (6)
overcome such disadvantage of the conventional 
penalty function, Deb [15] proposes a feasibility 
 where Uj,i,g+1 denotes the trial vector. j denotes the 
rules based constraint handling method; this 
 index of element for any vector; randj represents 
method has been integrated with the Differential a uniform random number of [0, 1]; Cr denotes 
 109
the crossover probability which is often selected 
as a constant number (e.g. 0.8); rnb(i) denotes a 
randomly chosen index of {1,2,...,NP}.
(iv) Selection: The trial vector is compared to 
the target vector in this step according to the 
following rule:
 (7)
 2.2 The ε Constraint Handling Method
 The ε constraint-handling method has been 
proposed by Takahama, et al. [1]. Using this 
 Fig 1. The ε CHDE Excel Solver
method, the constraint violation degree is defined 
either as the maximum of all constraints or the 
sum of all constraints as follows:
φ(xh )= max{maxj {0,g j (x)}, max jj | (x) |} (8)
φ = pp+
 (xh )∑∑ || maxj {0,g j (x) || || maxjj | (x) || 
 jj
 (9)
where p denotes a positive integer.
 Based on such definition of the constraint 
violation, the selection operation of the employed 
metaheuristic is revised as follows:
 (10)
3. The ε Constraint Handling DE (CHDE) 
Excel Solver Applications
 The ε CHDE Excel Solver tool has been 
developed in Visual Basic for Applications 
(VBA). The graphical user interface of the Excel Fig 2. Illustration of the simplified retaining wall design 
Solver is displayed in Fig. 1. The tool requires the problem (Adopted from [23])
decision variables, upper bounds, lower bounds, The ε CHDE Excel Solver tool is applied to 
type (real, integer, or binary), constraints, and optimize the design of a simplified retaining wall 
the objective function of the problem as input [23] as illustrated in Fig. 2. The design variables 
information. Notably, all of the constraints must of the problem are the lengths of the base and the 
be described in the following template: top of the retaining wall. For more detail of the 
 G(x) ≥ 0 (11) problem formulation, the readers are suggested to 
110
study the work [23]. The optimization outcome As can be seen from the figure, the Excel Solver 
performed by the newly developed tool is reported based on DE and the ε rules can help to find the 
in Fig. 3 with the number of population size = 12 decision variables which result in low value of 
and the maximum number of generations = 100. the objective function within the feasible domain.
 Fig 3. Solving the constrained optimization problem using the ε CHDE Excel Solver tool
4. Conclusion
 In this study, ε CHDE Excel Solver tool relied Supplementary material
on the DE metaheuristic and the ε constraint The Excel solver can be downloaded at:
handling method has been developed. The ε 
 https://github.com/NhatDucHoang/Epsilon_
CHDE Excel Solver is programmed in VBA 
 CHDE_ExcelSolver 
environment and can directly solve optimization 
problems formulated in Microsoft Excel. A References
simplified case of retaining wall design is [1] T. Takahama, S. Sakai, and N. Iwane, “Solving 
 Nonlinear Constrained Optimization Problems by 
employed to demonstrate the effectiveness of 
 the ε Constrained Differential Evolution,” in 2006 
the ε CHDE Excel Solver. Hence, the newly IEEE International Conference on Systems, Man and 
constructed tool can be a useful tool for engineers Cybernetics, 2006, pp. 2322-2327.
in dealing with optimization problems. [2] M. Shaqfa and Z. Orbán, “Modified parameter-
 111
 setting-free harmony search (PSFHS) algorithm for Methods in Applied Mechanics and Engineering, vol. 
 optimizing the design of reinforced concrete beams,” 191, pp. 1245-1287, 2002/01/04/ 2002.
 Structural and Multidisciplinary Optimization, [13] G. V. Reklaitis, A. Ravindran, and K. M. Ragsdell, 
 March 28 2019. “Engineering Optimization Methods and 
[3] A. B. Senouci and M. S. Al-Ansari, “Cost optimization Applications,” Wiley, New York, 1983.
 of composite beams using genetic algorithms,” [14] N. Đ. Hoàng and D. T. Vũ, “Tối ưu hóa kết cấu có 
 Advances in Engineering Software, vol. 40, pp. 1112- điều kiện ràng buộc sử dụng thuật toán bầy đom đóm 
 1118, 2009/11/01/ 2009. và các hàm phạt,” Tạp Chí Khoa Học và Công Nghệ, 
[4] S. Monghasemi, M. R. Nikoo, M. A. Khaksar Fasaee, Đại Học Duy Tân, vol. 2, pp. 75–84, 2015.
 and J. Adamowski, “A novel multi criteria decision [15] K. Deb, “An efficient constraint handling method for 
 making model for optimizing time–cost–quality genetic algorithms,” Computer Methods in Applied 
 trade-off problems in construction projects,” Expert Mechanics and Engineering, vol. 186, pp. 311-338, 
 Systems with Applications, vol. 42, pp. 3089-3104, 2000/06/09/ 2000.
 2015/04/15/ 2015. [16] O. Kramer, “A Review of Constraint-Handling 
[5] M. Rogalska, W. Bożejko, and Z. Hejducki, “Time/ Techniques for Evolution Strategies,” Applied 
 cost optimization using hybrid evolutionary algorithm Computational Intelligence and Soft Computing, vol. 
 in construction project scheduling,” Automation in 2010, 2010.
 Construction, vol. 18, pp. 24-31, 2008/12/01/ 2008. [17] R. M. John, G. R. Robert, and B. F. David, “A Survey 
[6] N.-D. Hoang, “NIDE: A Novel Improved Differential of Constraint Handling Techniques in Evolutionary 
 Evolution for Construction Project Crashing Computation Methods,” in Evolutionary 
 Optimization,” Journal of Construction Engineering, Programming IV: Proceedings of the Fourth Annual 
 vol. 2014, p. 7, 2014. Conference on Evolutionary Programming, ed: 
[7] M.-Y. Cheng, D.-H. Tran, and N.-D. Hoang, “Fuzzy MITP, 1995, p. 1.
 clustering chaotic-based differential evolution for [18] H. Nhat-Duc and L. Cong-Hai, “Sử dụng thuật toán 
 resource leveling in construction projects,” Journal tiến hóa vi phân cho các bài toán tối ưu hóa kết 
 of Civil Engineering and Management, vol. 23, pp. cấu với công cụ DE-Excel solver,” DTU Journal of 
 113-124, 2017/01/02 2017. Science and Technology, vol. 03, pp. 97-102, 2019.
[8] N.-D. Hoang, Q.-L. Nguyen, and Q.-N. Pham, [19] N. D. Hoang, “FR-DE Excel Solver: Differential 
 “Optimizing Construction Project Labor Utilization Evolution with Deb’s feasibility rules for 
 Using Differential Evolution: A Comparative Study of solving constrained optimization problems in 
 Mutation Strategies,” Advances in Civil Engineering, civil engineering,” DTU Journal of Science and 
 vol. 2015, p. 8, 2015. Technology 04 (35), 2019.
[9] H.-H. Tran and N.-D. Hoang, “A Novel Resource- [20] K. Price, R. M. Storn, and J. A. Lampinen, Differential 
 Leveling Approach for Construction Project Based Evolution - A Practical Approach to Global 
 on Differential Evolution,” Journal of Construction Optimization: Springer-Verlag Berlin Heidelberg, 
 Engineering, vol. 2014, p. 7, 2014. 2005.
[10] K. El-Rayes and D. H. Jun, “Optimizing Resource [21] R. Storn and K. Price, “Differential Evolution 
 Leveling in Construction Projects,” Journal of - A Simple and Efficient Heuristic for global 
 Construction Engineering and Management, vol. Optimization over Continuous Spaces,” Journal of 
 135, pp. 1172-1180, 2009. Global Optimization, vol. 11, pp. 341-359, December 
[11] C. A. C. Coello, “Constraint-handling techniques 01 1997.
 used with evolutionary algorithms,” presented at [22] N.-D. Hoang, D. Tien Bui, and K.-W. Liao, 
 the Proceedings of the Genetic and Evolutionary “Groutability estimation of grouting processes with 
 Computation Conference Companion, Kyoto, Japan, cement grouts using Differential Flower Pollination 
 2018. Optimized Support Vector Machine,” Applied Soft 
[12] C. A. Coello Coello, “Theoretical and numerical Computing, vol. 45, pp. 173-186, 2016/08/01/ 2016.
 constraint-handling techniques used with evolutionary [23] T. G. Hicks, Handbook of civil engineering 
 algorithms: a survey of the state of the art,” Computer calculations: McGraw-Hill, 2007.