Bài toán tối ưu hoá là gì

Theo Russell and Norvig bài toán tối ưu hoá là bài toán mà “the aim is to find the best state according to an objective function” (mình xin phép để nguyên câu tiếng anh).

Trong đó, state trong từ best state phụ thuộc vào ngữ cảnh của bài toán. Ví dục

• Trong ngữ cảnh là mạng neural network, state chính là các trọng số (weight), best state là tìm các trọng số tối ưu
• Trong bài toán 8 hậu, state là vị trí của các con hậu, best state là vị trí tốt nhất thoả yêu cầu, cũng chính là lời giải.
• Trong bài toán người giao hàng, state là các thành phố người giao hàng đi qua.
• Trong bài toán tô màu cho mỗi quốc gia trên bản đồ, state là màu được tô cho mỗi quốc gia

Nói đến đây, các bạn chắc cũng đã hiểu được khái niệm state là gì rồi. Điều quan trọng ở đây là chúng ta có thể biểu diễn state dưới dạng một con số, hoặc một mảng các giá trị số. (nghĩa là chúng ta phải chuyển đổi màu, thành phố, … dưới dạng số) thì mới có thể tính toán được.

Từ best trong chữ best state được biểu diễn bởi một hàm toán học (mà chúng ta quen thuộc với các từ như là objective funtion, fitness funtion, cost funtion, loss function , v.v). Cái mà chúng ta muốn là cực đại hoặc cực tiểu hoá nó (để có được kết quả tốt nhất). Hàm này nhận đầu vào là state array và trả về “fitness” value.

Cho nên, chúng ta có thể định nghĩa đơn giản bài toán tối ưu là việc tìm các giá trị tối ưu để cực đại/ cực tiểu hoá một hàm toán học.

Ví dụ

Một ví dụ xàm xàm như sau

Ta có một (state) vector x = [x0,x1,x2,x3,x4] thuộc đoạn [0,1] một hàm f(x) = x0 + x1 + x2 + x3 + x4, tìm các giá trị x để f đạt cực đại.

Rõ ràng, bằng việc tính nhẩm, chúng ta biết được rằng giá trị cực đại của hàm trên là 5, và lời giải cho bài toán trên là x = [1,1,1,1,1].

Còn theo toán học cấp 3, ta sẽ tính đạo hàm riêng phần của từng phần tử (cái này đơn giản, mình không nhắc lại), và cũng đạt được x = [1,1,1,1,1]

Tại sao lại dùng Randomized Optimization?

Trong bài toán ở trên, chúng ta có thể dễ dàng nhẩm được giá trị tối ưu một cách nhanh chóng. Tuy nhiên, trong thực tế, bài toán sẽ khó hơn một chút, và có nhiều hàm chúng ta không thể dễ dàng tìm được giá trị đạo hàm một cách nhanh chóng được (tốn thời gian rất lâu để giải bài toán ). Lúc này, chúng ta sẽ dùng Randomized optimization.

Randomized optimization sẽ bắt đầu tại một điểm ngẫu nhiên “best” state nào đó, sau đó sẽ sinh ngẫu nhiên một state khác (thường là láng giềng của “best” state hiện tại). Nếu state mới đạt giá trị finest tốt hơn “best” state hiện tại thì gán “best” state bằng state mới. Quá trình này lặp đi lặp lại cho đến khi không thể tìm được state mới này tốt hơn “best” state hiện tại.

Không có gì bảo đảm rằng randomized optimization sẽ tìm được lời giải tối ưu. Ví dụ như hình trên, thuật toán chỉ có thể dừng ở local maximin, rồi đứng yên ở đó. Tuy nhiên, nếu chúng ta thiết lập số lần lặp đủ lớn, thuật toán thông thường sẽ trả về kết quả tốt hơn.

Ở đây, chúng ta có một sự đánh đổi trade-off giữa thời gian tìm ra lời giải tối ưu và chất lượng của lời giải.

Giải bài toán tối ưu bằng thư viện mlrose

Để giải bài toán tối ưu bằng thư viện mlrose, chúng ta sẽ phải định nghĩa 4 thứ:

