Tài liệu Nghiên cứu các thuật toán tiến hóa quần thể ứng dụng cho bài toán người đưa hàng

LỜI CẢM ƠN Qua thời gian học tập và rèn luyện tại Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên, đến nay chúng em đã kết thúc khoá học 5 năm và hoàn thành đồ án tốt nghiệp. Ngoài sự cố gắng hết mình của bản thân chúng em đã nhận được rất nhiều sự quan tâm, giúp đỡ, ủng hộ của các thầy cô, bạn bè và gia đình.. Trước hết, em xin gửi lời cảm ơn đến Ban giám hiệu Đại học Công nghệ thông tin và truyền thông đã quan tâm, tạo điều kiện thuận lợi để chúng em học tập và rèn luyện trong suốt thời gian theo học tại trường. Em cũng xin cảm ơn các thầy cô giáo trong bộ môn Khoa học máy tính đã tận tình giảng dạy và truyền đạt những kiến thức quý báu cho chúng em trong suốt quá trình học tập. Em xin gửi lời cảm ơn sâu sắc nhất đến Cô giáo – Dương Thị Mại Thương đã tận tình hướng dẫn, giúp đỡ em trong quá trình làm đồ án. Thái Nguyên, ngày 11 tháng 06 năm 2012 Sinh viên thực hiện Nguyễn Thị Hiền 1 LỜI CAM ĐOAN Để hoàn thành đồ án tốt nghiệp đúng thời gian quy định và đáp ứng được yêu cầu đề ra, bản thân em đã cố gắng nghiên cứu, học tập và làm việc trong thời gian dài. Em đã tham khảo một số tài liệu được nêu trong phần “Tài liệu tham khảo” và có được sự hướng dẫn tận tình của cô giáo Dương Thị Mai Thương. Nội dung đồ án hoàn toàn không sao chép từ các đồ án khác, không vi phạm bản quyền tác giả. Toàn bộ đồ án là do bản thân em nghiên cứu và xây dựng nên. Em xin cam đoan những lời trên là đúng, nếu có thông tin sai lệch em xin hoàn toàn chịu trách nhiệm trước Hội đồng. Thái Nguyên, ngày 11 tháng 06 năm 2012 Sinh viên thực hiện Nguyễn Thị Hiền 2 MỤC LỤC LỜI NÓI ĐẦU.............................................................................................................................4 MỞ ĐẦU.....................................................................................................................................5 CHƯƠNG 1:GIỚI THIÊÊU TỔNG QUAN QUẦN THỂ, CÁC THUẤT TOÁN TIẾN HOÁ QUẦN THỂ.................................................................................................................................8 1.1 Giới Thiê Êu Cơ Sở Sinh Học Của Lý Thuyết Quần Thể(Bầy Đàn)......................................8 1.1.1. Ong mật di chuyển...................................................................................................16 1.1.2.Châu chấu..................................................................................................................18 1.2.Các thuâ Êt toán Metaheuristic............................................................................................25 1.2.1. Tìm hiểu mô Êt số thuâ Êt toán kinh điển........................................................................25 1.2.2.Các thuâ Êt toán Metaheuristic.....................................................................................26 CHƯƠNG 2:PHƯƠNG PHÁP TỐI ƯU BẦY ĐÀN..................................................................32 2.1.Trí tuê Ê bầy đàn..................................................................................................................32 2.1.1.Khái niê Êm..................................................................................................................32 2.1.2. Ứng Dụng Trí Tuê Ê Bầy Đàn......................................................................................33 2.2.Phương Pháp Tối Ưu Bầy Đàn.........................................................................................35 2.2.1 Nguồn Gốc Của Ant Colony Tối Ưu Hóa..................................................................35 2.2.2 Ant Colony Tối ưu hóa: Mô tả chung........................................................................42 2.2.3 Xu hướng gần đây.....................................................................................................48 CHƯƠNG 3 : NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN ACO (ANT COLONY OPTIMIZATION) CHO BÀI TOÁN NGƯỜI ĐƯA HÀNG......................................................52 3.1 Bài toán người đưa hàng...................................................................................................52 3.2. Thuật toán ACO...............................................................................................................53 3.3 Phân tích và mô hình hoá bài toán....................................................................................57 3.3.1 Tối ưu đa mục tiêu (MULTI-OBJECTIVE OPTIMIZATION)..................................58 3.3.2. Phân tích giải thuâ Êt...................................................................................................58 3.4. Kêt quả của giải thuâ tÊ , đánh giá và so sánh với thuâ tÊ toán Hueristic khác..........................63 KẾT LUẬN................................................................................................................................65 TÀI LIÊÊU THAM KHẢO..........................................................................................................66 3 LỜI NÓI ĐẦU Công nghệ thông tin(CNTT) là một trong những động lực quan trọng nhất của sự phát triển,cùng với một số nghành công nghệ khác đang làm biến đổi sâu sắc đời sống kinh tế , văn hóa, xã hội của thế giới hiện đại. Hiện nay hầu hết các cơ quan chức năng nhà nước hoặc tư nhân đều có sự góp mặt của tin học nhằm giải phóng sức mạnh vật chất trí tuệ và tinh thần của toàn dân tộc thúc đẩy công cuộc đổi mới phát triển nhanh và hiện đại hóa các ngành kinh tế là một công cụ lưu trữ và xử lý thông tin một cách hoàn hảo từ tốc độ đến sự chính xác cao tăng cường sức cạnh tranh của các doanh nghiệp hỗ trợ hiệu quả cho quá trình hội nhập kinh tế quốc dân nâng cao chất lượng cuộc sống có khả năng đi tắt đón đầu thắng lợi sự nghiệp công nghiệp hóa,hiện đại hóa. Bởi vậy tin học đang được sử dụng rộng rãi trong các trường học là những sinh viên đã được trang bị các kiến thức tin học, nhờ sự giảng dạy của thầy cô và học hỏi từ bạn bè. Đến nay có thể vận dụng những kiến thức đã có giải quyết những công việc cụ thể một cách nhanh chóng cũng chính vì vậy mà ban giám hiệu nhà trường đã tạo điều kiện cho chúng em làm đồ án tốt nghiê Êp với đề tài : ”Nghiên cứu các thuâ ât toán tiến hoá quần thể, ứng dụng cho bài toán người đưa hàng ” Song vì thời gian thực hiện có hạn.Vì vậy có chỗ nào thiếu sót mong thầy cô giáo đóng góp ý kiến cho em.Em xin chân thành cảm ơn cô Dương Thị Mai Thương đã tận tình giúp đỡ em hoàn thành đề tài này. Để hoàn thành đồ án tốt nghiê Êp này, em đã nhận sự giúp đỡ tận tình của cô Dương Thị Mai Thương- người đã trực tiếp hướng dẫn em làm đề tài và các thầy cô trong khoa.Cùng sự cổ vũ lớn lao, khích lệ của gia đình và bạn bè. Đã hoàn thành báo cáo của mình. Em xin chân thành cảm ơn và ghi nhận những tấm lòng ấy. Thái Nguyên, ngày 11 tháng 06 năm 2012 Sinh viên thực hiện: 4 Nguyễn Thị Hiền. MỞ ĐẦU Giới thiệu chung Mục đích của bài toán tối ưu tổ hợp là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc .Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân lọai thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ )trong giới hạn thời gian cho phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được nghiên cứu sâu trong lĩnh vực tối ưu tổ hợp. Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc giải quyết các bài toán tổ hợp khó. Metaheuristic bao gồm những chiến lược khác nhau trong việc khám phá không gian tìm kiếm bằng cách sử dụng những phương thức khác nhau và phải đạt được sự cân bằng giữa tính đa dạng và chuyên sâu của không gian tìm kiếm. Một cài đặt thành công của metaheuristic trong một bài toán tổ hợp phải cân bằng giữa sự khai thác được kinh nghiệm thu thập được trong quá trình tìm kiếm để xác định được những vùng với những lời giải có chất lượng cao gần tối ưu. Những ví dụ của metaheuristic bao gồm giải thuật luyện thép (SA) , giải thuật di truyền (GA) , giải thuật đàn kiến (ACO) ,… Giải thuật đàn kiến là metaheuristic dùng chiến lược của kiến trong thế giới thực để giải bài toán tối ưu. SA xuất phát từ phương thức xác suất và kỹ thuật luyện bao gồm việc nung và điều khiển làm nguội các kim loại để đạt được trạng thái năng lượng nhỏ nhất .Trong khi đó giải thuật di truyền dựa trên ý tưởng từ cơ chế di truyền trong sinh học và tiến trình tiến hóa trong cộng đồng các cá thể của 1 loài. Với độ phức tạp tính toán cao của các bài toán tối ưu tổ hợp cũng như đòi hỏi về mặt thời gian , việc giải các bài toán này yêu cầu cần phải có những cài đặt song song hóa hiệu quả của các giải thuật để giải quyết chúng. Song song hóa các giải thuật metaheuristic phải đạt được 2 yêu cầu : đa dạng hóa để khám phá được nhiều vùng trong không gian tìm kiếm và tăng tốc độ tìm kiếm . Nhiều mô hình song song hoái đã được đề xuất cho nhiều metaheuristic. ACO và GA đều là các cách tiếp cận dựa trên tập cá thể và vì vậy khá tự nhiên cho việc xử lý song song . Tuy nhiên SA thì vốn đã mang tính tuần tự và rất chậm cho các bài toán 5 với không gian tìm kiếm lớn nhưng vẫn có một vài kỹ thuật song song hóa có thể được áp dụng để tăng tốc độ tìm kiếm. Đồ án nhằm mục đích nghiên cứu ,cài đặt thực tế các giải thuật song song hóa metaheuristic nhằm mục đích so sánh hiệu quả của từng giải thuật và khả năng song song hóa của các mô hình song song cho việc tìm kiếm lời giản gần tối ưu của bài toán TSP. 6 CHƯƠNG 1:GIỚI THIÊâU TỔNG QUAN QUẦN THỂ, CÁC THUẤT TOÁN TIẾN HOÁ QUẦN THỂ 1.1 Giới Thiê âu Cơ Sở Sinh Học Của Lý Thuyết Quần Thể(Bầy Đàn) Khi người Ai Cập lần đầu tiên bắt đầu để giữ cho ong mật 5.000 năm trước, họ chắc chắn phải ngạc nhiên về vẻ đẹp của chiếc lược của các con ong. Không chỉ là tổ ong đẹp, nhưng làm thế nào những con ong quyết định để xây dựng các tế bào lục giác và không phải là tế bào hình thức khác? Ban đầu nó đã được đề xuất rằng các tế bào lục giác giữ mật ong nhất, nhưng các nhà vật lý Pháp RAF de R'eaumur nhận ra rằng nó không phải là tính các tế bào, nhưng số tiền sáp, vật liệu, đó là cần thiết để phân chia một khu vực nhất định vào các tế bào bằng nhau. Rõ ràng tại thời điểm đó nó đã được giả định rằng những con ong "bằng cách mù quáng đã sử dụng đô Êt phá toán học bằng cách hướng dẫn của Thiên Chúa và lệnh "(Ball 1999). Mãi cho đến Darwin mới đưa ra quan điểm là sự hướng dẫn thiêng liêng đã được gỡ bỏ và các tế bào lục giác được cho là kết quả của chọn lọc tự nhiên. Theo quan điểm này, tổ tiên của những con ong 'thử nghiệm' với các tế bào hình khác nhau, nhưng những con ong mà tình cờ 'quyết định' để xây dựng các tế bào lục giác đã làm tốt hơn, và như là một kết quả, xây dựng các tế bào lục giác lây lan. Nói cách Darwin, “Vì vậy, như tôi tin rằng, hầu hết các chiến thắng của tất cả các bản năng được biết đến, đó là con ong, tổ ong có thể được giải thích là do tự nhiên lựa chọn nhiều lần, liên tiếp, thay đổi chút ít bản năng đơn giản, chọn lọc tự nhiên có độ chậm, nhiều hơn và nhiều hơn nữa để đạt đô Ê hoàn hảo, đã khiến những con ong làm viê Êc bình đẳng tại một khoảng cách nhất định từ mỗi một lớp kép”. Trong thực tế, nhiều trường hợp hình thành mô hình tự phát có thể được giải thích bởi các lực lượng vật lý, và các mảng gần như vô tận của các mẫu và hình dạng được tìm thấy xung quanh chúng ta.Sau khi kiểm tra chặt chẽ hơn, sự tương đồng tuyệt vời bộc lộ ra giữa các mô hình và hình dạng của các đối tượng rất khác nhau, các đối tượng sinh học cũng như bẩm sinh.Như đã ám chỉ ở trên, mô hình lục giác đặc trưng được tìm thấy trên tổ ong không phải là duy nhất, cùng một khuôn mẫu có thể thu được bằng cách nung nóng một chất lỏng thống 7 nhất từ dưới lên.Hệ thống khuếch tán Autocatalytic phản ứng sẽ dẫn đến mô hình Turing (nghĩ sọc trên con hổ) trong cả hai hóa chất và phương tiện sinh học (Kondo và Asai 1995; bóng 1999), và khoáng chất hình thành mô hình đã được nhầm lẫn cho thêm hóa thạch trên mặt đất (McKay et al1996).. Tất cả các mô hình mô tả ở trên đã được giải thích bằng cách tiếp cận các hệ thống từ dưới lên: và làm thế nào để các hạt tương tác với nhau với môi trường trực tiếp của mình? Một người có thể không thực sự ngạc nhiên bởi thực tế là phương pháp tương tự giúp người ta hiểu các phân tử. Trong phần sau đây sẽ minh họa làm thế nào một cách tiếp cận từ dưới lên có thể giải thích một tính năng đáng chú ý của ong mật: các mô hình điển hình của phấn hoa, mật ong và cá bố mẹ được tìm thấy trên lược. Các của ong mật lược là không chỉ là 1 ngạc nhiên vì gần như các tế bào lục giác của nó hoàn hảo, những con ong dường như làm các tế bào với bố mẹ (trứng có phát triển thành ấu trùng và sau đó nhộng nổi lên như là công nhân trẻ tuổi hoặc nam giới), phấn hoa (để nuôi bố mẹ) và mật hoa (mà sẽ được chuyển đổi thành mật ong) trong một mô hình đặc trưng. Mô hình này bao gồm ba khu vực khác nhau, đồng tâm: một khu vực trung tâm bố mẹ, viền xung quanh phấn hoa, và một lớn khu vực ngoại vi của mật ong (Hình 1). Nếu chúng ta hình dung thuộc địa ong mật là một cấu trúc ba chiều, mô hình này được phát âm trong các lược trung tâm, nơi giao nhau một phần lớn khối lượng gần như hình cầu của bố mẹ. Làm thế nào để mô hình này? Các lưu trữ gần phấn hoa để bố mẹ chắc chắn làm cho ý nghĩa vì nó làm giảm thời gian cần thiết để có được những phấn hoa tới bố mẹ. Nhưng làm thế nào để những con ong biết điều này? Họ sử dụng một bản thiết kế (hoặc mẫu) để sản xuất mô hình đặc trưng này, ngụ ý rằng có vị trí đặc biệt quy định cho sự lắng đọng của mật hoa, phấn hoa và bố mẹ? Hoặc là mô hình selforganized và nổi lên một cách tự nhiên từ sự năng động tương tác giữa các con ong chúa, ong thợ của chúng và bố mẹ? Scott Camazine thiết lập để xác định hai giả thuyết này là hầu hết tiêu dùng tiết kiệm (Camazine 1991). Vẻ đẹp của việc làm trên các thực thể vĩ mô như côn trùng là cá nhân bạn có thể đánh dấu chúng. Sau đó có thể chứa chúng trong tổ quan sát, một ngôi nhà 8 vách kính cho những con ong.Điều này có thể biết sự tương tác của những con ong cá nhân đánh dấu mà không cần lấy chúng ra khỏi môi trường tự nhiên của chúng (xem hình 1).. Hình1.Do kích thước tương đối lớn, chúng ta có thể dễ dàng đánh dấu những con ong cá nhân ở thuộc địa.Trong thuộc địa đặc biệt này đã đánh dấu 5.000 con ong bằng cách kết hợp biển số và màu sơn khác nhau.Điều này cho phép chúng ta nghiên cứu hành vi của chúng ở một mức độ cá nhân. Camazine đã làm điều đó. Ông theo dõi hành vi đẻ trứng của ong chúa, kiếm ăn trở lại với phấn hoa hay mật hoa, và ong thợ, những cá thể mang thức ăn cho cá bố mẹ. Việc đầu tiên mà ông quan sát được rằng ong chúa khá cẩu thả trong hành vi đẻ trứng của mình, di chuyển về trong zig-zag như cách thức, thường bị thiếu các tế bào có sản phẩm nào và retracing bước của mình. Camazine hơn nữa nhận thấy rằng ong chúa có một sở thích rõ ràng để đặt một khoảng cách nhất định từ ngoại biên của lược và không bao giờ nhiều hơn một vài độ dài tế bào của các tế bào bố mẹ có chứa gần nhất. Mặc dù ong chúa phần nào có một chút ưu tiên ít nhất là giữa của lược và vùng phụ cận của bố mẹ, con ong trở về với phấn hoa hay mật hoa không có vẻ có một ưu đãi cho các tế bào cụ thể ở tất cả. Mặc dù không có ưu tiên rõ ràng bác bỏ giả thuyết kế hoạch chi tiết, nó không giải thích làm thế nào các mô hình đặc trưng cuối cùng phát sinh Khi nó quay ra, ong có một sở thích rõ ràng khi chúng loại bỏ phấn hoa, mật ong từ các tế bào. Cả mật ong và phấn hoa được ưu tiên từ các tế bào gần nhất để bố mẹ. Bằng cách làm theo các mô hình của tế bào làm rỗng trong một khoảng thời gian trong hoạt ðộng tìm kiếm thức ãn thấp (qua ðêm hoặc trong mýa), Camazine quan sát thấy rằng tất cả các tế bào ðã được làm trống của phấn hoa hay mật hoa của chúng được đặt trong hai tế bào từ một tế bào có chứa cá bố 9 mẹ. Không có tế bào được làm trống hơn nữa từ các tế bào bố mẹ. Nó rất dễ dàng để xem lý do tại sao những con ong sẽ có một sở thích cho việc loại bỏ (thông qua sử dụng) của phấn hoa được tìm thấy gần nhất để bố mẹ, vì nó là cá bố mẹ mà tiêu thụ phấn hoa. Ngoài ra, ong thợ là những con ong trẻ hạn chế hoạt động của chúng đến khu vực bố mẹ (Seeley 1982). Việc loại bỏ ưu đãi của phấn hoa và mật hoa từ các tế bào gần nhất với các tế bào có chứa cá bố mẹ và sở thích của ong chúa để đẻ trứng trong các tế bào gần với hiện thực cá bố mẹ Camazine thực hiện điều này có thể giải thích mô hh nh lược đặc tính của ong mật. Nhưng làm thế nào để chứng minh điều này? Đây là nơi mà các phương pháp của vật lý. Bằng cách xây dựng một mô hình mô phỏng dựa trên những quan sát hành vi của mình, Camazine đã có thể theo sát sáp nhập của các mô hình. Ban đầu, cả hai phấn hoa và mật hoa được gửi ngẫu nhiên trong suốt khung với ong chúa lang thang trên lược từ quan điểm của mình bắt đầu từ ban đầu. Mặc dù lưu trữ ngẫu nhiên của các hạt phấn hoa và mật hoa, xu hướng đẻ trứng trong vùng lân cận của các tế bào mà đã chứa cá bố mẹ của ong chúa nhanh chóng kết quả trong một lĩnh vực mà bố mẹ chủ yếu được tìm thấy. Điều này được tăng cường bởi sở thích của các con ong để loại bỏ mật ong và phấn hoa từ các tế bào gần gũi với bố mẹ, làm tăng sự sẵn có cho ong chúa của các tế bào để đẻ trứng. Điều này làm giảm số lượng của các tế bào có sẵn cho việc lưu trữ của mật ong hoặc phấn hoa. Như vậy, khu vực bố mẹ liên tục tự do của mật ong và phấn hoa và đầy kết quả trứng trong một cấu trúc bố mẹ nhỏ gọn. Nhưng làm thế nào để phấn hoa và mật hoa bị chia cách (Hình 2)? 10 Hình 2.Các mô hình điển hình của mật ong (tế bào màu xám), phấn hoa (tế bào màu trắng), và bố mẹ (các tế bào màu đen) như trên lược của ong mật. Trong ảnh là góc trên bên trái của lược Bởi vì ban đầu cả hai được gửi ngẫu nhiên, cả hai phấn hoa và mật hoa sẽ có mặt ở ngoại vi của lược. Tuy nhiên, hầu hết các phấn hoa mà được thu thập trên một cơ sở hàng ngày được tiêu thụ cùng ngày. Điều này có nghĩa là bình thường dao động trong sẵn sàng phấn hoa, thường có một lỗ của phấn hoa, với hiện tại phấn hoa ở ngoại vi được tiêu thụ ở mức gần tương tự như phấn hoa được lưu trữ ở nơi khác. Đồng thời, các tế bào này có sản phẩm nào có thể được lấp đầy với mật hoa, lượng mật hoa là cao hơn nhiều, và ngay sau đó là không còn không gian để lưu trữ phấn hoa. Được phấn hoa được lưu trữ sau đó? Thời gian phát triển từ trứng đến trưởng thành là 21 ngày, có nghĩa là ba tuần một tế bào bố mẹ không có thể được sử dụng cho bất cứ điều gì khác. Tuy nhiên, trong khu vực giao diện giữa bố mẹ và các cửa hàng mật ong ở ngoại vi, loại bỏ ưu đãi của mật ong và phấn hoa liên tục cung cấp một khu vực trong đó các tế bào được làm trống ở một tỷ lệ tương đối cao. Và nó là những tế bào mà có sẵn cho phấn hoa. Các tế bào khác trở nên có sẵn bởi vì con ong xuất hiện từ họ được tìm thấy ở giữa các tổ bố mẹ, nhưng sau đó sẽ được ưu tiên làm trống và một lần nữa đầy trứng. Nếu không có Camazine mô phỏng máy tính của mình sẽ không thể hiểu đầy đủ về hành vi của những con ong cá nhân trong các mô hình tổ chức, cá bố mẹ của mật ong và phấn hoa trên lược của những con ong. Và đây là một nguyên tắc chung của hành vi động vật tập thể: không có các công cụ như mô phỏng hoặc toán học, nó là không thể dịch hành vi cá nhân vào hành vi tập thể. Và nó là chính xác với những công cụ ban đầu đến từ các ngành bên ngoài của sinh học, và với quan điểm rằng sự tương tác giữa các cá nhân mang lại cái nhìn sâu vào hành vi của tập thể. Trong thực tế, bằng cách minh họa mà ngay cả sinh học henomena có thể thường xuyên hơn parsimoniously được hiểu bằng cách sử dụng giải thích vật lý, và nhiều hệ thống, cả hai bẩm sinh và sinh hoạt, chia sẻ các nguyên tắc vật lý như nhau. Và nó đã chính xác được những tương đồng và 11 áp dụng rộng các quy tắc toán học chi phối hành vi đa dạng đã dẫn đến các lĩnh vực Swarm Intelligence (ví dụ như Dorigo et al 1996; Dorigo và Di Caro 1999). Tuy nhiên, điều quan trọng là nhận ra rằng 'hạt' là phức tạp hơn so với các phân tử và nguyên tử và các "quy tắc đơn giản của ngón tay cái của tổ chức tự (Nicolis và Prigogine 1977) đã chỉ giới hạn quyền lực giải thích khi nói đến hệ thống sinh học(Seeley 2002). Bên cạnh sự phức tạp của các cá nhân, thì không thể bỏ qua chọn lọc tự nhiên diễn xuất.Nếu các nguyên tắc cơ bản chi phối hành vi xây dựng kết quả mối thuộc địa, mức độ hành vi đó là từ chức năng, điều này sẽ được nhanh chóng lựa chọn chống lại. Đó là sự thật rằng nếu cùng một mô hình toán học hoặc thuật toán hành vi nắm bắt được hành vi của các hệ thống khác nhau, sau đó chúng ta có thể nói về sự tương đồng giữa các hệ thống đi xa hơn tương tự đơn giản (Sumpter 2005).  Phân cấp quyết định làm Sự tiến hóa của tính xã hội, hiện tượng cá nhân sống chung với nhau trong một tổ như được tìm thấy trong rất nhiều con ong và ong bắp cày, và tất cả kiến và mối, đã tạo ra nhu cầu chuyển giao thông tin giữa các thành viên trong nhóm. Không còn có thể mỗi cá nhân chỉ đơn giản là cư xử như thể cô độc, nhưng hành động của các thành viên trong nhóm khác nhau cần phải được chỉnh cẩn thận để đạt được hành vi thích ứng ở các mức độ của cả nhóm. Thuộc địa côn trùng cần phải thực hiện nhiều quyết định tập thể, ví dụ như thức ăn gia súc, làm tổ mới để di chuyển đến, khi sinh sản, và làm thế nào để phân chia các nhiệm vụ cần thiết trong số các công việc có sẵn buộc. Để minh họa cách thuộc địa côn trùng đạt được điều này qua viê Êc mô tả di chuyển theo nhóm . Di chuyển theo nhóm Trong nhiều loài động vật, cá nhân di chuyển trong các nhóm khi chúng thực hiện di cư theo mùa, đi đến nguồn thức ăn và trở về nơi trú ẩn an toàn, thường là trên một khoảng cách đáng kể (Boinski và Garber 2000 Krause và Ruxton 2002; Couzin và Krause 2003). Sự chuyển động của các nhóm này thường được phát sinh từ các tương tác địa phương giữa các cá nhân chứ không phải từ một trung tâm chỉ huy phân cấp. Nhóm tự tổ chức phong trào không hạn 12 chế cho các nhóm tương đối đơn giản, sinh vật như bầy côn trùng hoặc trường học của cá, nhưng thậm chí có thể bao gồm các loài 'thông minh' như chúng ta. Có hai cách cực đoan, trong đó nhóm có thể 'quyết định' trên một hướng của phong trào. Hoặc là tất cả các cá nhân trong nhóm đóng góp vào sự đồng thuận, hoặc người nào khác, cá nhân tương đối ít (cho thuận tiện, chúng ta sẽ gọi các nhà lãnh đạo) có thông tin về điểm đến du lịch của nhóm và hướng dẫn phần lớn không hiểu rõ. Như vậy, ở một số loài, tất cả các cá nhân trong một nhóm chia sẻ một xu hướng di truyền xác định đi theo một hướng nhất định (Berthold và Querner 1981; Berthold et al 1992), tất cả đều được tham gia trong việc lựa chọn một hướng đi cụ thể (Neill 1979; Gr ¨ unbaum 1998). Ngược lại, một vài cá nhân thông tin trong một trường học của cá có thể xác định chuyển động tìm kiếm thức ăn của nhóm và có thể chỉ đạo một nhóm hướng tới một mục tiêu (Reebs 2000, Swaney et al. 2001). Tương tự như vậy, cá nhân rất ít (khoảng 5%) trong một đàn ong mật có thể hướng dẫn nhóm đến một trang web tổ mới (Seeley et al. 1979). Khi các nhà lãnh đạo hiện nay, câu hỏi đặt ra là làm thế nào các cá nhân thông báo chuyển thông tin định hướng đến đa số không hiểu rõ. Tương tự như vậy, trong sự vắng mặt của các nhà lãnh đạo như thế nào là sự đồng thuận về hướng đi du lịch? Gần đây, hai nghiên cứu lý thuyết đã giải quyết vấn đề chuyển giao thông tin từ thông báo cho các thành viên nhóm không hiểu rõ. Stefan Janson, Martin Middendorf và Madeleine Beekman (2005) mô hình hóa một tình huống trong đó các cá nhân, thông tin làm cho sự hiện diện của họ được biết đến bằng cách di chuyển ở tốc độ cao hơn so với các thành viên trong nhóm trung bình trong sự chỉ đạo của du lịch. Hướng dẫn của nhóm được thực hiện bởi cá nhân không hiểu rõ việc xếp thẳng hướng của phong trào với các nước láng giềng của họ. Bởi vì các cá nhân thông tin ban đầu di chuyển nhanh hơn, họ có một ảnh hưởng lớn hơn về phong trào hướng của các cá nhân không hiểu rõ, do đó chỉ đạo nhóm. Một mô hình thứ hai bởi Iain Couzin và các cộng sự (2005) cho thấy sự chuyển động của một nhóm có thể được hướng dẫn bởi một vài cá nhân thông tin mà không có những cá nhân cung cấp các tín hiệu hướng dẫn rõ ràng và thậm chí 13 không có bất kỳ cá nhân trong nhóm”được biết” Ao cá nhân đều có thông tin về đi du lịch chỉ đạo. Chỉ có các thành viên thông tin của nhóm có một hướng ưu tiên, và nó là xu hướng của họ để đi theo hướng này để lái nhóm. Sự khác biê tÊ chính giữa hai mô hình nằm trong sự hiện diện hay vắng mặt của các tín hiệu hoặc tín hiệu từ các cá nhân thông tin cho đa số không hiểu rõ. Janson et al, AOS (2005) lãnh đạo. Rõ ràng làm cho sự hiện diện của họ được biết đến, trong khi Couzin et al., AOS (2005) mô hh nh cho thấy rằng lănh đạo có thể phát sinh đơn giản là một chức năng của thông tin khác nhau giữa các cá nhân thông tin và không hiểu rõ, không có các cá nhân không hiểu rõ có thể nói với những người thân mà có thêm thông tin. Có vẻ như có khả năng rằng cơ chế hướng dẫn chính xác là phụ thuộc vào loài. Khi nhóm cần để di chuyển nhanh chóng, ví dụ như 1 bầy ong mật mà không thể chạy nguy cơ mất nữ hoàng của nó trong thời gian , sự hiện diện của các nhà lãnh đạo mà rõ ràng báo hiệu sự hiện diện của họ có thể là cần thiết, như nhóm khác phải mất một thời gian dài để bắt đầu di chuyển vào hướng ưu tiên. Tuy nhiên, khi tốc độ của phong trào là ít quan trọng hơn sự gắn kết nhóm, ví dụ bởi vì trong một nhóm làm giảm cơ hội của loài săn mồi, các nhà lãnh đạo không cần phải báo hiệu sự hiện diện của họ. Nếu không có nhà lãnh đạo, bước đầu tiên cần thiết trước khi một nhóm có thể bắt đầu di chuyển gắn bó khăng khít là sự đồng thuận giữa các cá nhân ơ mô Êt mức đô Ê nào đó trong sự liên kết của họ. Làm thế nào là đạt được khi không có nhà lãnh đạo?Hầu hết khả năng có một số lượng tối thiểu của các cá nhân cần phải được liên kết trong cùng một hướng trước khi nhóm có thể bắt đầu di chuyển theo một hướng cụ thể mà không vi phạm.Nếu số lượng cá nhân đều liên kết bên dưới ngưỡng này, các nhóm không di chuyển gắn bó khăng khít.Ngay sau khi này bị vượt quá ngưỡng, phong trào phối hợp đạt được.Một quá trình chuyển đổi phi tuyến tính ở ngưỡng được biết đến trong lý thuyết vật lý và toán học như là một giai đoạn chuyển tiếp khi phát hiện gần đây, lần đầu tiên, tương tự như quá trình chuyển đổi trong các hệ thống sinh học (Beekman et al 2001). lý thuyết vật lý đã phát triển một bộ các mô hình, gọi là mô hình hạt tự hành (SPP), mà cố 14 gắng để nắm bắt các hiệu ứng chuyển tiếp giai đoạn trong hành vi tập thể (Vicsek et al 1995). SPP mô hình nhằm mục đích để giải thích sự năng động nội tại của các nhóm lớn của cá nhân. Sau đó sẽ hiển thị khuôn khổ lý thuyết này có thể được áp dụng cho sự vận động chung của châu chấu. Nhưng trước tiên sẽ mô tả một số kết quả thử nghiệm về phong trào nhóm trong bầy ong, châu chấu. 1.1.1. Ong mật di chuyển Quyết định nơi để sống chỉ là một phần của vấn đề một đàn ong mật. Vấn đề thứ hai phát sinh khi quyết định đó đã được thực hiện như thế nào số lượng nhỏ các thông tin ong (khoảng 5%) chuyển tải thông tin định hướng cho đa số các con ong không am hiểu trong một cách mà bầy di chuyển trong sự đồng thuâ nÊ ? Trong phần trước đã mô tả hai khả năng lý thuyết: hoặc là lãnh đạo báo hiệu sự hiện diện của chúng phần lớn không hiểu rõ, hoặc chúng không chỉ đơn giản là di chuyển theo hướng ưa thích của chúng. Trong thực tế, mô hình của Janson và các đồng nghiệp đã được lấy cảm hứng từ một đề nghị được thực hiện vào đầu những năm 1950 bởi Martin Lindauer (1955). Lindauer quan sát thấy trong bầy trong không khí mà một số con ong bay qua các đám mây đám ở tốc độ cao và theo hướng du lịch chính xác, dường như "chỉ hướng đến các trang web tổ mới. Ông đề nghị rằng những con ong bay nhanh, sau đó đặt tên 'streakers (Beekman et al, 2006), là các cá nhân, thông tin hoặc các trinh sát. Một trong các trang web lĩnh vực của mình là gần một bệnh viện tâm thần và tin đồn có một ngày, anh được nhầm lẫn với một bệnh nhân bị bệnh tâm thần (Tom Seeley, thông tin liên lạc cá nhân). May mắn thay, Lindauer chạy nhanh hơn so với các vệ sĩ đã cố gắng để bắt kịp anh ta, trong đó cung cấp cho một một dấu hiệu của cách nhanh chóng một bầy ong ruồi! Một thay thế cho giả thuyết của Lindauer (mà chúng ta sẽ chỉ là giả thuyết 'tầm nhìn') là giả thuyết khứu giác của Avitabile et al. (1975). Họ đề xuất rằng các trinh sát cung cấp hướng dẫn bằng cách giải phóng pheromone lắp ráp từ Nasanov tuyến của họ (1 tuyến giữa của 2 tergites cuối cùng của bụng các của ong) vào 1 bên của các đám mây bầy đàn, do đó tạo ra 1 Gradient mùi đó có thể 15 hướng dẫn các con ong khác trong bầy. Cho đến gần đây không phải là giả thuyết tầm nhìn cũng không phải giả thuyết khứu giác đã được thử nghiệm thực nghiệm, mặc dù các nhà điều tra đã xác nhận báo cáo Lindauer có streakers trong bầy bay (Seeley et al 1979; Dyer 2000). Madeleine Beekman, của Rob Fathke và các Tom Seeley (2006) đã quyết định rằng đó là thời gian để làm sáng tỏ về vấn đề này. Trong nghiên cứu này, họ đã làm hai điều. Họ đã nghiên cứu chi tiết các chuyến bay của bầy ong mật bình thường (có chứa khoảng 15.000 con ong) và nhỏ hơn (4,000-5,000 ong) bầy trong đó tuyến Nasanov của ong đã được niêm phong đóng cửa bằng cách áp dụng sơn để mọi ong duy nhất trong bầy đàn. Điều này có nghĩa rằng bầy kín-ong không thể phát ra pheromone Nasanov (họ đã có để áp dụng sơn cho tất cả các con ong trong bầy bởi vì họ không có phương tiện biết con ong sẽ được các tuyển trạch viên). Bằng cách sử dụng một trang web baitnest rằng họ đã làm cực kỳ hấp dẫn một bầy ong, họ có thể là gần như chắc chắn rằng bầy của họ sẽ chọn trang web đó làm tổ. Điều này cho phép họ thực hiện theo bầy đàn (như Lindauer đã thông qua Munich, mặc dù họ sử dụng một trường mở), đo tốc độ của nó và thời gian nó đã bầy đàn để giải quyết trong ngôi nhà mới của nó. Sử dụng thủ tục này và một số bầy ong kín, cho phép họ để cho thấy rằng ngay cả khi mỗi con ong duy nhất trong bầy là không thể sản xuất các pheromone Nasanov, bầy đàn vẫn có thể bay nhiều hơn hoặc ít trực tiếp hướng tới các trang web tổ mới. Từ đó họ kết luận rằng các tuyển trạch viên không sử dụng pheromone để hướng dẫn bầy. Chứng minh các giả thuyết tầm nhìn là khó khăn hơn.Họ quyết định rằng một bước đầu tiên sẽ là để cho thấy rằng có sự thay đổi về tốc độ bay và hướng bay trong số những con ong cá nhân trong một đám bay bằng cách chụp ảnh của một đám lớn trong suốt chuyến bay của mình để tổ mồi như những con ong cá nhân xuất hiện như là nhỏ,vệt tối trên nền sáng. Các nhanh hơn tốc độ bay của một con ong, còn vệt sản xuất bằng cách sử dụng kỹ thuật này (con ong bay trong mặt phẳng của tầm nhìn). Mỗi bức ảnh được phân tích bằng cách chiếu lên một bề mặt màu trắng để tạo ra một hình ảnh mở rộng. Sau đó, họ đo chiều dài (mm) và góc (theo độ, tương đối so với chiều ngang) của mỗi vệt tối ở tập trung 16 trong hình ảnh mở rộng. Bởi vì một tham chiếu kích thước mặt trong mỗi bức ảnh, và bởi vì mỗi bức ảnh ghi lại sự di chuyển của ong trong một khoảng thời gian được biết đến (1/30 s), họ đã có thể tính toán cho mỗi bức ảnh là yếu tố chuyển đổi giữa chiều dài vệt và tốc độ bay. Sử dụng thủ tục này, họ có thể định lượng những gì họ thấy trong khi đang chạy với bầy: một phần của những con ong bay nhanh hơn nhiều trong sự chỉ đạo của du lịch trong khi đa số các con ong bay chậm hơn nhiều và với các đường bay cong. Hơn nữa, những con ong bay nhanh, các streakers, xuất hiện phổ biến nhất trong khu vực trên của bầy đàn. Đối với con người, và có lẽ cũng cho ong, streakers nhiều hơn nữa dễ dàng nhìn thấy trên bầu trời tươi sáng hơn là mặt đất tối hoặc thực vật, như vậy bằng cách bay trên hầu hết các con ong trong bầy, các streakers này có thể được tạo điều kiện thuận lợi cho việc chuyển giao thông tin chỉ đạo của họ để những con ong khác. Công việc trong tương lai nên tập trung vào xác định nếu nó thực sự là streakers các trinh sát, những người có thông tin về vị trí của các trang web tổ mới. 1.1.2.Châu chấu. Đến thời điểm này chúng ta đã xem xét ví dụ tự tổ chức và trí thông minh bầy đàn cao cấu trúc các nhóm xã hội, trong đó có sự phân biệt giữa các cá nhân sinh sản và công nhân nhiều hơn hoặc ít vô trùng và phân chia rõ rệt của lao động giữa người lao động.Nhưng không phải tất cả các nhóm động vật gắn bó khăng khít hành xử như vậy cấu trúc.Một số bao gồm các cá nhân cơ bản là tất cả như nhau. Và, như chúng ta sẽ thấy trong phần tiếp theo, các lực lượng mà ràng buộc và thúc đẩy các nhóm như vậy có thể được thực sự rất nham hiểm. Trong phần lớn thời gian giống như bất kỳ con châu chấu vô hại khác nhưng, đôi khi, catastrophically, chúng thay đổi và thay vì sống cuộc sống đơn độc, sản xuất lớn, quy tụ di cư. Khi chưa thành niên chúng hình thành các ban nhạc diễu hành. mở rộng cho km. Một khi trở nên trưởng thành có cánh,chúng có thể di cư là hàng trăm km vuông trong khu vực và du lịch hàng trăm cây số mỗi ngày. Hơn 1/5 bề mặt đất của trái đất là nguy cơ từ bệnh dịch này và sinh kế của một trong mười người trên hành tinh có thể bị ảnh hưởng. 17 Tại trung tâm của sự hình thành bầy đàn và di cư là sự chuyển đổi từ hành vi nhút nhát, khó hiểu của châu chấu giai đoạn solitarious, mà là tương đối ít vận động và tránh nhau, hành vi hoạt động rất mạnh và xu hướng tổng hợp điển hình của côn trùng giai đoạn sống thành bầy. Trong những năm gần đây tiến bộ đã được thực hiện trong việc hiểu cơ chế sinh lý và thần kinh kiểm soát giai đoạn thay đổi hành vi trong châu chấu. Châu chấu sa mạc gợi gregarization hành vi kích thích kinh tế trọng điểm là kích thích các thụ thể cảm ứng nhạy cảm trên chân sau (nhảy). Các thụ thể thông qua dự án xác định các con đường thần kinh đến hệ thống thần kinh trung ương và gây ra phát hành một bộ thần kinh điều biến, trong đó có serotonin bắt đầu quá trình chuyển đổi thông qua hành động của nó trên các mạch thần kinh kiểm soát hành vi (Simpson et al 2001;. Rogers và cộng sự năm 2003. 2004; Anstey et al, chưa xuất bản). Đặc điểm giai đoạn, bao gồm cả hành vi, không chỉ thay đổi trong cuộc sống của một cá nhân, họ cũng epigenetically tích lũy qua nhiều thế hệ (Simpson et al 1999; Simpson và Miller 2007).Các nữ Solitarious sản xuất con non được tập tính gregarized đến một mức độ phản ánh mức độ và recency của đông đúc mẹ. Nếu lần đầu tiên tại thời điểm đẻ trứng của mình, người mẹ sẽ sản xuất đầy đủ theo bầy hành vi con cái. Ngược lại, nếu con cái sống thành bầy thấy mình một mình khi đẻ trứng, nó sẽ sản xuất một phần tính hành động solitarized trẻ (đạo Hồi et al 1994a, b;. Boua ¨ ichi et al 1995). Hiệu quả gregarizing được trung gian bởi một chất hóa học mà người mẹ sản xuất trong tuyến phụ kiện sinh sản của mình và cho biết thêm để bọt trứng trong đó cô đẻ trứng của mình trong đất (McCaffery et al 1998). Trong hiệu lực, châu chấu cái sử dụng kinh nghiệm của mình được đông đảo dự đoán mật độ dân số trẻ của chúng sẽ trải nghiệm khi đang nổi lên từ trứng và predispose để hành xử một cách thích hợp. Như một kết quả thay đổi giai đoạn tích lũy qua nhiều thế hệ. nhóm hình thành Giai đoạn thay đổi hành vi trong phạm vi cá nhân thiết lập một vòng phản hồi tích cực, trong điều kiện môi trường thích hợp thúc đẩy sự chuyển đổi nhanh chóng của dân số từ solitarious giai đoạn sống thành bầy. Nếu có thể, châu chấu 18 solitarious sẽ tránh nhau. Tuy nhiên, nếu môi trường buộc chúng đến với nhau, tiếp xúc gần gũi giữa các cá nhân sẽ nhanh chóng tạo ra việc chuyển đổi từ tránh để tập hợp hoạt động, mà sẽ lần lượt thúc đẩy gregarization hơn nữa và dẫn đến hình thành các nhóm. Cho rằng giai đoạn sống thành bầy châu chấu di cư và di chuyển cùng nhau, hoặc như các ban nhạc diễu hành của người chưa thành niên hoặc các đám trưởng thành có cánh, có khả năng rằng các nhóm địa phương kết hợp lại, cuối cùng giống hình thành những đàn lớn trong khu vực. Ngược lại, khi các cá nhân tổng hợp trước đó tách ra, chúng sẽ bắt đầu solitarize, do đó làm giảm xu hướng để tổng hợp và do đó, thúc đẩy solitarization hơn nữa. Nếu môi trường sống có xu hướng để giữ cho châu chấu ngoài, sau đó cuối cùng sẽ dẫn đến resolitarization của một dân số sống thành bầy. Thật thú vị, việc chuyển đổi từ solitarious để sống thành bầy xảy ra nhanh hơn quá trình chuyển đổi ngược lại (Roessingh và Simpson 1994), cho thấy một hiệu ứng trễ. Các mối quan hệ giữa phân bổ nguồn lực, nguồn tài nguyên phong phú, và quy mô dân số châu chấu đã được khám phá bằng cách sử dụng các mô phỏng máy tính dựa trên cá nhân, tham số bằng cách sử dụng các dữ liệu thử nghiệm từ châu chấu (Collett et al 1998). Mức độ gregarization trong một gia tăng dân số mô phỏng với mật độ tăng dân số châu chấu và kết khối càng tăng của nguồn thức ăn. Khu vực quan trọng mà tại đó quần thể solitarious gregarize chóng xuất hiện trong mô hình trên kết hợp đặc biệt của sự phong phú tài nguyên, phân phối nguồn lực và quy mô dân số. Dữ liệu thử nghiệm sau đó hỗ trợ các dự đoán từ các mô hình mô phỏng (Despland et al 2000). Các mô hình không gian của phân phối thực phẩm tương tác với chất lượng dinh dưỡng của thực phẩm để xác định sự lây lan của giai đoạn thay đổi trong dân số địa phương (Despland và Simpson 2000b). Tác dụng dinh dưỡng được trung gian thông qua sự khác biệt trong phong trào châu chấu (Simpson và Raubenheimer 2000). Côn trùng cung cấp các bản vá lỗi thực phẩm kém chất lượng được đánh giá cao hoạt động và có khả năng liên lạc với nhau và gregarize ngay cả khi bản vá lỗi thực phẩm không co cụm. Ngược lại, châu chấu với các bản vá lỗi thực phẩm dinh dưỡng tối ưu không di chuyển ra xa sau khi ăn, dẫn 19 đến hạn chế tương tác vật lý giữa các cá nhân, ngay cả khi bản vá lỗi thực phẩm được đánh giá cao clumped. Rõ ràng là quy mô nhỏ các tính năng của môi trường sống như chất lượng tài nguyên, sự phong phú và phân phối có thể thúc đẩy hoặc cản trở việc thay đổi giai đoạn trong vòng dân địa phương.Các mô hình tương tự dường như áp dụng ở quy mô trung gian của một số lượng nhỏ km (Babah và Sword, 2004), nhưng quy mô không gian cao hơn mối quan hệ giữa phân bố thảm thực vật và sa mạc châu chấu dịch thay đổi quá trình sinh thái khác nhau đi vào chơi.Ở quy mô các nhà máy cá nhân, một môi trường sống bị phân mảnh với nhiều phân tán các bản vá lỗi khuyến khích solitarization, trong khi ở quy mô cảnh quan mô hình đảo ngược lại: phân mảnh môi trường sống mang đến cho châu chấu di cư với nhau và khuyến khích dịch (Despland et al 2004). Hiểu biết về mô hình của phong trào tập thể trên địa phương với quy mô cảnh quan đòi hỏi phải trả lời hai câu hỏi: những gì gây ra các ban nhạc diễu hành rầy (giai đoạn vị thành niên) và người lớn bay vẫn là nhóm gắn kết, và những gì làm cho chúng di chuyển đồng bộ và chung giữa các bản vá lỗi ở quy mô khác nhau?tập thể Phong trào Các aggregations Locust sẽ xây dựng thành dịch lớn nếu dân số tại địa phương gregarized vẫn còn lại với nhau và di chuyển chung vào các khu vực lân cận của môi trường sống, nơi họ có thể tuyển dụng châu chấu tiếp tục ban nhạc đang phát triển. Trừ khi phong trào gắn kết như vậy xảy ra, các aggregations địa phương sẽ giải tán và các cá nhân sẽ quay trở lại giai đoạn solitarious. Trong thời hạn ban nhạc diễu hành của châu chấu vị thành niên, cá nhân có xu hướng để đồng bộ hóa và sắp xếp các hướng dẫn của họ đi du lịch với những người hàng xóm gần (Despland và Simpson năm 2006). Nó đã được thể hiện trong phòng thí nghiệm diễu hành bắt đầu với mật độ châu chấu cao (Ellis, 1951), nhưng những thí nghiệm này không đo lường như thế nào và tại sao gia tăng sự liên kết với mật độ điểm là một tập hợp châu chấu đột nhiên bắt đầu diễu hành tập thể. 20