Luận Văn Thạc Sĩ: Ứng Dụng Thuật Giải Di Truyền Để Giải Các Bài Toán Tối Ưu Nhiều Biến

Luận văn thạc sĩ nghiên cứu vnu uet ứng dụng thuật giải di truyền giải các bài toán hàm mục tiêu nhiều biến, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện

• Tác giả: Lê Chí Luận
• Người hướng dẫn: PGS.TSKH Hà
• Trường học: Đại Học Quốc Gia Hà Nội Trường Đại Học Kinh Tế
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Ứng Dụng Thuật Giải Di Truyền Các Bài Toán Hàm Mục Tiêu Nhiều Biến
• Loại tài liệu: Luận Văn Tiến Sỹ
• Năm xuất bản: 2008
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: THUẬT GIẢI DI TRUYỀN
• 1.1. Tổng quan về thuật giải di truyền
• 1.2. Thuật giải di truyền là gì?
• 1.3. Lịch sử phát triễn của giải thuật di truyền
• 1.4. Từ ngẫu nhiên đến thuật giải di truyền
• 1.5. Một số ứng dụng nổi bật của thuật giải di truyền
• 1.6. Các nguyên tắc cơ bản của thuật giải di truyền
• 1.7. Những tính chất cơ bản của thuật giải di truyền
• 1.8. Các bước trong việc áp dụng thuật giải di truyền
• 1.9. Các phương pháp mã hoá trong thuật giải di truyền
• 1.10. Một vài ví dụ minh hoạ
• 1.11. Các giai đoạn cần thực hiện để giải quyết bài toán bằng thuật giải di truyền
• 1.12. Mối liên hệ giữa thuật giải di truyền và sự tiến hoá
• 1.13. Những tính chất quan trọng của thuật giải di truyền
• 1.14. Một số vấn đề liên quan đến thuật giải di truyền
• 2. CHƯƠNG 2: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ GIẢI CÁC BÀI TOÁN TỐI ƯU NHIỀU BIẾN
• 2.1. Bài toán tối ưu
• 2.2. Một số ví dụ về bài toán tối ưu
• 2.3. Một số ứng dụng nổi bật của bài toán tối ưu
• 2.4. Ứng dụng giải thuật di truyền để giải các bài toán tối ưu nhiều biến
• 2.5. Biễu diễn các biến bằng véc tơ nhị phân
• 2.6. Toán tử chọn cá thể (select)
• 2.7. Toán tử lai ghép (cross over)
• 2.8. Toán tử đột biến (mutation)
• 2.9. Bài toán cực tiểu hàm f với n biến liên tục
• 2.10. Bài toán 1: Bài toán cực tiểu hàm với N biến
• 2.11. Hàm thích nghi (fitness)
• 2.12. Bài toán 2: Travelling Salesman Problem (TSP)
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Ứng Dụng Thuật Giải Di Truyền Trong Tối Ưu Nhiều Biến

Thuật giải di truyền (GA) đã trở thành một công cụ mạnh mẽ trong việc giải quyết các bài toán tối ưu nhiều biến. Với khả năng mô phỏng quá trình tiến hóa tự nhiên, GA giúp tìm ra các giải pháp tối ưu cho những bài toán phức tạp mà các phương pháp truyền thống không thể giải quyết hiệu quả. Bài viết này sẽ khám phá cách thức hoạt động của GA và ứng dụng của nó trong tối ưu hóa nhiều biến.

1.1. Thuật Giải Di Truyền Là Gì

Thuật giải di truyền là một phương pháp tối ưu hóa dựa trên nguyên lý tiến hóa tự nhiên. Nó sử dụng các khái niệm như chọn lọc tự nhiên, lai ghép và đột biến để tìm kiếm giải pháp tối ưu cho các bài toán phức tạp. GA đã được áp dụng rộng rãi trong nhiều lĩnh vực, từ khoa học máy tính đến kỹ thuật và kinh tế.

1.2. Lịch Sử Phát Triển Của Thuật Giải Di Truyền

Lịch sử của GA bắt đầu từ những năm 1950, nhưng được phát triển mạnh mẽ bởi John Holland vào những năm 1970. Ông đã giới thiệu các khái niệm cơ bản và ứng dụng của GA trong việc giải quyết các bài toán phức tạp. Kể từ đó, GA đã trở thành một lĩnh vực nghiên cứu quan trọng trong trí tuệ nhân tạo.

II. Vấn Đề Trong Giải Bài Toán Tối Ưu Nhiều Biến

Bài toán tối ưu nhiều biến thường gặp phải nhiều thách thức, bao gồm không gian tìm kiếm lớn và sự phức tạp trong việc xác định hàm mục tiêu. Những vấn đề này có thể dẫn đến việc các phương pháp tối ưu hóa truyền thống không đạt được kết quả mong muốn. GA cung cấp một giải pháp hiệu quả bằng cách sử dụng các phương pháp ngẫu nhiên và tiến hóa.

2.1. Thách Thức Trong Tối Ưu Nhiều Biến

Một trong những thách thức lớn nhất trong tối ưu hóa nhiều biến là không gian tìm kiếm khổng lồ. Điều này có thể dẫn đến việc mất nhiều thời gian và tài nguyên để tìm kiếm giải pháp tối ưu. GA giúp giảm thiểu vấn đề này bằng cách sử dụng các phương pháp chọn lọc và lai ghép để tìm kiếm hiệu quả hơn.

2.2. Các Phương Pháp Tối Ưu Hóa Truyền Thống

Các phương pháp tối ưu hóa truyền thống như gradient descent thường gặp khó khăn trong việc tìm kiếm giải pháp tối ưu trong không gian nhiều biến. Những phương pháp này có thể bị kẹt ở các cực tiểu địa phương và không thể tìm ra giải pháp toàn cục. GA cung cấp một cách tiếp cận khác biệt để vượt qua những hạn chế này.

III. Phương Pháp Ứng Dụng Thuật Giải Di Truyền Trong Tối Ưu Nhiều Biến

GA sử dụng một quy trình gồm nhiều bước để tìm kiếm giải pháp tối ưu cho các bài toán nhiều biến. Các bước này bao gồm khởi tạo quần thể, đánh giá hàm thích nghi, chọn lọc, lai ghép và đột biến. Mỗi bước đều đóng vai trò quan trọng trong việc cải thiện chất lượng của các giải pháp.

