Lập trình

BÀI TOÁN TỐI ƯU HÓA

Thông thường, một vấn đề hay bài toán thiết kế tối ưu có N biến, được viết như là một chương trình phi tuyến (Nonlinear Programming-  NLP) như sau:

Tìm giá trị cực tiểu (hoặc cực đại ) của hàm :

f(x)àmin(max);                                                                    (1)

Với điều kiện :

Mục tiêu của bài toán là tìm tập hợp các   thỏa mãn :

đồng thời  f(x) đạt giá trị cực tiểu hoặc cực đại. 

Trong đó, f(x) ở (1) được gọi là hàm mục tiêu hoặc tiêu chuẩn tối ưu, được biểu diễn qua chất lượng của quá trình khảo sát và biến x.

Các hàm số ,  là các điều kiện ràng buộc của bài toán tối ưu dưới dạng bất đẳng thức và đẳng thức.  Trong không gian các biến, các hàm số này tạo ra miền giới hạn D các khả năng cho phép của hàm f(x).

Nếu Rⁿ (Với R là số chiều của hàm mục tiêu), nghĩa là không tồn tại bất kỳ một điều kiện giới hạn nào, ta nói rằng bài toán quy hoạch phi tuyến không ràng buộc.

Giải thuật di truyền cho bài toán tối ưu một hàm F có n biến . Biết rằng mỗi biến  được lấy các giá trị từ miền  là tập con của tập các số thực R và yêu cầu độ chính xác là k chữ số thập phân.

 

2.2. CÁCH BIỂU DIỄN BIẾN TRONG THUẬT TOÁN DI TRUYỀN

2.2.1. Biểu diễn nhờ vector nhị phân

- Mã hóa, ánh xạ một chuỗi với chiều dài hữu hạn sang các tham biến của bài toán tối ưu.

- Tham biến  sẽ được biểu diễn bởi chuỗi nhị phân có chiều dai L. L bit mã hóa ứng x với giá trị trong miền  ánh xạ lên miền .

Tỷ lệ co gián của ánh xạ g là:

                                                                                               (2)

Giá trị của x ứng với chuỗi nhị phân String2, tính theo công thức :

                                                                                    (3)

Trong đó,  biểu diễn giá trị thập phân của chuỗi nhị phân String2.

g: được xác định theo công thức (2)

Ví dụ :  được biểu diễn bởi chuỗi nhị phân 0001 thì decimal(0001) = 1

2.2.2. Toán tử chọn cá thể

- Giá trị thích nghi f(i) được xác định đối với mỗi quần thể, giá trị này càng lớn thì cá thể được xem là hợp lý.

- Các bước để chọn :

+ Tính tổng giá trị thích nghi của tất cả các thành viên trong quần thể và gọi là tổng thích nghi.           

+  Phát sinh 1 số nguyên n thỏa mãn :

+ Trả lại thành viên quần thể đầu tiên mà độ thích nghi của nó cộng với độ thích nghi các thành viên quần thể trước đó lớn hơn hay bằng n.

2.2.3. Toán tử lai ghép

Thực hiện crossover để  tác động lên các cá thể cha, mẹ để tạo nên con lai tốt.

Ký hiệu :  là xác suất lai ghép khi tác lai ghép trên cặp bố mẹ được chọn.

 *pop_size ( kích thước của quần thể lai tạo)  cho biết số lượng nhiễm sắc thể được dùng cho hoạt động lai ghép.

Với mỗi nhiễm sắc thể trong quần thể :

Phát sinh một số r ngẫu nhiên thuộc đoạn [0,1].

r< thì chọn nhiễm sắc thể đó lai ghép.

Sau đó, kết hợp nhiễm sắc thể được chọn 1 cách ngẫu nhiên: bằng cách chọn ngẫu nhiên vị trí lai ghép pos từ miền [0,L]; ( L tổng số bit trong nhiễm sắc thể).

Lai ghép được con cháu :

2.2.4. Toán tử đột biến

  Nhằm tạo ra các thông tin mới trong quần thể lai tạo tại các vị trí bit nào đó. Số lượng bit đột biến là  : ( là xác suất đột biến). Mỗi bit có cơ hội đột biến như nhau và có thể thay đổi 0 thành bit 1 và ngược lại.

