Mapcon
05-11-2002, 07:55 PM
Giải thuật Di truyền ( Genetic ) có ứng dụng nhiều trong việc giải quyết các bài toán tối ưu hoá trong Tin học . Sau đây là một chút giới thiệu sơ lược về thuật giải Di truyền :
Công thức tổng quát:
Cấu trúc dữ liệu + Thuật giải di truyền = Chương trình tiến hoá
Chương trình tiến hoá:
Thuật ngữ Chương trình tiến hoá trong công thức trên la khái niệm dùng để chỉ các chương trình máy tính có sử dụng các thuật toán tìm kiếm và tối ưu hoá dựa trên nguyên lý tiến hoá tự nhiên. Ta gọi chung các thuật toán như thế là thuật toán tiến hoá.
Thuật giải di truyền, cũng như các thuật toán tiến hoá nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hoá tự nhiên là hoàn hảo nhất, hợp lý nhất, và tự nó đã mang tính tối ưu. Quan niệm này có thể được xem như là một tiên đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách quan. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn, phát triển hơn, hoàn thiện hơn thế hệ trước. Tiến hoá tự nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hoá tự nhiên, các thế hệ mới luôn được sinh ra để bổ xung thay thế thế hệ cũ. Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại, cá thể nào không thích ứng với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực thúc đẩy quá trình tiến hoá. Ngược lại, tiến hoá cũng tác động trở lại góp phần làm thay đổi môi trường.
Cấu trúc dữ liệu:
Các chương trình tiến hoá được dùng để giải các bài toán tìm nghiệm. Nghiệm của bài toán được biểu thị bằng các nhiễm sắc thể (NST), mỗi NST bao gồm nhiều gen. Mỗi NST có một giá trị gọi là độ thích nghi cho biết nó tốt hơn hay kém hơn các NST khác. Trong một bài toán, độ thích nghi càng cao thì NST càng được đánh giá tốt (tuy nhiên cũng có thể độ thích nghi càng bé thì NST lại càng phát triển). Ví dụ:
Bài toán1: Travelling Salesman Problem(TSP)
Cho n thành phố và ma trận C kích thước nxn. Chi phí đi giữa thành phố i và j là Cij (Cij = Cji). Hãy tìm một hành trình từ một thành phố bất kì đi qua n thành phố, mỗi thành phố đúng 1 lần rồi trở về thành phố xuất phát sao cho tổng chi phí là nhỏ nhất.
Trong bài toán này, có thể thấy rõ nghiệm của bài toán là 1 vectơ A độ dài n, chính là một hoán vị của các số tự nhiên liên tiếp từ 1 đến n. Chỉ số Ai cho biết thành phố thứ i trong hành trình. Vd: n=5, A1 = [2,3,4,1,5] thì hành trình của chúng ta là bắt đầu từ thành phố thứ 2 đi qua lần lượt các thành phố 3,4,1,5 rồi trở về 2.
Như vậy các nhiễm sắc thể chính là các mảng độ dài n, còn các gen là các phần tử của mảng. Độ thích nghi của 1 nhiễm sắc thể A (vectơ A) chính là chi phí đi lại theo hành trình đã vạch ra ở A. Theo ví dụ trên độ thích nghi của A1 là
F (A1) = C23 + C34 + C41 + C15 + C 52.
F càng bé thì A1 càng được đánh giá tốt.
Bài toán 2: Tập thống trị.
Cho đồ thị G có n đỉnh và ma trận C kích thước nxn chỉ gồm các giá trị 0,1. Cij =1 nếu i thống trị j, và Cij = 0 nếu i không thống trị j. Giả thiết rằng mọi đỉnh đều thống trị chính nó (Cii =1 với mọi i). Hãy tìm tập A gồm ít nhất các đỉnh của đồ thị sao cho A thống trị G.
Trong bài toán này, ta coi nghiệm của bài toán (cũng là các nhiễm sắc thể ) là một mảng M độ dài n, phần tử Mi (các gen) mang giá trị 1 hay 0 cho biết đỉnh i của đồ thị có thuộc tập A hay không. Độ thích nghi F của M chính là số phần tử có giá trị 1 của M. Vd: n=6,
M = [1,0,1,1,0,0] thì F(M) = 3.
Thuật giải di truyền:
Trong thuật giải di truyền, các cá thể mới liên tục được sinh ra trong quá trình tiến hoá nhờ sự lai ghép ở thế hệ cha-mẹ. Một cá thể mới có thể mang những tính trạng của cha-mẹ (di truyền), cũng có thể mang những tính trạng hoàn toàn mới(đột biến). Di truyền và đột biến là hai cơ chế có vai trò quan trọng như nhau trong tiến trình tiến hoá, dù rằng đột biến xảy ra với xác xuất nhỏ hơn rất nhiều so với hiện tượng di truyền. Các thuật toán tiến hoá, tuy có những điểm khác biệt, nhưng đều mô phỏng bốn quá trình cơ bản: Lai ghép, đột biến, sinh sản và chọn lọc tự nhiên.
Như vậy, quá trình tiến hoá càng lâu thì càng có điều kiện cho các cá thể tốt được sinh ra.
1. Quá trình lai ghép (phép lai)
Phép lai là quá trình hình thành nhiễm sắc thể mới trên cơ sở các nhiễm sắc thể cha-mẹ, bằng cách ghép một hay nhiều đoạn gen của hai (hay nhiều)
nhiễm sắc thể cha-mẹ với nhau. Ví dụ về một phép lai với xác suất Pc có thể mô phỏng như sau:
- Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kì trong quần thể. Giả sử các nhiễm sắc thể của cha-mẹ đều có m gen.
- Tạo một số ngẫu nhiên trong khoảng từ 1 đến m - 1 (ta gọi là điểm lai) Điểm lai chia các chuỗi cha-mẹ dài m thành hai nhóm chuỗi con dài m1 và m2. Hai chuỗi nhiễm sắc thể con mới sẽ là m11 + m22 và m12 + m21
- Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hoá tiếp theo.
2. Quá trình đột biến (phép đột biến ).
Đột biến là hiện tượng cá thể con mang một (số) tính trạng không có trong mã di truyền của cha-mẹ. Phép đột biến xảy ra với xác suất Pm nhỏ hơn rất nhiều so với xác suất lai Pc. Một phép đột biến có thể mô phỏng như sau:
Chọn ngẫu nhiên một cá thể cha-mẹ bất kì trong quần thể.
Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1≤ k ≤ m)
Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá trình tiến hoá tiếp theo.
3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)
Phép tái sinh là quá trình trong đó các cá thể được sao chép trên cơ sở độ thích nghi của nó. Còn phép chọn là quá trình loại bỏ các cá thể xấu trong quần thể để chỉ giữ lại trong quần thể các cá thể tốt. Phép chọn có thể được mô phỏng như sau:
Sắp xếp quần thể theo thứ tự độ tốt giảm dần.
Loại bỏ các cá thể cuối dãy để chỉ giữ lại m cá thể tốt nhất, ở đây ta giả sử quần thể có kích thước cố định m.
Một thuật giải di truyền giải được một bài toán được cho phải có 5 thành phần sau:
Một cấu trúc dữ liệu I biểu diễn không gian lời giải của bài toán.
Phương pháp khởi tạo quần thể ban đầu P(0).
Hàm định nghĩa độ thích nghi Eval(.) đóng vai trò môi trường.
Các phép toán di truyền như đã mô phỏng ở trên.
Và các tham số thuật giải di truyền sử dụng (kích thước quần thể, xác suất lai, đột biến v.v...)
Cấu trúc thuật giải di truyền tổng quát:
Bắt đầu
t=0;
Khởi tạo P(t);
Tính độ thích nghi cho các cá thể thuộc P(t);
Khi (điều kiện dừng chưa thoả) lặp
t = t+1;
Tái sinh P′(t) từ P(t);
Lai Q(t) từ P(t-1);
Đột biến R(t) từ P(t-1);
Chọn lọc P(t) từ P(t-1) υ Q(t) υ R(t) υ P(t);
Hết lặp
Kết thúc.
Các bài toán mẫu:
Đến đây chúng ta kết thúc vấn đề bằng đoạn chương trình giải bài toán
Travelling Salesman đã đề cập ở trên bằng thuật giải tiến hoá GENETIC:
Nên chú ý rằng GENETIC không phải lúc nào cũng có thể tìm được lời giải tối ưu cho bài toán, đôi khi nó chỉ cho kết quả gần tối ưu. Ta chỉ nên dùng GENETIC cho các bài toán không có thuật giải tối ưu hoặc không biết thuật giải tối ưu.
File Input: travel.inp
Dòng 1: n (1≤ n ≤ 100);
N dòng sau: ma trận Cij cho biết chi phí đi từ thành phố i đến j.
{$R+,S+,Q+,B-}
{$M 16384,0,655360}
Uses crt;
Const
Time = 5;{s}{thời gian chạy càng lâu thì kết quả càng tốt}
Inp = 'travel.inp';
Out = 'travel.out';
Max = 110;
Sonstmax = 255;
tilelai = 25;{%}
tiledotbien = 1;{%}
Type
arr100int = array[0..max] of integer;
arr100100int = array[0..max] of arr100int;
arr100byte = array[0..max] of byte;
arr100100byte = array[0..max] of arr100byte;
arrnst = array[0..sonstmax+2] of arr100byte;
arr100bool = array[0..max] of boolean;
arr100long = array[0..sonstmax+2] of longint;
Var
fi, fo : text;
n, solai, c1, c2, sonst,
count : integer;
c : arr100100int;
nst : arrnst;
res, tenlai, nst1, nst2,
n1, n2 : arr100byte;
f1, f2 : arr100bool;
cost : arr100long;
best, t1 : longint;
current : longint absolute $0000:$046C;
Procedure khoitao;
Begin
t1:= current;
Assign(fi, inp); Reset(Fi);
Assign(Fo, out);Rewrite(Fo);
End; { of procedure }
{---------------------------------------}
Procedure docdulieu;
Var i, j : integer;
Begin
Readln(Fi, n);
For i:= 1 to N do
Begin
For j:= 1 to N do Read(Fi, c[i, j]);
Readln(Fi);
End; { of for }
End; { of procedure }
{--------------------------------------}
Procedure chuanbi;
Begin
Best:= maxlongint;
Randomize;
sonst:= round(2.5*n);
End; { of procedure }
Function f(d : integer) : longint;
Var i : integer;
sum : longint;
Begin
sum:= c[nst[d, 1], nst[d, n]];
For i:= 1 to N do inc(sum, c[nst[d, i], nst[d, i+1]]);
f:= sum;
If best > sum then
Begin
best:= sum;
res:= nst[d];
count:= 0;
End; { of if }
End; { of procedure }
{--------------------------------------}
Procedure tao(d : integer);
Var i, j, t : integer;
Begin
For i:= 1 to N do
nst[d, i]:= i;
For i:= 1 to n*2 do begin
j:= random(n) + 1;
t:= nst[d, j];
nst[d, j]:= nst[d, 1];
nst[d, 1]:= t;
End; { of for }
If best > f(d) then
Begin
best:= f(D);
res:= nst[d];
count:= 0;
End; { of if }
cost[d]:= f(d);
end; { of procedure }
{-----------------------------------}
Procedure taoquanthe;
Var i : integer;
Begin
For i:= 1 to sonst do
tao(i);
End; { of procedure }
Procedure chonnstlai;
Var i, t : Integer;
Begin
solai:= 0;
For i:= 1 to sonst do
Begin
t:= random(100);
If t < tilelai then
Begin
inc(solai);
tenlai[solai]:= i;
End; { of if }
End; { of for }
End; { of procedure }
{------------------------------------}
Procedure them1(d : integer);
Begin
f1[d]:= false;
inc(c1);
if c1 > n then c1:= 1;
n1[c1]:= d;
End; { of procedure }
Procedure them2(d : integer);
Begin
f2[d]:= false;
inc(c2);
if c2 > n then c2:= 1;
n2[c2]:= d;
End; { of procedure }
Procedure tienhanhlai;
Var a, b, i, t, j : integer;
Begin
a:= random(n-1)+1;c1:=a-1;
b:= random(n-a)+1+a;c2:=a-1;
fillchar(f1, sizeof(F1), true);
fillchar(F2, sizeof(F2), true);
for i:= a to b do
Begin
them1(nst2[i]);
them2(nst1[i]);
End; { of for }
For i:= b+1 to N do
Begin
if f1[nst1[i]] then them1(nst1[i]);
if f2[nst2[i]] then them2(nst2[i]);
End; { of for }
For i:= 1 to b do
Begin
if f1[nst1[i]] then them1(nst1[i]);
if f2[nst2[i]] then them2(nst2[i]);
End; { of for }
End; { of procedure }
{---------------------------------}
Procedure add(var đ : arr100byte);
Var i, d : integer;
maxx, t : longint;
Begin
nst[sonst+1]:= đ;
t:= f(sonst + 1);
maxx:= 0;
For i:= 1 to sonst do
if cost[i] > maxx then
Begin
maxx:= cost[i];
d:= i;
End; { of if }
if cost[i] > t then
Begin
nst[d]:= đ;
cost[d]:= t;
End; { of if }
End; { of procedure }
{-----------------------------------}
Procedure lainst;
Var i, j : integer;
Begin
For i:= 1 to solai do
if i mod 2 = 0 then
Begin
nst1:= nst[tenlai[i-1]];
nst2:= nst[tenlai[i]];
tienhanhlai;
add(n1);
add(n2);
End; { of if }
End; { of procedure }
{-----------------------------------}
Procedure lai;
Begin
count:= 0;
repeat
chonnstlai;
lainst;
inc(Count);
if count > 10*n then exit;
{ write(#13, count);}
until current-t1 > Time*18;
End; { of procedure }
{-----------------------------------}
Procedure tinh;
Begin
Repeat
taoquanthe;
lai;
until current-t1 > Time*18;
End; { of procedure }
{----------------------------------}
Procedure ghikq;
Var i : integer;
Begin
Writeln(Fo, best);
For i:= 1 to N do Write(Fo, res[i] : 3);
close(Fi);
close(Fo);
writeln;
writeln(best);readln;
End; { of procedure }
{-------------------------------------}
Begin
khoitao;
docdl;
chuanbi;
tinh;
ghikq;
End. { of program }
Công thức tổng quát:
Cấu trúc dữ liệu + Thuật giải di truyền = Chương trình tiến hoá
Chương trình tiến hoá:
Thuật ngữ Chương trình tiến hoá trong công thức trên la khái niệm dùng để chỉ các chương trình máy tính có sử dụng các thuật toán tìm kiếm và tối ưu hoá dựa trên nguyên lý tiến hoá tự nhiên. Ta gọi chung các thuật toán như thế là thuật toán tiến hoá.
Thuật giải di truyền, cũng như các thuật toán tiến hoá nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hoá tự nhiên là hoàn hảo nhất, hợp lý nhất, và tự nó đã mang tính tối ưu. Quan niệm này có thể được xem như là một tiên đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách quan. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn, phát triển hơn, hoàn thiện hơn thế hệ trước. Tiến hoá tự nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hoá tự nhiên, các thế hệ mới luôn được sinh ra để bổ xung thay thế thế hệ cũ. Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại, cá thể nào không thích ứng với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực thúc đẩy quá trình tiến hoá. Ngược lại, tiến hoá cũng tác động trở lại góp phần làm thay đổi môi trường.
Cấu trúc dữ liệu:
Các chương trình tiến hoá được dùng để giải các bài toán tìm nghiệm. Nghiệm của bài toán được biểu thị bằng các nhiễm sắc thể (NST), mỗi NST bao gồm nhiều gen. Mỗi NST có một giá trị gọi là độ thích nghi cho biết nó tốt hơn hay kém hơn các NST khác. Trong một bài toán, độ thích nghi càng cao thì NST càng được đánh giá tốt (tuy nhiên cũng có thể độ thích nghi càng bé thì NST lại càng phát triển). Ví dụ:
Bài toán1: Travelling Salesman Problem(TSP)
Cho n thành phố và ma trận C kích thước nxn. Chi phí đi giữa thành phố i và j là Cij (Cij = Cji). Hãy tìm một hành trình từ một thành phố bất kì đi qua n thành phố, mỗi thành phố đúng 1 lần rồi trở về thành phố xuất phát sao cho tổng chi phí là nhỏ nhất.
Trong bài toán này, có thể thấy rõ nghiệm của bài toán là 1 vectơ A độ dài n, chính là một hoán vị của các số tự nhiên liên tiếp từ 1 đến n. Chỉ số Ai cho biết thành phố thứ i trong hành trình. Vd: n=5, A1 = [2,3,4,1,5] thì hành trình của chúng ta là bắt đầu từ thành phố thứ 2 đi qua lần lượt các thành phố 3,4,1,5 rồi trở về 2.
Như vậy các nhiễm sắc thể chính là các mảng độ dài n, còn các gen là các phần tử của mảng. Độ thích nghi của 1 nhiễm sắc thể A (vectơ A) chính là chi phí đi lại theo hành trình đã vạch ra ở A. Theo ví dụ trên độ thích nghi của A1 là
F (A1) = C23 + C34 + C41 + C15 + C 52.
F càng bé thì A1 càng được đánh giá tốt.
Bài toán 2: Tập thống trị.
Cho đồ thị G có n đỉnh và ma trận C kích thước nxn chỉ gồm các giá trị 0,1. Cij =1 nếu i thống trị j, và Cij = 0 nếu i không thống trị j. Giả thiết rằng mọi đỉnh đều thống trị chính nó (Cii =1 với mọi i). Hãy tìm tập A gồm ít nhất các đỉnh của đồ thị sao cho A thống trị G.
Trong bài toán này, ta coi nghiệm của bài toán (cũng là các nhiễm sắc thể ) là một mảng M độ dài n, phần tử Mi (các gen) mang giá trị 1 hay 0 cho biết đỉnh i của đồ thị có thuộc tập A hay không. Độ thích nghi F của M chính là số phần tử có giá trị 1 của M. Vd: n=6,
M = [1,0,1,1,0,0] thì F(M) = 3.
Thuật giải di truyền:
Trong thuật giải di truyền, các cá thể mới liên tục được sinh ra trong quá trình tiến hoá nhờ sự lai ghép ở thế hệ cha-mẹ. Một cá thể mới có thể mang những tính trạng của cha-mẹ (di truyền), cũng có thể mang những tính trạng hoàn toàn mới(đột biến). Di truyền và đột biến là hai cơ chế có vai trò quan trọng như nhau trong tiến trình tiến hoá, dù rằng đột biến xảy ra với xác xuất nhỏ hơn rất nhiều so với hiện tượng di truyền. Các thuật toán tiến hoá, tuy có những điểm khác biệt, nhưng đều mô phỏng bốn quá trình cơ bản: Lai ghép, đột biến, sinh sản và chọn lọc tự nhiên.
Như vậy, quá trình tiến hoá càng lâu thì càng có điều kiện cho các cá thể tốt được sinh ra.
1. Quá trình lai ghép (phép lai)
Phép lai là quá trình hình thành nhiễm sắc thể mới trên cơ sở các nhiễm sắc thể cha-mẹ, bằng cách ghép một hay nhiều đoạn gen của hai (hay nhiều)
nhiễm sắc thể cha-mẹ với nhau. Ví dụ về một phép lai với xác suất Pc có thể mô phỏng như sau:
- Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kì trong quần thể. Giả sử các nhiễm sắc thể của cha-mẹ đều có m gen.
- Tạo một số ngẫu nhiên trong khoảng từ 1 đến m - 1 (ta gọi là điểm lai) Điểm lai chia các chuỗi cha-mẹ dài m thành hai nhóm chuỗi con dài m1 và m2. Hai chuỗi nhiễm sắc thể con mới sẽ là m11 + m22 và m12 + m21
- Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hoá tiếp theo.
2. Quá trình đột biến (phép đột biến ).
Đột biến là hiện tượng cá thể con mang một (số) tính trạng không có trong mã di truyền của cha-mẹ. Phép đột biến xảy ra với xác suất Pm nhỏ hơn rất nhiều so với xác suất lai Pc. Một phép đột biến có thể mô phỏng như sau:
Chọn ngẫu nhiên một cá thể cha-mẹ bất kì trong quần thể.
Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1≤ k ≤ m)
Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá trình tiến hoá tiếp theo.
3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)
Phép tái sinh là quá trình trong đó các cá thể được sao chép trên cơ sở độ thích nghi của nó. Còn phép chọn là quá trình loại bỏ các cá thể xấu trong quần thể để chỉ giữ lại trong quần thể các cá thể tốt. Phép chọn có thể được mô phỏng như sau:
Sắp xếp quần thể theo thứ tự độ tốt giảm dần.
Loại bỏ các cá thể cuối dãy để chỉ giữ lại m cá thể tốt nhất, ở đây ta giả sử quần thể có kích thước cố định m.
Một thuật giải di truyền giải được một bài toán được cho phải có 5 thành phần sau:
Một cấu trúc dữ liệu I biểu diễn không gian lời giải của bài toán.
Phương pháp khởi tạo quần thể ban đầu P(0).
Hàm định nghĩa độ thích nghi Eval(.) đóng vai trò môi trường.
Các phép toán di truyền như đã mô phỏng ở trên.
Và các tham số thuật giải di truyền sử dụng (kích thước quần thể, xác suất lai, đột biến v.v...)
Cấu trúc thuật giải di truyền tổng quát:
Bắt đầu
t=0;
Khởi tạo P(t);
Tính độ thích nghi cho các cá thể thuộc P(t);
Khi (điều kiện dừng chưa thoả) lặp
t = t+1;
Tái sinh P′(t) từ P(t);
Lai Q(t) từ P(t-1);
Đột biến R(t) từ P(t-1);
Chọn lọc P(t) từ P(t-1) υ Q(t) υ R(t) υ P(t);
Hết lặp
Kết thúc.
Các bài toán mẫu:
Đến đây chúng ta kết thúc vấn đề bằng đoạn chương trình giải bài toán
Travelling Salesman đã đề cập ở trên bằng thuật giải tiến hoá GENETIC:
Nên chú ý rằng GENETIC không phải lúc nào cũng có thể tìm được lời giải tối ưu cho bài toán, đôi khi nó chỉ cho kết quả gần tối ưu. Ta chỉ nên dùng GENETIC cho các bài toán không có thuật giải tối ưu hoặc không biết thuật giải tối ưu.
File Input: travel.inp
Dòng 1: n (1≤ n ≤ 100);
N dòng sau: ma trận Cij cho biết chi phí đi từ thành phố i đến j.
{$R+,S+,Q+,B-}
{$M 16384,0,655360}
Uses crt;
Const
Time = 5;{s}{thời gian chạy càng lâu thì kết quả càng tốt}
Inp = 'travel.inp';
Out = 'travel.out';
Max = 110;
Sonstmax = 255;
tilelai = 25;{%}
tiledotbien = 1;{%}
Type
arr100int = array[0..max] of integer;
arr100100int = array[0..max] of arr100int;
arr100byte = array[0..max] of byte;
arr100100byte = array[0..max] of arr100byte;
arrnst = array[0..sonstmax+2] of arr100byte;
arr100bool = array[0..max] of boolean;
arr100long = array[0..sonstmax+2] of longint;
Var
fi, fo : text;
n, solai, c1, c2, sonst,
count : integer;
c : arr100100int;
nst : arrnst;
res, tenlai, nst1, nst2,
n1, n2 : arr100byte;
f1, f2 : arr100bool;
cost : arr100long;
best, t1 : longint;
current : longint absolute $0000:$046C;
Procedure khoitao;
Begin
t1:= current;
Assign(fi, inp); Reset(Fi);
Assign(Fo, out);Rewrite(Fo);
End; { of procedure }
{---------------------------------------}
Procedure docdulieu;
Var i, j : integer;
Begin
Readln(Fi, n);
For i:= 1 to N do
Begin
For j:= 1 to N do Read(Fi, c[i, j]);
Readln(Fi);
End; { of for }
End; { of procedure }
{--------------------------------------}
Procedure chuanbi;
Begin
Best:= maxlongint;
Randomize;
sonst:= round(2.5*n);
End; { of procedure }
Function f(d : integer) : longint;
Var i : integer;
sum : longint;
Begin
sum:= c[nst[d, 1], nst[d, n]];
For i:= 1 to N do inc(sum, c[nst[d, i], nst[d, i+1]]);
f:= sum;
If best > sum then
Begin
best:= sum;
res:= nst[d];
count:= 0;
End; { of if }
End; { of procedure }
{--------------------------------------}
Procedure tao(d : integer);
Var i, j, t : integer;
Begin
For i:= 1 to N do
nst[d, i]:= i;
For i:= 1 to n*2 do begin
j:= random(n) + 1;
t:= nst[d, j];
nst[d, j]:= nst[d, 1];
nst[d, 1]:= t;
End; { of for }
If best > f(d) then
Begin
best:= f(D);
res:= nst[d];
count:= 0;
End; { of if }
cost[d]:= f(d);
end; { of procedure }
{-----------------------------------}
Procedure taoquanthe;
Var i : integer;
Begin
For i:= 1 to sonst do
tao(i);
End; { of procedure }
Procedure chonnstlai;
Var i, t : Integer;
Begin
solai:= 0;
For i:= 1 to sonst do
Begin
t:= random(100);
If t < tilelai then
Begin
inc(solai);
tenlai[solai]:= i;
End; { of if }
End; { of for }
End; { of procedure }
{------------------------------------}
Procedure them1(d : integer);
Begin
f1[d]:= false;
inc(c1);
if c1 > n then c1:= 1;
n1[c1]:= d;
End; { of procedure }
Procedure them2(d : integer);
Begin
f2[d]:= false;
inc(c2);
if c2 > n then c2:= 1;
n2[c2]:= d;
End; { of procedure }
Procedure tienhanhlai;
Var a, b, i, t, j : integer;
Begin
a:= random(n-1)+1;c1:=a-1;
b:= random(n-a)+1+a;c2:=a-1;
fillchar(f1, sizeof(F1), true);
fillchar(F2, sizeof(F2), true);
for i:= a to b do
Begin
them1(nst2[i]);
them2(nst1[i]);
End; { of for }
For i:= b+1 to N do
Begin
if f1[nst1[i]] then them1(nst1[i]);
if f2[nst2[i]] then them2(nst2[i]);
End; { of for }
For i:= 1 to b do
Begin
if f1[nst1[i]] then them1(nst1[i]);
if f2[nst2[i]] then them2(nst2[i]);
End; { of for }
End; { of procedure }
{---------------------------------}
Procedure add(var đ : arr100byte);
Var i, d : integer;
maxx, t : longint;
Begin
nst[sonst+1]:= đ;
t:= f(sonst + 1);
maxx:= 0;
For i:= 1 to sonst do
if cost[i] > maxx then
Begin
maxx:= cost[i];
d:= i;
End; { of if }
if cost[i] > t then
Begin
nst[d]:= đ;
cost[d]:= t;
End; { of if }
End; { of procedure }
{-----------------------------------}
Procedure lainst;
Var i, j : integer;
Begin
For i:= 1 to solai do
if i mod 2 = 0 then
Begin
nst1:= nst[tenlai[i-1]];
nst2:= nst[tenlai[i]];
tienhanhlai;
add(n1);
add(n2);
End; { of if }
End; { of procedure }
{-----------------------------------}
Procedure lai;
Begin
count:= 0;
repeat
chonnstlai;
lainst;
inc(Count);
if count > 10*n then exit;
{ write(#13, count);}
until current-t1 > Time*18;
End; { of procedure }
{-----------------------------------}
Procedure tinh;
Begin
Repeat
taoquanthe;
lai;
until current-t1 > Time*18;
End; { of procedure }
{----------------------------------}
Procedure ghikq;
Var i : integer;
Begin
Writeln(Fo, best);
For i:= 1 to N do Write(Fo, res[i] : 3);
close(Fi);
close(Fo);
writeln;
writeln(best);readln;
End; { of procedure }
{-------------------------------------}
Begin
khoitao;
docdl;
chuanbi;
tinh;
ghikq;
End. { of program }