Download miễn phí Đồ án Tối ưu hóa theo thuật toán di truyền
1.TỔNG QUAN VỀ TỐI ƯU HÓA.
1.1.KHÁI QUÁT
Tối ưu hóa (optimization) là quá trình tìm cực trị một ñại lượng nào ñó của ñối tượng
thiết kế dưới dạng hàm số và phải thỏa mãn các ràng buộc của bài toán.
Cho nên người ta hiểu lời giải tối ưu hay một bản thiết kế tối ưu là lời giải tốt nhất
hay bản thiêt kế hay nhất. Trong kỹ thuật, người ta dùng nhiều phương pháp tối ưu
hóa khác nhau ñể tìm lời giải hay nhất.
Theo cách nhìn hiện ñại, lý thuyết tối ưu hóa bao gồm tập hợp các kết quả của toán
học cơ sở kết hợp với các phương pháp số dùng ñể tìm phương án tốt nhất từ tập hợp
phương án theo một thuật giải nhất ñịnh. Hầu hết các bài toán kỹ thuật ñều có nhiều
biến cho nên việc tính toán ñể tối ưu hóa rất phức tạp ñòi hỏi rất nhiều thời gian và
trong nhiều trường hợp không thể giải ñược bằng phương pháp số thông thường mà
thiếu ñi sự hỗ trợ của máy tính.
Lý thuyết tối ưu hóa ñược phát triển mạnh do sự xuất hiện của máy tính với tốc ñộ
xử lý nhanh, ñảm bảo thực hiện các phương pháp số khác nhau ñể tối ưu hóa. Hầu
hết các phương pháp tối ưu thực chất là bất biến và có thể giải nhiều thiết kế khác
nhau. Hiện nay ñã có hàng chục phương pháp số tối ưu hóa, thể hiện dưới dạng thuật
toán tiêu chuẩn ñược xây dựng và ngày càng hoàn thiện. Cho nên nhiệm vụ của
người thiết kế là chọn phương pháp và tập hợp chương trình sao cho ñúng và hợp lý.
1.2.PHÂN LOẠI
Các phương pháp tối ưu hóa ñược phân ra thành nhiều nhóm mà mỗi nhóm lại có
phương pháp khác nhau. Chúng có thể ñược chia thành các nhóm sau ñây:
• Phương pháp tối ưu hóa bằng thống kê
• Phương pháp tối ưu bằng quy hoạch toán học
• Phương pháp tối ưu hóa liên tục
• Phương pháp tối ưu hóa gián ñoạn
• Phương pháp tối ưu hóa không có ràng buộc
Phương pháp tối ưu hóa thống kê ñược kể ñến là phương pháp lý thuyết trò
chơi và phương pháp qui hoạch thực nghiệm.
Phương pháp tối ưu hóa bằng quy hoạch toán học ñược chia thành hai nhóm
nhỏ. Phương pháp thứ nhất là phương pháp phân tích bao gồm những phương
pháp phân tích vi phân, phương pháp phân tích biến phân, nguyên tắc max
min..nhóm thứ hai là những phương pháp phân tích số bao gồm phương pháp
qui hoạch tuyến tính, phương pháp qui hoạch phi tuyến, phương pháp qui
hoạch ñộng, phương pháp qui hoạch ngẫu nhiên…
Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng
8
Trong quy hoạch tuyến tính thông dụng nhất là phương pháp ñơn hình và
phương pháp ñơn hình cải biên. Trong quy hoạch phi tuyến có thể kể tới là
phương pháp quy hoạch lồi, phương pháp quy hoạch bình phương….
Các phương pháp tối ưu hóa liên tục ñược phân lọa theo dấu hiệu như: sự tồn
tại của ràng buộc kỹ thuật, dạng cực trị, ñặc tính của phương pháp giải
o Theo dạng của hàm mục tiêu, phương pháp tối ưu hóa liên tục ñược
chia ra: phương pháp tuyến tính, phương pháp lồi, phương pháp bậc
hai và phương pháp phi tuyến.
o Theo sự tồn tại của ràng buộc kỹ thuật phương pháp tối ưu hóa liên tục
ñược chia ra: không có ràng buộc kỹ thuật và có ràng buộc kỹ thuật.
Lọai không có ràng buộc kỹ thuật có thể giải bằng phương pháp bậc
không, bậc nhất và bậc hai. Loại có ràng buộc kỹ thuật có thể giải bằng
phương pháp hàm phạt và hàm chắn.
o Theo dạng cực trị các phương pháp tối ưu hóa chia hai loại : tối ưu hóa
cục bộ và tối ưu hóa toàn bộ.
o Theo phương pháp xác ñịnh ñạo hàm thì có hai phương pháp : phương
pháp phân tích và phương pháp số. Nếu theo ñạo hàm thì chia làm ba
loại : bậc không, bậc nhất và bậc hai.
Phương pháp tối ưu hóa gián ñoạn dùng trong trường hợp biên số và hàm mục
tiêu thay ñổi một cách gián ñoạn. Các phương pháp này áp dụng rất hiệu quả
ñể giải các bài toán ñặc trưng như bài toán vận tải, bài toán tối ưu hóa số
nguyên hay bài toán dạng tổ hợp.
Phương pháp tối ưu hóa gián ñoạn có thể kể ñến như : phương pháp cắt ñứt,
phương pháp nhánh cây, phương pháp cộng ñược, phân tích quy hoạch ñộng
và phương pháp tìm kiếm ngẫu nhiên.
Các phương pháp tối ưu hóa cục bộ không có ràng buộc kỹ thuật tùy theo bậc
ñạo hàm sẽ ñược phân ra bậc không, bậc nhất và bậc hai.
• Phương pháp bậc hai nổi tiếng là phương pháp Newton.
• Phương pháp bậc nhất có mấy phương pháp chính như
phương pháp gradient, phương pháp dốc ñứng, phương
pháp metric thay ñổi. Loại bậc không một biến bao gồm:
phương pháp chia ñôi, phương pháp mặt cắt vàng,
phương pháp Phibônasi, phương pháp nội suy bậc hai….
/file/d/0Bz7Zv9 ... sp=sharing
