Đề tài Giải thuật Gen

qua 3 chương trình con prescale ,scale , scalepop. procedure prescale(umax,uavg,umin :real; var a,b :real); {tính các hệ số co cho phép co tuyến tính} const fmultiple = {bội số của phép co là 2} var delta :real; {ước số} Begin if umin > (fmultiple * uavg – umax) / (fmultiple –1.0) {kiểm tra không âm} then begin {phép co thông thường} delta := umax –uavg; a := (fmutiple – 1.0) * uavg / delta ; b := uavg * (uavg – fmultiple * uavg) / delta ; end else begin {co thật nhiều nếu có thể được} a:= uavg / delta ; b:= -umin * uavg / delta ; end; end; function scale(u,a,b :real) :real; {co một giá trị của hàm mục tiêu} Begin scale := a * u + b; end; procedure scalepop (popsize :integer ;var max ,avg ,min ,sumfitness :real ; var pop :poulation) ; {co toàn bộ dân số} var j :integer ; a ,b :real ; {độ dốc và phần bị chắn cho phương trình tuyến tính} Begin prescale(max ,avg ,min ,a ,b) ; {nhận độ dốc và phần bị chắn cho hàm} sumfitness := 0.0 ; for j:= 1to popsize do begin fitness :=scale(objective ,a ,b) ; sumfitness := sumfitness + fitness ; end; end; Thủ tục prescale nhận các giá trị thích nghi thô trung bình ,tối đa và tối thiểu ,là uavg ,umax ,umin và tính toán các hệ số co tuyến tính a và b dựa trên logic .Nếu có thể thì co đến bội sô 1mong muốn Cmult (trong chương trình là fmultiple) ,sau đó thực hiện tính toán .Mặt khác việc thực hiện co bằng cách chốt quanh giá trị trung bình và kéo giãn độ thích nghi cho đến khi giá trị cực tiểu dần đến 0 .Thủ tục scale sẽ được gọi sau thủ tục prescale để co tất cả các giá trị thô của các cá thể bằng cách dùng hàm scale đơn giản .Ở đây chúng ta giả thiết rằng các giá trị thích nghi thô được lưu trữ trong record indivadual trong một giá trị thực được gọi là objective(pop[j].objective) .Các độ thích nghi đã co được đặt vào thông số thực fitness ,và tổng thích nghi sumfitness sẽ được tính lại . Bằng cách này ,phép co đơn giản sẽ giúp ta ngăn chặn những chi phối sớm của những cá thể đặc biệt ,để khuyến khích sự cạnh tranh lành mạnh giữa những cá thể gần bằng nhau .Tuy nhiên ,điều này không phải là toàn bộ những nghiên cứu của chúng ta về các biến đổi hàm mục tiêu có thể có . VIII-MÃ HOÁ : Để biến đổi chuỗi có chiều dài hữu hạn thành các thông số của bài toán tối ưu hoá .chúng ta đã giới thiệu một mã nhị phân đơn giản để giải bài toán bậc công tắc nhị phân đơn giản .Trong phép mã hoá này chúng ta cho phép nối dài các bit 0 ,1 ,trong đó giá trị 0(hay 1) thứ I chỉ rằng công tắc thứ I là tắt (hay mở) .Chúng ta cũng đã giải mã chuỗi nhị phân này thành số nguyên không dấu. Mặt dù ,cách mã hóa này cho chúng ta một sự linh hoạt nào đó ,nó không cung cấp đủ các chọn lựa mà chúng ta cần để giải quyết các bài toán mà chúng ta gặp trong khoa học ,kinh doanh và kỹ thuật .Trong phần này chúng ta giải quyết 2 nguyên lý cơ bản của sự mã hóa trong GAs để giúp thiết kế mã cho các bài toán khác nhau .Sau đó ,chúng ta sẽ nghiên cứu cách mã hóa chuỗi nhị phân ,đã biến đổi và đa thông số ,mà cách này đã chứng tỏ có ích lợi tropng nhiều bài toán khác nhau . Về một phương diện nào đó mã hóa một bài toán cho việc tìm kiếm trong GAs không phải là vấn đề lớn ,vì các lập trình viên GAs bị hạn chế nhiều bởi sự hình dung của họ .Chúng ta đã thấy trong chương trứớc ,các GAs khai thác những sự tương đồng trong các mã tùy ý ,cũng như là những viên gạch xâydẫn đến điểm gần tối ưu . Chúng ta dựa trên 2 nguyên lý cơ bản để mã hóa GAs : Nguyên lý khối gạch xây có nghĩa và nguyên lý bộ ký tự tối thiểu . Nguyên lý khối gạch xây có nghiã : Ngưòi sử dụng nên chọn cách mã hóa sau cho các sơ đồ bậc thấp ,ngắn sẽ thích hợp với bài toán đã cho và không có liên hệ tương đối với sơ đồ trên các vị trí khác. Nguyên lý bộ ký tự tối thiểu :Người sử dụng nên chọn bộ ký tự nhỏ nhất cho phép diễn tả bài toán một cách tự nhiên . Bảng sau sẽ thấy các chuỗi nhị phân với độ thích nghi của chúng : có được bằng cách giải mã một chuỗi nhị phân thành một số nguyên không dấu và sau đó đánh giá độ thích nghi bằng hàm f(x) = x2 . Chuỗi nhị phân Trị x Chuỗi không nhị phân Độ thích nghi 01101 13 N 169 11000 24 Y 576 01000 8 I 64 10011 19 T 361 Sự tương quan giữa mã nhị phân và mã không nhị phân Nhị phân Không nhị phân 00000 A 00001 B 00010 C … … 11001 Z 11010 1 11011 2 … … 11111 6 Trong trường hợp nhị phân vi65c tìm kiếm những tương đồng quan trọng có thể thực hiện bằng một số lượng nhỏ ký tự của bảng chữ cái .Trong trường hợp không nhị phân ,chúng ta chỉ có 4 chuỗi ký tự đơnvà các giá trị thích nghi của chúng ;không có sự tương đồng về mặt mã để khai thác . Để hiểu điều này một cách toán học hơn ,chúng ta so sánh số lượng sơ đồ có sẳn trong mã nhị phân với một sơ đồ có sẳn trong mã không nhị phân .Trong cả hai trưòng hợp mã nhị phân và không nhị phân phải mã hóa một số lượng như nhau các giải pháp ,tuy nhiên những phần chính của bộ ký tự khác nhau yêu cầu những chiều dài chuỗi khác nhau .Để cân bằng số điểm trong mỗi không gian ,chúng ta cần 2l = kl’ ,trong đó l là chiều dài chuỗi theo mã nhị phân ,l’ là chiều dài chuỗi theo mã không nhị phân .Số lượng sơ đồ theo mỗi cách mã hóa có thể được tính toán bằng cách sử dụng chiều dài chuỗi tương ứng : 3l cho trường hợp nhị phân va(k+1)l’ cho trường hợp không nhị phân.Dể dà chỉ ra rằng bộ ký tự nhị phân cung cấp một số sơ đồ tối đa trên một bit thông tin trên bộ mã bất kỳ .Từ đó, những tương đồng này là điều thiết yếu cho sự tìm kiếm,khi chúng ta thiết kế một bộ mã chúng ta nên cực đại hóa số lượng khả dụng của chúng cho GAs khai thác . IX-CÁC RÀNG BUỘC : Chúng ta chỉ mới thảo luận GAs để tìm kiếm những hàm mục tiêu không ràng buộc .Nhiều bài toán thực tế chưá một hay nhiều ràng buộc .Trong phần này chúng ta xét sự hợpnthành trong tìm kiếm theo GAs. Các ràng buộc thường được phân lớp thành các quan hệ bằng nhau hay khác nhau .Từ đó,các ràng buộc “bằng nhau” có thể được xếp vào một mô hình hệ thống – hay hộp đen ,chúng ta chỉ quan tâm đến những ràng buộc “khác nhau”.Đầu tiên ,có thể xuất hiện những ràng buộc “khác nhau” mà có thể không tạo ra bài toán riêng .Một GAs sinh ra một trình tự các thông số được kiểm tra nhờ mô hình hệ thống ,hàm mục tiêu và các ràng buộc .Đơn giản là chúng ta chỉ cần chạy mô hinh ,đánh giá hàm mục tiêu ,và kiểm tra để phát hiện các ràng buộc bị vi phạm.Nếu không tập thông số sẽ được gắn giá trị thích nghi phù hợp với sự đánh giá hàm mục tiêu .Nếu ràng buộc bị vi phạm ,giải pháp sẽ là không khả thi và do đó không thích nghi .Thủ tục này là tốt ,ngoại trừ các bài toán ứng dụng bị ràng buộc cao ;việc tìm thấy một điểm khả thi cũng khó khăn như tìm ra điểm tốt nhất .Kết quả là ,chúng ta thường muốn rút ra một số thông tinnào đó về giải pháp không khả thi ,có thể bằng cách giảm tầm quan trọng của thích nghi trong mối quan hệ với mức độ vi phạmcủa ràng buộc .Đó chính là phương pháp chụi phạt. Trong phương pháp chụi phạt ,một bài toán ràng buộc trong tối ưu hóa được biến đổi thành bài toán kông ràng buộc bằng cách kết hợp với phí tổn hay phạt với tất cả phạm vi ràng buộc .Phí tổn này được bao hàm trong sự đánh giá hàm mục tiêu .Thí dụ ,bài toán ràng buộc ban đầu với dạng tối thiểu hóa: tối thiểu hóa g(x) phụ thuộc vào hi(x) >= 0 ,I = 1,2,…,n trong đó x là một m-vectơ Chúng ta dổi sang dạng không ràng buộc : tối thiểu hóa g(x) + r. Trong đó F : hàm phạt r : hệ số chụi phạt Có một số giải pháp thực hiện hàm phạt F .Ở đây, chúng ta lấy bình phương của vi phạm ràng buộc , F|hi(x)| = hi2(x) cho tất cả mọi ràng buộc i bị vi phạm .Dưới điều kiện xác định ,giải pháp không ràng buộc sẽ hội tụ đến giải pháp ràng buộc ,khi hệ số phạt r dần đến vô cực.Trong thực tiễn ,các giá trị r trong các GAs thưởng được xáx dịnh độc lập cho mỗi ràng buộc ,vì thế những vi phạm vừa phải cuả các ràng buộc sẽ sinh ra các phần phạt ,đó là một số phần trăm đáng kể của chi phí hoạt động theo danh nghiã . --------------- ***------------------ CHƯƠNG IV SỰ CẢI TIẾN VÀ ỨNG DỤNG CỦA GIẢI THUẬT GEN I-SỰ CẢI TIẾN CỦA GIẢI THUẬT GEN: 1.Sự tiến hóa của giải thuật gen: Qua các chương , những khái niệm cơ bản của GAs đã được đề cập ,tuy nhiên để GAs thực thi có hiệu quả hơn ,người ta đã thực hiên một số cải tiến GAs chuẩn này.Trước tiêncải tiến dựa trên chọn lọc các sơ đồ và sau đó là một số cải tiến trên toan tử gen. a/Cải tiến trong việc chọn lựa các sơ đồ: Việc chọn lọc các sơ đồ được sử dụng trong GAs chuẩn đó là lựa chọn trên bánh xe roulette .Những sơ đồ này là những thành viên tốt nhất nhưng có thể thất bại trong các lần sinh kế tiếp và có thể dẫn đến những lỗi ngẫu nhiên .Để cải thiện điều này , một vài phương pháp cải tiếnđược liên kết cùng với việc chọn lựa trên bánh xe roulette đã được tiến hành. Chọn lọc ưu tú (elitist): Chiến thuật này nhằm sao chép lại thành viên tốt nhất trong một thế hệ và đưa nó vào trong thế hệ kế tiếp .Chiến thuật này có thể gia tăng tốc độ tôí ưu của một dân số bởinhững cá thể tốt và do đó không những cải thiện được việc tìm kiếmcục bộ mà còn làm cho GAs được thực hiện hoàn chỉnh hơn . Chọn lọc khi lấy mẫu (Deterministic Sampling): Trong một sơ đồ ,xác suất chọn lọc thường được tính như sau : pselecti = fi /S fj .Sau đó số con cái ei trong một chuỗi Ai được tính bởi ei = n * pselecti .Mỗi chuỗi sẽ cấp phát một số con cái tùy thuộc vào giá trị ei .Những chuỗi còn lại cần phải điền cho đầy một dân số thì sẽ được lấy ra theo thứ tự từ đầu dân số đã được sắp xếp trước . Lấy phần mẫu còn lại ngẫu nhiên có thay thế (Remainder Stochatic Sampling With Replacement) :Sau khi đã tính số con cái ei trong một sơ đồ đã được chọn lọc để lấy mẫu trong giai đoạn trên , thì phần nguyên của ei sẽ gán cho những cá thể có trong dân số đó ,còn phần lẻ của ei sẽ được sử dụng để tính trọng số trong việc chọn lựa trên vòng tròn bánh xe để sinh ra các cá thể còn lại. Lấy mẫu còn lại ngẫu nhiên và không thay thế ( Remainder Stochatic Sampling Without Replacement ) :Cũng tương tự như trên nhưng phần lẻ của giá trị ei bây giờ được xem như là xác suất. Hay nói cách khác ,số lần tham gia vào trong quá trình sinh sản của một chuổi bằng với giá trị phần nguyên của ei .Sau đó ,để đảm bảo đủ kích thước dân số , ta chọn những con cái khác của những chuỗi với xác suất tương đương với phần lẻ của số cá thể mong đợi cho đến khi đạt được kích thước dân số n .Ví dụ 1 chuỗi với số bản copy mong đợi là 1.5 ,chắc chắn sẽ nhận được một bản copy và một bản copy khác với xác suất 0.5 Ranking Procedure : Theo phuơng pháp này ,một dân số được sắp xếp tùy thuộc vào giá trị fitness .Sau đó ta gán các cá thể này cho mỗi một con cháu mà có hàm gần giống với Rank .Một hàm Rank do BanKer đề ra (1985) : Count Rank Khi đó : Trong đó lmax là giá trị do user đưa vào ,1 < lmax <=2 với n là kích thước dân số .Miền ei sau đó sẽ là[2 - lmax , lmax].Phương trình trên là một trường hợp đặc biệt. 2-Cải tiến trên các toán tử tối ưu : GAs là sự kết hợp của 3 toán tử :tái tạo ,ghép chéo và đột biến .Chúng tác động ở cấp độ trên toàn bộ dân số ,ta có một số cải tiến trên các toán tử này như sau: Ghép chéo nhiều điểm: Toán tử ghép chéo mà ta sử dụng từ trước đến giờ là ghép chéo chỉ trên 1 bit đơn tại 1 vị trí được. Quá trình ghép chéo này có thể tiến hóa thành ghép chéo nhiều điểm mà trong đó số điểmghép chéo sẽ được cho trước Nc .Khi Nc = 1 thì trở thành ghép chéo đơn ,với Nc chẳn chuỗi được xem như là một chuỗi không có sự bắt đầu và kết thúc ,và số điểm ghép chéo Nc được chọn xung quanh một vòng tròn đồng nhất một cách ngẫu nhiên. Quá trình ghép chéo nhiều điểm có thể giải quyết 1 tổ hợp cụ thể các đặt tính đã được mã hóa trên một chuỗi nhiễm sắc thể mà sự ghép chéo một điểm không giải quyết được. Giả sử ta có hai chuỗi : Chuỗi 1 : 10110001100 Chuỗi 2 : 00101101001 Trong đó các bits gạch dưới biểu diễn cho những sơ đồ có tính hoàn thiện cao .Giả sử một trong hai sơ đồ này hoán chuyển thì sẽ mất đi thuận lợi trong quá trình ghép chéo .Rõ ràng ghép chéo một điểm không thể tránh được điều này ,sơ đồ 1 sẽ bị phá vỡ và không được truyền đi .Vấn đề này có thể giải quyết bằng ghép chéo hai điểm như sau : Chuỗi 1 : 1 0 1 1 | 0 0 0 1 | 1 0 0 Chuỗi 2 : 0 0 1 0 | 1 1 0 1 | 0 0 1 Chuỗi con 1 : 1 0 1 1 1 1 0 1 1 0 0 Chuỗi con 2 : 0 0 1 0 0 0 0 1 0 0 1 Một cách khác thể hiện sự ghép chéo nhiều điểm là ghép chéo đồng nhất đã được giới thiệu bởi Syswerda(1989) .Theo cách này ,hai chuỗi parents được chọn và hai chuỗi children sẽ được tạo ra .Với mỗi vị trí trên hai chuỗi con ,chúng ta quyết địng ngẫu nhiên chuỗi cha nào đó đóng góp giá trị bit vào chuỗi con này tùy thuộc vào khuôn mẫu (template) đã được chọn ngẫu nhiên .Quá trình được mô tả như sau : parent 1 : 01100111 parent 2 : 11010001 template: 01101001 Tương ứng với 0 thì lấy chuỗi 1 còn 1 thì lấy chuỗi 2 và ngược lại.Kết quả : child 1 : 11110001 child 2 : 01000111 Mặc dù ghép chéo nhiều điểm có ưu điểm trên ,nhưng đôi khi nó dẫn đến cấu trúc phức tạp . Các toán tử tái lập lại bậc : Không giống như toán tử từ trước chỉ tìm kiếm trên tập allele tốt ,các toán tử này còn tìm kiếm trên những cách mã hóa cũng như tập các giá trị allele tốt hơn .Những toán tử này thích hợp cho bài toán mà giá trị fitness phụ thuộc vào sự sắp xếp chuỗi ,chẵn hạn như trị fitness phụ thuộc vào tổ hợp của các giá trị allele v và bậc o , f = f(v,o) ,một chuỗi kết hợp các giá trị allele và các thônh tin có thể biểu diễn như sau : 12345678 10010001 Trong đó 1,2 … 8 biểu diễn vị trí gen hay tên gen .Thông thường các toán tử tái lập lại bậc là toán tử đảo chiều .Với toán tử này ,người ta chọn hai điểm trên chiều dài chuỗi ,sau đó ta tiến hành cắt lại điểm này ,và những điểm cuối của phần cắt sẽ hoán chỗ cho nhau . Ví dụ ,hai chuỗi có 8 bit sẽ hoán đổi như sau : 1 2 | 3 4 5 6 | 7 8 0 1 | 1 1 1 0 | 1 0 Sau khi hoán đổi ta có : 1 2 6 5 4 3 7 8 0 1 0 1 1 1 1 0 3/ Giải thuật lai gen : Giải thuật lai gen đơn giản ,mặc dù mạnh mẻ ,nhưng nói chung không phải lúc nào giải thuật cũng đạt tối ưu hoá .Ghép chéo hoá một GA với GA hiện có có thể sinh ra một giải thuật tốt hơn cả GA và giải thuật hiện tại .Vì vậy , đối với các bài toán tối ưu hoá , khi có nhiều giải thuật tối ưu hoá một cách có hiệu quả ,thì có thể sử dụng nó cho vấn đề tối ưu .Một GA có thể ghép chéo vơí nhiều kỹ thuật tìm kiếm khác nhau ,để taọ ra một dạng ghép chéo mà khai thác được việc tìm kiếm toàn cục và cả tìm kiếm cục bộ. Có rất nhiều kỹ thuật đạo hàm và không đạo hàm có sẵn cho việc tìm kiếm tối ưu hóa cục bộ trong các hàm tính toán quaen thuộc .Mặc dù không có những hàm tính toán quen thuộc ,vẫn luôn luôn có những sơ đồ tìm kiếm tối ưu cho bài toán đặc biệt .Trong một số trường hợp ,sự kế thừa ghép chéo đã đưa ra việc biểu diễn tốt cũng như kỹ thuật tốt trang việc sử dụng . II-ỨNG DỤNG CỦA GIẢI THUẬT GEN : 1 / Tối ưu hóa đường ống : David E.Golderg đã ứng dụng GAs để tối ưu hóa bài toán điều khiễn hệ thống đường ống dãn khí thiên nhiên . Trong bài roán đầu tiên ,ông đã xem xét bài toán của Wong và Larson ,với hệ thống 10 máy nén khí ,10 ống dẫn khí nối tiếp . Bài toán bị chi phối bởi phương trình chuyển đổi phi tuyến ,chỉ ra sự sụt áp qua các đường ống và sự tăng áp khi qua máy nén. Để kiểm tra GAs đơn giản trong các bài toán đường ống khác nhau , tác giả đã mã hoá bài toán điều khiển nhất thời một đường ống của Wong và Larson .Trong bài toán này, mục tiêu là cực tiểu hóa năng lượng do quá trình nén ,phụ thuộc vào áp suất tối đa và áp suất tối thiểu và các ràng buộc tỉ lệ áp suất . Các chi tiết nhất thời mà tác giả đã dùng vượt quá phạm vi nghien cứu .Điều này đủ để noí rằng các phương trình riêng phần đã đơn giản hoá tính liên tục và động lượng được chuyển đổi thành các phương trình vi phân thông thường bằng cách dùng các phương pháp đặc thù .Sau đó ,các phương trình này được giải quyết bằng số trên một mạng lưới thời gian thông thường bởi thủ tu5c vi phân hữu hạn .Cũng như bài toán trạng thái bền ,các ràng buộc được đưa vào bài toán bằng phương pháp phạt bên ngoài ,dạng bậc hai. 2 / Tối ưu hoá kết cấu qua GAs : Tác giả đã áp dụng GAs vào việc tối ưu hóa kết cấu của một khung phẳng gồm 10 thanh. Mục tiêu của bài toán này là cực tiểu hóa trọng lượng của kết cấu ,Phụ thuộc vào các ràng buộc về ứng suất lớn nhất và ứng suất nhỏ nhất của mỗi thanh .Trong công trình của tác giả ,một bộ mã cho khung kết cấu theo ma trận tiêu chuẩn được dùng để phân tích mỗi thiết kế tạo ra bởi GAs .GAs 3 toán tử bao gồm lựa chọn bằng bánh xe roulette ,ghép chéo đơn giản và đột biến đưọc dùng với các ràng buộc kề nó ,sử dụng hàm phạt bên ngoài ,dạng bậc hai .Các biến thiết kế , 10 vùng thành phần Ai ,được mã hoá như là một chuỗi dạng dấu chấm cố định ,được biến đổi ,được nối kết ,trong đó 1 trong 10 chuỗi con 4 bit được biến đổi tuyến tính giữ a giá trị = 0.1 in2 và Amax = 10 in2 .Kết quả các lần chạy độc lập của GAs chỉ rằng độ hộim tụ không khác biệt so với các nghiên cứu quan sát trước đây. 3 / Ghi ảnh y học với GAs : Các tác giả đã sử dụng GAs đơn giản để thực hiện ghi hình ảnh ,như là bộ phận của hệ thống lớn có tên là Digital Subtraction Angiography (DSA) .Trong DSA ,Bác sĩ sẽ cố gắng xem xét bên trong của một động mạch khả nghi bằng cách so sánh hình ảnh x-quang ,một được chụp trước khi tiêm thuốc đã nhuộm màuvào động mạch ,một và một được chụp sau khi tiêm thuốc .Cả hai hình được số hóa và được trừ nhau theo từng điểm một ,với kết quả mong muốn cuối cùng nhận được một hình ảnh sai khác phác họa rõ ràng hình ảnh bên trong động mạch chủ .Nếu sự khác biệt gữa hai hình ảnh chỉ là sự bổ sung của phần nhuộm màu thì phép trừ ảnh phải để lại hình ảnh chỉ riêng phần bị phủ màu .Tuy nhiên sự chuyển động nhẹ của bệnh nhân có thể tạo ra hai hình ảnh kế nhau ,làm rối loạn phần hình ảnh sai khác .Kết quả là ,các hình ảnhphải được xếp kế nhau ,để tính toán phần hình ảnh sai khác. Các tác giả đã sử dụng GAs .Trong thủ tục này ,hình ảnh trước khi tiêm thuốc được chuyển đổi bởi bởi một phép biến đổi tuyến tính .GAs được dùng để tìm kiếm các hệ số biế đổi để tìm kiếm các hệ số giúp cực tiểu hóa sự sai biệt hình ảnh trước và sau khi tiêm ,trên cơ sở các sai khác hình ảnh tuyệt đối. 4 /Ứng dụng GAs trong C++ : Trong phần 2 của nội dung đề tài này chúng ta sẽ vận dụng GAs vào trong mội trường C++ để giải quyết hai lĩnh vực : Tối ưu hóa và máy hữu hạn . Trong lĩnh vực tối ưu hóa đầu tiên chúng ta giải quyết bài toán về hộp đen ,sau đó là vận dụng sự tối ưu hóa trong chọn lọc tự nhiên để giải bài toán tối ưu hóa hàm nhiều biến ,tiếp theo là vận dụng GAs trong bài toán tối ưu trong du lịch .Trong lĩnh vực máy hữu hạn chúng ta vận dụng GAs xem xét máy tiến hoá. CHƯƠNG V BÀI TOÁN HỘP ĐEN --------*****-------- I-YÊU CẦU VẤN ĐỀ: Trong chương này ta ứng dụng GAs vào môi trường C++ để giải bài toán Giải mã hộp đen (hay Tố ưu hoá hộp đen) . Hộp đen (Blackbox) có một ngõ vào (input) và một ngõ ra ,mỗi giá trị đầu vào cho một giá trị đầu ra ,yêu cầu tìm các giá trị đầu vào tương ứng với các giá trị đầu ra. Bài toán cho thấy sức mạnh của GAs trong C++ ,đồng thời kết hợp những cải tiến nhằm nâng cao hiệu quả của GAs. Nguyên tắc của hộp đen là chúng ta hoàn toàn không biết gì về hoạt động bên trong hộp đen ,chỉ cho biết các điều kiện bên ngoài như sau: - Đầu vào của hộp là số nguyên không dấu có chiều dài 32 bit. - Đầu ra của hộp là số nguyên không dấu 32 bit có giá trị từ 0 đến 32. - Chỉ có một giá trị đầu vào chưa biết sẽ cho ra giá trị đầu ra là 32. -Những giá trị đầu ra nhỏ hơn 32 được tao ra từ nhiều giá trị đầu vào. - Không có thông tin liên quan rõ ràng gữa giá trị đầu vào và giá trị đầu ra.Ví dụ :Đầu vào là 10 cho giá trị đầu ra là 4 ,trong khi đầu vào là 32 thì cho giá trị đầu ra là 0. Nhiệm vụ của bài toán là tìm các giá trị đầu ra tương ứng với các giá trị đầu vào, cụ thể tìm giá trị đầu vào mà nó cho ra giá trị đầu ra là 32. Với điều kiện của hộp đen như thế ta khai báo hàm Blackbox với chức năng tương ứng như sau: long Blackbox(long x); Tham số đưa vào kiểu long ,hàm trả về là giá trị kiểu long. long Blackbox(long x); { static const long n = 0x11DE784AL;//299.792.458 long fit = 0L; long mask = 1L; for(int i=0;i < 32;++i) { if((x & mask)==(n & mask)) ++fit; mask <<= 1; } //tra ve gia tri giua 0 va 32 return fit; } II-CÁC THÔNG SỐ : 1-DÂN SỐ(Populations): Tham số được sử dụng ở hàm Blackbox kiểu long ,nên ta định nghĩa dân số là một mãng kiểu long ,mỗi phần tử là một nhiễm sắc thể (Chromosome) là một chuỗi có chiều dài 32 bit .Giá trị đầu ra của Blackbox là độ thích nghi (fitness) tương ứng của một dân số ,nhiệm vụ của bài toán là tìmgiá trị lớn nhất được trả lại từ Blackbox cho một thành viên dân số cho trước .Do đó, ta cần định nghiã mãng thứ hai cũng kiểu long có cùng kích thước với mãng đầu tiên để giữ giá trị đầu ra từ Blackbox . size_t m_PopSize ; // kích thước dân số long * pop = new long[m_PopSize]; //mãng chứa dân số cũ Giả sử ta không tìm thấy đầu vào tạo ra đầu ra là 32 ,ta cần tạo ra dân số mới (children) từ dân số cũ (parents) ,dùng giá trị thích nghi quyết định cho sự sinh sản thành công ,việc chọn lựa được dựa vào thực hiện bởi cơ chế quay bánh xe roulette . long * newpop = new long[m_PopSize]; // mãng chứa dân số mới (children) long * fit = new long[m_PopSize]; // mãng chứa độ thích nghi. 2-CHỌN LỰA BÁNH XE ROULETTE : Việc chọn lựa nhiễm sắc thể cho quá trình sinh sản đựơc điều khiển bằng cách quay bánh xe roulette như đã nói ở phần 1 .Bánh xe có các khe hở (phần) khác nhau tương ứng với độ thích nghi của các cá thể , việc chọn lựa ngẫu nhiên rơi vào phần nào thì nhiễm sắc thể được chọn là parents cho quá trình sinh sản ,sau đó quá trình chọn lựa được tiếp tục .Như vậy, nhiễm sắc thể nào có độ thích nghi cao sẽ có cơ hội sinh sản nhiều hơn .Nhiễm sắc thể được chọn cho quá trình sinh sản sẽ được đưa vào ghép chéo (nếu có) để tạo ra nhiểm sắc thể mới.Ở đây việ quay bánh xe roulette được thực hiện thông qua sử dụng hàm tạo số ngẫu nhiên của ngôn ngữ C : sel = (long)((float(rand()) / float(RAND_MAX))* float(totf));//quay bánh xe i = 0; while(sel > fit[i]) // so sánh với độ thích nghi { sel -= fit[i]; ++i; //tìm phần kế tiếp } 3-GHÉP CHÉO(crossover): Ghép chéo là sự trộn lẫn các thuộc tính khác nhau từ các nhiểm sắc thể khác nhau .Ở bài toán này ta thực hiện việc ghép chéo giống như phần 1 đã nói , nhiểm sắc thể có độ thích nghi cao được chọn lựa ngẫu nhiên từ bánh xe roulette sẽ được đưa vào ghép chéo ,tiếp theo là xác định vị trí ghép chéo để sinh ra nhiểm sắc thể con .Như vậy sẽ làm tăng thêm sức mạnh cho việc tìm kiếm trực tiếp thông tin dựavào thông tin đã biết .Quá trình ghép chéo liên quan tới 2 biến được khai báo như sau: bool m_Crossover ; // dùng để chọn ghép chéo. float m_CrossProb; // xác suất ghép chéo. //chọn cha mẹ thứ 1 sel = (long)((float(rand()) /float(RAND_MAX)) * float(totf)); p2 = 0; while(sel > fit[p2]) { sel -= fit[p2]; ++p2; } //sinh sản bằng ghép chéo (sinh sản hữu tính) if(cross && ((float(rand())/float(RAND_MAX))< crate)) { //chọn parent thứ 2 sel = (long)((float(rand()) /float(RAND_MAX)) * float(totf)); p2 = 0; while(sel > fit[p2]) { sel -= fit[p2]; ++p2; } //mat na bit xac dinh diem ghep cheo mask = 0xFFFFFFFFL << (int)((float(rand()) / float(RAND_MAX))* 32.0F); // new string two parents newpop[i] = (pop[p1] & mask) |(pop[p2] & (~mask)); } 4-ĐỘT BIẾN (mutation): Bước cuối cùng của quá trình sinh sản là đột biến .Với một nhiễm sắc thể ta thực hiện đột biến bằng cách thay đổi ngẩu nhiên một bit từ 0 thành 1 hoặc ngược lại.Thường đột biến xảy ra với xác suất rất thấp .Trong bài toán này quá trình đột biến được thực hiện liên quan tơí 2 biến được khai báo như sau: bool m_Mutate ; // dùng để chọn đột biến. float m_MuteProb; // xác suất đột biến. if(mutate &&((float(rand()) / float(RAND_MAX)) < mrate)) { //xac dinh vi tri dot bien mask = 1L << (int)((float(rand()) / float(RAND_MAX))* 32.0F); //lat bit tai vi tri dot bien if(newpop[i] & mask) newpop[i] &= ~mask; else newpop[i] |= mask; } } Quá trình sinh sản ,ghép chéo ,đột biến được lặp đi lặp lại để tạo ra nhiễm sắc thể mới cho đến khi vượt quá kích thước dân số ,quá trình này được đặt trong vòng lặp số thế hệ đã chọn. 5-KỸ THUẬT CẢI TIẾN: Kích thước dân số và số các thế hệ sinh ra liên quan đến tốc độ và chất lượng thông tin tìm kiếm .Dân số lớn thì quá trình xử lý sẽ dài ,dân số nhỏ thông tin tìm kiếm sẽ kém .Do đó trong việc thiết kế giải thuật ta cần cân bằng giữa kích thước dân số và số các thế hệ sinh ra.Kích thước dân số cũng tác động đến sự ảnh hưởng của nhiễm sắc thể có độ thích nghi cao trong quá trình sinh sản ,nếu kích thước dân nhỏ sẽ làm giảm ảnh hưởng của nhiễm sắc thể có độ thích nghi cao cho sự thành công của quá trình sinh sản. Để nâng cao hiệu quả GAs ,bài toán được đưa vào hai kỹ thuật: Elitist selection và Fitness scaling. Elitist selection: là chọn lọc thành phần tốt nhất,khi thực hiện Elitist selection sẽ luôn luôn copy nhiễm sắc thể có độ thích nghi cao nhất dùng để tạo ra thế