Thuật toán di truyền và ứng dụng trong xây dựng – Tài liệu text

THUẬT to¸n DI TRUYỀN
VÀ ỨNG DỤNG TRONG QUẢN LÍ XÂY DỰNG
PGS. Lê Kiều – Trường Đại Học Kiến Trúc Hà Nội
Lại Hải Đăng, Lưu Trường Văn – Trường Đại Học Bách Khoa TP.HCM
I)Tổng quan
– Cã thĨ sư dơng tht to¸n di trun lµm c«ng cơ ®Ĩ thùc hiƯn nh÷ng phÐp tèi u ho¸ cho c¸c bµi
to¸n trong tỉ chøc s¶n xt x©y dùng.
– Thuật to¸n di truyền (Genetic Algorithms- Viết tắt là GAs), do John Holland (1975) và
Goldberg (1989) đề xuất và phát triển, là thuật to¸n tìm kiếm dựa trên cơ chế chọn lọc và di
truyền tự nhiên.Thuật to¸n này sử dụng các nguyên lý di truyền về sự thích nghi và sự sống
các cá thể thích nghi nhất trong tự nhiên. Các thuật ngữ được sử dụng trong GAs được lấy từ
ngôn ngữ di truyền sinh học trong tự nhiên.
– Tập hợp tất cả các lời giải trong không gian tìm kiếm được gọi là kiểu hình. Các kiểu hình
này khi mã hoá gọi là kiểu gen. Toán tử di truyền sẽ được thực thi trên đối tượng này. Một
ánh xạ từ kiểu hình sang kiểu gen gọi là quá trình mã hoá. Mỗi cá thể trong kiểu gen có
nhiều nhiễm sắc thể. Trong mỗi nhiễm sắc thể có chứùa nhiều gen. Mỗi đặc trưng di truyền
cụ thể được quy đònh bởi giá trò và vò trí của gen trong nhiễm sắc thể. Độ thích nghi là thước
đo khả năng sốâng sót và phát triển của cá thể trong môi trường
– Toán tử xác đònh cá thể trong thế hệ hiện tại được giữ lại trong thế hệ kế tiếp được gọi là
chọn lọc. Toán tử kết hợp ngẫu nhiên hai cá thể được chọn gọi là lai ghép. Toán tử thay đổi
ngẫu nhiên cấu trúc cá thể, túc làm thay đổi giá trò của gen gọi là đột biến.
II) Các tính chất quan trọng của thuật to¸n di truyền
– GAs lập luận mang tính chất ngẫu nhiên để tìm giải pháp tối ưu cho những vấn đề phức
tạp, thay vì xác đònh như toán học giải tích. Tuy nhiên đây là hình thức ngẫu nhiên có hướng
dẫn bỏi trò số thích nghi. Chính hàm số thích nghi là giúp GAs tìm giải pháp tối ưu trong rất
nhiều giải pháp có thể có.
-GAs không để ý đến chi tiết vấn đề, trái lại chỉ chú ý đến giải pháp cho vấn đề, hay tìm
điều kiện tối ưu cho việc điều hành, và phân nhóm những giải pháp có được.
– GAs được sử dụng đặc biệt cho nhứõng bài toán yêu cầu tìm kiếm tối ưu toàn cục với không
gian tìm kiếm lớn và không thể kiểm soát nhờ khả năng duyệt qua không gian tìm kiếm đại
diện mà không thực sự đi qua từng điểm của toàn bộ không gian

