AI không phải 'phao cứu sinh': Đây là cách sinh viên dùng AI để học giỏi hơn!

Kỷ nguyên học tập mới với AI

Trong năm 2024, trí tuệ nhân tạo (AI) đã nhanh chóng chuyển từ một khái niệm tương lai thành một phần không thể thiếu trong cuộc sống hàng ngày của chúng ta, và giáo dục cũng không ngoại lệ. Các công cụ AI tạo sinh (Generative AI), như ChatGPT, đang mở ra một thế giới mới cho sinh viên, mang đến những cơ hội chưa từng có để nâng cao việc học tập. Tuy nhiên, điều cốt yếu là phải hiểu rằng sử dụng AI trong học tập là để học tập thông minh hơn, chứ không phải vất vả hơn—đó là tận dụng các công cụ mạnh mẽ này như một "người bạn đồng hành trong học tập" chứ không phải là một lối tắt hay một "phao cứu sinh" để tránh nỗ lực thực sự. Hướng dẫn này sẽ chỉ cho bạn cách học bằng AI hiệu quả, đảm bảo bạn khai thác sức mạnh của nó một cách có trách nhiệm.

AI không phải 'phao cứu sinh': Đây là cách sinh viên dùng AI để học giỏi hơn!

Cách dùng AI hiệu quả để học tập thông minh hơn

Các công cụ AI có thể cách mạng hóa thói quen học tập của bạn, nhưng chìa khóa là sự tích hợp có chủ ý và chiến lược. Dưới đây là cách bạn có thể biến AI thành trợ lý học tập giá trị nhất của mình:

• Tóm tắt tài liệu, sách báo: Bạn có bao giờ cảm thấy choáng ngợp bởi những cuốn sách giáo khoa dài, bài báo học thuật hoặc các bài giảng video dài dòng không? AI có thể giúp ích. Các công cụ như ChatGPT, QuillBot và NotebookLM có thể tóm tắt lượng lớn thông tin thành các điểm chính và bản tóm tắt chi tiết, giúp bạn tiết kiệm thời gian và nắm bắt các khái niệm cần thiết nhanh hơn. Bạn thậm chí có thể nhập ghi chú bài giảng hoặc các chương sách giáo khoa của mình vào một công cụ AI để tạo các câu hỏi luyện tập và thẻ ghi nhớ phù hợp với tài liệu của bạn. Các công cụ khác như Quizlet, Anki có thể tạo thẻ ghi nhớ, trong khi Otter.ai có thể phiên âm và sắp xếp các bài giảng thành văn bản viết. Notion cũng là một công cụ linh hoạt để ghi chú và quản lý dự án. Một số ứng dụng còn có thể chuyển đổi PDF và bản trình bày thành âm thanh để bạn nghe khi di chuyển.

• Tạo dàn ý, sơ đồ tư duy: Bắt đầu một bài tập hoặc bài nghiên cứu có thể rất đáng sợ. Các công cụ AI có thể đóng vai trò là đối tác động não của bạn, giúp bạn tạo dàn ý có cấu trúc, gợi ý thảo luận và thậm chí là sơ đồ tư duy cho các chủ đề khác nhau. Điều này có thể giúp bạn vượt qua tình trạng bí ý và tổ chức suy nghĩ một cách hiệu quả, cung cấp nền tảng vững chắc cho công việc của bạn.

• Hỗ trợ học ngôn ngữ mới: Học một ngôn ngữ mới ư? Các ứng dụng học ngôn ngữ được hỗ trợ bởi AI đang làm cho việc đó dễ dàng hơn bao giờ hết. Các nền tảng như Duolingo, Babbel và Memrise sử dụng thuật toán thích ứng để cá nhân hóa trải nghiệm học tập của bạn, cung cấp dịch thuật theo thời gian thực, phản hồi về phát âm và sửa lỗi ngữ pháp. Bạn thậm chí có thể thực hành kỹ năng hội thoại với hình đại diện AI hoặc chatbot, chúng cung cấp phản hồi tức thì và điều chỉnh theo tiến độ của bạn. Một số công cụ AI khác cũng được nhắc đến như Speak, Practica, TalkPal, Univerbal, Torly, Lingvist, Lura, Mondly, Eggbun Education, Pimsleur, và Drops.

• Kiểm tra ngữ pháp, chính tả: Đối với các bài luận và báo cáo, các công cụ AI như Grammarly có thể vô cùng hữu ích. Chúng cung cấp phản hồi tức thì và chi tiết về bài viết của bạn, đề xuất cải thiện ngữ pháp, chính tả, độ rõ ràng và mạch lạc. Quá trình lặp lại này cho phép bạn tinh chỉnh bài làm của mình trước khi nộp, nâng cao đáng kể kết quả học tập và kỹ năng viết của bạn.

Cảnh báo sai lầm khi sử dụng AI

Mặc dù những lợi ích rất rõ ràng, nhưng việc nhận thức được những cạm bẫy cũng quan trọng không kém. Tránh những lỗi phổ biến này sẽ đảm bảo hành trình sử dụng AI trong học tập của bạn hiệu quả và có đạo đức:

• Lạm dụng, phụ thuộc quá mức: AI là một công cụ bổ trợ cho việc học tập của bạn, chứ không phải thay thế nó. Việc phụ thuộc quá nhiều vào AI có thể cản trở sự phát triển tư duy phản biện, kỹ năng giải quyết vấn đề và tư duy độc lập của bạn. Hãy luôn tương tác trực tiếp với tài liệu, sử dụng AI để hỗ trợ và nhớ rằng việc học thực sự đến từ nỗ lực của chính bạn.

• Đạo văn: Đây là một mối lo ngại lớn đối với các nhà giáo dục. Việc nộp bài làm hoàn toàn do AI tạo ra, hoặc sử dụng AI để tinh chỉnh nội dung mà không có sự thừa nhận hoặc chỉnh sửa phù hợp, được coi là đạo văn. Nhiều tổ chức đã cập nhật chính sách liêm chính học thuật của họ để giải quyết việc sử dụng AI, và các công cụ phát hiện AI đang trở nên phổ biến hơn. Tuy nhiên, các công cụ phát hiện AI có thể không đáng tin cậy và thiên vị đối với những người viết không phải là người bản xứ tiếng Anh. Luôn trích dẫn bất kỳ đóng góp nào của AI theo hướng dẫn của tổ chức của bạn, và đảm bảo công việc bạn nộp thực sự phản ánh sự hiểu biết và nỗ lực của chính bạn.

