Mục đích nghiên cứu của đề tài
Đề tài được thực hiện với ba mục đích chính:
Nghiên cứu lý thuyết các phương pháp tối ưu: o Tối ưu bầy đàn PSO (Particle Swarm Optimization) o Phương pháp tối ưu MOGA (MultiObject Genetic Algorithm)
Hiểu được quy trình giải bài toán tối ưu trong phần mềm mô phỏng số ANSYS
Áp dụng các phương pháp tối ưu vào mô hình bài toán cụ thể, chúng tôi đã sử dụng phương pháp Tối ưu hóa Bầy đàn (PSO) để giải quyết vấn đề Kết quả được phân tích thông qua phần mềm ANSYS, từ đó chúng tôi tiến hành so sánh và đánh giá hai kết quả đạt được để đưa ra nhận định chính xác về hiệu quả của từng phương pháp.
Nội dung cơ bản của đề tài
Luận văn bao gồm phần tổng quan về đề tài, danh mục các bảng, hình ảnh, chữ viết tắt, phụ lục và tài liệu tham khảo, với kết cấu chia thành hai phần chính.
Phần 1: Cơ sở lý thuyết – Nội dung phần này được chia làm 3 chương, bao gồm:
Chương 1: Tổng quan về tối ưu hóa
Chương 2: Nội dung phương pháp thiết kế mẫu Central Composite
Chương 3: Nội dung thuật toán tối ưu bầy đàn Particle Swarm
Chương 4: Nội dung phương pháp tối ưu MultiObject Genetic Algorithm
Phần 2 của bài viết tập trung vào việc áp dụng lý thuyết giải quyết bài toán tối ưu hóa mặt cắt ngang của dầm chính cầu trục một dầm tổ hợp chữ I Nội dung của phần này được chia thành ba chương, mỗi chương sẽ trình bày các khía cạnh khác nhau của vấn đề tối ưu hóa, từ lý thuyết cơ bản đến ứng dụng thực tiễn trong thiết kế cầu trục.
Chương 1: Nội dung bài toán
Chương 2: Giải quyết bài toán Sử dụng phương pháp MOGA trên phần mềm mô phỏng số ANSYS và phương pháp PSO
Trong phần này, tác giả áp dụng lý thuyết nghiên cứu từ phần 1 để giải quyết một bài toán tối ưu hóa cụ thể Do không thể xây dựng mô hình thực tế theo kết quả tối ưu, tác giả đã sử dụng phần mềm mô phỏng số ANSYS để đánh giá kết quả Với độ tin cậy cao của ANSYS, tác giả có thể sử dụng kết quả từ phần mềm này làm căn cứ để xác định độ chính xác của kết quả tối ưu.
Dựa trên kết quả nghiên cứu, tác giả đã nắm vững quy trình giải bài toán tối ưu và lý thuyết của nhiều phương pháp tối ưu phổ biến hiện nay Tác giả cũng hiểu rõ cơ chế thực hiện giải bài toán tối ưu trong phần mềm ANSYS, từ đó có khả năng giải quyết các bài toán tối ưu kết cấu một cách nhanh chóng và hiệu quả.
Ý nghĩa khoa học và thực tiễn của đề tài
Đề tài này trình bày ứng dụng thuật toán tối ưu bầy đàn PSO trong việc giải quyết bài toán tối ưu kết cấu thép cầu trục và máy nâng chuyển Với cơ chế hoạt động đơn giản hơn so với phương pháp MOGA trong ANSYS, nghiên cứu sẽ xây dựng một modul tối ưu hóa tương đương, giúp giải quyết các bài toán tối ưu một cách hiệu quả hơn Ngoài ra, đề tài cũng cung cấp tài liệu tham khảo cho những người chưa nắm vững thuật toán PSO và phương pháp MOGA, giúp họ hiểu rõ hơn về cơ chế giải bài toán tối ưu trong ANSYS và dễ dàng thao tác với các thiết lập ban đầu Cuối cùng, đề tài cho phép những người không có điều kiện sử dụng ANSYS vẫn có thể áp dụng thuật toán PSO để giải quyết bài toán tối ưu của mình.
TỔNG QUAN VỀ TỐI ƯU HÓA
Khái niệm tối ưu hóa
Là quá trình tìm kiếm điều kiện tốt nhất (điều kiện tối ưu) của hàm số được nghiên cứu
Quá trình xác định cực trị của hàm nhằm tìm ra điều kiện tối ưu cho một quy trình cụ thể Để đánh giá điểm tối ưu, cần lựa chọn các tiêu chuẩn công nghệ phù hợp.
Biểu diễn bài toán tối ưu
Giả sử một hệ thống công nghệ được biểu diễn dưới dạng sau:
Y 1 , 2 , , Trong đó: x 1 ,x 2 , ,x k : là vecto thông số đầu vào
Bài toán được biểu diễn f * f(x 1 * ,x 2 * , ,x * k ) trong đó:
* x k x x f f : đối với bài toán tìm giá trị lớn nhất
* x k x x f f : đối với bài toán tìm giá trị nhỏ nhất f *: là kết quả tối ưu
1,x , ,x k x nghiệm tối ưu hoặc phương án tối ưu
1.3 Phương hướng giải quyết bài toán tối ưu
Có nhiều phương pháp tối ưu hóa, trong đó phương pháp vét cạn và tìm cực trị là hai phương pháp phổ biến nhất Mặc dù cơ chế thực hiện của chúng tương đối đơn giản, nhưng cả hai đều tồn tại nhiều nhược điểm Đặc biệt, phương pháp tìm cực trị đã quen thuộc với nhiều người, nên chúng ta chỉ cần lưu ý đến những hạn chế của nó mà không đi sâu vào chi tiết.
Việc tính hàm cực trị và xây dựng đồ thị biến thiên cho hàm mục tiêu trong các bài toán tối ưu với số lượng biến đầu vào lớn là rất khó khăn, đặc biệt khi không gian tìm kiếm là ba chiều mà không có sự hỗ trợ của máy tính Điều này cho thấy rằng phương pháp tìm cực trị không khả thi trong nhiều trường hợp Vậy còn phương pháp vét cạn thì sao? Hãy cùng tìm hiểu nội dung cơ bản của phương pháp này.
2 1 kien dieu tra kiem doan k max 2 min
Trong bài toán này, ta có n biến đầu vào với giá trị nằm trong khoảng min và max tương ứng Mỗi biến sẽ được chia thành nhiều đoạn nhỏ, tùy thuộc vào yêu cầu của người tính toán Để đạt được kết quả chính xác, việc chia đoạn nên được thực hiện càng nhỏ càng tốt Số lượng bộ thông số đầu vào sẽ được tính bằng N = i × j × × k Đối với mỗi bộ thông số này, ta sẽ kiểm tra điều kiện và tính giá trị hàm mục tiêu để tìm ra giá trị tối ưu Phương pháp này có ưu điểm là không cần phải tính toán hàm cực trị hay vẽ đồ thị, nhưng khối lượng tính toán lớn và độ chính xác phụ thuộc vào kích thước của các đoạn chia.
Để đạt được kết quả chính xác cao mà không cần tìm hàm cực trị hay vẽ đồ thị, chúng ta có thể sử dụng thuật toán tiến hóa Phương pháp này giúp giảm khối lượng tính toán và đáp ứng các yêu cầu về hiệu quả trong việc tối ưu hóa.
Thuật toán tối ưu bầy đàn và thuật giải di truyền bắt nguồn từ một quần thể ban đầu, được khởi tạo ngẫu nhiên từ các bộ số đầu vào Bằng cách áp dụng các quy luật sinh tồn trong tự nhiên, thuật toán tìm ra giải pháp tối ưu cho bài toán Để cải thiện kết quả, phương pháp lấy mẫu sẽ được sử dụng thay vì khởi tạo ngẫu nhiên quần thể Dưới đây là quy trình giải bài toán tối ưu mà tác giả sẽ trình bày.
1.4 Quy trình giải bài toán tối ƣu
Các bước để giải bài toán tối ưu nói chung như sau:
1 Đặt vấn đề công nghệ: xem xét công nghệ cần được giải quyết là công nghệ gì và chọn ra những yếu tố ảnh hưởng chính
Chỉ ra được hàm mục tiêu f MAX, hoặc f MIN
2 Xây dựng mối quan hệ giữa các yếu tố ảnh hưởng và hàm mục tiêu theo qui luật biết trước hoặc mô hình thống kê thực nghiệm
3 Tìm thuật giải: là phương pháp để tìm nghiệm tối ưu của các bài toán công nghệ trên cơ sở các mô tả toán học tương thích đã được thiết lập Đa số dẫn đến tìm cực trị của các hàm mục tiêu
4 Phân tích và đánh giá kết quả thu được
Nếu phù hợp > kiểm chứng bằng thực nghiệm
Nếu không phù hợp > xem lại từng bước hoặc làm lại từ việc đặt vấn đề
Quy trình giải quyết bài toán tối ưu chung đã được trình bày ở trên, từ đó tác giả đề xuất các bước cụ thể để giải bài toán tối ưu kết cấu thép cầu trục như sau:
1 Tính toán sơ bộ kích thước mặt cắt ngang dầm chính cầu trục
2 Xây dựng hàm mục tiêu và hàm điều kiện
3 Thiết kế giá trị mẫu ban đầu Sử dụng phương pháp thiết kế mẫu CCD được trình bày trong chương 2
4 Thuật giải: Sử dụng thuật toán tối ưu bầy đàn PSO để giải quyết bài toán (Nội dung thuật toán PSO được trình bày trong chương 3)
5 Khai thác kết quả và đánh giá kết quả này với kết quả mô phỏng trên phần mềm ANSYS.
PHƯƠNG PHÁP THIẾT KẾ MẪU CENTRAL
Giới thiệu
Tối ưu hóa là quá trình tìm kiếm phương án tốt nhất từ tập hợp các giá trị đầu vào để giải quyết bài toán tối ưu Phương pháp Vét cạn có thể giúp giải bài toán nhưng tốn nhiều thời gian và tăng số lượng tính toán khi số tham số đầu vào lớn Do đó, cần tìm cách giảm thiểu thời gian thực hiện và số phép tính mà vẫn đạt được kết quả tối ưu Một giải pháp là lựa chọn một số phương án mẫu từ các giá trị đầu vào và sử dụng chúng kết hợp với các thuật toán tối ưu để giải quyết bài toán hiệu quả hơn.
Trong nghiên cứu này, tác giả sẽ áp dụng phương pháp thiết kế mẫu Central Composite Design để xây dựng mẫu ban đầu, nhằm tối ưu hóa mặt cắt ngang của dầm chính trong cầu trục Các phương pháp thiết kế mẫu khác như Optimal Space-Filling Design và Box-Behnken Design cũng tồn tại, nhưng không được sử dụng trong luận văn này.
Phương pháp thiết kế mẫu Central Composite Design (CCD)
Thiết kế Central Composite, hay còn gọi là thiết kế Box-Wilson, thuộc cấp độ 5 trong thiết kế phân đoạn yếu tố và thường được áp dụng trong mô hình đáp ứng bậc hai Thiết kế này bao gồm ba loại điểm khác nhau, giúp tối ưu hóa quá trình nghiên cứu và phân tích dữ liệu.
Center Point: được tạo bởi thiết kế Nominal
Axial Point: được tạo bởi thiết kế Screening Analysis
Cube Points: được tạo bởi thiết kế Full Factorial
Hình 1 Phương pháp thiết kế mẫu Central Composite Design
Trước khi tiếp tục tìm hiểu phương pháp này, để thuận tiện ta sẽ làm quen với khái niệm giá trị danh nghĩa
Giả sử ta có tham số a như sau: max min a a a
Như vậy giá trị danh nghĩa của a được định nghĩa như sau:
2.2.1.1 Center Point: Được tạo ra bởi thiết kế Nominal theo nguyên tắc: điểm ở tâm của phương án mà giá trị của các tham số bằng giá trị danh nghĩa của nó
2.2.1.2 Axial Points: Được tạo ra bởi thiết kế Screening Analysis Thiết kế này sẽ tạo ra 2*n điểm
Các điểm tối ưu được xác định khi một tham số đạt giá trị tối đa hoặc tối thiểu, trong khi các tham số khác giữ nguyên giá trị danh nghĩa của chúng Tham số n đại diện cho số lượng tham số đầu vào cần tối ưu hóa.
Hình 2 Ví dụ thiết kế Screening Analysis với 3 tham số đầu vào
2.2.1.3 Cube Points: Được tạo ra bởi thiết kế Full Factorial theo quy tắc sau: thiết kế tạo ra 2 n điểm bằng cách tổ hợp các giá trị min max của các tham số với nhau
Hình 3 Ví dụ thiết kế Full Factorial với 3 tham số đầu vào
Như vậy tổng số điểm thiết kế được tạo ra từ phương pháp CCD là:
2.2.2 Phân loại: Để mô tả phương pháp thiết kế trong trường hợp tổng quát, giá trị lớn nhất và nhỏ nhất của các tham số đầu vào (tham số điều khiển) được đặc trưng bởi hai giá trị là +1 và -1 Hình ảnh của thiết kế Central Composite Circumscribed cho ba tham số được thể hiện trong hình 4 Ở đây điểm axial points có vị trí nằm trên đường thẳng đi qua tâm các mặt của khối lập phương và có bán kính là b i Khối lập phương được xây dựng từ các điểm cube points có độ dài các cạnh là 2*a i
Hình 4 Hình ảnh các điểm thiết kế của phương pháp thiết kế Central Composite
Circumscribed với ba tham số đầu vào
Thiết kế Central Composite gồm 3 loại:
Central Composite Face-centered (CCF)
Hai loại thiết kế này có cấu trúc tương đồng, như thể hiện trong Hình 4, nhưng khác nhau về giá trị của a i và b i Việc xác định giá trị a i và b i cho ba loại thiết kế là rất quan trọng.
Central Composite được thể hiện trong Bảng 1
Bảng 1 Cách xác định giá trị a và b cho thiết kế Central Composite
Trong bảng trên, giá trị range i được xác định bằng chiều dài của tham số đầu vào i, cụ thể là hiệu giữa giá trị lớn nhất và nhỏ nhất của tham số này Bảng 1 chỉ thể hiện giá trị khi thiết kế có một điểm Center Point, tuy nhiên, điều này không ảnh hưởng lớn đến mô phỏng số, vì kết quả của hai mô phỏng với dữ liệu đầu vào giống nhau sẽ phải giống nhau.
Thiết kế của CCC và CCI có sự khác biệt nổi bật, đó là thiết kế xoay Thiết kế được xem là xoay khi các điểm thiết kế như Axial Points và Cube Points có thể quay quanh điểm trung tâm (Center Point) mà không làm thay đổi các phân vùng thiết kế.
Trong thiết kế Central Composite xoay, hệ số i a b phải bằng n Để minh họa cho định nghĩa thiết kế xoay, giả sử số lượng tham số đầu vào là 2, tạo thành không gian tìm kiếm 2 chiều Giá trị lớn nhất của tham số đầu vào được biểu thị bằng +1, trong khi giá trị nhỏ nhất được biểu thị bằng -1 Hai tham số đầu vào sẽ được đặt tên tương ứng.
1,x x Ta có: i i a b 2 Như vậy các điểm Axial Points sẽ tạo lên một hình tròn ngoại tiếp hình vuông được tạo lên từ các điểm Cube Points
Hình ảnh cho thiết kế CCC như sau:
Hình 5 Thiết kế CCC với hai tham số đầu vào
Sau khi xoay các điểm Cube Points và Axial Points quanh điểm Center Points ta được hình ảnh sau:
Hình 6: Thiết kế CCC với hai tham số đầu vào sau khi xoay
Ta thấy rằng các phân vùng thiết kế không có gì thay đổi, như vậy CCC là một thiết kế xoay
Center Point Cube Points Axial Points
Chúng ta sẽ chứng minh rằng thiết kế CCF không phải là thiết kế xoay hay không Theo nguyên tắc của thiết kế CCF, ta có a i = b i, từ đó có thể xác định các điểm thiết kế một cách chính xác.
Hình 7: Thiết kế CCF với hai tham số đầu vào
Sau khi xoay ta có:
Hình 8: Thiết kế CCF với hai tham số sau khi xoay
Hình 8 cho thấy rằng phân vùng thiết kế sau khi xoay khác biệt so với trước khi xoay, điều này được thể hiện qua phần có gạch chéo Do đó, thiết kế CCF không phải là thiết kế Central Composite xoay.
THUẬT TOÁN TỐI ƯU BẦY ĐÀN PARTICLE SWARM
Giới thiệu
Tối ưu bầy đàn (Particle Swarm Optimiser - PSO) là phương pháp tối ưu hóa dựa trên quần thể, được giới thiệu lần đầu bởi James Kennedy và kỹ sư Russell C Eberhart vào năm 1995 tại một hội nghị của IEEE PSO là một dạng thuật toán tiến hóa quần thể, tương tự như thuật toán di truyền (Genetic Algorithm), nhằm tìm kiếm giải pháp tối ưu trong các bài toán phức tạp.
Thuật toán tối ưu hóa bầy (PSO) là một phương pháp hiệu quả, không yêu cầu thông tin về độ dốc, cho phép giải quyết các bài toán tối ưu hóa phức tạp Khác với thuật toán di truyền (GA), PSO tập trung vào tương tác giữa các cá thể trong quần thể để khám phá không gian tìm kiếm Một ví dụ minh họa cho PSO là quá trình tìm kiếm thức ăn của một đàn chim trong không gian ba chiều Khi bắt đầu, đàn chim bay ngẫu nhiên, nhưng sau một thời gian, một số cá thể tìm thấy thức ăn và gửi tín hiệu cho các cá thể khác Tín hiệu này giúp toàn bộ đàn điều chỉnh hướng bay và tốc độ để hướng về nơi có nhiều thức ăn nhất, thể hiện cơ chế trí tuệ bầy Nhờ vào cơ chế này, PSO có thể tối ưu hóa việc tìm kiếm trong không gian rộng lớn.
Đàn chim đã sử dụng trí tuệ, kiến thức và kinh nghiệm tập thể để nhanh chóng xác định nguồn thức ăn Điều này dẫn đến việc nghiên cứu cách mà mô hình sinh học này có thể được áp dụng trong tính toán và phát triển thuật toán PSO Quá trình mô hình hóa này được gọi là Phỏng sinh học (Bioinspired), một khái niệm phổ biến trong nhiều lĩnh vực khoa học.
Một thuật toán được xây dựng trên việc một hình hóa các quá trình sinh học được gọi là thuật toán phỏng sinh học (Bioinspired Algorithms)
Trong bài toán tối ưu hàm số F trong không gian n chiều, mỗi vị trí được xác định bởi một điểm tọa độ n chiều Hàm F, được gọi là hàm mục tiêu (fitness function), có giá trị thực và mục tiêu là tìm điểm cực tiểu của nó trong một miền xác định Để hiểu rõ hơn, ta có thể liên hệ bài toán tìm thức ăn với việc tìm cực tiểu của hàm F, trong đó giả sử rằng số lượng thức ăn tại một vị trí tỉ lệ nghịch với giá trị của hàm F tại vị trí đó.
Một vị trí hàm F nhỏ hơn tương ứng với lượng thức ăn lớn hơn Do đó, việc xác định vùng chứa thức ăn dồi dào nhất giống như việc tìm kiếm điểm cực tiểu của hàm.
F trên không gian tìm kiếm.
Thuật toán tối ưu bầy đàn PSO
Giải thuật này duy trì một quần thể các cá thể, mỗi cá thể thể hiện khả năng giải quyết vấn đề tối ưu Trong quá trình lặp, độ thích nghi của các cá thể được xác định thông qua hàm mục tiêu.
27 thời các cá thể này sẽ "bay" trong không gian tìm kiếm để tìm ra giá trị lớn nhất hoặc nhỏ nhất của hàm mục tiêu
Giải thuật PSO bắt đầu bằng việc lựa chọn ngẫu nhiên các cá thể trong không gian tìm kiếm Tuy nhiên, nó không cung cấp kết quả tối ưu hóa chính xác, do đó không thể xác định được mức độ gần hay xa của một giải pháp khả thi so với giá trị tối ưu cục bộ hoặc toàn cục Thuật toán này sử dụng hàm mục tiêu để tính toán giá trị cho các giải pháp và đánh giá kết quả dựa trên những tính toán đó.
Gọi N là kích thước của quần thể Mỗi cá thể i của quần thể được coi là một đối tượng gắn với các đặc tính sau:
x i : Vị trí tại thời điểm hiện tại của cá thể i
v i : Vận tốc tại thời điểm hiện tại của cá thể i
p i : Vị trí tốt nhất đạt được trong lịch sử của cá thể i
Vị trí tốt nhất của cá thể i trong lịch sử di chuyển của nó là vị trí tối ưu giúp giá trị hàm mục tiêu đạt mức cao nhất Trong trường hợp mục tiêu cần tối thiểu, vị trí này sẽ là nơi mà hàm mục tiêu có giá trị thấp nhất.
Giả sử rằng trong không gian tìm kiếm D-chiều có một bầy đàn SR D gồm
Các cá thể trong không gian D-chiều có quỹ đạo được điều chỉnh tự động thông qua việc cập nhật vận tốc dựa trên kinh nghiệm bay của từng cá thể và của cả bầy đàn Vị trí của cá thể thứ i được biểu diễn bằng vector x i (x i 1 ,x i 2 , ,x iD )S.
Vecto vận tốc của cá thể i trong miền D như sau: v i (v i 1 ,v i 2 , ,v iD )S
Vị trí tốt nhất trong lịch sử của cá thể i được gọi là p best , được biểu thị như sau:
, và vị trí tốt nhất trong lịch sử của cả bầy đàn được gọi là g best được biểu thị như sau: p g (p g 1 ,p g 2 , ,p gD )
Đối với mỗi cá thể i, vận tốc bay và vị trí được cập nhật trong lần di chuyển kế tiếp như sau:
Hình 9 Quá trình cập nhật vị trí mới của các cá thể trong bầy đàn
Trong quá trình tối ưu hóa, hàm mục tiêu f được xác định với giá trị nhỏ nhất Công thức dưới đây thể hiện cách cập nhật vị trí tốt nhất trong lịch sử của các cá thể i.
w là hệ số quán tính (inertia weight)
c 1 ,c 2 tương ứng là hệ số nhận thức (cognitive parameter) và hệ số xã hội (social parameter)
r 1 ,r 2 hệ số được random trong đoạn [0,1]
Các tham số w, c1, c2 (0 ≤ w ≤ 1.2, 0 ≤ c1 ≤ 2, 0 ≤ c2 ≤ 2) được người sử dụng cung cấp, trong khi giá trị r1, r2 được chọn ngẫu nhiên mỗi khi cập nhật vị trí vận tốc mới Phương trình cập nhật vận tốc được chia thành ba thành phần, trong đó thành phần đầu tiên wv_i(t) là thành phần quán tính, giúp giữ cho cá thể di chuyển theo hướng của lần di chuyển trước Hệ số quán tính w thường có giá trị từ 0.8 đến 1.2, có khả năng điều chỉnh hướng di chuyển của cá thể.
Hệ số quán tính ảnh hưởng đến chuyển động của các cá thể trong quần thể Cụ thể, hệ số quán tính nhỏ giúp tăng tốc độ hội tụ về giá trị tối ưu, trong khi hệ số quán tính lớn hữu ích khi cần khảo sát toàn bộ không gian tìm kiếm.
Thành phần thứ hai c 1 r 1 (p i (t)x i (t)), gọi là thành phần nhận thức
Hệ thống nhận thức của cá thể hoạt động như bộ nhớ, giúp cá thể quay trở lại những khu vực trong không gian mà nó đã có kinh nghiệm tìm kiếm Hệ số nhận thức (cognitive coefficient) c1 thường được chọn với giá trị tối đa là 2, ảnh hưởng đến khoảng cách di chuyển của cá thể hướng về vị trí tốt nhất mà nó đã đạt được trong quá khứ.
Thành phần xã hội (social component) đóng vai trò quan trọng trong việc giúp cá thể di chuyển đến vị trí tối ưu trong quần thể Hệ số xã hội (social coefficient) c2 thường được chọn với giá trị tối đa là 2, ảnh hưởng đến khoảng cách di chuyển của cá thể hướng tới vị trí tốt nhất mà nó đã đạt được trong lịch sử di chuyển của cả bầy đàn.
Giá trị ngẫu nhiên r1 và r2 trong các thành phần nhận thức và xã hội giúp điều chỉnh tính ngẫu nhiên trong quá trình cập nhật vận tốc mới Để ngăn chặn các cá thể di chuyển ra ngoài giới hạn không gian tìm kiếm, chúng ta áp dụng kỹ thuật vận tốc kẹp, giới hạn vận tốc tối đa cho các cá thể Trong không gian tìm kiếm có giới hạn [−x max, x max], vận tốc kẹp sẽ kiểm soát vận tốc di chuyển trong khoảng [−v max, v max], với v max = k × x max, trong đó k là hệ số vận tốc kẹp.
Trong nhiều trường hợp tối ưu, không gian tìm kiếm không đối xứng quanh điểm 0, dẫn đến việc phạm vi [−x max, x max] không xác định không gian tìm kiếm Khi đó, không gian tìm kiếm sẽ được giới hạn bởi [x min, x max] Từ đó, ta có thể xác định v max bằng công thức v max = k × (x max - x min) / 2.
Sau khi tính toán vận tốc của cá thể bằng công thức (3), vị trí mới của cá thể sẽ được cập nhật theo công thức (4) Quá trình này sẽ lặp lại cho đến khi đạt được điều kiện dừng, phụ thuộc vào mục đích sử dụng của thuật toán Nếu thuật toán nhằm tìm vị trí tối ưu toàn cục sau một số lần nhất định, điều kiện dừng được xem là thỏa mãn khi kết quả không cải thiện Ngược lại, nếu đã biết trước kết quả, sau một số vòng lặp (ví dụ 500), nếu sai khác giữa giá trị hàm mục tiêu và giá trị tối ưu nhỏ hơn ngưỡng đã chọn (chẳng hạn 0.001), ta coi đó là hội tụ; nếu không, sẽ không được xem là hội tụ.
Như vậy để sử dụng thuật toán PSO giải bài toán tối ưu với hàm mục tiêu )
( x 1 x 2 x nx f cần thực hiện các bước như sau:
Bước đầu tiên trong phương pháp là thiết lập các tham số ban đầu, bao gồm N, đại diện cho số lượng cá thể khởi tạo ban đầu của bầy đàn, và nx, là số lượng biến có trong hàm mục tiêu.
Bước 2: Nếu điều kiện dừng được thỏa mãn thì kết thúc, không thỏa mãn thì thực hiện bước 3
Bước 3: Khởi tạo quần thể ban đầu trong không gian nx – chiều
Bước 5: Xác định vị trí cục bộ tốt nhất của cá thể là rất quan trọng Nếu điều kiện f(xi) < f(pi) được thỏa mãn, ta sẽ cập nhật vị trí tốt nhất trong lịch sử của cá thể i, với xi là vị trí hiện tại và pi là vị trí tốt nhất trước đó.
Bước 6: Xác định vị trí toàn cục tốt nhất, tức là vị trí tối ưu của cả bầy đàn, bằng cách gán p g = p i, trong đó p g đại diện cho vị trí tốt nhất của bầy đàn và được chọn từ tất cả các giải pháp của các cá thể.
Bước 8: Nếu i n s quay trở lại bước 3, không thỏa mãn điều kiện thì thực hiện bước 9
Bước 10: Cập nhật vận tốc cho cá thể:
Bước 11: Cập nhật vị trí mới cho cá thể:
Bước 13: Nếu i n s , đi tới bước 10, không thì thực hiện bước 2
PHƯƠNG PHÁP TỐI ƯU MULTIOBJECT GENETIC
Giới thiệu
MOGA là phương pháp tối ưu đa mục tiêu dựa trên giải thuật di truyền (Genetic Algorithms - GA), được ứng dụng rộng rãi trong nhiều lĩnh vực kinh tế và kỹ thuật Đặc biệt, phương pháp này đã được tích hợp vào modul tối ưu của phần mềm mô phỏng số ANSYS, giúp nâng cao độ chính xác trong việc giải quyết các bài toán tối ưu hóa.
Trong đời sống thực, nhiều vấn đề chứa đựng mục tiêu tối ưu hóa như giảm chi phí nhưng vẫn đảm bảo hiệu suất và độ an toàn cao Đây là thách thức lớn cho các nhà nghiên cứu, bởi trong tối ưu đa mục tiêu, các mục tiêu thường mâu thuẫn với nhau Do đó, việc tối ưu cho một mục tiêu có thể dẫn đến kết quả không đạt yêu cầu cho mục tiêu khác Làm thế nào để giải quyết vấn đề này?
Có hai phương pháp chính để giải quyết vấn đề tối ưu hóa đa mục tiêu Phương pháp đầu tiên là kết hợp các hàm mục tiêu đơn lẻ thành một hàm tổng hợp, nhưng việc lựa chọn các hàm utility hoặc trọng số phù hợp thường rất khó khăn ngay cả với các chuyên gia Phương pháp thứ hai là tìm kiếm một tập hợp các giải pháp gọi là Bộ Pareto tối ưu, đáp ứng các mục tiêu mà không bị chi phối bởi giải pháp nào khác Kích thước của Bộ Pareto tối ưu thường tăng lên khi số lượng mục tiêu gia tăng, và phương pháp này được ưa chuộng hơn vì tính linh hoạt và khả năng đáp ứng đa dạng các mục tiêu.
Bộ Pareto tối ưu là giải pháp quan trọng cho bài toán, mang lại tính thực tiễn cao hơn Tuy nhiên, việc tìm ra Bộ Pareto tối ưu không phải là điều dễ dàng Các nhà khoa học đã nghiên cứu và phát triển giải thuật di truyền GA với những cải tiến mới để giải quyết thách thức này.
Tối ưu hóa đa mục tiêu
Quyết định từ nhà sản xuất nhằm tối ưu hóa K mục tiêu không liên quan và không có ưu tiên rõ ràng giữa các mục tiêu này Để duy trì tính tổng quát, tất cả các mục tiêu được xem như là dạng tối thiểu hóa; một mục tiêu tối thiểu hóa có thể chuyển đổi từ dạng tối đa hóa bằng cách sử dụng giá trị âm của nó Vấn đề đặt ra là quyết định tối thiểu hóa đa mục tiêu với K mục tiêu khác nhau.
Cho không gian n – chiều quyết định giá trị vector x x 1 , ,x n trong miền tìm kiếm X , tìm một vector x * làm cho K hàm mục tiêu đạt giá trị nhỏ nhất
(x * z 1 x * z x * z k Miền tìm kiếm X được xác định bởi một số điều kiện ràng buộc sau g j (x * )b j j 1, m
Trong thực tế, các mục tiêu tối ưu được xem xét có sự mâu thuẫn với nhau
Việc tối ưu hóa cho một mục tiêu cụ thể thường không đáp ứng được mong đợi của các mục tiêu khác Do đó, việc tìm kiếm một giải pháp hoàn hảo cho nhiều mục tiêu cùng lúc là điều không khả thi Một cách tiếp cận hợp lý cho vấn đề đa mục tiêu là xác định một tập hợp các giải pháp có khả năng đáp ứng các mục tiêu ở mức độ nhất định mà không bị ảnh hưởng bởi bất kỳ giải pháp nào khác.
Nếu tất cả các hàm mục tiêu đều ở dạng tối thiểu hóa, một giải pháp khả thi x được coi là chi phối giải pháp khả thi y (x y) nếu và chỉ nếu tất cả các giá trị hàm mục tiêu của y không lớn hơn của x (z_i(y) ≤ z_i(x) với i = 1, ,n) và ít nhất một hàm mục tiêu j thỏa mãn điều kiện z_j(x) < z_j(y) Một giải pháp được xem là Pareto optimal khi nó không bị chi phối bởi bất kỳ giải pháp nào khác trong miền giải pháp Giải pháp Pareto optimal không thể được cải thiện hơn nữa.
Mọi mục tiêu đều cần được thiết lập sao cho không làm giảm chất lượng của ít nhất một mục tiêu khác Tập hợp tất cả các giải pháp khả thi không bị ảnh hưởng trong miền X được gọi là Bộ.
Pareto optimal là khái niệm quan trọng trong tối ưu hóa, trong đó các giá trị của hàm mục tiêu tương ứng với bộ Pareto optimal được gọi là Pareto front Trong nhiều tình huống, số lượng giải pháp Pareto optimal có thể rất lớn, thậm chí là vô hạn.
Mục tiêu của thuật toán tối ưu đa mục tiêu là xác định các giải pháp trong Bộ Pareto optimal Tuy nhiên, việc xác định toàn bộ Bộ Pareto optimal cho nhiều bài toán đa mục tiêu thường không khả thi do kích thước của nó Thêm vào đó, trong nhiều bài toán, đặc biệt là bài toán tổ hợp tối ưu hóa, các giải pháp tính toán có thể không khả thi Do đó, một phương pháp thực tiễn để giải quyết bài toán tối ưu hóa đa mục tiêu là tìm kiếm một bộ giải pháp đại diện cho Bộ Pareto optimal khả thi, được gọi là bộ giải pháp tốt nhất đã biết (best-known Pareto set) Để đạt được điều này, tối ưu đa mục tiêu cần tuân thủ ba tiêu chí quan trọng.
Best – known Pareto front phải có giá trị gần như là Pareto front Lý tưởng nhất, Bộ Best – known Pareto nên là tập hợp con của Bộ Pareto optimal
Bộ Best – known Pareto cần được phân bố đồng đều và đa dạng hơn trên Pareto front, nhằm cung cấp cho nhà sản xuất cái nhìn chính xác về các trade-offs.
Để nắm bắt toàn bộ hình ảnh của Pareto front, cần tìm kiếm các phương án tại các giới hạn của không gian tìm kiếm Trong một khoảng thời gian tính toán nhất định, tiêu chí đầu tiên được đáp ứng tốt nhất khi tập trung vào một khu vực đặc biệt của Pareto front Ngược lại, mục tiêu thứ hai yêu cầu nỗ lực tìm kiếm trên toàn bộ Pareto front Mục tiêu thứ ba nhằm mở rộng Pareto front để khám phá các giải pháp mới.
Thuật giải di truyền
Thuật giải di truyền và các thuật toán tiến hóa được xây dựng dựa trên quan niệm rằng tiến hóa tự nhiên là quá trình tối ưu nhất Quan niệm này có thể coi là một tiên đề đúng, phù hợp với thực tế rằng thế hệ sau thường tốt hơn thế hệ trước Tiến hóa tự nhiên diễn ra qua hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên Trong quá trình này, các cá thể mới được sinh ra để thay thế thế hệ cũ, và những cá thể nào thích ứng tốt với môi trường sẽ tồn tại, trong khi những cá thể không thích ứng sẽ bị đào thải.
Sự thay đổi môi trường không chỉ là động lực chính cho quá trình tiến hóa mà còn là yếu tố mà tiến hóa có thể tác động trở lại, từ đó góp phần làm biến đổi môi trường sống.
Các cá thể mới sinh ra trong quá trình tiến hóa nhờ sự lai ghép giữa các thế hệ cha mẹ, mang theo những tính trạng di truyền và có thể xuất hiện những tính trạng mới do đột biến Di truyền và đột biến đóng vai trò quan trọng trong tiến trình tiến hóa, mặc dù đột biến xảy ra với xác suất thấp hơn Các thuật toán tiến hóa mô phỏng bốn quá trình cơ bản: lai ghép, đột biến, sinh sản và chọn lọc tự nhiên, mặc dù có những điểm khác biệt trong cách thức thực hiện.
Sự phổ biến của GA được thúc đẩy bởi các yếu tố sau:
Tiến hóa là một phương pháp mạnh, thành công cho sự thích nghi bên trong các hệ thống sinh học
GA có khả năng khám phá các không gian giả thuyết phức tạp với nhiều phần tử tương tác, nơi mà tác động của từng phần tử đến độ thích nghi tổng thể là rất khó để mô hình hóa.
Thuật giải GA có thể được thực hiện song song và có thể tận dụng thành tựu của phần cứng máy tính
4.3.2 Các thành phần của một thuật giải di truyền
Một thuật giải di truyền (hay một chương trình tiến hóa bất kỳ) giải một bài toán cụ thể phải gồm năm thành phần sau đây:
Cách biểu diễn di truyền cho lời giải bài toán
Cách khởi tạo quần thể ban đầu
Một hàm lượng giá đóng vai trò môi trường, đánh giá các lời giải theo mức độ thích nghi của chúng
Các phép toán di truyền
Sau đây ta sẽ đi vào tìm hiểu cụ thể từng thành phần này
4.3.2.1 Cách biểu diễn di truyền cho lời giải bài toán
Trong thuật giải di truyền, giá trị của các biến đầu vào x được biểu diễn dưới dạng vector nhị phân thay vì hệ thập phân thông thường Chiều dài của vector này phụ thuộc vào độ chính xác yêu cầu, với độ chính xác đến k số lẻ Biến x có giá trị trong miền D = [x min, x max].
Rõ ràng để đạt được độ chính xác như vậy thì miền D được chia thành
x max x min 10 k đoạn con bằng nhau Gọi m là số nguyên nhỏ nhất sao cho
Biến x được biểu diễn dưới dạng chuỗi nhị phân có chiều dài m, đáp ứng các yêu cầu về độ chính xác Công thức tính giá trị thập phân cho mỗi chuỗi nhị phân của biến x được trình bày như sau:
Trong đó decimal() là giá trị thập phân của chuỗi nhị phân đó
Trong trường hợp tổng quát, với n biến đầu vào, các biến này được biểu diễn lần lượt dưới dạng chuỗi nhị phân Mỗi nhiễm sắc thể (NST) sẽ tương ứng với một chuỗi nhị phân, thể hiện các giá trị của các biến đầu vào này.
45 được biểu diễn bằng chuỗi nhị phân có chiều dài
Số bit m i đại diện cho giá trị trong khoảng [x i min, x i max] Để hiểu rõ hơn về cách biểu diễn này, chúng ta sẽ xem xét một ví dụ cụ thể với biến x đầu vào có giá trị nằm trong khoảng đã nêu.
Giả sử muốn kết quả chính xác tới 4 chữ số sau dấu phẩy cho biến x Ban đầu ta thực hiện tính toán chiều dài cho biến x như sau:
Như vậy muốn độ chính xác là 4 chữ số thì phải chia [5.5;20] thành ít nhất 14.5*10000 đoạn
Do đó khi biến x được mã hóa sang hệ nhị phân thì cần phải dung 18 bit vì:
Quá trình giải mã lại (chuyển sang hệ thập phân) được thực hiện như sau:
Dưới đây là một vài ví dụ chuyển đổi giá trị của biến x từ dạng nhị phân sang thập phân: x ở dạng nhị phân x ở dạng thập phân
Bảng 2 Ví dụ chuyển đổi từ dạng nhị phận sang thập phân trong GA
Khi đầu vào có nhiều biến, chúng ta cần mã hóa từng biến tương tự như trước, sau đó kết hợp các chuỗi nhị phân thành một chuỗi duy nhất Ví dụ dưới đây sẽ minh họa cho quy trình này.
Giả sử ta có hai biến đầu vào là x và y Kết quả sau khi mã hóa cho x và y tương ứng như sau: x: 001101001011101001 y: 000111001100110100
Vậy NST của x và y là:
4.3.2.2 Cách khởi tạo quần thể ban đầu
Khởi tạo quần thể ban đầu rất đơn giản bằng cách tạo ra một quần thể các nhiễm sắc thể, mỗi nhiễm sắc thể là một vector nhị phân n bit với các bit được khởi tạo ngẫu nhiên Tuy nhiên, nếu có kiến thức về xác suất, việc áp dụng hiểu biết về sự phân phối để khởi tạo quần thể sẽ mang lại kết quả tốt hơn.
4.3.2.3 Hàm thích nghi và sự chọn lọc trong giải thuật di truyền
Hàm thích nghi (fitness) eval(v i ) của các vector nhị phân v i chính là hàm f:
Nhiễm sắc thể v biểu diễn giá trị thực x, như đã nêu trong mục 4.3.2.1, trong khi f là hàm mục tiêu Hàm thích nghi đóng vai trò như một môi trường, đánh giá độ thích nghi của từng lời giải.
Quá trình chọn lọc là việc lựa chọn quần thể mới dựa trên phân bố xác suất và độ thích nghi Để thực hiện điều này, phương pháp bánh xe Roulette được áp dụng, với các rãnh được điều chỉnh kích thước theo độ thích nghi của các cá thể Bánh xe Roulette được xây dựng để tối ưu hóa quá trình chọn lọc.
Tính độ thích nghi eval(v i ) của mỗi nhiễm sắc thể v i , i =1…N, N: Kích thước của quần thể
Tính tổng giá trị thích nghi toàn quần thể
Tính xác suất chọn p i cho mỗi nhiễm sắc thể v i :
Tính vị trí xác suất q i của mỗi nhiễm sắc thể
Tiến trình chọn lọc được thực hiện bằng cách quay bánh xe Roulette N lần; mỗi lần chọn một NST từ quần thể hiện hành theo cách sau:
Phát sinh ngẫu nhiên một số r trong khoảng [0,1]
Nếu rq 1 thì chọn NST đầu tiên v 1 ; ngược lại chọn NST thứ i sao cho i i r q q 1
N: Kích thước quần thể i = 0 F=0 Bắt đầu i
