traigiau_91
New Member
Download miễn phí Đề tài Giải thuật gen và một số bài toán về giải thuật gen
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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
favg trong đó Cmult là số lượng các bản sao mong muốn cho thành viên dân số tốt nhất .Đối với các dân số nhỏ (n = 50 .. 100) , = 1.2 đến 2 được sử dụng thành công.Thủ tục co đơn giản thông 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
oulation) ;{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 ...