1
Hà Nội-2014
2
Ngành: CÔNG NGHỆ THÔNG TIN
Chuyên ngành: KỸ THUẬT PHẦN MỀM
Mã số:60480103 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. BÙI THU LÂM
Hà Nội-2014 3
LỜI CAM ĐOAN
hoàn thành luận văn này.
5 MỤC LỤC
Trang phụ bìa Trang 2
Lời cam đoan 3
Lời cảm ơn 4
Mục lục 5
Danh mục các ký hiệu và chữ viết tắt 7
Danh mục các hình vẽ, đồ thị 9
Danh mục các bảng 11
MỞ ĐẦU 12
Chương 1. Tổng quan về quản lý dự án phần mềm 14
1.1. Định nghĩa dự án, quản lý dự án phần mềm 14
1.1.1. Dự án là gì 14
1.1.2. Thế nào là quản trị dự án 17
1.2. Vấn đề lập kế hoạch, lập lịch trong quản trị dự án phần mềm 21
1.2.1. Khái niệm về lập kế hoạch 21
1.2.2. Tự động hóa việc lập lịch 21
Chương 2. Giải thuật di truyền và các ứng dụng 24
2.1. Tổng quan về giải thuật di truyền 24
2.2. Lịch sử phát triển 25
2.3. Các bước áp dụng giải thuật di truyền 26
2.3.1. Mã hóa dữ liệu 26
2.3.2. Khởi tạo quần thể 27
2.3.3. Xác định hàm thích nghi 27
2.3.4. Quá trình lai ghép 28
4.5. Chương trình demo 67
4.5.1. Tạo mới database lưu trữ dữ liệu. 67
4.5.2. Mở database có sẵn 68
4.5.3. Quản lý dự án 69
4.5.4. Quản lý loại tài nguyên dự án 70
4.5.5. Quản lý tài nguyên dự án 71
4.5.6. Quản lý công việc 71
4.5.7. Thực hiện việc estimate các công việc dự án 74
4.5.8. Chức năng lập lịch dự án bằng giải thuật di truyền: 75
4.5.9. Các chức năng bổ trợ khác 77
4.6. Kết quả chạy chương trình 82
KẾT LUẬN 90
TÀI LIỆU THAM KHẢO 91
PHỤ LỤC 92
7
THUẬT NGỮ VIẾT TẮT
Số thứ tự
Thuật ngữ
Tên đầy đủ
1
GP
Genetic programming
2
EA
Evolutionary algorithm
3
EP
Pred
j
Tập hợp các công việc trực tiếp phía
trước của công việc j. Công việc j là
một công việc trong tập các công việc
được định nghĩa trong bảng phân rã
công việc.
2
C
pr
Bảng phân rã công việc. Ở bảng này đã
chỉ định rõ công việc nào là công việc
trực tiếp phía trước, công việc nào là
công việc sau.
3
TaskLine
Đường biểu diễn chuỗi công việc. Đây
là tập hợp các công việc đã chỉ định rõ
thứ tự thực hiện. Giả sử công việc e có
công việc trực tiếp phía trước là d, trước
công việc d có công việc trực tiếp phía
trước c. Công việc e lại có công việc
trực tiếp phía sau là f, công việc f lại có
công việc trực tiếp phía sau là g. Thì ta
có đường biểu diễn công việc e là tập
hợp các công việc theo thứ tự như sau:
c, d, e, f, g.
4
Hình 2.10 Sơ đồ quá trình tính toán của thuật toán di truyền 32
Hình 3.1 Ví dụ bảng phân rã gồm 8 công việc được đánh chỉ số từ 0 tới 7 36
Hình 3.2 Biểu diễn thứ tự công việc bằng mảng một chiều nguyên không âm 37
Hình 4.1 Mô hình các thành phần trong chương trình demo luận văn 49
Hình 4.2 Mô hình quan hệ cơ sở dữ liệu 51
Hình 4.3 Mô hình thực thể liên kết 52
Hình 4.4 Màn hình các chức năng Add-in 59
Hình 4.5 Tạo project từ trình đơn Visual studio 59
Hình 4.6 Chọn loại dự án là Project 2010 Add-in 60
Hình 4.7 Solution explorer của dự án 60
Hình 4.8 class ThisAddIn 61
Hình 4.9 Đồ thị thứ tự công việc được vẽ lại bằng phần mềm demo luận văn 66
Hình 4.10 Truy cập tính năng tạo mới database từ menu 67
Hình 4.11 Chọn tên database và lưu lại 68
Hình 4.12 Chọn mở database từ menu 68
Hình 4.13 Mở danh sách dự án từ menu 69
Hình 4.14 Danh sách dự án 69
Hình 4.15 Màn hình edit dự án 70
Hình 4.16 Màn hình tạo mới dự án 70
Hình 4.17 Vào chức năng quản trị Resource type từ menu 70
Hình 4.18 Vào chức năng quản trị Resource từ menu 71
Hình 4.19 Màn hình quản trị tài nguyên 71
Hình 4.20 Truy xuất màn hình đồ họa quản lý task từ menu 72
Hình 4.21 Màn hình quản lý task 73
Hình 4.22 Xem danh sách tasks 73
Hình 4.23 Danh sách tasks trong dự án 74
Hình 4.24 Màn hình estimate task 75
Hình 4.25 Combobox công việc 75
10
11 DANH MỤC BẢNG BIỂU
Bảng 1.1 Các hoạt động của quản lý dự án 19
Bảng 1.2 Các kế hoạch của dự án 22
Bảng 4.1 Bảng phân rã công việc dự án và kế hoạch tài nguyên 62
Bảng 4.2 Bảng loại tài nguyên 66
cónhiều biến động,khi đó vấn đề lập kế hoạch, lập lịch dự án sẽ gặp khó khăn. Người
làm kế hoạch sẽ phải tốn nhiều thời gian để tiến hành sửa đổi kế hoạch, lập lịch lại mỗi
khi có sự biến động về nhân sự (hay rộng hơn là thay đổi về nguồn lực thực hiện dự
án). Như vậy, vấn đề cấp thiết phải làm sao tự động được khâu này, để giảm thiểu sức
người cũng như nâng cao chất lượng khâu này.
Trong trí tuệ nhân tạo “Giải thuật di truyền” đã được ứng dụng rộng rãi đề giải quyết
nhiều bài toán phức tạp. Trong đó có các bài toán về lập lịch, lập kế hoạch.Việc áp
dụng giải thuật di truyền nhằm làm tối ưu hóa vấn đề lập kế hoạch và phân bổ nguồn
lực trong dự án phần mềm đã và đang được nghiên cứu cải tiến rất nhiều trên thế giới.
Trong luận văn này tôi đặt trọng tâm tìm hiểu giải thuật di truyền và áp dụng vào lập
lịch thực hiện các công việc trong dự án phần mềm với sự giới hạn về tài nguyên thực
hiện các công việc trong dự án.
Các kiến thức về lập lịch trong quản lý dự án phần mềm, kiến thức về giải thuật di
truyền, cách áp dụng giải thuật di truyền để tự động lập lịch dự án cũng như các kỹ
năng lập trình xây dựng ứng dụng hoàn chỉnh bước đầu có thể quản lý dự án và tự
động chọn lựa phương án tối ưu để lập lịch dự án được học viên trình bày chi tiết trong
luận văn vàđược chia thành 4 chương sau đây:
Chƣơng 1. TỔNG QUAN VỀ QUẢN LÝ DỰ ÁN PHẦN MỀM
Chương này giới thiệu về dự án phần mềm và quản lý dự án phần mềm. Qua chương
này ta thấy được phần mềm cũng như các tiến trình, công cụ quản lý phần mềm ngày
càng phức tạp. Do vậy cần phải tìm cách tự động hóa càng nhiều khâu trong quản lý
dự án càng tốt. Trong chương này cũng chỉ ra là có thể áp dụng giải thuật di truyền vào
quản lý dự án phần mềm ở bước lập lịch biểu, gán nguồn lực thực hiện dự án.
Chƣơng 2. GIẢI THUẬT DI TRUYỀN VÀ CÁC ỨNG DỤNG
Chương này sẽ cho người đọc một cái nhìn tổng quan về giải thuật di truyền và các
ứng dụng của nó trong thực tế, qua đó người đọc có thêm hiểu biết về các vấn đề mã
hóa giải thuật di truyền. Giúp người đọc có thể vận dụng những kiến thức ở chương
này để giải quyết các vấn đề của mình.
13
- Mỗi dự ánphải có một hoặc một số mục tiêu rõ ràng do dự ánlà một quá trình
tạo ra kết quả cụ thể.
- Mỗi dự án đều có một thời hạn nhất định, toàn bộ thời gian của dự án được chia
thành các giai đoạn: Giai đoạnkhởi đầu, giai đoạn triển khai và giai đoạn kết
thúc. Thời gian thực hiện dự án được chỉ định không được vượt quá một
khoảng thời gian nhất định (ví dụ không quá một tháng, một năm, hai năm…).
Thời gian thự hiện dự án được ước lượng thông qua các tính năng của sản phẩm
(kết quả của dự án) mà khách hàng yêu cầu và được sự đồng ý của khách hàng.
Để đảm bảo dự án hoàn thành theo đúng thời gian cho phép, bộ phận quản trị
dự án cần áp dụng các công cụ, phương pháp quản lý dự án phù hợp cho từng
loại hình dự án nhằm đảm bảo dự án hoàn thành đúng tiến độ đã đề ra.
- Mỗi dự án đều có sử dụng nguồn lực và nguồnlực này bị hạn chế. Các nguồn
lực đó bao gồm nhân lực, nguyên vậtliệu, ngân sách. Do các nguồn lực này là
hạn chế nên phải có phương pháp quản trị và sử dụng các nguồn lực này trong
dự án một cách hợp lý.
- Giữa các dự án, không có sự lặp lại hoàn toàn giữa các dự án. Ví dụ như giữa
hai dự án hoàn toàn giống nhau về sản phẩm đầu ra, quy trình phát triển nhưng
có yếu tố nhân lực vật lực hoặc thời gian triển khai dự án khác nhau, do vậy
giữa hai dự án không có sự trùng lặp hoàn toàn.
Với các dự án phần mềm thì có nhiều điểm thuận lợi hơn các dự án khác. Những điểm
thuận lợi mà dự án phần mềm có được như:
- Sản phầm của dự án dễ sửa đổi hơn sản phẩm vật chất khác. Với dự án phần
mềm khi có yêu cầu sửa đổi sản phẩm thì đội phát triển sẽ sửa đổi mã nguồn và
biên dịch thành chương trình chạy và gửi lại khách hàng. Nhưng với các sản
15
phẩm thông thường ví dụ như chiếc tivi, nếu khách muốn đổi các thông số trên
chiếc tivi này, muốn có một số tính năng mới thì rất khó có thể làm được điều
này.
- Sản phẩm phần mềm là vô hình, không cầm nắm được như các sản phẩm thông
thường. Sản phẩm phần mềm được lưu trữ trên máy tính bao gồm chương trình,
cơ sở dữ liệu và các tài liệu hướng dẫn sử dụng. Khi sử dụng sản phẩm phần
mềm cần phải có máy tính, người sử dụng sản phẩm phần mềm cũng cần phải
có một số kiến thức nhất định về công nghệ thông tin, cần phải biết cách sử
dụng máy tính.
16
- Cùng một yêu cầu nhưng không xác định duy nhất sản phẩm đầu ra. Khi mà
khách hàng yêu cầu xây dựng phần mềm thì mỗi đội phát triển sẽ cho ra một
sản phẩm khác nhau, có thể có những khác nhau về giao diện, quy trình nghiệp
vụ, tính năng sản phẩm. Những sự khác nhau này vẫn cần phải đảm bảo sản
phẩm làm ra phải thỏa mãn yêu cầu và làm hài lòng khách hàng.
- Các nguyên tắc kỹ nghệ để làm ra phần mềm hoàn toán khác với các nguyên tắc
tạo ra sản phẩm thông thường(như cơ, điện ).
- Sản phẩm phần mềm chịu nhiều yếu tố biến động hơn các sản phẩm khác, các
yếu tố biến động như công nghệ, môi trường, nghiệp vụ và nguồn lực ảnh
hưởng trực tiếp tới chất lượng phần mềm.
- Nguyên liệu đầu vào để sản xuất phần mềm cũng rất đặc trưng, nguyên liệu đầu
vào có thể là các sản phẩm phần mềm khác, các gói thư viện phần mềm, còn
một nguyên liệu rất trừu tượng đó là chất sám.
Dự án phần mềm cũng giống như các loại dự án khác về các nguyên nhân gây nên sự
thất bại của dự án. Các nguyên nhân thất bại như:
- Dự án không có tính thực tế và sản phẩm không khớp với yêu cầu khách hàng
- Dự án không hoàn thành đúng hạn dẫn đến sự không hài lòng của khách hàng
làm cho khách hàng có thể kết thúc dự án
- Chi phí dự án bị vượt quá dự toán
- Khi lập kế hoạch người có thẩm quyền đã ước tính không chính xác nguồn lực
cần thiết cho dự án
- Xác định yêu cầu hệ thống không đúng
kỹ năng nhất định để đảm bảo dự án phần mềm, và những người trong đội phát
triển cũng phải có kỹ năng ở mức độ cho phép để tham gia dự án. Đó là một
trong những nguyên nhân dẫn đến chi phí liên quan ngày càng tăng.
- Các yêu cầu của khách hàng thì càng ngày càng nhiều. Do phần mềm càng ngày
càng phức tạp, dẫn đến tính năng phần mềm nhiều và phức tạp
- Quy mô, độ phức tạp ngày càng lớn.
- Yêu cầu hiệu năng phần mềm ngày càng tăng theo sự tăng trưởng của phần
cứng và nhu cầu người dùng.
- Phần mềm ngày càng lớn, nhiều người tham gia thực hiện, vấn đề truyền thông,
quản lý ngày càng quan trọng (một ví dụ là hệ điều hành Window2000 cần đến
5.000 người tham gia).
Với những vấn đề nổi cộm ở trên ta thấy việc cấp thiết phải có những phương pháp để
quản lý các dự án phần mềm hiệu quả. Ngày nay trên thế giới các nhà hoạch định
chiến lược, các công ty lớn, các nhà nghiên cứu trong các viện, các trường đại học đã
tập chung nghiên cứu tìm tòi, cải tiến các phương pháp, quy trình, cải tiến công cụ
quản lý dự án phần mềm. Nhờ áp dùng các kết quả nghiên cứu, công cụ mới mà đã
từng bước giải quyết được các vấn đề khó khăn trên của dự án phần mềm.
1.1.2. Thế nào là quản trị dự án
Quản lý dự án là việc áp dụng kiến thức, phương pháp, kỹ thuật, công cụ và tổ chức
các hoạt động nhằm tạo ra sản phẩm đáp ứng yêu cầu đã cho. Hoạt động quản lý dự án
phần mềm bao gồm: lập kế hoạch, triển khai, theo dõi, giám sát, đánh giá và điều
chỉnh. Vòng đời chuẩn của quản lý dự án gồm 4 pha sau: Khởi tạo dự án
Quản lý dự án tập chung vào các nội dung: Quản lý công việc, quản lý tiến độ, quản lý
tài chính, quản lý nhân lực, quản lý nguồn lực, quản lý chất lượng. Việc quản lý dự án
sẽ gặp phải nhiều thách thức như thách thức nhân lực, công việc, ước lượng, tổ chức,
quản lý và kiểm soát.
- Nhân lực:Thách thức từ khâutuyển chọn(từ đâu? kỹ năng cần có là gì?), đến
khâu sử dụng (vào đâu? công việc gì?). Vàkhi dự án kết thúc, không cần dùng
tới thì phải sắp xếp nhân lực hợp lý.
- Công việc và ước lượng: Khi ước lượng công việc người quản trị cần phải xác
định đủ việc, ước lượng đúng khối lượng, chi phí nguồn lực, thời gian cần thiết
để hoàn thành công việc.
- Tổ chức và quản lý: Tùy theo tổ chức hiện có và mục tiêu cần đạt được của dự
án phần mềm mà tiến hành tổ chức bộ phận quản lý dự án phần mềm hợp lý.
Các cách tổ chức này là tạm thời, tồn tại cho đến khi dự án kết thúc. Ứng với
một dự án mà thành viên tham gia sẽ được xác lập một thẩm quyền nhất định,
và mối quan hệ giữa các thành viên cũng thay đổi theo từng dự án.
- Kiểm soát: Do công việc có nhiều thay đổi, ví dụ như thay đổi về nhân lực, thay
đổi do yêu cầu khách hàng,nên kế hoạch công việc và việc thực hiện kế hoạch
này không ổn định, luôn thay đổi. Người quản trị cần nắm thông tin kịp thời và
điều chỉnh cho phù hợp với yêu cầu thực tế, cần phải ra quyết định chính xác,
phù hợp và đạt đồng thuận cao trong nhóm.
19
- Việc quản lý qua các thể hiện, không nhìn thấy trực tiếp:Các thể hiện ở đây là
tài liệu và chương trình, chúng rất đa dạng và thiếu thước đo, các dự án phần
mềm khác nhau lại dùng các chuẩn khác nhau, việc áp dụng chuẩn tài liệu rất
vất vả và mất nhiều công sức.
- Thách thức chất lượng: Chất lượng phần mềm phụ thuộc vào rất nhiều yếu tố
như: quy trình có phù hợp với thực tế hay không và có mang lại hiệu quả
không. Công nghệ và công cụ có phù hợp với sản phẩm và môi trường hay
không. Kiểm soát thay đổi, các thay đổi có được kiểm soát thường xuyên hay
Đảm bảo hoàn thành hạng mục
công việc trong thời hạn dự kiến
-Xác định thời gian hoàn thành
công việc
- Xác định trình tự thực hiện
- Lập lịch thực hiện
-Kiểm soát thực hiện theo lịch
3
Quản lý chi phí
Đảm bảo huy động, sử dụng
ngân sách đáp ứng yêu cầu
- Lập kế hoạch huy động ngân
sách
-Ước tính chi phí
- Phân phối ngân sách
- Kiểm soát chi tiêu
4
Quản lý chất
lượng
Đảm bảo sản phẩm đạt yêu cầu
chất lượng đề ra
- Xác định các chuẩn chất
lượng, độ đo, quy trình kiểm
định
20
- Kiểm định chuẩn cho mỗi sản
phẩm
- Quản lý thay đổi chất lượng
5
- Xác định dữ liệu thông tin lưu
trữ
- Quy định hình thức báo cáo,
lưu trữ, cung cấp thông tin
8
Quản lý rủi ro
Đảm bảo ngăn ngừa và hạn chế
thiệt hại do sự cố xảy ra
- Nhận diện các rủi ro
- Xác định khả năng xuất hiện,
phân tích tác động đến dự án
- Lập kế hoạch phòng chống
- Kiểm soát, xử lý
9
Quản lý cấu hình
(và thay đổi)
Đảm bảo kiểm soát mọi thay đổi,
đồng bộ sản phẩm
- Xác định khoản mục cấu hình
- Xây dựng triển khai quy trình
- Giám sát thực hiện quy trình
và lưu trữ cấu hình, phiên bản
Ngoài các hoạt động từng mặt người quản trị dự án cần quản lý chung để phối hợp các
quản lý cụ thể để đảm bảo dự án được thực hiện tốt nhất. Trong các hoạt động trên thì
hai hoạt động: Quản lý rủi ro và quản lý cấu hình là đặc thù riêng biệt của quản lý dự
án phần mềm. Cònquản lý thời gian, quản lý chi phí, quản lý chất lượng là đặc biệt
quan trọng của quản lý dự án phần mềm.
Trong phạm vi đề tài này học viên quan tâm tìm hiểu kỹ về hoạt động Quản lý thời
gian của dự án để tìm cách áp dụng kiến thức về giải thuật di truyền áp dụng vào các
bước lập lịch dự án đảm bảo thời gian thực hiện toàn bộ dự án là tối ưu nhất. Hoạt
án cần phải có năng lực phù hợp.
- Các phần mềm dùng lại được: Thành phần đóng gói dùng được ngay vào công
việc làm dự án, các thành phần đã kiểm nghiệm tốt, có thể sửa và dùng lại
được.
- Phần cứng, công cụ phần mềm chia sẻ.
Khi lập kế hoạch người quản trị dự án phải đưa ra được các kế hoạch phục vụ cho dự
án, đó là kế hoạch công việc, kế hoạch quản lý rủi ro, kế hoạch chất lượng, kế hoạch
quản lý cấu hình, kế hoạch ngân sách, kế hoạch nguồn lực. Trong các kế hoạch này kế
hoạch công việc là khá quan trọng. Trong phạm vi luận văn này học viên quan tâm tìm
22
hiểu kỹ về kế hoạch công việc và tiến hành áp dụng giải thuật di truyền trên kế hoạch
công việc để ra được kết quả lập lịch thực hiện công việc.
Bảng 1.2 Các kế hoạch của dự án
Tên kế hoạch
Mô tả
Kế hoạch công việc
Mô tả công việc và lịch biểu thực hiện
cho sản phẩm dự án
Kế hoạch quản lý rủi ro
Xác định các rủi ro và các giải pháp
Kế hoạch chất lượng
Mô tả thủ tục và các chuẩn chất lượng
được áp dụng
Kế hoạch quản lý cấu hình
Mô tả cấu hình, thủ tục và tiến trình quản
lý cấu hình và sự thay đổi
Kế hoạch ngân sách
Chỉ ra lượng ngân sách cần theo thời gian
Việc áp dụng giải thuật này được học viên trình bày kỹ lưỡng trong các trang tiếp theo
của luận văn, các kết quả dữ liệu test trên bộ dữ liệu tự sinh cũng được học viên trình
bày để thấy được việc áp dụng giải thuật khiến khâu lập lịch này là hợp lý và là một
hướng nghiên cứu đúng đắn.
24 Chương 2. GIảI THUậT DI TRUYềN VÀ CÁC ứNG DụNG
2.1. Tổng quanvề giải thuật di truyền
Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp
thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật di
truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa
như di truyền, đột biến, chọn lọc tự nhiênvà trao đổi chéo[11].Ngày nay, giải thuật di
truyền được dùng phổ biến trong một số ngành như tin sinh học, khoa học máy tính, trí
tuệ nhân tạo, tài chính và một số ngành khác.
Giải thuật di truyền được lấy cảm hứng từ thuyết tiến hóa của giới tự nhiên do nhà bác
học Darwin xây dựng.Nguyên lý sinh học khởi nguồn của tư tưởng lập trình tiến hóa
như sau:Trong tất cả cá thể sống đều chứa các tế bào. Mỗi mội tế bào đều chứa cùng
tập hợp bộ nhiễm sắc thể giống nhau. Nhiễm sắc thể chứa các chuỗi DNA. Các chuỗi
DNA được nhóm lại thành các khối (block) hay còn gọi là gen, mỗi một gen này là
một Protein. Hay có thể nói mỗi một gen này biểu diễn một đặc điểm của sinh vật, ví
dụ như đặc điểm của màu mắt (nâu, đen, xanh, vàng), đặc điểm của màu tóc(đen, bạch
kim, nâu, vàng), kiểu tóc (thẳng, xoăn…). Các Gen tương ứng là các Gen có cùng một
đặc tính với giá trị khác nhau, hoặc giống nhau. Ví dụ Gen quy định màu tóc vàng ở cá
thể A tương ứng với Gen quy định tóc đen ở cá thể B.Tập hợp toàn bộcác nguyên liệu
di truyền học (tất cả các nhiễm sắc thể) được gọi là bộ di truyền. Kiểu Gen là tập hợp
con các gen trong bộ các nguyên liệu di truyền. Kiểu gen này sẽ quy định đặc tính cơ
cá thể nào không thích nghi với môi trường sẽ bị đào thải. Sự thay đổi của môi trường
sẽ tác động đến quá trình tiến hóa và bản thân quá trình tiến hóa cũng có tác động và
làm thay đổi môi trường. Cá thể mới sinh ra trong quá trình tiến hóa nhờ vào sự lai
ghép ở thế hệ cha-mẹ. Một cá thể mới có thể mang những đặc tính của cha-mẹ ở thế hệ
trước (di truyền) hoặc mang những đặc tính mới hoàn toàn (đột biến). Di truyền và đột
biến là hai cơ chế quan trọng như nhau trong quá trình tiến hóa mặc dù xác suất để xảy
ra hiện tượng đột biến nhỏ nhiều so với hiện tượng di truyền” [1]. Mặc dù cơ chế là
ngẫu nhiên nhưng thuật toán di truyền không phải là một thuật toán ngẫu nhiên. Thuật
toán khai thác và tận dụng được một cách hiệu quả thông tin quá khứ để có được
những kết quả mới đạt kết quả như mong muốn. Các cải tiến trong việc sử dụng thuật
toán di truyền đã làm tăng thêm hiệu quả của việc sử dụng thuật toán trong các bài
toán phức tạp. Điều này thể hiện ở việc giảm thời gian tính toán ngày càng hiệu quả
mà ta sẽ tìm hiểu cụ thể hơn ở dưới đây.
2.2. Lịch sử phát triển
Năm 1954, GP bắt đầu với giải thuật tiến hóa, nó được sử dụng lần đầu tiên bởi Nils
Aall Barricelli trong việc mô phỏng quá trình tiến hóa.
Vào những năm 1960 và nửa đầu những năm 1970 giải thuật tiến hóa (EA) được biết
đến như là các phương pháp tối ưu hóa. I. Rechenberg và nhóm của ông ấy đã giải
quyết được nhiều vấn đề phức tạp trong ngành công nghệ bằng chiến lược tiến hóa
(Evolution strategies). Ôngđã giới thiệu ý tưởng về lập trình tiến hóa trong tác phẩm
"Evolution strategies" (Evolutionsstrategie in original). Sau đó các nhà nghiên cứu
khác tiếp tục phát triển ý tưởng này của ông. Năm 1971 ông làm luận án tiến sỹ về
evolution strategies và năm 1973 ông xuất bản thành sách.
Trong những năm 1970 Jonh Holland có những ảnh hưởng rất lớn trong quá trình phát
triển của giải thuật di truyền. Giải thuật di truyền (GA) được Holland phát minh và sau
Copyright: Tài liệu đại học ©