Bài giảng Hệ thống điều khiển thông minh Chương 2: TS. Huỳnh Thái Hoàng

Moân hoïc Moân hoïc

HEÄ THOÁNG ÑIEÀU KHIEÅN THOÂNG MINH HEÄ THOÁNG ÑIEÀU KHIEÅN THOÂNG MINH

â Ñi à Khi å Tö Ñ ä

Giaûng vieân: TS. Huyønh Thaùi Hoaøng Boä moân Ñieàu Khieån Töï Ñoäng B ä Khoa Ñieän – Ñieän Töû Ñaïi hoïc Baùch Khoa TP.HCM Email: hthoang@hcmut.edu.vn Email: hthoang@hcmut edu vn Homepage: http://www4.hcmut.edu.vn/~hthoang

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 1

Chöông 2 Chöông 2

LÝ THUYẾT CƠ SỞ LÝ THUYẾT CƠ SỞ LÝ THUYẾT CƠ SỞ LÝ THUYẾT CƠ SỞ

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 2

Noäi dung chöông 2 Noäi dung chöông 2

(cid:145) Hệ mờ Hệ ờ (cid:145) Mạng thần kinh (cid:145) Giải thuật di truyền (cid:145) Giải thuật di truyền

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 3

HEÄ MÔ HEÄ MÔØ HEÄ MÔ HEÄ MÔØ

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 4

Giới thiệu phương pháp điều khiển mờ Giới thiệu phương pháp điều khiển mờ

Điều khiển mực chất lỏng dùng logic kinh điển Điề khiể

i ki h điể

hất lỏ

dù

l

LH LH

chaát chaát

g loûng nhaát möùc cao treân loûng döôùi cao möùc nhaát

ï möïc khi 1 ⎧ ⎧ ⎨ ⎨ 0 khi möïc ⎩

chat chaát chaát

long loûng tren treân möc möùc loûng döôùi möùc

thap thaáp nhat nhaát thaáp nhaát

1 khi khi möïc möc 1 ⎧ ⎧ ⎨ 0 khi möïc ⎩

(1)

neáu LL LH neáu

1 0

sang 0 sang 1

• Boä ñieàu khieån logic kinh ñieån ⎧ ⎧ ,1 chuyeån töø å ⎨ töø 0, chuyeån ⎩

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 5

Giới thiệu phương pháp điều khiển mờ Giới thiệu phương pháp điều khiển mờ

Điều khiển mực chất lỏng dùng logic mờ Điề khiể ờ hất lỏ

dù

l

i

V1 V1

Giaù trò ñaët Sai soá

Möïc chaát loûng

(2)

lôùn soá thì goùc so soá nho nhoû thì thì goc goùc

V1 môû lôùn nho V1 mô môû nhoû V1

• Ngöôøi vaän haønh neáu sai ⎧ ⎪ ⎨ neu sai sai neáu ⎪⎩ ⎪⎩

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 6

Giới thiệu phương pháp điều khiển mờ Giới thiệu phương pháp điều khiển mờ

(cid:145) Phương án điều khiển 1: PLC (Programmable Logic Controller)

ề

ể

(cid:145) Phương án điều khiển 2: FLC (Fuzzy Logic Controller)

⇒ Phương pháp điều khiển mờ là phương pháp điều khiển bắt chước

quá trình xử lý các thông tin không rõ ràng và ra quyết định điều

khiển của con người.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 7

Các ứng dụng của phương pháp điều khiển mờ Các ứng dụng của phương pháp điều khiển mờ

Ứ d

điề khiể độ

h i

đầ

iê

(cid:145) Ứng dụng đầu tiên: điều khiển động cơ hơi nước (Mamdani, 1974) ớ (M d i 1974) (cid:145) Càng ngày có càng nhiều hệ thống điều khiển trong công nghiệp và

dân dụng áp dụng phương pháp điều khiển mờ. dân dụng áp dụng phương pháp điều khiển mờ. (cid:142) Điều khiển hệ thống thắng và tăng tốc của xe lửa, hệ thống lái

(cid:142) Điều khiển robot (cid:142) Điều khiển máy giặt, máy ảnh tự động,...

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 8

Cơ sở toán học của phương pháp điều khiển mờ Cơ sở toán học của phương pháp điều khiển mờ

Phan loaïi mô Phaân loai môø

Nhaän daïng môø

Lyù thuyeát äp taäp môø

Logic môø vaø ä suy luaän môø

Ñieàu khieån môø

Ño löôøng môø

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 9

Khái niệm tập hợp mờ Khái niệm tập hợp mờ

Taäp roõ

Taäp môø

~ A

A A

