Home Page OR Soft Computing Research GIẢI THUẬT DI TRUYỀN
GIẢI THUẬT DI TRUYỀN

GIẢI THUẬT DI TRUYỀN

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa, ĐHQG TPHCM

 

 

Darwin cha đẻ của thuyết tiến hóa khảo sát sự tồn tại của một sinh thể phụ thuộc vào quy luật đấu tranh sinh tồn hay quy luật tồn tại của các cá thể thích nghi trong quá trình chọn lọc tự nhiên. Darwin xác định rằng thế hệ mới của các sinh vật ra đời qua quá trình tái  sinh, lai ghép và đột biến từ những cá thể hiện hữu.

 

Giải thuật di truyền giải thuật tìm kiếm tối ưu được John Holland đề nghị vào năm 1975. Giải thuật di truyền mô phỏng quá trình tiến hoá tự nhiên nhằm giải các bài toán tối ưu qua việc tìm kiếm ngẫu nhiên trong một tập phương án đã cho với mục đích tìm ra phương án tốt nhất theo một tiêu chuẩn đánh giá được mô tả bởi một hàm mục tiêu hay còn gọi là hàm thích hợp.

 

Các khái niệm của thuyết tiến hoá được sử dụng ở giải thuật tìm kiếm, nhằm tìm ra lời giải một cách tự nhiên. Đầu tiên các phương án có thể, khác nhau của bài toán được tạo ra. Các lời giải này được đánh giá qua mức độ thích hợp. Quá trình chọn lọc sẽ chọn các lời giải tốt và loại các lời giải không tốt còn lại như quá trình chọn lọc tự nhiên các cá thể thích nghi. Các lời giải được chọn sẽ qua quá trình tái sinh, lai ghép, đột biến để tạo thế hệ các lời giải mới với kỳ vọng thế hệ mới này sẽ tốt hơn thế hệ trước. Quá trình sinh sản và đánh giá các thế hệ cứ tiếp tục cho đến khi có sự hội tụ thế hệ, hay thế hệ mới không khác gì thế hệ cũ. Kỹ thuật này có ưu điểm là tìm kiếm lời giải trên một dãi rộng các lời giải có thể hơn là giới hạn tìm kiếm trên một miền hẹp với kỳ vọng kết quả sẽ ở trong miền này.

 

Giải thuật di truyền thực hiện với tập phương án hữu hạn, với các bài toán tối ưu có tập phương án liên tục hay vô hạn cần phải rời rạc hoá tập phương án liên tục hay vô hạn này để có tập phương án hữu hạn thích hợp. Giải thuật di truyền mã hoá các phương án bởi các chuỗi ký tự được gọi là nhiễm sắc thể, chuỗi ký tự tạo bởi một số hữu hạn các ký tự được gọi là gien, gien được lấy từ một tập ký tự được gọi là tập gien xác định.

 

 

TLTK

Nguyễn Như Phong. Vận trù mềm. NXBĐHBK. 2013.

 

 

 
  • thiet ke noi that chung cu

  • thiet ke noi that chung cu

  • thiet ke noi that chung cu

  • thiet ke noi that chung cu

ABOUT US

ADMIN


GOOD BROWSERS

 
   

STATISTIC

mod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_counter
mod_vvisit_counterH�m nay124
mod_vvisit_counterH�m qua199
mod_vvisit_counterTu?n n�y1264
mod_vvisit_counterTh�ng n�y1264
mod_vvisit_counterT?t c?731320
Hiện có 17 khách Trực tuyến