Chia sẻ cho ae luận văn thạc sỹ công nghệ sinh học
MỞ ĐẦU
Trong thực tế, rất nhiều ngành khoa học phải giải quyết các bài toán tối ưu
đa mục tiêu đặc biệt là trong ngành kinh tế. Chẳng hạn, người chế tạo sản phẩm
thường phải đưa ra phương án sao cho vừa tiết kiệm vật liệu, chi phí sản xuất thấp
và lại muốn giá trị sản phẩm là cao nhất. Nghiên cứu giải bài toán tối ưu đa mục
tiêu là một vấn đề không đơn giản vì chưa chắc có lời giải thỏa mãn đồng thời các
mục tiêu đặt ra (thường là các mục tiêu đối nghịch như ví dụ trên) mà không vi
phạm các ràng buộc nào đó. Đã có nhiều phương pháp giải bài toán tối ưu đa mục
tiêu được đề xuất, việc nghiên cứu phát triển các phương pháp này và ứng dụng
chúng để giải quyết các bài toán thực tế là một vấn đề đang được quan tâm.
Trong nhiều bài toán tối ưu thực tế, việc trọng tâm là tìm vị trí cực tiểu toàn
cục của hàm mục tiêu giá trị thực f: E R, nghĩa là tìm điểm
*
xE
sao cho
*
( ) ( ), f x f x x E
với tập đóng
d
ER
, trong đó d là số chiều.
Đã có nhiều phương pháp tối ưu toàn cục (Global Optimization - GO) được
phát triển để giải quyết vấn đề như trên như: Mô phỏng việc luyện thép (Simulated
Annealing), Tabu search, Tính toán tiến hóa (Evolutionary computation). Về mặt lý
thuyết tổng quát, các phương pháp GO có tính hội tụ mạnh, hay ít ra về nguyên tắc
cũng dễ hiểu trong việc thực hiện và ứng dụng.
Tính toán tiến hóa (Evolutionary computation) là kỹ thuật đặc biệt trong số
các phương pháp GO. Phương pháp này làm việc trên một tập hợp những lời giải
tiềm năng, được gọi là quần thể (population) và tìm lời giải tối ưu thông qua việc
cộng tác và cạnh tranh giữa các lời giải tiềm năng. Thường được sử dụng nhất là các
thuật toán di truyền (Genetic Algorithms – GA) và Artificial Life, dựa trên sự tiến
hóa tự nhiên và cư xử xã hội. Các phương pháp này thường có thể tìm tốt nhất trong
các bài toán tối ưu phức tạp với các phương pháp tối ưu truyền thống.
Thuật toán tối ưu Particle Swarm Optimization (PSO) được R.C.Eberhat và
J.Kennedy đề nghị năm 1995. Từ lúc ra đời đến nay PSO đã được nhiều nhà khoa
học tham gia nghiên cứu, cải tiến và ứng dụng nó để giải nhiều bài toán lý thuyết và
thực tế.
Đề tài “Thuật toán bầy đàn PSO, giải thuật di truyền và ứng dụng giải các
bài toán tối ưu đa mục tiêu” nhằm tìm hiểu khả năng ứng dụng của thuật toán PSO,
GA trong việc giải quyết các bài toán tối ưu đa mục tiêu trong thực tế. Với mục đích
đó, đề tài tập trung trình bày về việc giải bài toán tối ưu bằng giải thuật PSO, GA và
thực nghiệm về khả năng ứng dụng thực tế của hai thuật toán này.
Nội dung đề tài gồm 3 chƣơng:
Chương 1: Mô hình bài toán tối ưu đa mục tiêu.
Chương 2: Cơ sở thuật toán di truyền.
Chương 3: Ứng dụng thuật toán GA, và PSO cho các bài toán thực tế.
Trong luận văn, các kết quả thực nghiệm được thực hiện bằng các chương
trình viết trên nền Matlab phiên bản 7.0.
CHƢƠNG 1
MÔ HÌNH BÀI TOÁN TỐI ƢU
Trong chương này, luận văn sẽ trình bày một số kiến thức cơ bản về mô hình
tổng quát của bài toán tối ưu hóa, việc phân loại các bài toán tối ưu và một số
phương pháp giải bài toán tối ưu đa mục tiêu, các kiến thức của chương này được
tham khảo từ các tài liệu [1,2].
1.1 Mô hình bài toán tối ƣu hóa
1.1.1 Mô hình tổng quát
Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh
hưởng đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội. Việc tìm
giải pháp tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan
trọng như việc tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các
quá trình … Nếu sử dụng các kiến thức trên nền tảng của toán học để giải quyết các
bài toán cực trị, người ta sẽ đạt được hiệu quả kinh tế cao. Điều này phù hợp với
mục đích của các vấn đề đặt ra trong thực tế hiện nay.
Bài toán tối ưu tổng quát được phát biểu như sau:
Cực đại hóa (cực tiểu hóa) hàm:
( ) ax(min) f X m
Với các điều kiện:
1 ( ) ,
ii
g X b i J
(1.1)
2 ( ) ,
jj
g X b j J
(1.2)
3 ( ) ,
kk
g X b k J
(1.3)
12 , ,..., 0.
n x x x
(1.4)
Trong đó
() fX
được gọi là hàm mục tiêu, Các điều kiện (1.1) được gọi là
ràng buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng buộc bất đẳng thức.
Các điều kiện (1.4) được gọi là ràng buộc về dấu.
12 ( , ,..., ) n X x x x
là véc tơ thuộc
không gian
n
R
. Tập các véc tơ
X
thỏa mãn hệ ràng buộc lập nên một miền
D
được
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Nghiên cứu giải thuật di truyền và ứng dụng vào bài toán tái tạo
Bài toán ứng dụng giải thuật di truyền
THUẬT TOÁN DI TRUYỀN VÀ CÁC TOÁN TỬ DI TRUYỀN
Nghiên cứu và cài đặt vài giải thuật phân cụm, phân lớp
Tổng hợp Source code đồ án cho dân Lập trình, Trang 6 Hỏi đáp
thuật toán
Đề tài Phương pháp giải các bài tập về di truyền liên kết
Thuật toán và chương trình của tin 8
MỞ ĐẦU
Trong thực tế, rất nhiều ngành khoa học phải giải quyết các bài toán tối ưu
đa mục tiêu đặc biệt là trong ngành kinh tế. Chẳng hạn, người chế tạo sản phẩm
thường phải đưa ra phương án sao cho vừa tiết kiệm vật liệu, chi phí sản xuất thấp
và lại muốn giá trị sản phẩm là cao nhất. Nghiên cứu giải bài toán tối ưu đa mục
tiêu là một vấn đề không đơn giản vì chưa chắc có lời giải thỏa mãn đồng thời các
mục tiêu đặt ra (thường là các mục tiêu đối nghịch như ví dụ trên) mà không vi
phạm các ràng buộc nào đó. Đã có nhiều phương pháp giải bài toán tối ưu đa mục
tiêu được đề xuất, việc nghiên cứu phát triển các phương pháp này và ứng dụng
chúng để giải quyết các bài toán thực tế là một vấn đề đang được quan tâm.
Trong nhiều bài toán tối ưu thực tế, việc trọng tâm là tìm vị trí cực tiểu toàn
cục của hàm mục tiêu giá trị thực f: E R, nghĩa là tìm điểm
*
xE
sao cho
*
( ) ( ), f x f x x E
với tập đóng
d
ER
, trong đó d là số chiều.
Đã có nhiều phương pháp tối ưu toàn cục (Global Optimization - GO) được
phát triển để giải quyết vấn đề như trên như: Mô phỏng việc luyện thép (Simulated
Annealing), Tabu search, Tính toán tiến hóa (Evolutionary computation). Về mặt lý
thuyết tổng quát, các phương pháp GO có tính hội tụ mạnh, hay ít ra về nguyên tắc
cũng dễ hiểu trong việc thực hiện và ứng dụng.
Tính toán tiến hóa (Evolutionary computation) là kỹ thuật đặc biệt trong số
các phương pháp GO. Phương pháp này làm việc trên một tập hợp những lời giải
tiềm năng, được gọi là quần thể (population) và tìm lời giải tối ưu thông qua việc
cộng tác và cạnh tranh giữa các lời giải tiềm năng. Thường được sử dụng nhất là các
thuật toán di truyền (Genetic Algorithms – GA) và Artificial Life, dựa trên sự tiến
hóa tự nhiên và cư xử xã hội. Các phương pháp này thường có thể tìm tốt nhất trong
các bài toán tối ưu phức tạp với các phương pháp tối ưu truyền thống.
Thuật toán tối ưu Particle Swarm Optimization (PSO) được R.C.Eberhat và
J.Kennedy đề nghị năm 1995. Từ lúc ra đời đến nay PSO đã được nhiều nhà khoa
học tham gia nghiên cứu, cải tiến và ứng dụng nó để giải nhiều bài toán lý thuyết và
thực tế.
Đề tài “Thuật toán bầy đàn PSO, giải thuật di truyền và ứng dụng giải các
bài toán tối ưu đa mục tiêu” nhằm tìm hiểu khả năng ứng dụng của thuật toán PSO,
GA trong việc giải quyết các bài toán tối ưu đa mục tiêu trong thực tế. Với mục đích
đó, đề tài tập trung trình bày về việc giải bài toán tối ưu bằng giải thuật PSO, GA và
thực nghiệm về khả năng ứng dụng thực tế của hai thuật toán này.
Nội dung đề tài gồm 3 chƣơng:
Chương 1: Mô hình bài toán tối ưu đa mục tiêu.
Chương 2: Cơ sở thuật toán di truyền.
Chương 3: Ứng dụng thuật toán GA, và PSO cho các bài toán thực tế.
Trong luận văn, các kết quả thực nghiệm được thực hiện bằng các chương
trình viết trên nền Matlab phiên bản 7.0.
CHƢƠNG 1
MÔ HÌNH BÀI TOÁN TỐI ƢU
Trong chương này, luận văn sẽ trình bày một số kiến thức cơ bản về mô hình
tổng quát của bài toán tối ưu hóa, việc phân loại các bài toán tối ưu và một số
phương pháp giải bài toán tối ưu đa mục tiêu, các kiến thức của chương này được
tham khảo từ các tài liệu [1,2].
1.1 Mô hình bài toán tối ƣu hóa
1.1.1 Mô hình tổng quát
Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh
hưởng đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội. Việc tìm
giải pháp tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan
trọng như việc tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các
quá trình … Nếu sử dụng các kiến thức trên nền tảng của toán học để giải quyết các
bài toán cực trị, người ta sẽ đạt được hiệu quả kinh tế cao. Điều này phù hợp với
mục đích của các vấn đề đặt ra trong thực tế hiện nay.
Bài toán tối ưu tổng quát được phát biểu như sau:
Cực đại hóa (cực tiểu hóa) hàm:
( ) ax(min) f X m
Với các điều kiện:
1 ( ) ,
ii
g X b i J
(1.1)
2 ( ) ,
jj
g X b j J
(1.2)
3 ( ) ,
kk
g X b k J
(1.3)
12 , ,..., 0.
n x x x
(1.4)
Trong đó
() fX
được gọi là hàm mục tiêu, Các điều kiện (1.1) được gọi là
ràng buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng buộc bất đẳng thức.
Các điều kiện (1.4) được gọi là ràng buộc về dấu.
12 ( , ,..., ) n X x x x
là véc tơ thuộc
không gian
n
R
. Tập các véc tơ
X
thỏa mãn hệ ràng buộc lập nên một miền
D
được
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Nghiên cứu giải thuật di truyền và ứng dụng vào bài toán tái tạo
Bài toán ứng dụng giải thuật di truyền
THUẬT TOÁN DI TRUYỀN VÀ CÁC TOÁN TỬ DI TRUYỀN
Nghiên cứu và cài đặt vài giải thuật phân cụm, phân lớp
Tổng hợp Source code đồ án cho dân Lập trình, Trang 6 Hỏi đáp
thuật toán
Đề tài Phương pháp giải các bài tập về di truyền liên kết
Thuật toán và chương trình của tin 8