3.1. Khởi Tạo Quần Thể

Quá trình khởi tạo quần thể là bước đầu tiên trong GA, nơi mà một tập hợp các giải pháp ngẫu nhiên được tạo ra. Điều này giúp đảm bảo rằng GA có một điểm khởi đầu đa dạng để tìm kiếm giải pháp tối ưu.

3.2. Đánh Giá Hàm Thích Nghi

Hàm thích nghi được sử dụng để đánh giá chất lượng của các giải pháp trong quần thể. Các giải pháp tốt hơn sẽ có giá trị thích nghi cao hơn, từ đó được chọn lọc để tạo ra thế hệ tiếp theo.

3.3. Các Toán Tử Lai Ghép và Đột Biến

Toán tử lai ghép và đột biến là hai yếu tố quan trọng trong GA. Lai ghép giúp kết hợp các đặc điểm tốt của các giải pháp khác nhau, trong khi đột biến tạo ra sự đa dạng trong quần thể, giúp tránh kẹt ở các cực tiểu địa phương.

IV. Ứng Dụng Thực Tiễn Của Thuật Giải Di Truyền Trong Tối Ưu Nhiều Biến

GA đã được áp dụng trong nhiều lĩnh vực khác nhau, từ thiết kế kỹ thuật đến tối ưu hóa quy trình sản xuất. Những ứng dụng này không chỉ giúp tiết kiệm thời gian và chi phí mà còn nâng cao hiệu quả trong việc giải quyết các bài toán phức tạp.

4.1. Ứng Dụng Trong Ngành Kỹ Thuật

Trong ngành kỹ thuật, GA được sử dụng để tối ưu hóa thiết kế các bộ phận máy móc, giúp cải thiện hiệu suất và giảm chi phí sản xuất. Ví dụ, GA đã được sử dụng để thiết kế động cơ máy bay và các bộ phận của tuabin.

4.2. Ứng Dụng Trong Kinh Tế

Trong lĩnh vực kinh tế, GA giúp tối ưu hóa các quyết định đầu tư và quản lý tài chính. Các nhà đầu tư có thể sử dụng GA để tìm ra danh mục đầu tư tối ưu, từ đó tối đa hóa lợi nhuận.

V. Kết Luận Về Ứng Dụng Thuật Giải Di Truyền Trong Tối Ưu Nhiều Biến

GA đã chứng minh được giá trị của mình trong việc giải quyết các bài toán tối ưu nhiều biến. Với khả năng mô phỏng quá trình tiến hóa tự nhiên, GA không chỉ giúp tìm ra giải pháp tối ưu mà còn mở ra nhiều cơ hội mới trong nghiên cứu và ứng dụng thực tiễn.

5.1. Tương Lai Của Thuật Giải Di Truyền

Tương lai của GA hứa hẹn sẽ tiếp tục phát triển với sự kết hợp của các công nghệ mới như học máy và trí tuệ nhân tạo. Điều này sẽ giúp GA trở nên mạnh mẽ hơn trong việc giải quyết các bài toán phức tạp trong tương lai.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ với đề tài "Ứng dụng thuật giải di truyền các bài toán hàm mục tiêu nhiều biến" (tiêu đề trong hồ sơ nghiên cứu: "Ứng dụng thuật giải di truyền trong giải bài toán tối ưu") được nghiên cứu sinh Lê Chí Luận thực hiện dưới sự hướng dẫn của cán bộ hướng dẫn có học hàm, học vị Phó Giáo sư - Tiến sĩ Khoa học (PGS.TSKH) tại Trường Đại học Kinh tế thuộc Đại học Quốc gia Hà Nội, hoàn thành năm 2008 thuộc chuyên ngành Công nghệ thông tin (Mã số: 101 10).

Tính cấp thiết và khoảng trống nghiên cứu

Theo phần mở đầu của luận án, sự phát triển của công nghệ phần cứng và kỹ thuật truyền thông trong các thập niên gần đây đã thúc đẩy sự hình thành và mở rộng các hệ thống dữ liệu phức tạp phục vụ hoạt động kinh tế, xã hội và kỹ thuật. Trong bối cảnh đó, các bài toán tối ưu hóa nảy sinh ngày càng nhiều và đòi hỏi năng lực xử lý cao.

Khoảng trống nghiên cứu được tác giả xác định xuất phát từ giới hạn của các phương pháp truyền thống:

• Phương pháp giải tích và công thức toán học cổ điển: Cho kết quả chính xác nhưng đòi hỏi phải thiết lập được mô hình toán học tường minh và đặt ra nhiều giả thiết khó đáp ứng trong điều kiện vận hành thực tế.
• Phương pháp hệ chuyên gia (Expert Systems): Phụ thuộc vào tri thức chuyên gia, gặp khó khăn khi thu thập dữ liệu do sự bất hợp tác hoặc kỹ thuật thu thập không thích ứng; đồng thời không thể giải quyết được các tình huống mới chưa từng phát sinh trong quá khứ.
• Phương pháp tìm kiếm ngẫu nhiên và vét cạn: Không khả thi khi không gian trạng thái quá lớn (ví dụ với bài toán có không gian $10^{30}$, nếu một máy tính xử lý 1 tỷ trường hợp mỗi giây thì cần thời gian tương đương tuổi của Trái Đất để duyệt qua một nửa không gian).
• Phương pháp leo núi (Hill-climbing): Dễ rơi vào và bị kẹt tại các điểm tối ưu cục bộ khi không gian tìm kiếm có nhiều đỉnh cực trị phụ.

Do đó, việc nghiên cứu cơ chế tiến hóa phỏng sinh học và ứng dụng thuật giải di truyền (Genetic Algorithms - GA) nhằm tìm kiếm giải pháp tối ưu cho các bài toán hàm mục tiêu nhiều biến liên tục và bài toán tổ hợp phức tạp là yêu cầu thực tế cấp thiết.

Mục tiêu và câu hỏi nghiên cứu

Mục tiêu tổng quát của luận án bao gồm:

1. Hệ thống hóa nền tảng lý thuyết và cơ chế hoạt động của thuật giải di truyền, bao gồm các phương pháp mã hóa dữ liệu, xác định độ thích nghi, và các toán tử tiến hóa (chọn lọc, lai ghép, đột biến).
2. Xây dựng mô hình và phương pháp luận áp dụng thuật giải di truyền để giải quyết bài toán tối ưu hóa hàm mục tiêu nhiều biến liên tục và bài toán tối ưu tổ hợp.
3. Cài đặt các hàm thuật toán, xây dựng chương trình thử nghiệm để đánh giá khả năng cân bằng và tìm kiếm nghiệm tối ưu của thuật toán di truyền trên mô hình thực tế.

Câu hỏi nghiên cứu được đặt ra:

1. Thuật giải di truyền hoạt động dựa trên những nguyên tắc, tính chất và toán tử cơ bản nào để khắc phục hiện tượng rơi vào cực trị cục bộ?
2. Làm thế nào để biểu diễn không gian nghiệm nhiều biến (bằng chuỗi nhị phân hoặc chuỗi số thực) và tối ưu hóa chi phí bộ nhớ cùng tốc độ truy xuất trên máy tính?
3. Thiết lập hàm thích nghi và cơ chế chọn lọc thế nào để vừa duy trì áp lực chọn lọc vừa bảo tồn tính đa dạng di truyền thông qua độ phân ly?
4. Hiệu quả giải quyết của thuật giải di truyền đối với bài toán cực tiểu hàm $N$ biến liên tục, bài toán lập lịch/thời khóa biểu và bài toán người bán hàng (Travelling Salesman Problem - TSP) đạt mức độ nào?

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Lý thuyết thuật giải di truyền, cấu trúc nhiễm sắc thể, hàm thích nghi, các toán tử tiến hóa (lai ghép đơn điểm, đa điểm, mặt nạ, tạo sinh đường, tạo sinh tức thời; đột biến nhị phân, đột biến giá trị thực) và các lớp bài toán tối ưu hóa hàm nhiều biến, bài toán lập lịch, bài toán người bán hàng.
• Phạm vi nghiên cứu:
  • Về mặt toán học: Tập trung vào bài toán cực tiểu hóa hàm số $f$ với $n$ biến liên tục và các bài toán tối ưu rời rạc có ràng buộc cứng/mềm.
  • Về mặt kỹ thuật cài đặt: Sử dụng các kiểu dữ liệu mảng byte, mảng byte nén, mảng số nguyên tối ưu theo độ dài từ của máy tính (sử dụng ngôn ngữ lập trình Pascal và C/C++).
  • Về mặt thực nghiệm: Đánh giá quá trình hội tụ và khả năng cân bằng hệ thống thông qua các hàm mô phỏng và bài toán thực nghiệm.

---

Tổng quan tài liệu và vị trí của luận án

Luận án điểm lại các mốc phát triển chính của thuật giải di truyền từ thập niên 1950 đến thời điểm nghiên cứu:

Tác giả / Tổ chức	Năm / Thời kỳ	Đóng góp và công trình ghi nhận trong luận án
Fraser	Thập niên 1950 - 1960	Người đầu tiên nêu lên sự tương đồng giữa quá trình tiến hóa của sinh vật và chương trình tin học giả tưởng.
John Henry Holland	1975	Xuất bản cuốn sách nền tảng "Adaptation in Natural and Artificial Systems", được xem là người khai sinh học thuyết thuật giải di truyền tại Đại học Michigan.
Kenneth De Jong & David E. Goldberg	Thập niên 1970 - 1980	Phát triển cơ sở lý thuyết, phân tích tham số tiến hóa (xác định tỉ lệ lai ghép trung bình khoảng 0.6, tỉ lệ đột biến khoảng 0.001, tỉ lệ tạo sinh 0.399). De Jong làm chủ biên nguyệt san Evolutionary Computation (1993).
David E. Goldberg	Đầu thập niên 1980	Ứng dụng GA đầu tiên vào kỹ thuật với đề tài "Computer Aided Gas Pipeline Operation using Genetic Algorithms and Rule learning", dùng ngôn ngữ Pascal trên máy Apple II điều phối mạng lưới bơm van đường ống dẫn khí.
General Electric Co. (GE)	Thập niên 1980 - 1990	Phát triển phần mềm Engineous dùng GA tối ưu hóa thiết kế động cơ máy bay Boeing, cánh quạt tuabin nhiệt điện, cánh quạt tuabin nhà máy điện nguyên tử.
Naval Surface Weapons Center (Bethesda)	-	Ứng dụng công cụ Engineous để thiết kế cánh quạt tàu ngầm.
Chuck Karr	-	Kết hợp GA và Logic mờ (Fuzzy Logic) trong luận án tiến sĩ để chế tạo dụng cụ đo lường ngành mỏ, điều chỉnh độ pH môi trường và thiết lập bộ kiểm soát trực thăng.
Adolph Coors Company (ACC)	-	Ứng dụng GA giải bài toán lập kế hoạch sản xuất cho hơn 500 mặt hàng và 16 dây chuyền sản xuất, thay thế cơ chế "đến trước phục vụ trước" (First-Come First-Served).

Vị trí của luận án: Luận án tiếp thu các nguyên lý nền tảng của Holland và Goldberg, hệ thống hóa chi tiết các phương pháp biểu diễn nhiễm sắc thể (nhị phân, số thực, cây) và các kỹ thuật chọn lọc theo độ phân ly, sau đó mở rộng áp dụng trực tiếp vào lớp bài toán hàm mục tiêu nhiều biến và bài toán tối ưu tổ hợp có ràng buộc phức tạp.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

Luận án dựa trên lý thuyết tính toán tiến hóa (Evolutionary Computation) và các nguyên lý di truyền học sinh học:

• Khái niệm nhiễm sắc thể (Chromosome) biểu diễn cho một cấu trúc dữ liệu mang thông tin của nghiệm.
• Quần thể (Population) gồm tập hợp các cá thể (giải pháp tiềm năng).
• Hàm thích nghi (Fitness Function) và giá trị thích nghi (Fitness Value) đóng vai trò môi trường đánh giá chất lượng nghiệm.
• Các toán tử sinh học phỏng sinh: Tái sinh (Reproduction), Lai ghép (Crossover), Đột biến (Mutation), Chọn lọc (Selection).

Khung thuật toán tổng quát được xác định qua chu trình:

1. Thiết lập $t = 0$; Khởi tạo quần thể ban đầu $P(0)$;
2. Tính độ thích nghi cho các cá thể thuộc $P(t)$;
3. Vòng lặp khi điều kiện dừng chưa thỏa mãn ($t = t + 1$):
   • Tái sinh $P'(t)$ từ $P(t)$;
   • Lai ghép tạo tập cá thể con $Q(t)$ từ $P(t-1)$;
   • Đột biến tạo tập cá thể biến đổi $R(t)$ từ $P(t-1)$;
   • Chọn lọc thế hệ mới $P(t)$ từ tập hợp $P(t-1) \cup Q(t) \cup R(t) \cup P'(t)$;
4. Trả về cá thể có độ thích nghi cao nhất.

Phương pháp nghiên cứu thực tế

Luận án kết hợp giữa phương pháp phân tích mô hình hóa toán học và phương pháp thực nghiệm lập trình mô phỏng:

• Phương pháp biểu diễn và tối ưu không gian nhớ:

  • Mã hóa chuỗi nhị phân: Cài đặt mảng Byte thông thường (ARRAY[0..N-1] OF BYTE hoặc unsigned char Cgen[N]), mảng Byte nén (mỗi byte lưu 8 bit, truy xuất vị trí byte bằng phép chia nguyên n SHR 3 hoặc n >> 3, xác định vị trí bit bằng phép toán n AND 7 hoặc n & 7), và mảng Integer nén phụ thuộc vào độ dài từ của hệ thống thông qua toán tử sizeof.
  • Lượng hóa số thực: Biểu diễn số thực $x \in [\min, \max]$ bằng chuỗi nhị phân độ dài $L$ bit với độ chính xác lượng hóa $g = \frac{\max - \min}{2^L - 1}$, giá trị giải mã được tính bởi công thức: $$x = \min + \text{Decimal}(\langle A \rangle) \times g$$ trong đó $\text{Decimal}(\langle A \rangle) = \sum_{i=0}^{L-1} a_i 2^i$.
  • Mã hóa chuỗi số thực: Biểu diễn nghiệm dưới dạng mảng số thực (ARRAY[0..N-1] OF real hoặc float Cgen[N]).
  • Cấu trúc cây: Sử dụng cây 2 nhánh thông qua biến con trỏ.

• Kỹ thuật đánh giá độ thích nghi:

  • Độ thích nghi tiêu chuẩn: Chuẩn hóa theo tổng quần thể: $$F(a_i) = \frac{G(a_i)}{\sum_{j=1}^N G(a_j)}$$
  • Độ thích nghi xếp hạng: Khắc phục hiện tượng hội tụ cục bộ do một vài cá thể vượt trội gây ra, xác suất chọn của cá thể xếp thứ $i$ được tính theo công thức: $$F(i) = p \times (1 - p)^{i-1} \quad (p \in [0, 1])$$
  • Độ thích nghi xếp hạng dựa trên độ phân ly: Đưa thêm thước đo khoảng cách phân ly của cá thể đối với toàn quần thể: $$P(a_i) = \sum_{j=1, j \neq i}^N \frac{1}{|G(a_i) - G(a_j)|}$$ Giá trị $P(a_i)$ càng bé thì độ phân ly càng lớn. Hạng tổng hợp được xác định bằng tổng hạng theo $G(a_i)$ và hạng theo $P(a_i)$ để bảo tồn các cá thể ở biên không gian tìm kiếm.

---

Nội dung chính theo từng chương

Chương 1: Thuật giải di truyền

Chương 1 tập trung trình bày toàn diện lý thuyết nền tảng của thuật giải di truyền, phân loại các toán tử và minh họa các bài toán mẫu:

1. Các toán tử tiến hóa cơ bản

• Toán tử chọn lọc:
  • Chọn lọc xén (Truncation Selection): Sắp xếp quần thể giảm dần theo độ thích nghi và chọn ra tỉ lệ phần trăm $\text{Trunc}$ (ví dụ $\text{Trunc} = 50%$) cá thể tốt nhất để tham gia sinh sản.
  • Chọn lọc nhiều lần: Phân chia nhóm ngẫu nhiên để chọn lọc.
  • Chọn lọc đấu loại (Tournament Selection): Cho các nhóm nhỏ thi đấu trực tiếp theo giá trị hàm thích nghi.
• Toán tử lai ghép:
  • Lai ghép đơn điểm: Chọn vị trí cắt $k \in [2, N-1]$ chia chuỗi cha mẹ thành hai phần rồi hoán đổi.
  • Lai ghép đa điểm: Chọn các vị trí cắt $k_1, k_2, \dots, k_m$ chia chuỗi thành $m+1$ đoạn, giữ nguyên đoạn vị trí lẻ và hoán đổi đoạn vị trí chẵn.
  • Lai ghép mặt nạ: Sử dụng hai chuỗi nhị phân mặt nạ $m_A$ và $m_B$ (thường chọn $m_A = \text{NOT } m_B$) để sao chép từng gen tương ứng.
  • Tạo sinh đường (Line Recombination): Áp dụng cho chuỗi số thực: $$C_i = \min(A_i, B_i) + \alpha |B_i - A_i| \quad (\alpha \in [-d, 1+d])$$
  • Tạo sinh tức thời: Sử dụng một dãy hệ số ngẫu nhiên $\alpha_i$ riêng biệt cho từng thành phần gen.
• Toán tử đột biến:
  • Đột biến nhị phân: Đảo giá trị bit $0 \leftrightarrow 1$ tại vị trí ngẫu nhiên với xác suất $p_m$.
  • Đột biến trị thực: Biến đổi giá trị gen $A$ thành $A' = A + S \times \text{range} \times \text{delta}$, trong đó $S \in {-1, 1}$, $\text{range} \le \text{độ lớn miền xác định} \times 0.1$, $\text{delta} = \sum_{i=1}^{20} a_i 2^{-i}$ với $a_i = 1$ có xác suất $\frac{1}{20}$. Xác suất đột biến được khuyến nghị chọn tỉ lệ nghịch với chiều dài gen ($1/N$).

2. Các ví dụ minh họa và bài toán áp dụng trong Chương 1

• Bài toán giải phương trình $X^2 = 64$: Tác giả thiết lập hàm thích nghi $F = 1000 - |X^2 - 64|$. Quần thể ban đầu gồm 4 cá thể nhị phân độ dài 5 bit.

