Robust adaptive nonlinear control of uncertain time varying nonlinear systems

52(4): 69 - 71 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009

1

MỘT SỐ KỸ THUẬT ĐIỀU CHỈNH THAM SỐ TRONG GIẢI THUẬT DI TRUYỀN

Vũ Mạnh Xuân (Trường ĐH Sư phạm – ĐH Thái Nguyên),

Lê Quang Hùng, Lê Thị Thuỷ (Khoa Công nghệ thông tin – ĐH Thái Nguyên)

Tóm tắt.

Giải thuật di truyền với các toán tử chọn lọc, lai ghép, đột biến là giải thuật tìm kiếm lời giải của bài toán mô

phỏng quá trình tiến hoá tự nhiên. Bài báo này nghiên cứu và đề xuất một số kỹ thuật hiệu chỉnh tham số của giải

thuật ngay trong quá trình tiến hoá.

Mở đầu

Giải thuật di truyền (GA - Genetic Algorithm)

thực hiện việc tìm kiếm lời giải dựa trên sự mô

phỏng quá trình tiến hoá của tự nhiên. GA sử dụng

các toán tử chọn lọc (Selection), lai ghép

(Crossover), đột biến (Mutation) và các tham số

khác như kích cỡ quần thể, xác suất lai ghép, xác

suất đột biến. Tự thích nghi là một đặc tính quan

trọng của tự nhiên và lẽ tất nhiên cũng được sớm

quan tâm trong giải thuật di truyền. Điều chỉnh các

tham số của giải thuật ngay trong quá trình tiến hoá

là một trong những vấn đề được chú ý và phát triển.

Kích cỡ quần thể (Population Size) là tham số đầu

tiên cần chú ý, nếu kích cỡ quần thể quá nhỏ thì

tính đa dạng của quần thể bị hạn chế; còn nếu quá

lớn sẽ hao phí tài nguyên của máy tính và làm

chậm quá trình. Trong hầu hết các nghiên cứu về

GA người tathường chọn kích cỡ là một số cố định

trong suốt quá trình thực hiện. Gần đây, giải thuật

di truyền mã hoá số thực RCGA (Real-Coded

Genetic Algorithm) phát triển mạnh và một số giải

pháp biến đổi kích cỡ quần thể được giới thiệu [1],

[2], với cách tiếp cận chủ yếu dựa trên cơ chế định

tuổi của cá thể. Bài báo này đề xuất một vài kỹ

thuật điều chỉnh kích cỡ quần thể trong quá trình

thực hiện giải thuật dựa trên độ thích nghi trung

bình của quần thể.

1. Một số kết quả liên quan

GAVaPS (Genetic Algorithm with Varying

Population Size) được giới thiệu bởi Arabas,

Michalewicz và Mulawka năm 1994. Thuật toán

này biến đổi kích cỡ quần thể dựa trên độ tuổi của

cá thể. Cụ thể là cá thể khi sinh ra được gắn với độ

tuổi (age) và thời gian sống (lifetime), sau mỗi

bước tạo sinh, độ tuổi này được tăng lên và khi

đến ngưỡng thì cá thể đó sẽ bị đào thải [1].

APGA (Genetic Algorithm Adaptive Population

Size) được giới thiệu bởi Back, Eiben và van de

Vaart năm 2000. Thuật toán này cũng sử dụng độ

tuổi của cá thể song việc chọn lọc tạo sinh duy trì

phần tử ưu tú. Cơ chế đánh giá thời gian sống

(lifetime) của cá thể mềm dẻo hơn bởi việc đánh

giá thời gian duy trì cá thể (RLT – Remaining

LifeTime) và chiến lược chọn lọc tạo sinh có tính

tinh hoa [1], [2].

2.Thay đổi kích cỡ quần thể dựa trên độ thích

nghi trung bình

Chúng tôi đề xuất một kỹ thuật biến đổi kích

cỡ quần thể ngay trong quá trình tiến hoá dựa trên

độ thích nghi trung bình của quần thể. Với kỹ

thuật này ta sử dụng thêm một tham số là độ thích

nghi trung bình của quần thể. Độ thích nghi trung

bình của quần thể được tính theo công thức sau:

popsize

eval v

AverageFitness i

i

PopulationSize

1

trong đó PopulationSize là kích cỡ quần thể, vi

là các cá thể trong quần thể tại thế hệ hiện tại, hàm

eval là hàm lượng giá. Thuật toán cụ thể như sau:

procedure BaseOnAverageFitness{

Khởi tạo quần thể;

startpopsize=popsize;

Tính độ thích nghi của các cá thể eval (vi);

Tính AverageFitness;

While (chưa thỏa điều kiện dừng) do

Begin

Lựa chọn ngẫu nhiên 2 cá thể P1 và P2 trong quần

thể ;