Một Thuật Toán Di Truyền Mới cho Vấn Đề Tối Ưu Tổ Hợp Phụ Thuộc Thời Gian

National Academy Science Letters - Tập 39 - Trang 207-211 - 2016
D. Venkatesan1, K. Kannan2, S. Raja Balachandar2
1School of Computing, SASTRA University, Thanjavur, India
2School of Humanities and Sciences, SASTRA University, Thanjavur, India

Tóm tắt

Trong bài báo này, một Thuật Toán Di Truyền Mới (NGA) dựa trên toán tử chọn lọc tìm kiếm xung quanh tâm khối lượng được trình bày nhằm giải quyết một trong những vấn đề khó khăn phụ thuộc vào thời gian, đó là Vấn Đề Đấu Thầu Đường Cao Tốc, với mục tiêu tìm ra chi phí phụ thuộc vào thời gian tối thiểu để xây dựng liên kết giữa các thành phố. Hiệu suất của NGA được đánh giá trên 120 bài kiểm tra tiêu chuẩn với nhiều kích thước liên kết và đấu thầu khác nhau và so sánh với các Thuật Toán tiên tiến nhất hiện nay. Kết quả tính toán cho thấy NGA cung cấp các giải pháp chất lượng cao cho tất cả các vấn đề và các giải pháp tối ưu chuẩn xác cho tất cả các vấn đề, kích thước của chúng dao động từ 4 đến 18.000 liên kết cho 10 đến 22.000 đấu thầu.

Từ khóa

#Thuật Toán Di Truyền #Tối Ưu Tổ Hợp #Vấn Đề Đấu Thầu Đường Cao Tốc #Tối Ưu Hóa Phụ Thuộc Thời Gian #Chi Phí Tối Thiểu

Tài liệu tham khảo

Michael RG, David SJ (1979) Computers and intractability: A guide to the theory of NP-completeness. Macmillan Higher Education, New York Gargano ML, Edelson W (2001) Optimal sequenced matroid bases solved by genetic algorithms with feasibility including applications. Congr Numer 150:5–14 DeCicco J (2002) Sensitivity analysis of certain time dependent base models solved by genetic algorithms. DPS Dissertation, Pace University DeCicco J, Gargano ML, William E (2002) A minimal bidding application (with Slack Time) solved by a genetic algorithum where element costs are time dependent GECCO-2002- Genetics And Evolutionary Computation Conference NY Gargano E et al (2003) Evolving efficient security systems under budget constraints using genetic algorithms. Genetic and Evolutionary Computation Conference, Chicago Glover F, Kochenberger A (2003) Handbook of metaheuristics. Kluwer Publishers, Philadelphia Diaz R (2004) Solving a class of time-dependent combinatorial optimization problems with abstraction, transformation and simulated annealing. PhD Thesis, Pace University Kasinadhuni MP (2004) Solving optimization problems using genetic algorithms with multiple genome coding. Ph.D. Thesis, Pace university Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading Osman KE, Ibrahim E (2006) A new optimization method: big bang–big crunch. Adv Eng Softw 37:106–111 Dorigo M, Stutzle T (2004) Ant colony optimization a bradford book. MIT Press, Cambridge, London Clerc M (2004) Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: Babu BV, Onwubolu GC (eds) Studies in fuzziness and soft computing new optimization techniques in engineering, vol 141., pp 219–239 Dorigo M, Gambardella L (1997) Ant colonies for the traveling salesman problem. Biosystems 43:73–81