| STT | Chuỗi nhị phân ban đầu | Giá trị thập phân | $|X^2 - 64|$ | Độ thích nghi ban đầu | Quá trình lai ghép (điểm cắt giữa bit 3 và 4) | Chuỗi mới tạo thành | Giá trị thập phân mới | Độ thích nghi sau lai ghép | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | 00100 | 4 | 48 | 952 | Chọn lai ghép với cá thể 3 | 00100 (giữ lại) | 4 | 952 | | 2 | 10101 | 21 | 377 | 623 | Bị loại thải (thích nghi thấp) | 01000 (con lai 1) | 8 | 1000 | | 3 | 01010 | 10 | 36 | 964 | Chọn lai ghép với cá thể 1 | 01010 (giữ lại) | 10 | 964 | | 4 | 11000 | 24 | 512 | 488 | Bị loại thải (thích nghi thấp) | 00110 (con lai 2) | 6 | 968 |

Kết quả sau 1 thế hệ lai ghép đã tìm ra chính xác nghiệm tối ưu $X = 8$ (01000) với độ thích nghi cực đại bằng 1000.

• Bài toán lập lịch sửa chữa ô tô: Gồm $n$ ô tô sẵn sàng tại thời điểm $r_i = 0$, mỗi ô tô có thời gian sửa $t_i$ và hạn định hoàn thành $d_i$. Nhà máy xử lý liên tục từng xe không ngắt quãng. Ví dụ với 7 xe: $X_1(d_1=7, t_1=3)$, $X_2(5, 2)$, $X_3(8, 4)$, $X_4(12, 4)$, $X_5(17, 6)$, $X_6(9, 2)$, $X_7(20, 5)$. Nếu xử lý tuần tự $X_1 \to X_7$ chỉ có 2 xe đúng hạn; nếu sắp xếp tối ưu theo thứ tự $X_2, X_1, X_6, X_4, X_5, X_3, X_7$ thì số lượng xe đúng hạn tăng lên 5 xe.

• Bài toán lập thời khóa biểu: Mô hình hóa lịch học thành ma trận kích thước $K$ dòng (số lớp) và 30 cột (6 giờ/ngày $\times$ 5 ngày/tuần).

  • Ràng buộc cứng: Giáo viên không dạy 2 lớp cùng giờ; mỗi lớp chỉ học 1 môn tại 1 giờ; môn học trong lớp do 1 giáo viên duy nhất phụ trách; giáo viên dạy không quá 20 giờ/tuần.
  • Ràng buộc mềm: Giờ trống của lớp; môn học lặp lại trong ngày; độ đồng đều giờ dạy giữa các giáo viên.
  • Hàm thích nghi được thiết lập dựa trên tỉ lệ vi phạm ràng buộc: $$\text{Fitness} = (100 - X) + (20 - Y) + \text{bonus}$$ trong đó $X$ là tỉ lệ lỗi trung bình ràng buộc cứng, $Y$ là tỉ lệ lỗi trung bình ràng buộc mềm (nhân hệ số 0.2).

---

Chương 2: Ứng dụng giải thuật di truyền để giải các bài toán tối ưu nhiều biến

Chương 2 trình bày phương pháp luận và kỹ thuật giải quyết các bài toán tối ưu hóa trong không gian nhiều chiều:

• Biểu diễn biến nhiều chiều bằng vectơ nhị phân: Nghiệm của bài toán gồm $n$ biến $(x_1, x_2, \dots, x_n)$ được mã hóa bằng cách ghép nối tiếp các đoạn nhị phân biểu diễn từng biến thành một nhiễm sắc thể duy nhất có chiều dài $L = \sum_{j=1}^n L_j$.
• Thiết kế các toán tử đa biến:
  • Toán tử chọn lọc cá thể (select).
  • Toán tử lai ghép (crossover) đa điểm trên các ranh giới biến hoặc lai ghép ngẫu nhiên.
  • Toán tử đột biến (mutation) kiểm soát theo từng thành phần biến.
• Lớp bài toán khảo sát:
  • Bài toán cực tiểu hàm số $f$ với $n$ biến liên tục: Xây dựng hàm thích nghi nghịch đảo hoặc hàm chuyển đổi tương ứng với bài toán tìm cực tiểu.
  • Bài toán 1: Bài toán cực tiểu hàm với $N$ biến.
  • Bài toán 2 - Bài toán người bán hàng (Travelling Salesman Problem - TSP): Khảo sát bài toán tìm hành trình ngắn nhất đi qua các thành phố (quy mô thử nghiệm lên tới 120 nút/thành phố).

---

Chương 3: Phân tích và cài đặt thử nghiệm

Chương 3 trình bày chi tiết việc cài đặt chương trình và kết quả thử nghiệm:

• Cấu trúc các mô-đun hàm thuật toán được cài đặt:
  • Hàm khởi tạo giá trị ngẫu nhiên.
  • Hàm khởi tạo giá trị nhị phân (0 hoặc 1) theo phân phối xác suất.
  • Hàm tính trị số thích nghi (Fitness evaluation).
  • Hàm chọn lọc cá thể (select).
  • Hàm mô phỏng toán tử đột biến (mutation).
  • Hàm mô phỏng toán tử lai ghép (crossover).
  • Hàm khởi tạo quần thể ban đầu.
  • Hàm tạo sinh và hàm tái tạo quần thể (reproduction).
  • Hàm điều phối toàn bộ các bước của thuật giải di truyền.
• Thử nghiệm trên mô hình cân bằng hệ thống: Tác giả đưa ra minh họa thiết bị thí nghiệm trước khi cân bằng và trạng thái hội tụ đạt trạng thái cân bằng sau quá trình tối ưu hóa bằng thuật toán di truyền.

---

Kết quả và những đóng góp mới

Dựa trên các nội dung trình bày trong luận án, các kết quả và đóng góp được tổng hợp như sau:

Đóng góp về mặt lý luận và kỹ thuật