χA(x)

)(~ xAμ

2 2

6 6

2 2

6 6

x x

• Taäp roõ coù bieân roõ raøng • Taäp roõ ñöôïc ñònh nghóa

thoâng qua haøm ñaëc tröng ø

• Taäp môø coù bieân khoâng roõ raøng • Taäp môø ñöôïc ñònh nghóa thoâng qua haøm lieân thuoäc i

ø

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 10

ĐịĐịnh ngh

nh nghĩĩa ta tậập hp hợợp mp mờờ

~ ~ A

(cid:145)Tập mờ

xác định trên tập cơ sở X là một tập hợp mà mỗi phần tử

ầ

của nó là một cặp giá trị

là ánh

, trong đó x∈X và

x ,(

~ x (

))

ỗ )(~ xAμ

Aμ

xạ:

:)(~

]1,0[

aXxAμ

(cid:145) Ánh xạ

được gọi là hàm liên thuộc của tập mờ

~ A

)(~ xAμ

(cid:145) Hàm liên thuộc đặc trưng cho độ phụ thuộc của một phần của bất ~ A

. Nói cách khác, tập mờ xác định

ỳ kỳ thuộc tập cơ sở X vào tập mờ

, ập

ập

ộ

ị

bởi hàm liên thuộc của nó.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 11

Các dạng hàm liên thuộc Các dạng hàm liên thuộc

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 12

Các dạng hàm liên thuộc Các dạng hàm liên thuộc

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 13

Các phép toán trên tập mờ Các phép toán trên tập mờ

PHEP GIAO PHEÙP GIAO

coù cuøng cô sôû X laø moät taäp

~ Giao cuûa hai taäp môø A

~ vaø B

x )(

x )}(

môø xaùc ñònh treân cô sôû X coù haøm lieân thuoäc: ~ ~ ~ BA { x : ( ∩ μμ ~ B

~ A

~~ BA ∩

Toaùn töû T coù theå laø pheùp MIN (cöïc tieåu), PROD (tích),…

Giao của hai tập mờ dùng toán tử MIN Giao của hai tập mờ dùng toán tử MIN

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 14

Các phép toán trên tập mờ Các phép toán trên tập mờ

Ô

PHEP HÔÏP Ù ~ Hôïp cuûa hai taäp môø A

~ vaø B

coù cuøng cô sôû X laø moät taäp môø

x )(

})( x

xaùc ñònh treân cô sôû X coù haøm lieân thuoäc: ~ ~ { BA x ( ∪ μμ ~ B

~ A

~~ BA ∪

Toaùn töû S coù theå laø MAX (cöïc ñaïi), BSUM (toång bò chaën), …

Hợp của hai tập mờ dùng toán tử MAX Hợp của hai tập mờ dùng toán tử MAX

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 15

Các phép toán trên tập mờ Các phép toán trên tập mờ

PHEP BU Ø Ù ~ Buø cuûa taäp môø A

ò

ä

ñònh nghóa treân taäp cô sôû X laø moät taäp môø xaùc ñònh treân cô sôû X coù haøm lieân thuoäc xaùc ñònh bôûi bieåu thöùc:

~ A

x 1)(

x )(

−=

μ ~ A

~ A

x x

Pheùp buø cuûa taäp môø

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 16

Biến ngôn ngữ và giá trị ngôn ngữ Biến ngôn ngữ và giá trị ngôn ngữ

Giaù trò ngoân ngöõ laø moät taäp môø.

Membership

cao

thaáp

0.5

100

40 Percent full Haøm lieân thuoäc cuûa hai taäp môø moâ taû hai giaù trò ngoân ngöõ "cao", "thaáp"

Bieán ngoân ngöõ laø bieán chæ nhaän caùc giaù trò ngoân ngöõ.

Thí duï: Bieán ngoân ngöõ “möïc chaát loûng” coù theå nhaän hai giaù

trò ngon ngö la thap va cao trò ngoân ngöõ laø “thaáp” vaø “cao”

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 17

Mệnh đề mờ Mệnh đề mờ

, laø phaùt bieåu coù chöùa thoâng tin khoâng roõ raøng.

- "Nhieät ñoä" laø "cao" - "Möc chaát loûng" laø "thaáp" p - "Vaän toác" laø "trung bình",…

ÑÒNH NGHÓA ~ Meänh ñeà môø, kyù hieäu P Trong kyõ thuaät, caùc phaùt bieåu sau ñaây laø caùc meänh ñeà môø: ⇒ Meänh ñe mô la phat bieu co daïng: ⇒ Meänh ñeà môø laø phaùt bieåu coù dang:

"bieán ngoân ngöõ " laø "giaù trò ngoân ngöõ ".

~ ~ AxP : ∈ AxP

∈

Veà maët toaùn hoïc, meänh ñeà môø laø bieåu thöùc:

ñaëc tröng cho giaù trò ngoân ngöõ trong meänh ñeà môø.

~ Taäp môø A

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 18

MMệệnh nh đềđề mmờờ

~ (PT

)

~ laø giaù trò thaät cuûa meänh ñeà môø P ~ PT ( ( PT

~ x )( )( x

) )

GIAÙ TRÒ THAÄT CUÛA MEÄNH ÑEÀ MÔØ Khaùc vôùi meänh ñeà kinh ñieån chæ coù hai khaû naêng sai hoaëc ñuùng g (0 hoaëc 1), giaù trò thaät cuûa meänh ñeà môø laø moät giaù trò baát kyø naèm trong ñoaïn [0,1]. Goïi

Aμ= μ

~ ~ AxP

Bieåu thöùc treân cho thaáy "ñoä ñuùng" cuûa meänh ñeà

∈ baèng

~ ñoä phuï thuoäc cuûa x vaøo taäp môø A

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 19

Các phép toán trên mệnh đề mờ Các phép toán trên mệnh đề mờ

PHEÙP PHUÛ ÑÒNH ~ ~ AxP : ∈ . AxP ∈ . Cho meänh ñe mô Cho meänh ñeà môø ~ Phuû ñònh cuûa meänh ñeà P laø meänh ñeà : ~ ~ AxP ∉

~ PT (

~ x )(

−=

Giaù trò thaät cuûa meänh ñeà phuû ñònh: 1) 1) Aμ−=

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 20

Các phép toán trên mệnh đề mờ Các phép toán trên mệnh đề mờ

~ ~ BxQ

~ ~ AxP ∈ ,

∈ laø meänh ñeà

PHEÙP HÔÏP Hôïp cuûa hai meänh ñeà môø xac ñònh bôi xaùc ñònh bôûi

~ Bx ∈

~ ~ AxQP : ∈ hoaëc ~ ~ ~ BAxQP : ∪∈

~ ∨ ~ ∨ Q

⇒ Giaù trò thaät cuûa meänh ñeà hôïp laø: ~ ~ QPT x ( )(

)

∨

~~ BA∪

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 21

Các phép toán trên mệnh đề mờ Các phép toán trên mệnh đề mờ

~ ~ BxQ

~ ~ AxP ∈ ,

∈ laø meänh ñeà

PHEÙP GIAO Giao cuûa hai meänh ñeà môø xaùc ñònh bôûi

~ Bx ∈

~ ~

~ ~ AxQP : ∈ vaø ~ ~ ~ ~ ~ BAxQP : ∩∈

∧ ∧ ⇒ Giaù trò thaät cuûa meänh ñeà giao laø: ~ ~ QPT QPT x )( ( ( )(

) )

∧

~~ BA∩

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 22

Các phép toán trên mệnh đề mờ Các phép toán trên mệnh đề mờ

PHEÙP KEÙO THEO (IMPLICATION) Meänh ñeà keùo theo:

~ Ax ∈ thì

~ Bx ∈ ∈ ñöôïc goïi laø meänh ñeà ñieàu kieän vaø

ä h ñ à k á l

ä

~ ~ QP → Neáu : ~ ~ AxP trong ñoù meänh ñeà ~ ~ BxQ : ∈ ñöôïc goïi laø meänh ñeà keát luaän. h ñ à Q meänh ñeà i l ø ñ Giaù trò thaät cuûa meänh ñeà keùo theo ñöôïc xaùc ñònh bôûi toaùn töû

I (Implication). I (Implication)

~ PT (

~ Q

))

(

)

~ B

I ( A μμ=→ Caùc toaùn töû I thöôøng söû duïng ñeå xaùc ñònh giaù trò thaät cuûa

meänh ñeà keùo theo MIN vaø PROD.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 23

Qui tắc mờ Qui tắc mờ

ä h ñ à k át l

ä h ñ à

ôø T

l ø

Qui taéc môø laø phaùt bieåu neáu−thì, trong ñoù meänh ñeà ñieàu kieän vaø meänh ñeà keát luaän laø caùc meänh ñeà môø. Trong meänh ñeà ñieàu kieän ä h ñ à ñi à ki ä coù theå coù caùc pheùp giao, pheùp hôïp hoaëc pheùp phuû ñònh.

Thí duï phaùt bieåu sau ñaây laø moät qui taéc môø: neáu x1 laø

~ A vaø x2 laø 1

~ ~ A thì y laø B 2

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 24

HHệệ qui t

qui tắắc mc mờờ

Heä qui taéc môø goàm nhieàu qui taéc môø. Thí duï heä k qui taéc môø ñoái vôùi n bieán ngoõ vaøo coù daïng nhö sau:

g ~ B 1 ~ B 2

g ~ nx laø A vaø … vaø 1,1 ~ A vaø … vaø nx laø 2,1

~ nA thì y laø ~ nA thì y laø

thì y laø

r1: neáu x1 laø r2: neáu x1 laø … rk: neáu x1 laø

~ kB

vaø … vaø nx laø

~ kA ,1

~ knA ,

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 25

Suy luậận mn mờờ Suy lu

Giaû söû chuùng ta coù qui taéc môø: ~ ~ neu x la A thì y la B neáu x laø A thì y laø B ~ Neáu bieát ngoõ vaøo x laø A′ thì coù theå suy ra giaù trò ngoõ ra y laø ~ ñöôïc khoâng? Neáu ñöôïc thì B′

ñöôïc tính baèng caùch naøo? ~ ~ ~ ~ thì y laø B neáu x laø A ~ x laø A′ ~ y laø B′ y la B ? ?

ñöôïc goïi laø

~ Caâu traû lôøi laø ñöôïc. Quaù trình suy ra giaù trò B′

~ B′ söï suy luaän môø .

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 26

g pháp suy diễn MAX--MINMIN

PhPhươươnng pháp suy diễn MAX

)

) thì (y laø

~ kA1

~ kB

Xeùt qui taéc thöù k cuûa moät heä qui taéc môø: ~ kA2 ) vaø ( x2 laø ~ A′ , tìm y. 2

rk: neáu (x1 laø ~ A′ vaø x2 laø 1

Giaû söû ngoõ vaøo x1 laø Ngoõ ra y tính theo phöông phaùp suy dieãn MAX−MIN nhö sau:

~ kB

~ A′ 2

~ kA2

~ kA1

~ A′ 1

Neáu

thì

vaø

α1k α1k

α2k α2k

βk β

~ B′ kB

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 27

PROD Phương pháp suy diễn MAX--PROD Phương pháp suy diễn MAX

)

) thì (y laø

~ kA1 k1

~ kB k

Xeùt qui taéc thöù k cuûa moät heä qui taéc môø: ~ kA2 ) vaø ( x2 laø k2 ~ A′ , tìm y. 2

rk: neáu (x1 laø ~ A′ vaø x2 laø 1

Giaû söû ngoõ vaøo x1 laø Ngoõ ra y tính theo phöông phaùp suy dieãn MAX−PROD nhö sau:

~ kB

~ kA1

~ A′ 1

~ A′ 2

~ kA2

Neu Neáu

thì thì

va vaø

α2k α

~ B′ kB

α1k

βk

x'2

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 28

Suy luận từ hệ qui tắc mờ Suy luận từ hệ qui tắc mờ

(cid:145) Kết quả suy luận của hệ qui tắc mờ bằng hợp kết quả suy luận

của từng qui tắc. Thí dụ: xét hệ gồm 2 qui tắc mờ:

~ A ) thì (y là 21 ~ 22A ) thì (y là A ) thì (y là

~ B ) 1 ~ 2B ) B )

