Trường Đại học Hải Phòng Khoa: Công nghệ thông tin

Đề tài: Thuật toán di truyền và ứng dụng giải bài toán người du lịch.     Giảng viên hướng dẫn:  Th.S LÊ ĐẮC NHƯỜNG          Sinh viên:   Bùi Thị Hạnh. Hoàng T.Thu Hiền Trần Hồng Lân 1

Nội dung trình bày:

2

I: Giải thuật di truyền.         *Khái niệm,

Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm  tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp.

Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận  dụng các nguyên lý của tiến hóa như  di truyền, đột biến, chọn lọc  tự nhiên, và trao đổi chéo

3

ng

I: Giải thuật di truyền.         *  T  t ư ưở

Mô phỏng các hiện tượng tự nhiên: Kế thừa và đấu tranh sinh tồn  để cái tiến.

Ví dụ: Sự tiến hóa của loài thỏ.

Thỏ đần  độn, chậm  chạp

Thỏ thông  minh nhanh  nhẹn

Thỏ bị  loại bỏ

4

ng

ầ

I: Giải thuật di truyền.         *  T  t ư ưở ầ ể Qu n th  ban đ u

5

ng

I: Giải thuật di truyền.         *  T  t ư ưở Quá trình sinh s nả

6

ng ắ ầ

i, b t đ u quá trình sinh

I: Giải thuật di truyền.         *  T  t ư ưở ạ ể ầ Qu n th  còn l s nả

7

ng

I: Giải thuật di truyền.         *  T  t ư ưở ế ệ Th  h  sau .

8

I: Giải thuật di truyền.         *  L u đư ồ

9

ư ồ ậ ả ơ ả L u đ  thu t gi i c  b n.

ử

ề

I: Giải thuật di truyền.         *  Các toán t

di truy n

Văn bản  của bạn.

Biểu  diễn cá  thể.

Đột biến Toán tử

Hàm  mục  tiêu.

di truyền

Lai tạo

Lai  ghép

10

ử

ề

I: Giải thuật di truyền.         *  Các toán t

di truy n

ễ ể ể:

v Bi u di n cá th   Là vi c ánh x  các tham s  c a bài toán lên m t chu i có chi u dài  ị xác đ nh.

ố ủ ệ ề ạ ộ ỗ

ộ

ấ ộ ư

ả ề ề ầ ể ấ ả ỗ ụ v M t hàm m c tiêu (fitness): ầ ỗ  L y m t chu i NST là đ u vào và tr  v  giá tr  t chu i NST đó đ  đánh giá trên v n đ  c n gi ị ượ ng tr ng cho  ế i quy t.

ạ ử tái t o

v Toán t Là quá trình các chu i đ tiêu..

11

ỗ ượ ự ụ ọ ộ ị c l a ch n tùy thu c vào giá tr  hàm m c

ử

ề

I: Giải thuật di truyền.         *  Các toán t

di truy n

ơ ở ẹ ớ

ủ ề ề ằ ạ

v Lai ghép.    Phép lai là quá trình hình thành NST m i trên c  s  NST cha m ,    ộ    b ng cách ghép m t hay nhi u đo n gen c a hai (hay nhi u) NST  cha    m  khác nhau.

ü Lai ghép một điểm cắt, nhiều

ü Lai ghép nhi u ề

điểm cắt

đo nạ

ẹ

ộ ế

ộ ố ạ ặ ộ

v Đ t bi n  ế Đ t bi n là tình tr ng NST con không có m t (ho c m t s ) tính  ẹ tr ng có trong mã di truy n c a cha m .

12

ề ủ ộ ạ

I. Giải thuật di truyền.         *  Đ u tranh sinh  ấ t nồ

ọ

ừ ầ

ả

ộ

ể ế ẹ ể

ữ Ch n nh ng NST t  qu n th  k t qu  theo m t quy  ế ệ ớ ế ắ t c nào đó thay th  cho cha m  đ  sinh ra th  h  m i.

Phương thức 2

Phương thức 3

Phương thức  1

TT

Chọn những cá thể  ưu tú nhất

Tráo đổi hoàn toàn  05 cha mẹ bằng con.

Tráo đổi ngẫu nhiên (k  con mẹ thay thế  bằng  k  con con)

13

ướ

ả

c gi

ậ i thu t

I. Giải thuật di truyền.         *  Các b

ướ

ả

ủ ấ

ọ        B c 1: Ch n mô hình cho gi

ề i pháp c a v n đ .

ướ

ỗ

ị

ả

ệ

ỉ        B c 2: Ch  đ nh cho m i gi

ộ i pháp m t ký hi u

ệ ố

ướ

ừ

ề

ố

ả