1. Hệ thống hóa đầy đủ cơ chế hoạt động của thuật giải di truyền từ các toán tử mã hóa, đánh giá thích nghi, lai ghép, đột biến đến chọn lọc.
2. Xây dựng giải pháp kỹ thuật biểu diễn dữ liệu nhị phân nén (mảng byte nén và mảng integer nén) giúp giảm thiểu dung lượng bộ nhớ tiêu tốn gấp 8 lần so với mảng byte thông thường, đồng thời tối ưu hóa tốc độ tính toán dựa trên các phép toán thao tác bit (SHR, AND, phép dịch bit).
3. Đề xuất phương pháp tính độ thích nghi xếp hạng kết hợp với độ phân ly cá thể $P(a_i)$, cho phép bảo toàn các cá thể dị biệt ở xa vùng tập trung, tránh hiện tượng quần thể bị hút sớm vào các điểm cực trị cục bộ.

Đóng góp về mặt thực tiễn

1. Xây dựng thuật toán và công thức hàm thích nghi giải quyết bài toán lập thời khóa biểu thực tế với hệ thống ràng buộc cứng và mềm phức tạp.
2. Cài đặt hoàn chỉnh bộ chương trình thử nghiệm bằng ngôn ngữ lập trình cho phép giải quyết bài toán cực tiểu hàm $N$ biến liên tục và bài toán tối ưu tổ hợp TSP quy mô 120 điểm.
3. Ứng dụng thành công thuật toán vào bài toán mô phỏng cân bằng thiết bị thí nghiệm.

---

Hạn chế và hướng nghiên cứu tiếp

Hạn chế

• Các bài toán thử nghiệm tập trung chủ yếu vào mô hình mô phỏng, bài toán tối ưu hàm giải tích nhiều biến và bài toán tổ hợp kinh điển (TSP 120 điểm, lập lịch).
• Thao tác truy xuất trên cấu trúc mảng byte nén và bit đòi hỏi thêm các phép toán xử lý bit trung gian nên thời gian truy xuất từng bit riêng lẻ chậm hơn so với mảng byte trực tiếp.

Hướng nghiên cứu tiếp

• Mở rộng nghiên cứu kết hợp thuật giải di truyền với các kỹ thuật trí tuệ nhân tạo khác như Mạng nơ-ron nhân tạo (ANN) và Logic mờ (Fuzzy Logic) để giải quyết các bài toán điều khiển và tối ưu động trong thời gian thực.
• Cải tiến các toán tử lai ghép và đột biến thích nghi theo từng giai đoạn tiến hóa để tăng tốc độ hội tụ khi giải các bài toán tối ưu hàm số có số lượng biến lớn hơn.

---

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên khảo trong lĩnh vực Công nghệ thông tin và Toán ứng dụng:

• Đối với nghiên cứu sinh và học viên cao học: Cung cấp cơ sở lý thuyết chi tiết, các công thức toán học về lượng hóa số thực, các biến thể của toán tử lai ghép/đột biến và phương pháp thiết kế hàm thích nghi.
• Đối với lập trình viên và kỹ sư phần mềm: Cung cấp các cấu trúc dữ liệu tối ưu bộ nhớ (mảng byte nén, mảng integer) và mã giả thuật toán bằng ngôn ngữ Pascal, C/C++ có thể tái sử dụng trực tiếp trong các bài toán tối ưu hóa công nghiệp, vận tải và lập lịch sản xuất.
• Đối với các nhà quản lý và hoạch định: Cung cấp phương pháp luận giải quyết bài toán lập lịch, điều phối dây chuyền sản xuất và quy hoạch mạng lưới giao thông.

---

Câu hỏi thường gặp

1. Luận án giải quyết nhược điểm rơi vào cực trị cục bộ của phương pháp leo núi bằng cách nào?

Thuật giải di truyền làm việc đồng thời trên một quần thể gồm nhiều cá thể (tương đương nhiều người cùng leo núi ở các vị trí khác nhau). Ngoài ra, luận án áp dụng cơ chế tính độ thích nghi xếp hạng kết hợp độ phân ly $P(a_i)$ và toán tử đột biến ngẫu nhiên, giúp tạo ra các cá thể mới nằm ngoài vùng tập trung hiện tại, tránh hiện tượng toàn bộ quần thể bị hút về một ngọn núi thấp.

2. Sự khác biệt giữa mảng byte thông thường và mảng byte nén trong biểu diễn gen là gì?

• Mảng byte thông thường: Mỗi byte chỉ lưu 1 bit (0 hoặc 1), truy xuất nhanh nhưng lãng phí 7 bit trong mỗi byte (tốn bộ nhớ gấp 8 lần).
• Mảng byte nén: Mỗi byte lưu đúng 8 bit dữ liệu. Vị trí byte chứa bit thứ $n$ được xác định bằng phép chia n DIV 8 (n SHR 3), vị trí bit trong byte xác định bằng phép chia dư n MOD 8 (n AND 7). Cách này tiết kiệm tối đa bộ nhớ nhưng tốn thêm chi phí thao tác bit khi truy xuất.

3. Công thức lượng hóa số thực $x \in [\min, \max]$ sang chuỗi nhị phân $L$ bit được xác định như thế nào?

Đoạn $[\min, \max]$ được chia thành $2^L - 1$ vùng với độ chính xác: $$g = \frac{\max - \min}{2^L - 1}$$ Giá trị số thực tương ứng của chuỗi nhị phân $A$ là: $$x = \min + \text{Decimal}(\langle A \rangle) \times g$$ trong đó $\text{Decimal}(\langle A \rangle)$ là giá trị nguyên hệ thập phân của chuỗi nhị phân $A$.

4. Trong bài toán lập thời khóa biểu, hàm thích nghi được tính toán ra sao?

Hàm thích nghi được xây dựng dựa trên tỉ lệ vi phạm ràng buộc: $$\text{Fitness} = (100 - X) + (20 - Y) + \text{bonus}$$ trong đó $X$ là tỉ lệ lỗi trung bình của các ràng buộc cứng (như giáo viên trùng giờ dạy, lớp học trùng môn), $Y$ là tỉ lệ lỗi trung bình của các ràng buộc mềm (giờ trống, môn học trùng lặp).

---

Kết luận

Luận án tiến sĩ "Ứng dụng thuật giải di truyền các bài toán hàm mục tiêu nhiều biến" của tác giả Lê Chí Luận đã hệ thống hóa cơ sở lý thuyết của thuật toán di truyền, phân tích các giải pháp mã hóa cấu trúc dữ liệu nhị phân nén và số thực, đồng thời thiết lập các phương pháp xác định độ thích nghi theo thứ hạng và độ phân ly nhằm duy trì tính đa dạng của quần thể. Công trình đã cài đặt thành công các mô-đun thuật toán, áp dụng hiệu quả vào bài toán cực tiểu hàm số $N$ biến liên tục, bài toán lập lịch, bài toán người bán hàng và mô hình thí nghiệm cân bằng hệ thống. Luận án đóng góp tài liệu nghiên cứu và thuật toán thực nghiệm cho lĩnh vực tối ưu hóa tính toán trong Công nghệ thông tin.

