Tiểu luận: Thuật toán di truyền cùng với logic mờ

Chia sẻ: Vang Thi | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

144
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tiểu luận: Thuật toá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 Hoàng Kiếm Tiểu luận Thuật toán di truyền cùng với logic mờ Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 1
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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 toán di truyền. Qua đây, em xin chân thành cảm ơn GS.TSKH Hoà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 Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 2
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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 toán di truyền ........................................................... 12 1.3. Mô hình bài toá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 toán......................................................................................... 14 1.3.2. Xây dựng cấu trúc dữ liệu bài toán ................................................................ 14 1.3.3. Giải thuật di truyền cho bài toá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. Toán tử lai ghép ......................................................................................... 16 1.3.3.3. Toán tử đột biến ......................................................................................... 17 1.3.3.4. Hàm thích nghi........................................................................................... 18 1.3.3.4. Toá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 Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 3
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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: Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 4
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm - 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. Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 5
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm  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. Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 6
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm  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à. Toà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. Nghiên cứu cơ bản thuần túy Nghiên cứu cơ bản Nghiên cứu nền tảng Nghiên cứu cơ bản định hướng Nghiên cứu Nghiên cứu ứng dụng chuyên đề Triển khai trong phòng thí nghiệm Triển khai Triển khai bán đại trà Quan hệ giữa các 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 Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 7
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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ư đã hoàn toà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 Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 8
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm - 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  Hoà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 hoà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: - Hoà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 đoá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. Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 9
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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ụ Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 10
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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) Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 11
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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 toá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 toá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 toá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. Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 12
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm Chúng ta có thể mô tả phần đặc tả của toàn bộ thuật giải di truyền như sau sơ đồ sau: 1. Khôûtaï ngaã nhieâ i o u n moätaä quaà theå t p n . 2. Ñaùh giaù i caù n moï theå trong quaà theå n . 3. Taï caù nhieã saé theå o c m c môùbaèg caùh lai gheù. i n c p 4. Ñoäbieá cuû toå p t n a hôï caë nhieã saé theå meï p m c boá . 5. Ñaùh giaù c caù môù n caù theå i vaø chuùg vaø quaà theå ñöa n o n baèg caùh thay theá n c . 6. Kieå tra ñieà kieä döøg m u n n (caù giôùhaï : soá heäñoä c i n theá , thích nghi, thôøgian ...) i 7. keáthuù quaù vaø t c trình traû veà theå t nhaá caù toá t. 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 toán mà có cách khởi động khác nhau. Trước một bài toá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ể Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 13
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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. Toán tử lai ghép Lai ghép nhằm nâng cao kết quả cá thể, do đó, toá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. Toán tử đột biến Cũng giống như lai ghép, toá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) Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 14
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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 Thoát ra quá trình tiến hóa quần thể, dựa vào bài toá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 toá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 toá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 toá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 toá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 Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 15
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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 toá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ể Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 16
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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 toá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
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm {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. Toá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 toá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. Toá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
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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 toá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 đó: T1   Yiklh i k l h T2   Yiklh i k l h T3    Yiklh i k l h T4   Yiklh i k l h 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: Học viên: Nguyễn Văn Phong(CH1101026) – khóa 6 Trang 19
Bài thu hoạch môn PP NCKH trong Tin học GVPT: GS.TSKH Hoàng Kiếm 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ự đ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ể