• Giảm tư duy độc lập và đánh giá phê phán: Các mô hình AI được đào tạo trên lượng lớn dữ liệu và tạo ra phản hồi dựa trên xác suất; chúng không có tư duy độc lập hay đảm bảo độ chính xác. AI có thể "tạo ra thông tin sai lệch" hoặc tạo ra thông tin sai lệch, gây hiểu lầm hoặc bịa đặt, còn được gọi là "ảo giác" (hallucination). Các mô hình AI cũng có thể chứa đựng thành kiến do dữ liệu mà chúng được đào tạo mang tính lịch sử và văn hóa cụ thể. Do đó, điều cần thiết là phải đánh giá phê phán các đầu ra của AI, đối chiếu thông tin với các nguồn đáng tin cậy, và áp dụng phán đoán của riêng bạn. Đừng chỉ chấp nhận nội dung do AI tạo ra một cách mặc nhiên. Sinh viên cần được hướng dẫn về cách đánh giá tính hợp lệ, mục đích và đạo đức của thông tin mà họ gặp phải.

Sử dụng AI có trách nhiệm cho một tương lai học thuật tươi sáng hơn

AI sẽ tồn tại và vai trò của nó trong giáo dục sẽ tiếp tục phát triển. Bằng cách áp dụng cách học bằng AI hiệu quả, bạn có thể cá nhân hóa việc học của mình, hợp lý hóa các tác vụ hành chính và thu được những hiểu biết sâu sắc hơn về các môn học. Tuy nhiên, sức mạnh thực sự của AI trong giáo dục nằm ở việc áp dụng nó một cách có trách nhiệm, đạo đức và sáng tạo.

Mục tiêu không phải là loại bỏ việc sử dụng AI, mà là nuôi dưỡng một cách tiếp cận cân bằng nhằm nâng cao, chứ không phải thay thế, trí tuệ và nỗ lực của con người. Vì vậy, hãy mạnh dạn khám phá tiềm năng to lớn của AI như người bạn đồng hành trong học tập của bạn—nhưng hãy luôn nhớ ưu tiên tư duy phản biện của chính bạn, duy trì tính liêm chính trong học thuật và sử dụng AI như một công cụ để khuếch đại việc học của bạn, chứ không phải để làm suy yếu nó. Thành công học tập của bạn trong tương lai sẽ đến từ đó!

Bạn có thể kiếm thêm thu nhập một cách tự động mà không phải đầu tư, không mất thời gian ? Điều đó có thể không ? điều đó có an toàn không? Xem thêm tại đây 

Xem thêm các bài viết khác về AI tại đây 

Read More

ML 1 _ Tổng quan về Machine Learning (Học máy)

Tổng quan về Machine Learning (Học máy)

Thời gian gần đây, Trí tuệ nhân tạo (AI) hay cụ thể hơn là Machine Learning (ML) được nhắc tới như là phần cốt lõi của các hệ thống thông minh. Rất nhiều những sản phẩm, giải pháp công nghệ được ứng dụng AI, có thể kể đến một số sản phẩm tiêu biểu đã làm thay đổi cách nhìn về AI nói chung và Machine learning nói riêng như:
 - Xe tự hành của Google và Tesla, 

 - Hệ thống tự tag khuôn mặt trong ảnh của Facebook, 

 - Trợ lý ảo Siri của Apple, 

 - Hệ thống gợi ý sản phẩm của Amazon, 

 - Hệ thống gợi ý phim của Netflix, 

 - Máy chơi cờ vây AlphaGo, AlphaGo Zero của Google DeepMind, …, 

 -  Jarvis - trợ lý thông minh cho căn nhà của Mark Zuckerberg
 ... ngoài ra, còn vô số các ứng dụng khác trong các sản phẩn tích hợp. [1]

Theo định nghĩa của Wikipedia, Machine learning is the subfield of computer science that “gives computers the ability to learn without being explicitly programmed”. Nói đơn giản, Machine Learning là một lĩnh vực nhỏ của Khoa Học Máy Tính, nó có khả năng tự học hỏi dựa trên dữ liệu đưa vào mà không cần phải được lập trình cụ thể.

Qua các lịch sử phát triển và các lĩnh vực phát triển, có thể hiểu machine learning là  "tập con" của AI. Xuất phát từ thực tiễn, nhu cầu tính toán, phân tích trên dữ liệu có kích thước lớn (big data) ngày càng cao, cộng với sự phát triển nhanh chóng của công nghệ phần cứng dẫn tới hiệu năng tính toán của máy tính ngày càng cao.  Điều này đã thúc đầy machine learning tiến thêm một bước đột phá mới gọi là Deep learning (tạm hiểu là học sâu). Với bước tiến nhảy vọt này, máy tính đã có thể giải quyết được những bài toán và trước đó tưởng trừng như không thể như: phân loại cả ngàn vật thể khác nhau trong các bức ảnh, tự tạo chú thích cho ảnh, bắt chước giọng nói và chữ viết của con người, giao tiếp với con người, hay thậm chí cả sáng tác văn hay âm nhạc (Xem thêm 8 Inspirational Applications of Deep Learning) [1]

Mối quan hệ giữa AI, Machine Learning và Deep Learning.

(Nguồn: What’s the Difference Between Artificial Intelligence, Machine Learning, and Deep Learning?)

Trong bối cảnh đó, tại Việt Nam những nghiên cứu và ứng dụng AI hay Machine learning còn khá khiêm tốn, chưa kể đến việc đào tạo nguồn nhân lực chất lượng cao cho lĩnh vực này còn thiếu và yếu. Đây thực sự là cơ hội và thách thức không nhỏ đối với các cơ sở đào tạo. Rất mong các bạn sinh viên, đặc biệt là các bạn sinh viên CNTT quan tâm nghiên cứu sâu về lĩnh vực này - một lĩnh vực cốt lõi của cuộc cách mạng 4.0.

#

Tham khảo:

[1]  Bài 1: Giới thiệu về Machine Learning - Blog: machinelearningcoban.com - Truy cập: 22.10.19 

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

Read More

Thuật toán A* tìm đường đi ngắn nhất trong đồ thị [ Cùng học AI ]

Thuật toán A* (A-star) là một thuật toán tìm đường sử dụng trong các lĩnh vực như trí tuệ nhân tạo, đồ họa máy tính, và robot học. Nó được sử dụng để tìm đường đi ngắn nhất từ điểm khởi đầu đến điểm đích trên một đồ thị. 

Thuật toán A* kết hợp hai yếu tố chính:

1. Giá trị chi phí đi từ điểm khởi đầu đến điểm hiện tại (g(n)).

2. Ước lượng chi phí từ điểm hiện tại đến đích (h(n)), còn gọi là hàm heuristic.

Tổng chi phí của một nút n được tính bằng công thức: 

 f(n) = g(n) + h(n)

Trong đó:

-  g(n) là chi phí từ điểm khởi đầu đến nút n.

-  h(n) là chi phí ước lượng từ nút n đến đích (hàm heuristic).

Thuật toán A* hoạt động bằng cách khám phá các nút với giá trị f(n) nhỏ nhất trước, đảm bảo rằng nó tìm ra con đường ngắn nhất nếu hàm heuristic h(n) là admissible (không bao giờ đánh giá quá cao chi phí từ n đến đích).

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

### Sơ đồ thuật toán A*