Bắt đầuKhởi tạo quần thểMã hoá các biếnĐánh giá độ thích nghiChọn lọcLai ghépĐột biếnĐạt tiêu chẩn tối ưuKết quảThỏaKhôngKết thúcHình 1. Sơ đồ cấu trúc thuật to¸n di truyềnIII) Cơ chế thực hiện của thuật to¸n1. Mã hóa- GAs bắt đầu với quần thể, tập của nhiều cá thể ( nhiễm sắc thể). Sự mã hoá các biến phụthuộc vào từng bài toán. Thông thường có các dạng mã sau: mã nhò phân, mã Gray, mã sốthực và mã dạng cây. Khi mã hoá dùi dạng chuỗi nhò phân, mỗi nhiễm sắc thể được kí hiệubằng các chuỗi bít 0 và 1.1 1 0 0 1 0 10 1101 1 0Nhiễm sắc thể ANhiễm sắc thể BHình 2. Mã hoá dưới dạng nhò phân- Giả sử muốn tối ưu hàm n biến f(x,x2,), trong đó mỗi biến xthuộc miền D=[ a,b] làtập con của tập số thực R và yêu cầu độ chính xác là k chữ số thập phân cho các giá trò biến. Để đạt được độ chính xác như vậy miền [ a,b] được phân cắt thành (b- a)*10miền conbằng nhau. Gọi mlà số nguyên nhỏ nhất sao: (b- a)*1012 −- Như vậy mỗi biến xthuộc [ a,b] được biểu diễn bằng một chuỗi nhò phân có chiều dài mPhép ánh xạ biến nhò phân thành biến thực xđượctính theo công thức := a+ decimal(string)*12 −iiabTrong đó decimal(string) biểu diễn giá trò thập phân của chuỗi nhò phân string. Bây giờmỗi nhiễm sắc thể (là một lời giải ) được biểu diễn bằng chuỗi nhò phân có chiều dài m=i 1; mbít đầu tiên biểu diễn các giá trò trong khoảng [ a,b], mbít kế tiếp biểu diễn giá tròtrong khoảng [ a,b] và nhóm mbít cuối cùng biểu diễn giá trò trong khoảng [ a,b].2. Chọn lọc cá thể.- Đối với tiến trình chọn lọc ( chọn quần thể thỏa phân bố xác suất dựa trên độ thích nghi),ta dùng bánh xe rulét với các rãnh được đònh kích thước theo độ thích nghi như sau:Tính độ thích nghi eval(v) của mỗi nhiễm sắc thể v(i=1 pop-size), với pop-size là kíchthước của quần thể:eval(v)=sizepopvfvf)()(với f (v) là hàm mục tiêuTìm tổng giá trò thích nghi F cho toàn quần thể :F =sizepopi 1eval(vTính xác xuất chọn pcho mỗi nhiễm sắc thể vsizepopvevalveval)()(Tính xác xuất tích luỹ qcho mỗi nhiễm sắc thể vsizepopi 1- Tiến trình chọn lọc được thực hiện bằng cacùh quay bánh xe rulét pop-size lần. Mỗi lầnchọn ra một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới theo cách sau:Phát sinh 1 số ngẫu nhiên r trong khoảng [0,1Nếu r< qthì chọn nhiễm sắc thể đầu tiên v, ngược lại chọn nhiễm sắc thể vsao qi-1< r ≤ q3. Lai ghép- Toán tử tác động trên các cá thể cha mẹ để tạo ra những con lai tốât được gọi là lai ghép.Các cặp cha mẹ được chọn lựa lai ghép với xác suất p. Có 3 dạng lai ghép cơ bản: lai mộtvò trí, lai nhiều vò trí và lai đều. Với 3 loại trên, xác suất cá thể tạo ra do lai ghép vẫn làhằng số.- Với mỗi nhiễm sắc thể trong quần thể:Phát sinh 1 số ngẫu nhiên r trong khoảng [0,1Nếu r < pthì chọn nhiễm sắc thể đó để lai ghép- Sau đó ghép các nhiễm sắc thể đã được chọn một cách ngẫu nhiên. Đối với mỗi cặpnhiễm sắc thể được ghép đôi, lại phát sinh ngẫu ngiên một số nguyên pos trong khoảng[ 0,m ] (m là tổng số bit trong một nhiễm sắc thể). Số pos cho vò trí điểm lai. Hai nhiễm sắcthể (bpospos+1) và (cpospos+1) được thay bằng cặp con của chúng(bpospos+1) và (cpospos+1Hình 3. Lai đơnVò trí laiCá thể cha mẹ0000 1 11011Cá thể con01011 11011Hình 4. Lai bộiVò trí laiCá thể cha mẹ0000 1 11011Cá thể con01011 11110- Trường hợp lai đều thì mỗi gen của cá thể con được chọn một cách ngẫu nhiên gen tươngứng với cá thể bố hoặc mẹ. Cách tiến hành lai đều được tiến hành như sau:+ Tạo một chuỗi lai giả M có chiều dài bằng chiều dài chuỗi bố, mẹ. Các bít được tạo ngẫunhiên+ Chuỗi con O được tạo ra bằng cách lấy từng gen từ cá thể cha, mẹ.Nếu bít thứ I trongchuỗi lai giả M là 1 thì lấy gen tương ứng của cá thể P, ngược lại lấy gen tương ứng cá thểP =P =0 010M=00 110 0011O = 10110 1011 0O =Cá thể cha mẹ Cá thể conChuo ãi lai giảHình 5. Lai đều4. Đột biến- Đột biến nhằm tạo ra những thông tin mới trong quần thể lai tạo tại các vò trí bit nào đótrong mỗi nhiễm sắc thể. Với xác suất đột biến trong quần thể là pthì số lượng nhiễm sắcthể bò đột biến sẽ là p*pop-size. Mỗi bít trong nhiễm sắc thể có cơ hội đột biến như nhauvà được thay đổi từ 0 thành 1 hay ngược lại:- Với mỗi nhiễm sắc thể trong quần thể và mỗi bít trong nhiễm sắc thể:Phát sinh 1 số ngẫu nhiên r trong khoảng [0,1Nếu r

Xem thêm  Cách tải Zalo về điện thoại dành cho Android và iOS siêu đơn giản

0Ngược lại f(x)=0- Trong đó Cminlà tham số đầu vào, có thể là trò tuyệt đối của u bé nhất trong quần thể hiệntại, hoặc trong k vòng lặp cuối cùng, hoặc là một hàm của biến quần the.å- Trong một vài trường hợp hàm thích nghi có thể là nghòch đảo của hàm mục tiêu hoặc làsai số trung bình bình phương của các tập mẫu trong quần thể.6. Xử lý các ràng buộc- GAs thích hợp cho các bài toán tìm kiếm tối ưu với điều kiện không ràng buộc. Tuy nhiênthực tế bài toán có thể chứa một hoặc nhiều ràng buộc phải thỏa. Lời giải nhận được từgchiến lược tìm kiếm tối ưu nhất thiết phải nằm trong vùng khả thi, tức phải thỏa tất cả cácràng buộc. Thông thường có thể xử lý các ràng buộc bằng hàm phạt. Một số hàm phạtthường được dùng như sau:- Hàm phạt tónh: f(x) = f(x) +iiTrong đó :f(x) là hàm mục tiêu;=1 nếu ràng buộc thứ i vi phạm;=0 nếu ràng buộc thứ i thỏa: hệ số phạt tương ứng khi ràng buộc thứ i vi phạm- Hàm phạt động: f(x,t) = f(x) +iidtS)(Với+=mqixhqixgii,1)(,1)((x), h(x) là các phương trình ràng buộc(x)0 với i=1, ,q(x) = 0 với i=q+1, m(t) =( )tCt : thế hệ vào thời điểm tính toán: hằng số, có giá trò bằng 1 hoặc 2- Hàm phạt thích nghi: f(x,k) = f(x) +ikVới≤≤+−∀∉≤≤+−∀∈tiktFiBtiktFiB1:)(/1:)(,/βλβλTrong đó :F:phần khả thi của không gian tìm kiếm.)(iB:biểu diễn cá thể tốt nhất trong thế hệ thứ i.>1 và7. Điều kiện kết thúc lặp của GAs- Để kết thúc vòng lặp GAs ,thường có thể chỉ đònh trước số thế hệ cần tạo ra sau đó kiểmtra lại độ thích nghi những phần tử tốt nhất bằng cách so sánh với bài toán ban đầu.IV) Các ứng dụng của GAs trong lónh vực quản lý xây dựng- Mawdesley [4] đã nghiên cứu và ứng dụng GAs trong công tác thiết lập tổng mặt bằng xâydựng. Trong nghiên cứu này, Mawdesley đã giải quyết các yếu tố tồn tại trong công tácthiết kế tổng mặt bằng cho 1 nhà máy ở Anh:+ Chọn phương án thi công xây dựng công trình tạm với điều kiện vật tư, nhân cônghạn chế.+ Chọn vò trí và diện tích tối ưu các đòa điểm cung cấp nguyên vật liệu như kho chứa ximăng, sắt thép, ván khuôn, trạm đổ bêtông. Thiết kế lộ trình cung cấp vật tư từ các đòa điểmnày đến nơi tiêu thụ và đường di chuyển của máy đào đất sao cho đạt được hiệu quả nhất.- Liên quan đến lónh vực tối ưu hóa tổng mặt bằng, Tam [5] đã sử dụng GAs để tối ưu hóacác vò trí cung cấp nguyên vật liệu xung quanh cần trục tháp cho một tòa nhà cao tầng ởHồng Kông- Trong các công trình xây dựng lớn như: xây đập, đường cao tốc, khoan hầm, công tác đất(đào đất, vận chuyển và đổ đất) chiếm một tỉ trọng lớn chi phí của công trình. Vì vậy việclựa chọn máy móc thiết bò, phương pháp thi công để tối ưu hóa công tác đất có ý nghóa quantrọng để giảm chi phí xâydựng công trình. Marzouk [6][7] đã nghiên cứu GAs kết hợp vớimô phỏng trên máy tính về đề tài tối ưu công tác đất trong luận án tiến só và báo cáo khoahọc trên tạp chí xây dựng ASCE (Mỹ). Trong nghiên cứu này Marzouk đã áp dụng GAs đểtối ưu việc lựa chọn các tổ máy móc thi công tham gia công tác vận chuyển 2.5 triệu mđấtra khỏi công trình xây dựng đến nơi chứa cách xa 15 km. Kết hợp với công tác lựa chọn máymóc thi công, trình tự và biện pháp thi công sẽ được mô phỏng trên máy tính sao chi phí xâydựng nhỏ nhất.- Một nhóm nghiên cứu tại Đại học South Bank [8] (Anh) đã nghiên cứu và ứng dụng GAsđể tối ưu hóa năng suất máy móc phục vụ công trình đào hầm theo phương pháp đúc mở;Kết quả của nghiên cứu đã được thực nghiệm qua 4 công trình trong thực tế để kiểm tra tínhxác thực của đề tài này.- Một ứng dụng quan trọng của GAs là tối ưu hoá tiến độ thi công với các ràng buộc về tàinguyên và nhân vật lực. Đây là lónh vực được nhiều nhà quản lí dự án quan tâm nhất. Đãcó rất nhiều nhà nghiên cứu tìm hiểu về lónh vực tối ưu hoá tiến độ cùng với việc cải tiếnGAs để đạt được mô hình hiệu quả nhất. Với sự đa dạng các yếu tố tác động đến tiến độ ,trong tương lai sẽ còn nhiều nhà nghiên cứu tìm hiểu về lónh vực này. Hegazy [9] ứng dụngGAs để lập tiến độ với điều kiện nhân lực bò giới hạn. Senouci [10] sử dụng GAs để thiếtlập mô hình tiến độ có xét đến các yếu tố như mối quan hệ giữa các công tác, cấu trúcthành phần tổ đội, cân bằøng nguồn lực theo tiến độ, cực tiểu hóa chi phí dự án sao cho thờigian hoàn thành công trình là ngắn nhất. Li và Love [11] nghiên cứu GAs để tối ưu hóa tiếnđộ với điều kiện thỏa hiệp về thời gian – chi phí- Trong quá trình thi công, việc cung cấp tài nguyên (vật tư, nhân công) làthường xuyên. Đểtránh rủi ro khan hiếm vật liệu, vật liệu tăng giá, do tiến độ thi công bò đẩy nhanh đột xuấtlàm cho thiếu hụt vật tư, nhân công, nhà thầu cần dự trữ những vật liệu gì? Số lượng baonhiêu? Vào thời gian nào? Đây chính là bài toán tối ưu hoá quản lí tài nguyên. Lew [12] đãứng dụng GAs để tối ưu hóa kế hoạch sử dụng tài nguyên lao động theo tiến độ. Hegazy[13] ứng dụng GAs để lựa chọn và bố trí cấu trúc thành phần tổ đội thi công các công tácsao cho đạt được năng suất chung cao nhất. Ngoài ra, nghiên cứu về lónh vực tối ưu hoá kếhoạch sử dụng tài nguyên lao động còn có nhiều nhà nghiên cứu khác như:, Chan [14],Syswerda[15], Satyanarayana [16]- Đối với các công ti thi công, vấn đề kiểm soát điều khiển nhiều công trình thi công cùnglúc là một điều rất khó khăn. Để hoàn thành các công trình đúng tiến độ với điều kiện bòhạn chế về vật tư, nhân công, thiếu vốn, đòi hỏi các nhà quản lí phải tính toán lựa chọn tốiưu sao cho đạt được kết quả tốt nhất. GAs có thể giúp giải quyết các bài toán tối ưu hóa sửdụng nguồn tài nguyên(dòng tiền tệ, nhân công, máy móc, vật tư) phân phối cho nhiều côngtrình các nhau trong một công ty xây dựng. Đề tài này đã được East [17] nghiên cứu vàkiểm nghiệm qua các dự án của trường Đại học Illinois. Lam và Gao [18] ứng dụng GAs đểtối ưu hóa dòng tiền phân phối cho nhiều công trình ở các công ti xây dựng của Trung QuốcTóm lai, bên cạnh lónh vực tối ưu hoá trong quản lí xây dựng, GAs còn có thể được ứngdụng trong lónh vực quản lí quản lí quy hoạch đô thò, đầu tư xây dựng và tài chính doanhnghiệp. Hy vọng trong tương lai sẽ có nhiều nhà nghiên cứu Việt Nam tìm hiểu về lónh vựctối ưu hóa bằng thuật giải di truyền./.Tài liệu tham khảo1. Nguyễn Đình Thú (2001). Lập trình tiến hóa, Nhà xuất bản giáo dục.2. Michlaewicz, Z.(1992). Genetic Algorithms + Data Structures= Evolutionary Programs.Second Edition, Springer-Verlag, Cambridge, Mass.3. David E. Goldberg.(1989). Genetic Algorithms in Search, Optimization and MachineLearning. Addision-Wesley Publishing Company, Inc.4. Michael J. Mawdesley; Saad H. Aljbi. Genetic Algorithms for Construction Site Layout inProject Planning. ASCE, Journal of Construction Engineering and Management.5. C.M.Tam.(2001). Genetic Algorithms for Optimizing Supply Locations around TowerCrane. City University of HongKong. HongKong.6.Mohamed Marzouk; Osama Moselhi.(2004). Multiobjective Optimization of EarthmovingOperations. ASCE, Journal of Construction Engineering and Management.7. Mohamed Marzouk.(2002).Optimizing earthmoving operations using computersimulation.PhD thesis, Concordia Univ.Motreùal.8. A.Haidar;S.Naoum;R.Howes.(1999). Genetic Algorithms Application and Testing forEquipment Selection.South Bank University.UK9. Tarek Hegazy.(1999). Algorithm for Scheduling with Multiskilled Constrained Resources.University of Waterloo. Canada.10.Ahmed B. Senouci.(2004). Use of Genetic Algorithms in Resource Scheduling ofComstruction Projects.ASCE, Journal of Construction Engineering and Management.11. H.Li; Peter Love.(1997). Using Improved Genetic Algorithms tp Facilitate Time-CostOptimization. ASCE, Journal of Construction Engineering and Management.12. Sou-Sen Lew.(1999). GA-Based Multicriteria Optimal Model for Construction Scheduling.National Taiwan University of Science and Technology, Taiwan.13. Tarek Hegazy.(1999). Optimization of Resource Allocation and Levelng Using GeneticAlgorithms. University of Waterloo.Canada.14. Chan, W.T.Chua.(1996). Construction resource scheduling with genetic algorithms. ASCE,Journal of Construction Engineering and Management.15. Syswerda,G.,and Palmucci,J.(1991). The Application of Genetic Algorithms to ResourceScheduling.Proc, 4 th Int. Conf on Genetic Algorithms, R.K Belew and L.B.Booker,MorganKaufman.San Mateo, California. USA.16. Satyanarayana.(1993).Optimum resource allocation in construction project using geneticalgorithms.Proc,3rdInd.Conf, on the Application of AI to Civil and Structure Engineering,Edinburgh, UK.17. E.W.East(1998). Dynamic, Multi-project Scheduling Under Limited Resources withUncertain Project Demand. Construction Engineering Research Laboratories, ATTN. USA.18. K.C.Lam, H.Gao(2003). Optimizing Multi-project Cash Flow for Chinese ConstructionFirms. City University of HongKong. HongKong.19. Lª KiÒu. Sö dông thuËt to¸n di truyÒn trong tæ chøc s¶n xuÊt x©y dùng, T¹p chÝ X©y dùng5/2004

Xem thêm  Tổng quan về vi điều khiển, cấu tạo và cách hoạt động

Xem thêm: Glucozơ: tính chất vật lý hóa học, điều chế và ứng dụng

Source: https://bem2.vn
Category: Ứng dụng hay

Rate this post

Bài viết liên quan

Để lại ý kiến của bạn:

Email của bạn sẽ không được hiển thị công khai.