Nếu r<  tiến hành đột biến tại bit đó.

Quá trình trên lặp đi lặp lại cho đến khi các cá thể con cháu của chúng tăng đến kích cỡ mong muốn của quần thể.

2.2.5. Hàm thích nghi

-  Ánh xạ giá trị hàm mục tiêu sang giá trị hàm thích nghi

Giả sử cực tiểu hàm đánh giá g(x) chuyển sang hàm thích nghi là :

Với Cmax là tham số đầu vào (có thể là giá trị lớn nhất trong quần thể hiện tại hoặc lớn nhất sau k vòng lặp).

-Điều chỉnh độ thích nghi :

       Điều chỉnh tuyến tính, giả sử độ thích nghi gốc là f, độ thích nghi biến đổi là f’ thì :

f’ = a*f + b   và :  .

 Trong đó :   là số các bản sao đối với 1 thành viên tốt nhất. Kinh  nghiệm cho thấy nếu số lượng quần thể n nhỏ thì  =1.2 đến 2 là tỏ ra hiệu quả.

2.3. CÁC GIẢI THUẬT GAs TIÊN TIẾN

2.3.1. Real-coded GAs

Như trình bày ở trên, đối với GAs nhị phân ở đó biến được biểu diễn bởi một chuỗi nhị phân. Tuy nhiên,không phải lúc nào cũng vậy và các biến lấy giá trị thực có thể được sử dụng trực tiếp. Khác lại với các giải thuật GAs truyền thống, bộ gen gồm các thông số đối tượng (giá trị thực) Real-coded  GAS sử dụng toán tử tái tổ hợp đặc biệt, đó là cấu trúc lai của tái tổ hợp trung gian ( intermediate recombination)  ( thường ) và đột biến.

Mặc dù các hoạt động sinh sản tương tự được mô tả ở đây có thể được sử dụng, nhưng thủ thuật nằm trong việc sử dụng hiệu quả ở khai thác các hoạt động crossover và mutation và khai thác chéo đột biến (Eshelman & Schaffer 1993), [4]. Real – coded GAs mã hóa loại bỏ những khó khăn để đạt được độ chính xác tùy ý trong các biến quyết định và các vấn đề Hamming Cliff (Goldberg 1989) kết hợp với đại diện của chuỗi nhị phân của số thực.

Sự corosser được thực hiện biến với biến. Để crosser biến thứ i giữa  2 vectơ bố mẹ (có  và giá trị ), các thủ tục sau đây được sử dụng để tạo ra 2 giá trị mới ( và  ) bằng cách sử dụng một phân bố xác suất () được mô tả như sau [12]:

                                                                           (4)

Ở đây, tham số  là tỷ lệ của sự khác biệt ở các giải pháp con và bố mẹ (children và parent solutions):

                                                                                                              (5)

Các thủ tục để tính trẻ giải pháp con và bố mẹ như sau :

(1) Tạo một số n ngẫu nhiên giữa 0 và 1.

(2) Tìm   để   

(3) Con có thể được tính như sau :

Các phân phối xác suất được chọn để sản xuất các giải pháp gần bố mẹ (near –parent) với một xác suất lớn hơn so với các giải pháp xa bố mẹ (far-parent). Các tham số  xác định làm thế nào giải pháp con có thể trở thành các gần với các giải pháp bố mẹ. Thực nghiệm cho thấy với giá trị của  tốt trong hầu hết các trường hợp [13].

2.3.2. Tối ưu hóa đa phương thức (Multimodal optimization)

Nhiều vấn đề trong thế giới thực có nhiều giải pháp được tối ưu hoặc gần tối ưu. Các kiến ​​thức về nhiều giải pháp tối ưu trong vấn đề cung cấp sự linh hoạt trong việc lựa chọn các giải pháp thay thế nào tốt như nhau và khi cần thiết. Trong các phương pháp truyền thống, giải pháp tối ưu sử dụng point-by-point, việc lặp đi lặp lại áp dụng các thuật toán tối ưu hóa với các điểm khác nhau ban đầu là bắt buộc. Tuy nhiên, vì GAs thực hiện với các điểm dân số, một số giải pháp tối ưu có thể được thực hiện để cùng tồn tại trong dân số, qua đó cho phép chúng ta tìm thấy nhiều giải pháp tối ưu đồng thời.

