Thuật toán di truyền - Ứng dụng giải một số bài toán kinh điển (phần 2)

Bài đăng này đã không được cập nhật trong 6 năm

Trong bài viết trước mình đã giới thiệu về thuật toán di truyền, ở bài viết này mình sẽ demo giải quyết một bài toán kinh điển là "Người bán hàng"

Phát biểu bài toán

Cho trước một danh sách các thành phố và khoảng cách giữa chúng, tìm chu trình ngắn nhất thăm mỗi thành phố đúng một lần. Ở đây mình sẽ ví dụ với danh sách các thành phố và khoảng cách như sau:

Thành phố	A	B	C	D	E
A	max	5	6	9	max
B	5	max	10	2	7
C	6	10	max	max	15
D	9	2	max	max	1
E	max	7	15	1	max

Những thành phố không có đường đi nối nhau hoặc cùng thành phố sẽ mặc định để khoảng cách là max, vì mình sẽ đánh giá độ thích nghi theo khoảng cách, khoảng cách càng thấp thì độ thích nghi càng cao.

Code nào :v

Mình sẽ viết bằng Java nha (hehe)

Các biến sẽ sử dụng

    public int  max = 10000;
	public int khoangcach[][] = {{max,5,6,9,max},{5,max,10,2,7},{6,10,max,max,15},{9,2,max,max,1},{max,7,15,1,max}};
	public Random ran = new Random();
	public static int n = 1000;
	int[][] nghiem = new int [n][];
	int[] thichnghi = new int[n];

max: mình mặc định nó sẽ là 10000, lấy cái số thiệt to rứa thôi (yaoming)
khoangcach[][]: cái mảng để mình lưu cái khoảng cách trong đề bài thui
nghiem[][]: lưu tất cả các nghiệm
thichnghi[]: lưu độ thích nghi của nghiệm[i]

Khởi tạo quần thể (tập nghiệm)

Mình sẽ khởi tạo random 1000 nghiệm (cá thể) (bao nhiêu cũng đc, nhiều nhiều cho đông vui :v), mỗi nghiệm là tập 5 thành phố (lộ trình sẽ đi qua), vì random cho nên nó rất chi là random

    public void khoitao()
	{
		for (int i=0;i<n;i++)
		{
			nghiem[i] = new int[5];
			for (int j=0;j<5;j++)	 nghiem[i][j] = ran.nextInt(5); 
		}
	}

Trong đống này, hên thì có thằng là tối ưu, xui thì không có thằng nào tối ưu cả, kệ nó, xử lí sau (hihi)

Đánh giá

Sau khi có được quần thể rồi thì mình bắt đầu đánh giá độ thích nghi của từng cá thể trong quần thể đó với điều kiện môi trường (cái yêu cầu bài toán)

    public void danhgia()
	{
		for (int i = 0;i<n;i++)
		{
			thichnghi[i] =0;
			for(int j=0;j<4;j++) thichnghi[i] += khoangcach[nghiem[i][j]][nghiem[i][j+1]]; 
			for(int j=0;j<4;j++)
				for (int t=j+1;t<5;t++)
					if (nghiem[i][j] == nghiem[i][t]) thichnghi[i]+= 100000;
		}
	}

Chỉ đơn giản là cộng tất cả các khoảng cách giữa các thành phố lại thôi, những nghiệm có các thành phố trùng nhau thì mình sẽ cộng thêm cho nó một số thiệt to (mỗi thành phố chỉ qua 1 lần), và lưu trong mảng thichnghi[]

Chọn lọc

Sau khi đánh giá độ thích nghi của các cá thể thì quá trình chọn lọc sẽ bắt đầu

    public void chonloc()
	{
		int [] temp = thichnghi.clone();
		Arrays.sort(temp);
		int nguong = temp[n*80/100];
		for (int i=0;i<n;i++){
			if (thichnghi[i]>nguong){
				nghiem[i]=nghiem[ran.nextInt(n)].clone();
			}
		}
	}

Mình sẽ sắp xếp mảng thichnghi[] rồi lấy ngưỡng ở 80%, những đứa nào có độ thích nghi lớn hơn ngưỡng sẽ bị loại bỏ và tạo ra 1 đứa random khác (vì ở đây mình lấy độ thích nghi là tổng khoảng cách nên càng nhỏ càng tốt hehe)

Lai ghép

Sau quá trình chọn lọc sẽ đến lai ghép, kiểu như sinh sản ấy, lấy nữa gen của mẹ, ghép nữa gen của cha, ra thằng con (hihi)

    public void laighep() {
		for (int i=0;i<20;i++){
			int cha=ran.nextInt(n);
			int me = ran.nextInt(n);
			for (int j=0;j<nghiem[cha].length;j++)
				if (ran.nextInt(2)==1){
					int temp=nghiem[cha][j];
					nghiem[cha][j]=nghiem[me][j];
					nghiem[me][j]=temp;
			}
		}
	}

sinh sản đơn giản rứa thôi :v

Đột biến

Có 1 cái quan trọng trong di truyền đó là đột biến, chính đột biến là nhân tố dẫn đến những giống loài mới có độ thích nghi cao hơn với môi trường

    public void dotbien()
	{
		int index=ran.nextInt(n);
		int bit=ran.nextInt(5);
		nghiem[index][bit]= ran.nextInt(5);
	}

Lấy đại một thằng rồi cho nó đột biến 1 gen thôi.

Như vậy là xong rồi, giờ viết cái hàm để in ra kết quả thôi

    public void Print() {
		int [] temp = thichnghi.clone();
		Arrays.sort(temp);
		int best = temp[0];
		System.out.print(best+": ");
		for (int i=0;i<n;i++){
			if (thichnghi[i]==best){
				for (int j=0;j<nghiem[i].length;j++)
					System.out.print(nghiem[i][j]+" ,");
				System.out.println();
				break;
			}
		}
	}

public static void main (yaoming)

    public static void main(String[] args)
	{
		nguoibanhang jang = new nguoibanhang();
		jang.khoitao();
		for (int i=0;i<100;i++)
		{
			jang.danhgia();
			jang.Print();
			jang.chonloc();
			jang.laighep();
			jang.dotbien();
		}		
	}

Như vậy là xong, ở đây mình cho quá trình di truyền diễn ra trong 100 đời thôi, mấy đời cũng được, càng lâu đời thì kết quả ra càng tối ưu.