Giả sử ngõ vào x1 là

r1: nếu (x1 là r : nếu (x là r2: nếu (x1 là ~ A′ và x2 là 1

~ A ) và ( x2 là 11 ~ 12A ) và ( x2 là A ) và ( x là ~ A′ 2

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 29

Suy luậận tn từừ hhệệ qui t Suy lu

qui tắắc mc mờờ

~ A

~ B 1

~ A 11

~ A′ 1

~ A′ 2

Neáu

thì

vaø

1 α11

~ 1B′ ′

α21

β1

~ 2B B

~ 22A A

x'2 ~ 2A′ A′

~ ~ 12A1A′ A′ A

Neáu

thì

vaø

~ B′ 2

1 α22

α12

β2

x'2

~ B 2

~ B 1

~ B′

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 30

Hệ mờHệ mờ

Hệ môø cô baûn

Heä qui taéc

Tieàn Môø Giaûi Haäu

xöû lyù hoùa môø xöû lyù Phöông phaùp

suy dieãn

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 31

Khối tiền xử lý Khối tiền xử lý

(cid:145) Tín hiệu vào bộ điều khiển thường là giá trị rõ từ các mạch đo, bộ tiền xử lý có chức năng xử lý các giá trị đo này trước khi đưa vào bộ điều khiển mờ cơ bản. bộ điề khiể

ờ

bả (cid:145) Khối tiền xử lý có thể:

(cid:142) Lượng tử hóa hoặc làm tròn giá trị đo. (cid:142) Lượng tử hóa hoặc làm tròn giá trị đo (cid:142) Chuẩn hóa hoặc tỉ lệ giá trị đo vào tầm giá trị chuẩn. ọ (cid:142) Lọc nhiễu.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 32

Mờ hóaMờ hóa

ố

ổ

ập

′

~ A

′

1 1

+1%

−1

Khối mờ hóa có chức năng biến đổi giá trị rõ sang giá trị ngôn ế ngữ, hay nói cách khác là sang tập mờ, vì hệ qui tắc mờ chỉ có thể suy diễn trên các tập mơ.

(b)

(a)

(c)

Taäp mô ô ngo ra cua khau mô hoa Taäp môø ôû ngoõ ra cuûa khaâu môø hoùa

~ ′ khi tín hieäu vaøo x' khoâng coù sai soá, khoâng coù nhieãu (a) Taäp môø A ~ ′ khi tín hieäu vaøo x' coù sai soá ±1% (b) Taäp môø A ~ (c) Taäp môø A′ khi tín hieäu vaøo x' coù nhieãu phaân boá Gauss ′

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 33

Hệ qui tắc mờ Hệ qui tắc mờ

ắ

ễ

ể

(cid:145) Hệ qui tắc mờ có thể xem là mô hình toán học biểu diễn tri thức, kinh nghiệm của con người trong việc giải quyết bài toán dưới dạng các phát biểu ngôn ngữ. dạng các phát biểu ngôn ngữ.

(cid:145) Có hai loại qui tắc điều khiển thường dùng:

(cid:142) Qui tắc mờ Mamdani (cid:142) Qui tắc mờ Sugeno

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 34

Qui tắc Mamdani Qui tắc Mamdani

d ø

Ñ â

é ñ

l ø l

ñ à

i â

g q

ï g

)

Ñaây laø loaïi qui taéc ñöôïc duøng trong caùc öùng duïng ñaàu tieân cuûa û ñieàu khieån môø (Mamdani, 1974; Assilian, 1974; Mamdani vaø y Assilian, 1975) vaø coù daïng toång quaùt sau ñaây: ~ iA ,1

~ inA ,

)

ri: neáu (x1 laø

) vaø … vaø ( xn laø ~ iB ,1

~ imB ,

)

y ), …, (ym laø

thì (y1 laø

i i 1

k k ..1=

ôùi k l ø

, vôùi k laø soá qui taéc ñieàu khieån.

m laø soá tín hieäu ra á

i t é ñi à khi å

ôø M d

ä h ñ à

i l ø

ä

û

neáu sai soá "lôùn" vaø toác ñoä thay ñoåi sai soá "nhoû"

y Trong ñoù: n laøsoá tín hieäu vaøo Qui taéc môø Mamdani laø loaïi qui taéc môø ñaõ xeùt trong caùc chöông tröôùc. Keát luaän cuûa qui taéc ñieàu khieån môø Mamdani laø meänh ñeà môø. t öôù K át l ôø Thí duï moät qui taéc môø Mamdani nhö sau:

thì tín hieäu ñieàu khieån "lôùn"

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 35

Qui tắc Sugeno Qui tắc Sugeno

Qui taéc môø naøy ñöôïc Sugeno ñöa ra vaøo naêm 1983 vaø coù daïng toång quaùt nhö sau:

,...,

( )

,...,

)

( 1 thì

ri: neáu (x1 laø i y = 1

) vaø … vaø ( xn laø x x ( 1

~ iA ,1 i,1 ) f i ,1

~ inA in, ) ) y = f m

x ( 1

im ,

å

n , …, Keát luaän cuûa qui taéc ñieàu khieån môø Sugeno laø haøm cuûa caùc tín hieäu vaøo boä ñieàu khieån. à Neáu duøng haøm tuyeán tính ôû keát luaän thì qui taéc môø Sugeno coù daïng:

y y

b b

i ,0

xb xb ij ,

∑+ ∑ +

~ inA , ) thì A

~ iA ,1 ) vaø … vaø ( xn laø A

ri: neáu (x1 laø á

= 1

neáu e "lôùn" vaø Δe "nhoû" thì u = 4e + 2Δe ø Δ l ø ñ l ø í hi ä ñi à khi å

b ä

h ø

, n laø ,

, ( j j

j,i

Thí duï: Trong ñoù u laø tín hieäu ñieàu khieån, e laø sai soá vaø Δe laø ñaïo haøm baäc nhaát T h á ñ ù l ø cuûa sai soá n ..1= Qui taéc môø Sugeno coù theå ñôn giaûn hôn khi cho bj,i = 0, ( soá tín hieäu vaøo). Khi ñoù keát luaän cuûa qui taéc môø Sugeno laø haèng soá.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 36

Giải mờ Giải mờ

iá ị ậ lý ( iá ị õ)

ì ậ

ầ

(cid:145) Ngõ ra của bộ điều khiển mờ là các giá trị ngôn ngữ, hay nói cách khác là các tập mờ. Trong khi đó các đối tượng điều khiển chỉ “hiểu” được các giá trị vật lý (giá trị rõ), vì vậy cần phải chuyển hải h ể “hiể ” đ các tập mờ ở ngõ ra bộ điều khiển mờ sang giá trị rõ. Quá trình này gọi là giải mờ (defuzzification). gọi là giải mờ (defuzzification)

(cid:145) Các phương pháp giải mờ có thể qui vào hai nhóm chính:

Giải mờ dựa vào độ cao. (cid:142) Giải mờ dựa vào độ cao. (cid:142) Giải mờ dựa vào điểm trọng tâm.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 37

Các phương pháp giải mờ dựa vào độ cao Các phương pháp giải mờ dựa vào độ cao

μ 1

0 a y* b y

0 y* y

Phöông phaùp trung bình Phöông phap ñoä cao Phöông phap trung bình cuûa ñoä phuï thuoäc cöïc ñaïi

Phöông phaùp ñoä cao

caän phaûi cöïc ñaïi

μ 1 1

0 y* y caän traùi cöïc ñaïi

Phöông phaùp caän traùi cöïc ñaïi (hay caän phaûi cöïc ñaïi)

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 38

Các phương pháp giải mờ dựa vào trọng tâm Các phương pháp giải mờ dựa vào trọng tâm

μ 1

0 y* y

coù dieän tích lôùn nhaát

μ 1 1 .9

0 a b y

Phöông phaùp troïng taâm (COG) Phöông phaùp troïng taâm vuøng

Phöông phaùp trung bình coù troïng soá

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 39

Khối hậu xử lý Khối hậu xử lý

(cid:145) Chuyển giá trị chuẩn hóa [-1, 1] (không thứ nguyên) thành giá trị

ẩ

ể vật lý. (cid:145) Khuếch đại. (cid:145) Khuếch đại (cid:145) Mạch tích phân,…

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 40

MAÏNG THAN KINH MANG THAÀN KINH MAÏNG THAN KINH MANG THAÀN KINH

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 41

Tế bào thần kinh Tế bào thần kinh

vector tín hieäu vaøo teá baøo thaàn kinh

w =w

[ 1=x x [ [ ww ww

vector trọng số te bao than kinh vector trọng số teá baøo thaàn kinh

1 1

]T mx ]mw ]Tw

K2 K2

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 42

Hàm xử lý ngõ vào tế bào thần kinh Hàm xử lý ngõ vào tế bào thần kinh

(cid:145) Hàm tuyến tính (linear function):

ế

net

xw T

−

j xw j

j j

∑ ∑

1 =j

⎛ ⎜ ⎜ ⎜ ⎝ ⎝

⎞ ⎟ =−⎟ θ ⎟ ⎠ ⎠

(cid:145) Hàm toàn phương (quadratic function): (cid:145) Hàm toàn phương (quadratic function):

net

j xw

2 j

⎛ ∑ ⎜ ⎜ ⎝ =j 1 ⎝ 1 j =

⎞ ⎟ θ−⎟ ⎠ ⎠

(cid:145) Hàm cầu (spherical function): (cid:145) Hàm cầu (spherical function):

net

(

)

(

T ()

)

− ρθ

wx −

−

j w −

− ∑

=1j 1 j

⎛ ⎜ ⎜ ⎝ ⎝

⎞ ⎟ =−⎟ ⎠ ⎠

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 43

Hàm tác động Hàm tác động

( fa

(cid:145) Hàm tuyến tính:

ế

neáu

(cid:145) Hàm dốc bão hòa dố b

fa (

)

f 0

> 1 f ≤

≤

neáu

1 ⎧ ⎪ ⎪ f ⎨ ⎪ 0 ⎩

neáu

(cid:145) Hàm tuyến tính bão hòa

fa (

)

0 neáu f

−

≤ ≤ 1 −<

neáu

1 ⎧ ⎪ ⎨ ⎪ ⎪ ⎩

( fa fa (

) )

= =

(cid:145) Hàm dạng S đơn cực (cid:145) Hàm dạng S đơn cực

1 fe λ−+

1 1

(cid:145) Hàm dạng S lưỡng cực (cid:145) Hàm dạng S lưỡng cực

fa ( =fa ( ) ) =

− −

2 − fe λ

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 44

Các dạng hàm tác động Các dạng hàm tác động

Hàm dốc bão hòa Hàm dốc bão hòa

Hàm dạng S đơn cực Hàm dạng S đơn cực

Hàm tuyến tính

Hàm tuyến tính bão hòa Hàm dạng S lưỡng cực

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 45

Mạng truyền thẳng 3 lớp Mạng truyền thẳng 3 lớp

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 46

Biểu thức ngõ ra mạng truyền thẳng 3 lớp Biểu thức ngõ ra mạng truyền thẳng 3 lớp

(cid:145) Tổng có trọng số tín hiệu vào tế bào thần kinh thứ q ở lớp ẩn: (cid:145) Tổ

à tế bà thầ ki h thứ ở lớ ẩ

ố tí hiệ

ó t

net

xv qj

∑

= 1

a a

z z

( ( net net

) )

q q

h h

q q

xv xv qj qj

j j

∑ ∑

=j 1

(cid:145) Ngõ ra tế bào thần kinh thứ q ở lớp ẩn: ⎛ ⎜ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎟ ⎠

(cid:145) Tổng có trọng số tín hiệu vào tế bào thần kinh thứ i ở lớp ra:

net

zw iq

∑

1 =

(cid:145) Ngõ ra tế bào thần kinh thứ i ở lớp ra:

( ( net

) )

iy y i

o o

i i

o o

zw iq iq

q q

∑ ∑

1 =q

⎛ ⎜ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎟ ⎠

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 47

Thuật toán huấn luyện cập nhật trọng số mạng Thuật toán huấn luyện cập nhật trọng số mạng

(cid:145) Cập nhật trọng số lớp ra: (cid:145) Cậ

hật t

ố lớ

zk )(

k )(

)1 =+

kw ( iq

kw )( iq

ηδ+ oi

k )(

[(

))][

(

net

(

))]

−

Trong đó:

δ oi

kd )( i

ky ( i

′ o

(cid:145) Cập nhật trọng số lớp ẩn:

(

k )(

)1 =+

ηδ+

v qj

kxk )( )( j

k )(

)(

(

net

(

))

Trong đó:

δ hq

n n ⎡ ⎡ = ∑ δ ⎢ oi ⎣ 1 i =

⎤ ⎤ ′⎥ akwk )( h iq ⎦

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 48

Mạng hàm cơ sở xuyên tâm Mạng hàm cơ sở xuyên tâm

μx − q

−

2σ 2 σ q

(cid:145)Ngõ ra mạng RBF:

y i

zw iq

ew iq

l ∑ ∑ 1 q =

x

(

x

T ()

x

)

−

Trong đó

μ q

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 49

Thuật toán huấn luyện mạng RBF Thuật toán huấn luyện mạng RBF

(cid:145) Cách 1: dùng thuật toán lan truyền ngược để huấn luyện mạng RBF (cid:145) Cá h 1 dù RBF ề

th ật t á l

để h ấ l

ệ

(cid:145) Cách 2: huấn luyện mạng RBF qua 2 bước:

(cid:190) Bước 1: Xác định tâm và độ phân tán của các hàm cơ sở dùng

giải thuật phân nhóm

(cid:190) Bước 2: Xác định trọng số lớp ra dùng giải thuật bình phương

ố

tối thiểu.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 50

GIAI THUAÄT DI TRUYEN GIAÛI THUAÄT DI TRUYEÀN GIAI THUAÄT DI TRUYEN GIAÛI THUAÄT DI TRUYEÀN

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 51

Giôùi thieäu GA Giôùi thieäu GA

(cid:145) GA laø giaûi thuaät tìm kieám lôøi giaûi toái öu phoûng theo quaù trình h

i ûi h

ki á

l øi

i ûi

h û

ái GA l ø tieán hoùa cuûa sinh vaät trong töï nhieân.

(cid:145) Qua trình tien hoa: (cid:145) Quaù trình tieán hoùa:

(cid:142) Choïn loïc töï nhieân (Natural Selection) (cid:142) Lai gheùp (sinh saûn) (Crossover) (cid:142) Ñoät bieán (Mutation)

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 52

Löu ñoà giaûi thuaät Löu ñoà giaûi thuaät

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 53

Giaûi baøi toaùn duøng giaûi thuaät di truyeàn Giaûi baøi toaùn duøng giaûi thuaät di truyeàn

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 54

Giaûi baøi toaùn duøng giaûi thuaät di truyeàn Giaûi baøi toaùn duøng giaûi thuaät di truyeàn

(cid:145) Baøi toaùn toái öu hoùa cô baûn caàn giaûi trong lónh vöïc ñieàu khieån: à

ñi à khi å

l h

i ûi

ái

øi

b û

h ù min J(θ) vôi θ=[θ1, θ2,…, θn]T vôùi θ [θ θ θ]T

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 55

Maõ hoùa Maõ hoùa

h ù

hò h

(cid:145) Maõ hoùa nhò phaân (cid:145) Maõ hoùa thaäp phaân (cid:145) Ma hoa so thöïc (cid:145) Maõ hoùa soá thöc

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 56

Maõ hoùa nhò phaân Maõ hoùa nhò phaân

h i k ù hi

(cid:145) Boä gien goàm hai kyù hieäu 0 vaø 1. ø 1 (cid:145) Moãi bieán ñöôïc maõ hoùa thaønh moät ñoaïn gien, chuoãi NST goàm

nhieu ñoaïn gien. nhieàu ñoan gien

(cid:145) Giaû söû:

(cid:142) Bien θi can tìm trong ñoaïn θi min≤θi≤θimax (cid:142) Bieán θ caàn tìm trong ñoan θ ≤θ≤θ (cid:142) Bieán θi ñöôïc maõ hoùa thaønh chuoãi nhò phaân coù ñoä daøi Li (cid:145) Chieu dai cua ñoaïn gien ñöôïc xac ñònh döïa tren ñoä chính xac (cid:145) Chieàu daøi cuûa ñoan gien ñöôc xaùc ñònh döa treân ñoä chính xaùc

mong muoán töông öùng vôùi moãi bieán:

θ θ i i

max max

min min

log l

iL L

− i θ θ i ε i

⎛ ⎛ ⎜ ⎜⎜ ⎝

⎞ ⎞ ⎟ ⎟⎟ ⎠

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 57

nhò phaân Maõ hoùa nhò phaân Maõ hoùa

,...,

) )

( (

ñöô

i ûi

(cid:145) Moãi ñoaïn maõ nhò phaân ñöôïc giaûi maõ (cid:145) M ãi ñ õ s Li ,

s i 1

s i

õ hò h â 1 i − thaønh giaù trò cuûa bieán θi nhö sau:

−

θ i

sDV (

)

= θθ i

min

θ i min 1

max L 2

i −

trong ñoù DV(si) laø giaù trò thaäp phaân cuûa chuoãi si

)

j s .2

sDV ( i

iL 1L 1 − ∑

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 58

Thí duï 1 Thí duï 1

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 59

Thí duï 2: Thí duï 2:

(cid:145) Maõ hoùa nhò phaân baøi toaùn tìm cöïc trò haøm: b øi

hò h

ò h ø

h ù

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 60

thaäp phaân Maõ hoùa thaäp phaân Maõ hoùa

(cid:145) Boä gien goàm 10 kyù hieäu 0 1 2 (cid:145) Boä gien gom 10 ky hieäu 0, 1, 2,…, 9 9 (cid:145) Moãi bieán ñöôïc maõ hoùa thaønh moät ñoaïn gien: moãi ñoaïn gien

goàm coù: (cid:142) 1 gien ñeå bieåu dieãn daáu cuûa bieán (cid:142) caùc gien coøn laïi bieåu dieãn caùc chöõ soá coù nghóa

trò

gò gien

g baèng

daáu

Giaù

trò gien

baèng

− :4-0 + daáu :9-5

Giaù ⎧ (cid:145) Qui öôùc gien maõ hoùa daáu: ⎨ (cid:145) Qui öôc gien ma hoa dau: ⎨ ⎩

(cid:145) Vò trí dau cham thaäp phan cua moi gien ñöôïc löu trö ñe sö duïng (cid:145) Vò trí daáu chaám thaäp phaân cuûa moãi gien ñöôc löu tröõ ñeå söû dung

khi giaûi maõ

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 61

Thí dThí dụụ 33

(cid:145) Neáu söû duïng caùch maõ hoùa thaäp phaân vôùi 5 chöõ soá coù nghóa thì ñoaïn gien bieåu dieãn bieán θi = −56.4172 laø si = (056417), ñoàng thôøi löu tröõ vò trí daáu chaám thaäp phaân laø 2.

(cid:145) Neáu söû duïng caùch maõ hoùa thaäp phaân vôùi 4 chöõ soá coù nghóa, vò trí daáu chaám thaäp phaân laø 0 thì ñoaïn gien si = (71428), seõ ñöôïc giaûi maõ thaønh lôøi giaûi θi = 0.1428.

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 62

Thí duï 4 Thí duï 4

(cid:145) Maõ hoùa thập phaân baøi toaùn tìm cöïc trò haøm:

h â b øi

M h ù

ò h ø

hậ

2 April 2010 © H. T. Hoàng - ÐHBK TPHCM 63

Haøm thích nghi Haøm thích nghi

h h

hi d ø

ñ å ñ ù h i ù

ù h å

ù ñ

(cid:145) Haøm thích nghi duøng ñeå ñaùnh giaù caùc caù theå, caù theå naøo coù ñoä thích nghi toát hôn seõ toàn taïi qua quaù trình choïn loïc töï nhieân vaø ä coù nhieàu cô hoäi ñeå lai gheùp.

(cid:145) Thöôøng haøm thích nghi chính laø haøm caàn tìm cöïc trò hoaëc bieán

ñoåi töông ñöông cuûa haøm caàn tìm cöïc trò.

(cid:145) Caùc haøm thích nghi thöôøng duøng: )(θJ (cid:142) Baøi toaùn tìm cöïc ñaïi haøm

fitness

)(θ

)(θJ )(θJ

(cid:142) Baøi toaùn tìm cöc tieåu haøm

Bai toan tìm cöïc tieu ham

fitness

1 )( )( θ

Choïn loïc töï nhieân Choïn loïc töï nhieân

(cid:145) Nguyeân taéc cô baûn cuûa caùc phöông phaùp choïn loïc laø NST coù ñoä (cid:145) N l ø NST ù ñ ä höô

ô b û

h ù

t é

ù thích nghi caøng cao thì coù xaùc suaát choïn löïa caøng lôùn.

(cid:145) Caùc phöông phaùp choïn loïc

(cid:142) Choïn loïc tæ leä (cid:142) Choïn loïc ñaáu voøng (cid:142) Choïn loïc cat (cid:142) Ch ét l (cid:142) Choïn loïc saép haïng tuyeán tính p (cid:142) Choïn loïc saép haïng luõy thöøa.

ï g

ï (cid:145) Cöôøng ñoä choïn loïc

* MM − σ σ

trong ñoù M vaø M* laø ñoä thích nghi trung bình cuûa quaàn theå tröôùc vaø sau choïn loïc, σ2 laø phöông sai cuûa ñoä thích nghi tröôùc p choïn loïc

Choïn loïc tæ leä Choïn loïc tæ leä

(cid:145) Xac suat choïn loïc tæ leä vôi ñoä thích nghi (cid:145) Xaùc suaát chon loc tæ leä vôùi ñoä thích nghi

Choïn loïc ñaáu voøng Choïn loïc ñaáu voøng

(cid:145) Chon ra t caù theå ngaãu nhieân (t goi laø qui moâ ñaáu voøng) caù theå (cid:145) Choïn ra t ca the ngau nhien (t goïi la qui mo ñau vong), ca the naøo coù ñoä thích nghi toát nhaát trong t caù theå treân seõ ñöôïc choïn ñeå lai gheùp. Laëp laïi N laàn böôùc treân ñeå choïn ñuû N caù theå.

Choïn loïc caét Choïn loïc caét

(cid:145) Chon loc caét vôùi möùc ngöôõng T (T ∈ [0 1]) chæ coù T N caù theå (cid:145) Choïn loïc cat vôi möc ngöông T (T ∈ [0, 1]), chæ co T.N ca the toát nhaát môùi coù cô hoäi ñöôïc löïa choïn vaø xaùc xuaát choïn löïa cuûa caùc caù theå naøy nhö nhau.

Choïn loïc caét Choïn loïc caét

(

)2/

−

2 Cf

)( TI

1 T

1 2 π

∞

(

)2/

−

∫

1 2 π

Choïn loïc saép haïng tuyeán tính Choïn loïc saép haïng tuyeán tính

1(2

−

) η

1 pk = Nk N

k 1 − −1N N 1

⎡ η ⎢⎣ ⎢⎣

⎤ ⎥⎦ ⎥⎦

)( η

) − η π π

Choïn loïc saép haïng luõy thöøa Choïn loïc saép haïng luõy thöøa

kN −

p p

( (;

..1

) )

jN jN −

c = k ∑ = N N ∑ 1c

588.0) 588.0)

(I ( I α α

≈

/ ) απ α

ln( 69.3

Lai gheùp (Crossover) Lai gheùp (Crossover)

(cid:145) Lai gheùp keát hôïp ñaëc ñieåm cuûa hai NST cha meï ñeå taïo ra hai h i

i h ù k á h

û h i S

ñi å

ñ å

NST con vôùi trieån voïng cha meï toát seõ taïo ra con toát hôn.

(cid:145) Phep lai ghep thöông khong tac ñoäng ñen tat ca cac NST ma (cid:145) Pheùp lai gheùp thöôøng khoâng taùc ñoäng ñeán taát caû caùc NST maø traùi laïi chæ xaûy ra giöõa hai NST cha meï ñöôïc löïa choïn ngaãu nhieân vôùi xaùc suaát pC (goïi laø xaùc suaát lai gheùp).

ä p

(cid:145) Nguyeân taéc thöïc hieän pheùp lai gheùp laø baét caëp ngaãu nhieân hai NST trong quaàn theå sau khi ñaõ qua böôùc choïn loïc ñeå taïo ra hai ä , NST con, moãi NST con thöøa höôûng moät phaàn gien cuûa cha, moät phaàn gien cuûa meï.

(cid:145) Caùc phöông phaùp lai gheùp: (cid:142) Lai gheùp moät ñieåm (cid:142) Lai gheùp nhieàu ñieåm (cid:142) Lai ghep ñeu (cid:142) Lai gheùp ñeàu

Lai gheùp moät ñieåm Lai gheùp moät ñieåm

Lai gheùp nhieàu ñieåm Lai gheùp nhieàu ñieåm

Lai gheùp ñeàu Lai gheùp ñeàu

Ñoät bieán (Mutation) Ñoät bieán (Mutation)

h ù

ù ñ

ñ åi

hi à

bi á

(cid:145) Pheùp toaùn ñoät bieán thay ñoåi ngaãu nhieân moät hoaëc nhieàu gene cuûa moät caù theå ñeå laøm taêng söï ña daïng veà caáu truùc trong quaàn theå.

(cid:145) Ñoät bieán chæ ñöôïc pheùp xaûy ra vôùi xaùc xuaát pM thaáp. (cid:145) Caùc phöông phaùp ñoät bieán (cid:142) Ñoät bieán moät bieán (cid:142) Ñoät bieán nhieàu ñieåm

Ñoät bieán moät ñieåm Ñoät bieán moät ñieåm

Ñoät bieán nhieàu ñieåm Ñoät bieán nhieàu ñieåm

Caùc thoâng soá cuûa giaûi thuaät di truyeàn Caùc thoâng soá cuûa giaûi thuaät di truyeàn

h h ù

(cid:145) Kích thöôùc quaàn theå: 20-30 h å 20 30 (cid:145) Xaùc suaát lai gheùp: 0.8-0.9 (cid:145) Xac suat ñoät bien: 0.01-0.1 (cid:145) Xaùc suaát ñoät bieán: 0 01 0 1

Thí duï: GA tìm cöïc tieåu haøm Thí duï: GA tìm cöïc tieåu haøm

Giaûi baøi toaùn duøng giaûi thuaät di truyeàn Giaûi baøi toaùn duøng giaûi thuaät di truyeàn

Thí duï GA tìm cöïc tieåu haøm (tt) Thí duï GA tìm cöïc tieåu haøm (tt)

(cid:145) Maõ hoùa:

h ù

(cid:142) Maõ hoùa thaäp phaân (cid:142) Moi lôi giai cua bai toan tìm cöïc trò la moät caëp (x1,x2) ñöôïc (cid:142) Moãi lôøi giaûi cuûa baøi toaùn tìm cöc trò laø moät caëp (x x ) ñöôc

maõ hoùa thaønh chuoãi NST coù daïng nhö sau:

Thí duï GA tìm cöïc trò haøm (tt) Thí duï GA tìm cöïc trò haøm (tt)

(cid:145) Haøm thích nghi: hi

h h

fitness fitness =

(

1 xxf 1

(cid:145) Kích thöôùc quaàn theå laø N=20 (cid:145) Kích thöôc quan the la N 20 (cid:145) Khôûi ñoäng: theá heä ñaàu khôûi ñoäng ngaãu nhieân. (cid:145) Caùc pheùp toaùn di truyeàn:

(cid:142) choïn loïc tæ leä (cid:142) lai gheùp 2 ñieåm vôùi xaùc suaát pC=0.9 (cid:142) ñoät bieán ñeàu vôùi xaùc suaát pM=0.1 (cid:142) löu giöõ NST öu vieät trong quaù trình tieán hoùa.

Thí duï GA tìm cöïc trò haøm (tt) Thí duï GA tìm cöïc trò haøm (tt)

(cid:145) Keát quaû chaïy chöông trình: h

û h

Thí duï: GA tìm ñöôøng ñi ngaén nhaát Thí duï: GA tìm ñöôøng ñi ngaén nhaát

Hoaïch ñònh ñöôøng ñi ngaén nhaát cho robot di ñoäng giöõa M ñieåm coù toïa ñoä bieát tröôùc ñeå robot thöïc hieän moät taùc vuï naøo ñoù.

Giaûi baøi toaùn duøng giaûi thuaät di truyeàn Giaûi baøi toaùn duøng giaûi thuaät di truyeàn

Thí duï GA tìm ñöôøng ñi ngaén nhaát Thí duï GA tìm ñöôøng ñi ngaén nhaát

(cid:145) Maõ hoùa:

h ù

(cid:142) Ñaët teân cho caùc ñieåm maø robot caàn phaûi di chuyeån tôùi laø caùc

so töï nhien 1,2,…,M. soá tö nhieân 1 2 M

(cid:142) Moät lôøi giaûi cuûa baøi toaùn tìm ñöôøng ñi ñöôïc maõ hoùa thaønh

moät chuoãi NST goàm coù caùc gien laø teân cuûa caùc ñieåm

(cid:142) Chuù yù do ñöôøng ñi phaûi qua taát caû caùc ñieåm neân chuoãi NST hôp leä phaûi coù teân cuûa taát caû caùc ñieåm vaø khoâng coù gien naøo hôïp leä phai co ten cua tat ca cac ñiem va khong co gien nao coù giaù trò gioáng nhau.

Thí duï GA tìm ñöôøng ñi ngaén nhaát Thí duï GA tìm ñöôøng ñi ngaén nhaát

h h

..1

i (,

)

(cid:145) Haøm thích nghi: hi iyix ),((

))(

laø toïa ñoä cuûa ñieåm thöù

ø (cid:142) Goïi (cid:142) D la ñoä dai ñoaïn ñöông ma robot phai di chuyen. (cid:142) D laø ñoä daøi ñoan ñöôøng maø robot phaûi di chuyeån (cid:142) Ñoä daøi ñöôøng ñi töông öùng vôùi chuoãi NST goàm caùc gien

[ [

, ,

] ]

ñöôïc tính theo cong thöc: ñöôc tính theo coâng thöùc:

Mg Mg

gg , , gg 1 1

2 2

gx ([

)

gx (

2 )]

gy ([

)

gy (

2 )]

−

1 −

= ∑

i i

2 2

)

gx (

2 )]

)

gy (

2 )]

