• Thứ Ba, 16/12/2003 18:01 (GMT+7)

    Ứng dụng MEP vào thiết kế mạch

        Trí tuệ nhân tạo (AI) là một lĩnh vực đầy thú vị với những người làm tin học. Ta có thể thấy sự có mặt của AItrong nhiều lĩnh vực như nhận dạng, trò chơi, hệ chuyên gia… AI đem đến cho máy tính sự thông minh của con người, giờ đây máy tính đã có thể “bắt chước” con người trong một số công việc. Liệu nó có thể thay chúng ta thiết kế mạch tính toán mới? Bài viết này giới thiệu ứng dụng kỹ thuật AI - MEP vào thiết kế mạch logic.
        Lý thuyết giải thuật di truyền (GA – Genetic Algorithm) là một lĩnh vực hấp dẫn của AI, nó mô phỏng sự tiến hoá của tự nhiên để giải quyết các bài toán. Ý tưởng của GA là coi mỗi phương án giải bài toán như một cá thể trong tự nhiên, hàm mục tiêu được xây dựng trên yêu cầu bài toán để đánh giá “độ thích nghi” (khả năng đi đến lời giải) của cá thể. Ban đầu, một tập các phương án (quần thể) được tạo ra nhưng chưa tối ưu, quần thể này phát triển qua nhiều thế hệ, cuối cùng tới một thế hệ nào đó sẽ thu được cá thể biểu diễn lời giải của bài toán. MEP (Multiple Expression Programming) là một kỹ thuật mới trong GA. MEP đưa ra cách thức mã hoá mới, mỗi cá thể là một chuỗi các biểu thức phức tạp có thể mã hoá nhiều phương án giải bài toán.

    MÔ TẢ BÀI TOÁN

        Bài toán thiết kế mạch có thể mô tả như sau: thiết kế mạch có N đầu vào và M đầu ra. Đầu vào và đầu ra là bảng chân trị của mạch cần thiết kế. Ta phải tính toán biểu thức logic để thoả mãn bảng chân trị (thoả mãn yêu cầu của thiết kế). Hay nói cách khác là tìm ra biểu thức (mạch) logic có bảng chân trị trùng với bảng chân trị đã cho.

    THUẬT GIẢI DI TRUYỀN

    Biểu diễn “gen” (mã di truyền) có cấu trúc như sau:
    struct Gene{

          int instruction1;

          int intstruction2;

          int operation;

     }
    Mạch logic của chúng ta có nhiều đầu vào và 4 phép toán: và (AND), hoặc (OR), hoặc loại trừ (XOR) và phủ định (NOT).
    Ta sẽ mã hoá các biến và phép toán như sau:

    0: AND

    1: OR

    2: XOR

    3: NOT

    4: input 0

    5: input 1

    ...
    Gen được lưu vào một mảng có độ dài thay đổi vì các biểu thức có thể có độ dài khác nhau.
    Công việc đầu tiên phải làm là tạo ra quần thể ban đầu cho bài toán, thuật toán tổng quát như sau:
    Population: Array;

    For i = 1 to PopulationSize

       // Tạo ra một nhiễm sắc thể mới

       aGenome : Array;

       For j = 1 to GeneLength

          aGene = new Gene;

          if (j = 0) // gen đầu tiên

               aGene.operation = Random(4, ((4 + N)-1)); // ký hiệu các đầu vào

               continue;

          end if

          aGene.operation = Random(0, N – 1);

          aGene.instruction1 = Random(0, j – 1); // biểu thức trước vị trí j

          aGene.instruction2 = Random(0, j – 1); // biểu thức trước vị trí j

          aGenome.Add(aGene); // đưa gen mới vào bộ nhiễm sắc thể

       end for

       Population.Add(aGenome); Đưa nhiễm sắc thể mới vào quần thể

    end for
    Để tính độ thích nghi của một cá thể, ta tiến hành theo bốn bước sau:
        B1. Với mỗi bộ giá trị của đầu vào, ta tính giá trị biểu thức được chứa trong bộ mã.
        B2. So sánh giá trị tìm được với giá trị trong bảng chân trị đã cho tương ứng với bộ giá trị đang xét.
        B3. Tính sai số của giá trị nhận và giá trị trong bảng chân trị. Hàm mục tiêu tỷ lệ nghịch với sai số.
       B4. Lặp lại các bước trên đối với mọi bộ giá trị trong bảng chân trị và tính tổng các hàm mục tiêu của từng lần lặp.
    Điều quan trọng trong phần này là tính được giá trị của biểu thức dựa trên bộ giá trị của các đầu vào. Hàm tính giá trị biểu thức của một bộ giá trị (input 0, input 1, ... , input N-1) được viết như sau:
    function PerformCalculation(InputArray){   

    Temp: Array; // mảng chứa các giá trị trung gian trong biểu thức gen

    for i = 0 to aGenome.Length() // duyệt lần lượt các gen trong aGenome

       Gene g = aGenome[i];

       case (g.operation)

       // gen chứa một biểu thức

        0: Temp[i] = Temp[g.instruction1] & Temp[g.instruction2]; // phép AND

       1: Temp[i] = Temp[g.instruction1] | Temp[g.instruction2]; // phép OR

       2: Temp[i] = Temp[g.instruction1] ^ Temp[g.instruction2]; // phép XOR

       3: Temp[i] = ~ Temp[g.instruction1];  // phép đảo, chỉ xử lý instruction1

       else  // gen chỉ chứa một biến

       // g.operation – 4 = số thứ tự của đầu vào đang xét

       Temp[i] = InputArray[g.operation - 4];

       end case

    end for

    return Temp[aGenome.Length() - 1];

    // giá trị tại gen cuối cùng

    }
        Để chọn lọc các cá thể cho thế hệ mới ta dựa vào độ thích nghi của từng cá thể và so sánh nó với độ thích nghi của “môi trường” do ta đặt ra. Nếu độ thích nghi của cá thể đó cao hơn thì nó sẽ được giữ lại, nếu không nó sẽ bị đào thải. Trong quá trình đó, có thể số cá thể bị giảm xuống hoặc tăng lên. Nếu số cá thể giảm xuống quá nhiều chứng tỏ quần thể ban đầu không đủ sức sống và ta nên khởi tạo lại. Nếu số cá thể tăng lên quá giới hạn quy định, ta lại phải loại bỏ các cá thể thừa để đảm bảo tốc độ xử lý.
        Trong việc lai ghép, ta tiến hành ngẫu nhiên theo 3 cách: lai đều, lai một điểm và lai hai điểm. Để tiến hành trao đổi gen, ta sử dụng hai biến mảng tạm, sau đó copy lần lượt từng gen của một trong hai gen đem lai vào hai biến đó theo đúng quy luật đã nêu trên. Cuối cùng, ta tính độ thích nghi của gen bố mẹ và gen con. Hai cá thể có độ thích nghi cao nhất trong gia đình bốn cá thể sẽ được đưa vào quần thể.

         Trong việc đột biến, ta xác định số cá thể bị đột biến trước, sau đó tiến hành đột biến trên các cá thể được chọn ngẫu nhiên. Việc đột biến rất đơn giản: chỉ cần thay thế một gen bất kỳ trong bộ mã bởi một gen ngẫu nhiên khác.   

    HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH

        Chương trình có khả năng thiết kế các mạch logic sử dụng 4 mạch cơ bản AND, OR, XOR, NOT. Người dùng sẽ viết một tập tin mô tả chức năng mà mình mong muốn, sau đó chạy chương trình để đọc tập tin và đưa ra kết quả. Để thuận tiện, tập tin thiết kế được để ở dạng văn bản (text) nên người dùng có thể sử dụng bất kỳ chương trình soạn thảo văn bản nào để soạn.

    Cấu trúc tập tin thiết kế như sau:
    Dòng 1: Tên mạch cần thiết kế
    Dòng 2: 3 tham số viết cách nhau một dấu cách:
    Số đầu vào (N), số đầu ra (M), số bộ giá trị mẫu.
    Các dòng tiếp theo (số dòng = số bộ giá trị mẫu).
    Mỗi dòng chứa một bộ gồm (N+M) giá trị logic (0/1) theo thứ tự: Input0 Input1 ... Input(N-1) Output(M-1) ... Output1 Output0. Với Input(i) là giá trị đầu vào i, Output(i) là giá trị đầu ra i.
    Đây chính là bảng chân trị của mạch, tuy nhiên người dùng có thể thiết kế các mạch có bảng chân trị không đầy đủ nếu chỉ cần tìm mạch đáp ứng đúng một số trường hợp mong muốn, còn không quan tâm đến các trường hợp khác.
    Lưu ý: Tất cả các giá trị được viết trên cùng dòng phải được phân cách bằng một và chỉ một dấu cách.
    Ví dụ: Để thiết kế mạch cộng 2 bit a1b1+a2b2 = x2x1x0, tập tin thiết kế có nội dung sau:

    Mach cong hai bit

    4 3 16

    0 0 0 0 0 0 0

    0 0 0 1 0 0 1

    0 0 1 0 0 1 0

    0 0 1 1 0 1 1

    0 1 0 0 0 0 1

    0 1 0 1 0 1 0

    0 1 1 0 0 1 1

    0 1 1 1 1 0 0

    1 0 0 0 0 1 0

    1 0 0 1 0 1 1

    1 0 1 0 1 0 0

    1 0 1 1 1 0 1

    1 1 0 0 0 1 1

    1 1 0 1 1 0 0

    1 1 1 0 1 0 1

    1 1 1 1 1 1 0
    Dịch ra là:
    Dòng 1: Tên mạch là “Mạch cộng hai bit”.
    Dòng 2: Mạch có 4 đầu vào (2 số 2 bit), 3 đầu ra (tổng 2 số 2 bit là số 3bit), bảng chân lý có 16 bộ giá trị mẫu.
    Dòng 3: Khi a1b1 = 00, a2b2  = 00 thì x2x1x0 = 000.
    Dòng 4: Khi a1b1 = 00, a2b2  = 01 thì x2x1x0 = 001.


    Đọc tập tin thiết kế và đưa ra kết quả:

    • Chọn tập tin thiết kế bằng nút “Mở file”.

    • Hiệu chỉnh các thông số cho chương trình, nhấn OK.

    • Sau khi nhấn OK, tại hộp “Đầu ra cần tính” sẽ có danh sách các đầu ra (mặc định chọn đầu 0), chọn đầu ra cần tính rồi nhấn OK tiếp.

    • Chuyển sang tab “Đầu ra” để xem kết quả.

    • Kết quả thiết kế là đúng khi độ thích nghi là 1. Nếu vẫn chưa nhận được kết quả ngay thì nhấn tiếp OK để tính tiếp n  thế hệ sau (có thể thay đổi được n tại “Số thế hệ cần tính”).

    • Nếu sau một thời gian dài chưa ra kết quả, có thể do quần thể gồm nhiều cá thể có độ thích nghi quá kém, có thể nhấn “RESET” để tính lại từ đầu (khởi tạo một quần thể ban đầu mới).

    Ý nghĩa các tham số cho chương trình:

    •Số cá thể khởi tạo: Số cá thể của thế hệ thứ nhất.

    • Số cá thể giới hạn: Số cá thể lớn nhất của quần thể.

    • Độ dài NST: Độ dài nhiễm sắc thể (bộ mã gen).

    • Tỷ lệ đột biến.

    • Ngưỡng đào thải: Trước khi sang thế hệ mới, những cá thể có độ thích nghi thấp hơn mức này sẽ bị đào thải khỏi quần thể.

    • Ngưỡng tái tạo: Trước khi sang thế hệ mới, chỉ những cá thể có độ thích ghi cao hơn mức này mới được tham gia tái tạo thế hệ mới.

    • Số thế hệ cần tính: Sau lần đầu tiên khởi tạo, mỗi lần nhấn OK sẽ tính toán n thế hệ tiếp theo, n được thay đổi tại mục này.

    • Đầu ra cần tính: Chọn đầu ra cần tìm biểu thức logic.

    Bạn đọc quan tâm có thể liên hệ với tác giả qua e-mail để nhận mã nguồn. Chương trình được viết bằng C# nên để chạy cần phải cài đặt  dotNETframework hoặc VisualStudio .NET.

    Doãn Hồng Hà – Lê Vũ Trung Thành
    Email : dhhhct@yahoo.com

     

    ID: A0308_101