1. Khởi tạo:

   - Tạo danh sách mở (open list) và thêm nút bắt đầu vào danh sách này. Khởi tạo danh sách đóng (closed list) rỗng.

   - Đặt giá trị g(n) của nút bắt đầu là 0 và f(n) = g(n) + h(n).

2. Lặp lại các bước sau cho đến khi danh sách mở trống hoặc tìm thấy điểm đích:

   - Chọn nút có giá trị f(n) nhỏ nhất trong danh sách mở và gán nó là nút hiện tại.

   - Nếu nút hiện tại là đích, tái tạo đường đi từ điểm khởi đầu đến điểm đích và kết thúc.

   - Di chuyển nút hiện tại từ danh sách mở sang danh sách đóng.

   - Đối với mỗi hàng xóm của nút hiện tại:

     + Nếu hàng xóm nằm trong danh sách đóng, bỏ qua nó.

     + Nếu hàng xóm không nằm trong danh sách mở, thêm nó vào danh sách mở và tính các giá trị g(n), h(n), và f(n).

     + Nếu hàng xóm đã nằm trong danh sách mở, kiểm tra xem đường đi hiện tại đến hàng xóm có tốt hơn không. Nếu có, cập nhật giá trị g(n), h(n) và f(n) của hàng xóm và cập nhật nút cha.

3. Kết thúc:

   - Nếu danh sách mở trống và điểm đích không được tìm thấy, báo rằng không có đường đi.

### Mô tả step-by-step các bước

1. Initialization (Khởi tạo):

   - Đặt nút bắt đầu (start) vào danh sách mở (open list).

   - Thiết lập g_score của nút bắt đầu là 0.

   - Tính toán f_score của nút bắt đầu bằng cách cộng g_score và heuristic (h(n)).

2. Loop until the open list is empty or the destination is found (Lặp lại cho đến khi danh sách mở trống hoặc tìm thấy đích):

   - Step 1: Chọn nút có giá trị f(n) nhỏ nhất trong danh sách mở (gọi là nút hiện tại).

   - Step 2: Nếu nút hiện tại là điểm đích, tái tạo và trả về đường đi.

   - Step 3: Di chuyển nút hiện tại từ danh sách mở sang danh sách đóng.

   - Step 4: Đối với mỗi hàng xóm của nút hiện tại:

     + Step 4.1: Nếu hàng xóm nằm trong danh sách đóng, bỏ qua nó.

     + Step 4.2: Tính g_score tạm thời (tentative_g_score) cho hàng xóm.

     + Step 4.3: Nếu hàng xóm không nằm trong danh sách mở hoặc tentative_g_score nhỏ hơn g_score hiện tại của hàng xóm:

        Cập nhật nút cha của hàng xóm là nút hiện tại.

        Cập nhật g_score và f_score của hàng xóm.

        Nếu hàng xóm không nằm trong danh sách mở, thêm nó vào danh sách mở.

3. ermination (Kết thúc):

   - Nếu danh sách mở trống và điểm đích không được tìm thấy, báo rằng không có đường đi.

### Ví dụ cụ thể

Giả sử chúng ta có một đồ thị đơn giản:

- Bắt đầu tại A, cần tìm đường ngắn nhất đến F.

- Hàm heuristic sử dụng khoảng cách Manhattan.

**Step-by-step:**

1. Initialization:

   - Đặt A vào danh sách mở. g(A) = 0, h(A) = heuristic(A, F), f(A) = g(A) + h(A).

2. Loop:

   Iteration 1:

   - Chọn A (f(A) = 0 + h(A)).

   - Di chuyển A từ danh sách mở sang danh sách đóng.

   - Xem xét các hàng xóm của A: B, C.

     + Với B: tentative_g(B) = g(A) + 1 = 1. Đặt g(B) = 1, h(B), f(B) = g(B) + h(B).

     + Với C: tentative_g(C) = g(A) + 4 = 4. Đặt g(C) = 4, h(C), f(C) = g(C) + h(C).

   - Thêm B và C vào danh sách mở.

   Iteration 2:

   - Chọn B (vì f(B) nhỏ hơn f(C)).

   - Di chuyển B từ danh sách mở sang danh sách đóng.

   - Xem xét các hàng xóm của B: A, D, E.

     + Với D: tentative_g(D) = g(B) + 2 = 3. Đặt g(D) = 3, h(D), f(D) = g(D) + h(D).

     + Với E: tentative_g(E) = g(B) + 5 = 6. Đặt g(E) = 6, h(E), f(E) = g(E) + h(E).

   - Thêm D và E vào danh sách mở.

   Iteration 3:

   - Chọn D (f(D) nhỏ hơn f(C) và f(E)).

   - Di chuyển D từ danh sách mở sang danh sách đóng.

   - Xem xét các hàng xóm của D: B, E, F.

     + Với F: tentative_g(F) = g(D) + 1 = 4. Đặt g(F) = 4, h(F) = 0, f(F) = g(F) + h(F).

   - Thêm F vào danh sách mở.

   Iteration 4:

   - Chọn F (f(F) nhỏ nhất).

   - F là điểm đích, tái tạo và trả về đường đi: A -> B -> D -> F.

Vậy, đường đi ngắn nhất từ A đến F là A -> B -> D -> F.

Dưới đây là một ví dụ chương trình ứng dụng của thuật toán A* với Python:

'''python'''

import heapq

def heuristic(a, b):

    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star(graph, start, end):

    open_list = []

    heapq.heappush(open_list, (0, start))

    came_from = {}

    g_score = {node: float('inf') for node in graph}

    g_score[start] = 0

    f_score = {node: float('inf') for node in graph}

    f_score[start] = heuristic(start, end)

    while open_list:

        current = heapq.heappop(open_list)[1]

        if current == end:

            path = []

            while current in came_from:

                path.append(current)

                current = came_from[current]

            path.append(start)

            return path[::-1]

        for neighbor in graph[current]:

            tentative_g_score = g_score[current] + graph[current][neighbor]

            if tentative_g_score < g_score[neighbor]:

                came_from[neighbor] = current

                g_score[neighbor] = tentative_g_score

                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, end)

                heapq.heappush(open_list, (f_score[neighbor], neighbor))

    return None

# Ví dụ đồ thị (graph) với chi phí giữa các điểm

graph = {

    'A': {'B': 1, 'C': 4},

    'B': {'A': 1, 'D': 2, 'E': 5},

    'C': {'A': 4, 'F': 3},

    'D': {'B': 2, 'E': 1},

    'E': {'B': 5, 'D': 1, 'F': 1},

    'F': {'C': 3, 'E': 1}

}

start = 'A'

end = 'F'

path = a_star(graph, start, end)

print(f"Đường đi ngắn nhất từ {start} đến {end} là: {path}")