ấ        B c 3: Tìm hàm s  thích nghi cho v n đ  và tính h  s  thích nghi cho t ng gi

i pháp

ệ ố

ướ

ự

ủ

ả

ệ ự ạ

ể ự

ế

B c 4: D a trên h  s  thích nghi c a các gi

i pháp đ  th c hi n s  t o sinh (reproduction) và bi n

ả

ươ

ứ

ế

ế

ồ

ộ

hóa    các gi

i pháp. Các ph

ng th c bi n hóa g m: lai ghép (cross over), đ t bi n (mutation).

ướ

ả

ạ ỏ

ữ

ớ

ả

ệ ố       B c 5: Tính các h  s  thích nghi cho các gi

i pháp m i là lo i b  nh ng gi

ấ ể ỉ i pháp kém nh t đ  ch

ộ ố

ấ ị

ả

cong gi

ữ ạ  l

i m t s  nh t đ nh các gi

i pháp

ướ

ư

ượ

ả

ố ư

ươ

ư ế

ỳ ấ

ạ

ấ

ố

ị

ế       B c 6: N u ch a tìm đ

c gi

i pháp t

i  u hay t

ng đ i khá nh t hay ch a h t  h n k   n đ nh,

ứ

ể

ả

ớ

tr  l

ở ạ ướ i b

c th  4 đ  tìm gi

i pháp m i.

ướ

ượ

ả

ố ư

ặ ế

ể ấ

ứ

ế

ả

ờ

B c 7: Tìm đ

c gi

i pháp t

i  u ho c n u th i gian cho phép đ  ch m d t thì báo cáo k t qu  tính

đ

c.ượ

14

ị i du l ch.

ộ ứ ạ

ườ II. Bài toán ng ị         *Đ nh nghĩa, đ  ph c t p

vĐ nh nghĩa. ị ầ ồ

ỉ

ướ

Cho  đ   th   đ y  đ   n  đ nh  vô  h

ọ

ố

ớ

ủ ng,  có    tr ng                                                                                                                          s  G = (V, E). Tìm  chu trình → ộ

ư ậ

→ → →  v1 v2      … vn v1 V i vi  ọ M t  chu  trình  nh   v y  còn  g i  là  chu  trình

Hamilton.

ị

15

vĐ  ph c t p ộ ứ ạ ộ ớ Bài toán TSP thu c l p bài toán NP­Khó.

ả

ườ

ị

III: Gi

i bài toán ng

ằ i du l ch b ng GA. v    Mã hóa bài toán (đ  th ) ồ ị

Ø Đồ thị được mã hóa bằng danh sách mảng các điểm và tọa độ.

Ø Trọng số trong cột đầu tiên là số hiệu của đỉnh, trọng số thứ hai

Ø Khoảng cách giữa hai đỉnh M(xi, yi) và N(xj, yj) của đồ thị (trọng

là hoành độ, trọng số thứ ba là tung độ.

16

số cho cạnh) được tính theo công thức:

ả

ườ

ằ

ị

III: Gi

i bài toán ng

i du l ch b ng GA.

v    Mã hóa bài toán(chu trình)

Ø Chu trình đ ụ

ằ ượ ứ ự ố ệ ủ c mã hóa b ng m ng có th  t các s  hi u c a

ỉ ả ủ ồ ị ỉ đ nh. Ví d  chu trình c a đ  th  10 đ nh:

ỗ ủ ộ

ố ề ộ ấ ả ượ ạ ằ ØM i chu trình có thông s  v  chi phí c a toàn b  chu trình đó. Chi  ạ t c  các c nh t o nên chu trình. ổ c tính b ng t ng đ  dài t phí này đ

ờ ả ả ậ ØM i chu trình là 1 l i gi i, trong gi ư ề i thu t di truy n coi đó nh

17

ỗ 1cá th . ể

III: Giải bài toán người du lịch bằng GA. v  Khởi tạo quần thể

Ø Quần thể ban đầu được khởi tạo bằng cách sinh ngẫu nhiên các

Ø Số lượng chu trình khởi tạo là một nửa số kích thước cá thể tối

chu trình.

Ø  Việc sinh ngẫu nhiên sử dụng hàm đột biến. Ø Số kích thước cá thể tối đa có thể tùy biến theo số đỉnh của đo

đa.

18

thị cần giải, ở đây chọn kích thước quần thể là 100 cá thể.

III: Giải bài toán người du lịch bằng GA.

v  Lai ghép

ể ầ

ự

ệ

Ø  Lai ghép th c hi n trên 2 cá th  đ uvào

Ø  Thực hiện lai ghép 1 điểm cắt với vị trí cắt là ngẫu nhiên : Ø  Cắt từ điểm p đến hết chu trình của C2 đưa vào chu trình mới, lấy một ví dụ p = 5:

Ø  Xét từ đầu đến cuối chu trình 1, nạp dần các điểm chưa có trong con lai theo thứ tự

duyệt ta được chu trình mới:

19

ạ

ớ

Tính l

i chi phí cho chu trình m i:

Private circle hybridize( circle cl, circle c2)

{          Circle child =new circle (c1.getLength());

Random rand = new Random();

int  p =rand.nextInt(child.length ­ 1)

int I =0;j =0,k=0;

For(i =p; i< child.length; i++){

child.vertex[j] =c2.vertex[i];

j++;

}

For(i = 0; i < child.length; i++){

For(j=0;j

If (c1.vertex[i] == child.length.vertex[j])

Break;

Else

If (j == child.length – p ­ 1){

K++

Child.vertex[j+k] = c1. Vertex[i];

} }}

20

ả

ằ

ị

III: Gi

i bài toán ng

i du l ch b ng GA.

ườ ế ộ v  Đ t bi n.

Ø Ph vào

ươ ứ ộ ế ượ ệ ự ể ầ ự ng th c đ t bi n đ c th c hi n d a trên 1 cá th  đ u

ệ ế ằ ổ

Ø  Th c hi n đ t bi n b ng tráo đ i các đi m trên gen cho nhau.  ề ẫ c sinh ng u nhiên t Ø  S  l n tráo đ i đ

ộ ố ượ ự ố ầ ừ ả ể  trong kho ng 5% chi u

dài chu trình.

Ø  V  trí đi m tráo cũng đ

21

ị ể ượ ẫ ạ c sinh ng u nhiên trong quá trình ch y.

private Circle mutate(Circle c)

{

Int n = c.getLength();

Circle nextgen = new circle(n);

Nextgen.setCircle(n, c.getCircle());

Random rand = new Random();

Int count = rand.nextInt (mutateCoefficien) +1;

Int p1,p2, temp;

While(count >0 )

{

P1 = rand.nextInt(n);

P2 = rand.nextInt(n);

Temp = nextgen.vertex[p1];

Nextgen.vertex[p1] = nextgen.vertex[p2];

Nextgen.vertex[p2] = temp;

Count ­­;

}

Return nextgen;

}

22

ả

ằ

III: Gi

i bài toán ng

i du l ch b ng GA.

ườ ọ ọ ự v  Ch n l c t

ị  nhiên

ả

ằ

ể ặ ị

ể ớ

ố

ủ , l th  h ] = [Kích th

ầ ướ c m c đ nh] + [S  cá th  m i

ọ ọ

ứ

ỗ

ể

ủ

ọ ọ ể ả Ø Ch nl c đ  đ m b o tính cân b ng c a qu n th ế ệ ể ở ố         [S  cá th   sinh] Ø Cách th c ch n l c cá th  đánh giá d a trên chi phí c a m i chu trình

ự Cách thức chọn lọc tự nhiên.

ể

ế

ầ

ắ

ầ

1. S p x p qu n th  theo chi phí tăng d n.

ỉ ố

ự

ẫ

ọ

2. L a ch n ng u nhiên l ch  s  : a (0 < a < l)

ạ ỏ

ể ứ

ấ ừ

ể ứ

ầ

ầ

cá th  đ ng đ u danh sách qu n

3.Lo i b  cá th  th   a kém thích nghi nh t t th .ể

ạ ế

ể

ố

ạ ằ

ướ

4. Lo i đ n khi s  cá th  còn l

i b ng kích th

ặ ị c m c đ nh.

23

private void sortList()

{

int i =0, j =0,min;

Circle temp;

For(I =0;i

{

Min =I;

For(j =i+1;j

{

If(population.get(j).cost

Min =j;

}

Temp = population.get(i);

Population.add(I, population.get(min));

Population.remove(i+1);

Population.remove(min);

Population.add(min, temp);

}

24

ả

ằ

III: Gi

i bài toán ng

i du l ch b ng GA.

ọ ọ ự

ị  nhiên

ườ v  Ch n l c t

v Với quần thể khởi tạo ban đầu được tiến hóa ngẫu nhiên và

v Các cá thể kém thích nghi sẽ bị loại thải và cá thể tốt nhất

thích nghi với điều kiện chọn lọc.

v Việc tiến hóa diễn ra qua một số thế hệ, ở mỗi thế hệ ta thực

được chọn làm lời giải.

25

hiện lai ghép và đột biến ngẫu nhiên trên toàn quần thể.

ầ

ự

ấ

ầ

ả ơ ự ắ Xin chân thành c m  n s  l ng nghe c a các th y cô  ừ giáo và r t mong s  góp ý t

ủ  phía quý th y cô!!

26