Ý tưởng về một số giải pháp tối ưu cùng tồn tại trong một dân số đòi hỏi một số thay đổi trong thuật toán di truyền đơn giản được mô tả trong phần trước. Vay mượn tương tự của cùng tồn tại nhiều hốc trong tự nhiên, chúng tôi nhận ra rằng nhiều hốc (con người và động vật, ví dụ) tồn tại bằng cách chia sẻ các nguồn lực có sẵn (ví dụ đất và thực phẩm). Một khái niệm chia sẻ tương tự được giới thiệu nhân tạo trong một dân số GA bởi chức năng chia sẻ (Goldberg & Richardson 1987; Deb 1989; Deb & Goldberg 1989), trong đó tính toán mức độ chia sẻ mà cần phải được thực hiện giữa hai chuỗi. Nếu khoảng cách (có thể là một số chuẩn mực của sự khác biệt trong các giá trị tham số được giải mã) giữa các chuỗi thứ i và thứ j là d,;, thường là một chức năng chia sẻ tuyến tính được sử dụng:

                                                                                             (6)

 Tham số  là khoảng cách tối đa giữa hai dây cho họ để được chia sẻ và được cố định trước (Deb 1989). Việc tăng cường chia sẻ với GAs đơn giản như sau. Đối với mỗi chuỗi trong dân số, các giá trị chức năng chia sẻ được tính cho các chuỗi khác lấy hoặc từ một mẫu dân số hoặc từ toàn dân.

GAs với chiến lược chia sẻ này đã giải quyết được một số vấn đề tối ưu hóa đa phương thức, bao gồm hơn năm triệu tối ưu cục bộ, trong đó chỉ có 32 là tối ưu toàn cục [14].

2.3.3. Tối ưu hóa đa mục tiêu (Multi-objective Optimization )

Trong một bài toán tối ưu đa mục tiêu, có nhiều hơn một chức năng khách quan để được tối ưu hóa cùng một lúc. Theo truyền thống, việc thực hành là để chuyển đổi nhiều mục tiêu vào một hàm mục tiêu (thường là trung bình có trọng số của các mục tiêu được sử dụng) và sau đó xử lý các vấn đề như là một vấn đề duy nhất tối ưu hóa mục tiêu. Thật không may, kỹ thuật này là chủ quan cho người dùng, với các giải pháp tối ưu là phụ thuộc vào các vector trọng lựa chọn. Trong thực tế, các giải pháp của vấn đề tối ưu hóa đa mục tiêu có thể được coi như một bộ sưu tập các giải pháp tối ưu thu được bằng cách giải quyết các chức năng mục tiêu duy nhất khác nhau được hình thành bằng cách sử dụng các vector trọng số khác nhau. Những giải pháp này được gọi là giải pháp tối ưu Pareto (Pareto optimal solution).

Nhiều kết quả nghiên cứu khác nhau cho việc mở rộng GAs với giải pháp tối ưu Pareto được nhiều tác giả công bố như Fonseca & Fleming 1993; Horn & Nafpliotis 1993 và  Srinivas & Deb 1995, cho thấy cách tiếp cận này là khá lý tưởng. Có thể mô tả ngắn gọn phương pháp đó như sau :

GAs yêu cầu một giá trị thich nghi cho một giải pháp cá thể trong quần. Như vậy, một giá trị thích nghi tạo ra phải được gán cho mỗi giải pháp trong dân số phụ thuộc vào các giá trị so sánh của từng hàm mục tiêu. Ý tưởng này được đề xuất bởi Goldberg [7], Srinivas & Deb [19]. Trong một quần thể, các giải pháp nondominated sorting of population members được định nghĩa là những giải pháp mà có trong ít nhất một mục tiêu tốt hơn so với bất kỳ giải pháp khác trong dân số. Để thực hiện giải pháp này các thủ tục sau đây được áp dụng:

• Dân số được sắp xếp để tìm các tập nondominated của các giải pháp. Tất cả các cá nhân trong quần thể này được gán một giá trị thích nghi nhân tạo.

• Vì mục tiêu là để tìm thấy một số giải pháp Pareto tối ưu, chia sẻ thủ tục được mô tả trước đó được thực hiện trong số các giải pháp này nondominated và giá trị thích nghi chung mới được tính cho giải pháp này.

• Những giải pháp này được tạm tính ra dân số và các tập nondominated tiếp theo được tìm thấy. Những giải pháp này được gán một giá trị thích nghi  nhân tạo nhỏ hơn giá trị thích nghi chung được chia sẻ trong tập nondominated trước. Điều này được thực hiện để áp một tham chiếu cao hơn đối với giải pháp ở trước (và tốt hơn) thiết lập hơn cho các thiết lập hiện hành.

• Chia sẻ được thực hiện một lần nữa trong bộ nondominated mới và quá trình này tiếp tục cho đến khi tất cả các thành viên dân số và được xếp theo thứ tự giảm dần của các bộ nondominated.

• Sau đó, các hoạt động sinh sản được thực hiện với những giá trị thích nghi nhân tạo.

• Các hoạt động Crossover và Mutation được áp dụng như bình thường.

2.3.4.GAs ở thiết kế điều khiển mờ (fuzzy logic controller design)

Kỹ thuật logic mờ chủ yếu được áp dụng trong vấn đề kiểm soát tối ưu mà ở đó chiến lược kiểm soát nhanh là cần thiết và định nghĩa chính xác và chất lượng của kế hoạch hành động có sẵn. Có hai hoạt động trong việc thiết kế một bộ điều khiển mờ tối ưu chủ yếu:

 (1) Tìm hàm thành viên tối ưu cho biến điều khiển và biến tác động

 (2) Tìm một tập hợp các luật tối ưu giữa biến điều khiển và biến tác động.

Hình 2.1. cho thấy hàm thành viên điển hình cho một biến có ba sự lựa chọn - low, medium và high. Do giá trị cực đại hàm thành viên  của những lựa chọn này luôn luôn là một (được đánh dấu  thường được chọn bởi người sử dụng). GAs sẽ thực hiện điều chỉnh hoành độ như các biến và một vấn đề tối ưu hóa có thể được đặt ra để tìm các biến để giảm thiểu hay tối đa hóa một chiến lược kiểm soát (chẳng hạn như thời gian của hoạt động tổng thể, chất lượng sản phẩm, và những thứ khác)[8].

Ở hoạt động thứ 2 nhằm tìm kiếm cơ sở quy tắc tối ưu sử dụng GAs. Để hiểu rõ điều này, chúng ta hãy lấy một ví dụ để minh họa như sau. Giả sử cần điều khiển động cơ của máy bay phản lực chạy bằng hơi nước, giả định rằng có hai biến điểu khiển(nhiệt độ và độ ẩm) và có ba lựa chọn cho mỗi biến - thấp(low), trung bình(medium) và cao(high). Có một biến tác động (tốc độ máy bay phản lực nước) cũng phải lựa chọn mất một trong ba lựa chọn - thấp, trung bình và cao.

Hình 2.1. Hàm thành viên mờ và các loại biến sử dụng cho thiết kế tối ưu

Với các tùy chọn này, có tổng cộng 3 x 3 hoặc 9 kết hợp của các biến điều khiển. Trong thực tế, ta phải xem xét ảnh hưởng của các biến điều khiển riêng biệt và có tổng cộng (4 x 4-1) hoặc 15 tổng các kết hợp của các biến điểu khiển có thể xảy ra. Vì vậy, việc tìm kiếm một cơ sở quy tắc tối ưu là tương đương với việc tìm kiếm một trong bốn tùy chọn (tùy chọn thứ tư là không có hành động) của biến hành động cho mỗi sự kết hợp của các biến điều khiển. Một GA với chiều dài chuỗi là 15 và với một ternary-coding có thể được sử dụng để đại diện cho cơ sở luật cho vấn đề này. Sau đây là một chuỗi điển hình: 312424344243224.

