Đề tài Giải thuật Gen và bài toán tìm đường đi ngắn nhất

file, lưu trữ các thông số vào file : const max = 100; char tam[max]; //tao file Cfile random_file("Natural.dat", CFile::modeCreate|CFile::modeWrite);//ghi du lieu vao file wsprintf(tam,"Equation: "); random_file.Write(tam,max); switch(m_Equation) { case 0: wsprintf(tam,"f6(x,y)= x2+2y2-0.3cos(3px) 0.4cos(4py)+0.7 "); random_file.Write(tam,max); break; case 1: wsprintf(tam,"f7(x,y)= x2+2y2-0.3[cos(3px)cos(4py)]+0.3 "); random_file.Write(tam,max); break; case 2: wsprintf(tam,"f8(x,y)= x2+2y2-0.3[cos(3px)+cos(4py)]+0.3 "); random_file.Write(tam,max); break; case 3: wsprintf(tam,"f(x,y)=1/[(x+0.5)2+2(y+0.5)2-0.3cos(3px)-0.4cos(4py)]+0.8 "); random_file.Write(tam,max); } wsprintf(tam,"Pop. Size: %u",m_PopSize); random_file.Write(tam,max); wsprintf(tam,"Test Size: %u",m_TestSize); random_file.Write(tam,max); wsprintf(tam,"Rep. Freq: %u",m_ReptFreq); random_file.Write(tam,max); wsprintf(tam,"Sig. Digits: %u",m_SigDigits); random_file.Write(tam,max); wsprintf(tam,"X Min: %s",change(m_XMin,4)); random_file.Write(tam,max); wsprintf(tam,"X Max: %s",change(m_XMax,4)); random_file.Write(tam,max); wsprintf(tam,"Y Min: %s",change(m_YMin,4)); random_file.Write(tam,max); wsprintf(tam,"Y Max: %s",change(m_YMax,4)); random_file.Write(tam,max); wsprintf(tam,"Wt. Sign: %s",change(m_WtSign,4)); random_file.Write(tam,max); wsprintf(tam,"Wt. Expt: %s",change(m_WtExp,4)); random_file.Write(tam,max); wsprintf(tam,"Wt. Mant: %s",change(m_WtMant,4)); random_file.Write(tam,max); wsprintf(tam,"Crossover %%: %s",change(m_CrossRate*100.0f,4)); random_file.Write(tam,max); wsprintf(tam,"Mutation %%: %s",change(m_MuteRate*100.0f,4)); random_file.Write(tam,max); CString m_str; if(m_CrossX) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Cross X: %s",m_str); random_file.Write(tam,max); if(m_CrossY) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Cross Y: %s",m_str); random_file.Write(tam,max); if(m_CrossB) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Cross B: %s",m_str); random_file.Write(tam,max); if(m_MutateX) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Mutate X: %s",m_str); random_file.Write(tam,max); if(m_MutateY) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Mutate Y: %s",m_str); random_file.Write(tam,max); if(m_MuteLoop) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Mutate Loop: %s",m_str); random_file.Write(tam,max); if(m_Elitist) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Elitism: %s",m_str); random_file.Write(tam,max); if(m_FitScale) m_str = "TRUE"; else m_str = "FLASE"; wsprintf(tam,"Scaling: %s",m_str); random_file.Write(tam,max); wsprintf(tam,"Fit Algor: "); random_file.Write(tam,max); switch(m_FitAlgor) { case FSA_EXPON: wsprintf(tam,"Exponential"); random_file.Write(tam,max); break; case FSA_WINDOW: wsprintf(tam,"Windowing"); random_file.Write(tam,max); break; case FSA_LINEAR: wsprintf(tam,"Linear Normalization"); random_file.Write(tam,max); wsprintf(tam,"Lin Base: %s",change(m_FitLinBase,4)); random_file.Write(tam,max); wsprintf(tam,"Lin Dec: %s",change(m_FitLinDec,4)); random_file.Write(tam,max); wsprintf(tam,"Lin Min: %s",change(m_FitLinMin,4)); random_file.Write(tam,max); } const size_t POP_SZ = m_PopSize; const size_t GEN_SZ = m_TestSize; const size_t EQ_ID = m_Equation; const size_t SIG_DIG= m_SigDigits; // tao may phat ngau nhien va doi tuong dot bien RandDev devgen; Mutage fmute(m_WtSign,m_WtExp,m_WtMant); Tiếp theo ta cấp phát vùng nhớ chứa là các mãng chứa dân số cũ và mơi , độ thích nghi tương ứng củc các dân số. // cap phat vung nho double * x = new double[POP_SZ]; double * xnew = new double[POP_SZ]; double * y = new double[POP_SZ]; double * ynew = new double[POP_SZ]; double * fit = new double[POP_SZ]; Khởi tạo ngẫu nhiên dân số ban đầu có giá trị nằm trong phạm vi đã xác định: //xac dinh pham vi const double rangex = m_XMax - m_XMin; const double rangey = m_YMax - m_YMin; // tao ra gia tri ban dau for(i=0;i < POP_SZ;++i) { Tạo ngẫu nhiên dân số ban đầu } //cac bien phu khac double best,lowf,fitn,vf,vx,vy; size_t i,j,inc,g,ibest,p1,p2; Giải thuật chính nằm trong vòng lặp đếm số các thế hệ:// vong lap cac the he for(g = 0;g < GEN_SZ; ++g) { // cac xu ly trong qua trinh sinh san . . . } Bước đầu tiên của việc xử lý quátrình sinh sản là tính toán giá trị thích nghi của các dân số . Tiếp theo là vòng lặp chọn lựa các hàm thích nghi cho mỗi cặp dân số x-y. Vòng lặp cũng sẽ giữ lại độ thích nghi cao nhất và thấp nhất dùng cho việc thông tin quá trình tìm kiếm và việc điều chỉnh độ thích nghi trong trường hợp chọn Fitness scaling : //tinh gia tri thich nghi best = DBL_MIN; lowf = DBL_MAX; ibest = 0; for(i=0;i < POP_SZ; ++i) { switch(EQ_ID) { Chọn các hàm mục tiêu và chuyển sang hàm thich nghi } // lay gia tri thich nghi tot nhat if(fit[i] > best) { best = fit[i]; ibest = i; } // lay gia tri thich nghi thap nhat if(fit[i] < lowf) lowf = fit[i]; } Tiếp theo là lưu trữ các bước tìm kiếm vào file dữ liệu: // hien thi cac giai phap tot nhat if(g% m_ReptFreq ==0){wsprintf(tam,"%u :( %s , %s ) fit= %s ",g,change(x[ibest],10),change(y[ibest],10),change(best,12)); random_file.Write(tam,max); } Thực hiện linear normalization , các nhiễm sắc thể phải có thứ bậc khởi đầu giá trị thích nghi trước khi giải thuật ấn định giá trị mới từ cao nhất đến thấp nhất.Khi Linear Normalization được chọn ta dùng khung sắp xếp phạm vi x,y và mãng fit theo thứ tự yêu cầu . Tiếp theo là cân bằng độ thích nghi, trong vòng lặp ta biến đổi mỗi giá trị thích nghi tùy theo việc chọn lựa mức cân bằng trong giải thuật: for(i=0;i < POP_SZ;++i) { //can bang do thich nghi if(m_FitScale) { Chọn phép co độ thích nghi; } } Kết quả việc tạo ra dân số mới yêu cầu chọn lựa cha mẹ .Giống như sinh sản trong tự nhiên có hai dạng :sinh sản vô tính ,sao chép từ cha mẹ (trong trong trường hợp không chọn ghép chéo) và Sinh sản hữu tính cha mẹ kết hợp bằng ghép chéo tạo ra thế hệ mới (nếu chọn ghép chéo), sau đó là đột biến nếu được chọn . //Tạo bánh xe roulette sol = new Roulette(POP_SZ,fit); // neu elitist, chon dan so tot nhat if (m_Elitist) { Chọn nhiễm sắc thể tốt nhất gán cho thành phần đầu tiên của thế hệ tiếp theo; i = 1; } else i = 0; Tạo dân số mới : for( ; i < POP_SZ; ++i) { //Chọn cha mẹ của nhiễm sắc thể x thứ nhất p1=sol->GetIndex(); if(m_CrossX && (devgen() <= m_CrossRate)) { //Chọn cha mẹ của nhiễm sắc thể x thứ hai p2=sol->GetIndex(); xnew[i] = Crossover(x[p1],x[p2]);//ghep cheo x } else xnew[i] = x[p1]; //khong ghep cheo if(m_CrossB) //Chọn cha mẹ của nhiễm sắc thể y thứ nhất p1=sol->GetIndex(); if(m_CrossY &&(devgen() <= m_CrossRate)) { //Chọn cha mẹ của nhiễm sắc thể y thứ hai p2=sol->GetIndex(); ynew[i] = Crossover(y[p1],y[p2]);//ghep cheo y } else ynew[i] = y[p1];// khong ghep cheo // đột biến trên x if(m_MutateX) { Thực hiện đột biến trên x } //đột biến trên y if(m_MutateY) { Thực hiện đột biến trên y } // xoa roulette wheel delete sol; // copy dan so moi memcpy(x,xnew,POP_SZ * sizeof(double)); memcpy(y,ynew,POP_SZ * sizeof(double)); } //dong file random_file.Close(); Sau khi thực hiện ta giải phóng các vùng nhớ đã cấp phát trước đó: delete [] fit; delete [] ynew; delete [] y; delete [] xnew; delete [] x; V-KẾT QUẢ CHƯƠNG TRÌNH VÀ NHẬN XÉT : 1-CÁCH THỰC HIỆN: Chương trình được viết bằng ngôn ngữ Visual C++, trong chương trình có các lớp hỗ trợ như : Crossover : Thực hiện việc ghép chéo hai chuỗi với nhau. RandDev :Lớp tạo số thực ngẫu nhiên nằm trong khoảng từ 0.0 đến 1.0 . Roulette : Lớp tạo bánh xe roulette dùng chọn lựa trong việc sinh sản. Mutate : Lớp thực hiện việc đột biến . CSDL : chứa cấu trúc dữ liệu liên quan đến việc ghi đọc file. Lib : là thư viện chứa các thủ tục phục vụ cho việc ghi đọc file. Natural : lớp chinh thực hiện Giải thuật gen. Khi muốn sử dụng chương trình ,từ menu Example người sử dụng chọn mục NaturalDlg , sẽ hiện ra dialog để nhập các thông số vào các ô tương ứng (hoặc sử dụng các thông số được gán trị mặc nhiên) . Chương trình có 4 hàm mục tiêu để chọn , nếu không chọn chương trình tự động hàm mục tiêu cuối cùng . Khi chọn kỹ thuật co độ thich nghi (Fitness Scaling) có 3 kỹ thuật co độ thích nghi để chọn : Windowing , Exponent , Linear normalize; chương trình chọn mặc nhiên là Linear Normalize. Sau khi chọn các thông số , người sử dụng nhấn phím OK chương trình sẽ nhận các thông số và thực hiện ,kết quả được lưu trữ vào file , khi xem kết quả thì chọn menu print , rồi chọn mục Natural file. Kết quả được lưu trữ là thành phần tối ưu nhất ở mỗi thế hệ . 2-KẾT QUẢ : Chương trình thực hiện qua các lần chạy được các kết quả tốt nhất như sau: * Chọn hàm mục tiêu: f1(x,y) = x2 + 2y2 – 0.3cos(3px) – 0.4cos(4py) + 0.7 . Kết quả :x = -1.4231166e-007 , y =3,1967196e-154 , fit = 1 * Chọn hàmmục tiêu: f2(x,y) = x2 + 2y2 – 0.3cos(3px) 0.4cos(4py) + 0.3 . Kết quả :x = -5.1905104e-006 , y =-2.5460528e-077 , fit = 1 * Chọn hàm mục tiêu:f3(x,y) = x2 + 2y2 – 0.3cos(3px) + 0.4cos(4py) + 0.3 . Kết quả :x = 0 , y = 2.7234728-007 , fit = 1.3 * Chọn hàm f4(x,y) = 1/ [(x+0.5)2 + 2(y-0.5)2 – 0.3cos(3px) – 0.4cos(4py) + 0.8]. Kết quả :x = -0.65530978 , y = 0.50024127 , fit = 7.9402935. Khi chọn các hàm mục tiêu từ f1(x,y) đến f3(x,y) với kích thước dân số khoảng 50 chỉ cần số thế hệ khoảng 100 trở lại thì ta được kết quả tối ưu , tuy nhiên đối với hàm f4(x,y) để có kết quả ta thực hiên khoảng 1000 thế hệ. 3-NHẬN XÉT: Từ bài toán thực tế là xác định đỉnh núi cao nhất trong dãy núi, ta đưa về tìm giá trị cực đại của các hàm tương ứng được chọn . Với các hàm đã chọn thì việc tìm ra giá trị cực đại theo phương pháp tuyền thống rất là khó khăn .Nếu theo phương pháp tuần tự thì không khả thi , bởi vì các biến là số thực , mặt khác như đã phân tích dễ dàng rơi vào “bâỹ” đỉnh thấp hơn . Ta thử phân tích theo phương pháp giải tích : Với f4(x,y) = 1/ [(x+0.5)2 + 2(y-0.5)2 – 0.3cos(3px) – 0.4cos(4py) + 0.8]. Việc tìm giá trị cực đại của hàm , đưa về tìm giá trị cực tiểu của biểu thức sau: f(x,y) = (x+0.5)2 + 2(y-0.5)2 – 0.3cos(3px) – 0.4cos(4py) + 0.8. Theo lý thuyết, đầu tiên ta tìm các cực trị, bằng cách giải hệ các phương trình: f’x = 2x +1 + 0.9psin(3px) = 0. f’y = 2y - 1 +1,6psin(4py) = 0. Với f’x , f’y là đạo hàm riêng phần theo x ,y. Đến đây ta gặp 2 vấn đề khó khăn : Mỗi hàm ta phải xây dựng một thủ tục tính đạo hàm riêng , việc giải các phương trình trên không có phương pháp tổng quát , phải nhẫm nghiệm .Nếu thực hiện trên máy tính phải thực hiện vòng lặp điều này không thể thực hiện bằng số thực. Thử kiểm tra kết quả đạt được với phương pháp giải tích : Thế x0 = -0.65530978 , y0 = 0.50024127 vào các phương trình đạo hàm riêng phần ta được : f’x = 2 * (-0.65530978) + 1 + 0.9 * 3.14 * sin (3 * 3.14 * (-0.65530978)) = -1.31061956 + 1 + 2.826 * 0.109944468 = -0.31061956 + 0.310703067 = 0.000003507 = 0.0 . f’y = 2 * 0.50024127 +1 + 1.6 * 3.14 *sin(4 * 3.14 * 0.50024127) = 1.00048254 - 1 + 5.0234 *(- 0.000154955) = 0.00048254 – 0.000478405 = 0.000004135 = 0.0 . Vậy : x0 = -0.65530978 , y0 = 0.50024127 là điểm cực trị của hàm. f”x = 2 + 2.7pcos(3px) . f”y = 2 + 6.4pcos(4py) . f”x0 = 2 + 2.7 * 3.14 * cos (3* 3.14 * (-0.65530978)) = 10.42420611 = A f”y0 = 2 + 6.4 * 3.14 * cos (4* 3.14 * 0.50024127) = 22.09599976 = C f”xy = 0.0 = B. Ta có: B2-AC = 0.0 – 5.832951032 * 22.09599976 < 0 . mà A > 0 => f(x0,y0) = cực tiểu => f4(x0,y0) cực đại . Vậy kết quả đúng với phương pháp giải tích. Như ta thấy , một vấn đề quá khó khăn đối với các phương pháp khác , nhưng thực hiện bằng giải thuật gen thật dễ dàng , qua các thao tác đơn giản : sinh sản , ghép chéo và đột biến trong đó có phép chọn lựa ngẫu nhiên . Với tính mạnh mẽ này mà GAs áp dụng rất tốt cho việc giải các bài toán tối ưu hóa trong kỹ thuật như: Tối ưu hoá hệ thống đường ống dẫn khí thiên nhiên , tối ưu hoá kết cấu trong thiết kế và xây dựng , ghi ảnh trong y học , giải các bài toán thuộc lĩnh vực trí tuệ nhân tạo. -------*****-------- CHƯƠNG VII BÀI TOÁN NGƯỜI TÙ ( Prisoner's Dilemma Problem) * * * I/ ĐẶT VẤN ĐỀ Sở dĩ bài toán có tên " Tình thế tiến thoái lưỡng nan của người tù "vì nó là sự trừu tượng hoá của một tình thế khó quyết định.: Có hai người bị bắt giữ và nhốt ở hai nơi riêng biệt do đã cùng tham gia vào một tội ác. Viên biện lí đã gặp riêng từng người và đề nghị như sau: " Tôi đã thu thập được những chứng cứ chống lại cả hai anh. Nếu các anh cứ khăng khăng cho là mình vô tội thì bằng mọi giá tôi sẽ tìm cách kết án các anh với mức một năm. Nhưng nếu anh thú nhận tội của mình và đứng ra làm chứng tố cáo bạn anh thì anh sẽ được trả tự do còn bạn anh sẽ bị kết án nhiều năm tù. Còn nếu cả hai người cùng nhận tội thì sẽ bị kết án theo luật định hai năm." Viên biện lí cũng cho họ biết đề nghị này sẽ được đặt ra đối với cả hai, và tất nhiên họ không được biết trước quyết định của nhau. Rõ ràng trong tình huống khi cả hai chỉ bị xét xử về một tội danh thì cách chọn lựa tốt nhất đối với mỗi người là đứng ra tố cáo người kia. Vấn đề trở nên phức tạp khi một người bị đem ra xét xử riêng rẽ về hàng loạt tội danh mà anh ta đã phạm và giả sử cũng được hưởng đề nghị như trên. Câu hỏi đặt ra là liệu có thể xây dựng một chiến thuật , trong đó quyết định của người tù ở mỗi lần xét xử được chọn lựa dựa vào kết quả của các lần xét xử đã diễn ra trước đó để chung cuộc nhằm hưởng một mức án tối thiểu về hàng loạt tội danh đã phạm? Yêu cầu giải quyết bài toán người tù nêu trên cũng đã được đặt ra trong nhiều lĩnh vực như thuyết tiến hoá của sinh vật, giá cổ phiếu và trong nhiều tình huống khác, ở đó quyết định chọn lựa các hành động xảy ra kế tiếp nhau được suy diễn dựa trên diễn tiến của quá khứ. II/ XÂY DỰNG BÀI TOÁN Bài toán " Tình thế tiến thoái lưỡng nan" của người tù được mô tả qua trò chơi thi đấu như sau: Hai đấu thủ thi đấu với nhau, trận đấu gồm nhiều hiệp (nước). Tại mỗi hiệp, mỗi đấu thủ có thể chọn cho mình hành vi hợp tác hoặc bất hợp tác với đối thủ của mình, và không biết nước đi sắp tới của nhau. Phụ thuộc vào quyết định chọn lựa của hai đấu thủ, mỗi đấu thủ sẽ nhận được số điểm theo thể thức tính điểm như sau: Nếu cả hai cùng hợp tác với nhau thì sẽ nhận được số điểm bằng nhau - mức điểm thưởng trung bình (kí hiệu R, viết tắt của reward) . Khi chỉ có một đấu thủ chọn bất hợp tác, người này sẽ nhận được mức điểm thưởng cao nhất (T, viết tắt của temptation), trong khi đó đối thủ kia do chọn hợp tác sẽ bị số điểm phạt xấu nhất (kí hiệu S, viết tắt của sucker). Nếu cả hai đấu thủ cùng chọn hành vi bất hợp tác thì sẽ đều bị số điểm phạt trung bình (kí hiệu P, viết tắt của penalty). Đấu thủ 1 Đấu thủ 1 Quyết định Decision Hợp tác Cooperate Bất hợp tác Defect Hợp tác Cooperate (R=6, R=6) (S=0, T=10) Bất hợp tác Defect (T=10, S=0) (P=2, P=2) Bảng tính điểm Kết thúc trận thi đấu, đấu thủ nào có số điểm cao nhất sẽ giành thắng lợi. Mục tiêu của trò chơi nhằm tìm kiếm một chiến thuật thi đấu tối ưu khả dĩ. Chiến thuật ở đây được hiểu theo nghĩa mỗi nước đi kế tiếp được chọn trên cơ sở diễn tiến của các nước đi trước đó. III/ MÔ HÌNH CHIẾN THUẬT Chiến thuật là tập các qui tắc dùng để xác định hành vi ứng xử của đấu thủ ở mỗi nước đi. Mỗi qui tắc được xây dựng dựa trên các nước đi trước đó của đối thủ hoặc của cả hai bên. 1. CHUỖI BIT Để có thể sử dụng giải thuật Gen giải bài toán nêu trên, chiến thuật sẽ được mô phỏng dưới dạng một chuỗi bit nhị phân trong đó bit 0 ( kí hiệu là C- viết tắt của cooperate) biểu diễn hành vi hợp tác được chọn, và bit 1 (kí hiệu là D - viết tắt của defect) biểu diễn hành vi bất hợp tác. Cụ thể, xét trường hợp xây dựng qui tắc dựa vào ba nước đi trước đó của cả hai bên. Tại mỗi nước trong ba nước đi này, có 4 khả năng có thể xảy ra: - Cả hai đấu thủ đều chọn hợp tác (kí hiệu CC hay R). - Đối phương chọn bất hợp tác ( kí hiệu CD hay S). - Đấu thủ chọn bất hợp tác (kí hiệu DC hay T). - Cả hai đấu thủ cùng chọn bất hợp tác (kí hiệu DD hay P). Để mã hóa một chiến thuật cụ thể, trước hết cần qui định cách thức mã hoá một chuỗi hành vi cụ thể dưới dạng chuỗi có chiều dài là ba kí tự . Thí dụ: RRR, biểu thị chuỗi hành vi ở đó cả hai bên đều chọn hợp tác trong ba nước đi. SSP biểu thị chuỗi hành vi mà đấu thủ bị đối phương bất hợp tác hai lần và nước đi cuối cả hai đều bất hợp tác. Chuỗi ba chữ cái sau đó sẽ được sử dụng để tạo ra một con số có giá trị nằm giữa 0 và 63 bằng cách mã hoá chuỗi ở dạng một số nguyên theo cơ số 4 .Cách thức tiến hành như sau: CC = R = 0, DC = T =1, CD = S =2, DD = P =3. Như vậy một chuỗi mô tả ba hành vi bất hợp tác đồng thời liên tiếp nhau (PPP) sẽ được mã hoá thành 63. Sử dụng phương pháp mã hóa này, có thể định nghĩa một chiến thuật ( dựa trên ba nước đi trước đó) dưới dạng một chuỗi nhị phân dài 64 bit chứa C (hợp tác) và D (bất hợp tác), với ý nghĩa C hoặc D ở vị trí thứ i sẽ tương ứng với chuỗi hành vi biểu thị bởi số i. Thí dụ theo sơ đồ mã hoá thì kí hiệu D ở vị trí 0 sẽ là mã hoá của qui tắc có dạng RRR -> D, và kí hiệu C ở vị trí thứ 3 sẽ là mã hoá của qui tắc dạng RRP -> C. Vì tập các qui tắc sinh bởi chuỗi có độ dài 64 bit phụ thuộc vào ba nước đi trước đó nên hành vi khi bắt đầu trò chơi sẽ không được xác định. Để giải quyết vấn đề này cần phải thêm vào 6 bit (C và D) mô tả các giả thiết về hành vi trước khi trò chơi bắt đầu. Như vậy có thể xác định được hành vi ứng xử khi trò chơi bắt đầu cũng như khi đang diễn tiến. Kết hợp giả thiết và tập các luật sinh, mỗi chuỗi có độ dài 70 bit sẽ biễu diễn một chiến thuật cụ thể, trong đó 64 bit dùng cho tập luật sinh nước đi kế tiếp và 6 bit dùng cho giả thiết. Sau khi vấn đề mã hoá chiến thuật đã được xác định xong. Để tìm một chiến thuật tối ưu khả dĩ , cần tổ chức cuộc thi đấu với sự tham gia của nhiều đấu thủ theo thể thức vòng tròn - mỗi đấu thủ sẽ phải thi đầu lần lượt với các đôi thủ khác. Chiến thuật vượt trội (giành được số điểm cao nhất) của vòng đấu này sẽ được giữ lại để tham gia tiếp các vòng đấu sau với các chiến thuật khác. 2. MÁY HỮU HẠN TRẠNG THÁI (FINITE STATE MACHINES) Cấu trúc của máy hữu hạn trạng thái gồm: - Một tập hữu hạn các trạng thái nội tại, trong đó có một trạng thái được kí hiệu là trạng thái khởi đầu. Ở mỗi thời điểm có một trạng thái được chọn. - Một tập hữu hạn các kí hiệu input và một tập hữu hạn các kí hiệu ouput. Ở mỗi trạng thái của máy hữu hạn tồn tại một ánh xạ từ tập kí hiệu input tới tập kí hiệu output: với một kí hiệu input cho trước, máy hữu hạn sẽ hoàn trả một kí hiệu output và chuyển sang một trạng thái mới. Hình 1 minh hoạ một máy ba trạng thái có bảng kí hiệu input là {0, 1} và bảng kí hiệu output là {A, B, C}. Máy hữu hạn, thí dụ như hình 1, sẽ được chương trình hiện thực ở dạng bảng tìm kiếm hai chiều: có số hàng bằng với số trạng thái và số cột bằng kích thước của bảng input. Bảng 2 mô tả một máy hữu hạn ở dạng bảng [3][2], mỗi phần tử của bảng chứa một kí hiệu output và một trạng thái mới viết ở dạng O/S. Trạng tháiInput 0 Input 1 0 B/1 A/2 1 B/0 B/1 2 A/2 C/1 Bảng chuyển cho hình 1. Các máy hữu hạn trạng thái hoàn toàn có khả năng tính toán, i.e có thể xây dựng máy hữu hạn thực hiện một tác vụ bất kì, cũng có thể xem máy hữu hạn trạng thái như là một chương trình hay giải thuật. Cách tiến hoá của FSM cũng giống hệt như sự tiến hoá của nhiễm sắc thể trong giải thuật Gen. Một tập các FSMs được đánh giá so với môi trường - là một tập gồm những kí hiệu input. Giải thuật sẽ tính toán giá trị thích nghi cho từng máy FSM dựa trên khả năng hoạt động của nó. Các giá trị thích nghi sẽ xác định cơ hội sinh sản của cộng đồng các FSMs: con cái được tạo ra bằng cách sao chép một FSM bố mẹ và có thể đột biến nó. Các phép toán đột biến có thể bao gồm việc thay đổi một kí hiệu output, thay đổi trạng thái chuyển, qui định trạng thái khởi tạo mới, thêm một trạng thái mới, hay xoá một trạng thái hiện có. Cộng đồng mới sau đó sẽ thay thế các cha- mẹ và chu trình này lại bắt đầu lặp lại. Mô hình chiến thuật của bài toán người tù được xây dựng bằng FSM khá đơn giản. Bảng output luôn là {C, D}.Mỗi máy FSM sẽ quyết định nước đi kế tiếp - biểu diễn bởi kí hiệu output - dựa trên các nước đi trước đó của cả đấu thủ lẫn đối phương của nó, hoặc chỉ của đối phương. Số nước đi này sẽ quyết định kích thước của bảng input. Thí dụ, dựa vào nước đi ngay trước đó của cả hai bên, bảng input sẽ là {R, S, T, P}. Chỉ dựa vào nước đi trước đó của đối thủ, bảng input sẽ có dạng đơn giản hơn {C, D}, đồng thời cũng giới hạn được mức độ phức tạp của FSM. Để chọn ra chiến thuật tối ưu khả dĩ, tương tự như mô hình chuỗi bit tổ chức cuộc thi đấu theo thể thức vòng tròn với sự tham gia của nhiều FSM -mô tả các chiến thuật. Mỗi trận đấu giữa hai đấu thủ (hai FSM) cũng trải qua nhiều hiệp đấu. Cộng đồng các FSM ban đầu được tạo ngẫu nhiên. Sau mỗi vòng đấu, hơn nửa chiến thuật tỏ ra yếu kém trong cộng đồng sẽ bị thay thể bởi các FSM con cái mới thông qua các phép toán đột biến. Vấn đề chọn mô hình biểu diễn chiến thuật trong bài toán người tù đặc biệt có ý nghĩa quan trọng. Biểu diễn dưới dạng chuỗi bit phù hợp với mô hình hiện thực chương trình theo giải thuật Gene chuẩn. Mỗi chiến thuật sau khi được mã hoá dưới dạng nhiễm sắc thể - một chuỗi bit (gene) biểu diễn thông tin, sẽ được đánh giá tính tốt xấu dựa trên giá trị thích nghi (điểm đạt được trong thi đấu) và quyết định khả năng sinh sản của nó để tạo ra các nhiễm sắc thể mới (những chiến thuật mới). Cấu trúc chuỗi bit phù hợp với việc thực hiện các phép toán sinh sản thông thường được định nghĩa trong giải thuật Gene: phép ghép chéo, đột biến, mà không cần phải thực hiện thêm thao tác đặc biệt nào. Tuy nhiên giải thuật theo mô hình này chỉ tập trung vào việc xử lí dữ liệu: chuỗi bit. Biểu diễn chiến thuật dưới dạng mô hình máy hữu hạn trạng thái mang một ý nghĩa khác. Giải thuật thực sự tạo ra một chương trình (giải thuật) là các máy hữu hạn. Hoạt động của máy hữu hạn theo cơ chế IF ... THEN ... tỏ ra thích hợp đối với môi trường biến động . Với cấu trúc đơn giản của bảng input có thể xây dựng được các chiến thuật tinh vi. Không cần sử dụng phép toán ghép chéo thường được yêu cầukhi áp dụng giải thuật Gene. Thông qua máy hữu hạn có thể tìm hiểu về tính thông minh trong quá trình tiến hoá của máy, tính thông minh ở đây được hiểu theo nghĩa khả năng dự đoán và sự phản ứng đối với môi trường. Bài toán người tù sẽ sử dụng mô hình chiến thuật thi đấu dưới dạng máy hữu hạn trạng thái. IV/ HIỆN THỰC CHƯƠNG TRÌNH DƯỚI DẠNG MÁY HỮU HẠN TRẠNG THÁI 1. KHAI BÁO DỮ LIỆU Để không làm mất tính tổng quát, phần lớn các khái niệm của giải thuật Gene sử dụng trong chương trình hiện thực bài toán, thí dụ : bánh xe roulette, máy hữu hạn ... - đa số được thể hiện ở dạng template. 1.1. BÁNH XE ROULETTE Giải thuật Gene chọn các yếu tố theo xác suất, thí dụ chọn cá thể, phép toán sản sinh ... - thông qua khái niệm bánh xe roulette (bánh xe roulette dùng quay số trong môn cờ bạc). Con xúc sắc dùng để gieo được hiện thực bởi class RandDev, bánh xe tương ứng với class RouletteWheel ở dạng template. // ----------------------------- // class tạo số ngẫu nhiên // ----------------------------- class RandDev { protected: // đối số seed ngầm định được chọn bởi đồng hồ hệ thống. static long TimeSeed() { return (long)time(NULL); } public: // constructor RandDev (long initSeed = TimeSeed()); // xác lập giá trị seed void SetSeed(long initSeed=TimeSeed()); // toán tử tạo giá trị ngẫu nhiên nằm giữa 0.0 và 1.0 float operator()(); private: long Seed; // Giá trị khởi tạo ban đầu của dãy số ngẫu nhiên }; Mỗi đối tượng thuộc lớp RandDev sẽ tương ứng với một chương trình tạo số ngẫu nhiên nằm giữa 0.0 và 1.0 (thực hiện thông qua toán tử ( )) . Thí dụ: RandDev G; Để tạo số ngẫu nhiên chỉ việc gọi toán tử (): G(); // ----------------------------------------------------------- // class hiện thực bánh xe roulette ở dạng template // ------------------------------------------------------------ template class RouletteWheel { public: // constructor RouletteWheel(size_t sz, FType *weights=NULL); // copy constructor RouletteWheel(const RouletteWheel &rw); // toán tử gán void operator =(const RouletteWheel &rw); // destructor ~RouletteWheel(); // thay đổi trọng số của bánh xe roulette FType Change(size_t i, FType weight); // các hàm truy xuất thành phần size_t GetSize() {return N;} float GetWeight(size_t i); // nhận một chỉ số mang tính ngẫu nhiên size_t GetIndex(); protected: // mảng các trọng số (tương ứng với số phần chia và kích thước // mỗi phần trên bề mặt bánh xe roulette size_t N; FType * W; // tổng các trọng số của bánh xe roulette FType T; // "xúc sắc" RandDev G; private: // các hàm sử dụng bên trong các hàm thành phần public float AbsVal(FType f) { if (f<0.0F) return -f; else return f; } void Copy(const RouletteWheel &rw); }; Mỗi đối tượng RouletteWheel đều có một biến thành phần thuộc class RandDev dùng để chọn một phân vùng trên bánh xe roulette. Khai báo đối tượng của class này bởi constructor thường kèm theo các đối số xác định mảng tương ứng: Thí dụ, tạo bánh xe roulette chọn một trong năm phép toán sinh sản: Double operarr[5]; RouletteWheel operwhl(5, operarr); 1.2. MÁY HỮU HẠN - MÁY HỮU HẠN TỔNG QUÁT Khai báo trong class FiniteStateMachine ở dạng template. Thành phần data của máy chủ yếu gồm: số trạng thái, trạng thái khởi đầu, trạng thái hiện thời, bảng input, bảng chuyển. // ---------------------------------------------------------------------------- // Khai báo phần tử dữ liệu trong bảng chuyển đổi của máy hữu hạn // ---------------------------------------------------------------------------- template struct FSM_TranData { size_t NextState; Tout Osym; // default constructor FSM_TranData(): NextState(0), Osym() {} // constructor FSM_TranData(size_t ns, Tout os) { NextState=ns; Osym=os; } }; // ----------------------------------------- // Máy hữu hạn trạng thái tổng quát // ------------------------------------------ template < class Tin, // kiểu input size_t Nin, // kích thước bảng input class Tout // kiểu output > class FiniteStateMachine { public: // constructor FiniteStateMachine ( size_t nState, // số trạng thái của máy FSM_TranData *table, // bảng chuyển Tin iset[Nin], // bảng input size_t start // trạng thái khởi đầu ); // destructor ~FiniteStateMachine(); // copy constructor FiniteStateMachine ( const FiniteStateMachine &fsm ); // toán tử gán void operator = ( const FiniteStateMachine &fsm ); // truy xuất thành phần dữ liệu của class size_t GetNumStates() {return N;} // số trạng thái size_t GetCurState() {return State;} // trạng thái hiện thời // hoàn trả kí hiệu output và thực hiện chuyển trạng thái khi nhận kí hiệu input. Tout Transition ( Tin in ); // Xác lập máy ở trạng thái khởi đầu void Reset(); protected: FSM_TranData (*TranTable)[Nin]; // bảng chuyển Tin InSymSet[Nin]; // bảng input size_t N; // số trạng thái size_t State; // trạng thái hiện thời size_t InitState; // trạng thái khởi đầu }; - MÁY HỮU HẠN SỬ DỤNG TRONG CHƯƠNG TRÌNH Máy hữu hạn trong chương trình cần có thêm một số đặc điểm của bài toán người tù, chủ yếu là việc thực hiện phép toán đột biến. Máy này được khai báo trong class EvolvingFSM, và được dẫn từ máy hữu hạn tổng quát xác định ở trên: //------------------------------------------------ // Máy hữu hạn cụ thể trong chương trình // ------------------------------------------------ // Bánh xe Roulette dùng để chọn phép toán đột biến typedef float EVFSM_MuteWts[5]; // các phép toán đột biến enum EVFSM_MuteType { EVFSM_OutSymbol=0, // thay đổi kí hiệu input EVFSM_Transition, // thay đổi trạng thái chuyển EVFSM_AddState, // thêm trạng thái mới EVFSM_DelState, // bỏ bớt trạng thái hiện có EVFSM_InitState, // thay đổi trạng thái khởi đầu EVFSM_None // không thực hiện phép toán đột biến }; template < class Tin, // kiểu và kích thước của bảng input size_t Nin, class Tout, // và output size_t Nout > class EvolvingFSM : public FiniteStateMachine { public: // constructor EvolvingFSM ( size_t nState, // số trạng thái của máy FSM_TranData *table, // bảng chuyển Tin iset[Nin], // bảng kí hiệu input Tout oset[Nout], // bảng kí hiệu output size_t start, // trạng thái khởi đầu EVFSM_MuteWts wts // bánh xe roulette chọn phép // toán đột biến ); // copy constructor EvolvingFSM ( const EvolvingFSM &fsm ); // toán tử gán void operator = ( const EvolvingFSM &fsm ); // phép toán đột biến EVFSM_MuteType Mutate ( size_t minstate, // số trạng thái nhỏ nhất size_t maxstate // và lớn nhất cho phép ); protected: Tout OutSymSet[Nout]; // bảng kí hiệu output RouletteWheel MuteChooser; // bánh xe Roulette RandDev DevGen; // bộ tạo số ngẫu nhiên // các hàm chọn ngẫu nhiên ... size_t PickIsym(); // kí hiệu input size_t PickOsym(); // kí hiệu output size_t PickState(); // trạng thái }; Hàm thành phần Mutate được gọi mỗikhi cần sinh ra một máy hữu hạn mới từ một máy tồn tại. Nó sẽ sử dụng biến thành phần MuteChooser để chọn phép toán sinh sản đột biến. 4.2. HIỆN THỰC CHƯƠNG TRÌNH Các thông số của chương trình được nhập vào hộp thoạigồm có: Population: Kích thước cộng đồng trong một thế hệhay số chiến thuật thẩm định qua mỗi vòng thi đấu. Generations: Số thế hệ kiểm tra ( số vòng thi đấu). Report Freq: Tần suất thông báo kết quả: Bao nhiêu thế hệ thì thông báo về chiến thuật (máy hữu hạn) đang chiếm ưu thế? Contest Length: Số nước (hiệp) trong một trận đấu . MaxState: Cộng đồng ban đầu gồm các máy hữu hạn có 3 trạng thái; thông số MaxState xácđịnh số trạng thái lớn nhất cho phép trong phép toán đột biến - thêm trạng thái. MinState: Số trạng thái cho phép nhỏ nhất trong phép toán đột biến - bớt trạng thái. First Move: Ba nút này cho phép chọn nước đi đầu tiên cho mọi máy trong cộng đồng: luôn luôn hợp tác (C), luôn luôn bất hợp tác (D) hoặc chọn ngẫu nhiên. Mutation Weights: Gồm 5 giá trị dùng để xác định xác suất xảy ra đối với mỗi phép toán đột biến. Mutation Rate: Xác suất cho phép thực hiện đột biến. Linear Normalization Parameters: Chương trình sử dụng phép chuẩn hoá tuyến tính để điều chỉnh lại các giá trị fitness của các FSM trong cộng đồng khi sự chênh lệch giữa chúng không lớn. SƠ ĐỒ GIẢI THUẬT GENE : Trước hết hiện thực chiến thuật thi đấu dưới dạng máy hữu hạn, giá trị fitness gán cho mỗi FSM chính là số điểm đạt được sau một vòng thi đấu với các FSM khác. Các bước thực hiện giải thuật như sau: Dưới đây là phần hiện thực ở dạng tóm lược nhằm mục đích giải thích thân chương trình chính: // khai báo dữ liệu const size_t SSZ=2; // kích thước bảng input, output const size_t NSZ=3; // số trạng thái ban đầu char SSET[2]={'C', 'D'}; // bảng kí hiệu const size_t POP_SZ=PopSize; // số chiến thuật khảo sát trong một thế // hệ // các biến dùng trong chương trình size_t n, i, j, k, inc; double vf; char mj, mk, tj; EvolvingFSM *vm; RouletteWheel *rw; RandDev devgen; FSM_TranData td[NSZ][SSZ]; EVFSM_MuteWts wts= { WeightO, WeightT, WeightA, WeightD, WeightN }; // phân bố vùng lưu trữ cho cộng đồng EvolvingFSM **pop= new EvolvingFSM* [POP_SZ]; EvolvingFSM **newpop= new EvolvingFSM *[POP_SZ]; double *fit=new double[POP_SZ]; // các con trỏ dùng cho việc sắp xếp EvolvingFSM **ptrm=pop-1; double *ptrf=fit-1; // tạo cộng đồng ban đầu for (j=0; j<POP_SZ; ++j) { for (n=0; n<NSZ; ++n) { for (i=0; i<SSZ; ++i) { td[n][i].NextState=size_t(devgen()*float(NSZ)); if (devgen()<0.5F) td[n][i].Osym=SSET[0]; else td[n][i].Osym=SSET[1]; } } pop[j]=new EvolvingFSM (NSZ, &td[0][0], SSET, SSET, 0,wts); } size_t g=0; // bắt đầu vòng lặp chính while (1) { // khởi tạo trận đấu double totf=0; double avgf=0; // xác lập trạng thái ban đầu của các FSM và xoá mảng fitness for (j=0; j<POP_SZ; ++j) { pop[j]->Reset(); fit[j]=0.0; } // đánh giá fitness qua thi đấu for (j=0; j<POP_SZ; ++j) { for (k=j; k<POP_SZ; ++k) { // khởi tạo trạng thái ban đầu pop[j]->Reset(); pop[k]->Reset(); // chọn nước đi đầu tiên FirstMove=(EVMove)intFirstMove; switch (FirstMove) { case EVM_DEFECT: mj='D'; mk='D'; break; case EVM_COOPER: mj='C'; mk='C'; break; case EVM_RANDOM: if (devgen() < 0.5F) mj='C'; else mj='D'; if (devgen() < 0.5F) mk='C'; else mk='D'; } //end switch n=1; // tính toán fitness theo các nước đi while (1) { if (mj==SSET[0]) { if (mk==SSET[0]) { fit[j]+=PayoffCC; fit[k]+=PayoffCC; } else { fit[j]+=PayoffCD; fit[k]+=PayoffDC; } } else { if (mk==SSET[0]) { fit[j]+=PayoffDC; fit[k]+=PayoffCD; } else { fit[j]+=PayoffDD; fit[k]+=PayoffDD; } } // thoát nếu xong if (n==TestLen) break; // chuyển trạng thái dựa trên nước đi trước đối thủ tj=pop[j]->Transition(mk); mk=pop[k]->Transition(mj); mj=tj; // nước đi kế tiếp ++n; } // end while } //end for } //end for // sắp xếp để lựa chiến thuật vượt trội của vòng thi đấu for (inc=1; inc <=POP_SZ/9; inc =3*inc+1); for ( ; inc>0; inc/=3) { for (i=inc+1; i<=POP_SZ; i +=inc) { vf=ptrf[i]; vm=ptrm[i]; j=i; while ((j>inc) && (ptrf[j-inc]<vf)) { ptrf[j]=ptrf[j-inc]; ptrm[j]=ptrm[j-inc]; j -=inc; } ptrf[j]=vf; ptrm[j]=vm; } } // chấm dứt khi hết số vòng thi đấu if (g==TestSize) break; // chuẩn hoá tuyến tính để điều chỉnh các giá trị của mảng // fitness if (FitScale) { fit[0]=FitLinBase; i=1; while (fit[i-1] > FitLinDec) { fit[i]=fit[i-1]-FitLinDec; ++i; } for ( ; i<POP_SZ; ++i) fit[i]=FitLinMin; } // chọn chiến thuật vượt trội ở vòng này để khảo sát tiếp ở vòng // sau newpop[0]= new EvolvingFSM (*(pop[0])); // sản sinh các chiến thuật mới rw= new RouletteWheel(POP_SZ, fit); for (j=1; j<POP_SZ; ++j) { i=rw->GetIndex(); newpop[j]= new EvolvingFSM (*(pop[i])); if (devgen()<(MuteRate / 100)) newpop[j]->Mutate(1, MaxState); // thay minstate=1 } delete rw; // copy để tạo thế hệ tiếp theo và lặp lại for (j=0; j<POP_SZ; ++j) { delete pop[j]; } for (j=0; j<POP_SZ; ++j) pop[j]= new EvolvingFSM (*(newpop[j])); for (j=0; j<POP_SZ; ++j) { delete newpop[j]; } ++g; } // end while // giải phóng các vùng lưu trữ for (j=0; j<POP_SZ; ++j) delete pop[j]; delete [] pop; delete [] newpop; delete [] fit;  V- NHẬN XÉT: Qua nhiều lần chạy thử chương trình , có thể rút ra một số nhận xét sau: Một chiến thuật muốn được nổi trội trong thi đấu phải mang những đặc điểm: có tính hợp tác (C-C :3 điểm), biết khai thác hành vi của đối thủ (D-C : 5 điểm). Diễn tiến các vòng đấu cho thấy sự xuất hiện nhiều mẫu nước đi mang tính lặp lại trong các chiến thuật. Một trong những mẫu phổ biến là sự luân phiên giưã hai đấu thủ để có các nước đi trái ngược nhau tạo ra số điểm trung bình cho mỗi nước đi là 2.5. Điều này cho thấy ưu thế trong sinh sản của các chiến thuật thành công. Các chiến thuật luôn đi D hoặc C không bao giờ chiếm ưu thế lâu dài, vì dễ bị đối thủ khai thác. Hơn nữa các chiến thuật luôn đi D sẽ ghi điểm nghèo nàn khi phải thi đấu với nhau. Một số chiến thuật được đánh giá cao như "Tit-for-Tat"- bắt trước nước đi của đối thủ, chiến thuật Pavlov-giữ nguyên nước đi khi ghi điểm cao và thay đổi nước đi khi bị điểm thấp cũng được tìm thấy qua kết quả ghi nhận . Ưu điểm của giải thuật Gene trong tìm kiếm có chọn lọc được khẳng định nếu nhận xét với bộ thông số nhập vào, sẽ tương ứng với hơn nửa tỉ các chiến thuật phải khảo sát. Ở đây chỉ dưới mức 100.000 chiến thuật ta đã có được những kết quả khả quan. --------******----------- CHƯƠNG VIII BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT (The Traveling Salesman Problem - TSP) *** I/ GIỚI THIỆU BÀI TOÁN Đây là một bài toán cổ điển: Một thương gia phải đi qua nhiều thành phố. Hãy vạch lộ trình đi qua tất cả các thành phố đó sao cho quãng đường đi là ngắn nhất. Biết rằng mỗi thành phố chỉ đi qua một lần. Bài toán TSP khó giải quyết, vì để tìm được lời giải ta phải tiến hành tìm kiếm trên tất cả lộ trình có thể, và như vậy dẫn tới phí tổn thời gian tính toán rất lớn. Backtracking và các kỹ thuật khác có thể rút ngắn phạm vi tìm kiếm trong một số điều kiện nhưng vẫn chỉ là sự hoàn thiện của giải pháp tìm kiếm toàn diện. Khoa học máy tính vẫn chưa tìm ra được một giải thuật cụ thể có hiệu quả để giải những bài toán tương tự như TSP có kích thước lớn. Giải thuật Gene tỏ ra hiệu quả trong việc giải các bài toán có thông tin không đầy đủ. Vì vậy giải thuật này sẽ được sử dụng để hiện thực chương trình. II/ CÁC KỸ THUẬT GHÉP CHÉO MỚI Giải thuật Gene mô phỏng sự tiến hoá của thế giới tự nhiên, ở đó thông tin về một cấu trúc sống được mã hoá dưới dạng nhiễm sắc thể. Do đó để áp dụng giải thuật Gene vào bài toán TSP, ta cũng phải tìm cách mã hoá các lời giải của bài toán dưới dạng các chuỗi nhiễm sắc thể và xây dựng qui tắc đánh giá độ thích nghi của nó theo ngữ cảnh của bài toán. Kí hiệu các thành phố là A, B, C, ... mỗi nhiễm sắc thể - sự mã hoá của lời giải - sẽ là một danh sách hoán vị của A, B, C ... biểu diễn lộ trình mà người thương gia đã đi qua. Thí dụ GFHBACDE sẽ là kí hiệu của hành trình từ G -> F -> H -> ... -> E. Mỗi thành phố (gene) sẽ chỉ xuất hiện trong danh sách này chỉ một lần. Vấn đề này dẫn tới khó khăn không thể áp dụng các kĩ thuật sinh sản, đột biến thường được sử dụng trong giải thuật Gene chuẩn. Thí dụ: Với ý nghĩa ghép chéo thông thường ta nhận được từ cặp bố mẹ 1, 2 các con cái sau: - Ghép chéo tại một điểm: Bố mẹ Con cái ---------------------------------------------------- #1 ABC|DEFGH ABC|BACDE #2 GFH|BACDE GFH|BACDE - Ghép chéo tại hai điểm: Bố mẹ Con cái ---------------------------------------------------- #1 AB|CDE|FGH AB|HBA|FGH #2 GF|HBA|CDE GF|CDE|CDE Điều kiện chỉ xuất hiện một lần trong danh sách hoán vị ở hai thí dụ trên đã bị vi phạm. Do đó đòi hỏi phải xây dựng các kĩ thuật ghép chéo mới phù hợp với ý nghĩa của bài toán. 1. GHÉP CHÉO RIÊNG PHẦN (Partially matched crossover - PMX) PMX được cải tiến từ phương pháp ghép chéo hai điểm thông thường. Bắt đầu bằng việc chọn ra hai điểm, thí dụ 2 và 5: Cha mẹ 1: AB|CDE|FGH Cha mẹ 2: GF|HBA|CDE Giải thuật PMX nhận thấy gene H có trong nhiễm sắc thể 2 sẽ được thay thế bởi gene C trong nhiễm sắc thể 1, vì vậy nó sẽ chuyển đổi H của nhiễm sắc thể 1 thành C và C trong nhiễm sắc thể 2 sang H. Quá trình được thực hiện tương tự với hai gene còn lại và cuối cùng nhận được các con cái: Con cái 1: ED|HBA|FGC Con cái 2: GF|CDE|HBA Mỗi con cái là một hoán vị mới, hoán chuyển một số gene trong khi vẫn giữ nguyên các đoạn cấu trúc của bố mẹ. 2. GHÉP CHÉO CÓ THỨ TỰ (Order crossover - OX) OX dời chỗ một số gen và dịch chuyển các gene khác. Lấy ví dụ ở trên, với kí hiệu "-" biểu thị gene bỏ trống ở vị trí đó: Cha mẹ 1: AB|CDE|FGH Cha mẹ 2: GF|HBA|CDE Con cái 1: --|HBA|FG- Con cái 2: GF|CDE|--- tiếp theo, ở sau điểm ghép chéo thứ hai, OX sẽ dịch các gene sang trái (có thể coi các đầu mút của nhiễm sắc thể nối với nhau nếu cần thiết), điền các vị trí trống của gene và để trống đoạn hoán đổi: Con cái 1: BA|---|FGH Con cái 2: DE|---|GFC Cuối cùng OX sẽ hoán đổi đoạn ghép chéo nằm giữa hai điểm, tạo ra các con cái mới: Con cái 1: BA|CDE|FGH Con cái 2: DE|HBA|GFC Trong khi PMX giữ nguyên vị trí của gene trong chuỗi nhiễm sắc thể, thì OX lại duy trì thứ tự các gene trong chuỗi. 3. GHÉP CHÉO CÓ CHU KÌ (Cycle crossover - CX) Nguyên tắc làm việc của CX hoàn toàn khác, nó thực hiện việc hoán đổi một tập hợp cụ thể các gen. Thí dụ: Cha mẹ 1: ABCDEFGH Cha mẹ 2: GFHBACDE Để tạo con cái, CX bắt đầu với các thành phố đầu tiên trong các nhiễm sắc thể bố mẹ: Con cái 1: G------- Con cái 2: A------- Tìm trong cha mẹ 1, CX thấy G ở vị trí 7 và thực hiện hoán đổi ở vị trí đó: Con cái 1: G-----D- Con cái 2: A-----G- Quá trình tìm và hoán đổi tiếp tục cho đến khi gene bị thay thế đầu tiên trong cha mẹ 1, A, được bắt gặp. Cuối cùng con cái nhận được như sau: Con cái 1: GECBAFDH Con cái 2: ABHDECGE 4- PHÉP ĐẢO VỊ TRÍ (Inversion operator) Để tăng tính đa dạng có thể đưa thêm vào bài toán phép hoán vị, thực hiện việc đảo ngược vị trí các gene trong chuỗi nhiễm sắc thể. Thí dụ: ABC|DEFGH đảo thành ABCHGFED G|FHB|ACDE đảo thành GBHFACDE 5- PHÉP ĐỘT BIẾN Được định nghĩa lại dưới dạng hoán vị vị trí của hai gene. Thí dụ: Hoán vị các gene A và E trong chuỗi ABCDEFGH sẽ cho con cái là EBDEAGFH. III/ SƠ ĐỒ GIẢI THUẬT GEN CỦA BÀI TOÁN TSP Sau khi xây dựng phép mã hoá dưới dạng nhiễm sắc thể và định nghĩa các phép toán sinh sản, có thể đưa ra sơ đồ giải thuật Gene để hiện thực chương trình: PHÉP HOÁN VỊ JOSEPHUS Theo sơ đồ, cộng đồng ban đầu được hình thành bằng phép hoán vị Josephus. Giả sử có một danh sách các thành phố được kí hiệu từ A tới H, có thể tạo một hoán vị bằng việc chọn điểm xuất phát và một số đếm - thí dụ F và 5. Giả thiết xem danh sách có dạng vòng tròn bằng cách nối liền hai đầu mút, đếm 5 thành phố ở bên phải F ta được C - thành phố đầu tiên trong danh sách hoán vị. Tiếp tục từ C đếm 5 thành phố khác sẽ được thành phố thứ hai trong danh sách hoán vị - H. Lập lại quá trình này cuối cùng ta nhận được danh sách hoán vị CHFEGBDA. Như vậy bằng cách chọn ngẫu nhiên điểm bắt đầu và số đếm, chương trình có thể tạo ra một tập gồmcác danh sách hoán vị khác. IV/ HIỆN THỰC CHƯƠNG TRÌNH Số thành phố được chọn trước là 10 , kí hiệu A, B, C, .... mà không tạo phần input. Population: Số thành viên (lộ trình tìm kiếm) cần kiểm tra. Việc giữ lại thành viên tốt nhất của thế hệ cha mẹ trong thế hệ con cái, và sự tham gia của 2 cá thể cha mẹ trong các phép toán sinh sản đòi hỏi Population phải là số lẻ. Generations: Số thế hệ cần kiểm tra. Report Frequency: Bao nhieu thế hệ thì thông báo kết quả một lần? Show Best: Số nhiễm sắc thể được xuất cho từng lần thông báo. Oper Probability: Xác xuất các phép toán sinh sản được sử dụng khi tạo con cái. Mutation, Inversion, PM Crossover, Order Crossover: Nếu đánh dấu checkbox thì các phép toán sinh sản tương ứng sẽ được chọn theo xác xuất tương ứng. Linear Normalization Các thông số này dùng để điều chỉnh lại các fitness của các thành viên trong cộng đồng vì chúng có thể chênh lệch không nhiều. Sơ đồ giải thuật Gene của bài toán TSP ở trên có thể hiện thực bằng đoạn chương trình chính sau đây: typedef size_t CityChrom[10]; static const size_t CSZ = 10 * sizeof(size_t); const size_t POP_SZ = PopSize; static const char *cityName[10] = { "A ", "E ", "G ", "I ", "C ", "F ", "D ", "H ", "B ", "E " }; static const double distance[10][10] = { {0.0, 220.0, 90.0, 155.0, 133.0, 123.0, 182.0, 89.0, 105.0, 141.0}, {220.0, 0.0, 135.0, 55.0, 173.0, 117.0, 124.0, 122.0, 222.0, 85.0}, {90.0, 135.0, 0.0, 92.0, 69.0, 34.0, 95.0, 56.0, 98.0, 57.0}, {155.0, 55.0, 92.0, 0.0, 145.0, 84.0, 116.0, 68.0, 184.0, 54.0}, {133.0, 173.0, 69.0, 145.0, 0.0, 60.0, 72.0, 125.0, 70.0, 91.0}, {123.0, 117.0, 34.0, 84.0, 60.0, 0.0, 61.0, 76.0, 106.0, 33.0}, {182.0, 124.0, 95.0, 116.0, 72.0, 61.0, 0.0, 134.0, 137.0, 66.0}, {89.0, 122.0, 56.0, 68.0, 125.0, 76.0, 134.0, 0.0, 142.0, 73.0}, {105.0, 222.0, 98.0, 184.0, 70.0, 106.0, 137.0, 142.0, 0.0, 139.0}, {141.0, 85.0, 57.0, 54.0, 91.0, 33.0, 66.0, 73.0, 139.0, 0.0} }; if (distance==NULL) MessageBox("Khong du bo nho"); //tạo các vùng lưu trữ cộng đồng và mảng fitness CityChrom *pop = new CityChrom[POP_SZ]; CityChrom *newpop = new CityChrom[POP_SZ]; double *fit = new double[POP_SZ]; // các pointers dùng cho việc sắp xếp mảng fitness CityChrom *ptrp = pop - 1; double * ptrf = fit -1; // khai báo các biến size_t g, i, j, k, l, n, s, t, p1, p2, inc; double vf; CityChrom vp; RouletteWheel *rw; RandDev devgen; // bánh xe roulette dùng chọn phép toán sinh sản double operwt[5]; if (Mutation) operwt[0] = WeightM; else operwt[0] = 0.0; if (Inversion) operwt[1] = WeightI; else operwt[1] = 0.0; if (PMX) operwt[2] = WeightP; else operwt[2] = 0.0; if (CX) operwt[3] = WeightC; else operwt[3] = 0.0; if (OX) operwt[4] = WeightO; else operwt[4] = 0.0; RouletteWheel ow(5,operwt); // khởi tạo cộng đồng ban đầu bằng phép hoán vị Josephus for (i = 0; i < POP_SZ; ++i) { int plist[10]; memset(plist,0,CSZ); s = size_t(devgen() * 8.0) + 1; j = size_t(devgen() * 10.0); k = 0; while (1) { pop[i][k] = j; plist[j] = 1; if (k == 9) break; for (l = 0; l < s; ++l) { do { ++j; if (j>9) j = 0; } while (plist[j] == 1); } ++k; } } // bắt đầu vòng lặp chính của chương trình g=0; while (1) { // tính fitness for (i =0; i < POP_SZ; ++i) { fit[i] = 0.0; for (j = 1; j < 10; ++j) fit[i] += distance[pop[i][j-1]][pop[i][j]]; } // sắp mảng để chuẩn bị cho phép chuẩn hoá tuyến tính for (inc = 1; inc <= POP_SZ / 9; inc = 3 * inc + 1); for ( ; inc > 0; inc /= 3) { for (i = inc + 1; i <= POP_SZ; i += inc) { vf = ptrf[i]; memcpy(vp, ptrp[i], CSZ); j = i; while ((j > inc) && (ptrf[j - inc] > vf)) { ptrf[j] = ptrf[j - inc]; memcpy(ptrp[j], ptrp[j - inc], CSZ); j -= inc; } ptrf[j] = vf; memcpy(ptrp[j],vp,CSZ); } } // ngừng chương trình nếu điều kiện dừng thoả if (g == TestSize) break; // áp dụng fitness scaling fit[0] = FitLinBase; i =1; while (1) { if (fit[i -1] <= FitLinDec) break; fit[i] = fit[i - 1] - FitLinDec; ++i; } for ( ; i < POP_SZ; ++i) fit[i] = FitLinMin; // chọn phần tử tốt nhất memcpy(newpop[0], pop[0], CSZ); // tạo thế hệ mới rw = new RouletteWheel(POP_SZ,fit); for (i = 1; i < POP_SZ; i += 2) { // chọn cha mẹ để sinh sản p1 = rw->GetIndex(); do { p2 = rw->GetIndex(); } while (p2 == p1); memcpy(newpop[i], pop[p1], CSZ); memcpy(newpop[i+1],pop[p2], CSZ); // bỏ qua phần còn lại của vòng lặp nếu không có phép toán // được chọn if (devgen() > OperChance /100.0F) continue; // chọn phép toán switch (ow.GetIndex()) { case 0: // mutation for (n = 0; n < 2; ++n) { // chọn chỉ số j = size_t(devgen() * 10.0F); do { k = size_t(devgen() * 10.0F); } while (k== j); // hoán đổi chỉ số tham chiếu thành phố t = newpop[i+n][k]; newpop[i+n][k] = newpop[i+n][j]; newpop[i+n][j] = t; } break; case 1: // inversion for (n = 0; n < 2; ++n) { //chọn chỉ số j = size_t(devgen() * 9.0F); do { k = size_t(devgen() * 10.0F); } while (k <= j); // tính toán chiều dài s = (k- j +1) / 2; //đảo for (l = 0; l < s; ++l) { t = newpop[i+n][k]; newpop[i+n][k] = newpop[i+n][j]; newpop[i+n][j] = t; ++j; --k; } } break; case 2: // partially crossover j = size_t(devgen() * 9.0F); do { k = size_t(devgen() * 10.0F); } while (k <= j); // hoán chuyển thành phố for (n=j; n<=k; ++n) { if (pop[p1][n] != pop[p2][n]) { s = TAFindCity(newpop[i+1], pop[p1][n]); t=newpop[i+1][n]; newpop[i+1][n]=newpop[i+1][s]; newpop[i+1][s]=t; s=TAFindCity(newpop[i],pop[p2][n]); t=newpop[i][n]; newpop[i][n]=newpop[i][s]; newpop[i][s]=t; } } break; case 3: // cycle crossover j=size_t(devgen() * 10.0F); t=pop[p1][j]; while (1) { newpop[i][j]=pop[p2][j]; newpop[i+1][j]=pop[p1][j]; if (newpop[i][j] == t) break; j = TAFindCity(pop[p1], newpop[i][j]); } break; case 4:// order crossover j=size_t(devgen() * 9.0F); do { k=size_t(devgen() * 10.0F); } while (k <= j); if ((j == 0) && (k == 9)) { memcpy(vp,newpop[i], CSZ); memcpy(newpop[i], newpop[i+1], CSZ); memcpy(newpop[i+1],vp,CSZ); break; } if (k ==9) n=0; else n=k+1; // dịch chuyển và điền vị trí gen bỏ trống do { while (1) { s =TAFindCity(pop[p2], newpop[i][n]); if ((sk)) break; // shift members if (n==9) l=0; else l=n+1; while (1) { if (l==0) newpop[i][9]=newpop[i][0]; else newpop[i][l1]=newpop[i][l]; if (l==k) break; if (l==9) l=0; else ++l; } } while (1) { s=TAFindCity(pop[p1], newpop[i+1][n]); if ((sk)) break; // dịch các thành phần if (n==9) l=0; else l=n+1; while (1) { if (l==0) newpop[i+1][9]=newpop[i+1][0]; else newpop[i+1][l-1]=newpop[i+1][l]; if (l==k) break; if (l==9) l=0; else ++l; } } if (n==9) n=0; else ++n; } while (n!=j); for (n=j; n<=k; ++n) { newpop[i][n]=pop[p2][n]; newpop[i+1][n]=pop[p1][n]; } break; //end switch } //end for } //delete, copy và loop delete rw; memcpy(pop, newpop, 10 * CSZ); ++g; //end while } m_report=buf; UpdateData(FALSE); //delete delete [] fit; delete [] newpop; delete [] pop; //Ket thuc OK MessageBox("The End True!"); UpdateData(FALSE); Dưới đây là kết quả của một lần thực hiện chương trình với giá trị thông số nhập trong hộp thoại. Giá trị 559 cũng chính là lới giải của bài toán. V/ NHẬN XÉT: Để tìm ra lời giải đúng của bài toán trong trường hợp số thành phố là 10, ta phải xét (10)!= 3628800 tổ hợp. Giải thuật Gen trong trường hợp này cho thấy có thể tìm ra lời giải trong số tổ hợp ít hơn nhiều (thế hệ 90). Chương trình này khi chạy thử nghiệm 10 lần đã có 4 lần cho lời giải đúng, các lần còn lại chỉ cho lời giải mang tính tối ưu gần đúng. Để lời giải tiệm cận tới giá trị tối ưu (tránh đường cong tối ưu nằm ngang khi chưa thỏa), vai trò của phép toán đột biến rất quan trọng.