−

gx ([ 1

gy ([ 1

(cid:142) Baøi toaùn tìm cöïc tieåu ñöôøng ñi D ñöôïc chuyeån thaønh baøi toaùn

tìm cöïc ñaïi haøm thích nghi ñònh nghóa nhö sau:

fitness

1 1 D

Thí duï GA tìm ñöôøng ñi ngaén nhaát Thí duï GA tìm ñöôøng ñi ngaén nhaát

(cid:145) Choïn loïc töï nhieân:

Ch (cid:142) AÙp duïng phöông phaùp choïn loïc saép haïng tuyeán tính vôùi heä soá

5.0=−η 5.0η

choïn loïc la chon loc laø

(cid:142) Chuù yù raèng caùc phöông phaùp choïn loïc khaùc cuõng coù theå aùp

duïng

Thí duï GA tìm ñöôøng ñi ngaén nhaát Thí duï GA tìm ñöôøng ñi ngaén nhaát

(cid:145) Lai gheùp

i h ù

Thí duï GA tìm ñöôøng ñi ngaén nhaát Thí duï GA tìm ñöôøng ñi ngaén nhaát

(cid:145) Ñoät bieán

bi á

Thí duï GA tìm ñöôøng ñi ngaén nhaát Thí duï GA tìm ñöôøng ñi ngaén nhaát

(cid:145) Keát quaû û á

Ñoà thò thay ñoåi haøm thích nghi

Ñöôøng ñi ngaén nhaát

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Nguyeân taéc ño toác ñoä löu chaát duøng phöông phaùp xöû lyù aûnh û h

h á d ø

á ñ l

é ñ

û l ù

h ù

Giaûi baøi toaùn duøng giaûi thuaät di truyeàn Giaûi baøi toaùn duøng giaûi thuaät di truyeàn

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Anh haït phaûn quang chuïp 2 laàn lieân tieáp caùch nhau khoaûng thôøi h øi

ù h h

kh û

2 l à

h û

i á

AÛ h h gian Δt

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Vò trí troïng tam cac ñiem phan quang (cid:145) Vò trí trong taâm caùc ñieåm phaûn quang

(cid:145) Baøi toaùn ñaët ra laø töông öùng caùc ñieåm phaûn quang ôû 2 aûnh

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Ma hoa (cid:145) Maõ hoùa

(cid:142) Giaû söû caùc haït phaûn quang trong hai aûnh laàn löôït ñöôïc ñaùnh

soá thöù töï töø 1 ñeán n vaø 1 ñeán m (giaû söû n>m)

(cid:142) Lôøi giaûi cuûa baøi toaùn töông öùng haït phaûn quang laø caùc caëp (ai,bi), vôùi ai vaø bi laø soá nguyeân hai baát kyø thuoäc ñoaïn [1,n] vaø [1,m], ø [1 ]

(cid:142) Lôøi giaûi naøy coù theå maõ hoùa thaønh moät caù theå goàm hai chuoãi

NST nhö sau: NST nhö sau:

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Ham thích nghi: (cid:145) Haøm thích nghi:

(cid:142) Haøm thích nghi ñôn giaûn nhaát laø nghòch ñaûo toång khoaûng

caùch giöõa caùc caëp töông öùng:

1 −

fitness

ax ([

)

)]

ay ([

)

)]

−

bx ( i

by ( i

⎡ = ∑ ⎢ ⎣i ⎣ 1= 1 i =

⎤ ⎥ ⎦ ⎦

(cid:142) Haøm thích nghi ñeå yù ñeán tính chuyeån ñoäng “cuøng höôùng”

cua cac haït lan caän nhau: cuûa caùc hat laân caän nhau:

1−

fitness

−

r r d i

r r k

⎡ m l ⎡ = ∑ ∑ ⎢ ⎣ i 1 1 = =

⎤ ⎤ ⎥ ⎦

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Choïn loïc töï nhien: (cid:145) Chon loc tö nhieân:

(cid:142) AÙp duïng phöông phaùp choïn loïc saép haïng luõy thöøa ä (cid:142) Löu giöõ baûo toaøn caù theå öu vieät

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Lai ghep (cid:145) Lai gheùp

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Ñoät bien (cid:145) Ñoät bieán

Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát Thí duï GA öùng duïng trong baøi toaùn ño toác ñoä löu chaát

(cid:145) Ket qua (cid:145) Keát quaû

GIAI THUAÄT DI TRUYEN MA HOA SO THÖÏC GIAÛI THUAÄT DI TRUYEÀN MAÕ HOÙA SOÁ THÖC GIAI THUAÄT DI TRUYEN MA HOA SO THÖÏC GIAÛI THUAÄT DI TRUYEÀN MAÕ HOÙA SOÁ THÖC

Giaûi thuaät di truyeàn maõ soá thöïc Giaûi thuaät di truyeàn maõ soá thöïc

õ h ù

á thö bi å di ã

t ö ti á

l ø

(cid:145) Cach ma hoa soá thöïc: bieåu dieãn cac gien tröïc tieáp la cac soá thöïc (cid:145) C ù h á thö cho baøi toaùn toái öu hoùa thoâng soá vôùi caùc bieán naèm trong mieàn lieân tuïc, khi ñoù chuoãi NST laø vector goàm caùc thaønh phaàn laø caùc soá thöïc:

(cid:145) Phöông phaùp maõ hoùa soá thöïc coù khuyeát ñieåm laø khoâng theå söû

duïng caùc pheùp toaùn lai gheùp vaø ñoät bieán cô baûn

Lai gheùp NST maõ soá thöïc Lai gheùp NST maõ soá thöïc

Ñoät bieán NST maõ soá thöïc Ñoät bieán NST maõ soá thöïc

GIAI THUAÄT DI TRUYEN SONG SONG GIAÛI THUAÄT DI TRUYEÀN SONG SONG GIAI THUAÄT DI TRUYEN SONG SONG GIAÛI THUAÄT DI TRUYEÀN SONG SONG

Khaùi nieäm GA song song Khaùi nieäm GA song song

(cid:145) GA song song laø GA trong ñoù quaàn theå ñöôc chia ra laøm nhieàu (cid:145) GA song song la GA trong ño quan the ñöôïc chia ra lam nhieu quaàn theå con, moãi quaàn theå con ñöôïc khôûi ñoäng ngaãu nhieân vaø tieán hoùa ñoäc laäp vaø thænh thoaûng coù vaøi caù theå di cö giöõa caùc quaàn theå con h å

Khaùi nieäm GA song song Khaùi nieäm GA song song

Caùc tuøy choïn cuûa GA song song Caùc tuøy choïn cuûa GA song song

(cid:145) Ñaëc ñieåm cuûa GA song song ñöôc xaùc ñònh bôûi nhieàu tuøy chon (cid:145) Ñaëc ñiem cua GA song song ñöôïc xac ñònh bôi nhieu tuy choïn, beân caïnh tuøy choïn caùc pheùp toaùn di truyeàn taùc ñoäng leân töøng quaàn theå con thì caùc tuøy choïn sau ñaây laø ñaëc tröng cuûa GA song song: (cid:142) Caáu hình phaân boá caùc quaàn theå con. (cid:142) Cach choïn löïa cac quan the con ma giöa chung xay ra hieän (cid:142) Caùch chon löa caùc quaàn theå con maø giöõa chuùng xaûy ra hieän

töôïng di cö.

(cid:142) Caùch choïn löïa caù theå di cö vaø caù theå bò thay theá. (cid:142) Soá löôïng caù theå di cö vaø taàn suaát di cö cuûa chuùng.

Soá quaàn theå con vaø caáu hình phaân boá Soá quaàn theå con vaø caáu hình phaân boá

(cid:145) So löôïng quan the con cang nhieu hieäu qua cua GA song song (cid:145) Soá löông quaàn theå con caøng nhieàu hieäu quaû cuûa GA song song

caøng cao.

(cid:145) Caáu hình phaân boá caùc quaàn theå con ñôn giaûn nhaát laø phaân boá

theo caáu hình löôùi trong khoâng gian 2 chieàu. Vôùi caáu hình naøy, hieän töôïng di cö xaûy ra ngaãu nhieân giöõa hai quaàn theå laân caän nhau hoaëc xaûy ra tuaàn tö töø moät quaàn theå con naøy laàn löôt ñeán nhau hoaëc xay ra tuan töï tö moät quan the con nay lan löôït ñen caùc quaàn theå con khaùc trong laân caän cuûa noù.

Choïn caù theå di cö Choïn caù theå di cö

(cid:145) Muïc ñích di cö (cid:145) Muc ñích di cö

(cid:142) laøm taêng ñoä thích nghi trung bình cuûa quaàn theå maø caù theå di cö sang, (cid:142) giuùp quaàn theå nhaän caù theå di cö sang ñaûm baûo tính ña daïng. (cid:145) Coù nhieàu caùch choïn tuøy theo ta muoán caù theå di cö nhaèm muïc ñích gì,

sau ñaây laø 3 caùch ñieån hình: (cid:142) Chon caù theå coù ñoä thích nghi cao nhaát: Neáu moät quaàn theå con thöôøng Choïn ca the co ñoä thích nghi cao nhat: Neu moät quan the con thöông xuyeân nhaän caù theå di cö coù ñoä thích nghi cao, caùc caù theå naøy trôû neân caù theå noåi troäi trong quaàn theå, GA seõ taäp trung tìm kieám vaøo caùc caù the nay va do ño mat tính ña daïng, GA de rôi vao cöïc trò cuïc boä theå naøy vaø do ñoù maát tính ña dang GA deã rôi vaøo cöc trò cuc boä (cid:142) Choïn caù theå ngaãu nhieân: neáu quaàn theå nhaän moät caù theå di cö ngaãu

nhieân thì tính ña daïng ñöôïc ñaûm baûo, tuy nhieân khoâng chaéc raèng ñoä thích nghi trung bình cuûa quaàn theå ñöôïc caûi thieän. thí h th å ñöô

ûi thi ä

bì h

hi t

(cid:142) Choïn theo phöông phaùp ñaáu voøng ngaãu nhieân vôùi xaùc suaát 0.6: caùch choïn naøy ñaûm baûo tính ña daïng, ñoàng thôøi caù theå di cö coù ñoä thích nghi treân trung bình.

Choïn caù theå bò thay theá Choïn caù theå bò thay theá

Coù theå chon baèng moät trong hai caùch sau ñaây: Co the choïn bang moät trong hai cach sau ñay: (cid:145) Thay theá caù theå coù ñoä thích nghi keùm nhaát: caùch naøy laøm taêng

aùp löïc choïn loïc, quaàn theå deã rôi vaøo cöïc trò cuï boä.

(cid:145) Thay theá caù theå “thaéng cuoäc” theo caùch choïn ñaáu voøng ngaãu

nhieân vôùi xaùc suaát 0.4: caùch naøy khoâng loaïi boû caù theå keùm nhaát maø chæ loai boû coù theå coù ñoä thích nghi döôùi trung bình do ñoù ma chæ loaïi bo co the co ñoä thích nghi döôi trung bình, do ño laøm giaûm aùp löïc choïn loïc, ñaûm baûo tính ña daïng cuûa quaàn theå.

Thoâng soá di cö Thoâng soá di cö

(cid:145) So löôïng ca the di cö: Thong thöông so löôïng ca the di cö bang (cid:145) Soá löông caù theå di cö: Thoâng thöôøng soá löông caù theå di cö baèng

1, tuy nhieân cuõng coù theå choïn nhieàu hôn 1.

(cid:145) Taàn suaát di cö: Hieän töôïng di cö khoâng neân xaûy ra quaù thöôøng

xuyeân