Trích đoạn nội dung tài liệu

Chương 1. THUẬT GIẢI DI TRUYỀN 1. Tổng quan về thuật giải di truyền [2] 1. Thuật giải di truyền là gì? Trong sinh hoạt hàng ngày, thường gặp nhiều vấn đề từ đơn giản đến phức tạp.

Có những vấn đề liên quan đến sinh hoạt cá nhân như chọn trường cho con em, tìm lộ trình ngắn nhất để đi làm mỗi ngày hoặc những vấn đề liên quan đến công việc tại cơ quan như: hoạch định chương trình chạy máy để tận dụng khả năng các dụng cụ, đảm bảo chất lượng và thoả mãn yêu cầu của khách hàng. Để giải quyết vấn đề, ở nhiều trường hợp, chúng ta có vô số giải pháp nhưng không có giải pháp vạn năng theo nghĩa chúng có thể giải mọi lớp bài toán với hiệu quả cao, có những trường hợp quá phức tạp không có giải pháp nào trước mắt hay không biết phải bắt đầu tìm kiếm từ đâu. Để giải quyết vấn đề thường dựa vào các phương thức sau đây: 1. Dựa trên các công thức toán học hay những định luật khoa học (tiếp cận chính xác).

Dựa theo ý kiến của các chuyên gia lĩnh vực (tiếp cận kinh nghiệm). Dựa theo sự tiến hoá, bắt chước các qui trình thích nghi và tiến hoá của sinh giới nói chung. Phương thức dựa trên các công thức toán học hay những định luật khoa học thường cho những đáp số chính xác. Tuy nhiên yếu điểm chính của nó là phải tìm ra công thức hay giả tưỏng những điều kiện hoạt động cho giống với thực tế, điều này không thể thực hiện một cách dễ dàng và nhanh chóng.

Trong hơn 20 năm qua, lĩnh vực trí tuệ nhân tạo đã được sử dụng để giúp giải quyết vấn đề. Nguyên tắc cơ bản của phương thức này là kết hợp kiến thức của các chuyên gia với chương trình tin học để dùng máy tính thay con người giải quyết vấn đề một cách khôn ngoan. Nhiều chương trình tin học như Mycin, Prospector v.v… đã thành công trong một số lĩnh vực cụ thể; tuy nhiên đối với những vấn đề chưa hề xảy ra, hệ chuyên gia không thể giúp giải quyết được vấn đề. Nhược điểm quan trọng nhất của hệ chuyên gia là khi thu thập kiến thức của các chuyên gia lĩnh vực, chúng ta không có được những ý kiến trung thực có thể vì các chuyên gia thiếu tinh LUAN VAN CHAT LUONG download : add [e-mail] -9 - thần hợp tác hoặc cũng có thể do kỹ thuật thu nhập không thích nghi.

Do đó kể từ những năm 90, thế kỉ 20, hệ chuyên gia không còn là kỹ thuật thích hợp nhất để giải quyết vấn đề. Từ đấy, khuynh hướng trở về với bản thể con người được xem là cứu cánh để giải quyết vấn đề. Trong những năm 70, Mạng nơron nhân tạo, Logic mờ, cùng với Thuật giải di truyền được nghiên cứu và áp dụng thành công trong việc giải quyết các trường hợp phức tạp. Nhìn chung con người và sinh vật đều phải tiến hoá để thích nghi với hoàn cảnh.

Vào thời kỳ đồ đá con người phải sống trong hang núi và dùng các dụng cụ thô sơ. Những bộ lạc du mục phải biết sống cho thích nghi với thời tiết và địa phương mà họ tạm cư. Sang thời đại tin học, mọi sinh hoạt đều diễn ra quanh máy vi tính nhiệm màu. Các nhà khảo cổ đã tìm ra những chứng tích của các loài khủng long sống hơn triệu triệu năm trên quả đất này.

Vào thời đó nhiệt độ của địa cầu còn khá nóng nên mọi sinh vật phải có da dày, chân cao để chạy nhanh. Tiến hoá cho thích nghi với điều kiện của môi trường chung quanh để tồn tại và phát triển là chứng cớ hiển nhiên mà con người và sinh vậtt đã phải thực hiện. Tiến hoá cho thích nghi không có nghĩa là luôn luôn tìm ra giải pháp tuyệt đối cho vấn đề, nhưng có thể chỉ là tương đối trong điều kiện cho phép. Lịch sử phát triễn của giải thuật di truyền Y niệm về thuật giải di truyền đã được một số nhà sinh vật học nêu ra từ những năm 50, 60, thế kỉ XX.

Fraser là người đầu tiên đã nêu lên sự tương đồng giữa sự tiến hoá của sinh vật và chương trình tin học giả tưởng về GA. Tuy nhiên chính John Henry Holland, đại học Michigan, mới là ngưòi triển khai ý tưởng và phương thức giải quýêt vấn đề dựa theo sự tiến hoá của con người. Ông bắt đầu bằng những bài giảng và bài báo, sau đó đúc kết các ý tưởng thành sách: Adaptation in Natural and Artificial Systems, xuất bản năm 1975. Holland được xem là “người khai sinh “ của học thuyết Thuật giải di truyền.

Trong giai đoạn đầu, thập niên 70 và 80, thế kỉ XX, phần lớn các nhà nghiên cứu và ứng dụng của GA đều được đào tạo tại đại học Michigan, và dưới sự hướng dẫn của J. Holland và một số đồng nghiệp như Kenneth De Jong, David E. Goldberg đã dần dần xây dựng nền LUAN VAN CHAT LUONG download : add [e-mail] - 10 - tảng lý thuyết và thực hiện các áp dụng của GA để giải quýêt các vấn đề phức tạp trong thực tế. Tạp chí đầu tiên về lý thuyết và ứng dụng của GA là nguyệt san Evulutionary Computation (1993) do Kenneth De Jong chủ biên, ngoài ra còn có nguyệt san AI Expert, Artificial Intelligent cũng thường có bài đề cập về GA.

