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-
typicallymoredifficultthananunconstrainedone; 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
generally as follows [13, 14]:
2. Research Methodology
2.1 Differential Evolution (DE)
Min. f(x):f(x1, x2, xd,…,xD), d = 1,2,…,D (1)
Subjected to:
Given that the problem at hand is to minimize
an objective function f(X), where the number of
decision variables is D, the DE [20, 21] algorithm
for unconstrained optimization consists of four
main steps: initialization, mutation, crossover,
and selection. The searching process of the DE
algorithm is repeated until a stopping condition is
met. Usually, the algorithm terminates when the
generation counters reach the maximum number
generations (Gmax). The four steps of the DE are
shortly described as follows:
gq(x1, x2, xd,…,xD) ≤ 0, d = 1,2,…,D, q =
1,2,…,M
(2)
hr(x1, x2, xd,…,xD) = 0, d = 1,2,…,D, r =
1,2,…,N
xdL ≤ xd ≤ xUd
(3)
(4)
where, f(x1, x2,…,xd) represents the objective
function; x1, x2,…,xd denotes a set of decision
variables; gq(x1, x2,…,xd) and hr(x1, x2,…,xd) are
inequality and equality constraints, respectively.
xdL
xdU
(i) Initialization: This step randomly generates
a set of PS D-dimensional vectors Xi,g where i =
1, 2, …, PS and g is the generation counter.
and
denote lower and upper boundaries
of xd, respectively. D is the number of decision
variables; and finally, M and N represent the
numbers of inequality and equality constraints,
respectively.
(ii) Mutation: A target vector is selected. For
each target vector, a mutant vector is created as
follows:
The conventional penalty function is often
utilized for dealing with constrained optimization
problems by converting them to unconstrained
ones [14-17]. Nhat-Duc and Cong-Hai [18]
developed a Differential Evolution (DE) based
constrained optimization solver using the penalty
function. The penalty function approaches
are simple and therefore easy to utilize.
Nevertheless, this method cannot satisfactorily
handle complex constraints and requires a
proper setting of the penalty factors [17]. To
overcome such disadvantage of the conventional
penalty function, Deb [15] proposes a feasibility
rules based constraint handling method; this
method has been integrated with the Differential
Vi,g+1 = Xr1,g + F(Xr2,g − Xr3,g
)
(5)
where r1, r2, and r3 are 3 random indexes ranging
from 1 to PS; F is the mutation scale factor which
is often selected as a fixed number (e.g. 0.5) or
can be generated from a Gaussian distribution
[22].
(iii) Crossover: A trial vector is created as
follows:
(6)
where Uj,i,g+1 denotes the trial vector. j denotes the
index of element for any vector; randj represents
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
method, the constraint violation degree is defined
either as the maximum of all constraints or the
sum of all constraints as follows:
Fig 1. The ε CHDE Excel Solver
φ(x) = max{max j{0,g j (x)},max j | hj (x) |} (8)
φ(x) = || max {0,g (x) ||p + || max | h (x) ||p
∑
∑
j
j
j
j
j
j
(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
Solver is displayed in Fig. 1. The tool requires the
decision variables, upper bounds, lower bounds,
type (real, integer, or binary), constraints, and
the objective function of the problem as input
information. Notably, all of the constraints must
be described in the following template:
Fig 2. Illustration of the simplified retaining wall design
problem (Adopted from [23])
The ε CHDE Excel Solver tool is applied to
optimize the design of a simplified retaining wall
[23] as illustrated in Fig. 2. The design variables
of the problem are the lengths of the base and the
top of the retaining wall. For more detail of the
problem formulation, the readers are suggested to
G(x) ≥ 0
(11)
110
study the work [23]. The optimization outcome As can be seen from the figure, the Excel Solver
performedbythenewlydevelopedtoolisreported 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
on the DE metaheuristic and the ε constraint
handling method has been developed. The ε
CHDE Excel Solver is programmed in VBA
environment and can directly solve optimization
problems formulated in Microsoft Excel. A
simplified case of retaining wall design is
employed to demonstrate the effectiveness of
the ε CHDE Excel Solver. Hence, the newly
constructed tool can be a useful tool for engineers
in dealing with optimization problems.
Supplementary material
The Excel solver can be downloaded at:
CHDE_ExcelSolver
References
[1] T. Takahama, S. Sakai, and N. Iwane, “Solving
Nonlinear Constrained Optimization Problems by
the ε Constrained Differential Evolution,” in 2006
IEEE International Conference on Systems, Man and
Cybernetics, 2006, pp. 2322-2327.
[2] M. Shaqfa and Z. Orbán, “Modified parameter-
111
setting-free harmony search (PSFHS) algorithm for
optimizing the design of reinforced concrete beams,”
Methods in Applied Mechanics and Engineering, vol.
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-
1118, 2009/11/01/ 2009.
[4] S. Monghasemi, M. R. Nikoo, M. A. Khaksar Fasaee,
điều kiện ràng buộc sử dụng thuật toán bầy đom đóm
và các hàm phạt,” Tạp Chí Khoa Học và Công Nghệ,
Đạ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
trade-off problems in construction projects,” Expert
Systems with Applications, vol. 42, pp. 3089-3104,
2015/04/15/ 2015.
genetic algorithms,” Computer Methods in Applied
Mechanics and Engineering, vol. 186, pp. 311-338,
2000/06/09/ 2000.
[16] O. Kramer, “A Review of Constraint-Handling
Techniques for Evolution Strategies,” Applied
Computational Intelligence and Soft Computing, vol.
2010, 2010.
[17] R. M. John, G. R. Robert, and B. F. David, “A Survey
of Constraint Handling Techniques in Evolutionary
[5] M. Rogalska, W. Bożejko, and Z. Hejducki, “Time/
cost optimization using hybrid evolutionary algorithm
in construction project scheduling,” Automation in
Construction, vol. 18, pp. 24-31, 2008/12/01/ 2008.
[6] N.-D. Hoang, “NIDE: A Novel Improved Differential
Evolution for Construction Project Crashing
Optimization,” Journal of Construction Engineering,
vol. 2014, p. 7, 2014.
Computation
Methods,”
in
Evolutionary
Programming IV: Proceedings of the Fourth Annual
Conference on Evolutionary Programming, ed:
MITP, 1995, p. 1.
[7] M.-Y. Cheng, D.-H. Tran, and N.-D. Hoang, “Fuzzy
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
of Civil Engineering and Management, vol. 23, pp.
113-124, 2017/01/02 2017.
tiến hóa vi phân cho các bài toán tối ưu hóa kết
cấu với công cụ DE-Excel solver,” DTU Journal of
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
Using Differential Evolution:AComparative Study of
Mutation Strategies,” Advances in Civil Engineering,
vol. 2015, p. 8, 2015.
Evolution with Deb’s feasibility rules for
solving constrained optimization problems in
civil engineering,” DTU Journal of Science and
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
on Differential Evolution,” Journal of Construction
Engineering, vol. 2014, p. 7, 2014.
Evolution - A Practical Approach to Global
Optimization: Springer-Verlag Berlin Heidelberg,
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
Construction Engineering and Management, vol.
135, pp. 1172-1180, 2009.
- A Simple and Efficient Heuristic for global
Optimization over Continuous Spaces,” Journal of
Global Optimization, vol. 11, pp. 341-359, December
01 1997.
[11] C. A. C. Coello, “Constraint-handling techniques
used with evolutionary algorithms,” presented at [22] N.-D. Hoang, D. Tien Bui, and K.-W. Liao,
the Proceedings of the Genetic and Evolutionary
Computation Conference Companion, Kyoto, Japan,
2018.
“Groutability estimation of grouting processes with
cement grouts using Differential Flower Pollination
Optimized Support Vector Machine,” Applied Soft
Computing, vol. 45, pp. 173-186, 2016/08/01/ 2016.
[12] C. A. Coello Coello, “Theoretical and numerical
constraint-handlingtechniquesusedwithevolutionary [23] T. G. Hicks, Handbook of civil engineering
algorithms: a survey of the state of the art,” Computer calculations: McGraw-Hill, 2007.
5 trang
13/04/2022
4460
Bạn đang xem tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- thuat_toan_tien_hoa_vi_phan_su_dung_phuong_phap_phat_trien_t.pdf
