Ứng dụng giải thuật di truyền để giải quyết một số bài toán tối ưu trong kinh tế

Đỗ Thanh Phúc Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 209 - 213

209

ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN

TỐI ƯU TRONG KINH TẾ

Đỗ Thanh Phúc*

, Nguyễn Quỳnh Hoa,

Trần Thị Mai, Nguyễn Thị Thu Hường

Trường ĐH Kinh tế và Quản trị kinh doanh – ĐH Thái Nguyên

TÓM TẮT

Trong thực tế hiện nay hầu hết các bài toán trong sản xuất, kinh doanh hàng hóa là các bài toán tối

ưu. Đã có rất nhiều phương pháp để giải các bài toán tối ưu này nhưng việc ứng dụng các giải

thuật tính toán tiến hóa hứa hẹn nhiều triển vọng. Bài báo này trình bày một phương pháp mới để

giải bài toán tối ưu đa mục tiêu đó là dùng thuật toán giải thuật di truyền (GA-Genetic Algorithm).

Từ khóa: Tối ưu trong kinh tế, giải thuật di truyền, mã hóa số thực,...

ĐẶT VẤN ĐỀ*

Trong thực tế của sản xuất, kinh doanh hàng

hóa hiện nay việc lựa chọn cách thức, phương

án sao cho sản xuất, kinh doanh thu được lợi

nhuận tốt nhất với chi phí nhỏ nhất đưa đến

việc hình thành một số bài toán tối ưu. Đã có

nhiều phương pháp tiếp cận khác nhau nhằm

giải quyết các loại bài toán này. Nhưng các

phương pháp trước đây hay sử dụng chỉ cho

chúng ta một số rất ít phương án để lựa chọn

giải quyết vấn đề.

Nhằm khắc phục tình trạng này, gần đây việc

ứng dụng các giải thuật tính toán tiến hóa hứa

hẹn nhiều triển vọng. Khi áp dụng phương

pháp này chúng ta sẽ tìm được một tập

phương án tối ưu. Việc này giúp chúng ta chủ

động hơn trong việc lựa chọn phương án tối

ưu nhất để giải quyết vấn đề.

GIẢI THUẬT DI TRUYỀN

Giải thuật di truyền (GA – Genetic

Algorithm) là giải thuật tìm kiếm, chọn lựa

các giải pháp tối ưu để giải quyết các bài toán

thực tế khác nhau, dựa trên cơ chế chọn lọc

của tự nhiên: Từ tập lời giải ban đầu, thông

qua nhiều bước tiến hóa, hình thành tập lời

giải mới phù hợp hơn, và cuối cùng dẫn đến

lời giải tối ưu toàn cục.

Trong tự nhiên, mỗi cá thể muốn tồn tại và

phát triển phải thích nghi với môi trường.

Trong mỗi cá thể, các gen liên kết với nhau

*

Tel: 0949374386; Email: [email protected]

theo cấu trúc dạng chuỗi, gọi là nhiễm sắc thể

(NST). Mỗi NST đặc trưng cho mỗi loài và

quyết định sự sống còn của cá thể đó. Do môi

trường tự nhiên luôn biến đổi nên cấu trúc

NST cũng thay đổi để thích nghi với môi

trường và thế hệ sau luôn thích nghi hơn thế

hệ trước. Cấu trúc này có được do sự trao đổi

thông tin có tính ngẫu nhiên với môi trường

bên ngoài hoặc giữa các NST với nhau.

Từ ý tưởng đó, các nhà khoa học đã nghiên

cứu và xây dựng nên giải thuật di truyền dựa

trên cơ sở chọn lọc tự nhiên và quy luật tiến

hóa. Giải thuật di truyền sử dụng các thuật

ngữ được lấy từ di truyền học như: lai ghép,

đột biến, NST, cá thể… Ở đây mỗi cá thể

được đặc trưng bởi một tập nhiễm sắc thể,

nhưng để đơn giản khi trình bày, ta xét trường

hợp tế bào mỗi cá thể chỉ một NST. Các NST

được chia nhỏ thành các gen được sắp xếp

theo một dãy tuyến tính. Mỗi cá thể (hay

NST) biểu diễn một lời giải có thể của bài

toán. Một xử lý tiến hóa duyệt trên tập các

NST tương đương với việc tìm kiếm lời giải

trong không gian lời giải của bài toán. Quá

trình tìm kiếm phải đạt được hai mục tiêu:

• Khai thác lời giải tốt nhất.

• Xem xét trên toàn bộ không gian tìm kiếm.

Bản chất GA là một giải thuật lặp, nhằm giải

quyết các bài toán tìm kiếm dựa trên cơ chế

chọn lọc nhân tạo và sự tiến hóa của các gen.

Trong quá trình đó, sự sống còn của cá thể

phụ thuộc vào hoạt động của các NST và quá