Tuy chỉ mới được hình thành cách đây chưa đầy 25 năm, GA đã có được cơ sở toán học vững chắc về lý thuyết và số lượng những áp dụng ngày càng gia tăng bao gồm nhiều lĩnh vực khác nhau. GA đã kết hợp với các kỹ thuật thuộc lĩnh vực trí tuệ nhân tạo như Expert Systems (Hệ chuyên gia), Mạng nơron nhân tạo (Artificial Neural Network) và Lôgic mờ (Fuzzy Logic) nhằm tìm giải pháp tối ưu cho những vấn đề phức tạp mà phương thức cổ điển đã không giải quýêt thoả đáng. GA được ứng dụng trong nhiều lĩnh vực khác nhau, từ khoa học tự nhiên đến khoa học nhân văn, từ kỹ thuật sang thương vụ và kinh tế- tài chính. Nhìn chung, những ứng dụng này có thể chia làm ba nhóm chính:  Tìm mô hình tối ưu.

Tìm kiếm và tối ưu hoá giải pháp là đề tài thích hợp nhất của GA.  Hoạch định quy trình sản xuất, lộ trình chuyển vận, cách bố trí các bộ phận trong môi trường. Những ứng dụng loại này được dùng trong ngành giao thông, chế tạo sản phẩm, tiếp thị v.v…  Chọn lựa các nhóm hay thành phần trong một tổ chức. Chúng ta cũng có thể sắp xếp các ứng dụng theo lĩnh vực như: quản trị, kinh tế- tài chính, kỹ thuật, nghiên cứu và phát triển.

Từ ngẫu nhiên đến thuật giải di truyền Xét bài toán tìm mật mã để mở khoá với mật mã là một con số thập phân có 30 chữ số với giả sử rằng ổ khoá này chỉ có thể mở bằng một mật mã duy nhất. Đối với bài toán này không gian tìm kiếm là 1030, nghĩa là sẽ có tổng cộng 1030 mật mã khác nhau. Để giải quyết vấn đề này ta thường chỉ nghĩ đến hai phương pháp : Vét cạn toàn bộ hoặc thử ngẫu nhiên các mật mã. Ta phát sinh ( ngẫu nhiên hoặc tuâầntự theo một quy tắc duyệt nào đó) các mã khoá rồi thử xem mật mã này có thể là mã khoá đúng không.

Với phương pháp này, để có được một mật mã với khả năng mở được ổ khoá là trên 50%, ta đã phải phát sinh nhiều hơn 1030/2 mật mã. Con số này quá lớn, trên thực tế, nếu dùng siêu máy tính Cray và giả sử rằng cứ mỗi một phần tỷ giây thì máy này có thể phát sinh và thử nghiệm được một mật mã LUAN VAN CHAT LUONG download : add [e-mail] - 11 - (nghĩa là một giây Gray thử được 1 tỷ mật mã) thì nó phải chạy trong một khoảng thời gian tương đương với tuổi của trái đất để thử trên 1030/2 mật mã. Đứng trước mhững bài toán như vậy, người ta thường tìm cách cải thiện thuật toán bằng cách cung cấp thêm một số thông tin khác. Chẳng hạn như thông tin 2 mật mã được phát sinh ra, mật mã nào tốt hơn (nghĩa là có khả năng mở kháo cao hơn).

Khi biết được độ tốt của các mật mã, ta sử dụng một phương pháp tìm kiếm thông minh hơn – người ta thường gọi là tìm kiếm theo kiểu leo núi (hill-climbing). Với tìm kiếm leo núi, ta tưởng tượng rằng không gian tìm kiếm của vấn đề bài toán là một vùng đất gập ghềnh(landscape), có nhiều ngọn đồi cao thấp khác nhau. Trong đó, ngọn đồi cao nhất của vùng đất này sẽ là lời giải tốt nhất và vị trí có độ cao càng lớn thì càng gần với lời với lời giải tốt nhất (độ cao đồng nghĩa với độ tốt của lời giải). Tìm kiếm theo kiểu leo núi có nghĩa là chúng ta phải phát sinh các lời giải sao cho càng về sau các lời giải càng tiến gần tới lời giải tốt nhất hơn.

Thao tác này cũng giống như thao tác leo núi vậy ( vì càng ngày càng lên cao hơn). Kiểu giải quyết này vẫn còn gặp trở ngại cơ bản là, nếu vùng đất của chúng ta có nhiều núi nhỏ khác bên cạnh ngọn núi cao nhất thì sẽ có khả năng thuật toán bị kẹt ở một ngọn núi nhỏ. Do tư tưởng là càng ngày càng lên cao nên khi lên đến đỉnh một ngọn núi nhỏ thuật toán sẽ không thể đi tiếp được (vì không thể lên cao được nữa, muốn tìm đến ngọn núi cao hơn thì phải xuống núi hiện tại, mà xuống núi thì không đúng tư tưởng càng ngày càng lên cao). Hã tuởng tượng một máy tính giải quyết vấn đề- bài toán theo kiểu leo núi là một nguời leo núi với tư tưởng „càng leo càng cao‟.

Nếu chỉ có một người leo núi thì khả năng người đó bị „kẹt‟ trên một đỉnh núi thấp. Nếu có nhiều người leo núi cùng leo ở nhiều điểm khác nhau thì khả năng có người leo đến đỉnh núi cao nhất sẽ cao hơn. Càng nhiều nguời thì khả năng đến đỉnh núi cao nhất sẽ cao hơn. Càng nhiều người thì khả năng đến đỉnh núi cao nhất sẽ cao hơn.

Tư tuởng này cũng chưa có gì mới mẻ, đơn giản chỉ là dùng nhiều máy tính để chia việc ra mà thôi. Hơn nữa, với không gian tìm kiếm cỡ 1030 như bài toán mở khoá, chúng ta phải cần bao nhiêu siêu máy tính ? Mà quan trọng hơn nữa, cho dù có nhiều người cùng lêo núi, nhưng số lượng người leo núi quá ít so với số lượng núi thì khả năng tất cả người leo núi đều bị „kẹt‟ cũng vẫn còn cao. Từ đó người ta nảy ra ý nghĩ tạo ra nhiều thế hệ người leo núi ?