Với khả năng được chọn lọc trong việc sinh ra thế hệ sau, giáo viên ra đề thi dựa
vào kết quả của bảng độ thích nghi có thể dự đoán những đề thi mới. Giáo viên tính
sao cho độ thích nghi cuối cùng là một xác suất, nghĩa là tổng độ thích nghi của mỗi cá
thể <=1. Nó cung cấp một lời giải thích đầy đủ về các sự kiện quan sát.
Chẳng hạn thí sinh thứ nhất vào gặp câu 1 không trả lởi được hệ thống sẽ lưu lại, thí
sinh thứ 2 vào thi câu 1 không trả lởi và thí sinh thứ n vào thi câu 1 không trả lởi. Lúc
đó hệ thống đánh giá độ thích nghi câu hỏi 1 xem như không phù hợp với môi trường
thí sinh, giúp cho giáo viên kịp thời chỉnh sửa và cách dạy cho phù hợp năng lực thí
sinh.
23 trang |
Chia sẻ: lylyngoc | Lượt xem: 2713 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Tiểu luận Thuật toán di truyền cùng với logic mờ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 1
Tiểu luận
Thuật tốn di truyền cùng với logic mờ
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 2
LỜI MỞ ĐẦU
Ngày nay nghiên cứu khoa học là một trong những hoạt động cĩ tốc độ phát
triển mạnh mẽ. Các thành tựu nghiên cứu khoa học đã được ứng dụng vào mọi lĩnh
vực của cuộc sống. Khoa học đã làm đảo lộn nhiều quan niệm truyền thống, nĩ làm
cho sức sản xuất xã hội tăng lên hàng trăm lần so với vài thập niên gần đây.
Về phần mình, bản thân khoa học càng cần được nghiên cứu một cách khoa học.
Một mặt, phải tổng kết thực tiễn nghiên cứu khoa học để khái quát những lý thuyết về
quá trình sáng tạo khoa học; mặt khác, phải tìm ra được các biện pháp tổ chức, quản
lý và nghiên cứu khoa học tốt hơn làm cho bộ máy khoa học vốn đã mạnh, lại phát
triển mạnh hơn và đi đúng quỹ đạo hơn.
Sự phát triển của khoa học hiện đại khơng những đem lại cho con người những
hiểu biết sâu sắc về thế giới, mà cịn đem lại cho con người cả những hiểu biết về
phương pháp luận thế giới. Chính vì vậy mà phương pháp và phương pháp luận
nghiên cứu khoa học đã gắn liền với hoạt động cĩ ý thức của con người, là một trong
những yếu tố quyết định sự thành cơng của hoạt động nhận thức và cải tạo thế giới
Trong bài thu hoạch này em xin được trình bày một khái niệm liên quan đến
khoa học cũng cách thức tiếp cận nghiên cứu khoa học và giới thiệu một ứng dụng cụ
thể liên quan đến thuật tốn di truyền.
Qua đây, em xin chân thành cảm ơn GS.TSKH Hồng Kiếm, thầy đã tận tình
truyền đạt cho chúng em những kiến thức cơ bản của mơn học “Phương pháp nhiên
cứu khoa học trong tin học”từ đĩ cĩ cái nhìn tổng quát hơn về nghiên cứu khoa học..
MỤC LỤC
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 3
PHẦN I PHƯƠNG PHÁP LUẬN NGHIÊN CỨU KHOA HỌC ............................. 3
1. Khoa học và Nghiên cứu khoa học ............................................................... 3
1.1. Khoa học............................................................................................................ 3
1.1.1. Các định nghĩa và khái niệm ........................................................................... 3
1.1.2. Phân loại ......................................................................................................... 3
1.2. Nghiên cứu khoa học ......................................................................................... 4
1.2.1. Khái niệm ....................................................................................................... 4
1.2.2. Phân loại ......................................................................................................... 4
1.2.2.1 Phân loại theo chức năng nghiên cứu ............................................................ 4
1.2.2.2. Phân loại theo tính chất của sản phẩm nghiên cứu ........................................ 5
1.2.2.3. Các đặc điểm của nghiên cứu khoa học ........................................................ 6
1.2.2.4 Các bước nghiên cứu .................................................................................... 7
2. Phương pháp Nghiên cứu khoa học ....................................................................... 8
2.1. Phương pháp chung trong NCKH ...................................................................... 8
2.1.1. Phương pháp nghiên cứu lý thuyết .................................................................. 8
2.1.2. Phương pháp nghiên cứu thực nghiệm ............................................................ 8
2.1.3. Phương pháp nghiên cứu phi thực nghiệm....................................................... 9
2.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế ............... 9
PHẦN II GIỚI THIỆU MỘT NGHIÊN CỨU KHOA HỌC CỤ THỂ ..................... 11
1. Ứng dụng giải thuật di truyền nâng cao chất lượng đề thi.................................... 11
1.1. Giới thiệu ......................................................................................................... 11
1.2. Thuật giải di truyền .......................................................................................... 11
1.2.1. Đặc điểm, đặc trưng ...................................................................................... 11
1.2. Các thành phần của thuật tốn di truyền ........................................................... 12
1.3. Mơ hình bài tốn ứng dụng thuật giải di truyền nâng cao chất lượng đề thi ...... 14
1.3.1. Giới thiệu bài tốn......................................................................................... 14
1.3.2. Xây dựng cấu trúc dữ liệu bài tốn ................................................................ 14
1.3.3. Giải thuật di truyền cho bài tốn nâng cao nhất lượng đề thi ......................... 15
1.3.3.1. Phương pháp khởi tạo ................................................................................ 15
1.3.3.2. Tốn tử lai ghép ......................................................................................... 16
1.3.3.3. Tốn tử đột biến ......................................................................................... 17
1.3.3.4. Hàm thích nghi ........................................................................................... 18
1.3.3.4. Tốn tử chọn lọc ........................................................................................ 19
PHẦN 3 KẾT LUẬN ............................................................................................. 21
TÀI LIỆU THAM KHẢO....................................................................................... 22
PHẦN I
PHƯƠNG PHÁP LUẬN NGHIÊN CỨU KHOA HỌC
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 4
1. Khoa học và Nghiên cứu khoa học:
1.1. Khoa học:
1.1.1. Các định nghĩa và khái niệm:
Khoa học được hiểu là “ hệ thống tri thức về mọi loại quy luât vật chất và sự vận
động của vât chất, những quy luật của tự nhiên, xã hội, tư duy “. Hệ thống tri thức
được nĩi ở đây là hệ thống tri thức khoa học, khác với tri thức kinh nghiệm.
Tri thức kinh nghiệm là những hiểu biết được tích luỹ một cách ngẫu nhiên từ
trong đời sống hàng ngày. Nhờ tri thức kinh nghiệm, con người cĩ được những hình
dung thực tế về các sự vật, biết cách phản ứng trước tự nhiên, biết ứng xử trong các
quan hệ xã hội. tri thức kinh nghiệm ngày càng trở nên phong phú, chứa đựng những
mặt đúng đắn, nhưng riêng biệt chưa thể đi sâu vào bản chất các sự vật, và do vậy tri
thức kinh nghiệm chỉ giúp cho con người phát triển đến một khuơn khổ nhất định. Tuy
nhiên, tri thức kinh nghiệm luơn là một cơ sở quan trọng cho sự hình thành các tri thức
khoa học.
Tri thức khoa học là những hiểu biết được tích lũy một cách hệ thống nhờ hoạt
động nghiên cứu khoa học, là loại hoạt động được vạch sẳn theo một mục tiêu xác
định và được tiến hành dựa trên những phương pháp khoa học. Tri thức khoa học
khơng phải là sự kế tục giản đơn các tri thức kinh nghiệm, mà là sự tổng kết những tập
hợp số liệu và sự kiện ngẫu nhiên, rời rạc để khái quát hĩa thành cơ sở lý thuyết về các
liên hệ bản chất.
Theo quan điểm của Marx, khoa học cịn được hiểu là một hình thái ý thức xã
hội, tồn tại độc lập tương đối với các hình thái ý thức xã hội khác.
Các tiêu chí nhận biết một bộ mơn khoa học:
1. Cĩ một đối tượng nghiên cứu
2. Cĩ một hệ thống lý thuyết
3. Cĩ một hệ thống phương pháp luận
4. Cĩ mục đích sử dụng
1.1.2. Phân loại
Các quan điểm tiếp cận phân loại khoa học:
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 5
- Theo nguồn gốc: Khoa học thuần túy (sciences pures), lý thuyết (sciences
theorique), thực nghiệm (sciences experimentales), thực chứng (sciences positives),
qui nạp (sciences inductives), diễn dịch (sciences deductives)….
- Theo mục đích ứng dụng: Khoa học mơ tả, phân tích, tổng hợp, ứng dụng, hành
động, sáng tạo….
- Theo mức độ khái quát: Cụ thể, trừu tượng, tổng quát…
- Theo tính tương liên giữa các khoa học: Liên ngành, đa ngành…
- Theo cơ cấu hệ thống tri thức: Cơ sở, cơ bản, chuyên ngành…
- Theo đối tượng nghiên cứu: Tự nhiên, kỹ thuật, xã hội nhân văn, cơng nghệ,
nơng nghiệp, y học…
1.2. Nghiên cứu khoa học:
1.2.1. Khái niệm
Nghiên cứu khoa học là một hoạt động xã hội, hướng vào việc tìm kiếm những
điều mà khoa học chưa biết hoặc là phát hiện bản chất sư vật, phát triển nhận thức
khoa học về thế giới hoặc là sáng tạo phương pháp mới và phương tiện kỹ thuật mới
để cải tạo thế giới.
Nghiên cứu nhằm thỏa mãn nhu cầu nhận thức và cải tạo thế giới:
* Khám phá những thuộc tính bản chất của sự vật hoặc hiện tượng.
* Phát hiện qui luật vận động của sự vật.
* Vận dụng qui luật để sáng tạo giải pháp tác động vào sự vật.
1.2.2. Phân loại
Cĩ nhiều cách phân loại nghiên cứu khoa học. Ở đây ta đề cập đến phân loại theo
chức năng nghiên cứu và theo tính chất của sản phẩmtri thức khoa học thu được nhờ
kết quả nghiên cứu.
1.2.2.1 Phân loại theo chức năng nghiên cứu:
Nghiên cứu mơ tả, là những nghiên cứu nhằm đưa ra một hệ thống tri thức về
nhân dạng sư vật, giúpcon người phân biệt được sự khác nhau, về bản chất giữa
sự vật này với sự vật khác. Nội dung mơ tả cĩ thể bao gồm mơ tả hình thái,
động thái, tương tác; mơ tả định tính tức là các đặc trưng về chất của sự vật; mơ
tả định lượng nhằm chỉ rõ các đặc trưng về lượng của sự vật.
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 6
Nghiên cứu giải thích, là những nghiên cứu nhằm làm rõ nguyên nhân dẫn đến
sự hình thành và quy luật chi phối quá trình vận động của sự vật. Nội dung của
giải thích cĩ thể bao gồm giải thích nguồn gốc; động thái; cấu tr1uc; tương tác;
hậu quả; quy luật chung chi phối quá trình vận động của sự vật.
Nghiên cứu dự báo, là những nhiên cứu nhằm nhận dạng trạng thái của sự vật
trong tương lai. Mọi dự báo đều phải chấp nhận những sai lệch, kể cả trong
nghiên cứu tự nhiên và xã hội. Sự sai lệch trong kết quả dự báo cĩ thể do nhiều
nguyên nhân : sai lêch khách quan trong kết quả quan sát: sai lệch do những
luận cứ bị biến dạng trong sự tác động của các sự khác; mội trường cũng luơn
cĩ thể biến động, …
Nghiên cứu sáng tạo, là nghiên cứu nhằm làm ra một sự vật mới chưa từng tồn
tại. Khoa học khơng bao giờ dừng lại ở mơ tả và dự báo mà luơn hướng vào sự
sáng tạo các giải pháp cải tạo thế giới.
1.2.2.2. Phân loại theo tính chất của sản phẩm nghiên cứu:
Theo tính chất của sản phẩm, nghiên cứu được phân loại thành nghiên cứu cơ
bản, nghiên cứu ứng dụng và nghiên cứu triển khai.
Nghiên cứu cơ bản (Fundamental research) là những nghiên cứu nhằm phát
hiện thuộc tính, cấu trúc, động thái các sự vật, tương tác trong nội bộ sự vật và
mối liên hệ giữa sự vật với các sư vật khác. Nghiên cứu cơ bản được phân thành
hai loại : nghiên cứu cơ bản thuần túy và nghiên cứu cơ bản định hướng.
Nghiên cứu cơ bản thuần túy, cị được gọi là nghiên cứu cơ bản tự do hoặc
nghiên cứu cơ bản khơng định hướng, là những nghiên cứu về bản chất sự vật
để nâng cao nhận thức, chưa cĩ hoặc chưa bàn đến ý nghĩa ứng dụng.
Nghiên cứu cơ bản định hướng, là những nghiên cứu cơ bản đã dự kiến trước
mục đích ứng dụng. các hoạt động điều tra cơ bản tài nguyên, kinh tế, xã hội,
… đều cĩ thể xem là nghiên cứu cơ bản định hướng.
Nghiên cứu ứng dụng (Applied research) : là sự vận dụng quy luật được phát
hiện từ nghiên cứu cơ bản để giải thích một sự vật, tạo ra những nguyên lý mới
về các giải pháp và áp dụng chúng vào sản xuất và đời sống.
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 7
Nghiên cứu triển khai (Development research) : cịn gọi là nghiên cứu triển
khai thực nghiệm hay triển khai thực nghiệm kỹ thuật, là sự vận dụng các quy
luật (thu được từ nghiên cứu cơ bản) và các nguyên lý (thu được từ nghiên cứu
ứng dụng) để đưa ra các hình mẫu với những tham số khả thi về kỹ thuật. Kết
quả nghiên cứu triển khai thì chưa triển khai được: sản phẩm của triển khai chỉ
mới là những hình mẫu khả thi về kỹ thuật, nghĩa là khơng cịn rủi ro về mặt kỹ
thuật, để áp dụng được cịn phải tiến hành nghiên cứu những tính khả thi khác
như khả thi tài chính, khả thi kinh tế, khả thi mơi trường, khả thi xã hội. Hoạt
động triển khai bao triển khai trong phịng thí nghiệm và triển khai bán đại trà.
Tồn bộ các loại hình nghiên cứu và mối liên hệ giữa các loại hình nghiên cứu
được trình bày trong sơ đồ bên dưới. Sự phân chia loại hình nghiên cứu như trên đây
được áp dụng phổ biến trên thế giới. Phân chia là để nhận thức rõ bản chất của nghiên
cứu khoa học, để cĩ cơ sở lập kế hoạch nghiên cứu, cụ thể hĩa các cam kết trong hợp
đồng nghiên cứu giữa các đối tác. Tuy nhiên trên thực tế, trong một đề tài cĩ thể tồn
tại cả ba loại hình nghiên cứu, hoặc tồn tại hai trong ba loại hình nghiên cứu.
1.2.2.3. Các đặc điểm của nghiên cứu khoa học
- Tính mới: NCKH là quá trình thâm nhập vào thế giới của sự vật mà con người
chưa biết, hướng tới những phát hiện mới hoặc những sáng tạo. Đây là đặc điểm quan
trọng nhất.
- Tính tin cậy: Kết quả nghiên cứu phải cĩ khả năng kiểm chứng lại nhiều lần do
nhiều người khác nhau trong điều kiện giống nhau. Do đĩ, một nguyên tắc mang tính
Nghiên cứu cơ bản
Nghiên cứu
ứng dụng
Triển khai
Nghiên cứu cơ bản
thuần túy
Nghiên cứu cơ bản
định hướng
Triển khai trong
phịng thí nghiệm
Nghiên cứu
nền tảng
Nghiên cứu
chuyên đề
Triển khai
bán đại trà
Quan hệ giữa các loại hình nghiên cứu
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 8
phương pháp luận của NCKH là khi trình bày một kết quả nghiên cứu, người nghiên
cứu cần chỉ rõ điều kiện, những nhân tố và phương tiện thực hiện.
- Tính thơng tin: là những thơng tin về qui luật vận động của sự vật hoặc hiện
tượng, thơng tin về qui trình cơng nghệ và các tham số đi kèm qui trình đĩ.
- Tính khách quan: vừa là một đặc điểm của NCKH vừa là tiêu chuẩn của người
NCKH. Để đảm bảo tính khách quan, người NCKH cần phải tự trắc nghiệm lại những
kết luận tưởng như đã hồn tồn được xác nhận.
- Tính rủi ro: Một nghiên cứu cĩ thể thành cơng, cĩ thể thất bại. Thất bại cĩ thể
do nhiều nguyên nhân nhưng trong khoa học thất bại cũng được xem là một kết quả và
mang ý nghĩa về một kết luận của NCKH và được lưu giữ, tổng kết lại như một tài liệu
khoa học nghiêm túc để tránh cho người đi sau khơng dẫm chân lên lối mịn, tránh
lãng phí các nguồn lực nghiên cứu.
- Tính kế thừa: Cĩ ý nghĩa quan trọng về mặt phương pháp luận nghiên cứu.
Ngày nay khơng cĩ một NCKH nào bắt đầu từ chỗ hịan tịan trống khơng về kiến
thức, phải kế thừa các kết quả nghiên cứu của các lĩnh vực khoa học khác nhau.
- Tính cá nhân: vai trị của cá nhân trong sáng tạo mang tính quyết định, thể hiện
trong tư duy cá nhân và chủ kiến riêng của các nhân.
- Tính phi kinh tế: Lao động NCKH hầu như khơng thể định mức, thiết bị chuyên
dụng dùng trong NCKH hầu như khơng thể khấu hao, hiệu quả kinh tế của NCKH hầu
như khơng thể xác định.
1.2.2.4 Các bước nghiên cứu
Xác lập vấn đề nghiên cứu:
- Chọn và cụ thể hĩa đề tài
- Xác định cơ sở cho lý thuyết
- Nghiên cứu lịch sử vấn đề
Giai đoạn chuẩn bị nghiên cứu :
- Chuẩn bị điều kiện nghiên cứu
- Thiết lập danh mục tư liệu
Lựa chọn và nghiên cứu thơng tin:
- Thu thập và xử lý thơng tin
- Nghiên cứu tư liệu
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 9
- Thâm nhập thực tế
- Tiếp xúc cá nhân
- Xử lý thơng tin
Xây dựng giải thuyết, lựa chọn phương pháp và lập kế hoạch :
- Xây dựng giải thuyết
- Xác định phương pháp luận nghiên cứu
- Lập kế hoạch
Hồn tất nghiên cứu:
- Đề xuất và xử lý thơng tin
- Xây dựng kết luận và khuyến nghị
Viết báo cáo hồn tất cơng trình:
- Sắp xếp tư liệu
- Viết báo cáo
Giai đoạn kết thúc:
- Hồn tất cơng tác
- Áp dụng kết quả
2. Phương pháp Nghiên cứu khoa học:
2.1. Phương pháp chung trong NCKH:
2.1.1. Phương pháp nghiên cứu lý thuyết:
Được sử dụng trong cả khoa học tự nhiên, khoa học xã hội và các khoa học khác,
bao gồm nhiều nội dung khác nhau như: nghiên cứu tư liệu, xây dựng khái niệm, phạm
trù, thực hiện các phán đốn, suy luận,.v.v… và khơng cĩ bất cứ quan sát hoặc thực
nghiệm nào được tiến hành
2.1.2. Phương pháp nghiên cứu thực nghiệm:
Nghiên cứu thực nghiệm là những nghiên cứu được thực hiện bởi những quan sát
các sự vật hoặc hiện tượng diễn ra trong những điều kiện cĩ gây biến đổi đối tượng
nghiên cứu một cách cĩ chủ định. Nghiên cứu thực hiện cĩ thể được thực hiện trên đối
tượng thực hoặc trên các mơ hìnhdo người nghiên cứu tạo ra với những tham số do
người nghiên cứu khống chế. Nghiên cứu thực nghiệm được áp dụng phổ biến khơng
những trong khoa học tự nhiên, khoa học kỹ thuật và cơng nghệ, y học, mà cả trong
khoa học xã hội và các lĩnh vực khoa học khác.
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 10
2.1.3. Phương pháp nghiên cứu phi thực nghiệm:
Là một phương pháp nghiên cứu dựa trên sự quan sát, quan trắc những sự kiện đã
hoặc đang tồn tại, hoặc thu thập những số liệu thống kê đã tích lũy. trên cơ sở đĩ phát
hiện qui luật của sự vật hoặc hiện tượng. Trong phương pháp này người nghiên cứu
chỉ quan sát những gì đã và đang tồn tại, khơng cĩ bất cứ sự can thiệp nào gây biến đổi
trạng thái của đối tượng nghiên cứu.
2.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế:
Cĩ 40 thủ thuật:
1. Nguyên lý phân nhỏ
2. Nguyên lý “tách riêng”
3. Nguyên lý phẩm chất cục bộ
4. Nguyên lý phản đối xứng
5. Nguyên lý kết hợp
6. Nguyên lý vạn năng
7. Nguyên lý chứa trong
8. Nguyên lý phản trọng lượng
9. Nguyên lý thực hiện sơ bộ
10. Nguyên lý dự phịng
11. Nguyên lý đẳng thế
13. Nguyên lý đảo ngược
14. Nguyên lý cầu (trịn) hĩa
15. Nguyên lý năng động
16. Nguyên lý tác động bộ phận và dư thừa
17. Nguyên lý bộ xung chiều khác
18. Sự dao động cơ học
19. Nguyên lý tác đơng theo chu kỳ
20. Nguyên lý tác đơng liên tục hữu hiệu
21. Nguyên lý vượt nhanh
22. Nguyên lý chuyển hại thành thắng
23. Nguyên lý quan hệ phản hồi
24. Nguyên lý sử dụng trung gian
25. Nguyên lý tự phục vụ
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 11
26. Nguyên lý sao chép (copy)
27. Nguyên lý rẻ thay cho đắt
28. Nguyên lý thay thế sơ đồ cơ học
29. Nguyên lý sử dụng các kết cấu thủy và khí
30. Sử dụng bao mềm dẻo và mềm mỏng
31. Sử dụng vật liệu nhiều lỗ
32. Nguyên lý đổi màu
33. Nguyên lý đồng nhất
34. Nguyên lý loại bỏ và tái sinh từng phần
35. Đổi các thơng số hĩa lý của đối tượng
36. Sử dụng chuyển pha
37. Sử dụng nở nhiệt
38. Sử dụng các chất oxy hĩa
39. Sử dụng mơi trường trơ
40. Sử dụng vật liệu tổng hợp (composit)
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 12
PHẦN II
GIỚI THIỆU MỘT NGHIÊN CỨU KHOA HỌC CỤ THỂ
1. Ứng dụng giải thuật di truyền nâng cao chất lượng đề thi
1.1. Giới thiệu
Trong xu hướng phát triển của xã hội ngày nay, cĩ rất nhiều ngành khoa học
mới ra đời. Trong đĩ cĩ một số ngành khoa học ra đời trên cơ sở phân lập từ các ngành
khoa học cổ điển, và một số ngành do sự tích hợp các khoa học. Trong thực tiễn cĩ
nhiều bài tốn tối ưu quan trọng địi hỏi những thuật giải chất lượng cao, trong đĩ phải
kể đến đĩ là thuật giải tiến hĩa. Một số thuật tốn tiến hĩa đã được cơng bố như:
Quy hoạch tiến hĩa như-EB, do D.B Pogel đề xuất. Chiến lược tiến hĩa do
T.Baech, F.H Hofineister và H.P. Schewfel đề xuất.
1.2. Thuật giải di truyền
1.2.1. Đặc điểm, đặc trưng
Các thuật giải di truyền là những kỹ thuật tối ưu dựa trên những khái niệm chọn
lọc tự nhiên và di truyền. Trong cách tiếp cận này, lời giải của bài tốn được trình
bày như các gen trong nhiễm sắc thể. Thuật giải di truyền mơ tả một nhĩm các lời
giải cĩ thể ứng cử (quần thể) trên bề mặt đáp ứng. Qua tiến hĩa và chọn lọc tự
nhiên các nhiễm sắc thể với độ thích nghi tốt hơn xuất hiện. Chọn lọc tự nhiên đảm
bảo cho nhiễm sắc thể cĩ độ thích nghi tốt nhất sẽ được truyền cho những quần thể
tương lai.
Những đăc trưng của thuật giải di truyền như sau:
Thuật giải di truyền làm việc với một mã hĩa của tập hợp tham số
chứ khơng phải với một tham số.
Thuật giải di truyền tìm từ một quần thể các điểm chứ khơng phải một điểm.
Thuật giải di truyền đánh giá thơng tin (với hàm mục tiêu), chứ khơng đưa
vào đạo hàm hoặc tri thức bổ sung khác.
Thuật giải di truyền sử dụng các luật biến đổi theo xác suất, khơng sử dụng
luật quyết định.
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 13
Chúng ta cĩ thể mơ tả phần đặc tả của tồn bộ thuật giải di truyền như sau sơ đồ
sau:
1.2.2. Các thành phần của thuật giải di truyền
a. Khởi động quần thể ban đầu
Tạo quần thể đầu tiên trong thuật giải, là nơi xuất phát quá trình tiến hĩa, bao
gồm tất cả các giá trị thơ ban đầu. Tùy theo vấn đề của bài tốn mà cĩ cách khởi động
khác nhau. Trước một bài tốn áp dụng thuật giải di truyền, ta cần phải xác định rõ
nhiễm sắc thể và cá thể cho vấn đề, và thơng thường đĩ sẽ kết quả cuối cùng. Việc
phân tích sẽ dựa trên kết quả là cơ bản nhất.
b. Đánh giá cá thể
1. Khởi tạo ngẫu nhiên
một tập quần thể.
3. Tạo các nhiễm sắc thể
mới bằng cách lai ghép.
2. Đánh giá mọi cá thể
trong quần thể.
4. Đột biến của tổ hợp
cặp nhiễm sắc thể bố mẹ.
5. Đánh giá các cá thể mới
và đưa chúng vào quần thể
bằng cách thay thế.
6. Kiểm tra điều kiện dừng
(các giới hạn: số thế hệ, độ
thích nghi, thời gian ...)
7. kết thúc quá trình và trả
về cá thể tốt nhất.
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 14
Chắc chắn rằng việc chọn cá thể sẽ thơng qua kết quả, hay mục đích của vấn đề.
Dựa trên mức độọ thích nghi của cá thể, bao gồm những vướng mắc mà cá thể gặp
phải. Thơng thường, đặt mỗi vấn đề nhỏ tương ứng với một giá trị điểm thích nghi, kết
quả đánh giá gồm tổng các số điểm đĩ. Cá thể tốt nhất sẽ cĩ số điểm thấp nhất hoặc
lớn nhất.
Theo thuyết tiến hĩa của Darwin, nhiễm sắc thể tốt nhất sẽ tồn tại và tạo ra các cá
thể con mới. Cĩ nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất.
1) Chọn lọc Roulette (Roulette Wheel Selection)
2) Chọn lọc xếp hạng (Rank Selection)
3) Chọn lọc cạnh tranh (Tournament Selection)
c. Tốn tử lai ghép
Lai ghép nhằm nâng cao kết quả cá thể, do đĩ, tốn tử lai ghép sẽ tạo điều
kiện cho tiến trình hội tụ nhanh hay chậm. Cịn tùy thuộc vào cách tổ chức và
phân bố các nhiễm sắc thể mà chúng ta cĩ xác suất lai ghép nhanh hay chậm. Sau
đây là vài phương pháp lai ghép thơng dụng trong kỹ thuật di truyền:
1) Lai ghép ánh xạ từng phần (PMX Partial Mapped Crossover)
2) Lai ghép cĩ trật tự (OX Order Crossover)
3) Lai ghép dựa trên vị trí (Position Based Crossover)
4) Lai ghép dựa trên thứ tự (Order Base Crossover)
5) Lai ghép cĩ chu trình (CX Cycle Crossover)
6) Lai ghép thứ tự tuyến tính (LOX Linear Order Crossover)
d. Tốn tử đột biến
Cũng giống như lai ghép, tốn tử đột biến làm tăng nhanh quá trình hội tụ,
nhưng tăng một cách đột ngột, cũng cĩ khi sẽ khơng gây tác dụng gì một khi khơng
thành cơng. Khơng ai cĩ thể đánh giá được phương pháp đột biến nào tốt hơn, do
đĩ cĩ một vài phương pháp đơn giản, cũng cĩ vài trường hợp khá phức tạp. Người
ta thường chọn một trong những phương pháp sau :
1) Đột biến đảo ngược (Inversion Mutation)
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 15
2) Đột biến chèn (Insertion Mutation)
3) Đột biến thay thế (Displacement Mutation)
4) Đột biến tương hỗ (Reciprocal Exchange Mutation)
5) Đột biến chuyển dịch (Shift Mutation)
e. Điều kiện kết thúc
Thốt ra quá trình tiến hĩa quần thể, dựa vào bài tốn mà cĩ các cách kết thúc
vấn đề khác nhau, một khi đã đạt đến mức yêu cầu. Một vài trường hợp thơng thường
như sau:
-Kết thúc theo kết quả: một khi đạt đến mức giá trị yêu cầu thì chấm dứt ngay
quá trình thực hiện.
-Kết thúc dựa vào số thế hệ: chọn số thế hệ, quá trình sẽ dừng đúng ngay số thế
hệ đã qui định trước, khơng cần biết kết quả như thế nào.
-Tính theo thời gian: khơng cần biết đã bao nhiêu thế hệ hay kết quả nào, chỉ dựa
vào số giờ qui định mà kết thúc.
-Tổ hợp: dùng nhiều phương án khác nhau cho vấn đề, chẳng hạn như : chạy theo
số thế hệ xong sau đĩ đánh giá cho chạy theo kết quả, hoặc ngược lại.
1.3. Mơ hình bài tốn ứng dụng thuật giải di truyền nâng cao chất lượng đề
thi
1.3.1. Giới thiệu bài tốn
Nâng cao chất lượng đề thi phù hợp với mơi trường học tập sinh viên, dạt được
kết quả tốt và tạo hứng thú học tập đồng thời giáo viên giảng dạy điều chỉnh phương
pháp và nội dung phù hợp với năng lực của sinh viên nâng cao chất lượng dạy và học.
Bài tốn đặt ra hướng giải quyết xây dựng được hệ thống đề thi ngẫu nhiên, tính độ
thích nghi mỗi câu hỏi, mỗi đề thi qua các thế hệ thí sinh vào thi.
1.3.2. Xây dựng cấu trúc dữ liệu bài tốn
Đầu vào:
MONTHI: Bảng danh sách các mơn thi
CAUHOI: Bảng danh sách các câu hỏi
SINH VIÊN: Bảng danh sách sinh viên
GIAOVIEN: Bảng danh sách các giáo viên
DAPAN: Bảng đáp án đề thi
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 16
KETQUA: Bảng kết quả thí sinh vào thi
Các ràng buộc:
Mỗi câu hỏi thi đều cĩ một đáp án duy nhất. Quan hệ giữa bảng câu hỏi và bảng
đáp án là quan hệ 1-1.
Mỗi mơn thi đều cĩ nhiều câu hỏi. Quan hệ giữa bảng mơn thi và bảng câu hỏi là
quan hệ 1 - ∞.
Mỗi mơn thi được thi nhiều thí sinh. Quan hệ giữa bảng mơn thi và bảng sinh
viên là quan hệ 1 - ∞.
Mỗi đáp án đều cĩ một kết quả là duy nhất. Quan hệ giữa bảng kết quả và bảng
đáp án là quan hệ 1-1.
Mỗi sinh viên cĩ điểm nhiều mơn. Quan hệ giữa bảng sinh viên và bảng kết
quả là quan hệ 1 - ∞.
Mỗi giáo viên ra nhiều đề thi. Quan hệ giữa bảng giáo viên và bảng mơn thi là
quan hệ 1 - ∞.
Đầu ra:
Số lượng các đề thi được tráo ngẫu nhiên.
Các câu hỏi trong đề thi đã được đánh giá độ thích nghi.
1.3.3. Giải thuật di truyền cho bài tốn nâng cao nhất lượng đề thi
1.3.3.1. Phương pháp khởi tạo
Ban đầu mỗi thí sinh vào thi hệ thống phát sinh ngẫu nhiên một lượng các câu
hỏi thi, giới hạn các cá thể cĩ gen ngẫu nhiên. Tập các cá thể này được gọi là quần thể
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 17
ban đầu. Các cá thể được tạo ra một cách độc lập, trong mỗi cá thể, bộ nhiễm sắc thể
được tạo ra nhờ một vịng lặp. Số lượng cá thể và độ dài của nhiễm sắc(NST) thể được
cho trước [5,9,11]. Mỗi NST là một câu hỏi thi, mỗi NST gồm các gen trong bài tốn
này là 4 gen mà mỗi gen biểu thị một phương án trả lời.
void khoitao()
{
for(i=0;i<kích thước quần thể; i++)
{
Tạo ngẫu nhiên cá thể thứ I của P(0)
}
}
Hàm tạo quần thể P(i+1)
void NextGen()
{
Tái sinh các cá thể P(i) vào P(i+1)
for(j=0;j<số phần tử tái sinh; j++ )
{
P(i+1,j)=P(i,j);
}
}
1.3.3.2. Tốn tử lai ghép
Cĩ 3 cách lai ghép đĩ là: lai đều, lai một điểm và lai ba điểm. Để tiến hành trao
đổi gen, ta sử dụng hai mảng tạm, sau đĩ sao chép lần lượt từng gen của một trong hai
gen đem lai vào hai biến đĩ theo đúng quy luật đã nêu trên.
Hình 2 Sơ đồ ghép 2 gen
void laighep()
{Tạo các cá thể mới từ các cá thể của P(i)
for(j=số phần tử được tái sinh, đếm=0; đếm<số phần tử di truyền)
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 18
{Chọn 2 cá thể cha và mẹ từ P(i);
CHA=Select();
ME= Select();
Các cá thể con=Lai ghép cha mẹ: tùy thuộc vào phương pháp lai ghép
chọn;
}
}
Hệ thống sẽ dựa vào các cá thể cha mẹ ban đầu để sinh sản ra thế hệ đề thi mới nhờ
lai ghép.
1.3.3.3. Tốn tử đột biến
Các phương pháp đột biến như mất đoạn, lặp đoạn, đảo đoạn và chuyển đoạn.
Trong hệ thống thi trực tuyến này tốn tử đột biến mất đoạn và lặp đoạn là khơng phù
hợp với cấu trúc đề thi. Do đĩ chỉ cĩ thể dùng phương pháp đảo đoạn và chuyển đoạn.
Tốn tử đột biến ta chỉ cần thay thế một gen bất kỳ trong NST bởi một gen ngẫu nhiên
khác. Thủ tục thể hiện như sau:
void dotbien()
{
if(laighep(cha,me,con)!=0 )
{đột biến các cá thể con
Đưa các cá thể con đã qua hàm đột biến vào quần thể P(i+1);
P(i+1,j)=con;
j++;dem++;
} tạo ngẫu nhiên các cá thể mới
s=số phần tử tái sinh+số phần tử di truyền
for(j=s;j<kích thước quần thể;j++)
{
Tạo ngẫu nhiên cá thể thứ j của quần thể P(i+1);
}
}
Tốn tử đột biến thể hiện rất rõ khi chọn ngẫu nhiên các câu hỏi thi, chẳng hạn cĩ K
câu hỏi:1,2,3,4,..K
Câu 1 Câu 3 Câu 4 Câu 4………………….Câu k
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 19
Chẳng hạn:
Câu 1 xuất hiện lần đầu cho thí sinh thứ 1 vào thi thì thí sinh thứ 2 vào thi đề thi
khơng thể lặp lại phải là câu 2 hoặc các câu cịn lại xuất hiện lần đầu như vây câu 1 ta
dùng tốn tử đột biến, dùng chuyển đoạn đưa câu 1 xuống và câu 2 xuất hiện lên trên
đầu, cứ như vậy ta cĩ ngân hàng câu hỏi ngẫu nhiên.
1.3.3.4. Hàm thích nghi(Fitness)[1,7,13]
Đĩ là tiêu chuẩn mà dựa vào đĩ chúng ta cĩ thể đánh giá chất lượng của đề thi
và chất lượng của học viên sau một vài thế hệ(mỗi thế hệ là lượt thi).
Tính độ thích nghi eval(vi) của mỗi NST vi (i=1.. kích thước quần thể):
Kích thước quần thể:
Eval(vi)= f(vi)/tổng f(vi)
Với f(vi) hàm mục tiêu
Hàm mục tiêu chính là tổng chi phí các phương án trả lời từ phương án 1 đến
phương án 4.
Gỉa sử chi phí các phương án trả lời là T1, T2 , T3 , T4 ta cĩ:
T= T1 + T2 + T3+ T4
Trong đĩ:
i k l h
iklhYT1
i k l h
iklhYT2
i k l h
iklhYT3
i k l h
iklhYT4
Chẳng hạn xét một thế hệ(một lượt thi) cĩ 5 cá thể với độ tốt(điểm thí sinh)
trong bảng sau:
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 20
Số BD Độ tốt
1 6
2 7
3 2
4 3
5 1
Vậy tổng gen của 5 cá thể(thí sinh): 19. Độ thích nghi của phần tử a1 =6/19=0,31.
Ta cĩ bảng kết quả của độ thích nghi sau:
SBD Độ tốt Độ thích nghi
1 6 0,31
2 7 0,36
3 2 0,105
4 3 0,158
5 1 0,053
Với khả năng được chọn lọc trong việc sinh ra thế hệ sau, giáo viên ra đề thi dựa
vào kết quả của bảng độ thích nghi cĩ thể dự đốn những đề thi mới. Giáo viên tính
sao cho độ thích nghi cuối cùng là một xác suất, nghĩa là tổng độ thích nghi của mỗi cá
thể <=1. Nĩ cung cấp một lời giải thích đầy đủ về các sự kiện quan sát.
Chẳng hạn thí sinh thứ nhất vào gặp câu 1 khơng trả lởi được hệ thống sẽ lưu lại, thí
sinh thứ 2 vào thi câu 1 khơng trả lởi và thí sinh thứ n vào thi câu 1 khơng trả lởi. Lúc
đĩ hệ thống đánh giá độ thích nghi câu hỏi 1 xem như khơng phù hợp với mơi trường
thí sinh, giúp cho giáo viên kịp thời chỉnh sửa và cách dạy cho phù hợp năng lực thí
sinh.
1.3.3.5. Tốn tử chọn lọc
Mục đích tốn tử chọn lọc sẽ chọn ra các cá thể(câu hỏi thi) để được lai ghép. Sau
khi đã chọn lọc, việc chọn cặp lai ghép cĩ thể tiến hành ngẫu nhiên hay tuần tự từng
cặp liên tiếp.
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 21
Một tồn tử lai ghép cần 2 cá thể để thực hiện lai ghép. Vấn đề là 2 cá thể đĩ
được chọn như thế nào. Theo nguyên lý tiến hĩa quần thể, các cá thể cĩ độ thích nghi
cao hơn sẽ cịn cĩ khả năng di truyền lại thế hệ sau.
Hàm tốn tử chọn lọc:
void Select(int k, quần thể , đề thi được chọn)
{ chọn ngẫu nhiên k cá thể từ quần thể
for(i=0;i<k ;i++)
{chọn ngẫu nhiên cá thể thứ i
A[i]=quần thể[rand() % độ dài quần thể]
}
Chọn cá thể tốt nhất theo hàm thích nghi trên;
}
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 22
PHẦN 3
KẾT LUẬN
Hiện nay Thuật tốn di truyền cùng với logic mờ được ứng dụng rất rộng
rãi trong các lĩnh vực phức tạp. Thuật tốn di truyền kết hợp với logic mờ
chứng tỏ được hiệu quả của nĩ trong các vấn đề khĩ cĩ thể giải quyết bằng các
phương pháp thơng thường hay các phương pháp cổ điển. Nhất là trong các bài
tốn cần cĩ sự lượng giá, đánh giá sự tối ưu của kết quả thu được.
Bài thu hoạch mơn PP NCKH trong Tin học GVPT: GS.TSKH Hồng Kiếm
Học viên: Nguyễn Văn Phong(CH1101026) – khĩa 6 Trang 23
TÀI LIỆU THAM KHẢO
1. Bài giảng mơn học “Phương pháp nhiên cứu khoa học trong tin học” .
Giảng viên : GS.TSKH Hồng Kiếm
Chương trình đào tạo thac sĩ CNTT qua mạng khĩa 5
Trường Đại học Cơng nghệ thơng tin.
2. Các thủ thuật (nguyên tắc) sáng tạo cơ bản (phần 1)
Phan Dũng
Trung tâm sáng tạo khoa học – kỹ thuật.
Trường Đại Học Khoa Học Tự Nhiên TP.HCM
3. Giải một bài tốn trên máy tính như thế nào ?( tập 1, 2, 3).
GS. TSKH Hồng Kiếm.
Nhà xuất bản giáo dục – 2003.
4. Đơi cánh I Ca Rơ
GS.TSKH Hồng Kiếm – Thanh Thủy – Chi Mai
Nhà xuất bản thống kê Hà Nội, 1990.
5. Phương pháp luận nghiên cứu khoa học .
Vũ Cao Đàm.
Nhà xuất bản Khoa Học và Kỹ Thuật – 1999.
6. Hồng Kiếm, Lê Hồng Thái, Thuật giải di truyền, NXB Giáo dục, Hà Nội,
2000.
7. Báo cáo hội thảo tại Đại học Điện lực năm 2011 của tác giả Phạm Thị Thơm
Các file đính kèm theo tài liệu này:
- tieu_luan_pp_nckh_nguyen_van_phong_ma_so_ch1101026__452.pdf