1. Định nghĩa state vector
2. Định nghĩa hàm fitness function
3. Xác định loại bài toán
4. Chọn một thuật toán tối ưu hoá ngẫu nhiên để chạy.

Để đơn giản, chúng ta sẽ giải quyết bài toán 8 hậu bằng thư viện mlrose.

Bài toán 8 hậu

Nhắc lại một chút về bài toán 8 hậu. Trong bàn cờ vua có kích thước 8x8, chúng ta phải chọn vị trí đặt 8 con hậu sao cho trên mỗi dòng, cột và đường chéo của một con hậu bất kỳ đang đứng không giáp mặt với con hậu khác.

Định nghĩa state

Đây rõ ràng là bài toán tối ưu, và bước đầu tiên ta sẽ định nghĩa một vector trạng thái x = [x0, x1, x2, x3, x4, x5, x6, x7], quy ước toạ độ 0,0 là vị trí trái dưới. Giá trị của xi là vị trị cột của con hậu dòng i đang đứng.

Ví dụ, ở hình trên, ta có x = [6, 1, 7, 5, 0, 2, 3, 4], với x0 = 6 nghĩa là con hậu đang ở cột 0 dòng 6 (góc toạ độ chúng ta khảo sát là trái dưới)

Hình trên không phải là lời giải tối ưu cho bài toán, vì con hậu ở cột 5, cột 6 và cột 7 giáp mặt nhau theo đường chéo.

Định nghĩa fitness funtion

Trong thư viện mlrose đã định nghĩa sẵn hàm fitness function cho một số bài toán đơn giản, ví dụ như trong bài toán 8 hậu vừa rồi. Tuy nhiên, chúng ta sẽ không sử dụng hàm có sẵn đó, mà sẽ tự viết một hàm fitness riêng. Có nhiều cách để định nghĩa hàm fitness khác nhau cho bài toán này. Ở đay, chúng ta sẽ xây dựng một hàm có input là vị trí của các con hậu output là một con số thông báo số lượng con hậu không giáp nhau. Nếu số lượng là 8 thì input chính là lời giải của bài toán.

 1# Define alternative N-Queens fitness function for maximization problem
 2def queens_max(state):
 3
 4    # Initialize counter
 5    fitness = 0
 6
 7    # For all pairs of queens
 8    for i in range(len(state) - 1):
 9        for j in range(i + 1, len(state)):
10
11            # Check for horizontal, diagonal-up and diagonal-down attacks
12            if (state[j] == state[i]) \
13                or (state[j] == state[i] + (j - i)) \
14                or (state[j] == state[i] - (j - i)):
15
16                # If no attacks, then increment counter
17                fitness += 1
18                break
19
20
21    return fitness
22
23fitness_cust = mlrose.CustomFitness(queens_max)

Xác định loại bài toán

Thư viện mlrose cung cấp cho chúng ta các lớp để định nghĩa 3 loại bài toán tối ưu:

• DiscreteOpt: Lớp này được sử dụng để giải các bài toán có giá trị trạng thái là rời rạc. Và tập các trạng thái sẽ được cung cấp trước. Mỗi phần tử trong state chỉ nhận một giá trị trong tập trạng thái. và mỗi phần tử trong tập trạng thái chỉ thuộc về một phần tử trong state.

• ContinuousOpt: Lớp này được sử dụng để giải các bài toán có giá trị trạng thái là liên tục.

• TSPOpt: Lớp này được dùng để giải các bài toán về travelling. Ví dụ bài toán người giao hàng. Bài toán này khác bài toán Discrete ở chỗ chúng ta sẽ phải tìm ra thứ tự tối ưu của các con số.

Bài toán 8 hậu được xếp vào dạng bài toán tối ưu rời rạc. Trong đó, mỗi phần tử trong state vector chỉ mang một con số từ 0 đến 7.

1
2problem = mlrose.DiscreteOpt(length = 8, fitness_fn = fitness,
3                             maximize = False, max_val = 8)