Mỗi vị trí trong chuỗi có nghĩa là một sự kết hợp của các biến tác động. Trong các mã trên, a1 đại diện thấp, a2 đại diện trung bình, a3 đại diện cho giá trị cao của biến  tác động và a4 không có tác động, qua đó đánh dấu sự vắng mặt của sự kết hợp tương ứng của các biến tác động trong các cơ sở luật. Do đó, chuỗi ở trên đại diện cho một cơ sở luật, có 9 luật (không có 4 giá trị). Cơ sở luật  không chứa 6 kết hợp của các biến tác động (cụ thể là các kết hợp thứ 4, 6, 8, 9, 1 l và 15). Bảng 2.1 chỉ ra sự tương ứng cơ sở luật. Mặc dù cơ sở nguyên tắc này có thể không phải là tối ưu nhất, GAs có thể xử lý một dân số với cơ sở luật như vậy và cuối cùng tìm thấy các cơ sở luật tối ưu. Một khi các quy tắc hiện tại trong các cơ sở luật được xác định từ chuỗi, hàm thành viên được định nghĩa bởi người dùng có thể được sử dụng để mô phỏng các quá trình cơ bản trên. Sau đó, giá trị hàm mục tiêu có thể được tính toán và hoạt động sinh sản có thể được sử dụng. Các họat động crossover đơn điểm thông thường và mutation có thể được sử dụng với mã hóa này. Việc đối phó với các biến rời rạc và với một chuỗi đại diện của một giải pháp, phương pháp nêu trên nhằm tìm kiếm một cơ sở luật  tối ưu với số lượng tối ưu của luật là điểm độc đáo trong GAs. Một kỹ thuật như vậy đã được sử dụng để thiết kế một bộ điều khiển logic mờ cho hướng di động Robot và các trở ngại động đã được công bố [3].

Bảng 2.1. Biến tác động cho một chuỗi đại diện một cơ sở luật mờ

( hiển thị ở phông chữ nghiêng).

2.3.5. GAs với mạng Neural

Mạng lưới neural đã được sử dụng chủ yếu trong các vấn đề mà ở đó một mối quan hệ phi toán học giữa một tập hợp các biến đầu vào và đầu ra là mong muốn. GAs có thể được sử dụng ở hai hoạt động chủ yếu trong các ứng dụng mạng neural.

(1) Sử dụng như một thuật toán máy học cho một mạng lưới neural mà người dùng định nghĩa [13].

(2) Sử dụng để tìm các kết nối tối ưu giữa các đầu vào, đầu ra.

2.3.6. GAs với tìm kiếm lịch trình tối ưu (Searching for optimal schedules)

Để cạnh tranh, các công ty phải giảm thiểu sự thiếu hiệu quả và tối đa hóa năng suất. Trong sản xuất, năng suất vốn liên quan đến như thế nào bạn có thể tối ưu hóa các nguồn lực bạn có, giảm lãng phí và tăng hiệu quả. Tìm cách tốt nhất để tối đa hóa hiệu quả trong quá trình sản xuất có thể cực kỳ phức tạp. Ngay cả các dự án đơn giản, có nhiều đầu vào, nhiều bước, nhiều hạn chế và nguồn lực hạn chế. Nói chung một nguồn lực hạn chế vấn đề lịch bao gồm:

• Một tập hợp các công việc phải được thực thi
• Một tập hữu hạn của tài nguyên có thể được sử dụng để hoàn thành từng công việc
• Một tập các ràng buộc mà phải được hài lòng (thời gian, rang buộc thứ tự nhiệm vụ, hạn chế tài nguyên )
• Một tập hợp các mục tiêu để đánh giá việc thực hiện kế hoạch

Vấn đề lập lịch trình thường sử dụng các thuật toán heuristic để tìm kiếm các giải pháp tối ưu.  Tuy nhiên, đây là loại vấn đề trong khoa học máy tính thuộc loại NP-Hard. Điều này có nghĩa khó có thể có một thuật toán để tìm kiếm một lời giải tối ưu trong thời gian đa thức.

GAs là rất thích hợp để giải quyết các vấn đề này, ​bởi vì không giống như các phương pháp heuristic, thuật toán di truyền hoạt động trên một số các giải pháp chứ không phải là một giải pháp duy nhất [12].