```

### Giải thích chương trình:

1. Heuristic function: Hàm heuristic được định nghĩa để tính khoảng cách Manhattan giữa hai điểm.

2. A* function: Hàm `a_star` thực hiện thuật toán A*.

   - open_list: Danh sách mở chứa các nút cần được khám phá. Các nút được sắp xếp theo giá trị `f(n)`.

   - came_from: Từ điển lưu trữ các nút và nút cha của chúng để tái tạo đường đi ngắn nhất.

   - g_score: Từ điển lưu trữ chi phí từ điểm khởi đầu đến mỗi nút.

   - f_score: Từ điển lưu trữ giá trị `f(n)` cho mỗi nút.

3. Main loop: Vòng lặp chính khám phá các nút với giá trị `f(n)` nhỏ nhất trước.

4. Reconstruction: Khi điểm đích được tìm thấy, hàm sẽ tái tạo lại đường đi ngắn nhất bằng cách đi ngược từ điểm đích đến điểm khởi đầu thông qua `came_from`.

Chương trình này sẽ in ra đường đi ngắn nhất từ điểm bắt đầu 'A' đến điểm kết thúc 'F'.

Read More

Giải thuật tiến hóa - thuật toán di truyền

Giải thuật tiến hóa - thuật toán di truyền

Giải thuật tiến hóa - thuật toán di truyền

Nội dung:

1. Giải thuật tiến hóa

2. Thuật toán di truyền

3. Các quá trình cơ bản trong thuật toán di truyền

4. Các tham số của thuật toán di truyền

5. Cài đặt giải thuật di truyền

--------------------------------

1. Giải thuật tiến hóa

Giải thuật tiến hóa (Evolutionary Computations - EC) bao gồm: thuật toán di truyền (Genetic Algorithm - GA), thuật toán tiến hóa vi phân (Differential Evolution- DE), qui hoạch tiến hóa (Evolutionary programming - EP) và chiến lược tiến hóa (Evolution Strategies - ES) dựa trên nền tảng tiến hóa tự nhiên đó cũng là các phương pháp tự nhiên nhằm giải quyết bài toán tối ưu và tìm kiếm. Mục tiêu cơ bản của EC là cơ cấu tính toán nhằm tạo ra sự tiến hóa của quần thể gồm nhiều cá thể với mục đích quần thể sau “tốt hơn” quần thể trước. Các toán tử sử dụng trong EC bao gồm: lai ghép (crossover), đột biến (mutation) và chọn lọc (selection). Các toán tử này kết hợp với nhau trong một mô hình tiến hóa và được điều khiển bởi một vài tham số như kích cỡ quần thể, xác suất lai ghép, xác suất đột biến... Hình thức sử dụng rộng rãi EC là thuật toán di truyền (GA).

2. Thuật toán di truyền

Giống như giải thuật tiến hóa nói chung, thuật toán di truyền (GA) hình thành dựa trên quan niệm cho rằng quá trình tiến hóa tự nhiên là quá trình hoàn hảo và hợp lý nhất và tự nó đã mang tính tối ưu. Đây là một tiên đề đúng, không thể chứng minh được nhưng phù hợp với thực tế khách quan. Tính tối ưu trong tự nhiên thể hiện ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước nhờ hai quá trình cơ bản là sinh sản và chọn lọc tự nhiên. Những cá thể nào phát triển thích nghi với môi trường sẽ tồn tại và ngược lại, những cá thể nào không thích nghi với môi trường sẽ bị đào thải. Sự thay đổi của môi trường sẽ tác động đến quá trình tiến hóa và bản thân quá trình tiến hóa cũng có tác động và làm thay đổi môi trường. Cá thể mới sinh ra trong quá trình tiến hóa nhờ vào sự lai ghép ở thế hệ cha mẹ. Một cá thể mới có thể mang những đặc tính của cha mẹ ở thế hệ trước (di truyền) hoặc mang những đặc tính mới hoàn toàn (đột biến). Di truyền và đột biến là hai cơ chế quan trọng như nhau trong quá trình tiến hóa mặc dù xác suất để xảy ra hiện tượng đột biến nhỏ nhiều (hàng chục đến
hàng trăm lần tùy từng quá trình) so với hiện tượng di truyền. Mặc dù cơ chế là ngẫu nhiên nhưng thuật toán di truyền không phải là một thuật toán ngẫu nhiên. Thuật toán khai thác và tận dụng được một cách hiệu quả thông tin quá khứ để có được những kết quả mới đạt kết quả như mong muốn. Các cải tiến trong việc sử dụng thuật toán
di truyền đã làm tăng thêm hiệu quả của việc sử dụng thuật toán trong các bài toán phức tạp. Điều này thể hiện ở việc giảm thời gian tính toán ngày càng hiệu quả mà ta sẽ tìm hiểu cụ thể hơn ở dưới đây.

3. Các quá trình cơ bản trong thuật toán di truyền

a) Mã hóa dữ liệu: hay còn gọi là biểu diễn di truyền cho lời giải của bài toán: Đây là bước đầu tiên và rất quan trọng đối với việc tìm ra lời giải của bài toán. Mỗi lời giải của bài toán được biểu diễn dưới dạng một chuỗi ký tự hữu hạn hay còn được gọi là một nhiễm sắc thể. Các ký tự có thể là số nhị phân, số thập phân, … tùy vào từng bài toán cụ thể. Trong quá trình này, việc mã hóa cái gì, mã hóa như thế nào, trật tự các thành phần trong nhiễm sắc thể ra sao,… luôn là những thách thức cho những người giải bài toán.

b) Khởi tạo quần thể (xây dựng tập hợp nghiệm ban đầu): có thể ngẫu nhiên hoặc không ngẫu nhiên: Có nhiều cách để khởi tạo giá trị quần thể nghiệm ban đầu, tùy từng bài toán mà ta lựa chọn phương pháp phù hợp. Thông thường, hệ nghiệm ban đầu được chọn ngẫu nhiên trong không gian tìm kiếm. Tuy vậy, việc chọn này cũng cần phải xem xét về tương quan giữa độ thích nghi của các nhiễm sắc thể để tránh tình trạng nghiệm tìm ra là nghiệm tối ưu cục bộ hay còn gọi là cực trị địa phương. Còn vấn đề số lượng nghiệm của tập nghiệm hay qui mô của quần thể cũng cần được xem xét kỹ dựa vào độ phức tạp của bài toán, độ chính xác yêu cầu (cao hay thấp) và thời gian tính toán yêu cầu (nhanh hay chậm)

c) Xác định hàm thích nghi: hay hàm lượng giá cho mỗi nhiễm sắc thể hay chính là cho các phương án nghiệm trong tập nghiệm. Hàm này dùng để đánh giá độ thích nghi của các nhiễm sắc thể. Hàm thích nghi cần phải đánh giá được mức độ thích nghi cho tất cả các nghiệm khả thi và luôn được giả định là không âm, để thể hiện độ thích nghi của các cá thể. Công thức biểu diễn hàm cần phải thể hiện được tất cả các đặc tính mong muốn của nhiễm sắc thể, thông qua đó có thể chọn lọc được các quần thể nghiệm tốt nhất cho bài toán.

d) Quá trình lai ghép: đây là quá trình nhiễm sắc thể mới được hình thành dựa trên nhiễm sắc thể cha mẹ bằng cách lai ghép một hay nhiều đoạn nhiễm sắc thể cha mẹ với nhau. Phép lai ghép xảy ra với xác suất là p1 có thể được mô phỏng như sau:
- Chọn hai (hay nhiều) cá thể bất kỳ trong quần thể. Quần thể ở đây bao gồm các nhiễm sắc thể (cha mẹ) có độ dài bằng nhau.
- Chọn điểm lai là một điểm có vị trí bất kỳ (như nhau) trên nhiễm sắc thể chamẹ và thực hiện hoán đổi các đoạn gen của nhiễm sắc thể cha mẹ tại điểm lai này.
- Đưa hai cá thể này vào quần thể để thực hiện vào các quá trình tiến hóa tiếp theo.

Hình 1.  Lai ghép hai cá thể

Tuy nhiên trong quá trình tồn tại và phát triển, thuật toán di truyền đã được bổ sung rất nhiều các phương pháp lai ghép để nhằm thích ứng với nhiều kiểu bài toán và cũng là để tăng hiệu quả của thuật toán. Có thể kể một số phép lai cải tiến như sau:
- Lai ghép có xét tới các đặc tính trội và lặn trong tự nhiên: Các đặc tính này được quy định trước trong khi biểu diễn cấu trúc nhiễm sắc thể. Bằng việc xem xét tới các đặc tính trội lặn, quá trình sản sinh ra các "quần thể chất lượng tốt" sẽ nhanh hơn và do đó thời gian tính toán cũng được rút ngắn.
- Lai ghép từng phần: Việc giữ lại những đoạn mã đã "tối ưu" trong nhiễm sắc thể cũng là một cách để quá trình lai ghép trở nên hiệu quả hơn
- Lai ghép có trật tự
- Lai ghép dựa trên vị trí
- Lai ghép chu trình
- Lai ghép thứ tự tuyến tính
- Lai ghép đa điểm: Với phương pháp này, chúng ta có thể cho 2 cá thể lai ghép ở 2 hay nhiều điểm lai ghép. Phương thức này làm cho thuật toán trở nên linh hoạt hơn, nhờ đó các thế hệ cá thể con cũng sẽ có chất lượng tốt hơn.

e) Quá trình đột biến: là quá trình cá thể con mang một hay một số tính trạng không có trong mã di truyền của cha mẹ. Quá trình này xảy ra với xác suất p2 (nhỏ hơn nhiều so với p1) có thể được mô tả như sau:
- Chọn ngẫu nhiên một cá thể bất kỳ trong quần thể
- Chọn một gen bất kỳ của cá thể vừa chọn
- Thay đổi giá trị gen đó (đối với cách mã hóa gen theo số nhị phân thì quá trình thay đổi giá trị là đổi giá trị từ 0 thành 1 hoặc từ 1 thành 0) rồi trả về quần thể để thực hiện các quá trình tiếp theo

Hình 2. Đột biến một nhiễm sắc thể

Tương tự như quá trình lai ghép, trong quá trình phát triển của thuật toán di truyền cũng đã được bổ sung rất nhiều cách thức để thực hiện quá trình gây đột biến ngày càng hiệu quả hơn:
- Đột biến đảo ngược (Inversion Mutation)
- Đột biến chèn (Insertion Mutation)
- Đột biến thay thế (Raplacement Mutation)
- Đột biến tương hỗ (Reciprocal Exchange Mutation)
- Đột biến dịch chuyển (Shift Mutation)

f) Quá trình chọn lọc: Quá trình mà các cá thể mới sinh ra được giữ lại hay bị loại bỏ khỏi quần thể dựa vào độ thích nghi của chúng. Độ thích nghi ở đây thường là một hàm gán một giá trị thực cho các cá thể trong quần thể. Đối với quá trình này có rất nhiều cách để xác định trình tự tính toán và thực hiện tùy vào cách lựa chọn độ thích nghi của cá thể nói riêng và của cả quần thể nói chung.

4. Các tham số của thuật toán di truyền

Kích cỡ hệ nghiệm (pop-size): số lượng cá thể phù hợp trong mỗi thế hệ Xác suất lai tạo (pc): xác suất để mỗi cá thể trong quần thể được tham gia quá trình lai ghép.

Xác suất đột biến (pm): xác suất để mỗi bit trong nhiễm sắc thể bị đột biến Thông thường, kích cỡ của quần thể phụ thuộc vào độ phức tạp của bài toán.

Bài toán càng phức tạp, nhiều ràng buộc - đơn hoặc đa mục tiêu - thì số lượng cá thể trong mỗi thế hệ càng phải lớn. Hai thông số xác suất trong quá trình di truyền có khoảng giá trị rất khác nhau. Đối với xác suất lai tạo, giá trị thường rơi trong khoảng 0,5 - 0,95 nhưng giá trị thông thường của xác suất đột biến thấp hơn nhiều, chỉ ở khoảng 0,001 - 0,05. Điều này cũng phản ánh đúng xác suất xảy ra hai quá trình trong thực tế.

Ưu điểm của thuật toán di truyền là một phương pháp tìm kiếm từ một quần thể các điểm chứ không phải một điểm. Điều này làm cho việc giải các bài toán đa mục tiêu hay việc tìm một tập hợp các phương án lân cận nghiệm trở nên dễ dàng. Thêm vào đó, việc đánh giá thông tin bằng hàm mục tiêu chứ không dùng đạo hàm hay các tri thức bổ sung cũng là một ưu điểm của thuật toán.

Hình 3. Sơ đồ quá trình tính toán của thuật toán di truyền 

Nhận xét cụ thể các bước trong lưu đồ trên:

- Bước 1: Khởi tạo/lựa chọn các thông số cho quá trình tính toán: Bước này người lập trình tính toán phải lựa chọn các thông số như: số lượng cá thể trong quần thể, cách thức hóa bài toán cần tính toán dưới dạng các nhiễm sắc thể (độ dài của nhiễm sắc thể, kiểu số biểu diễn dữ liệu,…), số thế hệ tính toán, xác suất lai ghép, xác suất đột biến, hàm thích nghi,…

- Bước 2: Khởi tạo quần thể ban đầu: xác định bằng phương pháp tạo số ngẫu nhiên để tạo giá trị cho các nhiễm sắc thể cho quần thể ban đầu. Tùy vào cách biểu diễn của các nhiễm sắc thể mà ta chọn phương pháp tạo số ngẫu nhiên phù hợp

- Bước 3: Đánh giá các nhiễm sắc thể bằng hàm thích nghi đã xác định ở bước
1. Trong bước này, ngoài việc đánh giá các nhiễm sắc thể riêng rẽ, chúng ta còn có thể đánh giá độ thích nghi của một nhiễm sắc thể hay cả quần thể. Nếu một nhóm hay cả quần thể có độ thích nghi "trung bình" (theo tiêu chí của từng trường hợp của người lập trình) thấp thì có thể loại nhóm nhiễm sắc thể hay quần thể đó ra khỏi quá trình di truyền.

- Bước 4: Thực hiện quá trình di truyền thông qua các cơ chế lai ghép và đột biến. Có thể thực hiện lần lượt hai quá trình này hoặc thực hiện đồng thời theo các phương pháp đã đề cập bên trên. Trong quá trình thực hiện thuật toán di truyền, giai đoạn này là giai đoạn mà mỗi người có thể thực hiện theo những phương pháp rất khác nhau. Giai đoạn này cũng là giai đoạn quyết định tới sự thành công của thuật toán. Người thực hiện cũng có thể đưa ra những phương thức tiến hành lai ghép hay đột biến mới trong giai đoạn này. Trong quá trình thực hiện, để có được một bộ các thông số lai ghép hay đột biến hiệu quả, người lập trình thường phải trải qua nhiều bước tính toán thử. Khâu này phụ thuộc nhiều vào kinh nghiệm và kỹ năng tính toán của người lập trình.

- Bước 5: Tạo quần thể mới bằng quá trình chọn lọc. Quá trình này cũng dựa vào đánh giá các nhiễm sắc thể thông qua hàm thích nghi. Cá thể nào có độ thích nghi cao sẽ được giữ lại cho thế hệ kế tiếp. Cũng giống như ở bước 3, chúng ta có thể sử dụng những hàm thích nghi phù hợp để đánh giá từng cá thể đơn lẻ hoặc cả một nhóm các cá thể. Sau quá trình này, nhóm cá thể nào thỏa mã tiêu chuẩn đánh giá với mức độ từ cao xuống thấp sẽ được dưa vào quần thể mới.

- Bước 6: Đánh giá quần thể vừa có được trong bước 5. Thông thường có hai tiêu chí để dừng quá trình di truyền tại bước này. Thứ nhất, độ thích nghi của từng cá thể và cả quần thể thỏa mãn một điều kiện hội tụ đã được đặt ra ban đầu. Các điều kiện hội tụ thể hiện mức độ chấp nhận được của kết quả tìm được. Thứ hai, quần thể mới tạo thành là quần thể ở thế hệ thứ (N+1) với N là số thế hệ dự định tính toán đã giả thiết ban đầu. Trong khi thực hiện các quá trình di truyền, những người tính toán có thể đưa ra những tiêu chí riêng để dừng quá trình di truyền. Các tiêu chí đưa ra góp phần quyết định tới thành công của thuật toán.

5. Cài đặt giải thuật di truyền [Tham khảo tại đây]

 >> Xem thêm phần cài đặt và ứng dụng thuật toán di truyển Tại đây

#

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

Read More

Gợi ý để bắt đầu học lập trình Trí tuệ nhân tạo (AI programming)

6 gợi ý để bắt đầu học lập trình trí tuệ nhân tạo (AI programming)

Trí tuệ nhân tạo hay trí thông minh nhân tạo (Artificial Intelligence hay Machine Intelligence - AI) là một ngành thuộc lĩnh vực khoa học máy tính (Computer Science).

Với xu thế của cuộc cách mạng công nghiệp 4.0 đang bùng nổ, có khá nhiều lập trình mong muốn được học và phát triển năng lực bản thân trong mảng này.

Gợi ý để bắt đầu học lập trình Trí tuệ nhân tạo (AI programming)

Vậy nên bắt đầu thế nào? 

Hãy thử tham khảo 6 bước sau xem sao:

Bước 1: Tìm hiểu về Python và Các hệ quản trị cơ sở dữ liệu (SQL, Oracle,...)

Điều cốt yếu mà bạn phải làm là phải học một ngôn ngữ lập trình. Mặc dù trong thực tế có rất nhiều ngôn ngữ mà bạn có thể bắt đầu, nhưng Python là sự lựa chọn tốt nhất vì các thư viện của nó phù hợp hơn với Machine Learning.


Bạn có thể tham khảo các liên kết dưới đây:

 Machine Learning with Text in scikit-learn (PyCon 2016) 

Machine learning in Python with scikit-learn 

Machine learning with Python 

Machine Learning Part 1 | SciPy 2016 Tutorial 


Bước 2: Học trí tuệ nhân tạo từ một số khóa học dưới đây

Artificial Intelligence: Principles and Techniques from Stanford - Một chương trình giáo dục xuất sắc cho những học giả, những người được truyền cảm hứng bằng cách làm quen nhiều hơn về AI. Khóa học tập trung vào các tiêu chuẩn cơ bản của AI.



CS405: ARTIFICIAL INTELLIGENCE: Giới thiệu lĩnh vực trí tuệ nhân tạo (AI). Các tài liệu về lập trình AI, logic, tìm kiếm, chơi trò chơi, nghiên cứu máy móc, hiểu ngôn ngữ tự nhiên và robot giới thiệu với sinh viên về phương pháp AI, công cụ và kỹ thuật, ứng dụng đối với các vấn đề tính toán và vai trò của AI.



edx.org course on AI: Khóa học này cung cấp các nguyên tắc cơ bản của Artificial Intelligence (AI) và cách áp dụng chúng. Thiết kế các intelligent agent để giải quyết các vấn đề trong thế giới thực bao gồm tìm kiếm, trò chơi, nghiên cứu máy móc, logic và sự hạn chế trong các vấn đề.



MIT’s course on AI: Khóa học này giới thiệu cho sinh viên kiến thức cơ bản, giải quyết vấn đề và phương pháp học tập của trí tuệ nhân tạo. Sau khi hoàn thành khóa học này, sinh viên sẽ có thể phát triển các hệ thống thông minh bằng cách ứng dụng các giải pháp cho các vấn đề tính toán cụ thể; hiểu vai trò của lập trình tri thức, giải quyết vấn đề và học tập trong hệ thống kỹ thuật thông minh. Khóa học đánh giá cao vai trò của việc giải quyết vấn đề, tầm nhìn và ngôn ngữ trong việc hiểu trí tuệ thông minh của con người từ góc độ tính toán.



Learn the Fundamentals of AI - Khóa học trực tuyến này, được chia thành 10 bài học, giúp sinh viên hiểu rõ hơn về vũ trụ AI. Để hiểu nó, hãy đảm bảo bạn có một số thông tin cần thiết về toán học dựa trên biến trực tiếp và giả thuyết khả năng. Bạn nên học cách ghi nhớ mục tiêu cuối cùng để chuẩn bị trước.



Berkeley Video Lecturers: Khóa học bao gồm các bài giảng bằng video.

Trên đây là 6 khóa học về trí tuệ nhân tạo hàng đầu cho người mới bắt đầu và nâng cao. Hy vọng chúng sẽ hữu ích cho bạn.


Bước 3: Tìm hiểu kiến thức cơ bản về lý thuyết xác suất, thống kê và Toán học

Bạn có thể tham khảo các liên kết dưới đây:



Đại số tuyến tính
- Linear Algebra
- MIT 18.06 Đại số tuyến tính của Gilbert Strang 

(Link tham khảo: https://www.youtube.com/watch?list=PLE7DDD91010BC51F8&v=ZK3O402wf1c)



Lý thuyết xác suất và thống kê
- Probability and Statistics
- MIT 6.041

Phân tích hệ số xác suất và xác suất ứng dụng của John Tsitsiklis 

(Link tham khảo: https://www.youtube.com/watch?list=PLUl4u3cNGP61MdtwGTqZA0MreSaDybji8&v=j9WZyLZCBzs)



Calculus (Link tham khảo: http://kisonecat.com/teaching/2013/calculus-one/)



Multivariate Calculus (Link tham khảo: http://kisonecat.com/teaching/2014/m2o2c2/)

Graph theory (Link tham khảo: https://class.coursera.org/pgm-003)



Optimization methods (Link tham khảo: https://online.stanford.edu/courses)

Bước 4: Đọc sách


http://aima.cs.berkeley.edu/



Artificial Intelligence: A Modern Approach, của Stuart J. Russell và Peter Norvig 

http://wps.aw.com/wps/media/objects/5771/5909832/PDF/Luger_0136070477_1.pdf



The Quest for Artificial Intelligence của Nils J. Nilsson

(Link tham khảo: http://ai.stanford.edu/~nilsson/QAI/qai.pdf)



Practical Artificial Intelligence: Programming in Java của Mark Watson 

(Link tham khảo: https://www.saylor.org/site/wp-content/uploads/2011/11/CS405-1.1-WATSON.pdf)


https://grey.colorado.edu/CompCogNeuro/index.php/CCNBook/

Main

Simply Logical: Intelligent Reasoning by Example của Peter Flach

 (Link tham khảo: https://www.cs.bris.ac.uk/~flach/SL/SL.pdf)



The AI Revolution: Road to Superintelligence 

(Link tham khảo: https://waitbutwhy.com/2015/01/artificial-intelligence-revolution-1.html)


http://psych.colorado.edu/~oreilly/comp_ex_cog_neuro.html

Bước 5: Thực hành 

Khi bạn có một sự hiểu biết đầy đủ về ngôn ngữ lập trình ưa thích của mình và thực hành đủ với các yếu tố cần thiết, bạn nên bắt đầu tìm hiểu thêm về Machine Learning.
Trong Python, bắt đầu học các thư viện Scikit-learning, NLTK, SciPy, PyBrain và Numpy sẽ có giá trị trong khi soạn các thuật toán Machine Learning.



Thực hành vài bài tập về Scikit từ trang web:

http://scikit-learn.org/ và https://www.edx.org/course/artificial-intelligence-ai-columbiax-csmm-101x-0 (dành cho các bài tập thực hành bằng Python).



Ngoài ra ở đây là một bản tóm tắt các tài liệu để để tìm hiểu và trau dồi Machine Learning:



http://www.r2d3.us/visual-intro-to-machine-learning-part-1/



https://www.coursera.org/learn/machine-learning



https://www.cs.cmu.edu/~tom/10701_sp11/lectures.shtml



https://code.tutsplus.com/tutorials/how-to-build-a-python-bot-that-can-play-web-games–active-11117



https://www.udacity.com/course/intro-to-artificial-intelligence–cs271



https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/

Bước 6: Thực hành — Học — Tự mình thực hành


Với trình tự này, từng bước một, bạn sẽ từ từ trở thành một lập trình viên AI.



Một khi tất cả 6 bước được thực hiện, bạn đã có thể tự tin để bắt đầu với AI/ML rồi.

Chúc bạn thành công!



#

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

Read More

[Algorithm] Thuật toán leo đồi (Hill Climbing Search)

Giơi thiệu Thuật toán leo đồi (Hill Climbing Search)

Trước hết, ta nghiên cứu bài toán sau: Trò chơi n<sup>2</sup>-1 số (n thuộc N, n > 1).

Bài toán:

 Có n<sup>2</sup>-1 số mang các giá trị từ 1 tới n<sup>2</sup>-1 được sắp xếp vào một lưới các ô vuông kích thước n x n. Mỗi số đó được gọi là một quân cờ và lưới ô đó được gọi là bàn cờ. Có một vị trí của bàn cờ bỏ trống. Mỗi lần di chuyển quân, người chơi được phép chuyển một quân ở vị trí ô tiếp giáp cạnh với ô trống vào ô trống.

Yêu cầu: 

Từ một trạng thái ban đầu (sự sắp xếp ban đầu của các quân trên bàn cờ), hãy thực hiện các nước đi hợp lệ để thu được trạng thái kết thúc (trạng thái đích cần đạt được).

Vídụ: với trò chơi 8 số ta minh họa trạng thái ban đầu và trạng thái kết thúc qua các hình vẽ dưới đây:

Hình 1

Để giải bài toán này, chúng ta sẽ nghĩ ngay tới việc xây dựng một cây tìm kiếm mà gốc của cây tương ứng với trạng thái xuất phát của bàn cờ. Các đỉnh khác của cây tương ứng với các trạng thái thu được do việc thực hiện các nước đi hợp lệ (các nước đi được phép thực hiện là: lên trên, xuống dưới, sang trái và sang phải). Với ví dụ trên, ta có cây tìm kiếm sau:

Hình 2

 Tiếp đó, ta chỉ việc áp dụng các thuật toán thông dụng như: thuật toán tìm kiếm theo chiều rộng hoặc thuật toán tìm kiếm theo chiều sâu để tìm ra lời giải.

Ý tưởng thuật toán:

Việc suy nghĩ như trên xem ra có tính khả thi (đơn giản, dễ cài đặt), tuy nhiên, dễ nhận thấy rằng nếu số n lớn hơn, ta sẽ phải phát triển một số quá lớn các trạng thái trước khi phát hiện ra trạng thái đích. Những hạn chế về mặt thời gian và dung lượng bộ nhớ không cho phépthực hiện điều đó.

Trong thực tế, có nhiều bài toán mà số các trạng thái của nó là rất lớn (như cờ vua, cờ tướng...), thì việc giải bài toán chỉ có thể thực hiện nếu bằng một cách nào đó ta lược bỏ những trạng thái thừa, không cần thiết nhằm giảm số lượng trạng thái cần phát triển. Để làm được điều đó, phải sử dụng khéo léo các thông tin phản hồi nảy sinh trong quá trình tìm kiếm (các thông tin này còn gọi là thông tin cảm tính: HeuristicInformation). Cách làm này được đưa ra nhằm mục đích lựa chọn được hướng tìm kiếm tốt nhất tại mỗi bước theo nghĩa: hướng đi đó nhanh dẫn tới trạng thái đích nhất và nhằm giảm công sức tìm kiếm.


Thuật toán leo đồi:

Thuật toán tìm kiếm leo đồi đã đáp ứng được yêu cầu trên. Nội dung thuật toán được mô tả như sau:

Bước 1: Nếu trạng thái đầu trùngvới trạng thái đích thì dừng ngay, ngược lại thì chuyển sang bước 2.

Bước 2: Sử dụng các quy tắc biến đổi để tạo ra 1 tập hợp các trạng thái từ trạng thái hiện thời (trong bài toán trên ta có 4 quy tắc biến đổi tương ứngvới 4 phép di chuyển quân).

Bước 3: Với mỗi trạng thái trong tập hợp vừa tạo ra kiểm tra xem đó có phải là trạng thái đích hay không? Nếu phải thì ngừng việc tìm kiếm, nếu không phải thì ta kiểm tra xem trạng thái mới này có tốt hơn (gần trạng thái đích hơn) so với trạng thái đã có hay không? Nếu quả thật như vậy thì ghi nhận trạng thái này, ngược lại thì bỏ qua.

Bước 4: Trong các trạng thái được tạo ra (sau khi thực hiện các thao tác ở bước 3), ta ưu tiên phát triển trạngthái tốt nhất (trạng thái tốt nhất là trạng thái có tiềm năng dẫn tới đích nhanh nhất).
Bước này nhằm mục đích chuyển hướng tìm kiếm lời giải nhanh đến đích nhất.

Bước 5: Lặp lại từ bước 2.

Đến đây bạn có thể nhận thấy thuật toán tìm kiếm leo đồi thực chất là thuật toán tìm kiếm theo chiều sâu, song tại mỗi bước ta sẽ ưu tiên chọn một trạng thái có hứa hẹn nhanh tới đích nhất để phát triển trước. Vấn đề quan trọng là ở chỗ biết khai thác khéo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhanh quá trình tìm kiếm.Thông thường ta gắn mỗi trạng thái của bài toán với một số đo (1 hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó.

Như vậy: Nếu trạng thái hiện thời là u, theo bước 4 của thuật toán trên thì trạng thái v sẽ được phát triển tiếp theo nếu vẻ kề(u) và hàm đánh giá của v đạt giá trị max (hoặc min).


Phần tiếp theo sẽ trình bày cụ thể thuật toán để giải bài toán trên. Trong bài toán này, ta sẽ sử dụng hàm đánh giá ký hiệu là h với ý nghĩa: h(u) cho biết số cácchữ số trong trạng thái u không trùng với vị trí của nó trong trạng thái đích.Trạng thái có tiềm năng dẫn tới đích nhanh nhất (được ưu tiên phát triển trước)là trạng thái có hàm đánh giá h đạt giá trị min.
Thuật toán cho trò chơi n<sup>2</sup>-1 số được mô tả như sau :

 

Hình 3

Algorithm:

Input: Trạng thái ban đầu u<sub>0</sub>và trạng thái đích u<sub>t</sub>

BEGIN

1. P:={u<sup>0</sup>} ; { P để lưu các trạng thái chờ phát triển được tổ chức dưới dạng Stack }

   Q:=Φ ;  { để lưu các trạng thái đãphát triển được tổ chức dưới dạng hàng đợi Queue }

   P:= Φ ; { P để lưu tạm thời các trạngthái kề với trạng thái đang xét }

   found:=false;

2. While (P # y) and (not found) do

   2.1. Loại bỏ trạng thái u ở đỉnh stack P và đặt nó vào hàng đợi Q:
          Pop(P, u);
          Add(u, Q);

2.2. if u=u<sub>t</sub> then found:= true
       else
           For v kề (u) do
              if (v thuộc P U Q) and (h(v) <= max { h(w)| w thuộc P U Q } then
               Begin
                  father (v):=u;
                  Add (v, P);
              End;

        if P <> f then
         Begin
           - Sắp xếp các trạng thái trong P theotrật tự tăng của hàm h;
           - Chuyển các trạng thái trong P vàođỉnh của stack P sao cho trạng thái có giá trị hàm h nhỏ nhất ở đỉnh của P;

         End;

END.

Output:  

- Nếu found = false thì bài toán không có lời giải.

- Nếu found = true thì lời giải là đường đi từ u<sub>0</sub> tới u<sub>t</sub> được xác định bằng cách sử dụng hàm father.


Chú ý: Sau khi chuyển các trạng thái từ P vào P thì P= f

 Hình 4

h(v<sub>1</sub>)  ≤  h(v<sub>2</sub>)  ≤ .... ≤  h(v<sub>k</sub>)

Với ví dụ trên, cây tìm kiếm được hình thành bởi tìm kiếm leo đồi có các trạng thái được phát triển như hình vẽ dưới (nét đậm thể hiện hướng tìm kiếm), các số ghi cạnh mỗi đỉnh là giá trị của hàm h tại đỉnh đó.

Thuật toán này có tên gọi là thuật toán tìm kiếm leo đồi, vì tư tưởng của nó tương tự như trường hợp: Một người ở vị trí chân đồi u<sub>0</sub> và muốn leo lên đỉnh đồi tại vị trí u<sub>t</sub>. Anh ta chọn một đỉnh cao nhất trong số các đỉnh mà anh ta có thể đến được (từ vị trí đang đứng) để leo lên, tại vị trí này anh ta lại chọn một đỉnh cao nhất như bước trước để leo lên. Quá trình cứ lặp lại như vậy cho đến khi tới được đích u<sub>t</sub>.

Nhận xét: Thuật toán này đơn giản, dễ cài đặt và tỏ ra có nhiều hiệu quả. Bạn đọc có thể tự lập trình để giải bài toán trên, kết quả khá tuyệt vời! Tuy nhiên, thuật toán này không phù hợp với các bài toán có giá trị hàm đánh giá đột nhiên thay đổi khi đến ngưỡng nào đó. Một số hiện tượng sẽ nảy sinh trong quá trình tìm kiếm được ghi nhận như sau:

*Có cực đại địa phương, là nơi đạt được lời giải tốt hơn các lời giải lân cận, nhưng chưa phải là lời giải tốt trên tổng thể. Như vậy phải có biện pháp ghi nhớ lại nhiều đường đi đề phòng khi cần đi lại đường cũ.

*Có vùng lời giải như cao nguyên bằng phẳng, không thể xác định được ngay hướng nào tốt hơn nếu chỉ so sánh vùng lân cận (các trạng thái của bài toán có hàm đánh giá xấp xỉ bằng nhau). Khi đó cần có bước nhảy xa để thoát khỏi vùng bằng phẳng.

Có đỉnh hình chóp, đó là trạng thái được lựa chọn tốt hơn vùng lân cận nhưng không vượt qua được theo bất kỳ hướng nào. Để xử lý hiện tượng này, nên chuyển theo đồng thời vài hướng.

Cực đại địa phương Cao nguyên Chóp

Minh họa cực trị địa phương khi giải bài toán bằng thuật toán leo đồi.

Như vậy: Thuật toán này chỉ làphương pháp giải quyết cục bộ, để tăng tính tối ưu, có thể sử dụng phối hợp nóvới các thuật toán tìm kiếm khác.

 Hình 5

• Có thể bạn quan tâm:

  - Kiếm tiền online tại nhà

  - Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ

  - Khoá học tin học văn phòng tốt nhất

Tham khảo 123doc

Read More