length chính là số lượng phần tử trong state vector ( chúng ta có 8 cột nên length = 8), max_val = 8 (đã nói ở trên, giá trị tối ưu là khi 8 con hậu không giáp mặt nhau). Do bài toán của mình là cực tiểu (lý do là fitness = 0 thì không có con hậu nào giáp mặt nhau, nên chúng ta set maximize = False)

Xác định thuật toán tối ưu

Thư viện mlrose cung cấp cho chúng ta các thuật toán như leo đồi (hill climbing), leo đồi ngẫu nhiên (stochastic hill climbing),simulated annealing, thuật giải di truyền (genetic algorithm), MIMIC (Mutual-Information-Maximizing Input Clustering). Với dạng bài toán rời rạc và travelling, chúng ta có thể chọn bất kỳ thuật toán tối ưu nào. Với bài toán liên tục, thì thuật toán MIMIC không hỗ trợ.

Ví dụ, chúng ta sẽ sử dụng simulated annealing để mô phỏng hàm tối ưu, với trạng thái init là x = [1,2,3,4,5,6,7], lặp 1000 lần để tìm trạng thái tốt nhất. Có 10 lần thử. để tìm hàng xóm tốt nhất trong mỗi lần lặp.

 1# Define decay schedule
 2schedule = mlrose.ExpDecay()
 3
 4# Define initial state
 5init_state = np.array([0, 1, 2, 3, 4, 5, 6, 7])
 6
 7# Set random seed
 8np.random.seed(1)
 9
10# Solve problem using simulated annealing
11best_state, best_fitness = mlrose.simulated_annealing(problem, schedule = schedule,
12                                                      max_attempts = 10, max_iters = 1000,
13                                                      init_state = init_state)
14
15print('The best state found is: ', best_state)
16print('The fitness at the best state is: ', best_fitness)

Kết quả

1The best state found is:  [0 7 6 4 7 1 3 5]
2The fitness at the best state is:  1.0

Do best state =1 , nên có 2 con hậu có thể nhìn thấy và tấn công nhau, Chúng ta sẽ thử thay dổi số max_attempts =10 thành max_attempts = 50 xem sao.

1
2The best state found is:  [2 0 6 4 7 1 3 5]
3The fitness at the best state is:  0.0

Thử thay bằng bài toán 12 hậu

 1import mlrose
 2
 3import numpy as np
 4
 5# Define alternative N-Queens fitness function for maximization problem
 6def queens_max(state):
 7
 8    # Initialize counter
 9    fitness = 0
10
11    # For all pairs of queens
12    for i in range(len(state) - 1):
13        for j in range(i + 1, len(state)):
14
15            # Check for horizontal, diagonal-up and diagonal-down attacks
16            if (state[j] == state[i]) \
17                or (state[j] == state[i] + (j - i)) \
18                or (state[j] == state[i] - (j - i)):
19
20                # If no attacks, then increment counter
21                fitness += 1
22                break
23
24
25    return fitness
26
27fitness_cust = mlrose.CustomFitness(queens_max)
28
29problem = mlrose.DiscreteOpt(length = 12, fitness_fn = fitness_cust, maximize = False, max_val = 12)
30
31
32# Define decay schedule
33schedule = mlrose.ExpDecay()
34
35# Define initial state
36init_state = np.array([0, 1, 2, 3, 4, 5, 6, 7,8,9,10,11])
37
38# Set random seed
39np.random.seed(1)
40
41# Solve problem using simulated annealing
42best_state, best_fitness = mlrose.simulated_annealing(problem, schedule = schedule,
43                                                      max_attempts = 100, max_iters = 5000,
44                                                      init_state = init_state)
45
46print('The best state found is: ', best_state)
47print('The fitness at the best state is: ', best_fitness)
48``
49
50Kết quả
51
52```python
53The best state found is:  [ 8 10  3  6  0  9  1  5  2 11  7  4]
54The fitness at the best state is:  0.0

Tất nhiên, ở trên chỉ là 1 trong số các lời giải của bài toán trên, chúng ta còn có nhiều lời giải khác, do bài toán có nhiều nghiệm.

Cảm ơn các bạn đã theo dõi. Hẹn gặp bạn ở các bài viết tiếp theo.